Алгоритмы взаимного исключения

Определения

Определение:

Взаимное исключение (англ. mutual exclusion) — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. race condition); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.

То есть критические секции не могут выполняться параллельно: [math]\forall i,j:i \neq j \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i [/math]. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.

Определение:

Критическая секция (англ. critical section) — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.

Проблема

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

Успешное решение этой проблемы должно иметь по крайней мере три свойства:

условие корректности

1. Взаимное исключение: только один поток может быть в критической секции.

условия прогресса

1. Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
2. Отсутствие голодания (англ. starvation-freedom): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время.

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

Порядок перехода между состояниями

Non-Critical Section

Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.

Trying

Процесс пытается войти в критический раздел.

Critical Section

В этом разделе разрешен доступ к общему ресурсу.

Exit 

Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.

Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел [math]try[/math] и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел.

Алгоритмы взаимного исключения

Алгоритм Петерсона для [math]2[/math] потоков

Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в [math]1981[/math] г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Гарантирует взаимное исключение, отсутствие взаимной блокировки и отсутствие голодания.

Принцип работы: перед тем как начать исполнение критической секции кода, поток должен вызвать процедуру [math]lock()[/math] со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру [math]unlock()[/math], после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип алгоритмом Петерсона для двух потоков.

  threadlocal int id  // 0 or 1
  shared int want[2]
  shared int victim
  def lock:
       want[id] = true
       victim = id
       while want[1-id] and
             victim == id:
          pass
  
  def unlock:
    want[id] = false

Корректность алгоритма

Взаимное исключение

Потоки [math]0[/math] и [math]1[/math] никогда не могут попасть в критическую секцию в один момент времени: если [math]0[/math] вошёл в секцию, он установил [math]want[0][/math] в [math]true[/math]. Тогда либо [math]want[1] = false[/math] (тогда поток [math]1[/math] не в критической секции), либо [math]waiting = 1[/math] (тогда поток [math]1[/math] пытается войти в критическую секцию и крутится в цикле), либо поток [math]1[/math] пытается войти в критическую секцию после установки [math]want[1] = true[/math], но до установки [math]waiting[/math] и цикла. Таким образом, если оба процесса находятся в критической секции, должно быть [math] want[0] and want[1] and waiting = 0 and waiting = 1 [/math], но такого не может быть одновременно и мы пришли к противоречию.

Свобода от взаимной блокировки

Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной [math]waiting[/math], что невозможно.

Свобода от голодания

Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения [math]unlock()[/math] и повторного захода в [math]lock()[/math] процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.

Алгоритм Петерсона для [math]N[/math] потоков

Обобщение Алгоритм Петерсона для [math]N[/math] потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. Невезучий поток может ждать пока другие потоки [math]O(N^2)[/math] раз войдут в критическую секцию (квадратичное ожидание).

  threadlocal int id  // 0 to N-1
  shared int level[N]
  shared int victim[N]
  def lock: 
    for j = 1..N-1:  //Для входа в CS надо пройти на N-1 уровней
       level[id] = j  //Обобщаем want на уровень j: 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

Алгоритм Лампорта (вариант [math]1[/math])

  threadlocal int id  // 0 to N-1
  shared boolean want[N] init false
  shared int label[N] init 0
  def lock:
    want[id] = true
    label[id] = max(label) + 1
    while exists k: k != id and
          want[k] and
          (label[k], k) < (label[id], id) :
       pass
  def unlock:
    want[id] = false

Алгоритм Лампорта (вариант [math]2[/math])

  threadlocal int id  // 0 to N-1
  shared boolean want[N] init false
  shared int label[N] init 0
  def lock:
    choosing[id] = true
    label[id] = max(label!=inf) + 1
    choosing[id] = false
    while exists k: k != id and
          (choosing[k] or
          (label[k], k) < (label[id], id)) :
       pass
  def unlock:
    label[id] = inf

См. также

• Алгоритм_Лампорта_взаимного_исключения

Источники информации

• Mutual exclusion