Лекция 5. Механизмы синхронизации

Синхронизация параллельных процессов. Механизмы синхронизации.

Реализация задач синхронизации осуществляется с помощью механизмов (средств) синхронизации.

Такие механизмы многочисленны по способам реализации, степени эффективности и областям использования в различных ОС.

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

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

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

Любое высокоуровневое средство синхронизации можно реализовать с помощью низкоуровневых средств.

Реализация задачи взаимного исключения.

Аппаратная реализация взаимоисключений

блокировка памяти
запрещение прерываний
проверка и установка (test&set)
load/store

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

2. Запрещение прерываний. Процесс, использующий критический ресурс, должен блокировать обработку всех прерываний, поступающих на ВС. Он выходит из под контроля ОС и становится монопольным «хозяином» ЦП до тех пор, пока сам не размаскирует систему прерываний.

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

Негативные стороны данного решения:

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

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

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

Чтобы захватить основной критический ресурс необходимо предварительно захватить вспомогательный - переменную состояния.

Для реализации вспомогательного критического интервала можно воспользоваться блокированием прерываний, но длительность этой области будет мала (только проверить и установить, если это допустимо, переменную состояния).

Тогда проблема взаимного исключения решается в три этапа:

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

Вспомогательные критические интервалы на этапах 1 и 3 являются неделимыми взаимоисключаемыми примитивами для решения задач взаимного исключения.

Если на первом этапе обнаруживается, что критический ресурс занят, то используются два решения:

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

3. Проверка и установка (test&set).

Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала.

Данная операция реализована на многих компьютерах. Так, в IBM 360 (370) эта команда называлась TS (test and set).

Команда TS является аппаратно-поддерживаемой составной командой.

Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.

F(D) – блокирующая переменная ресурса D (0- свободен, 1 – занят)
Выполнение команды:
Перед входом в критический интервал процесс выполняет команду TS:
1. Циклически проверяется F(D)=0 (TEST)
2. Если F(D)=0 то F(D)=1 (SET)
3. Процесс входит в критическую секцию
4. После выполнения критической секции F(D)=0

Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида.

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

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

Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван.

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

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

Во избежание таких ситуаций в системе команд многих компьютеров предусмотрена единая, неделимая команда анализа и присвоения значения логической переменной (например, команды BТС, STR и BTS процессора Pentium),

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

Программная реализация взаимоисключений