Тема 9. Примитивы синхронизации

Семафоры

Определение семафора

Семафор – специальная переменная, имеющая целое значение и связанную с ним очередь. Над семафором определены три операции.

1. Семафор может быть инициализирован неотрицательным значением.

2. Операция wait уменьшает значение семафора. Если это значение становится отрицательным, процесс, выполняющий операцию wait, блокируется.

3. Операция signal увеличивает значение семафора. Если это значение не положительно, то заблокированный операцией wait процесс разблокируется.

Существует более ограниченная версия семафора – бинарный семафор, принимающий только значения 0 или 1.

Для хранения процессов, ожидающих семафоры, используется очередь. Если она обслуживается в соответствии с дисциплиной FIFO, то такой семафор называется сильным семафором, в противном случае – слабым семафором.

Применение семафоров

Взаимное исключение. Ниже показано решение задачи взаимоисключений с использованием семафора s. Пусть имеется n процессов. В каждом из процессов перед входом в КС выполняется вызов wait(s). Если значение s становится отрицательным, процесс приостанавливается. Если же значение равно 1, оно уменьшается до нуля, и процесс немедленно входит в КС. Поскольку s больше не является положительным, ни один другой процесс не может войти в КС.

semaphore s = 1:

. . . . . . . . .

wait(s);

/* Критическая секция */

signal(s);

/* Остальной код */

Семафор инициализируется значением 1. Следовательно, первый процесс, выполняющий wait(s), сможет немедленно попасть в КС, устанавливая при этом значение семафора равным 0. Любой другой процесс при попытке войти в КС обнаружит, что он занят. Соответственно, произойдет блокировка процесса, а значение семафора будет уменьшено до -1. Пытаться войти в КС может любое количество процессов; каждая неуспешная попытка уменьшает значение семафора. После того как процесс, вошедший в КС первым, покидает его, s увеличивается, и один из заблокированных процессов (если таковые имеются) удаляется из очереди семафора и активизируется. Таким образом, как только планировщик ОС предоставит ему возможность выполнения, процесс тут же сможет войти в КС.

Сигнализирующий семафор. Это семафор с нулевым начальным значением. Процесс сигнализирует о событии, выполняя операцию signal(s). Другие процессы ожидают события, выполняя операцию wait(s).

Мьютексы

Мьютекс – упрощенная версия семафора, это переменная, которая может находиться в одном из двух состояний: блокированном и неблокированном.

Значение мьютекса устанавливается двумя процедурами. Если процесс (или поток) собирается войти в КС, он вызывает процедуру mutex_lock. Если мьютекс не заблокирован, т.е. вход в КС разрешен, запрос выполняется и вызывающий процесс входит в КС. Если же мьютекс заблокирован, то процесс блокируется до тех пор, пока другой процесс, находящийся в КС, не выйдет из нее, вызвав процедуру mutex_unlock. Если мьютекс блокирует несколько процессов, то из них выбирается один.

Хотя семафоры обеспечивают решение для всех видов проблем синхронизации, им присущи следующие недостатки.

1. Процесс, использующий семафор, должен быть осведомлен о других процессах, использующих этот же семафор, так как операции над семафорами во всех взаимодействующих процессах должны быть координированы.

2. Операции над семафорами в процессах должны быть тщательно отлажены. Пропуск одной из операций может привести к несостоятельности (нарушение целостности разделяемого ресурса) или к взаимной блокировке.

3. Программы, использующие семафоры, очень трудно проверять на корректность.

Мониторы

Чтобы упростить написание программ, был предложен примитив синхронизации более высокого уровня.

Монитор – набор процедур, переменных и других структур данных, объединенных в особый модуль. Это высокоуровневая конструкция языка программирования, которая обеспечивает функциональность, эквивалентную функциональности семафоров, но при этом легче управляется. Мониторы реализованы в языках программирования Concurrent Pascal, Pascal-Plus, Modula-2,-3, Java.

Структура монитора

Монитор представляет собой программный модуль, состоящий из инициализирующей последовательности, одной или нескольких процедур и локальных данных. Основные характеристики монитора следующие.

1. Локальные переменные монитора доступны только его процедурам; внешние процедуры доступа к локальным данным монитора не имеют.

2. Процесс входит в монитор путем вызова одной из его процедур.

3. В мониторе в определенный момент может выполняться только один процесс; любой другой процесс, вызвавший монитор, будет приостановлен в ожидании доступности монитора.

Первые две характеристики напоминают объекты в объектно-ориентированном программировании. Соблюдение третьего условия позволяет монитору обеспечить взаимоисключения. Данные монитора доступны в этот момент только одному процессу, следовательно, защитить совместно используемые данные можно, поместив их в монитор. Если данные в мониторе представляют некий ресурс, то монитор обеспечивает взаимоисключения при обращении к ресурсу.

Для широкого применения в параллельных вычислениях мониторы должны включать инструмент синхронизации. Предположим, например, что процесс использует монитор и, находясь в мониторе, должен быть приостановлен до выполнения некоторого условия. При этом требуется механизм, который не только приостанавливает процесс, но и освобождает монитор, позволяя войти в него другому процессу. Позже, когда условие окажется выполненным, а монитор доступным, приостановленный процесс сможет продолжить свою работу с того места, где он был приостановлен.

Монитор поддерживает синхронизацию при помощи переменных условия, располагающихся и доступных только в мониторе. Работать с этими переменными могут две функции.

1. cwait(c): Приостанавливает выполнение вызывающего процесса по условию c. Монитор при этом доступен для использования другим процессом.

2. csignal(c): возобновляет выполнение процесса, приостановленного вызовом cwait(c). Если имеется несколько таких процессов, выбирается один из них; если таких процессов нет, функция не делает ничего.

На рис. 9.1 показана структура монитора. Хотя процесс может войти в монитор посредством вызова любой его процедуры, мы будем рассматривать монитор как имеющий единственную точку входа, которая позволяет обеспечить наличие в мониторе не более одного процесса в любой момент времени. Другие процессы, которые пытаются войти в монитор, присоединяются к очереди процессов, приостановленных в ожидании доступности монитора. После того как процесс вошел в монитор, он может временно приостановиться, выполнив вызов cwait(x); после этого процесс помещается в очередь процессов, ожидающих повторного входа в монитор при выполнении условия. Если процесс, выполняющийся в мониторе, обнаруживает изменение переменной условия x, он выполняет операцию csignal(x), которая сообщает об обнаруженном изменении соответствующей очереди.

Вопросы для самоконтроля

1. Что такое состояние состязания?

2. Что такое семафор?

3. Какие операции определены для семафоров?

4. В чем различие между сильными и слабыми семафорами?

5. Приведите пример применения семафора для достижения взаимного исключения.

6. Реализуйте при помощи семафоров следующую задачу. Требуется организовать критическую секцию, в которой одновременно могут находиться не более n процессов.

7. Приведите пример применения сигнализирующего семафора.

8. Как реализовать семафоры в ОС, умеющей блокировать прерывания?

9. Дайте определение мьютекса.

10. В чем отличие мьютекса от бинарного семафора?

11. Можно ли синхронизировать два потока одного процесса, используя семафор в ядре, если потоки реализованы в пространстве ядра? Если потоки реализованы в пространстве пользователя? Предполагается, что потоки остальных процессов не имеют доступа к семафору. Поясните ответы.

12. Поясните принцип работы монитора.

13. В чем преимущество монитора перед семафором?

14. Для чего нужны в мониторах переменные условия (условные переменные)?