Поскольку UNIX всегда была многозадачной системой, ее алгоритм планирования с самого начала развития системы разрабатывался так, чтобы обеспечить хорошую реакцию в интерактивных процессах. У этого алгоритма два уровня. Низкоуровневый алгоритм выбирает следующий процесс из набора процессов в памяти и готовых к работе. Высокоуровневый алгоритм перемещает процессы из памяти на диск и обратно, что предоставляет всем процессам возможность попасть в память и быть запущенными.
У каждой версии UNIX свой слегка отличающийся низкоуровневый алгоритм планирования, но у большинства этих алгоритмов есть много общих черт, которые мы здесь и опишем. В низкоуровневом алгоритме используется несколько очередей. С каждой очередью связан диапазон непересекающихся значений приоритетов. Процессы, выполняющиеся в режиме пользователя (верхняя часть айсберга), имеют положительные значения приоритетов. У процессов, выполняющихся в режиме ядра (обращающихся к системным вызовам), значения приоритетов отрицательные. Отрицательные значения приоритетов считаются наивысшими, а положительные – наоборот, минимальными. В очередях располагаются только процессы, находящиеся в памяти и готовые к работе.
Когда запускается низкоуровневый планировщик, он ищет очередь, начиная с самого высокого приоритета (то есть с наименьшего отрицательного значения), пока не находит очередь, в которой есть хотя бы один процесс. После этого в этой очереди выбирается и запускается первый процесс. Ему разрешается работать в течение некоего максимального кванта времени, как правило, 100 мс, или пока он не заблокируется. Если процесс использует весь свой квант времени, он помещается обратно, в конец очереди, а алгоритм планирования запускается снова. Таким образом, процессы, входящие в одну группу приоритетов, совместно используют центральный процессор в порядке циклической очереди.
Раз в секунду приоритет каждого процесса пересчитывается по формуле, состоящей из суммы трех компонентов. Первой составляющей этой формулы является параметр использования центрального процессора, представляющий собой среднее значение тиков (прерываний) таймера в секунду, которые процесс работал в течение последних нескольких секунд. При каждом тике таймера счетчик использования центрального процессора в таблице процессов увеличивается на единицу. Этот счетчик в конце концов добавляется к приоритету процесса, увеличивая тем самым числовое значение его приоритета (что соответствует более низкому приоритету), в результате чего процесс попадает в менее приоритетную очередь. Однако в UNIX процесс не находится в конце очереди бесконечно долго, и величина параметра использования центрального процессора со временем уменьшается. В различных версиях UNIX это уменьшение выполняется по-разному. Один из способов состоит в том, что к этому параметру прибавляется полученное число тиков, после чего сумма делится на два. Такой алгоритм учитывает самое последнее значение числа тиков с весовым коэффициентом 1/2, предшествующее ему – с весовым коэффициентом 1/4 и т. д. Алгоритм взвешивания очень быстр, так как состоит из всего одной операции сложения и одного сдвига, но также применяются и другие схемы взвешивания.
Второй составляющей формулы является так называемый параметр nice. Его значение по умолчанию равно 0, но допустимый диапазон значений, как правило, составляет от -20 до +20. Процесс может установить значение nice в диапазоне от 0 до 20 с помощью системного вызова. Только системный администратор может запросить обслуживание с более высоким приоритетом (то есть значения nice от -20 до -1).
Третьей составляющей формулы является параметр base (база). Когда процесс эмулирует прерывание для выполнения системного вызова в ядре, процесс, вероятно, должен быть блокирован, пока системный вызов не будет выполнен и не вернется в режим пользователя. Например, процесс может обратиться к системному вызову, ожидая, пока один из его дочерних процессов не закончит работу. Он может также ожидать ввода с терминала или завершения дисковой операции ввода-вывода и т. д. Когда процесс блокируется, он удаляется из структуры очереди, пока этот процесс снова не будет готов работать. Однако когда происходит событие, которого ждал процесс, он снова помещается в очередь с отрицательным значением. Выбор очереди определяется событием, которого ждал процесс. Например дисковый ввод-вывод может быть событием с наивысшим приоритетом, так что процесс, только что прочитавший или записавший блок диска, вероятно, получит центральный процессор в течение 100 мс. Отрицательные значения приоритета для дискового ввода-вывода, терминального ввода-вывода и некоторых других операций жестко прошиты в операционной системе и могут быть изменены только путем перекомпиляции самой системы. Эти значения (отрицательные) и представлены параметром base. Их величина достаточно отличается от нуля, чтобы перезапущенный процесс наверняка попадал в другую очередь.
В основе этой схемы лежит идея как можно более быстрого удаления процессов из ядра. Например, если процесс пытается читать дисковый файл, необходимость ждать секунду между обращениями к системным вызовам read замедлит его работу во много раз. Значительно лучше позволить ему немедленно продолжить работу сразу после выполнения запроса, так чтобы он мог быстро обратиться к следующему системному вызову. Если процесс был заблокирован ожиданием ввода с терминала, то, очевидно, это интерактивный процесс, и ему должен быть предоставлен наивысший приоритет, как только он перейдет в состояние готовности, чтобы гарантировать хорошее качество обслуживания интерактивных процессов. Таким образом, процессы, ограниченные производительностью процессора (то есть находящиеся в положительных очередях), в основном обслуживаются после того, как будут обслужены все процессы, ограниченные вводом-выводом (когда все эти процессы окажутся заблокированы в ожидании ввода-вывода).
Планирование в операционной системе Linux представляет собой одну из немногих областей, в которых использует алгоритм, отличный от применяющегося в UNIX. Так как потоки в системе Linux реализованы в ядре, то планирование в ней основано на потоках, а не на процессах. В операционной системе Linux алгоритмом планирования различаются три класса потоков:
1. Потоки реального времени, обслуживаемые по алгоритму FIFO.
2. Потоки реального времени, обслуживаемые в порядке цикли-ческой очереди.
3. Потоки разделения времени.
Потоки реального времени, обслуживаемые по алгоритму FIFO, имеют наивысшие приоритеты и не могут прерываться другими потоками, за исключением такого же потока реального времени FIFO, перешедшего в состояние готовности. Потоки реального времени, обслуживаемые в порядке циклической очереди, представляют собой то же самое, что и потоки реального времени FIFO, но с тем отличием, что они могут прерываться таймером. Находящиеся в состоянии готовности потоки реального времени, обслуживаемые в порядке циклической очереди, выполняются в течение определенного кванта времени, после чего поток помещается в конец своей очереди. Ни один из этих классов на самом деле не является классом реального времени. Здесь нельзя задать предельный срок выполнения задания и предоставить гарантий его выполнения. Эти классы просто имеют более высокий приоритет, чем у потоков стандартного класса разделения времени.
У каждого потока есть приоритет планирования. Значение по умолчанию равно 20, но оно может быть изменено при помощи специального системного вызова, вычитающего некоторое значение в диапазоне от -20 до +19 из 20. Поэтому возможные значения приоритетов попадают в промежуток от 1 до 40. Цель алгоритма планирования состоит в том, чтобы обеспечить грубое пропорциональное соответствие качества обслуживания приоритету (то есть чем выше приоритет, тем меньше должно быть время отклика и тем большая доля процессорного времени достанется процессу).
Помимо приоритета с каждым процессом связан квант времени, то есть количество тиков таймера, в течение которых процесс может выполняться. По умолчанию каждый тик равен 10 мс. Планировщик использует сочетание значений приоритета и кванта для плани-рования по определенному алгоритму.
7.3. Управление памятью в UNIX