Александр Кручинин: Операционные системы

Здесь рассмотрены различные способы реализации взаимного исключения с целью избежать вмешательства в критическую область одного процесса при нахождении там другого и связанных с этим проблем.

1 Запрещение прерывания

Самое простое решение состоит в запрещении всех прерываний при входе процессоров в критическую область и разрешение прерываний по выходе из области. Но это решение неразумно. Предположим все прерывания отключились, а возник какой-то сбой – в результате операционная система закончит своё существование. А если система многопроцессорная, то тогда второй процессор все равно может зайти в критическую область.

2 Переменные блокировки

Программное решение проблемы может носит следующий вид. Пусть переменная блокировки равна 0, процесс, когда хочет попасть в критическую область изменяет её на 1 и входит в критическую область. Тут также может возникнуть состояние состязания, когда два процесса одновременно считывают переменную блокировки, когда она равна 0 и оба входят в критическую область.

3 Строгое чередование

Третий метод проиллюстрирован на листинге 1.

Листинг 1 – Решение проблемы критической области методом строгого чередования

Целая переменная turn , изначально равная 0, отслеживает, чья очередь входить в критическую область. Здесь для того, чтобы 0-ой процесс вошел в область, turn должна быть равна 0, а 1-ой – turn равна 1.

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

Однако здесь есть недостаток: если один процесс существенно медленнее другого, то может возникнуть ситуация, когда оба процесса находятся вне критической области, однако один процесс блокирован, ожидая пока другой войдёт в критическую область. Это нарушает 3 условие из сформулированных ранее.

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

В 1981 году датский математик Петерсон разработал простой алгоритм взаимного исключения, представленный на листинге 2 [17].

Листинг 2 – Решение Петерсона для взаимного исключения

Перед тем, как войти в критическую область процесс вызывает процедуру enter_regio n со своим номером в качестве параметра. После выхода из критической области процесс вызывает 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