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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
}}
 
}}
 
==Проблема==
 
==Проблема==
−
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
+
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение взаимного исключения - делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. Он контролирует доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.
−
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
+
 
−
#:<tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k</tex>
+
Успешное решение этой проблемы должно иметь по крайней мере эти два свойства:
−
#Домножить каждую строчку на <tex>z</tex> в соответствующей степени (<tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n \in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex> — это производящая функция, назовем ее <tex>G(z)</tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.
+
#Он должен реализовывать взаимное исключение: только один процесс может быть в критическом разделе за раз
−
#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде.
+
#Он должен быть свободен от взаимоблокировок (англ. ''deadlocks''): если процессы пытаются войти в критический раздел, один из них должен, в конечном счете, сделать это успешно, при условии, что процесс не останется в критическом разделе навсегда.
−
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
+
 
 +
Каждая программа процесса может быть разделена на четыре секции, что приводит к четырем состояниям. Выполнение программ осуществляется через эти четыре состояния в порядке:
 +
===Non-Critical Section===
 +
Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.
 +
===Trying===
 +
Процесс пытается войти в критический раздел.
 +
===Critical Section===
 +
В этом разделе разрешен доступ к общему ресурсу.
 +
===Exit===
 +
Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.
 +
Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел try и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел.
  
 
==Алгоритмы взаимного исключения==
 
==Алгоритмы взаимного исключения==

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

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

Non-Critical Section

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

Trying

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

Critical Section

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

Exit

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

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

[math]1[/math] пример

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_взаимного_исключения&oldid=66233»