Страницы | 4. Задача взаимного исключения для двух потоков
Ниже приведено простейшее из известных решений задачи взаимного исключения для двух потоков, которое было опубликовано Гэри Л. Петерсоном в 1981 году.
bool x2 = false;
int q; // номер потока, которому предоставляется очередь входа в критическую секцию void thread_l() // поток thread_l
{
while(true)
{
non_critical_section_l(); // код вне критической секции
xl = true; // поток thread_l хочет войти в критическую секцию
q = 2; // предоставить очередь потоку thread_2
while(х2 && q == 2); // ждем, пока в критической секции находится поток thread_2
critical_section_l(); // входим в критическую секцию
xl = false; // поток thread_l находится вне критической секции
}
}
void thread_2() // поток thread_2
{
while(true)
{
non_critical_section_2(); // код вне критической секции
х2 = true; // поток thread_2 хочет войти в критическую секцию
q = 1; // предоставить очередь потоку thread_l
while(xl && q == 1); // ждем, пока в критической секции находится поток thread_l
critical_section_2(); // входим в критическую секцию
х2 = false; // поток thread_2 находится вне критической секции
}
}
Покажем, что это решение удовлетворяет трем вышеперечисленным требованиям, предъявляемым к решению задачи взаимного исключения.
Сначала рассмотрим требование безопасности. Поток thread_1 входит в критическую секцию critcai section_1 () только в том случае, если не выполняется условие (х2 && q == 2). Это эквивалентно тому, что выполняется условие ! (х2 && q == 2), которое в свою очередь можно привести к условию (! х2 и q == 1), используя логический закон отрицания конъюнкции. Кроме того, заметим, что если поток thread_1 находится в критической секции, то выполняется условие (x1 == true). Теперь введем предикат:
Q1 - х1 && (!х2 || q == 1)
который является инвариантом критической секции criticai_section_1(). То есть, если поток threadi находится внутри своей критической секции, то предикат qi принимает значение "истина". Аналогично определим предикат
Q2 = х2 && (!х1 || q == 2)
который является инвариантом критической секции critical_section_2(). Теперь найдем истинностное значение предиката <qi && Q2). Используя законы логики высказываний, получим:
Q1 && Q2 =
= (х1 && (!х2 II q == 1)) && (х2 && {!xl 1 1 я = = 2}) =
= X1 && х2 && (Ixl И q — 2) && (1x2 | | q = - 1 ) =
= X1 && х2 && ((!xl && !х2 ) 1 1 (!х1 &£ q == 1) II (1x2 && q == 2) ||
(q == 1 & & q == 2)) =
= X1 && х2 && ((!х1 && !х2 ) 1 1 (!xl && q == 1) II (1x2 && q == 2)) =
=(xl && !х1 && х2 && !х2) 1 1 ((xl && х2 && !xl && q == 1) 1 1
(XI && х2 && !х2 && q == 2) =
= false
Символ = обозначает равносильность или, другими словами, логическую эквивалентность выражений.
В результате получили, что предикат (qi && Q2) имеет тождественно ложное истинностное значение. Отсюда следует, что потоки thread i и thread_2 не могут одновременно находиться в своих критических секциях. Таким образом, доказано, что решение Петерсона удовлетворяет требованию безопасности.
Теперь рассмотрим требование поступательности. Поток thread i может быть заблокирован, только если выполняется условие (х2 && q == 2). Аналогично, поток thread_2 может заблокироваться только при выполнении условия (х 1 && q == 1). Рассмотрим предикат (х2 && q == 2) && (х 1 && q == 1) и найдем его истинностное значение. Получим:
(х2 && q == 2) && (х1 && q == 1) =
= xl && х2 && q == 1 && q == 2 = false
т. к. переменная q не может принимать одновременно значения 1 и 2. То есть этот предикат имеет тождественно ложное значение. Откуда следует, что потоки thread_1 и thread_2 не могут быть заблокированы одновременно. Таким образом, доказано, что решение Петерсона удовлетворяет требованию поступательности.
Наконец покажем, что решение Петерсона удовлетворяет требованию справедливости. Для этого предположим противное, т. е. поток thread_1 заблокирован. Тогда должно выполняться условие (х2 && q == 2). Из истинности этого условия следует, что ВЫПОЛНЯЮТСЯ условия (х2 «« true) И (q — 2). Но из выполнения условия поступательности следует, что поток thread_2 не может быть заблокирован одновременно с потоком thread_1. Следовательно, должны также выполняться условия (х2 == false) или (q == 1). Получили противоречие с нашим предположением. Поэтому наше предположение неверно и поток thread_1 не может быть заблокирован.
Таким образом, доказано, что алгоритм Петерсона решает задачу взаимного исключения для двух потоков. Решение задачи взаимного исключения для произвольного количества потоков является более сложным.
Подводя итог изложенного материала, можно сделать следующий вывод: синхронизация потоков может осуществляться чисто программными средствами, используя глобальные переменные.
