Критерии планирования и требования к алгоритмам

Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы хотим достичь, используя планирование.
К числу таких целей можно отнести следующие:

• Справедливость — гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться.

• Эффективность — постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.

• Сокращение полного времени выполнения (turnaround time) — обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.

• Сокращение времени ожидания (waiting time) — сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.

• Сокращение времени отклика (response time) — минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

Независимо от поставленных целей планирования желательно также, чтобы алгоритмы обладали следующими свойствами:

• Были предсказуемыми. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток — при втором запуске.

• Были связаны с минимальными накладными расходами. Если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит.

• Равномерно загружали ресурсы вычислительной системы, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы.

• Обладали масштабируемостью, т. е. не сразу теряли работоспособность при увеличении нагрузки. Например, рост количества процессов в системе едва раза не должен приводить к увеличению полного времени выполнения процессов на порядок.

Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного критерия, мы ухудшаем ее с точки зрения другого. Приспосабливая алгоритм под один класс задач, мы тем самым дискриминируем задачи другого класса. «В одну телегу впрячь не можно коня и трепетную лань». Ничего не поделаешь. Такова жизнь.

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Еще по теме Критерии планирования и требования к алгоритмам:

  1. Критерий для подбора индивидуальных приемов — критерий мастерства, критерий оптимальности, критерий минимального усилия, критерий автоматизма.
  2. § 24 Замена одного требования другим противоположным (компенсация). – Основания сей замены и законные для нее условия. – Однородность требований. – Отношение их по количеству. – Действие несостоятельности на замену. – Требования несоизмеримые. – Необязательность замены.
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ
  5. Планирование телепередач
  6. 4. Кондикционное требование и требование стороны в обязательстве о возврате исполненного
  7. Планирование, а не планы
  8. АЛГОРИТМ УДАЧИ
  9. 2. Кондикционное требование и требование о возврате исполненного по недействительной сделке
  10. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  11. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  12. Алгоритм исцеления:
  13. § 5. Соотношение кондикционного требования с обязательствами возврата, а также с требованиями, составляющими содержание договорной ответственности (п. 2483—2485)
  14. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  15. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  16. Алгоритм избавления от боли
  17. 10.2. Планирование и организация следственных действий
  18. 5.4. Планирование упражнений
  19. 2. Специфика и алгоритмы работы с источниками.
  20. Алгоритм обработки результатов.