Реализация семафоров в ядре
Поскольку операции с семафорами являются частным случаем операторов await, их можно реализовать с помощью активного ожидания и методов из главы 3. Но единственная причина, по которой это может понадобиться, — потребность в написании параллельных программ с помощью семафоров, а не низкоуровневых циклических блокировок и флагов. Поэтому просто покажем, как добавить семафоры к ядру, описанному в предыдущих разделах. Для этого необходимо дополнить ядро дескрипторами семафоров и тремя дополнительными примитивами: createSem, Psem и Vsem. (Библиотеки наподобие Pthreads реализованы аналогично, но выполняются на основе операционной системы, поэтому используются с помощью обычных вызовов процедур и включают программные обработчики сигналов, а не аппаратные обработчики прерываний.)
Дескриптор семафора содержит значение одного семафора; его инициализация происходит при вызове процедуры createSem. Примитивы Psem и Vsem реализуют операции Р и V. Предполагается, что все семафоры являются обычными. Сначала покажем, как добавить семафоры к однопроцессорному ядру из раздела 6.1, а затем — как изменить полученное ядро, чтобы оно поддерживало мультипроцессоры, как в разделе 6.2.
Напомним, что в однопроцессорном ядре в любой момент времени выполняется только один процесс, а все остальные либо готовы к выполнению, либо ожидают завершения работы своих сыновних процессов. Как и раньше, индекс дескриптора выполняемого процесса хранится в переменной executing, а дескрипторы всех готовых к работе процессов хранятся в списке готовых к работе.
После добавления к ядру семафоров у процесса появляется еще одно возможное состояние: заблокированный на семафоре Процесс переходит в это состояние, когда ждет завершения операции Р. Чтобы отслеживать заблокированные процессы, каждый дескриптор семафора содержит связанный список дескрипторов процессов, заблокированных на этом семафоре. На отдельном процессоре выполняется только один процесс, который не входит ни в один из списков, дескрипторы всех остальных процессов находятся в списке либо готовых к работе, либо ожидающих, либо заблокированных на семафоре процессов.
Для каждого объявления семафора в параллельной программе вырабатывается один вызов примитива createSem; в качестве его аргумента передается начальное значение семафора Примитив createSem находит пустой дескриптор семафора, инициализирует значение семафора и список заблокированных процессов и возвращает "имя" дескриптора. Обычно этим именем является адрес дескриптора или его индекс в таблице адресов.
Созданный семафор используется с помощью вызовов примитивов Psem и Vsem, которые яв ляются процедурами ядра, реализующими операции Р и V. Обе процедуры имеют один аргумент -имя дескриптора семафора. Примитив Psem проверяет значение в дескрипторе. Если значение по ложительно, оно уменьшается на единицу, иначе дескриптор выполняемого процесса вставляете в список блокировки семафора. Аналогично процедура Vsem проверяет список блокировки деск риптора семафора. Если он пуст, значение семафора увеличивается, иначе из списка блокировю дескриптора семафора удаляется один дескриптор процесса и вставляется в список готовых к рабо те. Обычно списки заблокированных процессов реализуются в виде очереди с последовательно стью обработки FIFO, поскольку тогда гарантируется справедливость семафорных операций
В листинге 6.4 даны схемы перечисленных примитивов, которые нужно добавить к одно' процессорному ядру (см. листинг 6.1). Здесь также в конце каждого примитива вызываете! процедура dispatcher; она работает так же, как и раньше.
Для простоты реализации семафорных примитивов в листинге 6.4 дескрипторы семафоров повторно не используются. Если семафоры создаются один раз, этого достаточно. Однако обычно дескрипторы семафоров, как и дескрипторы процессов, приходится использовать повторно. Для того чтобы ядро поддерживало повторное использование дескрипторов семафоров, можно добавить примитив destroySem; он должен вызываться процессом, когда семафор больше не нужен. Другой подход — записывать в дескрипторы процессов имена всех соз-
Однопроцессорную реализацию примитивов семафора (см.
листинг 6.4) можно расши рить для мультипроцессора так же, как описано в разделе 6.2 и показано в листинге 6.3. Здесь также необходимо блокировать разделяемые структуры данных, поэтому для каждого дескриптора семафора используется отдельная блокировка. Дескриптор семафора блокируется в процедурах Psem и Vsem непосредственно перед доступом; блокировка снимается, как только исчезает потребность в дескрипторе. Блокировки устанавливаются и снимаются с помощью активного ожидания (см. решения задачи критической секции).
Вопросы, которые обсуждались в конце раздела 6.2, возникают и при реализации семафоров в многопроцессорном ядре. Например, процесс может требовать выполнения на определенном процессоре или на том же, на котором он выполнялся последний раз; может понадобиться совместное планирование процессов на одном процессоре. Чтобы выполнить эти требования или избежать конфликтов из-за разделяемого списка готовых к выполнению процессов, процессоры должны использовать отдельные списки готовых к работе процессов. В этой ситуации процесс, запускаясь примитивом Vsem, помещается в соответствующий список готовых к работе. Для этого примитиву Vsem нужно либо блокировать удаленный список готовых к работе, либо информировать другой процессор и позволить ему поместить разблокированный процесс в его список готовых к работе. При первом подходе нужна удаленная блокировка, при втором — использование механизма типа прерываний процессора для обмена сообщениями между процессорами.
224 Часть 1. Программирование с разделяемыми переменными
