В операционной системе Linux планирование основано на потоках, поскольку потоки реализованы в ядре. Различают три класса потоков:
1. Потоки реального времени, обслуживаемые по алгоритму FIFO
2. Потоки реального времени, обслуживаемые в порядке циклической очереди
3. Потоки разделения времени. Обслуживаемые по алгоритму FIFO потоки имеют наивысшие приоритеты и не могут вытесняться другими потоками, за исключением того же потока реального времени с более высоким приоритетом, перешедшего в состояние готовности.
Обслуживаемые в порядке циклической очереди потоки реального времени представляют собой то же самое, что и потоки реального времени FIFO, но с тем отличием, что они имеют квант времени и могут вытесняться по таймеру. Такой, находящийся в состоянии готовности, поток выполняется в течение кванта времени, после чего поток помещается в конец своей очереди. Рассмотренные классы имеют более высокий приоритет, чем потоки разделения времени. Потоки реального времени внутри системы Linux представлены приоритетами от 0 до 99, причем 0 – самый высокий, 99 – самый низкий.
Третий класс потоков представлен приоритетами от 100 до 139, т.е. в системе Linux реализовано 140 приоритетов.
Квант времени – количество тиков таймера, в течение которых процесс может выполняться( ~1 мс.) Планировщик Linux использует ключевую структуру данных, которая называется очередь исполнения. Эта очередь связана с процессором системы и помимо прочей информации поддерживает два массива active и expired.
Поля active и expired являются указателем на массив из заголовков 140 списков.
Работы планировщика. Планировщик выбирает задачу из активного массива с самым высоким приоритетом. Если квант времени этой задачи истек, то она переносится в список закончивших функционирование (возможно с другим уровнем приоритета). Если задача блокируется (например, в ожидании события ввода-вывода) до истечения ее кванта времени, то после события она помещается обратно в исходный массив, а ее квант уменьшается на количество уже использованного времени. После полного истечения кванта времени она также будет помещена в массив закончивших функционирование. Когда ни в одном из активных массивов больше нет задач, то планировщик просто меняет указатели, чтобы закончившие функционирование массивы стали активными и наоборот. Разным уровням приоритета присваиваются различные кванты времени, больший квант времени присваивается большему приоритету. Существует понятие статического и динамического приоритета. Статический приоритет возникает при создании процесса (потока). Динамический приоритет изменяется во время работы процесса (потока) в соответствии с политикой планирования данной операционной системы. В системе Linux с каждым потоком связывается значение nice. По умолчанию оно равно 0, но может изменяться с помощью системного вызова nice (value) -20<=value<=19. Это значение определяет статический приоритет потока. Поскольку Linux заранее не знает, будет ли задача интенсивно использовать процессор или ввод-вывод, она применяет динамический приоритет для решения данной проблемы.
Динамический приоритет используется в системе linux для того, чтобы:
1. Уделять большее внимание интерактивным потокам
2. Предотвращать излишний расход процессорного времени
Максимальное увеличение приоритета = -5, максимальное снижение приоритета = +5.
Планировщик поддерживает связанную с каждой задачей переменную sleep_avg. Когда задача просыпается, эта переменная получает приращение, а когда задача вытесняется или истекает ее квант, эта переменная уменьшается на соответствующее значение. Планировщик linux пересчитывает новый уровень приоритета при перемещении потока из списка активных в список закончивших функционирование.
Кроме того, планировщик имеет функциональные возможности в отношении многопроцессорных или многоядерных систем, например, с каждым процессором связывается своя очередь выполнения. Планировщик рассматривает только готовые к выполнению задачи, которые помещаются в соответствующие очереди выполнения.
Те задачи, которые не готовы к выполнению и ждут выполнения различных операций ввода-вывода, помещаются в структуру очередь ожидания. Такая очередь связана с каждым событием, которого могут дожидаться задачи. Заголовок очереди ожидания содержит указатель на связный список задач.
