Взаимоисключения: аппаратная поддержка

Отключение прерываний

Когда в машине имеется лишь один процессор, параллельные процессы не мо­гут перекрываться, а способны только чередоваться. Кроме того, процесс будет продолжаться до тех пор, пока не будет вызван сервис операционной системы или пока процесс не будет прерван. Следовательно, для того чтобы гарантировать взаим­ное исключение, достаточно защитить процесс от прерывания. Эта возможность мо­жет быть обеспечена в форме примитивов, определенных системным ядром для за­прета и разрешения прерываний. Процесс в таком случае может обеспечить взаимо­исключе­ние следующим образом (сравните с листингом 5.1):

while   (true)
{
/*   Запрет прерываний */;
/*   Критический раздел */;
/*   Разрешение прерываний */;
/*  Остальной код  */;
}

Поскольку критический раздел не может быть прерван, выполнение взаи­мо­исключения гарантируется. Однако цена такого подхода высока. Эффектив­ность работы может заметно снизиться, поскольку при этом ограничена возмож­ность процессора по чередованию программ. Другая проблема заключается в том, что такой подход не будет работать в многопроцессорной архитектуре. Если вычисли­тельная система включает несколько процессоров, то вполне возможно (и обычно так и бывает), что одновременно выполняются несколько процессов. В этом случае запрет прерываний не гарантирует выполнения взаимоисключений.

Специальные машинные команды

В многопроцессорной конфигурации несколько процессоров разделяют доступ к общей основной памяти. В этом случае отсутствует отношение ведущий/ведомый (master/slave) процессоры работают независимо, "на равных", и не имеется меха­низма прерывания, на котором могли бы основываться взаимоисключения.

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

В этом разделе мы рассмотрим две из наиболее часто реализуемых инструкций (с остальными инструкциями вы можете познакомиться в [RAYN86] и [STON93]).

Инструкция проверки и установки значения

Инструкцию проверки и установки значения можно определить следую­щим образом:

boolean test­set(int i)
{
if (i == 0)
{
i = 1;
return true;
}
else
{
return false;
}
)

Инструкция проверяет значение своего аргумента i. Если его значение рав­но 0, функция заменяет его на 1 и возвращает true. В противном случае значе­ние переменной не изменяется и воз­вращается значение false. Функция testset выполняется ато­марно, т.е. ее выполнение не может быть прервано.
Листинг 5.4. Аппаратная поддержка взаимных исключений

/* а)  Инструкция проверки я установки */
const int n  =   /* Количество процессов */;
int bolt;
void P(int i)
{
while(true)
{
while(!testset (bolt))
/* Ничего не делать */;
/* Критический раздел */;
bolt  =  0;
/* Остальная часть кода */
}
}
void main ()
{
bolt = 0;
parbegin(P(l),P(2),...,P(n));
}

/* б)  Инструкция обмена */
const int n = /* Количество процессов */;
int bolt; void P (int  i)
{
I   int keyi;
while(true)
{
keyi = I;
while(keyi !=0)
exchange(keyi, bolt);
/* Критический раздел */;
exchange(keyi, bolt);
/* Остальная часть кода */
}
}
void main ()
{
bolt = 0;
parbegin(P(l),P(2),...,P(n));
}

В листинге 5.4,а показан протокол взаимных исключений, основанный на ис­пользовании описанной инструкции. Разделяемая переменная bolt инициализирует­ся нулевым значением. Только процесс, который может войти в критический раздел, находит, что значение переменной bolt — 0. Все остальные про­цессы при попытке входа в критический раздел переходят в режим ожидания. Выйдя из критического раздела, процесс переустанавливает значение переменной bolt равным 0, после чего один и только один процесс из множества ожидающих входа в критический раздел полу­чает требуемый ему доступ. Выбор этого процесса зависит от того, ка­кому из процессов удалось выполнить инструкцию testset первым.

Инструкция обмена

Инструкция обмена может быть определена следующим образом:

void exchange(int register, int memory)
{
int temp;
temp = memory;
memory = register;
register = temp;
}

Инструкция обменивает содержимое регистра и ячейки памяти. В процессе ее выполнения доступ к ячейке памяти для всех остальных процессов блокируется.

В листинге 5.4,6 показан протокол взаимного исключения, основанный на использовании этой инструкции. Разделяемая переменная bolt инициализиру­ется нулевым значением. У каждого процесса имеется локальная переменная key, инициализированная значением 1. В критический раздел может войти только один процесс, который обнаруживает, что значение bolt равно 0. Этот процесс запрещает вход в критический раздел всем другим процессам путем ус­тановки значения bolt, равным 1. По окончании работы в критическом разделе процесс вновь сбрасывает значение bolt в 0, тем самым позволяя другому про­цессу войти в критический раздел.

Заметим, что при использовании рассмотренного алгоритма всегда выпол­ня­ется следующее соотношение:

Если bolt = 0, то в критическом разделе нет ни одного процесса. Если bolt = 1, то в критическом разделе находится ровно один процесс, а именно тот, переменная key которого имеет нулевое значение.

Свойства подхода, основанного на использовании машин­ных инструкций

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

Он применим к любому количеству процессов при наличии как одного, таки нескольких процессоров, разделяющих основную память.

Этот подход очень прост, а потому легко проверяем.

Он может использоваться для поддержки множества критических разде­лов; каждый из них может быть определен при помощи своей собствен­ной переменной.

Однако у такого подхода имеются и серьезные недостатки. Используется пережидание занятости. Следовательно, в то время как про­цессаходится в ожидании доступа к критическому разделу, он продолжает потреблять процессорное время.

Возможно голодание. Если процесс покидает критический раздел, а входа в него ожидают несколько других процессов, то выбор ожидающего процесса произволен. Следовательно, может оказаться, что какой-то из процессов бу­дет ожидать входа в критический раздел бесконечно.

Возможна взаимоблокировка. Рассмотрим следующий сценарий в однопро­цессорной системе. Процесс Р1 выполняет специальную инструкцию (т.е. testset или exchange) и входит в критический раздел. После этого про­цесс Р1 прерывается процессом Р2 с более высоким приоритетом. Если Р2 попытается обратиться к тому же ресурсу, что и Р1, ему будет отказано в доступе в соответствии с механизмом взаимоисключений,  и он войдет в цикл пережидания занятости. Однако в силу того что процесс Р1 имеет бо­лее низкий приоритет, он не получит возможности продолжить работу, так как в наличии имеется активный процесс с высоким приоритетом.

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