Первым пришел — первым обслужен

Наверное, наипростейшим из всех алгоритмов планирования будет неприоритетный алгоритм, следующий принципу «первым пришел — первым обслужен». При использовании этого алгоритма центральный процессор выделяется процессам в порядке поступления их запросов.
По сути, используется одна очередь процессов, находящихся в состоянии готовности. Когда рано утром в систему извне попадает первое задание, оно тут же запускается на выполнение и получает возможность выполняться как угодно долго. Оно не прерывается по причине слишком продолжительного выполнения. Другие задания по мере поступления помещаются в конец очереди. При блокировке выполняемого процесса следующим запускается первый процесс, стоящий в очереди. Когда заблокированный процесс переходит в состояние готовности, он, подобно только что поступившему заданию, помещается в конец очереди, после всех ожидающих процессов.

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

К сожалению, принцип «первым пришел — первым обслужен» страдает и существенными недостатками. Предположим, что используются один процесс, ограниченный скоростью вычислений, который всякий раз запускается на 1 с, и множество процессов, ограниченных скоростью работы устройств ввода-вывода, незначительно использующих время центрального процессора, но каждый из которых должен осуществить 1000 считываний с диска, прежде чем завершить свою работу. Процесс, ограниченный скоростью вычислений, работает в течение 1 с, а затем переходит к чтению блока данных с диска. Теперь запускаются все процессы ввода-вывода и приступают к чтению данных с диска. Когда процесс, ограниченный скоростью вычислений, получает свой блок данных с диска, он запускается еще на 1 с, а за ним непрерывной чередой следуют все процессы, ограниченные скоростью работы устройств ввода-вывода.

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

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Первым пришел — первым обслужен:

  1. КАК Я БЫЛ ПЕРВЫМ
  2. ОТВЕТ ПРИШЕЛ К НЕМУ СТРАННЫМ ПУТЕМ
  3. 7.15.2. Забудьте про первое правило
  4. Управление деканатами
  5. Глава 9. Примиритесь с неизбежным.
  6. АБСЦИССИЯ, ИЛИ ФРУСТРАЦИЯ.
  7. МИФ
  8. Глава 8. Как формулировать приглашения, которые наверняка будут приняты.
  9. Демонстрация искренности юристом
  10. Как запомнить свой сон
  11. Ретроградная Венера в XI поле