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