русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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

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

Когда в машине имеется лишь один процессор, параллельные процессы не мо­гут перекрываться, а способны только чередоваться. Кроме того, процесс будет продолжаться до тех пор, пока не будет вызван сервис операционной системы или пока процесс не будет прерван. Следовательно, для того чтобы гарантировать взаим­ное исключение, достаточно защитить процесс от прерывания. Эта возможность мо­жет быть обеспечена в форме примитивов, определенных системным ядром для за­прета и разрешения прерываний. Процесс в таком случае может обеспечить взаимо­исключе­ние следующим образом (сравните с листингом 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 имеет бо­лее низкий приоритет, он не получит возможности продолжить работу, так как в наличии имеется активный процесс с высоким приоритетом.

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

 

Просмотров:

Вернуться в оглавление:Операционные системы




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.