Алгоритмы взаимного исключения
Содержание
Определения
| Определение: |
| Взаимное исключение (англ. mutual exclusion) — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. race condition); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию. |
То есть критические секции не могут выполняться параллельно: . Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
| Определение: |
| Критическая секция (англ. critical section) — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения. |
Проблема
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
Успешное решение этой проблемы должно иметь по крайней мере два свойства:
- Взаимное исключение: только один поток может быть в критической секции.
- Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
Каждая программа процесса может быть разделена на четыре секции, что приводит к четырем состояниям. Выполнение программ осуществляется через эти четыре состояния в порядке:
- Non-Critical Section
- Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.
- Trying
- Процесс пытается войти в критический раздел.
- Critical Section
- В этом разделе разрешен доступ к общему ресурсу.
- Exit
- Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.
Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел try и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел.
