Программное обеспечение вычислительной системы

 

Все вычислительные системы  имеют такое средство для организации  взаимного исключения, как блокировка памяти. Это средство запрещает одновременное использование двух (и более) команд, которые обращаются к одной и той же ячейке памяти. Механизм блокировки памяти предотвращает одновременный доступ к разделяемой переменной, но не предотвращает чередование доступа. Таким образом, если критические интервалы исчерпываются  одной командой обращения к памяти, данного средства может быть достаточно для непосредственной реализации взаимного исключения. Если критические секции требую более одного обращения к памяти, задача становится сложной, но алгоритмически разрешимой.

Рассмотрим  следующую  модель двух взаимодействующих процессов.

            

        

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. Модель взаимодействующих  процессов

 

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

• некоторого критического интервала;
• оставшаяся часть кода, в которой нет работы с общими переменными.

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

Рассмотрим вариант  решения взаимного исключения, использующий только блокировку памяти. Это известный  алгоритм, предложенный математиком  Деккером. Алгоритм Деккера основан на использовании 3-х переменных: перекл1, перекл2 и ОЧЕРЕДЬ. С каждым из процессов CS₁ и CS₂ будут связаны  соответственно переменные перекл1 и перекл2, по смыслу являющиеся переключателями, которые принимают значение true, когда соответствующий процесс находится в своем критическом интервале, и false – в противном случае. Переменная целого типа ОЧЕРЕДЬ  указывает, чье сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интервалы.

Если перекл2= true и перекл1= false, то выполняется критический интервал для процесса CS₂ независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл1= true и перекл2= false. Если же оба процесса хотят выполнить свои критические интервалы, т.е. перекл2= true и перекл1= true, то выполняется критический интервал того процесса, на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития процесса.

 

2. Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»

 

Операция «ПРОВЕРКА  И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств  решения задачи критического интервала. Данная операция реализована во многих компьютерах. Так в IBM 360 эта команда называлась TS (test and set). Действие этой двухоперандной команды   заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Эта команда является неделимой, то есть между ее началом и концом не могут выполняться никакие другие команды.

Чтобы использовать команду TS для решения проблемы критического интервала, свяжем с ней переменную CS₁, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале.  С каждым процессом связана своя локальная переменная local, которая принимает значение, равное единице, если данный процесс хочет войти в свой критический интервал. Операция TS будет присваивать значение common переменной local и устанавливать common в единицу.

 Пусть значение common равно нулю. Предположим, что первым захочет войти в свой критический интервал процесс CS₁. В этом случае значение local1 установится в единицу, а после цикла проверки с помощью команды         TS(local1, common)  – в ноль. При этом значение common станет равным единице. Процесс CS₁ войдет в свой критический интервал. После выполнения этого критического интервала common примет значение равное нулю, что даст возможность второму процессу  CS₂ войти в свой критический интервал.

В микропроцессорах i80386 и старше есть специальные команды BTC, BTS (bit test and reset – проверка бита и установка), BTR, которые как раз и являются вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА».

 

Несмотря на то, что  и алгоритм Деккера и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой процесс, который пытается войти в свою критическую секцию, попадает в цикл проверки соответствующих переменных-флагов, регламентирующих доступ к критическим переменным (находится в активном ожидании). В результате имеем общее замедление вычислительной системы процессами, которые реально не выполняют никакой полезной работы.

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

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

Таким образом, мы подошли  к одному из главных механизмов решения  проблемы взаимного исключения –  семафорам Дейкстры.

 

3. Семафорные примитивы Дейкстры

 

Семафор – переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытии» и «открытия», названных соответственно P- и V-операциями.  Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операции. Здесь семафор выполняет роль вспомогательного критического ресурса, так как операции P и V неделимы при своем выполнении и взаимно исключают друг друга.

Основным достоинством семафорных операций является отсутствие состояния «активного ожидания», что повышает эффективность работы мультипрограммной вычислительной системы.

В настоящее время  используют много различных семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются:

• начальное значение и диапазон изменения значений семафора;
• логика действий семафорных операций;
• количество семафоров, доступных для обработки при исполнении отдельного примитива.

Обобщенный смысл примитива P(S) состоит в проверке текущего значения семафора S (P – от голландского Proberen – проверить), и если оно не меньше нуля, то осуществляется переход к следующей за примитивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние «пассивного ожидания». Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания.

Операция V(S) связана с увеличением значения семафора на единицу (V – от голландского Verhogen – увеличить) и переводом одного или нескольких процессов в состояние готовности к центральному процессору.

Операции P и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра.

Допустимыми значениями семафора являются только целые числа. Двоичным семафором называют семафор, максимальное значение которого равно единице. В противном случае семафоры называют N-ичными.

 

Рассмотрим на нашем  примере двух конкурирующих процессов использование данных семафорных примитивов для решения проблемы критического интервала:

1. семафор имеет начальное значение, равное 1. Если процессы CS₁ и CS₂ попытаются одновременно выполнить примитив P(S), то это удастся сделать только одному из них. Пусть это будет CS₂:
2. процесс  CS₂ закрывает семафор S (выполняет операцию P(S)) и выполняет свой критический интервал. Процесс CS₁ будет заблокирован на семафоре S. Тем самым гарантируется взаимное исключение;
3. после выполнения примитива V(S) процессом CS₂ семафор S открывается, указывая на возможность захвата каким-либо процессом освободившегося критического ресурса. При этом производится перевод процесса  CS₁ из заблокированного состояния в состояние готовности.

 

 

4. Мониторы Хоара

 

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

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

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

Монитор – это механизм организации параллелизма, который  содержит как данные, так и процедуры, необходимые для реализации динамического  распределения общего ресурса. Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору, который либо предоставит доступ, либо откажет в нем. Вход в монитор находится под жестким контролем – здесь осуществляется взаимоисключение процессов, так что в каждый момент времени только одному процессу можно войти в монитор. Процессам, которым надо войти в монитор, когда он уже занят, приходится ждать, причем режимом ожидания автоматически управляет сам монитор. При отказе в доступе монитор блокирует обратившийся к нему процесс и определяет условие, по которому процесс ждет. Внутренние данные монитора могут быть либо глобальными (относящимися ко всем процедурам монитора), либо локальными (относящимися только к одной конкретной процедуре). Ко всем этим данным можно обращаться только изнутри монитора. При первом обращении монитор присваивает своим переменным начальные значения. При каждом новом обращении используются те значения переменных, которые сохранились от предыдущего обращения.

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

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

 

5. Почтовые ящики

 

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

Основные достоинства  почтовых ящиков:

• процессу не нужно знать о существовании других процессов до тех пор, пока он не получит сообщения от них;
• два процесса могут обмениваться более чем одним сообщением за один раз;
• операционная система может гарантировать, что никакой процесс не вмешается в «беседу» других процессов:
• очереди буферов позволяют процессу-отправителю продолжать работу, обращая внимания на получателя.

 

Основным недостатком  буферизации сообщений является появление еще одного ресурса, которым  нужно управлять.

 

6. Конвейеры (программные каналы)

 

Конвейер (pipe –программный канал, транспортер) является средством, с помощью которого можно производить обмен данными между процессами. Принцип работы конвейера основан на механизме ввода/вывода, который используется с файлами в UNIX – задача, передающая информацию, действует так, как будто она записывает данные в файл, в то время как задача, для которой предназначается эта информация, читает ее из этого файла. Операции записи и чтения осуществляются не записями, как это делается в обычных файлах, а потоком байтов, как это делается в UNIX-системах. Функции, с помощью которых выполняется запись в канал и чтение из него, являются теми же самыми, что и при работе с файлами. На самом деле конвейеры являются не файлами на диске, а представляют собой буферную память, работающую по принципу обычной очереди (FIFO – first input, first output)