Аппаратная реализация взаимоисключения. Команда testandset(a,b)

Команда запускается и выполняется до конца без прерывания, поэтому ее называют неделимая аппаратная команда. Действия: читает логическое значение переменной b, копирует его в a, и устанавливает для b значение истина. Пример использования: логарифм Деккера.

Семафора

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

Операция P – эквивалент входа взаимоисключения, V – выход взаимоисключения.

Двоичные семафоры – примитивные операции P и V. Считающие семафоры распределяют ресурсы.

Операция P над семафором S записывается P(S). Если S>0, то S=S-1, иначе ожидать на S.

Операция V над семафором S записывается V(S). Если 1 или более процессов ожидает на S, то разрешить одному из этих процессов продолжить работу, иначе S=S+1.

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

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно.

Пара производитель/потребитель

Один процесс – источник (вычисляет), другой – потребитель.

Кольцевой буфер

Буфер – это часть памяти, выделенная для обработки приложений и др.

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

Мониторы

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

Внутренние данные монитора могут быть либо глобальными (относящимися ко всем процедурам монитора), либо локальными (относящимися только к конкретной процедуре). Ко всем этим данным можно обращаться только изнутри монитора. Процессы, находящиеся вне монитора, не могут получить доступ к этим данным. Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, то эта процедура монитора выдает команду ожидания wait. Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе. Однако может оказаться, что уже имеются процессы, ожидающие освобождение данного ресурса. В этом случае монитор выполняет примитив оповещения SIGNAL, чтобы один из ожидающих процессов мог занять данный ресурс и покинуть монитор.

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

Монитор от семафора отличается уровнем реализации

Читатели и писатели

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

Тупики

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

Примеры тупиков:

1. Транспортная пробка

2. Обедающие философы

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