3.9. Задачи на обслуживание прерываемых процессов

4. Синхронизация потоков

Вопрос№18 4.1. Атомарные действия (операции)

Действием (action) называется изменение контекста потока.

Контекстом действия называется область памяти, к которой действие имеет доступ.

Действие называется атомарным (atomic action), или непрерываемым, или непрерывным, если они удовлетворяют двум требованиям:

- не прерывается во время своего исполнения;

- контекст действия изменяется только самим действием.

Атомарные действия будем обозначать следующим образом:

атомарное_действие := <действие>

Атомарные действия делят на две группы:

- элементарные атомарные действия (fine grained atomic actions);

- составные атомарные действия (coarse grained atomic actions).

К элементарным атомарным действиям относятся команды микропроцессора, которые не могут быть прерваны во время своего исполнения. На практике, к элементарным действиям относятся команды микропроцессора, которые выполняются за один цикл работы микропроцессора. Условно (теоретически) считают, что такими являются следующие команды:

- операции над данными, хранящимися в регистрах микропроцессора;

- операции чтения данных из памяти в регистры микропроцессора;

- операции записи данных в память из регистров микропроцессора.

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

disable_interrupt();

составное_действие;

enable_interrupt();

Запрещение прерываний не обеспечивает атомарность составного действия на мультипроцессорной системе, так как в этом случае контекст действия, исполняемого одним процессором, может параллельно измениться потоком, исполняемым другим процессом.

Вопрос№19 4.2. Частные и разделяемые переменные

Переменная, доступ к которой имеет только один поток, называется частной (private) или личной переменной потока.

Переменная, доступ к которой имеют несколько одновременно исполняемых (параллельных, конкурирующих) потоков, называется переменной разделяемой (shared) потоками.

Предполагаем, что параллельные потоки для доступа (записи или чтения) к разделяемой переменной используют атомарные действия.

Пример.

shared x,y;

private a,b;

a = x; //атомарное действие

y = b; //атомарное действие

x = x+1; //неатомарное действие, которое эквивалентно следующей последовательности атомарных действий

private r;

r = x;

++r;

x = r;

x = y; //неатомарное действие, которое эквивалентно следующей последовательности атомарных действий

private r;

r = y;

x = r;

Вопрос№20 4.3. Аксиомы параллельности

Одновременно исполняемые потоки называются параллельными, если каждый из них исполняется своим процессором.

Одновременно исполняемые потоки называются псевдопараллельными или конкурирующими (concurent), если они исполняются одним процессором.

Аксиома 1 (Non-interference postulate).

Параллельные потоки, которые не имеют общих разделяемых переменных, не взаимодействуют (интерферируют) друг с другом.

Аксиома 2 (Atomicity postulate). Операции чтения и записи значения частной переменной потока в разделяемые переменные являются атомарными.

Аксиома 3 (Interleaving postulate – постулат чередования).

Результатом исполнения псевдопараллельных (конкурирующих) потоков является последовательность атомарных действий этих потоков.

Если результат исполнения псевдопараллельных потоков зависит от последовательности атомарных действий, исполняемых этими потоками, то говорят, что эти потоки находятся в состоянии гонки (race condition). Как правило, состояние гонки является причиной ошибок работы многих многопоточных приложений. Причиной состояния гонки потоков является неправильная синхронизация этих потоков.

Вопрос№21 4.4. Синхронизация

Неформально, под синхронизацией параллельных потоков понимают обмен между этими потоками управляющими сигналами, которые координируют их исполнение.

Если рассматривать параллельные потоки формально, то синхронизация таких потоков это достижение некоторого фиксированного порядка (соотношения) между управляющими сигналами, которыми обмениваются эти потоки. Этот порядок обеспечивает некоторые фиксированные последовательности атомарных действий, исполняемых параллельными потоками.

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

Введем для условного атомарного действия следующее обозначение: <await(условие) действие>, где условие является логическим (булевым) выражением, значением которого является истина или ложь.

Условие атомарного действия выполняется следующим образом:

- оператор await ждет до тех пор, пока значение условия не станет истинным;

- как только условие стало истинным, выполняется действие.

В общем случае не существует эффективной реализации условного атомарного действия. Поэтому на практике рассматривают его частные случаи.

Частные случаи условного атомарного действия.

1. Взаимное исключение

<await(true) действие> := <действие>

В этом случае происходит безусловное выполнение атомарного действия.

Этот случай называется взаимным исключением, а код, исполняемый внутри атомарного действия, называется критической секцией.

2. Условная синхронизация.

<await(условие)>

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

Вопрос№22 4.5. Проблема взаимного исключения

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

Формулировка проблемы: требуется обеспечить, чтобы в любой момент времени с разделяемым ресурсом мог работать только один из параллельных потоков. Для решения этой задачи, программный код, который работает с разделяемым ресурсом, заключается в критическую секцию.

Требования к решению задачи взаимного исключения:

1. Безопасность (safety requirement) – в любой момент времени в критической секции может находиться только один поток;

2. Поступательность (progress reqirement) – любой поток должен находиться в критической секции ограниченное время (нет тупиков);

3. Справедливость (fairness requirment) – любой поток получает доступ в критическую секцию за ограниченное время (нет голодания).

Можно отметить, что из выполнения требования 3 следует выполнение требования 2. Однако требование 3 иногда невозможно выполнить. В этом случае доказывают, что решение задачи удовлетворяет только требованию 2.

Вопрос№23 4.6. Программное решение проблемы взаимного исключения

Программное решение проблемы взаимного исключения для двух параллельных потоков было впервые дано Петерсеном (Peterson G. L., 1981)

Алгоритм Петерсона

bool x1, x2;

int q;

x1 = false;

x2 = false;

void thread1()

{

while (true)

{

nonCriticalSection1();

x1 = true;

q = 2; //поток 1 хочет войти в критическую секцию

while (x2&&q==2); //но, сначала предоставляет право входа потоку 2

criticalSection1(); //ждет, пока поток 2 находится в своей критич. секции

x1 = false;

}

}

void thread2()

{

while (true)

{

nonCriticalSection2();

x2 = true;

q = 1;

while (x1&&q==1);

criticalSection2();

x2 = false;

}

}

Доказательство правильности алгоритма Петерсона.

1. Безопасность.

- Поток thread1 находится в критической секции 1 только в том случае, если выполняется условие:

- Кроме того, если поток thread1 находится в критической секции 1, то выполняется условие:

(x1==true)=1

Определим следующий предикат:

, который является инвариантом критической секции 1, т.е. если поток thread1 находится внутри критической секции, то выполняется условие Q1=1

Аналогично, введем инвариант для критической секции 2:

Теперь рассмотрим предикат

...

2. Поступательность.

- Поток thread1 может быть заблокирован только при условии, если

Аналогично, поток thread2 может быть заблокирован только при условии, если .

Рассмотрим предикат

Следовательно, потоки thread1 и thread2 не могут быть заблокированы одновременно

3. Справедливость.

Препдоложим обратное, т.е. что поток thread1 заблокирован. Тогда выполняется условие (1)

Отсюда следует, что

Но из пункта 2 следует, что поток thread2 не может быть заблокирован одновременно с потоком thread1. Откуда следует, что выполняется условие (не равно тождественно 1). Следовательно, поток thread2 пройдет цикл while и установит значения x2 = false или q=1, что противоречит условию (1).

Следовательно, наше предположение неверно. Поэтому требование справедливости также выполняется.

Вопрос№24 4.7. Програмное решение условной синхронизации

Решение проблемы условной синхронизации двух потоков

bool event;

event = false;

void thread1()

{ beforeEvent1();

while(!event); //ждать наступления события

afterEvent1();

}

void thread2()

{

beforeEvent2();

event = true; //установить событие

afterEvent2();

}

Очевидно, что поток thread1 выполнит функцию afterEvent1 только в том случае, если поток thread2 установит истинным значение переменной event.

Вопрос№25 4.8. Непрерываемые (атомарные) команды микропроцессора

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

В микропроцессоре Intel x86 существует команда xchg (а в настоящее время и много других команд), которая не прерывается во время своего исполнения и реализует следующую функцию:

void xchg (register int r, int*x)

{

register int temp;

temp = r;

r=*x;

*x=temp; }

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

Решение:

int lock = 0;

void thread_i()

{

while (true)

{

int key_i=1; //ключ для входа в критическую секцию

while (key_i==1) //ждем, пока вход закрыт

xchg(key_i, &lock);

criticalSection_i();

lock = 0;

nonCriticalSection_i();

}

}

Доказательство правильности работы алгоритма

1. Безопасность.

Доказывем от противного. Предположим, что key_i=0 и key_j=0 при некоторых i!=j. Это может быть только в том случае, если одна команда xchg прервала исполнение другой такой команды. Но это невозможно, так как команда xchg атомарная. Следовательно, наше предположение неверно, и в критической секции может находиться только один из потоков.

2. Поступательность.

Доказываем от противного. Предположим, что все потоки выполняют циклы while(key_i==1)

xchg(key_i,&lock);

Отсюда следует, что

Но это невозможно, так как величина является инвариантом в силу атомарности команды xchg. Следовательно, тупик невозможен.

3. Справедливость.

О справедливости нельзя сказать ничего определенного, так как не задан порядок доступа процессоров к шине данных.

Программная и аппаратная реализации синхронизации имеют существенный недостаток: впустую тратится процессорное время в циклах ожидания while для разрешения входа в критическую секцию. Поэтому все алгоритмы синхронизации получили общее название занятие ожиданием (busy waiting).

Однако аппаратная реализация синхронизации используется в мультипроцессорных системах, так как нет другого решения. Цикл ожидания while с атомарными командами микропроцессора называется спин-локом, или спин-блокировкой, или активным ожиданием (spin lock, иногда live lock).