Введение в архитектуру компьютеров

Метод круговорота (карусель)


Простой круговорот (round robin, RR) не использует никакой информации о приоритетах. Порядок обслуживания процессов следующий: первый пришедший процесс получает квант времени to

и встает в очередь на обслуживание, если только он себя не заблокирует. Поэтому при наличии N процессов в системе для обслуживания будем считать, что скорость работы процессора равна V/N, где V– истинное быстродействие процессора. Если to ® ¥, то стратегия SRR (simple round robin) сводится к стратегии FIFO (first in first out). С уменьшением to улучшается обслуживание коротких процессов. Но to не должно быть слишком мало: если оно становится сравнимым по порядку со временем переключения с одного процесса на другой, то задержка в выполнении процессов становится заметной. Метод RR часто применяется в системах разделения времени (СРВ) с большим числом пользователей. Системы СРВ должны гарантировать каждому пользователю приемлемое время ответа. Время ответа в случае N пользователей » t0N.

Одна из модификаций метода – raund robin cicle (RRC). В нем в качестве to для гарантии

выбирается максимально возможное время ожидания. Суть метода: формируется множество Pг – множество готовых для выполнения процессов. Пусть мощность этого множества No. Выбирается время цикла Тц для очереди Pг, равное максимально достижимому времени ответа. Тогда to = Тц/No, to вычисляется для каждого прохождения цикла Pг. Процессы, вновь появляющиеся для обслуживания в Pг, не включаются в очередь до завершения цикла. Если to оказывается слишком маленьким (сравнимым со временем переключения процессов), то выбирается некоторая нижняя оценка для величины to, что позволяет сократить потери на переключение процессов.

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

Можно выделить ведущую и фоновую очередь готовых процессов в зависимости от вероятности затребования определенного количества квантов времени ЦП для их завершения.



Содержание раздела