Fcfs round что это

Fcfs round что это

Глава 3. Планирование процессов

“Я планов наших люблю громадьё…”
В. В. Маяковский

“Чем тщательнее мы планируем свою деятельность,
тем меньше времени остается на ее осуществление.”
Из анналов Госплана

Всякий раз, когда нам приходится иметь дело с ограниченным количеством ресурсов и несколькими их потребителями, будь то фонд заработной платы в трудовом коллективе или студенческая вечеринка с несколькими ящиками пива, мы вынуждены заниматься распределением наличных ресурсов между потребителями или, другими словами, планированием использования ресурсов. Такое планирование должно иметь четко поставленные критерии (чего мы хотим добиться распределением ресурсов) и алгоритмы, соответствующие критериям и опирающиеся на параметры потребителей. Только при правильном выборе критериев и алгоритмов можно избежать таких вопросов, как “Почему я получаю в десять раз меньше, чем мой шеф?” или “А где мое пиво?”. Настоящая глава посвящена планированию исполнения процессов в мультипрограммных вычислительных системах или, кратко говоря, планированию процессов.

3.1. Уровни планирования

Планирование использования процессора выступает в качестве краткосрочного планирования процессов. Оно проводится, к примеру, при обращении исполняющегося процесса к устройствам ввода-вывода или просто по завершении определенного интервала времени. Поэтому краткосрочное планирование осуществляется весьма часто, как правило, не реже одного раза в 100 миллисекунд. Выбор нового процесса для исполнения оказывает влияние на функционирование системы до наступления очередного аналогичного события, т. е. в течение короткого промежутка времени, что и обусловило название этого уровня планирования — краткосрочное.

В некоторых вычислительных системах бывает выгодно для повышения их производительности временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения. Такая процедура в англоязычной литературе получила название swapping, что можно перевести на русский язык как перекачка, хотя в профессиональной литературе оно употребляется без перевода — свопинг. Когда и какой из процессов нужно перекачать на диск и вернуть обратно, решается дополнительным промежуточным уровнем планирования процессов — среднесрочным.

3.2. Критерии планирования и требования к алгоритмам

Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы хотим достичь, используя планирование. К числу таких целей можно отнести:

Независимо от поставленных целей планирования желательно также, чтобы алгоритмы обладали следующими свойствами:

Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного критерия, мы ухудшаем ее с точки зрения другого. Приспосабливая алгоритм под один класс задач, мы тем самым дискриминируем задачи другого класса. “В одну телегу впрячь не можно коня и трепетную лань”. Ничего не поделаешь. Такова жизнь.

3.3. Параметры планирования

Для осуществления поставленных целей разумные алгоритмы планирования должны опираться на какие-либо характеристики процессов в системе, заданий в очереди на загрузку, состояния самой вычислительной системы, иными словами, на параметры планирования. В этом разделе мы опишем ряд таких параметров, не претендуя на полноту изложения.

Все параметры планирования можно разбить на две большие группы: статические параметры и динамические параметры. Статические параметры не изменяются в ходе функционирования вычислительной системы, динамические же, напротив, подвержены постоянным изменениям.

К статическим параметрам вычислительной системы можно отнести предельные значения ее ресурсов (размер оперативной памяти, максимальное количество памяти на диске для осуществления свопинга, количество подключенных устройств ввода-вывода и т. п.). Динамические параметры системы описывают количество свободных ресурсов в текущий момент времени.

К статическим параметрам процессов относятся характеристики, как правило, присущие заданиям уже на этапе загрузки:

Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик может выступать следующая информация:

Рис 3.1. Фрагмент деятельности процесса с выделением промежутков непрерывного использования процессора и ожидания ввода-вывода.

Для краткосрочного планирования нам понадобится ввести еще два динамических параметра. Деятельность любого процесса можно представить как последовательность циклов использования процессора и ожидания завершения операций ввода-вывода. Промежуток времени непрерывного использования процессора носит на английском языке название CPU burst, а промежуток времени непрерывного ожидания ввода-вывода – I/O burst. На рисунке 3.1. показан фрагмент деятельности некоторого процесса на псевдоязыке программирования с выделением указанных промежутков. Для краткости изложения мы будем использовать термины CPU burst и I/O burst без перевода. Значения продолжительности последних и очередных CPU burst и I/O burst являются важными динамическими параметрами процесса.

3.4. Вытесняющее и невытесняющее планирование

Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет использовать большую часть процессорного времени на работу самих процессов и до минимума сократить затраты на переключение контекста. Однако при невытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.

3.5. Алгоритмы планирования

Существует достаточно большой набор разнообразных алгоритмов планирования, которые предназначены для достижения различных целей и эффективны для разных классов задач. Многие из них могут быть использованы на нескольких уровнях планирования. В этом разделе мы рассмотрим некоторые наиболее употребительные алгоритмы применительно к процессу кратковременного планирования.

3.5.1. First-Come, First-Served (FCFS)

Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения своего текущего CPU burst. После этого для выполнения выбирается новый процесс из начала очереди.

Продолжительность очередного CPU burst

Рис 3.2. Выполнение процессов при порядке p₀,p₁,p₂

Рис 3.3. Выполнение процессов при порядке p₂,p₁,p₀

Как видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала своего выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени. Слишком большим получается среднее время отклика в интерактивных процессах.

3.5.2. Round Robin (RR)

Рис 3.4. Процессы на карусели.

Источник

17) алгоритм планирования FCFS

Что такое метод «первым пришел, первым обслужен»?

First Come First Serve (FCFS) — это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления. Это самый простой и простой алгоритм планирования процессора. В алгоритме этого типа процессы, которые сначала запрашивают ЦП, сначала получают распределение ЦП. Это управляется с помощью очереди FIFO. Полной формой FCFS является First Come First Serve.

Когда процесс входит в готовую очередь, его PCB (блок управления процессом) связывается с хвостом очереди и, когда ЦП становится свободным, его следует назначить процессу в начале очереди.

Из этого руководства по операционной системе вы узнаете:

Характеристики метода FCFS

Пример планирования FCFS

Реальный пример метода FCFS — покупка билета в кино на кассе. В этом алгоритме планирования человек обслуживается согласно порядку очереди. Человек, который прибывает первым в очереди, сначала покупает билет, а затем следующий. Это будет продолжаться до тех пор, пока последний человек в очереди не купит билет. Используя этот алгоритм, процесс ЦП работает аналогичным образом.

Как работает FCFS? Расчет среднего времени ожидания

Вот пример пяти процессов, прибывающих в разное время. Каждый процесс имеет разное время посылки.

Используя алгоритм планирования FCFS, эти процессы обрабатываются следующим образом.

Шаг 0) Процесс начинается с P4, который имеет время прибытия 0

Шаг 1) В момент времени = 1 приходит P3. P4 все еще выполняется. Следовательно, P3 хранится в очереди.

Шаг 2) В момент времени = 2 прибывает P1, который сохраняется в очереди.

Шаг 3) В момент времени = 3 процесс P4 завершает свое выполнение.

Шаг 4) В момент времени = 4, P3, который является первым в очереди, начинает выполнение.

Источник

Fcfs round что это

Алгоритмы планирования процессов

Приложение на платформе WPF, позволяющее симулировать работу алгоритмов FCFS, Round Robin, SJF, Priority. Результат работы выбранного алгоитма планирования представлен в виде Столбчатой диаграммы.

Основные понятия планирования процессов

Задачи алгоритмов планирования

Для всех систем

Контроль над выполнением принятой политики

Системы пакетной обработки

Интерактивные системы

Системы реального времени

FCFS (first come – first serve; первым пришел – первым обслуживается) – простейший алгоритм, работа, которой понятна из ее названия. Это алгоритм без вытеснения, то есть процесс, выбранный для выполнения на ЦП, не прерывается, пока не завершится (или не перейдет в состояние ожидания по собственной инициативе). FCFS обеспечивает минимум накладных расходов. Среднее потерянное время при применении этого алгоритма не зависит от длительности процесса, но штрафное отношение при равном потерянном времени будет большим для коротких процессов. Поэтому алгоритм FCFS считается лучшим для длинных процессов. Существенным достоинством этого алгоритма наряду с его простотой является то обстоятельство, что FCFS гарантирует отсутствие бесконечного откладывания процессов: любой поступивший в систему процесс будет, в конце концов, выполнен независимо от степени загрузки системы.

RR (round robin – карусель) – простейший алгоритм с вытеснением. Процесс получает в свое распоряжение ЦП на некоторый квант времени Q (в простейшем случае размер кванта фиксирован). Если за время Q процесс не завершился, он вытесняется из ЦП и направляется в конец очереди готовых процессов, где ждет выделения ему следующего кванта, и т.д. Показатели эффективности RR существенно зависят от выбора величины кванта Q. RR обеспечивает наилучшие показатели, если длительность большинства процессов приближается к размеру кванта, но не превосходит его. Тогда большинство процессов укладываются в один квант и не становятся в очередь повторно.

SJF (shortest job first – самая короткая работа – первой) – невытесняющий алгоритм, в котором наивысший приоритет имеет самый короткий процесс. Для того чтобы применять этот алгоритм, должна быть известна длительность процесса – задаваться пользователем или вычисляться методом экстраполяции. Для коротких процессов SJN обеспечивает лучшие показатели, чем RR, как по потерянному времени, так и по штрафному отношению. SJN обеспечивает максимальную пропускную способность системы – выполнение максимального числа процессов в единицу времени, но показатели для длинных процессов значительно худшие, а при высокой степени загрузки системы активизация длинных процессов может откладываться до бесконечности.

Окно программы имеет три области:

В области процесс задается такт его появления, CPU Burst, приоритет (в случае если будет использоваться алгоритм Priority, в выполнении других алгоритмов планирования это значение роли не играет).

После ввода корретных значений активируется кнопка «Добавить процесс», нажатие на которую приводит к добавлению процесса в таблицу.

В области Результатов показано среднее время ожидания процессов и среднее время выполнения. Также в таблице отобразится тик начала выполнения процесса в графе Start и тик окончания в графе Finish.

Чтобы изменить алгоритм планирования или добавить другие процессы, нужно нажать кнопку Сброс. При этом ранее добавленные процессы не удалятся, удалить их можно путем выделения в таблице и нажатия клавиши Delete.

После сброса можно добавить процессы, заново выбрать алгоритм планирования и вновь симулировать процесс работы выбранного алгоритма.

About

Приложение на платформе WPF, позволяющее симулировать работу алгоритмов FCFS, Round Robin, SJF, Priority.

Источник

Система управления вводом-выводом

Алгоритмы планирования запросов к жесткому диску

Прежде чем приступить к непосредственному изложению самих алгоритмов, давайте вспомним внутреннее устройство жесткого диска и определим, какие параметры запросов мы можем использовать для планирования.

Строение жесткого диска и параметры планирования

Современный жесткий магнитный диск представляет собой набор круглых пластин, находящихся на одной оси и покрытых с одной или двух сторон специальным магнитным слоем (см. рис. 13.2). Около каждой рабочей поверхности каждой пластины расположены магнитные головки для чтения и записи информации. Эти головки присоединены к специальному рычагу, который может перемещать весь блок головок над поверхностями пластин как единое целое. Поверхности пластин разделены на концентрические кольца, внутри которых, собственно, и может храниться информация. Набор концентрических колец на всех пластинах для одного положения головок (т. е. все кольца, равноудаленные от оси) образует цилиндр. Каждое кольцо внутри цилиндра получило название дорожки (по одной или две дорожки на каждую пластину). Все дорожки делятся на равное число секторов. Количество дорожек, цилиндров и секторов может варьироваться от одного жесткого диска к другому в достаточно широких пределах. Как правило, сектор является минимальным объемом информации, которая может быть прочитана с диска за один раз.

При работе диска набор пластин вращается вокруг своей оси с высокой скоростью, подставляя по очереди под головки соответствующих дорожек все их сектора. Номер сектора, номер дорожки и номер цилиндра однозначно определяют положение данных на жестком диске и, наряду с типом совершаемой операции – чтение или запись, полностью характеризуют часть запроса, связанную с устройством, при обмене информацией в объеме одного сектора.

При планировании использования жесткого диска естественным параметром планирования является время, которое потребуется для выполнения очередного запроса. Время, необходимое для чтения или записи определенного сектора на определенной дорожке определенного цилиндра, можно разделить на две составляющие: время обмена информацией между магнитной головкой и компьютером, которое обычно не зависит от положения данных и определяется скоростью их передачи (transfer speed), и время, необходимое для позиционирования головки над заданным сектором, – время позиционирования (positioning time). Время позиционирования, в свою очередь, состоит из времени, необходимого для перемещения головок на нужный цилиндр, – времени поиска (seek time) и времени, которое требуется для того, чтобы нужный сектор довернулся под головку, – задержки на вращение (rotational latency). Времена поиска пропорциональны разнице между номерами цилиндров предыдущего и планируемого запросов, и их легко сравнивать. Задержка на вращение определяется довольно сложными соотношениями между номерами цилиндров и секторов предыдущего и планируемого запросов и скоростями вращения диска и перемещения головок. Без знания соотношения этих скоростей сравнение становится невозможным. Поэтому естественно, что набор параметров планирования сокращается до времени поиска различных запросов, определяемого текущим положением головки и номерами требуемых цилиндров, а разницей в задержках на вращение пренебрегают.

Алгоритм First Come First Served (FCFS)

Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно длительному общему времени обслуживания запросов. Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63-м цилиндре. Тогда положение головок будет меняться следующим образом:

и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма хорошо иллюстрируется двумя последними перемещениями с 7 цилиндра через весь диск на 84 цилиндр и затем опять через весь диск на цилиндр 10. Простая замена порядка двух последних перемещений (7 10 84) позволила бы существенно сократить общее время обслуживания запросов. Поэтому давайте перейдем к рассмотрению другого алгоритма.

Алгоритм Short Seek Time First (SSTF)

и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож на алгоритм SJF планирования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянно группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.

Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Очевидно, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67-го цилиндра в промежуток между запросами 7-го и 84-го цилиндров, мы уменьшим общее время обслуживания. Это наблюдение приводит нас к идее целого семейства других алгоритмов – алгоритмов сканирования.

Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)

В простейшем из алгоритмов сканирования – SCAN – головки постоянно перемещаются от одного края диска до другого, по ходу дела обслуживая все встречающиеся запросы. По достижении другого края направление движения меняется, и все повторяется снова. Пусть в предыдущем примере в начальный момент времени головки двигаются в направлении уменьшения номеров цилиндров. Тогда мы и получим порядок обслуживания запросов, подсмотренный в конце предыдущего раздела. Последовательность перемещения головок выглядит следующим образом:

и всего головки переместятся на 147 цилиндров.

Если мы знаем, что обслужили последний попутный запрос в направлении движения головок, то мы можем не доходить до края диска, а сразу изменить направление движения на обратное:

По аналогии с алгоритмом LOOK для алгоритма SCAN можно предложить и алгоритм C-LOOK для алгоритма C-SCAN :

Существуют и другие разновидности алгоритмов сканирования, и совсем другие алгоритмы, но мы на этом закончим, ибо было сказано: «И еще раз говорю: никто не обнимет необъятного».

Заключение

Часть функций базовой подсистемы может быть делегирована драйверам устройств и самим устройствам ввода-вывода.

Источник

Алгоритмы планирования операционной системы

Планировщик процессов планирует различные процессы, которые должны быть назначены ЦПУ на основе определенных алгоритмов планирования. Существует шесть популярных алгоритмов планирования процессов, которые мы собираемся обсудить в этой главе:

First Come First Serve (FCFS)

Время ожидания каждого процесса выглядит следующим образом —

Среднее время ожидания: (0 + 4 + 6 + 13) / 4 = 5,75

Кратчайшая работа следующая (SJN)

Это не упреждающий, упреждающий алгоритм планирования.

Лучший подход для минимизации времени ожидания.

Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.

Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.

Процессор должен заранее знать, сколько времени займет процесс.

Это не упреждающий, упреждающий алгоритм планирования.

Лучший подход для минимизации времени ожидания.

Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.

Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.

Процессор должен заранее знать, сколько времени займет процесс.

Дано: таблица процессов и время их прибытия, время выполнения

Время ожидания каждого процесса выглядит следующим образом —

Среднее время ожидания: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Источник