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

1)  Взять очередной символ S из ПОЛИЗ;

2)  Если символ S – операнд, то

CO[i]:=операнд;

I:=i+1;GOTO 1

3) Если символ S – не знак операции, то

GOTO 4,

Иначе если символ S знак операции R, то

3.1.  Среди элементов стека СО [ i-k ]…CO [ i-1], где к – количество операндов R, найти рабочую переменную с минимальным номером l. Если в рассматриваемых элементах стека нет рабочих переменных, то положить l=j.

3.2.  Записать машинные команды, реализующие оператор присваивания: R_i:=R( CO[i-k],…,CO[i-1] ).Эта операция сводится фактически к постановке макроопределения данной операции.

3.3.  Записать символ R_i  в CO[i-k].

3.4.  I присвоить i-k+1; j присвоить l+1;GOTO 1.

Алгоритм заканчивает работу, когда заканчивается входная строка.

Стек – средство обработки структурированных программ.

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

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

Пример:

  A. begin

       Integer a, b;

       S₁;S₂;…;S_n;                                      A   уровень n

   B. begin

          Integer c, d;                           B              E   уровень n+1

         R₁;R₂;…;R_n;

     C. begin

            Integer e, f;                 C   уровень n+2                       

            Q₁;Q₂;…;Q_n;

     End;R_n+1

 End; S_n+1;S_n+2;…;S_h

    E. begin

           Integer g, h

           P;

    End

End

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

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

Адресным контекстом процедуры называется область известности имён и других структурных блоков, которые могут быть доступны для обработки командам из тела процедуры. Сюда же входят и параметры, передаваемые процедурой (адресный контекст для С – переменные e и f, а также c, d, a, b).

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

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

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

Стек данных и стек динамических связей.

Наличие определённого числа запущенных, но ещё не законченных процедур, связанных правилом LIFO, предполагает, что начальные данные процедур и их параметры должны храниться в стеке данных, а для управления стеком данных используются регистры ЦП.

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

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

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

Пример.

       Program MAIN;                             стек данных

Procedure A( );

   Integer a, b;                                                                                            S’

    Procedure B( );

       Integer c;                                                                                           D_n

      Begin                                                                                     …

          …                                                                                                    D₅

       C( );