Алгоритмы планирования потоков, основанные на квантовании

Вытесняющие и невытесняющие алгоритмы планирования потоков

Состояния потока в мультипрограммной системе

ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний:

выполнение — активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

ожидание — пассивное состояние потока, находясь в котором, поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);

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

Невытесняющие (non-preemptive) - поток выполняется, пока по собственной инициативе не отдаст управление ОС для активизации другого потока

Вытесняющие (preemptive) - решение о переключении принимается ОС

Примеры:

Unix, Windows NT/2000/XP, OS/2, VAX - поддерживаются вытесняющие алгоритмы

NetWare 3.x, 4.x - невытесняющие (ThreadSwitch)

Вытесняющие алгоритмы планирования делятся на алгоритмы, основанные на:

квантовании

приоритетах

смешанные

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

Возможные переходы между состояниями:

1. Потоку выделен квант процессорного времени

2. Поток ожидает завершения ввода/вывода

3. Ввод/вывод завершен (событие произошло)

4. Поток исчерпал квант

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

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