проиллюстрирован на листинге 1.
Листинг 1 – Решение проблемы критической области методом строгого чередования
Целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область. Здесь для того, чтобы 0-ой процесс вошел в область, turn должна быть равна 0, а 1-ой – turn равна 1.
Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием, которое используется только при уверенности в небольшом времени ожидания.
Однако здесь есть недостаток: если один процесс существенно медленнее другого, то может возникнуть ситуация, когда оба процесса находятся вне критической области, однако один процесс блокирован, ожидая пока другой войдёт в критическую область. Это нарушает 3 условие из сформулированных ранее.
4 Алгоритм Петерсона
В 1981 году датский математик Петерсон разработал простой алгоритм взаимного исключения, представленный на листинге 2 [17].
Листинг 2 – Решение Петерсона для взаимного исключения
Перед тем, как войти в критическую область процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает leav_region.
Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.
Если оба процесса вызвали enter_region практически одновременно, то оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до оператора while, процесс 0 войдет в критическую область, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области.
5 Команда TSL
Это решение требует участия аппаратного обеспечения. Многие компьютеры имеют команду: TSL RX, LOCK.
(Test and Set Lock – проверить и заблокировать), которая действует следующим образом. В регистр RX считывается содержимое слова памяти LOCK, а в ячейке памяти LOCK сохраняется некоторое ненулевое значение. Операция считывания слова неделима. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры, если они есть, не могли обратиться к памяти.
На листинге 3 представлены функции для входа и выхода из критической области, выполненные в синтаксисе Ассемблера.
Листинг 3 – Вход и выход из критической области с помощью команды TSL
Прежде чем попасть в критическую
