Критические секции

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

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

1-3 – свойства безопасности, 4 – живучести.

Критическая секция может быть реализована методом активной блокировки с помощью разделяемой логической переменной lock. Начальное значение – false

// вход

While lock do;

lock:=true;

//Крит. Секция

//выход

lock:=false;

Как добиться неделимости действий? В процессорах есть операция проверить и установить (test and set). Ее логика описывается следующим кодом

Function TS(var lock:Boolean):Boolean;

Var n:Boolean;

Begin

N:=lock; lock:=true; TS:=N;

End;

Тогда вход опишется так

While TS(Lock);

Если обозначить вход в Крит. cекцию CSEnter, а выход – CSExit, то задача взаимной блокировки решается следующим кодом

CSEnter;

S;

CSExit;

Задача условной синхронизации – <await (B) S;>

CSEnter;

While not(B) do

Begin

CSExit;

Delay; // задержка на случайное время

CSEnter;

End;

S;

CSExit;

Такая условная синхронизация применяется в сети Ethernet. Чтобы передать сообщение контроллер отправляет его в сеть и следит, не возникла ли коллизия. Если была коллизия, делается пауза случайной длины и повторяется передача. Интервал для длины паузы удваивается, если коллизии повторяются.

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

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

Алгоритм разрыва узла (алгоритм Питерсона) обеспечивает поочередный вход двух процессов в критическую секцию. Заводятся две логические переменные in1, in2 – значение true, если соответствующий поток находится в критической секции. Также заводится переменная Last, которая показывает какой поток пытается последним зайти в критическую секцию. Если оба процесса пытаются войти в Крит. Секцию, то выполнение последнего потока приостанавливается.

var in1, in2: boolean;

Last: integer;

//процесс 1

While true do

Begin

Last:=1; in1:=true;

While in2 and (last = 1) do;

//кр. Секция

in1:=false;

//некр. Секция

end;

//процесс 2

While true do

Begin

Last:=2; in2:=true;

While in1 and (last = 2) do;

//кр. Секция

in2:=false;

//некр. Секция

end;

Для n процессов алгоритм разрыва узла достаточно сложен.

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

Логика

Const number:integer =1; next:integer=1;

Var turn: array[1..n] of integer;

// процесс i

While true do

Begin

<turn[i]:=number; inc(number); >

//Здесь можно использовать обычный алгоритм CS (блокировка)

while turn[i]<>next do;

кр секция

inc(next)

некр секция

end;

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

Гораздо лучше, если критические секции реализуются на уровне ОС. В Windows 32 такая реализация имеется.

Для работы с критическими разделами используются следующие функции:

VOID InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - инициализация синхронизатора типа критический раздел.

lpCriticalSection - указатель на переменную типа CRITICAL_SECTION. Тип данных CRITICAL_SECTION является структурой, ее поля используются только Windows.

VOID EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - запрос на вход в критический раздел с ожиданием.

BOOL TryCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - запрос на вход в критический раздел без ожидания (с возвратом логического значения – вошли или нет).

VOID LeaveCriticalSection (LPCRITICAL_SECTION lpCriticalSection) - выход из критического раздела.

VOID DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection) - удаление критического раздела (обычно при выходе из программы).

В DELPHI критические секции описаны в модуле Windows. Для описания переменной типа критическая секция нужно использовать тип TRTLCriticalSection

Итак, для создания критического раздела необходимо инициализировать структуру CRITICAL_SECTION. Создав объект CRITICAL_SECTION, мы можем работать с ним, т.е. можем обозначить код, доступ к которому для одновременно выполняющихся задач требуется синхронизировать. Если один поток вошел в критический раздел, то следующий поток, вызывая функцию EnterCriticalSection с тем же самым объектом типа CRITICAL_SECTION, будет задержан внутри функции. Возврат произойдет только после того, как первый поток покинет критический раздел, вызвав функцию LeaveCriticalSection. В этот момент второй поток, задержанный в функции EnterCriticalSection, станет владельцем критического раздела, и его выполнение будет возобновлено.

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

Заметим, что возможно определение нескольких объектов типа критический раздел. Если в программе имеется четыре потока, и два из них разделяют одни данные, а два других - другие, то потребуется два объекта типа критический раздел.

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

Листинг 1. Ограничение доступа к массиву с использованием критических разделов

// Массив значений.

Var mas: array [1..1000] of integer;

// Критическая секция, регулирующая доступ к массиву

Var CritSec: TRTLCriticalSection;

…

// Инициализируем критический раздел

InitializeCriticalSection(CritSect);

// Запускаем потоки

Thread1.Resume;

Thread2.Resume;

DeleteCriticalSection(CritSec);

// Первый поток: запись в массив данных

procedure Thread1.Execute;

Var i: integer;

Begin // Запись значения в массив

// Запрос на вход в критический раздел

EnterCriticalSection(CritSec);

// Выполнение кода в критическом разделе

for i:= 1 to 1000 do mas[i]:= i;

// Выход из критического раздела:

// освобождаем критический раздел для доступа

// к нему других задач

LeaveCriticalSection(CritSec);

End;

// Второй поток: считывание данных из массива

procedure Thread2.Execute;

Var i: integer;

Begin // Считывание значений из массива

// Запрос на вход в критический раздел

EnterCriticalSection(CritSec);

// Выполнение кода в критическом разделе

for i:= 1 to 1000 do j:=mas[i];

// Выход из критического раздела:

// освобождаем критический раздел для доступа

// к нему других задач

LeaveCriticalSection(CritSec);

End;

И хотя приведенный нами пример подобного ограничения (см. листинг 1) чрезвычайно упрощен, он хорошо иллюстрирует работу синхронизатора типа критический раздел: пока один поток "владеет" массивом, другой доступа к нему не имеет.

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

Для упрощения работы с критическими секциями в DELPHI и C++Builder есть специальный класс TCriticalSection.

У него имеется конструктор Create без параметров, методы Acquire и Enter для входа в секцию, методы Release и Leave для выхода из секции. Для удаления объекта используется Free. Перепишем наш пример.