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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Петерсона для 2 потоков)
(Алгоритм Лампорта (вариант 1))
Строка 90: Строка 90:
  
 
===Алгоритм Лампорта (вариант <tex>1</tex>)===
 
===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году. Гарантирует взаимное
+
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году. <ref>[http://lamport.azurewebsites.net/pubs/bakery.pdf? A New Solution of Dijkstra's Concurrent Programming Problem]</ref> Гарантирует взаимное
 
исключение, отсутствие блокировки и отсутствие голодания.
 
исключение, отсутствие блокировки и отсутствие голодания.
 
=====Аналогия=====
 
=====Аналогия=====

Версия 19:58, 6 октября 2018

Определения

Определение:
Взаимное исключение (англ. 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. Взаимное исключение (англ. mutual exclusion): только один поток может быть в критической секции.

Условия прогресса:

  1. Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
  2. Отсутствие голодания (англ. starvation-freedom): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время. Может быть последовательно усиленно, превращаясь в условие честности (англ. fairness).
    • Квадратичное ожидание (англ. quadratic wait) — [math]O(n^2)[/math] операций.
    • Линейное ожидание (англ. linear wait) — [math]O(n)[/math] операций.
    • Первый пришел, первый обслужен (англ. first come first served)


Требование [math]First Come First Served (FCFS)[/math] формализуется так:

  1. Метод [math]lock[/math] должен состоять из двух последовательных секций.
  def lock():
     doorway
     waitnig
  1. Секция [math]doorway[/math] должны быть [math]wait free[/math], то есть выполняться за конечное число шагов, независимо от других потоков.
  2. Секция [math]waiting[/math] должна выполнять условие: Если [math]DW_i \Rightarrow DW_j[/math], то [math]res(WT_i) \Rightarrow res(WT_j)[/math].


Каждая программа может быть разделена на четыре секции, что приводит к четырем состояниям.
Порядок перехода между состояниями
Non-Critical Section
Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.
Trying
Процесс пытается войти в критический раздел.
Critical Section
В этом разделе разрешен доступ к общему ресурсу.
Exit 
Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.

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

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

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

Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в [math]1981[/math] г.[1] While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.Ошибка цитирования Отсутствует закрывающий тег </ref> Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания.

Аналогия

Алгоритм реализует идею пекарни с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.

Пусть покупатели это потоки, получившие номера [math]i[/math] от глобальной переменной.

Критическая секция

Когда поток хочет войти в критическую секцию, он должен проверить номера [math]n[/math], полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения [math]n[/math] у двух или нескольких потоков, в критическую секцию входит поток с наименьшим номером потока[math]i[/math].

(na, ia) < (nb, ib),

что эквивалентно:

(na < nb) or ((na == nb) and (ia < ib))

Когда поток заканчивает работу в критической секции, он освобождает номер n и выходит из критической секции.

Псевдокод
  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]FCFS[/math]), за счет того, что поток [math]P[/math] выполнивший [math]doorway (DW)[/math] до потока [math]Q[/math], имеет более ранний номер в очереди. Но метки должны быть бесконечными (их можно заменить на конечные метки).

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

Допустим, что два потока одновременно в [math]CS[/math]. Значит поток [math]id[/math] зашел в [math]CS[/math] последним, в то время как другой поток [math]k != id[/math] уже был в [math]CS[/math]. Но зайти в [math]CS[/math] можно если [math]want[k] == false[/math] или [math](label[k], k) \gt (label[id], id)[/math].

Случай 1: [math]want[k] == false[/math]

  • Противоречие.

Случай 2: [math](label[k], k) \gt = (label[id], id)[/math]

  • Но значит другой поток зашел по [math]want[id] == false[/math] выполнив свой [math]doorway[/math] до потока [math]id[/math] - противоречие.

Алгоритм Лампорта (вариант [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

См. также

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

  • G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_взаимного_исключения&oldid=66440»