Операционная система UNIX - Андрей Робачевский

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

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

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

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

Каждый компьютер имеет аппаратный таймер или системные часы, которые генерируют аппаратное прерывание через фиксированные интервалы времени. Временной интервал между соседними прерываниями называется тиком процессора или просто тиком (CPU tick, clock tick). Как правило, системный таймер поддерживает несколько значений тиков, но в UNIX это значение обычно устанавливается равным 10 миллисекундам, хотя это значение может отличаться для различных версий операционной системы. Большинство систем хранят это значение в константе HZ, которая определена в файле заголовков <param.h>. Например, для тика в 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]. Ядро системы преобразует это значение в тики, на основании которых и производится уменьшение таймера. Напомним, что тик является максимальным временным разрешением, которое может обеспечить система. В версиях System V для установки таймера реального времени используется вызов alarm(2), позволяющий указать интервал в секундах. UNIX SVR4 позволяет установить таймеры высокого разрешения с помощью системного вызова hrtsys(2), для которого время указывается в микросекундах. С помощью этого вызова также достигается совместимость с BSD, которая обеспечивается библиотечной функцией settimer(3). Аналогично, в BSD UNIX вызов alarm(3) реализован в виде библиотечной функции.

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