Критическая секция
Важным понятием при изучении способов синхронизации процессов является понятие критической секции (critical section) программы. Критическая секция – это часть программы, исполнение которой может привести к возникновению race condition для определенного набора программ. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо организовать работу так, чтобы в каждый момент времени только один процесс мог находиться в своейкритической секции, связанной с этим ресурсом. Иными словами, необходимо обеспечить реализацию взаимоисключения для критических секций программ. Реализация взаимоисключения для критических секций программ с практической точки зрения означает, что по отношению к другим процессам, участвующим во взаимодействии, критическая секция начинает выполняться как атомарная операция. Давайте рассмотрим следующий пример, в котором псевдопараллельные взаимодействующие процессы представлены действиями различных студентов (таблица 5.1):
Здесь критический участок для каждого процесса – от операции "Обнаруживает, что хлеба нет" до операции "Возвращается в комнату" включительно. В результате отсутствия взаимоисключения мы из ситуации "Нет хлеба" попадаем в ситуацию "Слишком много хлеба". Если бы этот критический участоквыполнялся как атомарная операция – "Достает два батона хлеба", то проблема образования излишков была бы снята.
Таблица 5.1. | |||
Время | Студент 1 | Студент 2 | Студент 3 |
17-05 | Приходит в комнату | ||
17-07 | Обнаруживает,что хлеба нет | ||
17-09 | Уходит в магазин | ||
17-11 | Приходит в комнату | ||
17-13 | Обнаруживает, что хлеба нет | ||
17-15 | Уходит в магазин | ||
17-17 | Приходит в комнату | ||
17-19 | Обнаруживает,что хлеба нет | ||
17-21 | Уходит в магазин | ||
17-23 | Приходит в магазин | ||
17-25 | Покупает 2 батона на всех | ||
17-27 | Уходит из магазина | ||
17-29 | Приходит в магазин | ||
17-31 | Покупает 2 батона на всех | ||
17-33 | Уходит из магазина | ||
17-35 | Приходит в магазин | ||
17-37 | Покупает 2 батона на всех | ||
17-39 | Уходит из магазина | ||
17-41 | Возвращается в комнату | ||
17-43 | |||
17-45 | |||
17-47 | Возвращается в комнату | ||
17-49 | |||
17-51 | |||
17-53 | Возвращается в комнату |
Сделать процесс добывания хлеба атомарной операцией можно было бы следующим образом: перед началом этого процесса закрыть дверь изнутри на засов и уходить добывать хлеб через окно, а по окончании процесса вернуться в комнату через окно и отодвинуть засов. Тогда пока один студент добывает хлеб, все остальные находятся в состоянии ожидания под дверью (таблица 5.2).
Таблица 5.2. | |||
Время | Студент 1 | Студент 2 | Студент 3 |
17-05 | Приходит в комнату | ||
17-07 | Достает два батона хлеба | ||
17-43 | Приходит в комнату | ||
17-47 | Приходит в комнату |
Итак, для решения задачи необходимо, чтобы в том случае, когда процесс находится в своем критическом участке, другие процессы не могли войти в своикритические участки. Мы видим, что критический участок должен сопровождаться прологом (entry section) – "закрыть дверь изнутри на засов" – и эпилогом (exit section) – "отодвинуть засов", которые не имеют отношения к активности одиночного процесса. Во время выполнения пролога процесс должен, в частности, получить разрешение на вход в критический участок, а во время выполнения эпилога – сообщить другим процессам, что он покинул критическую секцию.
В общем случае структура процесса, участвующего во взаимодействии, может быть представлена следующим образом:
while (some condition) {
entry section
critical section
exit section
remainder section
}
Здесь под remainder section понимаются все атомарные операции, не входящие в критическую секцию.
Оставшаяся часть этой лекции посвящена различным способам программной организации пролога и эпилога критического участка в случае, когда очередность доступа к критическому участку не имеет значения.