Алгоритм планирования FCFS: что такое, пример программы
Натаниэль Брукс
Что такое метод обслуживания в порядке очереди?
Первое прибытие - первое обслуживание (FCFS) — это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления. Это самый простой и простой алгоритм планирования ЦП. В этом типе алгоритма процессы, которые первыми запрашивают ЦП, сначала получают выделение ЦП. Это управляется с помощью очереди FIFO. Полная форма FCFS — «первым пришел, первым обслужен».
Когда процесс попадает в очередь готовности, его плата (блок управления процессом) связывается с хвостом очереди, и, когда ЦП освобождается, он должен быть назначен процессу в начале очереди.
Характеристики метода FCFS
- Он поддерживает невытесняющий и упреждающий алгоритм планирования.
- Задания всегда выполняются в порядке очереди.
- Его легко реализовать и использовать.
- Этот метод имеет низкую производительность, а общее время ожидания довольно велико.
Пример планирования FCFS
Реальный пример метода FCFS — покупка билета в кино в кассе. В этом алгоритме планирования человек обслуживается в порядке очереди. Тот, кто приходит первым в очереди, сначала покупает билет, а затем следующий. Это будет продолжаться до тех пор, пока последний человек в очереди не купит билет. Используя этот алгоритм, процесс ЦП работает аналогичным образом.
Как работает FCFS? Расчет среднего времени ожидания
Вот пример пяти процессов, приходящих в разное время. Каждый процесс имеет разное время пакета.
| Разработка | Время взрыва | Время прибытия |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Используя алгоритм планирования FCFS, эти процессы обрабатываются следующим образом.
Шаг 1) Процесс начинается с P4, время прибытия которого равно 0.
Шаг 2) В момент времени = 1 прибывает P3. P4 все еще выполняется. Следовательно, P3 хранится в очереди.
| Разработка | Время взрыва | Время прибытия |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 3) В момент времени = 2 поступает P1, который остается в очереди.
| Разработка | Время взрыва | Время прибытия |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 4) В момент времени=3 процесс P4 завершает свое выполнение.
Шаг 5) В момент времени = 4 P3, который находится первым в очереди, начинает выполнение.
| Разработка | Время взрыва | Время прибытия |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 6) В момент времени =5 прибывает P2 и остается в очереди.
| Разработка | Время взрыва | Время прибытия |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 7) В момент времени 11 P3 завершает свое выполнение.
Шаг 8) В момент времени = 11 P1 начинает выполнение. Его пакетное время равно 6. Он завершает выполнение через интервал времени 17.
Шаг 9) В момент времени = 17 P5 начинает выполнение. Его пакетное время равно 4. Он завершает выполнение в момент времени = 21.
Шаг 10) В момент времени = 21 P2 начинает выполнение. Его пакетное время равно 2. Он завершает выполнение через интервал времени 23.
Шаг 11) Давайте рассчитаем среднее время ожидания для приведенного выше примера.
Waiting time = Start time - Arrival time
Р4 = 0-0 = 0
Р3 = 3-1 = 2
ПИ = 11-2 = 9
П5= 17-4 = 13
П2= 21-5= 16
Среднее время ожидания
= 40 / 5 = 8
Преимущества FCFS
Вот плюсы/преимущества использования алгоритма планирования FCFS:
- Самая простая форма А. Алгоритм планирования ЦП
- Легко программировать
- Первым прибыл - первым обслужен Эквивалент в русском языке: поздний гость гложет и кость
Недостатки FCFS
Вот минусы/недостатки использования алгоритма планирования FCFS:
- Это алгоритм планирования ЦП без вытеснения, поэтому после того, как процесс был выделен ЦП, он никогда не освободит ЦП до тех пор, пока не завершит выполнение.
- Среднее время ожидания велико.
- Коротким процессам, находящимся в конце очереди, приходится ждать завершения длинного процесса, находящегося в начале очереди.
- Не идеальный метод для систем разделения времени.
- Из-за своей простоты FCFS не очень эффективен.
Резюме
- Определение: FCFS — это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления.
- Он поддерживает невытесняющее и упреждающее планирование.
- алгоритм.
- FCFS означает «первым пришел первым обслужен».
- Реальный пример метода FCFS — покупка билета в кино в кассе.
- Это простейшая форма алгоритма планирования ЦП.
- Это алгоритм планирования ЦП без вытеснения, поэтому после того, как процесс был выделен ЦП, он никогда не освободит ЦП до тех пор, пока не завершит выполнение.
