взаимное исключение
Запрет одновременного доступа к разделяемым ресурсам более чем одному процессу называется взаимным исключением.
критическая область
критическая секция
Критической областью называется часть программы, в которой содержится обращение к разделяемому ресурсу.
семафор
Семафор (semaphore) – это специальный тип переменных, которые могут принимать только неотрицательные значения, и над которыми определены только три следующие операции: операция инициализации семафора; операция "закрытия" семафора; операция "открытия" семафора.
двоичный семафор
мьютекс
Простейшим семафором является двоичный семафор, который может принимать лишь два состояния – 0 и 1. Иногда двоичный семафор называют мьютексом (mutex – сокращение от mutual exclusion).
спин-блокировка
Процесс, который достиг критической секции, занятой другим процессом, переходит в состояние спин-блокировки. В это время он непрерывно и с максимальной скоростью опрашивает состояние семафора.
алгоритм двоичного экспоненциального отката
Спин-блокировка приводит, во-первых, к напрасной трате времени соответствующего процессора, а, во-вторых, накладывает значительную нагрузку на коммуникационную сеть и память, снижая тем самым скорость работы остальных процессоров. Одним из способов решения этой проблемы является использование алгоритма двоичного экспоненциального отката. Суть алгоритма состоит в следующем: между опросами семафора вставляется цикл задержки; вначале задержка равна времени выполнения одной команды; если семафор занят, задержка удваивается, учетверяется и т.д. до некоторого максимального уровня.