Линейная форма стандартной схемы

СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

1. если выходная дуга начальной вершины с оператором start(х₁,..., х_n) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(х₁,..., х_n) goto L;

2.  если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=τ, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: x:= τ goto L1;

3.  если вершина с меткой L - заключительная вершина с оператором stop(τ₁,...τ_m), то ей соответствует инструкция:

L: stop(τ₁,..., τ_m);

4. если вершина с меткой L - распознаватель с условием р(τ₁,...τ_k), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция:

L: if  р(τ₁,...τ_k) then  L1 else L0;

5. если вершина с меткой L - петля, то ей соответствует инструкция:

L: loop.

Интерпретация стандартных схем программ

Интерпретацией базиса В в области интерпретации D называется функция I, которая элементам базиса В элементы из области D. Если S-схема в базисе В, I – интерпритация этого базиса, то пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).

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

Конфигурацией программы (S,I) - пара U = (L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Состояние памяти прог-мы (S,I) наз-ся ф-ия, которая каждой переменной х из памяти схемы S сопоставляет элемент W(x) из области интерпритации D. Протокол выполнения прог-мы (S,I) – последовательность конфигураций (U₀, U₁,..., U_i, U_i+1,...)

Основные свойства стандартных схем:

ССП S в базисе В тотальна, если для любой интерпретации I базиса В программа (S, I) останавливается. ССП S в базисе В пуста, если для любой интерпретации I базиса В программа (S, I) зацикливается. Стандартные схемы S₁, S₂ в базисе В функционально эквивалентны (S₁  S₂), если либо обе зацикливаются, либо обе останавливаются с одинаковым результатом, т. е. val(S₁, I)  val(S₂, I).

Разрешимые подклассы стандартных схем программ.

1. Свободные стандартные схемы

Цепочкой операторов (ЦО) называется последовательность операторов, метящих вершины некоторой цепочки схемы. Напр. (старт, у:=а, р(х), стом(у))

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

2. Схемы Янова

Это схема из подкласса стандартных схем со след базисом:

- одна переменная х;

- множество одноместных функций символов

- мн-во одном. предик. символов.

- оператор присваивания вида: x:=f(x)

- условный оператор вида p(x)

СЯ изучает логическую стру-ру программы. Она называется пустой, если в ней все опер-ры присваивания различны, т.н схема не содержит 2-х вхождений оного и того же функ. символа. Программа свободы для СЯ разрешима. Существует алгоритм преобразования СЯ в эквивалентную свободную схему.

64.Взаимодействие процессов: взаимодействие процессов через разделяемые ресурсы и общие данные, принципы организации взаимодействия процессов, классические задачи взаимодействия асинхронных процессов, динамика взаимодействия процессов и проблема тупиков, спецификация дисциплин взаимодействия процессов в терминах сетей Петри.

Разделяемые ресурсы. Обозначение (m: //S) мы использовали для именованного подчиненного процесса (m: R), единственной обязанностью которого является удовлетворение потребностей главного процесса S. Предположим теперь, что S состоит из двух параллельных процессов (P || Q) и они оба нуждаются в услугах одного и того же подчиненного процесса (m: R). К сожалению, P и Q не могут взаимодействовать с R по одним и тем же каналам, потому что тогда эти каналы должны содержаться в алфавитах обоих процессов, и, значит, согласно определению оператора ||, взаимодействия с (m: R) могут происходить, только когда P и Q одновременно посылают одно и то же сообщение, что далеко не соответствует желаемому результату. Нам же требуется своего рода чередование взаимодействий между P и (m: R) с взаимодействиями между Q и (m: R). В этом случае (m: R) служит как ресурс, разделяемый P и Q; каждый из них использует его независимо, и их взаимодействия с ним чередуются.

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

Пример. Совместно используемая подпрограмма: удв: УДВ // (P ||| Q). Здесь и P, и Q могут содержать вызов подчиненного процесса (удв.лев!v → удв.прав?х → ПРОПУСК), где ПРОПУСК – процесс, который ничего не делает, но благополучно завершается.

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

Ячейка общей памяти – это разделяемая переменная: (счет: ПЕРЕМ // (счет.лев!0 → (P ||| Q))). Произвольное чередование присваиваний в ячейку общей памяти различными процессами является следствием многочисленных опасностей.

Пример проблемы. Взаимное влияние.

Разделяемая переменная счет используется для подсчета числа исполнений некоторого важного события. При каждом наступлении этого события соответствующий процесс Р или О пытается изменить значение счетчика парой взаимодействий: счет.прав?х; и счет. лев!(х + 1).

К сожалению, эти два взаимодействия могут перемежаться аналогичной парой взаимодействий от другого процесса, в результате чего мы получим последовательность

счет.прав?х → счет.прав?у → счет.лев!(у + 1) → счет.лев!(х+ 1) →....

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

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