Механизмы синхронизации. Свойства и классификация

Механизмы синхронизации обеспечивают выполнение синхронных правил. Реализация синхронизирующих правил осуществляется с помощью механизмов синхронизации. Различаются механизмы синхронизации по:

1) выполняемым действиям

2) по степени приближённости к машинным командам

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

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

К низкоуровневым относится TS (test & set) — реализует проверку и установку состояния общей переменной в рамках одной машинной операции, что исключает возможность вмешательства других процессов. Такие варианты используются редко, или как базовые средства ОС.

Основные свойства.

Для осознанного выбора конкретного механизма необходимо зафиксировать требования к синхронизации. Как правило, механизмы сравнивают:

1) простота использования — определяется простотой синтаксиса и семантикой механизма синхронизации.

2) гибкость — определяет способность механизма быть использованным для реализации известных типов отношений между процессами в ясной и недвусмысленной форме.

3) проверяемость и понимаемость — определяет возможность применения формальных методов анализа

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

5) надёжность — определяет вероятность правильной работы механизма как в условиях предусмотренной спецификации, так и в аномальных условиях.

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

 

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

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

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

Такое решение не эффективно, т. к. всё сводится к однозадачному решению.

Указанного недостатка лишена двуступенчатая схема.

 

Механизмы синхронизации. Двухступенчатая схема

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

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

В этом случае можно эффективно использовать механизм блокировки прерывания. Работа вспомогательной переменной может проходить в режиме с заблокированным прерыванием. Поскольку переменное состояние является универсальным средством не зависящем от вида ресурса, то работа с ним может быть реализована как ф-ция ОС.

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

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

 

Механизмы синхронизации. Семафоры Дейкстры

S: semaphore

P(s) - close

V(s) - open

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

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

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

Неделимость операций

Примитивы — это неделимые операции. При попытке выполнить примитив над семафором из разных процессов приведет к успеху только одного действия, выполняемого потоком, причем неизвестно каким.

 

Механизмы синхронизации. Решение задачи реактивации

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

Возможны 2 варианта:

- процесс должен повторно выполнить операцию закрытия (считая попытку неуспешной)

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

Возможны ситуации тупика.

1)Пусть процесс 2 успешно выполнил операцию закрытия, значение семафора = 0, далее процесс 1 пытается выполнить операцию закрытия (не удается), т.е., 1 процесс останавливается на семафоре. Знач. семафора = -1. При выходе из крит. обл, процесс 2 открывает семафор, знач семафора = 0. Процесс 1 переходит в очередь готовности. Если он повторно выполнит операцию закрытия, значение семафора = -1, а 1-ый процесс остановится. Соответсвтенно, попытка 2-ого процесса войти в крит. область также будет заблокирована.

2) Пусть процесс 2 открывает семафор, т.е. значение семафора =0. Если 2 процесс повторно пытается закрыть семафор, он остановится, а значение семафора станет равным -1. 1-ый процесс при переходе в активное состояние входит в крит. обл. и при выходе устанавливает значение семафора = 0. "Освобожденный" 2-ой процесс также повтороно попадает в крит. обл., открывает семафор, значение семафора =1.

 

Механизмы синхронизации. Модификации семафоров

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

Счётные — в этой модификации при каждом исполнении примитива допускается изменение счетчика семафора на значение больше еденицы. Начальное значение устанавливается равным количеству читателей. Каждый читатель закрывает семафор на 1, а писатель — на максимальное открывает.

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

Тест-семафоры — для этой модификации вводится усложненная логика примитива V. В качестве параметров кроме семафора указывается величина R, на которую нужно изменить значение и величина Q, с которой сравнивается новое значение счетчика семафора. Если в результате разность > 0 — продолжается работа процесса, иначе — останавливается.