-
Планиpование в интеpактивных системах: Циклическое планиpование, Пpиоpитетное планиpование.
«Циклическое планирование»
Каждому процессу предоставляется некоторый интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а правление передается другому процессу. Разумеется, если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реализация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности (а). Когда процесс исчерпал свой лимит времени, он отправляется в конец списка (б).
а)
б)
Слишком малый квант приведет к частому переключению процессов и небольшой эффективности, но слишком большой квант может привести к медленному реагированию на короткие интерактивные запросы. Значение кванта около 20-50 мс.
«Приоритетное планирование»
Основная идея: каждому процессу присваивается приоритет, и управление передается готовому к работе процессу с самым высоким приоритетом.
На рис.представлена система с четырьмя классами приоритетов. Алгоритм планирования выглядит следующим образом: пока в классе 4 есть готовые к запуску процессы, они запускаются один за другим согласно алгоритму циклического планирования, и каждому отводится квант времени. При этом классы с более низким приоритетом не будут их беспокоить. Если в классе 4 нет готовых к запуску процессов, запускаются процессы класса 3 и т. д. Если приоритеты постоянны, до процессов класса 1 процессор может не дойти никогда.
-
Планиpование в интеpактивных системах: Несколько очеpедей. Самый коpоткий пpоцесс - следующий. Гаpантиpованное планиpование.
«Несколько очередей»
Процессам класса с высшим приоритетом выделялся один квант, процессам следующего класса - два кванта, следующего - четыре кванта и т. д. Когда процесс использовал все отведенное ему время, он перемещался на класс ниже.
Max приор.:
В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен 1 квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, затем 4, 8,16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобится всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые понадобились бы при использовании циклического алгоритма.
«Самый короткий процесс — следующий»
Интерактивные процессы чаще всего следуют схеме «ожидание команды, исполнение команды, ожидание команды, исполнение команды...» Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время отклика, запуская первой самую короткую задачу. Единственная проблема состоит в том, чтобы понять, какой из ожидающих процессов самый короткий. Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оцененное время самое маленькое. Допустим, что предполагаемое время исполнения команды равно То и предполагаемое время следующего запуска равно Т0. Можно улучшить оценку времени, взяв взвешенную сумму этих времен аТ0 + (1 — а)Т1.
Выбирая соответствующее значение а, мы можем заставить алгоритм оценки быстро забывать о предыдущих запусках или, наоборот, помнить о них в течение долгого времени. Взяв а = 1/2, мы получим серию оценок:
После трех запусков вес То в оценке уменьшится до 1/8.
«Гарантированное планирование»
Если вместе с вами процессором пользуются п пользователей, вам будет предоставлено 1/п мощности процессора. И в системе с одним пользователем и п запущенными процессорами каждому достанется 1/п циклов процессора.
Чтобы выполнить это, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на п. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только половину положенного, а 2,0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.