Семафоры Дейкстры (Dijkstra)

Семафор: переменная S, примитивы P (proberen – проверка; down) и V (verhogen – увеличение, up)

V(S) – переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа во время выполнения этой операции.

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

В частном случае семафор S может принимать двоичные значения 0 и 1, превращаясь в блокирующую переменную (двоичный семафор).

Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания (если S = 0).

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

Проблема тупиков

Тупик - множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества.

Пример

Система имеет два внешних устройства.

Поток А запрашивает сначала принтер; а затем порт, а поток В запрашивает устройства в обратном порядке. В зависимости от cоотношения скоростей потоков они могут либо взаимно блокировать друг друга - тупик (б), либо образовывать очереди к разделяемым ресурсам (в), либо совершенно независимо использовать разделяемые ресурсы (г).

Условия возникновения взаимоблокировки (тупиковой ситуации):

1. Взаимное исключение. Каждый ресурс в данный момент или отдан ровно одному процессу, или недоступен.

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

3. Отсутствие принудительной выгрузки ресурсов. У процесса нельзя забрать принудительно ранее полученные ресурсы.

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

Стратегии борьбы с взаимоблокировками:

1. Пренебрежение проблемой в целом.

2. Обнаружение и устранение взаимоблокировок (восстановление).

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

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