Реализация мониторов в ядре
Мониторы тоже легко реализуются в ядре; в данном разделе показано, как это сделать. Их можно также моделировать с помощью семафоров; этому посвящен следующий раздел. Блокировки и условные переменные в таких библиотеках, как Pthreads, и таких языках программирования, как Java, реализованы аналогично описанному здесь ядру.
Используем семантику мониторов, определенную в главе 5. В частности, процедуры выполняются со взаимным исключением, а условная синхронизация использует дисциплину "сигнализировать и продолжить". Постоянные переменные мониторов хранятся в области памяти, доступной всем процессам, вызывающим процедуры монитора. Код, реализующий процедуры, может храниться в разделяемой памяти или копироваться в локальную память каждого процессора, который выполняет процессы, использующие монитор. Наконец, постоянные переменные инициализируются перед вызовом процедур. Для этого, например, можно выделять и инициализировать постоянные переменные перед созданием процессов, обращающихся к ним. (Или можно выполнять код инициализации при первом вызове процедуры монитора. Но этот способ менее эффективен, поскольку при каждом вызове придется проверять, первый ли он.)
Для реализации мониторов нужно добавить к ядру примитивы входа в монитор, выхода из него и операций с условными переменными. Нужны также примитивы для создания дескрипторов каждого монитора и каждой условной переменной (если они не создаются при инициализации ядра); эти примитивы здесь не показаны, поскольку аналогичны примитиву createSem в листинге 6.4.
Каждый дескриптор монитора mName содержит блокировку mLock и входную очередь дескрипторов процессов, ожидающих входа (или повторного входа) в монитор. Блокировка используется, чтобы обеспечить взаимное исключение. Если она установлена, в мониторе выполняется только один процесс, иначе — ни одного.
Дескриптор условной переменной содержит начало очереди дескрипторов процессов, ожидающих на этой переменной.
Таким образом, каждый дескриптор процесса, за исключением, возможно, выполняющихся процессов, связан либо со списком готовых к работе, либо с очередью входа в монитор, либо с очередью условной переменной. Дескрипторы условных переменных обычно хранятся вместе с дескриптором монитора, в котором объявлена условная переменная, чтобы избежать избыточной фрагментации памяти ядра и иметь возможность идентифицировать условную переменную просто в виде смещения от начала дескриптора соответствующего монитора.
Примитив входа в монитор enter (mName) находит дескриптор монитора mName, затем либо устанавливает блокировку монитора и разрешает выполняемому процессу продолжать работу, либо блокирует процесс в очереди входа в монитор. Чтобы обеспечить быстрый поиск дескриптора, в качестве идентификатора монитора mName во время выполнения программы обычно используют адрес его дескриптора. Примитив выхода из монитора exi t (mName) либо перемещает один процесс из очереди входа в список готовых к работе, либо снимает блокировку монитора.
Оператор wait (cv) реализован с помощью вызова примитива ядра wait (mName, cName), а оператор signal(cv) — примитива ядра signal (mName, cName). В обоих примитивах mName — это "имя" монитора (его индекс или адрес дескриптора), в котором вызывается примитив, a cName — индекс или адрес дескриптора соответствующей условной переменной. Оператор wait приостанавливает выполнение процесса на указанной условной переменной, затем либо запускает процесс из очереди входа в монитор, либо снимает блокировку монитора. Выполнение процедуры signal заключается в проверке очереди условной переменной. Если очередь пуста, то выполняется просто выход из примитива, иначе дескриптор из начала очереди условной переменной перемещается в конец очереди входа в монитор.
В листинге 6.5 приведены схемы этих примитивов. Как и в предыдущих ядрах, вход в примитивы происходит в результате вызова супервизора, переменная executing указывает на дескриптор выполняемого в данный момент процесса, а, когда он заблокирован, ее значение равно 0.
Поскольку процесс, вызвавший примитив wait, выходит из монитора, прими-
Несложно реализовать остальные операции с условными переменными. Например, для реализации empty (cv) достаточно проверить, есть ли элементы в очереди ожидания на cv. В действительности, если очередь задержки доступна процессам напрямую, для реализации операции empty не обязательно использовать примитив ядра. Причина в том, что выполняемый процесс уже заблокировал монитор, поэтому другие процессы не могут изменить содержание очереди условной переменной. Реализация операции empty без блокировки позволяет избежать затрат на вызов супервизора и возврат из него.
Операцию signal также можно реализовать более эффективно, чем показано в листинге 6.5. Например, процедура signal может всегда перемещать дескриптор из начала соответствующей очереди задержки в конец соответствующей очереди входа. Затем процедура signal в программе должна транслироваться в код, который проверяет очередь задержки и вызывает процедуру ядра mSignal, только если очередь пуста. После таких изменений отсутствуют затраты на вход в ядро и выход из него, когда операция signal ни на что не влияет. Независимо от реализации signal операция signal_all реализуется примитивом ядра, который перемещает все дескрипторы из указанной очереди задержки в конец списка готовых к выполнению.
226 Часть 1. Программирование с разделяемыми переменными
Приоритетный оператор wait реализуется аналогично неприоритетному. Отличие состоит лишь в том, что дескриптор выполняемого процесса должен быть вставлен в соответствующую позицию очереди задержки. Чтобы сохранять упорядоченность очереди, необходимо знать ранги ожидающих процессов. Логично хранить ранг процесса вместе с его дескриптором, что делает реализацию функции minrank тривиальной. Фактически minrank, как и empty, можно реализовать без входа в ядро, поскольку минимальный ранг можно прочитать непосредственно из выполняемого процесса.
Это ядро можно расширить для мультипроцессора, используя методику, описанную в разделе 6.2. Здесь также основным будет требование защиты структур данных ядра от одновременного доступа из процессов, выполняемых на разных процессорах. Необходимо также обеспечить отсутствие конфликтов в памяти, использование кэш-памяти, совместное планирование процессов и балансировку нагрузки процессоров.
На одном процессоре мониторы иногда можно реализовать значительно эффективнее, не используя ядра. Если вложенных вызовов мониторов нет или все вложенные вызовы являются открытыми, все процедуры мониторов коротки и гарантированно завершаемы, то взаимное исключение стоит реализовать с помощью запрета прерываний. Делается это следующим образом. На входе в монитор выполняемый процесс запрещает все прерывания. Выходя из процедуры монитора, процесс разрешает прерывания. Если процесс должен ожидать внутри монитора, он блокируется в очереди условной переменной; при этом фиксируется, что процесс выполняется с запрещенными прерываниями. (Обычно флаг запрета прерываний находится в регистре состояния процессора, который сохраняется при блокировке процесса.) Запускаясь в результате операции signal, ожидающий процесс, перемещается из очереди условной переменной в список готовых к выполнению, а процесс, выработавший сигнал, продолжает работу. Когда готовый к работе процесс ставится диспетчером на выполнение, он продолжает работу с запрещенными или разрешенными прерываниями, в зависимости от состояния процесса в момент блокировки. (Вновь созданные процессы начинают выполнение с разрешенными прерываниями.)
При такой реализации уже не нужны примитивы ядра (они превращаются или во встроенный код, или в стандартные подпрограммы) и дескрипторы мониторов. Поскольку во время работы процесса в мониторе прерывания запрещены, нельзя заставить процесс освободить процессор. Таким образом, процесс получает исключительный доступ к монитору до перехода в состояние ожидания или выхода из процедуры.
При условии, что процедуры монитора завершаемы, в конце концов процесс переходит в состояние ожидания или выходит из процедуры. Если процесс ожидает, то при его запуске и продолжении работы прерывания вновь запрещаются. Следовательно, процесс снова получает исключительное управление монитором, в котором он ожидал. Однако вложенные вызовы процедур монитора недопустимы. Если бы они были разрешены, то в мониторе, из которого был сделан вложенный вызов, мог начать выполнение еще один процесс, в то время как в другом мониторе есть ожидающий процесс.
По существу, описанным способом мониторы реализованы в операционной системе UNIX. При входе в процедуру монитора запрещаются прерывания только от тех устройств, которые могут привести к вызову процедуры этого же монитора до того, как прерываемый процесс перейдет в состояние ожидания или выйдет из монитора. В общем случае, однако, необходима реализация мониторов в ядре, поскольку не все программы удовлетворяют условиям этой специфической реализации. Например, только в такой "надежной" программе, как операционная система, можно надеяться на то, что все процедуры монитора завершаемы Кроме того, описанная реализация может работать только на одном процессоре. На мультипроцессоре будут нужны блокировки в той или иной форме, чтобы обеспечить взаимное исключение процессов, выполняемых на разных процессорах.
