Лотерейное планирование
Основная идея состоит в раздаче процессам лотерейных билетов на доступ к различным системным ресурсам, в том числе и к процессорному времени. Когда планировщику нужно принимать решение, в случайном порядке выбирается лотерейный билет, и ресурс отдается процессу, обладающему этим билетом.
Применительно к планированию процессорного времени система может проводить лотерейный розыгрыш 50 раз в секунду, и каждый победитель будет получать в качестве приза 20 мс процессорного времени.
Справедливое планирование
Некоторые системы перед планированием работы процесса берут в расчёт, кто является его владельцем. В этой модели каждому пользователю, а не процессу, как в гарантированном, распределяется некоторая доля процессорного времени и планировщик выбирает процессы, соблюдая это распределение.
Таким образом, если каждому из двух пользователей было обещано по 50% процессорного времени, то они его получат, независимо от количества имеющихся у них процессов.
Приоритетное планирование
Запускается тот процесс, который находится в состоянии готовности и имеет наивысший приоритет. Чтобы предотвратить бесконечное выполнение высокоприоритетных процессов: понижать уровень приоритета текущего выполняемого процесса с каждым прерыванием по таймеру; выделить каждому процессу максимальный квант допустимого времени выполнения. Приоритеты могут присваиваться процессам в динамическом режиме.
20. Алгоритм планирования Windows nt.
Алгоритм планирования потоков в Windows NT объединяет в себе обе базовых концепции - квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой потоку назначается квант, в течение которого он может выполняться. поток освобождает процессор, если:
· блокируется, уходя в состояние ожидания;
· завершается;
· исчерпан квант;
· в очереди готовых появляется более приоритетный поток.
Использование динамических приоритетов, изменяющихся во времени, позволяет реализовать адаптивное планирование, при котором не принижаются интерактивные задачи, часто выполняющие операции ввода-вывода и недоиспользующие выделенные им кванты. Если поток полностью исчерпал свой квант, то его приоритет понижается на некоторую величину. В то же время приоритет потоков, которые перешли в состояние ожидания, не использовав полностью выделенный им квант, повышается. Приоритет не изменяется, если поток вытеснен более приоритетным потоком.
Для того, чтобы обеспечить хорошее время реакции системы, алгоритм планирования использует наряду с квантованием концепцию абсолютных приоритетов. В соответствии с этой концепцией при появлении в очереди готовых потоков, у которых приоритет выше, чем у выполняющейся в данный момент, происходит смена активного потока на поток с самым высоким приоритетом.
21. Алгоритмы планирования Linux: о(1), cfs.
В ОС LINUX поддерживается 3 класса потоков:
● реального времени (обслуживаются в порядке циклической очереди),
● реального времени (обслуживаются по FIFO)(First in First Out — первым прибыл, первым обслужен),
● разделения времени.
140 уровней приоритета. Чем меньше число, тем выше приоритет. Потоки реального времени: приоритет 0 – 99. 0 – наивысший. Обычный поток: 100 – 139. У каждого уровня потоков свое значение кванта времени. Linux связывает с потоком значение nice, оно определяет статический приоритет каждого потока. По умолчанию =0, изменяется с помощью системного вызова nice (value), value от -20 до +19.
В планировщике O(1) максимальное увеличение приоритета равно -5, поскольку более низкое значение приоритета соответствует более высокому приоритету, полученному планировщиком. Максимальное снижение приоритета равно +5. Планировщик поддерживает связанную с каждой задачей переменную sleep_avg. Когда задача просыпается, эта переменная получает приращение, когда задача вытесняется или истекает ее квант, эта переменная уменьшается на соответствующее значение.
Но несмотря на положительное свойство, заключающееся в постоянном времени проведения операций, у планировщика O(1) имелись существенные недостатки. Наиболее значимый состоял в том, что эвристическое правило, используемое для определения степени интерактивности задачи, а следовательно уровня ее приоритета, было слишком сложным и несовершенным, что выражалось в низкой производительности интерактивных задач.
Предыдущие алгоритмы показывали низкую производительность на многопроцессорных системах и не могли хорошо масштабироваться с увеличением количества задач и для решения проблемы был предложен новый планировщик (Completely Fair Scheduler (CFS))
CFS всегда планирует задачу, которой требуется наименьшее количество времени центрального процессора, обычно это самый левый узел дерева. Периодически CFS увеличивает значение vruntime задачи на основе того времени, которое уже было затрачено на ее выполнение, и сравнивает его со значением текущего самого левого узла дерева. Если выполняемая задача все еще имеет наименьшее значение vruntime, ее выполнение продолжается. В противном случае она будет вставлена в соответствующее место в красно-черном дереве, и центральный процессор получит задачу, соответствующую новому самому левому узлу дерева.
