Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Внутреннее устройство UNIX. Синхронизация и диспетчеризация процессов

#12 декабрь 2004

ка, и каждому КС соответствует тройка значений тонов лишь двух типов: О и 255

Божко А.Н., канд. техн. наук, Родионов С.В., МГТУ им. Н.Э. Баумана

 

Внутреннее устройство UNIX. Синхронизация и диспетчеризация процессов

 

Рассматриваются вопросы синхронизации и диспетчеризации процессов в операционной системе UNIX. Особое внимание уделяется аспектам внутреннего устройства UNIX, которые недостаточно освещены в литературе на русском языке.

 

В настоящее время растет интерес пользователей к операционной системе UNIX. Она завоевывает новые платформы и сферы приложений. Бурное развитие технических возможностей персональных компьютеров сделало возможным перенос полных версий операционной системы на платформу РС.

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

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

 

Внутренняя синхронизация процессов

Внутренняя синхронизация процессов основана на использовании аппарата событий для изменения состояний процессов в фазе “система”. Состояние процесса отражает поле p_stat структуры struct proc дескриптора процесса. Процесс может находиться в одном из следующих состояний в соответствии со значением поля p_stat:

SONPROC — процесс выполняется, т.е. его инструкции обрабатываются процессором;

SRUN — процесс готов к выполнению, но не обладает приоритетом, достаточным для использования ресурсов процессора;

SSLEEP — процесс ожидает некоторое событие, до наступления которого он не претендует на ресурсы процессора;

SZOMB — состояние промежуточного завершения, когда процесс не имеет образа в RAM, но сохраняет дескриптор в таблице процессов.

Взаимосвязь состояний процесса средствами внутренней синхронизации иллюстрирует следующая схема.

Схема внутренней синхронизации процессов

В каждый момент времени только один процесс может являться текущим, т.е. использовать ресурсы процессора и находиться в состоянии SONPROC. Другие процессы, обработка которых не блокирована ожиданием событий, находятся в состоянии SRUN. Их дескрипторы образуют очередь диспетчера dispq и связаны в таблице процессов посредством ссылочных полей p_linc структуры struct proc. Механизм синхронизации обеспечивает переключение текущего процесса в очередь диспетчера (switch out), когда он уступает процессор другому процессу, который, соответственно, включается (switch in) на выполнение. Переключение процессов между состояниями SRUN и SONPROC обеспечивает системная функция pswitch на основе сравнения приоритетов. Процесс остается текущим пока его приоритет выше, чем у любого процесса в очереди диспетчера. Планирование приоритетов процессов, претендующих на ресурсы процессора, обеспечивает механизм диспетчеризации процессов.

Для управления переключением процессов ядро использует системные флаги вытеснения runrun и kprunrun. Флаг runrun уведомляет системную функцию oswitch что она должна быть вызвана как только переключаемый процесс перейдет в фазу “пользователь”. Блокировка переключения в фазе “система” необходима для гарантии целостности системных данных. Флаг kprunrun позволяет реализовать переключение в фазе “система”, когда код текущего процесса достигает некоторых разрешенных точек вытеснения в адресном пространстве ядра.

Обычно при работе OS UNIX число “спящих” процессов в состоянии SSLEEP превышает число готовых к выполнению процессов в состоянии SRUN. Это объясняется наличием большого числа событий в реальной практике работы OS UNIX. Наиболее распространенная причина погружения процесса в “сон” связана с отработкой внешних прерываний от периферийных устройств. В частности, выполнение операций ввода-вывода не может быть реализовано параллельно с обработкой процессором кода программы процесса. Более высокий уровень приоритета контроллеров периферийных устройств, чем у процессора при выполнении программы процесса, заставляет последний переключаться на обработку внешних прерываний, переводя текущий процесс в состояние “сна” до завершения отработки прерывания. Поэтому увеличение числа “спящих” процессов характерно при интенсивном обмене с периферией, когда большое число процессов ожидает в состоянии SSLEEP наступления событий, связанных с завершением операций ввода-вывода, чтобы продолжить процессорную обработку своих данных. Кроме приоритетной обработки внешних прерываний события могут быть вызваны программными причинами. Например, выполнение процесса-предка может быть приостановлено системным вызовом wait до завершения процесса-потомка. В другом случае процесс “засыпает” при попытке чтения из пустого программного канала или при записи в полный программный канал. Рассмотренная содержательная трактовка события, как некоторой причины блокировки использования процессора данным процессом, формализуется следующим образом. Каждый тип ожидаемого события специфицируется уникальным целочисленным идентификатором, который сохраняется в поле p_wchan структуры struct proc дескриптора процесса, когда он находится в состоянии SSLEEP. Более конкретно, идентификатор события есть адрес определенной системной таблицы или элемента таблицы, связанной с ожидаемым ресурсом. Например, если процесс-предок ожидает завершения потомка, то идентификатор события, с которым будет связано его пробуждение, есть адрес дескриптора процесса-потомка. для погружения процесса в состояние “сна” используется системная функция sleep, которой в качестве аргументов передаются идентификатор события и приоритет процесса после пробуждения. После выполнения функции sleep поле состояния дескриптора текущего процесса принимает значение SSLEEP в поле p_wchan заносится идентификатор события, в поле приоритета p_pri фиксируется величина приоритета после пробуждения, а сам дескриптор включается в очередь дескрипторов “спящих” процессов sleepq. Очередь “спящих” процессов sleepq имеет организацию, аналогичную очереди диспетчера dispq. При погружении в “сон” текущего процесса процессор переключается на обслуживание самого приоритетного процесса из очереди диспетчера или обработку внешнего прерывания.

Для пробуждения процесса из состояния “сна”, при наступлении ожидаемого события, выполняется системная функция wakeup, аргументом которой является идентификатор объявленного события. При вызове функции wakeup все дескрипторы очереди “спящих” процессов sleepq, у которых значение поля p_wchan совпадает с аргументом функции wakeup, перемещаются в очередь диспетчера dispq для готовых к выполнению процессов. Если приоритет “разбуженного” процесса выше, чем у текущего, то он включается на обслуживание процессором по алгоритму, рассмотренному выше. Если в очереди “спящих” процессов нет процессов с идентификатором события, объявленным функцией wakeup, то “пробуждения” процессов не происходит. Последнее из состояний процесса, достижимых внутренней синхронизацией, есть состояние промежуточного завершения текущего процесса — SZOMB (состояние ‘зомби”). Состояние “зомби” имеет место, если процесс-потомок завершается по системному вызову exit или по сигналу до планируемой реализации системного вызова wait в процессе-предке. При этом образ завершившегося процесса освобождает адресное пространство, но его дескриптор временно сохраняется в таблице процессов, чтобы обеспечить корректную обработку системного вызова wait в процессе-предке.

В заключение следует отметить, что рассмотренный механизм внутренней синхронизации обслуживает процессы в фазе “система”, для синхронизации процессов в фазе “пользователь” используется аппарат сигналов OS UNIX.

 

Диспетчеризация процессов

Диспетчеризация процессов в OS UNIX реализует политику разделения времени процессора среди всех процессов, функционирующих в системе, на основе их приоритетов. Приоритеты процессов выражаются целыми числами. Их значения сохраняются в поле p_pri структуры struct proc дескриптора процесса. Во всех версиях OS UNIX кроме System V Release 4, принято, что приоритет процесса тем выше, чем меньше его численное значение (в SVR4 — наоборот). Процесс выбирается для обработки процессором из очереди диспетчера dispq на основе сравнения их приоритетов. Методы назначения приоритета различны в фазе “система” и в фазе “пользователь”.

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

Таблица системных приоритетов

Глобальный параметр

Системный приоритет

Событие ожидаемое процессом

PSWP

0

Свопинг

PRIBIO

20

Блоко-ориентированный ввод-вывод

PZERO

25

Уровень обслуживания сигналом

PPIPE

26

Пустой/полный программный канал

TTIPRI

28

Ввод с терминала

TTOPRI

29

Вывод на терминал

PWAIT

30

Вывод на терминал

PSLEE{

39

Пауза в ожидании сигнала

 

Глобальные параметры, определяющие значения системных приоритетов, задаются при генерации OS UNIX и подобраны таким образом, чтобы поддерживать равновесие в режиме разделения времени процессора. Глобальный параметр PZERO определяет границу между низкими и высокими приоритетами в фазе “система”. Системный приоритет со значением больше PZERO считается низким, не превышающий PZERO — высоким. Процессы, погруженные в состояние “сна” с высоким приоритетом, не могут быть выведены из этого состояния каким-либо сигналом. Процессы в состоянии “сна” с низким приоритетом могут быть “разбужены” сигналом. Текущий и готовые к выполнению процессы сохраняют фиксированный приоритет, пока они находятся в фазе “система”. После перехода в фазу “пользователь” приоритет процесса будет переопределен.

В фазе “пользователь” приоритет процесса имеет две составляющие пользовательскую и системную. Значения этих составляющих задают поля дескриптора процесса p_nice и p_cpu, соответственно. Полное значение приоритета в фазе “пользователь” устанавливается на основе определенной комбинации его составляющих в полях p_nice и p_cpu.

Начальное значение пользовательской составляющей приоритета определяется константой NZERO обычно равной 20. Пользовательская составляющая может быть изменена системным вызовом nice. Его аргумент определяет величину модификации поля p_nice и может задаваться в пределах от 0 до NZERO для непривилегированного процесса или в пределах от NZERO - до NZERO для привилегированного процесса. Поскольку значение пользовательской составляющей приоритета наследуется при порождении процесса, то непривилегированный процесс может только уменьшить приоритет, полученный от предка. Привилегированный потомок может как уменьшить, так и увеличить свой приоритет относительно предка.

Начальное значение системной составляющей приоритета (p_cpu) в фазе “пользователь” равно 0. Ее изменение зависит от времени использования процессора, т.е. времени, пока процесс остается текущим, работая в фазе “пользователь”. Для формирования системной составляющей приоритета используются прерывания от аппаратного таймера. При частоте сети питания 50 Гц прерывания от таймера генерируются 50 раз в секунду. Каждое таймерное прерывание увеличивает значение поля p_cpu, т.е. уменьшает системную составляющую приоритета на 1.

Результирующий приоритет процесса в фазе “пользователь” определяется по формуле:

p_pri = (p_nice - NZERO) + (p_cpu/16) + PUSER.

Разность (p_nice - NZERO) учитывает модификацию пользовательской составляющей приоритета системным вызовом nice. Отношение (p_cpu/16) учитывает усредненное значение системной составляющей приоритета. Усреднение необходимо, так как неизвестно, какую часть таймерного интервала проработал процесс на момент очередного прерывания от таймера. Кроме того, нежелательно частое переключение процессора между процессами с близкими значениями приоритетов. В частности, для равноприоритетных процессов в фазе “пользователь” выбранное значение усреднения (1/16) гарантирует переключение процессора не ранее, чем через 16 таймерных интервалов (320 мс), когда отношение (p_cpu/16) увеличится на 1. Константа PUSER по умолчанию равная 50, вводится для принудительного увеличения приоритета в фазе “пользователь” по отношению к приоритету в фазе “система”. Это сделано с целью стимулировать переключение процессора на выполнение процессов в фазе система, в частности, для ускорения доступа “разбуженных” процессов к ресурсам процессора. Для вычисления приоритета используется системная функция setpri , которой в качестве аргумента передается дескриптор процесса. Приоритет процесса, вычисленный функцией setpri, сравнивается с приоритетом текущего процесса, который сохраняет системная переменная curpri. Если приоритет какого-либо процесса из очереди диспетчера выше приоритета текущего, реализуется переключение процессора на более приоритетный процесс по схеме внутренней синхронизации процессов.

 

Свопинг и пейджинг процессов

Ограниченный объем RAM в общем случае не позволяет разместить в ней множество образов существующих процессов. Поэтому образы пассивных процессов, для размещения которых нет места в RAM, располагаются в специально отведенной области внешней памяти, называемой областью свопинга. Образы активных процессов располагаются в RAM. Перекачку (свопинг) образов процессов между оперативной и внешней памятью обеспечивает диспетчерский процесс (планировщик свопинга) .swapper (или sched для SUN OS) с идентификатором 0. Он осуществляет загрузку в RAM образов активных процессов и выгрузку в область свопинга образов пассивных процессов.

Свопинг происходит при практической реализации механизмов синхронизации, диспетчеризации и управлении иерархией процессов. Например, когда недостаточно места для размещения в RAM образа порожденного процесса-потомка, образ его предка может быть выгружен (откачен) в область свопинга, чтобы освободить место под образ потомка. В другом случае образ “разбуженного” процесса с высоким приоритетом может быть загружен (подкачен) из области свопинга в RAM для реализации процессорной обработки. В более общем случае образ любого активизированного процесса может быть загружен (подкачен) из области свопинга в RAM при наличии необходимости и свободной памяти, так же как образ любого пассивного процесса может быть выгружен (откачен) из RAM в область свопинга, чтобы освободить ресурсы памяти для более приоритетного процесса.

Диспетчерский процесс swapper, реализуя механизм свопинга, должен решать две задачи по определению процессов-претендентов для откачки из и подкачки в RAM. Для решения этих задач диспетчерский процесс, не имея фазы “пользователь”, осуществляет бесконечный цикл в фазе “система”. Цикл начинается с просмотра таблицы процессов для поиска процесса-претендента на загрузку или расширение своего образа в RAM. Если претендентов нет, диспетчер переходит в состояние ожидания их появления, используя системную функцию sleep которая назначает ему наивысший приоритет PSWP после пробуждения. диспетчер “пробуждается” системной функцией wakeup при появлении претендента на загрузку в RAM.

Если в RAM недостаточно свободного места для подкачки образа процесса-претендента на загрузку, диспетчер выгружает (откачивает) в область свопинга необходимое число пассивных процессов. Кандидаты на откачку определяются, прежде всего, среди “спящих” процессов с низким приоритетом (ниже PZERO), которые ожидают завершения сравнительно медленных операций ввода-вывода. Если таких процессов несколько, выбирается процесс с максимальным образом в RAM.

Чтобы обеспечить однозначность выбора процесса для загрузки в RAM или для выгрузки в область свопинга при прочих равных условиях, применяется временной критерий оценки. С этой целью в поле p_time структуры struct proc дескриптора любого процесса фиксируется время непрерывного пребывания в RAM или в области свопинга соответственно тому, где находится образ процесса. для свопинга выбирается процесс с максимальным значением в поле p_time. В современных версиях OS UNIX применяется альтернативный свопингу механизм, который использует страничную организацию памяти и называется пейджинг (paging). Пейджинг реализует перемещение активных страниц образов процессов из области свопинга в RAM, называемое подкачкой страниц по требованию, а также обратное перемещение пассивных страниц из RAM в область свопинга, называемое изъятием страниц. Схема реализации пейджинга подобна свопингу, за исключением того, что перемещению между RAM и областью свопинга подвергается не целиком образ процесса, а его отдельные страницы. При этом в RAM должны присутствовать только активные страницы образа процесса, к которым происходит частое обращение. Пассивные страницы, к которым нет обращений, могут быть откачены в область свопинга. Таким образом, при пейджинге загрузка в RAM полного образа процесса не является обязательной. Последнее обстоятельство обуславливает ряд преимуществ пейджинговой схемы по сравнению с традиционным механизмом свопинга, из которых наиболее существенными являются следующие.

·        Отсутствие ограничений на размер образа процесса по объему физической памяти. Связано с тем, что в RAM размещаются только активные страницы процесса, а не полные сегменты его образа.

·        Ускоренный старт процесса. Становится возможным, поскольку загрузка сравнительно небольшого числа активных страниц может быть реализована быстрее, чем загрузка всех сегментов процесса.

·        Экономия оперативной памяти. Поскольку для работы процесса необходима загрузка только активных страниц, память не расходуется на хранение редко используемых кодов и данных.

·        Увеличение производительности. Становится ощутимым при параллельном выполнении больших процессов, которые часто обращаются к небольшому подмножеству своих активных страниц.

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

Для размещения страниц в RAM при подкачке их по требованию используется пул свободных страниц. Определенный уровень наличия свободных страниц поддерживает процедура изъятия страниц, которая откачивает содержимое пассивных страниц в область свопинга и возвращает изъятые страницы в пул свободных страниц. Сохранение содержимого изъятой страницы в области свопинга происходит, если содержание страницы было модифицировано. Процедуры подкачки страниц по требованию и изъятия страниц являются основными в механизме пейджинга. Их реализует следящий процесс pageout (pagedaemon в SUN OS), называемый демоном страниц. Так же как и диспетчерский процесс swapper, управляющий свопингом, демон страниц — это один из начальных процессов OS UNIX. Он имеет идентификатор 2. Демон страниц следит за возрастом страниц и определяет, какие пассивные страницы следует отобрать у процессов, чтобы вернуть их в пул свободных страниц. Он также обеспечивает подкачку страниц по требованию в случае отказов страниц. Демон страниц активизируется, когда начинает ощущаться недостаток свободной памяти или для обработки отказов страниц.

В общем случае демон страниц успешно решает все проблемы по управлению памятью с помощью своих базовых процедур подкачки по требованию и изъятия страниц. Однако могут возникнуть критические ситуации, когда демон страниц не может предоставить необходимое число свободных страниц для удовлетворения запросов процессов к RAM и уровень свободной памяти опустится ниже определенного предела, заданно го системным параметром GPGSLO. В этом случае инициатива передается диспетчерскому процессу, который планирует и реализует свопинг целых процессов. Свопинг подразумевает возвращение в пул свободных страниц всех страниц образа процесса независимо от их возраста. Реализация свопинга продолжается, пока не восстановлен допустимый уровень свободной памяти. После этого инициатива по управлению памятью возвращается демону страниц.

 

Список литературы

1. Беликов ММ., Ливеровской А.Ю., Семик В.П., Шяудкулис В.И. Инструментальная мобильная операционная система ИНМОС. М.: Финансы и статистика 1985. 231 с.

2. Дансмур М., Дейвис Г. Операционная система UNIX программирование на языке Си. М.: Радио и связь 1989. 192 с.

3. Дунаев С. UNIX System V. Release 4.2. Общее руководство. М.: Диалог—МИФИ, 1995. 287 с.

4. Руководство по внутреннему устройству UNIX SVR4. Учебно-методический комплекс. Зеленоград, Институт Операционных Систем, 1995. 356 с.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, №3. 1997

ОПЕРАЦИОННЫЕ СРЕДЫ И ПРОГРАММИРОВАНИЕ

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)