Взаимоисключения. Понятие критической секции. Устаревшие подходы к организации взаимного исключения.

Ситуация гонок (race condition):

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

Например: 2 процесса имеют доступ к разделяемой памяти. В ней есть переменная целого типа со значением 5. Оба процесса пытаются увеличить на 1 ее значение одновременно. По идее она будет =7. Для этого надо загрузить значение в регистр, далее увеличить на 1 и выгрузить в память. Допустим 1й процесс выполнил MOV для перемещения из памяти в регистр. В этот моментпроизошло прерывание по таймеру и процесс снят с исплонения. В это время 2й процесс тоже выполнил MOV и INC, а потом снова MOV для перемещения из регистра в память => Переменная =6/. 1й процесс за это время дождался своей очереди и снова выполняется. Но первую MOV он уже выполнил, так что в его регистре уже было 5, далее INC и MOV обратно и имеем значение 6. Здесь возникает ситуация гонок.

Более серьезный пример:

301: 1000$ - 100$ = 900$ 1й оператор переводит 100$ с 301 на 768.

505: 1500$ + 200$ = 1700$ 2й оператор переводит 200$ с 768 на 505.

768: 2000$ - 100$ = 1900$

Пусть процесс запущенный 2м оператором был прерван после операции чтения остатков (1500 и 2000 соотв-но). Эти остатки он сохранил в своих структурах. Произошло прерывание, 1й процесс считает остатки с 301 и 768 (1000 и 2000 соотв-но) и все сделал верно. Затем снова 2й процесс, он получает 1700 и 1800, именно это она записывает в БД, в результате владелец 768 обнаружит недостачу. Нежелательные эффекты возможны тогда, когда один из участников даже не производит изменений, а только читает данные.

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

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

Требования, налагаемые на механизм взаимного исключения:

1) 2 и более процессов не должны ни при каких условиях находится одновременно в критических секциях.

2) В проге не дб предположений о скорости выполнения процесса и о количестве процессоров в системе.

3) Процесс находящийся вне критической секции не дб причиной блокировки др. процессов.

4) Недопустима ситуация вечного ожидания.

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

Использование блокировочной переменной:

Пусть есть некоторые данные, доступ к которым осущ-т несколько процессов. Для управления этим заведем в разделяемой памяти целочисленную переменную и примем соглашение что значение переменной: S=1 - означает что с раздел данными никто не работает, S=0 – с раздел данными работает 1 из процессов.

При запуске системы присвоим S=1 и доступ к данным будем осуществлять по схеме:

While (S==0) {} // пустой цикл, работает пока нельзя входить в критич. секцию

S=0; // запретим доступ другим процессам.

Section(); // функция

S=1; // разрешим доступ к разделяемым данным.

Все процессы имеющие доступ к раздел данным должнв следовать такой схеме. Выполнение процесса мб прервано в тот момент, когда он уже увидел число 1 в S и вышел из цикла while, но присвоить S=0 не успел. В этом случае другой процесс может тоже увидеть значение =1 и присвоить S=0 и войти в секцию. Затем управление будет передано 1му процессу, который проверку значения уже произвел, далее он S=0 и войдет в секцию. В результате оба процесса окажутся в секции, т.к. необходима атомарность (непрерывность) некоторых действий при организации взаимоисключений. Между while и S=0 не дб прерываний!

Запрет на внешние прерывания:

1) Запрет прерываний годится для кратковременных критич. секций с небольшим кодом.

2) Запрет прерываний годится только для работы с данными, нах-ся в ОЗУ.

3) Касается только 1 процессора, в системе с несколькими процессорами не дает эффекта.

4) В комбинации с активным ожиданием запрет прерываний приводит в зависанию системы.

5) Допускать запрет прерываний пользовательскими процессами просто опасно.

Чередование:

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

For {;;} // бесконечный цикл

{While (turn!=0) {}

Section(); // критическая секция 1й процесс

turn:=1;

NoneCriticalSection(); }

For {;;}

{While (turn!=1) {}

Section(); // критическая секция 2й процесс

turn:=0;

NoneCriticalSection(); }

Здесь показаны 2 процесса осуществляющие доступ к раздел данным в соотв. с маркером чередования (turn). Значение turn=0 – право на доступ имеет 1й процесс, =1 - …2й процесс. Каждый из процессов завершив критич. секцию передает ход другому процессу изменив turn и переходит к выполнению действий без доступа к раздел. данным.

Такой способ гарантирует процессам невозможность оказаться в критич. секции одновременно. Однако, если один из процессов передав ход другому быстро выполнит некритич действия и снова войдет в критич секцию, может оказаться что 21 процесс не дошел до критич секции и не передал ход 1ому. В результате 2й процесс не нуждаясь в доступе к раздел данным будет мешать доступу к этим данным 1му процессу.

Алгоритм Петерсона: (рассмотрим для 2х процессов)

В раздел памяти надо создать массив из 2х логич переменных interes[2]. Логич переем показывает нуждается ли соотв процесс в выполнении критич секции. Во время выполнения критич. секции соотв логич величина дб истина для конкретного процесса. Кроме того введем в раздел памяти переменную waits, которая будет показывать который из процессов в случае столкновения должен подождать завершения критич. секции другого процесса.

Принцип алгоритма:

Показать свою заинтересованность во входе в крит секцию – interes[0]:=true

Процесс заявляет о своей готовности подождать, если это надо. Процесс будет заносить в переем waits свой номер.

Void enter_section();

{ interes[0]:=true;

Waits:=0;

While (waits==0 && interes[1]) {} 1й процесс

}

Void leave_section();

{interes[0]:=false;}

Void enter_section();

{ interes[1]:=true;

Waits:=1;

While (waits==1 && interes[0]) {} 2й процесс

}

Void leave_section();

{interes[1]:=false;}

Алгоритм состоит из 2х функций: вход в критич. секцию и выход из нее. Единств недостаток – активное ожидание ( {} ).