Если в системе имеется только один процессор, то параллельные процессы не могут перекрываться, а способны только чередоваться. Кроме того, процесс будет продолжаться до тех пор, пока не будет вызванный сервис операционной системы или пока процесс не будет прерван. Поэтому, для того чтобы гарантировать взаимное исключение, достаточно защитить процесс от прерывания. Эта возможность может быть обеспечена в форме примитивов, определенных системным ядром для запрета и разрешения прерываний. Процесс в таком случае может быть обеспечить взаимоисключение следующим образом:
While (true)
{
/* Запрет прерываний */
/* Критический раздел */
/* Разрешение прерываний */
/* Остальной код */
}
Поскольку критический раздел не может быть прерван (невозможно прерывание даже по таймеру), выполнение взаимоисключения гарантируется. Однако цена такого подхода высока. Эффективность работы может заметно снизиться, поскольку при этом ограничена возможность процессора по чередованию программ. Было бы также неразумно давать пользовательскому процессу возможность разрешения и запрета прерываний во всей вычислительной системе. Представьте себе, что будет, если процесс запретил все прерывания и в результате какого-либо сбоя не включил их обратно. ОС на этом может закончить свое существование.
Другая проблема, что такой подход не будет работать в многопроцессорной архитектуре, так как одновременно может работать несколько процессов. В этом случае запрет прерываний не гарантирует выполнения взаимоисключений.
В многопроцессорных системах несколько процессоров разделяют доступ к общей основной памяти. В этом случае отсутствует отношение ведущий/ведомый (master/slave) – процессоры работают независимо, “на равных”, и не имеется механизма прерывания, на котором могли бы основываться взаимоисключения.
На уровне аппаратного обеспечения, как уже упоминалось, обращение к ячейке памяти исключает любые другие обращения к этой же ячейке. Основываясь на этом принципе, разработчики процессоров предлагают ряд машинных команд, которые за один цикл выборки команды атомарно выполняют над ячейкой памяти два действия, такие как чтение и запись, или чтение и проверка значения. Поскольку эти действия выполняются в одном цикле, на них не в состоянии повлиять никакие другие инструкции.
Рассмотрим две из наиболее часто реализуемых инструкций.
7.3.1. Инструкция проверки и установки значения
Инструкцию проверки и установки значения можно определить как:
Boolean TestSet(int I)
{
If I == 0)
{ I = 1;
Return true;
}
else return false;
}
Инструкция (команда) Test-and-Set (проверить и присвоить 1) проверяет значение своего аргумента I. Если он равен 0, функция заменяет его на 1 и возвращает true. В противном случае значение переменной не меняется и возвращается false. Функция TestSet выполняется атомарно, т.е. ее выполнение не может быть прервано.
Листинг 7.3. Аппаратная проверка взаимных исключений. Инструкция проверки и установки
const int n = /* Количество процессов */;
int bolt;
void P(int I)
{
while(true)
{
while(!testset(bolt)); /* ждать */
/* Критический раздел */
bolt = 0;
/* остальная часть кода */
}
}
void main()
{
bolt = 0;
parbegin(P(1),P(2),…,P(n));
}
В листинге 7.3 показан протокол взаимных исключений, основанный на использовании описанной инструкции. Разделяемая переменная bolt инициализируется нулевым значением. Только процесс, который может войти в критический раздел, находит, что значение переменной bolt равно 0. Все остальные процессы при попытке входа в критический раздел переходят в режим ожидания. Выйдя из критического раздела, процесс переустанавливает значение bolt, равным 0, после чего опять только один процесс из множества ожидающих входа в критический раздел получит требуемый ему доступ. Выбор этого процесса зависит от того, какому из процессов удалось выполнить инструкцию testset первым.
