Лекція №8 Паралельні обчислення: семафори, монітори, повідомлення
Семафори
Взаємні виключення
Завдання "виробника-споживача" ("письменник-читач")
Монітори
Монітори з сигналами (монітори Хоара)
Монітори з оповіщенням і широкомовлення
Передача повідомлень
Синхронізація
Адресація
Формат повідомлення
Взаємні виключення
Рассмотренные ранее алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок, как для алгоритма Петерсона, так и при использовании аппаратных инструкций, предполагает достаточно длительное вращение процесса в пустом цикле, то есть напрасную трату драгоценного времени процессора, проверяя возможность войти в критическую область.
Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них – H – с высоким приоритетом, другой – L – с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все отведенное ему время (если не появится процесс с еще большим приоритетом). Тогда в случае, если процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.
Для того чтобы не допустить возникновения подобных проблем, были разработаны различные механизмы синхронизации более высокого уровня. Описанию ряда из них – семафоров, мониторов и сообщений – и посвящена данная лекция.
8.1. Семафоры
Первой большой работой в 1965 году, посвященной вопросам параллельных вычислений, стала монография Дейкстры, в которой рассматривалась разработка ОС как построение множества сотрудничающих последовательных процессов и создания эффективных и надежных механизмов поддержки этого сотрудничества. Эти механизмы легко применяются и пользовательскими процессами, если процессор и ОС делают их общедоступными.
Дейкстра предложил обобщающее средство синхронизации процессов, введя два новых примитива. В абстрактной форме эти примитивы, обозначенные Дейкстрой как P и V (это первые буквы голландских слов проверка (Proberen) и увеличение (Verhogen)), оперируют над целыми неотрицательными переменными S, называемыми семафорами. Мы их обозначим соответственно как Wait(s) и Signal(s) (или Down(s) и Up(s), как это было еще в нотации Algol-68).
Для передачи сигнала через семафор S процесс применяет примитив Signal(s), а для получения сигнала – примитив Wait(s). В последнем случае процесс приостанавливается до тех пор, пока не будет принят соответствующий сигнал.
Над семафором определены три операции.
Семафор может инициализирован только положительным числом.
Операция Wait(s) уменьшает значение семафора на 1. Если это значение становится отрицательным, то процесс блокируется (т.е. ждет, пока это уменьшение станет возможным). Успешная проверка, уменьшение и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное (или атомарное) действие.
Операция Signal(s) увеличивает значение семафора на 1 одним неделимым действием (выборка, инкремент и запоминание). Если это значение отрицательное, то заблокированный операцией wait процесс деблокируется. То есть, один из процессов выбирается системой и ему разрешается завершить свою операцию Wait(s). Операция увеличения значения семафора и активизации процесса также неделима. Есть различные организации семафоров относительно операции Signal(s), примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и остается равным 0, но число ожидающих процессов уменьшается на единицу.
Таким образом, если значение семафора больше нуля, операция Wait(s) уменьшает его (т.е. расходует один из сохраненных сигналов активации) и просто возвращает управление. Если значение равно нулю, процедура Wait(s) не возвращает управление процессу, а процесс переводится в состояние ожидания.
При выполнении операции Signal(s), если с этим семафором связаны один или несколько процессов, которые не могут завершить более раннюю операцию Wait(s), один из них выбирается системой и ему разрешается завершить свою операцию Wait(s). Таким образом, после операции Signal(s), применяемой к семафору, связанному с несколькими ожидающими процессами, значение семафора так и остается равным нулю, но число ожидающих процессов уменьшается на единицу. Ни один процесс не может быть блокирован во время выполнения операции Signal(s).
В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция Wait заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как Signal-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией Wait. Такая упрощенная версия семафора, как мы уже говорилось ранее, называется мьютексом (mutex, сокращение от mutual exclusion). В общем случае мьютексом называют синхронизационный примитив, который не допускает выполнения некоторого фрагмента кода больше как одним процессом. Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам.
Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов "писатель-читатель", выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи.
Введем два семафора: e - число пустых буферов и f - число заполненных буферов, причем в исходном состоянии е =N, a f =0. Предположим, что запись в буфер и считывание из буфера являются критическими секциями. Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда работа потоков (процессов) с общим буферным пулом может быть представлена блок-схемой (рис. 8.1), а фрагмент программы на С-подобном языке выглядит следующим образом:
Рис. 8.1. Использование семафоров для синхронизации потоков
// Глобальные переменные
#define N 256
int e = N, f = 0, b = 1;
void Writer ()
{
while(1)
{
PrepareNextRecord(); /* подготовка новой записи */
Wait(e); /* Уменьшить число свободных буферов, если они есть */
/* в противном случае - ждать, пока они освободятся */
Wait(b); /* Вход в критическую секцию */
AddToBuffer(); /* Добавить новую запись в буфер */
Signal(b); /* Выход из критической секции */
Signal(f); /* Увеличить число занятых буферов */
}
}
void Reader ()
{
while(1)
{
Wait(f); /* Уменьшить число занятых буферов, если они есть */
/* в противном случае ждать, пока они появятся */
Wait(b); /* Вход в критическую секцию */
GetFromBuffer(); /* Взять запись из буфера */
Signal(b); /* Выход из критической секции */
Signal(e); /* Увеличить число свободных буферов */
ProcessRecord(); /* Обработать запись */
}
}
Семафор может использоваться и в качестве блокирующей переменной. В рассмотренном выше примере, для того чтобы исключить коллизии при работе с разделяемой областью памяти запись в буфер и считывание из буфера являются критическими секциями. Взаимное исключение обеспечивается с помощью двоичного семафора b. Оба потока после проверки доступности буферов должны выполнить проверку доступности критической секции. Более подробная блок-схема взаимодействия двух процессов "писатель-читатель" представлена на рисунке 8.2.
Рис. 8.2. Использование двоичного семафора
В листинге 8.1 приведено более формальное определение примитивов семафоров. Предполагается, что примитивы атомарны, т.е. они не могут быть прерваны, и каждая из подпрограмм может рассматриваться как единый шаг.
Листинг 8.1. Определение семафорных примитивов
Struct Semaphore {
Int count;
QueueTypy queue;
}
void Wait(semaphore S) {
s.count--;
if (s.count < 0) {
/* Поместить процесс s.queue, s.count++ или =0 */
/* Заблокировать процесс */
}
}
void Signal(semsphore S)
{
s.count++;
if (s.count <= 0)
{
/* Удалить процесс Р из s.queue */
/* Поместить процесс Р в список активных */
}
}
Для хранения процессов используется очередь. При этом возникает вопрос о порядке извлечения из очереди. Наиболее корректный способ – использование принципа “первым вошел – первым вышел” (First In First Out - FIFO). При этом из очереди освобождается процесс, который был заблокирован дольше других. Семафор, использующий данный метод, называется сильным семафором (strong semaphore). Семафор, порядок извлечения процессов из очереди которого не определен, называется слабым семафором (weak semaphore).
На рис. 8.3 приведен пример работы сильного семафора.
Процессор А
Семафор S
= 1
Список
приостан.процессов |
| | | |
Список готовых
процессов |
| | C
| D
| B
Процессор B
Семафор S
= 0
Список
приостан.процессов |
| | | |
Список готовых
процессов |
| | A
| C
| D
Процессор D
Семафор S
= -1
Список
приостан.процессов |
| | | | B
Список готовых
процессов |
| | | A
| C
Процессор D
Семафор S
= 0
Список
приостан.процессов |
| | | |
Список готовых
процессов |
| | B
| A
| C
Процессор C
Семафор S
= 0
Список
приостан.процессов |
| | | |
Список готовых
процессов |
| | D
| B
| A
Процессор D
Семафор S
= -3
Список
приостан.процессов |
| | B
| A
| C
Список готовых
процессов |
| | | |
Процессор D
Семафор S
= -2
Список
приостан.процессов |
| | | B
| A
Список готовых
процессов |
| | | | C
Рис. 8.3. Пример работы механизмов семафора
Здесь процессы A, B и C зависят от результатов работы процесса D. Изначально работает процесс А (1); процессы B, C и D находятся в списке активных процессов, ожидая своей очереди. Значение семафора равно 1, это указывает на то, что один из результатов работы процесса D имеется в наличии. Когда процесс А выполняет инструкцию wait, он тут же получает разрешение на дальнейшую работу и вновь становится в очередь на выполнение в список активных процессов.
Затем приступает к работе процесс В (2), который в конечном счете также выполняет инструкцию wait, в результате чего процесс приостанавливается, давая возможность приступить к работе процессу D (3).
Когда процесс D завершает работу над получением нового результата, он выполняет инструкцию signal, которая позволяет процессу В перейти из списка приостановленных процессов в список активных (4).
Процесс D присоединяется к списку активных процессов, и к выполнению приступает процесс С (5), но тут же приостанавливается при выполнении инструкции wait. Точно так же приостанавливается и выполнение процессов А и В, давая возможность процессу D приступить к работе (6).
После того как получается новый результат процесса D, им выполняется инструкция signal, которая и переводит процесс С из списка приостановленных в список активных. Последующие циклы выполнения процесса D переведут в список активных А и В.
В следующем разделе мы рассмотрим алгоритм взаимоисключений, использование сильного семафора, в котором гарантирует невозможность голодания, но слабый семафор такой гарантии не дает, далее мы будем считать, что работают сильные семафоры, так как именно они используются в ОС.