Блокировка памяти

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

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

Семафоры

Концепция использования семафоров для реализации взаимоисключений предложена Дейкстрой.

Семафор или общий семафор (semaphor e) - это целая переменная, значение которой можно опрашивать и менять только при помощи специальных неделимых (как команда testandset) операций P и V. Этиоперации являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор выполняет роль вспомогательного критического ресурса, т.к. операции P и V неделимы при своем выполнении и взаимно исключают друг друга.

Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.

Операция Р над семафором S записывается как P(S), алгоритм ее выполнения следующий:

if S>0 then S:=S-1 else <ожидать на S>

Операция V над семафором S, V(S), имеет следующий алгоритм выполнения:

if <один или несколько процессов ожидают на S>

then <разрешить одному из этих процессов продолжить работу>

else S:=S+1

Мьютексы

Одним из вариантов семафорных механизмов для организации взаимного исключения являются мьютексы. Термин mutex произошел от англ. mutual exclusion semaphore, что переводится как семафор взаимного исключения. Мьютексы реализованы во многих ОС, их основное назначение – организация взаимного исключения для задач из одного и того же или разных процессов.

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

Организация последовательного доступа к ресурсам с использованием мьютексов становится проще, т.к. в каждый момент только одна задача может владеть этим объектом. Для того чтобы объект мьютекс стал доступен задачам, принадлежащим разным процессам, при создании ему необходимо присвоить имя, потом это имя нужно передать «по наследству» задачам, которые должны его использовать для взаимодействия. Для этого вводятся специальные системные вызовы, в которых указываются начальное значение мьютекса, его имя и, возможно, атрибуты защиты. Если начальное значение мьютекса равно true, то считается, что задача, создающая этот объект, будет им сразу владеть. Можно указать в качестве начального значения false – в этом случае мьютекс не принадлежит ни к одной из задач и только специальным обращением к нему можно изменить его состояние