Реентерабельность системных функций

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

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

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

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

Проблема реентерабельности функций возникает в программировании и по совершенно другому поводу, не связанному с реализацией ОС. Речь идет о рекурсивных функциях, т.е. функциях, которые могут прямо или косвенно вызывать сами себя. Давно известна и основная причина нереентерабельности функций. Она заключается в использовании одних и тех же ячеек памяти для формальных параметров и локальных переменных при разных вызовах функции. Действительно, если при первом вызове функции в ячейку локальной переменной X будет занесено, например, число 10, а при втором – число 20, то после возобновления выполнения первого вызова значение X будет неверным.

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

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

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

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

При переходе от невытесняющей Windows 3.x к вытесняющей Windows 95 одна из серьезных проблем состояла в сохранении кода большого количества нереентерабельных системных функций. Проблему «решили» путем введения семафора, блокирующего повторный вызов для большого числа функций. Неприятным следствием этого стало взаимное тормозящее влияние процессов. В Windows NT этой проблемы нет, все функции реализованы реентерабельно.

Дисциплины диспетчеризации и приоритеты процессов

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

Одной из самых очевидных дисциплин является простая круговая диспетчеризация (round robin scheduling). Ее суть в следующем. Все активные процессы считаются равноправными и образуют круговую очередь. Каждый процесс получает от системы квант времени, по истечении которого планировщик выбирает для выполнения следующий процесс из очереди. Таким образом, если все процессы остаются активными, то система обеспечивает их равномерное продвижение, имитирующее параллельное выполнение всех процессов. Если текущий процесс блокируется, он выпадает из круга и попадает в список спящих процессов. Когда система активизирует один из спящих процессов, он включается в круговую очередь.

В некотором смысле противоположной дисциплиной является фоново-оперативная диспетчеризация (foreground/background scheduling) – одна из самых старых форм организации многозадачной работы. В простейшем случае она включает два процесса: фоновый процесс и оперативный процесс (процесс переднего плана). Фоновый процесс выполняется только тогда, когда спит оперативный процесс. При активизации оперативного процесса происходит немедленное вытеснение фонового, т.е. оперативный процесс имеет более высокий абсолютный приоритет. Обычно при такой дисциплине предполагается, что активизация оперативного процесса не потребует много процессорного времени, так что выполнение фонового процесса будет скоро возобновлено. Одним из примеров эффективного использования фоново-оперативной диспетчеризации является так называемая «фоновая печать», которую позволяет выполнить даже однозадачная MS-DOS. При этом процесс вывода файла на принтер рассматривается как процесс переднего плана, а обычная диалоговая работа с ОС – как фоновый процесс. Поскольку обслуживание прерываний от принтера занимает лишь доли процента процессорного времени, пользователь не ощущает никакого замедления работы.

Между описанными двумя крайностями лежит большое разнообразие дисциплин приоритетной диспетчеризации. Все они основаны на приписывании каждому процессу при его создании некоторого числа – приоритета. Более высокий приоритет должен давать процессу определенные преимущества перед низкоприоритетными процессами при работе планировщика.

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

· важность, ответственность данного процесса либо привилегированное положение запускающего процесс пользователя;

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

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

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

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

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