10. Алгоритмы планирования. Fcfs. Rr. Sjf.
Существует достаточно большой набор разнообразных алгоритмов планирования, которые предназначены для достижения различных целей и эффективны для разных классов задач.
First-Come, First-Served (FCFS)
Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS (First-Come, First-Served). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO.
Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков.
Алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах.
Round Robin
Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным
Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта.
- Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst), меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново.
- Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.
На производительность алгоритма RR сильно влияет величина кванта времени
Shortest-Job-First (SJF)
SJF-алгоритм краткосрочного планирования может быть как вытесняющим, так и невытесняющим. При невытесняющем SJF-планировании процессор предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в вычислительной системе. При вытесняющем SJF-планировании учитывается появление новых процессов в очереди готовых к исполнению (из числа вновь родившихся или разблокированных) во время работы выбранного процесса. Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося, то исполняющийся процесс вытесняется новым.
Основную сложность при реализации алгоритма SJF представляет невозможность точного знания продолжительности очередного CPU burst для исполняющихся процессов
Первым пришел, первым обслужен (fcfs) — определение из techopedia
Определение — что означает «первым пришел, первым обслужен» (FCFS)?
«Сначала пришел, первым обслужен» (FCFS) — это алгоритм планирования процессов операционной системы и механизм управления сетевой маршрутизацией, который автоматически выполняет запросы и процессы, поставленные в очередь, в порядке их поступления. С первым пришел, первым обслужен, то, что приходит первым, обрабатывается первым; следующий запрос в строке будет выполнен один раз до того, как он будет завершен.
FCFS также известен как «первым пришел, первым вышел» (FIFO) и «первым пришел, первым выбрал» (FCFC)
Техопедия объясняет «первым пришел, первым обслужен» (FCFS)
FCFS предоставляет эффективный, простой и безошибочный алгоритм планирования процессов, который экономит ценные ресурсы процессора. Он использует неперегрузочное планирование, при котором процесс автоматически ставится в очередь, а обработка происходит в соответствии с входящим запросом или технологическим заказом. FCFS основывается на реальном обслуживании клиентов.
Давайте посмотрим, как работает планирование процессов FCFS. Предположим, в очереди три процесса: P1, P2 и P3. P1 помещается в регистр обработки со временем ожидания ноль секунд и 10 секунд для полной обработки. Следующий процесс, P2, должен ждать 10 секунд и помещается в цикл обработки, пока не будет обработан P1. Предполагая, что для завершения P2 потребуется 15 секунд, последний процесс, P3, должен ждать 25 секунд для обработки. FCFS может быть не самым быстрым алгоритмом планирования процессов, так как он не проверяет приоритеты, связанные с процессами. Эти приоритеты могут зависеть от времени выполнения отдельных процессов.
Авторы Techopedia
Techopedia — это словарь для компьютерных терминов и технических определений
Облако тегов всех терминов на techopedia.com
Облако тегов всех Условий на Techopedia.com
First-Come, First-Served (FCFS)
Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First-Come, First-Served (первым пришел, первым обслужен).
Представим себе, что процессы, находящиеся в состоянии
готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его РСВ помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его РСВ. Очередь подобного типа имеет в программировании специальное наименование — FIFO, сокращение от First In, First Out (первым вошел, первым вышел)[2].
Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPU burst. После этого для выполнения выбирается новый процесс из начала очереди.
Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков.
Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса — ро, pi и Р2, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 3.1 в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.
Если процессы расположены в очереди процессов, готовых к исполнению, в порядке ро, pi, Р2, то картина их выполнения выглядит так, как показано на рисунке 3.2.
Первым для выполнения выбирается процесс ро, который получает процессор на все время своего CPU burst, т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс pi, он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс Р2- Время ожидания для процесса ро составляет 0 единиц времени, для процесса pi — 13 единиц, для процесса Р2 — 13 + 4= 17 единиц. Таким образом, среднее время ожидания в этом случае — (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса ро составляет 13 единиц времени, для процесса pi — 13 + 4 = 17 единиц, для процесса рг — 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.
Если те же самые процессы расположены в порядке р2, рь ро, то картина их выполнения будет соответствовать рисунку 3.3. Время ожидания для процесса ро равняется 5 единицам времени, для процесса р] — 1 единице, для процесса Р2 — 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса ро получается равным 18 единицам времени, для процесса р| — 5 единицам, для процесса Р2 — 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что в 2 раза меньше, чем при первой расстановке процессов.
Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени — слишком большим получается среднее время отклика в интерактивных процессах.
17) алгоритм планирования FCFS
Что такое метод «первым пришел, первым обслужен»?
First Come First Serve (FCFS) – это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления. Это самый простой и простой алгоритм планирования процессора. В алгоритме этого типа процессы, которые сначала запрашивают ЦП, сначала получают распределение ЦП. Это управляется с помощью очереди FIFO. Полной формой FCFS является First Come First Serve.
Когда процесс входит в готовую очередь, его PCB (блок управления процессом) связывается с хвостом очереди и, когда ЦП становится свободным, его следует назначить процессу в начале очереди.
Из этого руководства по операционной системе вы узнаете:
- Что такое метод «первым пришел, первым обслужен»?
- Характеристики метода FCFS
- Пример планирования FCFS
- Как работает FCFS? Расчет среднего времени ожидания
- Преимущества FCFS
- Недостатки FCFS
Характеристики метода FCFS
- Он поддерживает алгоритм упреждающего и упреждающего планирования.
- Задания всегда выполняются в порядке поступления.
- Это легко реализовать и использовать.
- Этот метод имеет низкую производительность, и общее время ожидания довольно велико.
Пример планирования FCFS
Реальный пример метода FCFS – покупка билета в кино на кассе. В этом алгоритме планирования человек обслуживается согласно порядку очереди. Человек, который прибывает первым в очереди, сначала покупает билет, а затем следующий. Это будет продолжаться до тех пор, пока последний человек в очереди не купит билет. Используя этот алгоритм, процесс ЦП работает аналогичным образом.
Как работает FCFS? Расчет среднего времени ожидания
Вот пример пяти процессов, прибывающих в разное время. Каждый процесс имеет разное время посылки.
| Обработать | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Используя алгоритм планирования FCFS, эти процессы обрабатываются следующим образом.
Шаг 0) Процесс начинается с P4, который имеет время прибытия 0
Шаг 1) В момент времени = 1 приходит P3. P4 все еще выполняется. Следовательно, P3 хранится в очереди.
| Обработать | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 2) В момент времени = 2 прибывает P1, который сохраняется в очереди.
| Обработать | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 3) В момент времени = 3 процесс P4 завершает свое выполнение.
Шаг 4) В момент времени = 4, P3, который является первым в очереди, начинает выполнение.
| Обработать | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 5) В момент времени = 5 приходит P2, и он сохраняется в очереди.
| Обработать | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 6) В момент 11 P3 завершает свое выполнение.
Шаг 7) В момент времени = 11, P1 начинает выполнение. Он имеет время пакета 6. Он завершает выполнение через интервал времени 17
Шаг 8) В момент времени = 17, P5 начинает выполнение. Он имеет время пакета 4. Он завершает выполнение в момент времени = 21
Шаг 9) В момент времени = 21 P2 начинает выполнение. Он имеет время пакета 2. Он завершает выполнение через интервал времени 23
Шаг 10) Рассчитаем среднее время ожидания для приведенного выше примера.
Waiting time = Start time - Arrival time
Среднее время ожидания
Преимущества FCFS
Вот преимущества и преимущества использования алгоритма планирования FCFS:
- Простейшая форма алгоритма планирования процессора
- Легко программировать
- Первым прибыл – первым обслужен Эквивалент в русском языке: поздний гость гложет и кость
Недостатки FCFS
Вот минусы / недостатки использования алгоритма планирования FCFS:
- Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.
- Среднее время ожидания высокое.
- Короткие процессы, которые находятся в конце очереди, должны ждать завершения длинного процесса на фронте.
- Не идеальная техника для систем с разделением времени.
- Из-за своей простоты FCFS не очень эффективна.
Резюме:
- Определение: FCFS – это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы, поставленные в очередь, в порядке их поступления
- Поддерживает не вытесняющее и упреждающее планирование
- алгоритм.
- FCFS расшифровывается как First Come First Serve
- Реальный пример метода FCFS – покупка билета в кино на кассе.
- Это самая простая форма алгоритма планирования процессора
- Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.