Алгоритмы взаимного исключения
Содержание
Определения
| Определение: |
| Взаимное исключение (англ. mutual exclusion) — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. race condition); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию. |
То есть критические секции не могут выполняться параллельно: . Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
| Определение: |
| Критическая секция (англ. critical section) — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения. |
Проблема
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
Успешное решение этой проблемы должно иметь по крайней мере три свойства:
- условие корректности
- Взаимное исключение: только один поток может быть в критической секции.
- условия прогресса
- Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
- Отсутствие голодания (англ. starvation-freedom): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время.
- Non-Critical Section
- Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.
- Trying
- Процесс пытается войти в критический раздел.
- Critical Section
- В этом разделе разрешен доступ к общему ресурсу.
- Exit
- Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.
Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел.
Алгоритмы взаимного исключения
Алгоритм Петерсона
threadlocal int id // 0 to N-1
shared int level[N]
shared int victim[N]
def lock:
for j = 1..N-1:
level[id] = j
victim[j] = id
while exist k: k != id and
level[k] >= j and
victim[j] == id:
pass
def unlock:
level[id] = 0
