Мультипроцессорные системы. Семафорная техника синхронизации и упорядочивания процессов. Стек – средство обработки структурированных программ, страница 2

Параметры семафора:

1)  начальное значение семафора;

2)  диапазон значений;

3)  логика действий над семафорами (задаётся процедурами обработки);

4)  количество семафоров, доступных для обработки отдельных примитивов.

Алгоритм  P(S)

S:=S-1;

IfS<0 then  <остановить процесс и поместить его в очередь ожидания к семафору S>

Else<продолжить процесс>

Алгоритм V(S)

IfS<0 then <поместить один из ожидающих процессов из очереди к семафору S в очередь готовности>;

S:=S+1;

Пример: Задача взаимного исключения двух процессов.

Begin

S:=1;

Cobegin

1:P(S); KO; V(S)

2: P(S); KO; V(S)

coend

end

KO - критическая область.

В языках высокого уровня семафорные переменные имеют тип «semaphore».

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

Множественные семафоры используется для решения задачи распределения конкурирующих ресурсов. Существуют счётные семафоры,   и есть тест – семафоры.

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

Мониторные средства распределения ресурсов.

Монитор – это высокоуровневое языковое средство согласования процессов при разделяемых ресурсах.

Структура монитора:

     1 – это описание локальных параметров монитора

     2 – процедуры распределения ресурсов.

     3 – инициализация локальных данных монитора.

1

2

3

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

Механизм стековой памяти.

Средства организации вычислительного процесса.

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

Стековая архитектура наиболее ярко выражена на следующих машинах:

n  МВК «Эльбрус»

n  «Мир 1», «Мир 2»

n  «СН 3», «СН 4»

Модель стека. Стек выражений.

Стек состоит из:

a)  Тело стека – это совокупность смежных элементов хранения, регистров, ячеек оперативной памяти;

b)  Длина стека – это количество элементов, которое в текущее время содержит информацию (величина переменная). При операциях с вершиной стека она увеличивается (уменьшается) на единицу. Стек работает по принципу LIFO (LASTINFIRSTOUT).

Указатель стека – это ячейка оперативной памяти или регистр ЦП, который содержит адрес вершины стека. При ограниченной длине стека указателя «на» может не быть.

                                                                 Указатель вершины

       Длина стека

                                                                        Указатель на стек

Стек пуст, когда указатель «на» показывает на вершину.

Реализация стека на основе ОП требует использования специальных регистров ЦП (S,B).

Стеки используются для вычисления арифметически-логических выражений, а также для трансляции выражений ПОЛИЗ (польская инверсная запись).

Любое выражение можно представить деревом, обход которого в определённом направлении даёт ПОЛИЗ (метод Дейкстра).

 

Пример:

(А+В)/(С+(D+E))

AB+CDE*+/  обратная

польская запись является

беспобочной                                  A             B             C

D               E

Для перевода арифметических и логических выражений в ПОЛИЗ используется стек с приоритетами. Приоритеты назначаются для ограничителей и операций в соответствии со старшинством этих операций.

Таблица приоритетов:

Ограничитель	приоритет
(   [   if	0
=  )  ]  then  else	1
	2
	3
	4
…	…
+	7
* / -	8
^	9

                   …                        операнд                   …

            выходная строка                         входная строка

                                                                  знак операции   

             вершина стека

                                                       …

                                                                  стек операций

Алгоритм метода Дейкстра.

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

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

      Обработка скобок.

Круглая скобка (приоритет нуль) записывается в вершину стека и не выталкивает ни одного знака. Её не может вытолкнуть ни один знак, кроме закрывающейся скобки « ) », поэтому появление

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

ПОЛИЗ можно перевести в машинные команды.

Для трансляции используется массив СО [ i ] – стек операндов, i – указатель стека, j=1 – номер первой рабочей переменной.

R – знак операции.