Модель алгоритма планирования потоков, основанного на квантовании — это модель алгоритма планирования потоков, в которой исходными данными является фиксированная единая очередь потоков с заданным временем исполнения.
Введение
Операционная система способна выполнять планирование потоков, при этом она учитывает их состояние. В мультипрограммной системе поток может обладать следующими основными состояниями:
- Поток может находиться в состоянии выполнения, то есть, в активном состоянии, во время которого поток может использовать все необходимые ему ресурсы, так как он непосредственно исполняется процессором.
- Поток может находиться в состоянии ожидания, то есть, в пассивном состоянии, в котором поток является заблокированным по своим внутренним причинам. Например, он может ожидать наступления определенного события, наиболее часто это завершение операции ввода-вывода, а также прибытия сообщения от другого потока или освобождения какого-нибудь требуемого ему ресурса.
- Поток может находиться в состоянии готовности, которое также является пассивным состоянием, но в данном случае поток блокируется по внешним по отношению к нему причинам. То есть, поток обладает всеми необходимыми ему ресурсами, готов к выполнению, но процессор занимается обслуживанием другого потока.
Не вытесняющими (non-preemptive) алгоритмами являются такие, в которых поток исполняется до тех пор, пока по собственной инициативе он не предаст управление операционной системе, для того чтобы активировать другой поток.
Вытесняющими (preemptive) алгоритмами являются алгоритмы, в которых решение о переключении принимает операционная система.
Можно привести следующие примеры:
Операционные системы Unix, Windows NT/2000/XP, OS/2, VAX поддерживают вытесняющие алгоритмы. Операционные системы NetWare 3.x, 4.x поддерживают не вытесняющие (ThreadSwitch) алгоритмы.
Вытесняющие алгоритмы планирования подразделяются на алгоритмы, которые основаны на следующих принципах:
- принципе квантования,
- принципе приоритетов,
- на смешанных принципах.
Модель алгоритма планирования потоков, основанного на квантовании
Основой многих вытесняющих алгоритмов планирования является концепция квантования. Квантом считается ограниченный непрерывный период процессорного времени. Потоки могут получать процессорное время квантами. Поток, исчерпавший свой квант, должен переводиться в состояние готовности и ожидать, когда ему предоставят новый квант, а на исполнение согласно определенным правилам должен быть выбран новый поток из очереди готовых к работе потоков, как показано на рисунке ниже.
Рисунок 1. Потоки. Автор24 — интернет-биржа студенческих работ
Между состояниями могут быть реализованы следующие переходы:
- Потоку выделен квант процессорного времени.
- Поток находится в ожидании окончания операции ввода-вывода.
- Ввод-вывод окончен (событие произошло).
- Поток использовал квант.
Кванты, которые выделяются потокам, могут быть как одинаковые для каждого потока, так и разные для всех потоков. Кванты, которые выделяются одному потоку, могут иметь фиксированную величину, но могут и меняться в различные этапы функционирования потока.
Помимо этого, соотношение между размером кванта и средним временем исполнения задачи может влиять на уровень производительности системы. Все эти аспекты предоставляют возможность операционной системе реализовать некоторую необходимую политику в планировании, а именно:
- Отдать предпочтение коротким или длинным задачам.
- Осуществить компенсацию неиспользованного кванта.
- Выполнить минимизацию накладных расходов, которые связаны с переключениями.
Причем операционная система не использует никакой предварительной информации о процессах, выбор методики обслуживания при квантовании основывается на истории существования потока в системе.
Как было указано выше, кванты, которые выделяются потокам, могут быть одинаковыми для всех потоков или разными. Приведем пример, когда каждому потоку предоставляются кванты одинаковой длины q, как показано на рисунке ниже.
Рисунок 2. Потоки. Автор24 — интернет-биржа студенческих работ
Когда в системе присутствует п потоков, то время, которое поток может провести в ожидании следующего кванта, можно приблизительно оценить как q(n-l). Очевидно, что чем больше потоков функционирует в системе, тем больше будет время ожидания. Это означает уменьшение возможности выполнения одновременной интерактивной работы несколькими пользователями.
Но когда величина кванта выбирается достаточно малой, то величина произведения q(n-l) все равно окажется достаточно малой для того, чтобы пользователь не испытывал дискомфорта от того, что в системе присутствуют другие пользователи. Стандартным значением кванта в системах разделения времени является величина порядка десятки миллисекунд.
Когда квант выбирается коротким, то общее время, проводимое потоком в ожидании процессора, является прямо пропорциональным времени, которое требуется для его исполнения. То есть, это время, которое необходимо для исполнения данного потока при монопольной загрузке вычислительной системы.
В самом деле, так как время ожидания между двумя циклами исполнения равняется q(n-l), а количество циклов равно:
B/q.
Здесь В является требуемым временем выполнения.
Тогда время ожидания будет равно:
W=B(n-l).
Следует подчеркнуть, что данные соотношения являются достаточно грубой оценкой, основанной на предположении, что В существенно больше, чем q. При этом не принимается во внимание, что конкретный поток может использовать квант не целиком, а часть времени может затрачиваться на операции ввода-вывода. Также не учитывается тот факт, что число потоков в системе способно динамически изменяться и так далее.
Чем большим размером обладает квант, тем больше вероятность того, что потоки могут быть завершены в результате первого же цикла исполнения, и тем менее очевидной становится зависимость времени ожидания потоков от их времени исполнения.
