Загрузка...

Алгоритм Деккера


Аппаратная реализация взаимоисключения: команда “проверка и установка” (testandset)
Алгоритм Деккера представляет собой программное решение проблемы взаимоисключения. Рассмотрим вариант аппаратного решения данной проблемы. Наличие аппаратной команды TS (testandset), которая осуществляет чтение переменной; запись ее значения в область сохранения и установку конкретного значения этой переменной, причем выполняет эти действия до конца без прерывания, значительно упрощает решение проблемы критического участка посредством блокировки памяти.
Чтобы использовать команду TS для решения проблемы критического интервала, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. Операция TS будет присваивать значение common локальной переменной и устанавливать common в единицу.
Основной недостаток использования операций типа TS состоит в следующем: находясь в цикле проверки переменной common, процессы впустую потребляют время ЦП и другие ресурсы. Например, если предположить, что произошло прерывание процесса1 во время выполнения своего критического интервала в соответствии с некоторой дисциплиной обслуживания и начал выполняться процесс2, то он войдет в цикл проверки, впустую тратя процессорное время. В этом случае до тех пор, пока диспетчер супервизора не поставит на выполнение процесс1 и не даст ему закончиться, процесс2 не сможет войти в свой критический интервал.

Загрузка...