Сначала самое короткое задание

Теперь рассмотрим другой неприоритетный алгоритм для пакетных систем, в котором предполагается, что сроки выполнения заданий известны заранее. К примеру, в страховой компании люди могут довольно точно предсказать, сколько времени займет выполнение пакета из 1000 исковых заявлений, поскольку подобная работа выполняется ежедневно.
Когда в ожидании запуска во входящей очереди находится несколько равнозначных по важности заданий, планировщик выбирает сначала самое короткое задание. Рассмотрим изображение, приведенное на рис. 2.21. Здесь представлены четыре задания: А, В, С и Б со сроками выполнения 8, 4, 4 и 4 минуты соответственно. Если их запустить в этом порядке, оборотное время для задания А составит 8 мин, для В — 12 мин, для С — 16 мин и для Б — 20 мин при среднем времени 14 мин.

Рис. 2.21. Пример планирования, когда первым выполняется самое короткое задание: а — запуск четырех заданий в исходном порядке; б — запуск этих заданий в порядке, когда самое короткое из них выполняется первым


Теперь рассмотрим запуск этих четырех заданий, когда первым запускается самое короткое из них (рис. 2.21, б). Теперь показатели оборотного времени составляют 4, 8, 12 и 20 мин при среднем времени 11 мин. Оптимальность алгоритма, при котором первым выполняется самое короткое задание, можно доказать. Рассмотрим пример с четырьмя заданиями, выполняемыми за время а, Ь, с и с1 соответственно. Первое задание будет выполнено за время а, второе — за время а + Ь и т. д. Среднее оборотное время составит (4а + 3Ь + 2с + ¿)/4. Очевидно, что время а оказывает наибольшее влияние на средний показатель по сравнению со всеми остальными временными показателями, поэтому это должно быть самое короткое задание. Затем по нарастающей должны идти Ь, с и наконец с1 как самое продолжительное, которое оказывает влияние лишь за счет своего собственного оборотного времени. Аналогичные аргументы точно так же применимы к любому количеству заданий.

Следует заметить, что алгоритм, основанный на выполнении первым самого короткого задания, оптимален только в том случае, если все задания доступны одновременно. В качестве примера противоположной ситуации рассмотрим пять заданий от А до Е со сроками выполнения 2, 4, 1, 1 и 1 соответственно. Время их поступления 0, 0, 3, 3 и 3. Первоначально может быть выбрано только задание А или задание В, а остальные три задания к тому времени еще не поступят. Используя правило, по которому первым выполняется самое короткое задание, мы будем выполнять задания в следующей очередности: А, В, С, Б, Е — при среднем времени ожидания, равном 4,6. Разумеется, их запуск в следующем порядке: В, С, Б, Е, А — привел бы к среднему времени ожидания, равному 4,4.

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

Еще по теме Сначала самое короткое задание:

  1. 6.2.7. Шаг шестой : последние самое - самое лучшее
  2. АНАЛИЗ КОРОТКИЙ
  3. ИЗНАЧАЛЬНО КОРОТКАЯ ПРОГРАММА
  4. Короткие любовные послания
  5. Метод Ключ — способ наиболее короткого поиска этого особого состояния для производства саморегуляции.
  6. НАЧНЕМ СНАЧАЛА
  7. Пусть сначала он (она)...
  8. Сизиф, или "Начни сначала"
  9. Что сначала: программа или анкета?
  10. 6.17.3. Сначала картины, а потом слова
  11. Самое трудное - начало
  12. Вот и вы займитесь сначала мелочами. Наработайте «банк мантр» на мелкие случаи жизни. Какие?
  13. САМОЕ РАСПРОСТРАНЕННОЕ «ПРЕСТУПЛЕНИЕ»
  14. Задания, мешающие когнитивному процессу (ЗМКП), и задания, помогающие когнитивному процессу (ЗПКП)
  15. Тест 14. "Как вы считаете, почему труп сначала утопили, а потом извлекли из воды и закопали в землю?"