Текст книги "Операционная система UNIX"

Автор книги: Андрей Робачевский

сообщить о нарушении

Текущая страница: 18 (всего у книги 39 страниц)

Планирование выполнения процессов

Как и оперативная память, процессор является разделяемым ресурсом, который должен быть справедливо распределен между конкурирующими процессами. Планировщик процессов как раз и является той подсистемой ядра, которая обеспечивает предоставление процессорных ресурсов процессам, выполняющимся в операционной системе. UNIX является системой разделения времени, это означает, что каждому процессу вычислительные ресурсы выделяются на ограниченный промежуток времени, после чего они предоставляются другому процессу и т.д. Максимальный временной интервал, на который процесс может захватить процессор, называется временным квантом (time quantum или time slice). Таким образом создается иллюзия, что процессы выполняются одновременно, хотя в действительности в каждый момент времени выполняется только один (на однопроцессорной системе) процесс.

UNIX является многозадачной системой, а это значит, что одновременно выполняются несколько приложений. Очевидно, что приложения предъявляют различные требования к системе с точки зрения их планирования и общей производительности. Можно выделить три основных класса приложений:

□ Интерактивные приложения. К этому классу относятся командные интерпретаторы, текстовые редакторы и другие программы, непосредственно взаимодействующие с пользователем. Такие приложения большую часть времени обычно проводят в ожидании пользовательского ввода, например, нажатия клавиш клавиатуры или действия мышью. Однако они должны достаточно быстро обрабатывать такие действия, обеспечивая комфортное для пользователя время реакции. Допустимая задержка для таких приложений составляет от 100 до 200 миллисекунд.

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

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

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

В этом разделе мы рассмотрим основные принципы и механизмы планирования в традиционных UNIX-системах. Начнем с обработки прерываний таймера, поскольку именно здесь инициируются функции планирования и ряд других действий, например, отложенные вызовы (callout) и алармы (alarm).

Обработка прерываний таймера

Каждый компьютер имеет аппаратный таймер или системные часы, которые генерируют аппаратное прерывание через фиксированные интервалы времени. Временной интервал между соседними прерываниями называется тиком процессора или просто тиком (CPU tick, clock tick). Как правило, системный таймер поддерживает несколько значений тиков, но в UNIX это значение обычно устанавливается равным 10 миллисекундам, хотя это значение может отличаться для различных версий операционной системы. Большинство систем хранят это значение в константе HZ, которая определена в файле заголовков . Например, для тика в 10 миллисекунд значение HZ устанавливается равным 100.

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

□ Обновление статистики использования процессора для текущего процесса

□ Выполнение ряда функций, связанных с планированием процессов, например пересчет приоритетов и проверку истечения временного кванта для процесса

□ Проверка превышения процессорной квоты для данного процесса и отправка этому процессу сигнала SIGXCPU в случае превышения

□ Обновление системного времени (времени дня) и других связанных с ним таймеров

□ Обработка отложенных вызовов (callout)

□ Обработка алармов (alarm)

□ Пробуждение в случае необходимости системных процессов, например диспетчера страниц и свопера

Часть перечисленных задач не требует выполнения на каждом тике. Большинство систем вводят нотацию главного тика (major tick), который происходит каждые n тиков, где n зависит от конкретной версии системы. Определенный набор функций выполняется только на главных тиках. Например, 4.3BSD производит пересчет приоритетов каждые 4 тика, a SVR4 обрабатывает алармы и производит пробуждение системных процессов раз в секунду.

Отложенные вызовы

Отложенный вызов определяет функцию, вызов которой будет произведен ядром системы через некоторое время. Например, в SVR4 любая подсистема ядра может зарегистрировать отложенный вызов следующим образом:

int co_ID = timeout(void (*fn)(), caddr_t arg, long delta);

где fn() определяет адрес функции, которую необходимо вызвать, при этом ей будет передан аргумент arg, а сам вызов будет произведен через delta тиков.

Ядро производит вызов fn() в системном контексте, таким образом функция отложенного вызова не должна обращаться к адресному пространству текущего процесса (поскольку не имеет к нему отношения), а также не должна переходить в состояние сна.

Отложенные вызовы применяются для выполнения многих функций, например:

□ Выполнение ряда функций планировщика и подсистемы управления памятью

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

□ Опрос устройств, не поддерживающих прерывания

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

Эти функции хранятся в системной таблице отложенных вызовов, организация которой отличается для различных версий UNIX. Поскольку просмотр этой таблицы осуществляется каждый тик при обработке высокоприоритетного прерывания, для минимизации влияния этой операции на функционирование системы в целом, организация этой таблицы должна обеспечивать быстрый поиск нужных функций. Например, в 4.3BSD и SCO UNIX таблица отложенных вызовов организована в виде списка, отсортированного по времени запуска. Каждый элемент хранит разницу между временем вызова функции и временем вызова функции предыдущего элемента таблицы. На каждом тике значение этой величины уменьшается на единицу для первого элемента таблицы. Когда это значение становится равным 0, производится вызов соответствующей функции и запись удаляется. На рис. 3.14 приведена схема организации этой таблицы.

Рис. 3.14. Организация таблицы отложенных вызовов

Алармы

Процесс может запросить ядро отправить сигнал по прошествии определенного интервала времени. Существуют три типа алармов – реального времени (real-time), профилирования (profiling) и виртуального времени (virtual time). С каждым из этих типов связан таймер интервала (interval timer, или itimer). Значение itimer уменьшается на единицу при каждом тике. Когда значение itimer достигает нуля, процессу отправляется соответствующий сигнал.

Указанные таймеры обладают следующими характеристиками:

ITIMER_REAL	Этот таймер используется для отсчета реального времени. Когда значение таймера становится равным нулю, процессу отправляется сигнал SIGALRM.
ITIMER_PROF	Этот таймер уменьшается только когда процесс выполняется в режиме ядра или задачи. Когда значение таймера становится равным нулю, процессу отправляется сигнал SIGPROF.
ITIMER_VIRT	Этот таймер уменьшается только когда процесс выполняется в режиме задачи. Когда значение таймера становится равным нулю, процессу отправляется сигнал SIGVTALRM.

В версиях BSD UNIX для установки таймеров всех трех типов используется системный вызов settimer(2), для которого значение таймера устанавливается в микросекундах[34]34
  Некоторые системы System V, например SCO UNIX, также имеют в своем распоряжении этот системный вызов.


[Закрыть]. Ядро системы преобразует это значение в тики, на основании которых и производится уменьшение таймера. Напомним, что тик является максимальным временным разрешением, которое может обеспечить система. В версиях System V для установки таймера реального времени используется вызов alarm(2), позволяющий указать интервал в секундах. UNIX SVR4 позволяет установить таймеры высокого разрешения с помощью системного вызова hrtsys(2), для которого время указывается в микросекундах. С помощью этого вызова также достигается совместимость с BSD, которая обеспечивается библиотечной функцией settimer(3). Аналогично, в BSD UNIX вызов alarm(3) реализован в виде библиотечной функции.

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

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

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

Контекст процесса

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

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

□ Управляющая информация. Ядро использует две основные структуры данных для управления процессом – proc и user. Сюда же входят данные, необходимые для отображения виртуального адресного пространства процесса в физическое.

□ Окружение процесса. Переменные окружения процесса представляют собой строки пар вида:

 переменная=значение

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

□ Аппаратный контекст. Сюда входят значения общих и ряда системных регистров процессора. К системным регистрам, в частности, относятся:

 • указатель инструкций, содержащий адрес следующей инструкции, которую необходимо выполнить;

 • указатель стека, содержащий адрес последнего элемента стека;

 • регистры плавающей точки;

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

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

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

1. Текущий процесс переходит в состояние сна, ожидая недоступного ресурса.

2. Текущий процесс завершает свое выполнение.

3. После пересчета приоритетов в очереди на выполнение находится более высокоприоритетный процесс.

4. Происходит пробуждение более высокоприоритетного процесса.

Первые два случая соответствуют добровольному переключению контекста и действия ядра в этом случае достаточно просты. Ядро вызывает процедуру переключения контекста из функций sleep() или exit(). Третий и четвертый случаи переключения контекста происходят не по воле процесса, который в это время выполняется в режиме ядра и поэтому не может быть немедленно приостановлен. В этой ситуации ядро устанавливает специальный флаг runrun, который указывает, что в очереди находится более высокоприоритетный процесс, требующий предоставления вычислительных ресурсов. Перед переходом процесса из режима ядра в режим задачи ядро проверяет этот флаг и, если он установлен, вызывает функцию переключения контекста.

Принципы планирования процессов

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

Планирование процессов в UNIX основано на приоритете процесса. Планировщик всегда выбирает процесс с наивысшим приоритетом. Приоритет процесса не является фиксированным и динамически изменяется системой в зависимости от использования вычислительных ресурсов, времени ожидания запуска и текущего состояния процесса. Если процесс готов к запуску и имеет наивысший приоритет, планировщик приостановит выполнение текущего процесса (с более низким приоритетом), даже если последний не «выработал» свой временной квант.

Традиционно ядро UNIX является "непрерываемым" (nonpreemptive). Это означает, что процесс, находящийся в режиме ядра (в результате системного вызова или прерывания) и выполняющий системные инструкции, может быть прерван системой, а вычислительные ресурсы переданы другому, более высокоприоритетному процессу. В этом состоянии выполняющийся процесс может освободить процессор "по собственному в результате недоступности какого-либо ресурса перейдя в состояние сна. В противном случае система может прервать выполнение процесса только при переходе из режима ядра в режим задачи. Такой подход значительно упрощает решение задач синхронизации и поддержания целостности структур данных ядра.

Каждый процесс имеет два атрибута приоритета: текущий приоритет, на основании которого происходит планирование, и заказанный относительный приоритет, называемый nice number (или просто nice), который задается при порождении процесса и влияет на текущий приоритет.

Текущий приоритет варьируется в диапазоне от 0 (низкий приоритет) до 127 (наивысший приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0–65, для режима ядра – 66–95 (системный диапазон).

Процессы, приоритеты которых лежат в диапазоне 96–127, являются процессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений реального времени[35]35
  Схема нумерации текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования. Разделение между приоритетами режима ядра и задачи также зависит от версии. Здесь мы привели схему, используемую в SCO UNIX, при которой большему значению соответствует более высокий приоритет.


[Закрыть].

Процессу, ожидающему недоступного в данный момент ресурса, система определяет значение приоритета сна, выбираемое ядром из диапазона системных приоритетов и связанное с событием, вызвавшее это состояние. В табл. 3.3 приведены значения приоритетов сна для систем 4.3BSD UNIX и SCO UNIX (OpenServer 5.0). Заметим, что направление роста значений приоритета для этих систем различно – в BSD UNIX большему значению соответствует более низкий приоритет.

Таблица 3.3. Системные приоритеты сна

Ожидание загрузки в память сегмента/страницы (свопинг/страничное замещение)	0	95
Ожидание индексного дескриптора	10	88
Ожидание ввода/вывода	20	81
Ожидание буфера	30	80
Ожидание терминального ввода		75
Ожидание терминального вывода		74
Ожидание завершения выполнения		73
Ожидание события – низкоприоритетное состояние сна	40	66

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

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

Текущий приоритет процесса в режиме задачи p_priuser зависит от двух факторов: значения nice number и степени использования вычислительных ресурсов p_cpu:

p_priuser = a*p_nice – b*p_cpu,

где p_nice – постоянная составляющая, зависящая от параметра nice.[36]36
  Мы специально не выделили явно параметр nice по следующей причине. Традиционно, большему значению параметра nice соответствует меньший приоритет, это уже обсуждалось в главе 1. В данном обсуждении выбрана схема, при которой большему значению p_cpu соответствует больший приоритет. Поэтому в простейшем случае коэффициент а является отрицательным, a p_nice равно значению параметра nice (nice number).


[Закрыть]

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

Каждую секунду ядро пересчитывает текущие приоритеты процессов, готовых к запуску (приоритеты которых меньше 65), последовательно увеличивая их.[37]37
  Ядро последовательно уменьшает отрицательную компоненту времени использования процессора.


[Закрыть] Это перемещает процессы в более приоритетные очереди и повышает вероятность их последующего запуска.

Например, UNIX версии SVR3, использует следующую формулу:

p_cpu = p_cpu/2

Эта простая схема проявляет недостаток нивелирования приоритетов при повышении загрузки системы. Это происходит потому, что в этом случае каждый процесс получает незначительный объем вычислительных ресурсов и следовательно имеет малую составляющую p_cpu, которая еще более уменьшается благодаря формуле пересчета p_cpu. В результате степень использования процессора перестает оказывать заметное влияние на приоритет, и низкоприоритетные процессы (т.е. процессы с высоким nice number) практически «отлучаются» от вычислительных ресурсов системы.

В 4.3BSD UNIX для пересчета p_cpu используется другая формула:

p_cpu = p_cpu*(2*load)/(2*load+1)

Здесь параметр load равен среднему числу процессов, находившихся в очереди на выполнение за последнюю секунду, и характеризует среднюю загрузку системы за этот период времени. Этот алгоритм позволяет частично избавиться от недостатка планирования SVR3, поскольку при значительной загрузке системы уменьшение p_cpu при пересчете будет происходить медленнее.

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

Как правило, очередь на выполнение не одна. Например, SCO UNIX имеет 127 очередей – по одной на каждый приоритет. BSD UNIX использует 32 очереди, каждая из которых обслуживает диапазон приоритетов, например 0–3, 4–7 и т.д. При выборе следующего процесса на выполнение из одной очереди, т. е. из нескольких процессов с одинаковым текущим приоритетом, используется механизм кругового чередования (round robin).[38]38
  Round robin (англ.) означает петицию, подписи под которой располагаются по кругу – чтобы нельзя было определить, кто подписался первым. Отсюда и название схемы выбора процессов.


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