Семафоры

API для работы с синхронизацией

Запрет прерываний

Алгоритм Петерсона

Если конкурентов 3, то генерируем алгоритм для трёх конкурентов. Если 4, то для четырёх

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

Мы можем запретить прерывания, все проблемы уходят (мы потеряем во времени максимум 18 машинных команд). Но разрешать их программисту чревато.

Можно выполнить атомарно эти 6 машинных команд одной машинной командой, но она есть не на всех процессорах. Поэтому упор на такую машинную команду не делают.

Нет возможности работать с переменными открытого вида: либо Петтерсон, либо прерывания.

Что сделали?

Делегировали обязанности операционной системе. Во всех современных системах синхронизация выполняется на уровне ядра операционной системы. Эти 6 машинных команд становятся системным вызовом (атомарно выполняющимся).


 

1. выделить переменную в ядре – semget

2. = (несинхронизационные действия) – semctl

3. while + = (синхронизационные действия) – semop

4. освобождение переменной – semctl

5. узнать состояние о переменной – semctl

Технология получила название Семафоры Дейкстры (берем переменную, помещаем в пространство ядра, окружаем набором API, и даём возможность атомарных действий)

<sys/sem.h>

Семафоры пришли из UNIX System V

semctl – могу выполнять set, или присвоение (запись в семафор нового значения), могу выполнять get.

Эти операции должны выполняться при инициализации.

Тип семафора: short int

Они создаются в памяти ядра неинициализированными (содержат мусор в момент создания)

Над ними можно выполнять блокирующую операцию изменения значения semop. Мы готовим задание (это одно число). Число может быть <0, 0 или > 0.

  <0 (-1) 0(0) >0(+3)
<0 (передаем -2) ожидание ожидание +1(ОК)
0 (перед. 0) ожидание ОК ожидание
>0 (перед. 2) +1(ОК) +2(ОК) (+5)ОК
>0 >=число (-4) ожидание ожидание ожидание

 

Если я даю задание 0, то я ожидаю, что значение семафора должно быть 0. Если текущее значение -1 или 3, то ожидание.

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

Для конкурентной борьбы создаю семафор, равный +1

semop (задание -1)

После выполнения критического участка, сформировать задание +1.

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

12.03.2013

При помощи функции semop() мы можем сформировать пакет заданий

0, +3 – дождаться состояния семафора = 0, затем добавить 3.

-2, +4 – отправляю в семафор (если -5, то отнять нельзя, он заблокирован, если 0 тоже нельзя, если 3, то можно отнять)

Блокирование по первому признаку

  +2 -2, +4
В
-1 В
В
-7 -5 В

 

Блокирование по второму признаку

  +2 +4, -2
-1
-7 -5 В

 

Зачем нужна такая схема?

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

-3, +3 – не блокировать, если больше 3.

Шаги:

1. Инициализировать переменную

2. При помощи функции semop() мы генерируем для ОС задания, она может его либо выполнить, либо нет. Если выполнит, то изменит значение семафора

3. Задание может быть сложным и оно либо выполнится всё, либо не выполнится вообще.


 

В System V семафоры по одному не ходят и есть наборы семафоров. При помощи функции semget(N) мы заказываем набор семафоров, где N – количество аргументов.

Набор семафоров

      N

 

Само задание

   

 

Первое число – номер семафора в наборе, второе число – задание, третье число – специальные флаги. В результате, чтобы выполнить над одним семафором одно задание, мне нужно массив из 3 чисел типа short.

int sem = semget(99, 1, IPC_CREAT | 0666); //внутри одного набора 1 семафор
semctl(sem, 0, SEM_SET, 1); //записать в семафор значение 1 (функция не синхронизируемая) инициализируем семафор: дескриптор открытого набора, номер в наборе, что я хочу сделать и значение
//sem[0] = 1;
short op[3] = {0, -1, 0};//над нулевым семафором совершается 1 действие без флагов
semop(sem, op, 1)//дескриптор открытого семафора, адрес в памяти, где лежат задания, сколько там заданий (1 шт.)

semctl (sem, xxx, IPC_RMID) – освободить набор семафоров

Чтобы дать 2 задания одному и тому же семафору:

short op2[6] = {0, -1, 0, 0, +1, 0};
semop(sem, op2, 2);

Если у нас два семафора в наборе, то semctl() выполняется дважды.

short op3[6] = {0, 0, 0, 1, 0, 0};//дать задания 0 и 1 семафору из набора
semop(sem, op3, 2);


 

Разделяемая переменная – любые операции, любые значения.

Семафоры Дейкстры – ограничили размер счётчика, количество операций.

Посчитали что семафоры Дейкстры слишком сложны для среднего программиста, придумали семафоры POSIX.

Семафоры POSIX – имеет только значения 0 и 1.

Мьютекс – либо открыт, либо закрыт.

Характеристика всех средств синхронизации:
они ДИСКРЕТНЫ, не являются соединёнными с объектом синхронизации.

Средства синхронизации
Объект синхронизации

 


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

Объект синхронизации – это данные, каналы.

Объект синхронизации

 

 


Сервер