Взаимоисключение необходимо в том случае, если процессы обращаются к разделяемым общим данным. Когда процесс обращается к разделяемым общим данным, то он находится в своём критическом участке. Для обеспечения взаимоисключения КУ необходимо в случае если хотя бы один процесс находится в своём КУ, исключить возможность вхождения для всех других процессов в их КУ.
Эта задача решается чисто программным способом. Одна команда машинного языка – неделимая операция. Информация о скоростях асинхронных параллельных процессов не известна. Процессы вне своих КУ не могут препятствовать другим процессам входить в их собственные КУ. Нельзя допускать бесконечного откладывания момента входа процессов в их КУ. Программно реализуется механизм взаимоисключения, который предложил математик Деккер.
1) алгоритм Деккера:
Постановка задачи.
Требуется обеспечить взаимоисключение КУ.
1 Модификация:
Не обеспечивается надежность при одновременном вхождении в критический участок (проблема решается при условии неделимости двух команд - условия и установки, test_and_set).
Модификация 2 вариант:
При одновременном входе в критический участок возможен бесконечный цикл, но задача защиты будет решена.
Модификация 3 вариант:
Цель – разомкнуть бесконечный цикл.
Этот алгоритм не требует специальных команд, обеспечивает полное взаимоисключение, и нет бесконечного цикла. Недостаток – сложность алгоритма для 3-х и более процессов.
2) Использование специальных команд:
Неделимая команда (test_and_set(x,y), test_and_clear(x,y)) + 1 алгоритм Деккера.
Это аппаратный метод.
Команда проверяет (возвращает) значение некоторой переменной, а затем устанавливает ее значение в 1. Функция
непрерываемая, во время ее выполнения никакой другой процесс не имеет доступа к той памяти, с которой работает функция (к переменной lock).
Пример:
1 void csBegin ( char *lock ) {
2 while (
testAndSet( lock ) );
3 }
4 void csEnd ( char *lock ) {
5
*lock = 0;
6 }
Команда testAndSet (строка 2) будет возвращать 1 до тех пор, пока другой процесс находится в критической секции, защищенной замком. Как только этот другой процесс выйдет из критической секции и установит замок в 0 (строка 5), наш процесс тут же вновь установит его в 1 и выйдет из цикла.
3) классический семафор, семафор Дейкстры.
Семафор – специальная защищенная переменная, значение которой можно опрашивать и изменять только специальными неделимыми командами.
S – семафор. Может иметь значения: 0, 1, 2, ….
0 – семафор закрыт.
1, 2, 3, … – показывает, что семафор открыт.
Существует 4 операции: создать, уничтожить, занять семафор, освободить семафор.
1) создать семафор – создается объект ядра семафор и его инициализация (всегда при создании открыт).
2)
– занять семафор.
3)
– освободить семафор
4) уничтожение – освобождение семафора.
Взаимное исключение двух потоков:
В рисунке ошибка. Оператор S=1 вынести из цикла, это инициализация семафора.
Использование бинарного семафора используется для организации взаимного исключения. Легко обеспечивать взаимодействие 3-х и более процессов.
Счетный семафор – семафор, который инициализируется значением более 1. Используется для учета ресурсов.
В современных ОС может быть реализована группа семафоров (UNIX).
