Морис Бах - Архитектура операционной системы UNIX
Оставшуюся часть алгоритма можно рассмотреть в качестве упражнения.
12.3.3.2 Wait
многопроцессорная версия алгоритма wait
{
для (;;) { /* цикл */
перебор всех процессов-потомков:
if (потомок находится в состоянии "прекращения существования") return;
P(zombie_semaphore); /* начальное значение — 0 */
}
}
Рисунок 12.15. Многопроцессорная версия алгоритма wait
Из главы 7 мы уже знаем о том, что во время выполнения системной функции wait процесс приостанавливает свою работу до момента завершения выполнения своего потомка. В многопроцессорной системе перед процессом встает задача не упустить при выполнении алгоритма wait потомка, прекратившего существование с помощью функции exit; если, например, в то время, пока на одном процессоре процесс-родитель запускает функцию wait, на другом процессоре его потомок завершил свою работу, родителю нет необходимости приостанавливать свое выполнение в ожидании завершения второго потомка. В каждой записи таблицы процессов имеется семафор, именуемый zombie_semaphore и имеющий в начале нулевое значение. Этот семафор используется при организации взаимодействия wait/exit (Рисунок 12.15). Когда потомок завершает работу, он выполняет над семафором своего родителя операцию V, выводя родителя из состояния приостанова, если тот перешел в него во время исполнения функции wait. Если потомок завершился раньше, чем родитель запустил функцию wait, этот факт будет обнаружен родителем, который тут же выйдет из состояния ожидания. Если оба процесса исполняют функции exit и wait параллельно, но потомок исполняет функцию exit уже после того, как родитель проверил его статус, операция V, выполненная потомком, воспрепятствует переходу родителя в состояние приостанова. В худшем случае процесс-родитель просто повторяет цикл лишний раз.
12.3.3.3 Драйверы
В многопроцессорной реализации вычислительной системы на базе компьютеров AT&T 3B20 семафоры в структуру загрузочного кода драйверов не включаются, а операции типа P и V выполняются в точках входа в каждый драйвер (см. [Bach 84]). В главе 10 мы говорили о том, что интерфейс, реализуемый драйверами устройств, характеризуется очень небольшим числом точек входа (на практике их около 20). Защита драйверов осуществляется на уровне точек входа в них:
P(семафор драйвера);
открыть (драйвер);
V(семафор драйвера);
Если для всех точек входа в драйвер использовать один и тот же семафор, но при этом для разных драйверов — разные семафоры, критический участок программы драйвера будет исполняться процессом монопольно. Семафоры могут назначаться как отдельному устройству, так и классам устройств. Так, например, отдельный семафор может быть связан и с отдельным физическим терминалом и со всеми терминалами сразу. В первом случае быстродействие системы выше, ибо процессы, обращающиеся к терминалу, не захватывают семафор, имеющий отношение к другим терминалам, как во втором случае. Драйверы некоторых устройств, однако, поддерживают внутреннюю связь с другими драйверами; в таких случаях использование одного семафора для класса устройств облегчает понимание задачи. В качестве альтернативы в вычислительной системе 3B20A предоставлена возможность такого конфигурирования отдельных устройств, при котором программы драйвера запускаются на точно указанных процессорах.
Проблемы возникают тогда, когда драйвер прерывает работу системы и его семафор захвачен: программа обработки прерываний не может быть вызвана, так как иначе возникла бы угроза разрушения данных. С другой стороны, ядро не может оставить прерывание необработанным. Система 3B20A выстраивает прерывания в очередь и ждет момента освобождения семафора, когда вызов программы обработки прерываний не будет иметь опасные последствия.
12.3.3.4 Фиктивные процессы
Когда ядро выполняет переключение контекста в однопроцессорной системе, оно функционирует в контексте процесса, уступающего управление (см. главу 6). Если в системе нет процессов, готовых к запуску, ядро переходит в состояние простоя в контексте процесса, выполнявшегося последним. Получив прерывание от таймера или других периферийных устройств, оно обрабатывает его в контексте того же процесса.
В многопроцессорной системе ядро не может простаивать в контексте процесса, выполнявшегося последним. Посмотрим, что произойдет после того, как процесс, приостановивший свою работу на процессоре A, выйдет из состояния приостанова. Процесс в целом готов к запуску, но он запускается не сразу же по выходе из состояния приостанова, даже несмотря на то, что его контекст уже находится в распоряжении процессора A. Если этот процесс выбирается для запуска процессором B, последний переключается на его контекст и возобновляет его выполнение. Когда в результате прерывания процессор A выйдет из простоя, он будет продолжать свою работу в контексте процесса A до тех пор, пока не произведет переключение контекста. Таким образом, в течение короткого промежутка времени с одним и тем же адресным пространством (в частности, со стеком ядра) будут вести работу (и, что весьма вероятно, производить запись) сразу два процессора.
Решение этой проблемы состоит в создании некоторого фиктивного процесса; когда процессор находится в состоянии простоя, ядро переключается на контекст фиктивного процесса, делая этот контекст текущим для бездействующего процессора. Контекст фиктивного процесса состоит только из стека ядра; этот процесс не является выполнимым и не выбирается для запуска. Поскольку каждый процессор простаивает в контексте своего собственного фиктивного процесса, навредить друг другу процессоры уже не могут.
12.4 СИСТЕМА TUNIS
Пользовательский интерфейс системы Tunis совместим с аналогичным интерфейсом системы UNIX, но ядро этой системы, разработанное на языке Concurrent Euclid, состоит из процессов, управляющих каждой частью системы. Проблема взаимного исключения решается в системе Tunis довольно просто, так как в каждый момент времени исполняется не более одной копии управляемого ядром процесса, кроме того, процессы работают только с теми структурами данных, которые им принадлежат. Системные процессы активизируются запросами на ввод, защиту очереди запросов осуществляет процедура программного монитора. Эта процедура усиливает взаимное исключение, разрешая доступ к своей исполняемой части в каждый момент времени не более, чем одному процессу. Механизм монитора отличается от механизма семафоров тем, что, во-первых, благодаря последним усиливается модульность программ (операции P и V присутствуют на входе в процедуру монитора и на выходе из нее), а во-вторых, сгенерированный компилятором код уже содержит элементы синхронизации. Холт отмечает, что разработка таких систем облегчается, если используется язык, поддерживающий мониторы и включающий понятие параллелизма (см. [Holt 83], стр.190). При всем при этом внутренняя структура системы Tunis отличается от традиционной реализации системы UNIX радикальным образом.
12.5 УЗКИЕ МЕСТА В ФУНКЦИОНИРОВАНИИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ
В данной главе нами были рассмотрены два метода реализации многопроцессорных версий системы UNIX: конфигурация, состоящая из главного и подчиненного процессоров, в которой только один процессор (главный) функционирует в режиме ядра, и метод, основанный на использовании семафоров и допускающий одновременное исполнение в режиме ядра всех имеющихся в системе процессов. Оба метода инвариантны к количеству процессоров, однако говорить о том, что с ростом числа процессоров общая производительность системы увеличивается с линейной скоростью, нельзя. Потери производительности возникают, во-первых, как следствие конкуренции за ресурсы памяти, которая выражается в увеличении продолжительности обращения к памяти. Во-вторых, в схеме, основанной на использовании семафоров, к этой конкуренции добавляется соперничество за семафоры; процессы зачастую обнаруживают семафоры захваченными, больше процессов находится в очереди, долгое время ожидая получения доступа к семафорам. Первая схема, основанная на использовании главного и подчиненного процессоров, тоже не лишена недостатков: по мере увеличения числа процессоров главный процессор становится узким местом в системе, поскольку только он один может функционировать в режиме ядра. Несмотря на то, что более внимательное техническое проектирование позволяет сократить конкуренцию до разумного минимума и в некоторых случаях приблизить скорость повышения производительности системы при увеличении числа процессоров к линейной (см., например, [Beck 85]), все построенные с использованием современной технологии многопроцессорные системы имеют предел, за которым расширение состава процессоров не сопровождается увеличением производительности системы.
