Реализация процессов в UNIX

 

У каждого процесса в системе UNIX есть пользовательская часть, в которой работает программа пользователя. Однако когда один из потоков обращается к системному вызову, происходит эмулированное прерывание с переключением в режим ядра. После этого поток начинает работу в контексте ядра, с отличной картой памяти и полным доступом к ресурсам машины. Это все еще тот же самый поток, но теперь обладающий большей мощью, а также со своим стеком ядра и счетчиком команд в режиме ядра. Это важно, так как системный вызов может блокироваться на полпути, например, ожидая завершения дисковой операции. При этом счетчик команд и регистры будут сохранены таким образом, чтобы позднее поток можно было восстановить в режиме ядра.

Ядро поддерживает две ключевые структуры данных, относящиеся к процес­сам: таблицу процессов и структуру пользователя. Таблица процессов является резидентной. В ней содержится информация, необходимая для всех процессов, даже для тех процессов, которых в данный момент нет в памяти. Структура пользо­вателя выгружается на диск, освобождая место в памяти, когда относящийся к ней процесс отсутствует в памяти, чтобы не тратить память на ненужную в данный момент информацию.

Информация в таблице процессов подразделяется на следующие категории:

1. Параметры планирования. Приоритеты процессов, процес-сорное время, потребленное за последний учитываемый период, количество времени, про­веденное процессом в режиме ожидания. Вся эта информация использует­ся для выбора процесса, которому будет передано управление следующим.

2. Образ памяти. Указатели на сегменты программы, данных и стека, или, если используется страничная организация памяти, указатели на соответствую­щие им таблицы страниц. Если программный сегмент используется совмест­но, то программный указатель указывает на общую таблицу программы. Когда процесса нет в памяти, то здесь также содержится информация о том, как найти части процесса на диске.

3. Сигналы. Маски, указывающие, какие сигналы игнорируются, какие пере­хватываются, какие временно заблокированы, а какие находятся в процессе доставки.

4. Прочая информация. Текущее состояние процесса, ожидаемые процессом события (если таковые есть), идентификатор текущего процесса, идентификатор родительского процесса, идентификаторы пользователя и группы, а также некоторая другая информация.

В структуре пользователя содержится информация, которая не требуется, ког­да процесса физически нет в памяти и он не выполняется. Например, хотя процес­су, выгруженному на диск, можно послать сигнал, выгруженный процесс не мо­жет прочитать файл. По этой причине информация о сигналах должна храниться в таблице процессов, постоянно находящейся в памяти, даже когда процесс не при­сутствует в памяти. С другой стороны, сведения об описателях файлов могут хра­ниться в структуре пользователя и загружаться в память вместе с процессом.

Данные, хранящиеся в структуре пользователя, включают в себя следующие пункты:

1. Машинные регистры. Когда происходит прерывание с пере-ключением в ре­жим ядра, машинные регистры (включая регистры с плавающей точкой) сохраняются здесь.

2. Состояние системного вызова. Информация о текущем системном вызове, включая параметры и результаты.

3. Таблица дескрипторов файлов. Когда происходит обращение к системному вызову, работающему с файлом, дескриптор файла используется в качестве индекса в данной таблице, что позволяет найти структуру данных (i-узел), соответствующую данному файлу.

4. Учетная информация. Указатель на таблицу, учитывающую процессорное время, использованное процессом в пользовательском и системном режи­мах. В некоторых системах здесь также ограничивается процессорное вре­мя, которое может использовать процесс, максимальный размер стека, ко­личество страниц памяти и так далее.

5. Стек ядра. Фиксированный стек для использования процессом в режиме ядра.

Рассмотрим подробне, как в системе UNIX создаются процессы. Когда выполняется системный вызов fork, вызываю­щий процесс обращается в ядро и ищет свободную ячейку в таблице процессов, в которую можно записать данные о дочернем процессе. Если свободная ячейка находится, системный вызов копирует туда информацию из ячейки родительского процесса. Затем он выделяет память для сегментов данных и для стека дочернего процесса, куда копируются соответствующие сегменты родительского процесса. Структура пользователя (которая часто хранится вместе с сегментом стека) копи­руется вместе со стеком. Программный сегмент может либо копироваться, либо использоваться совместно, если он доступен только для чтения. Начиная с этого момента дочерний процесс может быть запущен.

Для дочернего процесса создается новая ячейка в таблице процессов, которая заполняется по большей мере из соответствующей ячейки родительского процесса. Дочерний процесс получает идентификатор, затем настраивается его карта памяти. Кроме того, дочернему процессу пре­доставляется совместный доступ к файлам родительского процесса. Затем настра­иваются регистры дочернего процесса, после чего он готов к запуску.

Так как никакая область памяти не может ис­пользоваться совместно родительским и дочерним процессами, дочернему процессу выделяются новые таблицы страниц, но эти таблицы указывают на страницы родительского процесса, помеченные как доступ­ные только для чтения. Когда дочерний процесс пытается писать в такую страни­цу, происходит прерывание. При этом ядро выделяет дочернему процессу новую копию этой страницы, к которой этот процесс получает также и доступ записи. Таким образом, копируются только те страницы, в которые дочерний процесс пишет новые данные. Такой механизм называется копированием при записи. При этом сохраняется память, так как страницы с программой не копируются.

После того, как дочерний процесс начинает работу, его программа выполняет системный вызов ехес, задавая имя команды в качестве пара­метра. При этом ядро находит и проверяет исполняемый файл, копирует в ядро аргументы и строки окружения, а также освобождает старое адресное простран­ство и его таблицы страниц.

Затем следует создать и заполнить новое адресное пространство. Если си­стемой поддерживается отображение файлов на адресное пространство памяти, как, например, в System V, BSD и в большинстве других версий UNIX, то таблицы страниц настраиваются следующим образом: в них указывается, что страниц в па­мяти нет, кроме, возможно, одной страницы со стеком, а содержимое адресного пространства может подгружаться из исполняемого файла на диске. Когда новый процесс начинает работу, он немедленно вызывает страничное прерывание, в ре­зультате которого первая страница программы подгружается с диска. Таким обра­зом, ничего не нужно загружать заранее, что позволяет быстро запускать про­граммы, а в память загружать только те страницы, которые действительно нужны программам. Наконец, в стек копируются аргументы и строки окружения, сигна­лы сбрасываются, а все регистры устанавливаются на ноль. С этого момента новая команда начинает исполнение.

Реализация потоков зависит от того, поддерживаются они ядром или нет. Если потоки ядром не поддерживаются, как, например, в 4BSD, реализация потоков целиком осуществляется в библиотеке, загружающейся в пространстве пользователя.

 

Планирование в системе 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