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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
'''Взаимное исключение''' (англ. ''mutual exclusion'') — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. ''race condition''); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.
 
'''Взаимное исключение''' (англ. ''mutual exclusion'') — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. ''race condition''); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.
 
}}
 
}}
−
 
 
То есть критические секции не могут выполняться параллельно: <tex>\forall i,j:i \neq j \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i </tex>. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
 
То есть критические секции не могут выполняться параллельно: <tex>\forall i,j:i \neq j \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i </tex>. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.
−
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Строка 12: Строка 10:
 
}}
 
}}
  
−
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
+
==Проблема==
−
 
 
−
<tex>
 
−
F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z</tex>
 
−
 
 
−
<tex>a_n</tex> член может быть записан следующим образом:  <tex>a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).</tex>
 
−
 
 
−
Для этого можно использовать метод производящих функций (англ. ''generating function method'').
 
−
 
 
−
==Метод производящих функций==
 
 
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
 
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
 
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
 
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
Строка 29: Строка 18:
 
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
 
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
  
−
==Примеры==
+
==Алгоритмы взаимного исключения==
 
===<tex>1</tex> пример===
 
===<tex>1</tex> пример===
  

Версия 09:59, 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) — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.


Проблема

Алгоритм получения выражения для чисел [math]a_{n}[/math], удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из [math]4[/math] шагов.

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math]):
    [math]a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k[/math]
  2. Домножить каждую строчку на [math]z[/math] в соответствующей степени ([math]z^{k} \cdot a_{k} = … \cdot z^{k}[/math]) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где [math]n \in [k, +\infty)[/math]. В левой части получится сумма [math]\displaystyle\sum_{n=0}^{\infty} a_nz^n[/math] — это производящая функция, назовем ее [math]G(z)[/math]. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее [math]G(z)[/math].
  3. Решить полученное уравнение, получив для [math]G(z)[/math] выражение в замкнутом виде.
  4. Разложить [math]G(z)[/math] в степенной ряд, коэффициент при [math]z_n[/math] будет искомым выражением для [math]a_n[/math].

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

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

См. также

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

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