Учебники

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

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

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

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

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

Характеристики метода 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

P4 = 0-0 = 0

P3 = 3-1 = 2

PI = 11-2 = 9

P5 = 17-4 = 13

P2 = 21-5 = 16

Среднее время ожидания

= 40/5 = 8

Преимущества FCFS

Вот преимущества и преимущества использования алгоритма планирования FCFS:

  • Простейшая форма алгоритма планирования процессора
  • Легко программировать
  • Первым прибыл — первым обслужен Эквивалент в русском языке: поздний гость гложет и кость

Недостатки FCFS

Вот минусы / недостатки использования алгоритма планирования FCFS:

  • Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.
  • Среднее время ожидания высокое.
  • Короткие процессы, которые находятся в конце очереди, должны ждать завершения длинного процесса на фронте.
  • Не идеальная техника для систем с разделением времени.
  • Из-за своей простоты FCFS не очень эффективна.

Резюме:

  • Определение: FCFS — это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы, поставленные в очередь, в порядке их поступления
  • Поддерживает не вытесняющее и упреждающее планирование
  • алгоритм.
  • FCFS расшифровывается как First Come First Serve
  • Реальный пример метода FCFS — покупка билета в кино на кассе.
  • Это самая простая форма алгоритма планирования процессора
  • Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.