Есть такие ресурсы, которые могут использоваться только одним процессом. Например, принтер: если принтером воспользуются 2 процесса, то на выходе получится белиберда
Будем называть критической секцией код процесса, в котором он использует неразделяемый ресурс. Перед критической секцией находится пролог - код, предупреждающий, что процесс хочет использовать. После критической секцией находится эпилог - код, говорящий, что ресурс свободен
Задача синхронизации процессов - обеспечение целостности системы во времени. Для этого надо соблюсти 4 условия:
Взаимоисключение - нельзя, что бы неразделяемым ресурсом пользовались несколько процессов. Более формально: в критической секции одного и того же ресурса не должно находиться более 1 процесса
Прогресс - должна быть невозможна ситуация, когда ресурс свободен, есть хотя бы один процесс, готовый его использовать, но особенности алгоритма синхронизации не позволяют его использовать
Отсутствие голодания - должна быть невозможна ситуация, когда процесс неограничено долго ждет ресурс, предоставляемый в это время другим процессом
Отсутствие тупиков (о тупиках позже)
Тривиальным решением этих проблем является переход к однопрограммному управлению. Поэтому в прологе можно отправить системный вызов, говорящий процессору игнорировать любые прерывания - таким образом, процесс может свободно использовать ресурс. Однако в этом случае мы лишаемся обработки ошибок
Однопрограммное управление используется ядром для диспетчеризации процессов, чтобы поддерживать целостность данных во время переходов
Далее разберем механизмы синхронизации для двух процессов
Замок (или глобальная блокирующая переменная)
// замок
shared int lock = 0;
// код процесса
p_i() {
...
// пролог
while (lock);
lock = 1;
{ criticalSection }
// эпилог
lock = 0;
...
}
В прологе процесс находится в цикле, пока замок равен 1 (то есть ресурс занят). Когда замок освобождается, процесс его закрывает, исполняет критическую секцию и высвобождает замок
Однако, пролог является не атомарной операцией: если между while (lock); и lock = 1; произойдет переключение процесса, то потеряется целостность
Строгое чередование
Здесь вместо того, чтобы хранить, занят ли ресурс или нет, мы хранит номер процесса, который его занял
shared int turn = 0;
p_i() {
...
while (turn != i);
{ criticalSection }
turn = 1 - i;
...
}
Явный недостаток: порядок процессов трудно изменить. Также, если процессу 2 надо войти в критическую секцию, а процессу 1 не надо, но при этом сейчас его очередь, то процесс 2 будет ждать, из-за чего нарушится прогресс
Флаги готовности
Здесь мы храним флаги для процесса, обозначающие готовность воспользоваться ресурсом
shared int ready[2] = {0, 0};
p_i() {
...
ready[i] = 1;
while (ready[i - 1]);
{ criticalSection }
ready[i] = 0;
...
}
Здесь, если переключение процессов возникнет перед while (ready[i - 1]);, то может случиться так, что оба процесса отметили ready[i], значит, выхода из цикла нет - процессы вошли в тупик
Алгоритм вежливости (или алгоритм Петерсона)
Здесь процесс спрашивает другие процессы, готовы ли они принять ресурсы. Если все из них готовы принять, то первый “спросивший” процесс пользуется ресурс
shared int ready[2] = {0, 0};
shared int turn;
p_i() {
...
ready[i] = 1;
turn = 1 - i;
while (ready[1 - i] && turn != i);
{ criticalSection }
ready[i] = 0;
}
Его проблема в том, что он не предсказуем: в эту кольцевую очередь могут добавиться еще процессы, тогда время опроса увеличится
Алгоритм был создан по аналогии с этикетом входа 2 людей в одну дверь: сначала 1-ый должен пропустить 2-ого, а 2-ой 1-ого, после этого дальше уступать не имеет смысла, поэтому должен пройти 1-ый
Аппаратная поддержка взаимоисключения (или Spinlock)
shared int lock = 0;
p_i() {
...
while (test_and_set(&lock));
{ criticalSection }
lock = 0;
...
}
Здесь, чтобы исключить проблему с переключением процессов, вводится функция test_and_set, которая атомарно проверяет значение переменной, и устанавливает ее значение равным 1, если оно равно 0
Семафоры
Назовем семафором целую неотрицательную переменную, над которой разрешим две атомарные операции:
// Дождаться, когда она будет положительной, тогда уменьшить ее на 1
p(S): while S == 0: wait
S = S - 1
// Увеличить ее на 1
v(S): S = S + 1
Тогда, если у нас есть продюсер, производитель данных, и консьюмер, потребляющих их через какой-то буфер, то их параллельное взаимодействие можно описать так:
Semaphore mutex = 1;
// На сколько байтов буфер пустой
Semaphore empty = N;
// На сколько байтов заполнен буфер
Semaphore full = 0;
Producer() {
while (true) {
produceData();
p(empty);
p(mutex);
putData();
v(mutux);
v(full);
}
}
Consumer() {
while (true) {
p(full);
p(mutex);
getData();
v(mutex);
v(empty);
consumeData();
}
}
Основную сложность представляет то, как узнать, заполнен ли буфер чем-либо или нет. Для этого есть семафоры empty и full
Здесь мьютексом обозначается двоичный семафор, и используется он, чтобы гарантировать, что буфер читает/пишет один процесс. Сейчас слово мьютекс используют в смысле двоичного семафора, у которого есть опеределенный владелец, который может его высвобождать