1. Низкоуровневый алгоритм выбирает следующий процесс из набора процессов в памяти, готовых к работе. (расчет приоритета)
2. Высокоуровневый алгоритм перемещает процессы из памяти на диск и обратно. (переключение контекста)
У каждой версии UNIX низкоуровневый алгоритм слегка различается, но все они имеют много общих черт.
Используется несколько очередей. С каждой очередью связан диапазон непересекающихся значений приоритетов. В очередях находятся только процессы, находящиеся в памяти и готовые к работе.
Действия низкоуровневого планировщика
1. просматривает очереди, начиная с самого высокого приоритета, пока не находит очередь, в которой есть хотя бы один процесс,
2. в найденной очереди запускается первый процесс,
3. процессу разрешается работать в течении некоторого максимального кванта времени (обычно 100 мс) или пока он не заблокируется. Если процесс использует весь свой квант времени, он помещается обратно, в конец очереди, а алгоритм планирование запускается снова.
4. если процесс готов к запуску и имеет наивысший приоритет, планировщик приостановит выполнение текущего процесса (с более низким приоритетом), даже если последний не "выработал" свой временной квант.
Ядро UNIX является непрерываемым. Это означает, что процесс, находящийся в режиме ядра (в результате системного вызова или прерывания) и выполняющий системные инструкции, не может быть прерван системой, а вычислительные ресурсы переданы другому высокоприоритетному процессу. Система может прервать выполнение процесса только при переходе из режима ядра в пользовательский режим.
5. Раз в секунду приоритет каждого процесса пересчитывается по формуле:
Pri = CPU_usage + nice + base
CPU_usage – использование ЦП – среднее значение тиков (прерываний) таймера в секунду, которые процесс работал в течение последних нескольких секунд.
При каждом тика таймера счетчик использования ЦП в таблице процессов увеличивается на 1. Т.о., пока процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.
Но для того, чтобы не снизить приоритет процесса окончательно, ядро последовательно уменьшает величину CPU_usage (в разных версиях для этого используются разные формулы, качество алгоритма планирования определяется как раз эффективностью вычисления CPU_usage, вследствие чего лучше учитываются интересы низкоприоритетных процессов).
Nice – поправка приоритета (допустимый диапазон от -20 до 20).
Base – предопределенные отрицательные значения приоритетов для следующих операций.
- ожидание дискового ввода-вывода
- ожидание дискового буфера
- ожидание терминального ввода
- ожидание выполнения дочернего процесса
Эти величины определяются таким образом, чтобы перезапущенный процесс наверняка попадал в другую очередь.
В основе этой схемы лежит идея как можно скорее удалить процесс из ядра. Если процесс читает дисковый файл, эффективнее позволить ему немедленно продолжить работу сразу после запроса, так чтобы он мог быстро обратиться к следующему системному вызову. Таким образом, процессы, имеющие положительный приоритет, обслуживаются после того, как будут обслужены все процессы, связанные с вводом-выводом.
Особенности планирования в Linux
Потоки в Linux реализованы в ядре. Поэтому планирование основано на потоках, а не на процессах. Планировщик различает три класса потоков:
1. потоки реального времени, обслуживаемые по алгоритму FIFO
2. потоки реального времени, обслуживаемые в порядке циклической очереди
3. потоки разделения времени
1 – имеют наивысший приоритет и не могут прерываться другими потоками, за исключением таких же.
2 – то же, что и 1, но с тем отличием, что они могут прерываться таймером, после чего поток перемещается в конец своей очереди.
Каждый поток имеет приоритет. С каждым процессом связан квант времени, т.е. количество тиков таймера, в течение которых процесс может выполняться. По умолчанию каждый тик равен 10мс. Этот интервал в Linux называют «джиффи».
Планировщик использует квант и приоритет для определения текущего приоритета.
Кроме этого, процессы могут получать бонусы за неиспользованное процессорное время, который позволяет выиграть в спорных ситуациях. Предпочтение отдается только что работавшему процессу, т.к. в этом случае его страницы и кэш еще находятся в памяти и экономится время на их замену.
Планировщик выбирает поток с максимальным приоритетом. Во время работы его квант уменьшается на единицу на каждом тике. Поток лишается ЦП при выполнении одного из следующих условий:
- квант потока уменьшился до 0
- поток блокируется на операции ввода-вывода
- в состояние готовности пришел ранее заблокированный поток с более высоким приоритетом.
Т.о. потоки, связанные с в/в получают преимущество при планировании.
Другое свойство этого алгоритма заключается в том, что когда потоки соревнуются за право использовать ЦП, поток с большим приоритетом получает большую долю процессорного времени.
