Семафоры
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.
Мьютекс – либо открыт, либо закрыт.
Характеристика всех средств синхронизации:
они ДИСКРЕТНЫ, не являются соединёнными с объектом синхронизации.
Средства синхронизации |
Объект синхронизации |
Иногда бывают проблемы, что программисты забывают освободить объекты синхронизации и т.д. (неправильная работа с семафорами, не захватил мьютекс и т.д.) Поэтому предложили ввести промежуточный слой – сервер, который будет принудительно закрывать программы при сбоях.
Объект синхронизации – это данные, каналы.
Объект синхронизации |
Сервер