2.1.3.2. Алгоритмы планирования процессов в Windows nt

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

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

Windows NT поддерживает 32 уровня приоритетов, разделенных на два класса – класс реального времени и класс переменных приоритетов. Нити реального времени, приоритеты которых находятся в диапазоне от 16 до 31, являются более приоритетными процессами и используются для выполнения задач, критичных ко времени.

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

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции – квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если:

• блокируется, уходя в состояние ОЖИДАНИЕ;

• завершается;

• исчерпан квант процессорного времени;

• в очереди готовых появляется более приоритетная нить.

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

2.1.4. Средства синхронизации и взаимодействия процессов

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

Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например (рисунок 1.2), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл «Заказы» другие программы. Переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла «Заказы». Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла «Заказы» имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс А решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой предположим равным трем. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, исчерпан квант процессорного времени). Очередной процесс В, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в третью позицию имя своего файла и нарастил значение переменной на единицу, после чего был прерван. Когда в очередной раз управление будет передано процессу А, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию три, поверх имени файла процесса В.

Рис. 1.2. Пример необходимости синхронизации

Таким образом, процесс В не сможет распечатать свой файл.

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