Методы реализации взаимного исключения, классификация

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

• · внешние;
• · внутренние (пользовательские).

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

Первый вариант управления обычно реализуют в виде планировщика, второй — в виде монитора.

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

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

Если существует формальный алгоритм планирования, удовлетворяющий поставленной задаче и условиям работы системы, то работа в реальном времени будет возможна.

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

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

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

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

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

Алгоритм Петерсона — программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм Петерсона имеет смысл в системах на базе модели вычислений Фон-Неймана. Алгоритм Петерсона предложен в 1981 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера.

Алгоритм имеет следующие ограничения.

• · Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).
• · При ожидании ресурса процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

Алгоритм работает на использовании двух переменных: у каждого процесса есть собственная переменная flag[i] и общая переменная turn. Все переменные хранятся в общей для обоих процессов памяти. В переменной flag запоминается факт захвата ресурса, в переменной turn — номер захватившего ресурс процесса.

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

flag[0] = 0.

flag[1] = 0.

turn = 0.

turn = 1 turn = 0.

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

void mut_excl (int me /* 0 or 1 */).

{.

static int loser;

static int interested[2] = {0, 0};

int other; /* local variable */.

other = 1 — me;

interested[me] = 1;

loser = me;

while (loser == me && interested[other]).

;

/* critical section */.

interested[me] = 0;

}.

Алгоритм Деккера — программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм имеет смысл в системах на базе модели вычислений Фон-Неймана. Алгоритм Деккера усовершенствован Петерсоном (см. алгоритм Петерсона).

Алгоритм имеет следующие ограничения.

• · Алгоритм рассчитан только на 2 процесса (от этого ограничения свободен алгоритм пекарня (Bakery algorithm)).
• · При ожидании ресурса, процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

• · Если два процесса попытаются попасть в критическую секцию одновременно, алгоритм позволит войти только одному процессу, номер которого соответствует числу в переменной turn.
• · Если один из процессов уже находится в критической секции, другой процесс будет находится в ожидании. Необходимо заметить, что использование подобных алгоритмов в ОС РВ нежелательно, так как заблокированный процесс не снимается с обслуживания и напрасно расходует процессорное время.

f0:= false.

f1:= false.

turn:= 0 // or 1.

p0:

f0:= true.

while f1 {.

if turn? 0 {.

f0:= false.

while turn? 0 {.

}.

f0:= true.

}.

}.

// ждем.

// начало критической секции.

// конец критической секции.

turn:= 1.

f0:= false.

p1:

f1:= true.

while f0 {.

if turn? 1 {.

f1:= false.

while turn? 1 {.

}.

f1:= true.

}.

}.

// ждем.

// начало критической секции.

// конец критической секции.

turn:= 0.

f1:= false.

Алгоритм пекарня — программная реализация механизма взаимного исключения без запрещения прерываний. Алгоритм пекарня имеет смысл в системах на базе модели вычислений Фон-Неймана. В отличии от алгоритма Деккера и Петерсона отсутствует ограничение на число процессов.

Изобретен Лесли Лампортом (Leslie Lamport). Приоритет процессов задается случайным образом, алгоритм плохо предсказуем и практически не применим для решения задач реального времени. Кроме того, при ожидании ресурса процессы не снимаются с очереди на обслуживание и впустую тратят процессорное время (активное ожидание).

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

Критическая секция (Critical section) — это часть программы, в работу которой не может вмешаться другой процесс. Понятие «критическая секция» имеет смысл в тех системах, где возможно прерывание какого-либо действия. Как правило, критические секции используются в системах, сделанных на базе модели вычислений Фон-Неймана и Process Network. Другими словами, критические секции используются при программировании классических микроконтроллеров и микропроцессоров, при использовании ОС РВ или прерываний.

Критическая секция — один из механизмов управления процессами.

В ОС РВ к процессам, использующим взаимное исключение, предъявляются следующие требования:

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

Семафор — один из механизмов реализации взаимного исключения, позволяющий нескольким процессам обращаться к одному ресурсу. Идея семафоров предложена нидерландским ученым Дейкстрой в 15 г. Ввиду того, что семафоры управляются извне, самими процессами, которым нужен выделяемый ресурс, при использовании семафоров возможен ряд проблем:

• · взаимная блокировка;
• · утечка семафоров;
• · проблема синхронизации процедур семафоров.

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

Рассмотрим пример взаимной блокировки. Пусть имеются 2 процесса A и B, которым перед началом работы предоставлены ресурсы P1 и P2, соответственно. В какой-то момент времени процессу A понадобился P2, а процессу B — P1, но они их не получат, т.к. удерживаются предыдущими 97 процессами.

Предотвращение взаимной блокировки.

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

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

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

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

В программном обеспечении семафор обычно реализуется в виде блокирующей переменной s, изменение состояния которой производится одним (атомарным) действием (т.е. изменение нельзя прервать) с использованием функций P (s) и V (s).

В процессе инициализации в семафор записывается начальное значение. s = init_value;

Существует два действия над семафорами: P (s) — занять семафор V (s) — освободить семафор. При попадании на занятый семафор процесс блокируется до тех пор, пока другой процесс не освободит семафор.

Функция P (s):

if (s == 0).

Заблокировать_текущий_процесс ();

else.

s—;

Функция V (s):

if (s == 0).

разблокировать_один_из_процессов ();

else.

s++;

программируемый архитектура алгоритм драйвер В сетях Ethernet, имеющих способ доступа CSMA/CD, семафором является сама шина. Этот семафор может хранить только один бит информации, так как шина либо занята, либо нет. Таким образом, можно сказать, что в Ethernet для разделения ресурса шины используется бинарный семафор или мьютекс.

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