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

Определения

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

Взаимное исключение (англ. 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] мы часто хотим получить выражение для [math]a_n[/math]. Например, для рекуррентного соотношения, задающего числа Фибоначчи:

[math] F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z[/math]

[math]a_n[/math] член может быть записан следующим образом: [math]a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).[/math]

Для этого можно использовать метод производящих функций (англ. generating function method).

Метод производящих функций

Алгоритм получения выражения для чисел [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].

См. также

• Производящая функция

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

• Решение рекуррентных соотношений