Планирование в системе UNIX

Поскольку 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