Гарантированное планирование

Round Robin

First Come First Served

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

Первый пришедший первый и обслуживается. Все процессы в ОС находятся в очереди. Когда процесс переходит в состояние «готовность», ссылка на его Process Control Block помещается в конец очереди. Из названия алгоритма ясно, что процесс подлежащий выполнению берется из начала очереди путем удаления PCB из начала очереди.

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

Это алгоритм FCFS, реализованный в режиме вытесняющего планирования

CPU

При RR планировщики выбирают процесс из начала очереди и устанавливают таймер для подсчета кванта времени. Два варианта:

1. Время непрерывного использования процессора меньше или равно продолжительности два. Тогда оказывается, что процесс сам оставляет процессор и отдает его ОС

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

Если кванты времени очень большие, тогда алгоритм вырождается в FCFS. При работе системы с квантами можно считать, что есть n виртуальных машин (n – кол-во пользователей) с мощностью N/n.

3.5.3 Shortest Job – First

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

Процесс	Р0	Р1	Р2	Р3
Продолжительность CPU Burst

Очевидно, что первым на исполнение должен быть поставлен процесс Р3, затем Р1, Р0 и Р2. И время ожидания будет: (0+5+8+15)/4 = 7

Время

Р0

Г

Г

Г

Г

И

И

И

И

И

Р1

Г

И

И

И

Р2

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

И

И

Р3

И

Время ожидания: (0+1+4+9)/4 = 3,5

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

Пусть работает n-пользователей с данной ОС. Реализовано, чтобы каждый имел 1/n часть процессорного времени. Для каждого пользователя введем величины:

a) Т_i – время нахождения пользователя в системе

b) τ_i – суммарное процессорное время уже выделенное всем процесса пользователя в течение сеанса

c) τ_i/Т_i – пользовательское время

d) α_i – коэффициент справедливости, равный τ_i/(τ_i/N)

Пусть очередной квант времени будет представляться процессору с наименьшим α_i, если это так, то такой алгоритм планирования называется алгоритмом гарантированного планирования.

Дата добавления: 2014-01-07