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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритмы взаимного исключения)
(Алгоритмы взаимного исключения)
Строка 39: Строка 39:
 
         level[id] = j
 
         level[id] = j
 
         victim[j] = id
 
         victim[j] = id
         while exist k: k != id '''and'''
+
         '''while''' '''exist''' k: k != id '''and'''
 
               level[k] >= j '''and'''
 
               level[k] >= j '''and'''
 
               victim[j] == id:
 
               victim[j] == id:
Строка 49: Строка 49:
 
===Алгоритм Лампорта (вариант <tex>1</tex>)===
 
===Алгоритм Лампорта (вариант <tex>1</tex>)===
  
   '''threadlocal int''' id // 0 to N-1
+
   '''threadlocal int''' id <font color=green>// 0 to N-1</font>
 
   '''shared boolean''' want[N] '''init''' false
 
   '''shared boolean''' want[N] '''init''' false
 
   '''shared int''' label[N] '''init''' 0
 
   '''shared int''' label[N] '''init''' 0
 
   '''def''' lock:
 
   '''def''' lock:
 
     want[id] = true
 
     want[id] = true
     label[id] = max(label) + 1
+
     label[id] = '''max'''(label) + 1
     while exists k: k != id '''and'''
+
     '''while''' '''exists''' k: k != id '''and'''
 
           want[k] '''and'''
 
           want[k] '''and'''
 
           (label[k], k) < (label[id], id) :
 
           (label[k], k) < (label[id], id) :
Строка 63: Строка 63:
  
 
===Алгоритм Лампорта (вариант <tex>2</tex>)===
 
===Алгоритм Лампорта (вариант <tex>2</tex>)===
 +
 +
  '''threadlocal int''' id  <font color=green>// 0 to N-1</font>
 +
  '''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'''
  
 
==См. также==
 
==См. также==

Версия 10:58, 25 сентября 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. Взаимное исключение: только один поток может быть в критической секции.
условия прогресса
  1. Отсутствие взаимоблокировок (англ. deadlocks): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
  2. Отсутствие голодания (англ. starvation-freedom): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время.


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

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

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

Алгоритм Петерсона

  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

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

См. также

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