Основы многопоточного и распределенного программирования

Реализация семафоров в ядре


Поскольку операции с семафорами являются частным случаем операторов 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. Программирование с разделяемыми переменными


Содержание раздела