Лекция: Введение. Проблема взаимоисключения

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

Предположим, что два потока, фиксирующие какие-либо события, пытаются дать приращение общей переменной Count, счетчику этих событий (рис. 8.1).

Рис. 8.1. Два параллельных потока увеличивают значение общей переменной Count

Операция Count++ не является атомарной. Код операции Count++ будет преобразован компилятором в машинный код, который выглядит примерно так:

(1) MOV EAX, [Count]; значение из Count помещается в регистр

(2) INC EAX; значение регистра увеличивается на 1

(3) MOV [Count], EAX; значение из регистра помещается обратно в Count

В мультипрограммной системе с разделением времени может наступить неблагоприятная ситуация перемешивания (interleaving'а), когда поток T1 выполняет шаг (1), затем вытесняется потоком T2, который выполняет шаги (1)-(3), а уже после этого поток T1 заканчивает операцию, выполняя шаги (2)-(3). В этом случае результирующее приращение переменной Count будет равно 1 вместо правильного приращения — 2.

Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций: в предыдущем примере можно представить и другое, более благоприятное развитие событий. В данном случае все определяется взаимными скоростями потоков и моментами их прерывания. Ситуации, подобные той, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей процессов, называются гонками (условия состязания, race conditions).

Для устранения условий состязания необходимо обеспечить каждому потоку эксклюзивный доступ к разделяемым данным. Такой прием называется взаимоисключением (mutual exclusion). Часть кода потока, выполнение которого может привести к race condition, называется критической секцией (critical section). Например, операции (1)-(3) в примере, приведенном выше, являются критическими секциями обоих потоков. Таким образом, взаимоисключение необходимо обеспечить для критических секций потоков.

В общем случае структура процесса, участвующего во взаимодействии, может быть представлена следующим образом [2]:

while (some condition) {

entry section

critical section

exit section

remainder section

}

Внешний цикл означает, что нас будут интересовать многочисленные попытки входа в критическую секцию (синхронизация единичных попаданий может быть обеспечена и другими средствами). Наиболее важным с точки зрения синхронизации является пролог ( entry section ), где принимается решение о том, может ли поток быть допущенным в критическую секцию. В эпилоге ( exit section ) обычно открывается шлагбаум для других потоков, а операции, не входящие в критическую секцию, сосредоточены в remainder section.