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

Определения

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

Взаимное исключение (англ. 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].

См. также

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

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

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