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

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

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

Основным преимуществом этого алгоритма является то, что его легко понять и столь же легко программировать.

Недостатком является абсолютная неоптимизированность планирования.

Алгоритм пларирования SJF

«Кратчайшая задача — первая»

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

 

Преимущество алгоритма заключается в оптимизации задачи.

 

Недостатком является то, что эта схема работает лишь в случае одновременного наличия задач.

 

Алгоритм пларирования RoundRobin

Циклическое планирование.

Одним из наиболее старых, простых, справедливых и часто используемых является алгоритм циклического планирования. Каждому процессу предоставля­ется некоторый интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управ­ление передается другому процессу. Разумеется, если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реа­лизация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности. Когда процесс исчерпал свой лимит времени, он отправляется в конец списка.

 

Единственным интересным моментом этого алгоритма является длина кванта. Переключение с одного процесса на другой занимает некоторое время — необхо­димо сохранить и загрузить регистры и карты памяти, обновить таблицы и списки, сохранить и перезагрузить кэш памяти и т. п. Вывод можно сформулировать следующим образом: слишком малый квант приведет к частому переключению процессов и небольшой эффективности, но слишком большой квант может привести к медленному реагированию на корот­кие интерактивные запросы. Значение кванта около 2 0 -5 0 мс часто является ра­зумным компромиссом.

 

20. Алгоритм пларирования "Multilevel Queue"

Несколько очередей.

Один из первых приоритетных планировщиков был реализован в системе CTSS (compatible time-shared system — совместимая система с разделением времени).Основной проблемой системы CTSS было слишком медленное переключе­ние процессов, поскольку в памяти компьютера IBM 7094 мог находиться только один процесс. Каждое переключение означало выгрузку текущего процесса на диск

и считывание нового процесса с диска. Разработчики CTSS быстро сообразили, что эффективность будет выше, если процессам, ограниченным возможностями про­цессора, выделять больший квант времени, чем если предоставлять им небольшие кванты, но часто. С одной стороны, это уменьшит количество перекачек из памяти на диск, а с другой — приведет к ухудшению времени отклика, как мы уже видели.

 

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

 

В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, за­тем 4, 8,16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобится всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые пона­добились бы при использовании циклического алгоритма. Помимо этого, по мере погружения в очереди приоритетов процесс будет все реже запускаться, предо­ставляя процессор более коротким процессам.

 

21. Алгоритм пларирования "Multilevel Feedback Queue"