Теория

15.Ресурсы, конфликты на ресурсах. Разрешение конфликтов с помощью «временной синхронизации». Преимущества и недостатки метода.

Процессы Zi в системе Q развиваются параллельно. Это значит, что они изменяют значения параметров системы в течение одного и того же интервала времени. Достаточно типичны ситуации, когда по логике функционирования системы накладываются ограничения на изменение некоторых параметров несколькими процессами одновременно в течение заданного либо обусловленного интервала времени. Совокупность параметров системы, на изменение которых сформулированы некоторые ограничивающие условия, называется ресурсом R. Таким образом, R Q. Если объект Оk изменяет параметры ресурса R, то R Ok. Захват ресурса R процессом Z означает получение разрешения процессу Z изменять значения параметров q R.

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

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

Процесс Z1 может захватывать ресурс R лишь в интервалах (t1,t2), (t4,t5), (t7,t8) и т.д.,

процесс Z2 - в интервалах (t2,t3), (t5,t6), (t8,t9) и т.д., процесс Z3 - в интервалах (t3,t4), (t6,t7), (t9,t10) и т.д. Захват ресурса возможен на период одного интервала. Этот способ широко используется,

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

16.Ресурсы, конфликты на ресурсах. Разрешение конфликтов с помощью блоков – контроллеров

Процессы Zi в системе Q развиваются параллельно. Это значит, что они изменяют значения параметров системы в течение одного и того же интервала времени. Достаточно типичны ситуации, когда по логике функционирования системы накладываются ограничения на изменение некоторых параметров несколькими процессами одновременно в течение заданного либо обусловленного интервала времени. Совокупность параметров системы, на изменение которых сформулированы некоторые ограничивающие условия, называется ресурсом R. Таким образом, R Q. Если объект Оk изменяет параметры ресурса R, то R Ok.Захват ресурса R процессом Z означает получение разрешения процессу Z изменять значения параметров q R.

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

Наиболее общий способ управления процессами при захвате ресурсов состоит в создании соответствующих К-блоков.

П

R

Здесь первые П-блоки реализуют процессы Z1’ и Z2’ в пространстве Q\R; затем производится пассивизация инициаторов I1 и I2, они переводятся в параметры a и b соответственно. К-блок рассматривает ситуацию с входными параметрами в соответствие с собственным алгоритмом. Приняв решение о захвате ресурса каким-либо процессом, К-блок передает a или b в параметр e и активизирует его, отсылая в П-блок ресурса R. После завершения процесса в R выдается сигнал в параметре f, в ответ на который К-блок передает параметр-инициатор в c либо d и активизирует его, отсылая на продолжение процесса Z1’’, либо Z2’’ в соответствующие П-блоки. Использование К-блоков является наиболее универсальным способом управления множеством процессов при захвате ресурсов.

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

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

Будем реализовывать на однопроцессорной системе.

Совокупность обоих описаний, идущий параллельно во времени, мы отобразим на последовательный трек так, чтобы результат вычислений в нем не отличался бы от результатов вычислений в параллельных процессах. Этот процесс будем называть квазипараллельным. В нем 1 инициатор.

Попробуем отобразить первый процесс:

1)если операторы не сцеплены, то на линии времени КПП (квазипараллельного процесса) мы можем расположить операторы первого процесса в произвольном порядке. Чтобы потом расставить их результаты в правильном порядке, надо просто посмотреть, в какое время они выполнялись в самом процессе.

2)если некоторые из них между собой сцеплены. Зная времена, можем расставить результаты в верном порядке, а так как мы учли отношение сцеплённости, то мы не нарушили причинно-следственную связь:

3) а теперь если все они сцеплены, расставить можно только в порядке трека:

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

А теперь посмотрим с двумя процессами: 1) Z1 и Z1 не сцеплены между собой:

Операторы каждого процесса по отношению друг к другу идут как хотят, можно не подряд, но операторы каждого процесса идут строго по треку;

2) Z1 и Z1 сцеплены:

Если придерживаться правила выполнения на КПП в строгом соответствии со временем, то тогда отпадает необходимость знания сцеплённости у одновременных событий. И тогда остаётся проблема, в каком порядке выполнять одновременные события (порядок вычисления одновременных точек в исходных параллельных процессах). Если сказать умнее, то если следовать правилу монотонного роста (назад возвращаться нельзя) времени в КПП, то мы реализуем автоматически все варианты сцеплений внутри каждого процесса и все варианты сцеплений между процессами вне одновременных точек.

Ещё раз, когда у нас несколько процессов

Z1 S1 ,T1, F1, 1

Z1 S2 ,T2 , F2 , 2

...

Zn Sn ,Tn , Fn , n

КПП будет Zкпп Sкпп,Tкпп, Fкпп, кпп , и в КПП будут выполняться по росту. Итого, надо следить, чтобы ни одно из не нарушилось, и надо иметь механизм определения сцепления для одновременных событий.

18.Квазипараллельный процесс. Формирование модельного времени.

Будем реализовывать на однопроцессорной системе.

Совокупность обоих описаний, идущий параллельно во времени, мы отобразим на последовательный трек так, чтобы результат вычислений в нем не отличался бы от результатов вычислений в параллельных процессах. Этот процесс будем называть квазипараллельным. В нем 1 инициатор.

Рассмотрим последовательность выполнения элементарных операторов в системе. Система содержит 9 объектов, в каждом из которых развивается процесс. Пусть в некоторый момент времени система находилась в начальном состоянии. Для каждого процесса Zi указан текущий элементарный оператор в следующих обозначениях: hni ,c , hni , y ,

где i - номер процесса (он же - номер строки);

n - порядковый номер элементарного оператора в своем треке; с - символ “состояние”; у=л - символ логического условия продвижения инициатора;

у=t - символ временного условия продвижения инициатора.

Предположим, что к этому моменту времени все элементарные операторы вычислены. Тогда активное временное множество на текущий момент равно {t110, t311, t621, t926,}

Определим очередной момент времени, как: t0 =min {t110, t311, t621, t926}

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

времени t110, соответствующее временному условию h1,t9.

Начальное состояние

В этот момент времени инициатор I1 процесса Z1 перемещается в элементарный оператор (h1,c10, h1,л10) , вычисляя новое состояние объекта O1, а значит, и системы в целом. При этом оказывается выполненным условие h4,Л15 и h7,Л19.. В треке процесса Z4 выполняется оператор состояния h4,с16 и устанавливается логическое условие h4,Л16, а в треке процесса Z7 – h7,с20 и временное условие h7,t20. Так как больше условий не выполняется, то необходимо перейти к новым элементарным операторам в соответствии с треками. В рассматриваемый момент

времени следующее активное временное множество имеет вид t113 ,t216 ,t217 ,t269 . Необходимо

перейти к новому моменту времени t0 min t113 ,t216 ,t217 ,t269 . В нашем случае t0=t113 . Первым выполняется оператор h113, c , h113, t , который изменяет состояние объекта O3 и системы в целом, а также формирует новый заказ времени передвижения своего инициатора I3 в момент времени t123 . При этом выполняются логические условия для процессов Z5 и Z8. Инициаторы I5 и I8 вызывают выполнение операторов h5,c7 ,h5,л7 и h8,c32 ,h8,л32 соответственно. Формируется новое активное временное множество: t123 ,t216 ,t217 ,t269 , наименьшим в котором является t216 . С оператора h216,c ,h216,л и начинается следующий цикл вычислений, и т.д.

На этом примере хорошо иллюстрируется алгоритм продвижения модельного времени, т.е. времени, в котором описано функционирование системы и порядок выполнения элементарных операторов в каждом процессе.

20.Класс одновременных событий. Свойства класса одновременных событий.

Множество событий, происходящих в один и тот же момент модельного времени, назовем классом одновременных событий (КОС). Класс одновременных событий в момент времени t10l

включает события для 1, 4 и 7-го процессов; в момент времени t113 КОС составляют события для

3, 5 и 8-го процессов и т.д.

Рассмотрение КОС показывает, что в каждом КОС содержится активное событие. Введем следующие допущения:

Допущение 1. В каждом КОС содержится одно и только одно активное событие. Тогда: а) все остальные события в КОС, если они есть, являются пассивными; б) количество КОС равно мощности объединенного множества времен T.

Допущение 2. Первым событием в любом КОС является активное событие.

Если это так, то оставшиеся пассивные события для определения последовательности своего выполнения требуют знания отношения сцепления. Представим отношение сцепления в КОС в виде направленного графа..

Здесь: ha - активное событие; hb, hc, hd, he, hf- пассивные события.

Из графа следует, что после ha необходимо выполнить hb либо hc; затем hd, либо he; и наконец hf.

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

Так, условие выполнения события hd должно содержать выражение, проверяющее выполнение события hb. Если это удается сделать, то алгоритм формирования КОС выглядит следующим образом:

1.Выполняется активное событие.

2.Проверяются условия всех возможных в системе пассивных событий.

3.Если выполняется условие пассивного события, то оно вычисляется. Алгоритм продолжается с п.2.

Важно найти признак, по которому можно определить завершенность КОС.

КОС завершен, если все условия, заданные операторами hл во всех треках, равны 0.

Поскольку КОС содержит одно активное событие и оно выполняется первым, то все остальные

события пассивные. Пассивное событие по определению выполняется, если определяющее его условие равно 1. Однако, по предположению, все условия, заданные hл равны 0. Таким образом, выполнение пассивного события невозможно, а единственное активное событие уже выполнено. Поскольку не выполняется ни один элементарный оператор, состояние системы и параметры условных операторов не могут быть изменены. Состояние системы зафиксировано и не будет изменено вплоть до нового КОС.

Первым событием в КОС является активное событие. Когда завершен КОС, все условия

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

21.Моделирующий алгоритм сканирующего типа. Состав компонент, таблицы, структура.

Моделирующий алгоритм в любом случае должен включать следующие составные части:

подпрограммы событий, реализующие элементарные операторы;

алгоритм формирования модельного времени;

алгоритм выбора очередного КОС;

алгоритм генерирования КОС.

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

от {hi}

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

Параметр ВРЕМЯ - содержит текущее значение модельного времени; Параметр ИНИЦИАТОР - содержит значение текущего инициатора (ссылку на локальную

среду процесса).

КАЛЕНДАРЬ - алгоритм, реализующий монотонно возрастающее продвижение модельного времени и начало нового КОС в системе.

АПУ - Алгоритм Проверки Условий, обеспечивающий построение КОС для текущего значения модельного времени.

ТБВ - Таблица Будущих Времен. Каждая строка ТБВ соответствует одному процессу и содержит следующие элементы описания будущего активного события:

столбец 1 - значение момента времени активизации инициатора, определяемого предшествующим оператором ht ;

столбец 2 – инициатор процесса; столбец 3 - адрес подпрограммы активного события в треке данного процесса.

Совокупность значений атрибута “момент активизации” таблицы ТБВ составляет в любой момент модельного времени активное временное множество.