16. Алгоритм планирования, основанный на квантовании.
Квант – ограниченный непрерывный интервал процессорного времени, который поочередно предоставляется всем существующим в системе потокам. Они могут быть динамическими (длительность кванта времени может быть разной, либо может изменяться) и фиксированными (в системе определена длительность кванта времени, и она для всех одинакова и не изменяется).
Квантование - очередь потоков к процессору, из заголовка этой очереди выбирается поток, который получает квант времени, т.е. интервал процессорного времени, в течение которого он может выполняться, и когда квант времени истек, то поток снимается с выполнения и переходит в состояние готовности, если снимается принудительно.
Смена активного потока происходит, если:
Поток завершился и покинул систему;
Произошла ошибка;
Поток перешел в состояние ожидания;
Исчерпан квант процессорного времени, отведенный данному потоку.
Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых.
Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Чем больше квант, тем выше вероятность того, что потоки завершатся в результате первого же цикла выполнения, и тем менее явной становится зависимость времени ожидания потоков от их времени выполнения. При достаточно большом кванте алгоритм квантования вырождается в алгоритм последовательной обработки, присущий однопрограммным системам, при котором время ожидания задачи в очереди вообще никак не зависит от ее длительности.
Допустим, есть 3 процесса: А - это длинная задача, Б - короткая задача, С - средняя. Этим задачам можно определить короткие и более длинные кванты времени.
Короткие кванты времени выгодны коротким задачам, то есть они могут завершиться за 1 квант времени, и времени перед ними пройдет меньше.
Короткий квант времени невыгоден длинным задачам, так как её время выполнения растягивается. Если мы приоритет хотим отдать им, то длительность кванта времени должна быть больше, за это платим снижением интерактивности.
17. Приоритетное планирование.
Приоритетное планирование предполагает наличие у потоков некоторой изначально известной характеристики — приоритета, на основании которой определяется порядок их выполнения. Приоритет — это число, характеризующее степень привилегированности потока при доступе к ресурсам ОС: чем выше приоритет, тем выше привилегии, тем меньше времени будет проводить поток в очередях, или наоборот, чем ниже приоритет, тем ниже привилегии. Приоритет может выражаться целым или дробным, положительным или отрицательным значением. Планировщик в момент перепланировки, просматривая очередь готовых к выполнению потоков, сравнивает значения их приоритетов и понимает, у кого больше прав в данный момент времени на процессорное время и, соответственно, этим временем наделяет потоки.
Приоритеты бывают:
Фиксированные - приоритет потоку назначается ОС при его создании и не изменяется за время существования потока.
Динамические - приоритет может изменяться либо по инициативе самого потока, либо по инициативе пользователя, либо ОС изменяет приоритеты потоков.
Приоритетное планирование бывает:
С относительными приоритетами - приоритет учитывается только при выборе потока на выполнение из очереди готовых к выполнению потоков. Просматриваются очереди и выбирается поток. Он выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же произойдет ошибка, или поток завершится)
С абсолютными приоритетами выполнение активного потока прерывается, когда в очереди готовых к выполнению потоков появляется поток, приоритет которого выше, чем приоритет активного потока. В этом случае прерванный поток переходит в состояние готовности.