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

⇐ ПредыдущаяСтр 38 из 50Следующая ⇒

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

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

Сети Петри

Среди многих существующих методов описания и анализа параллельных систем уже более 35 лет значительное место занимают сетевые модели, восходящие к сетям специального вида, предложенных в 1962 году Карлом Петри для моделирования асинхронных информационных потоков в системах преобразования данных [64].

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

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

¨ теоретико-множественное;

¨ графовое – бихроматический (двудольный ориентированный) граф и, соответственно, графическое;

¨ матричное.

При использовании теоретико-множественного подхода к описанию сети Петри (поскольку эта модель представляет и структуру, и функционирование системы) она формально может быть определена как двойка вида: N =á S, М₀ñ. Здесь S – это структура сети, которая представляется двудольным ориентированным мультиграфом S=(V, U), где V – вершины этого графа, U – его дуги. М₀ – начальное состояние сети Петри, которое также называется начальной маркировкой. В силу того, что граф S является двудольным, можно перейти к формальному описанию структуры сети Петри в виде тройки:

Sá P, T, Yñ,

где Р – конечное множество позиций, Р ={p_i}, i = ; Т – конечное множество переходов, Т = {t_j}, j = ; ТÈ Р = V, ТÇ Р = Æ, то есть Т и Р – это два типа вершин биграфа S; Y – конечное множество дуг, заданное отношениями между вершинами графа S: Y Î (Р * T)È (T * Р).

Поскольку двудольный мультиграф S является ориентированным, то любой переход t_j, j = соединяется с позициями р_i Î Р через входные и выходные дуги, которые задаются через функцию предшествования В: (P * T) ® {0, 1, 2,...} и через функцию следования Е: (Т * Р)® {0, 1, 2..}, являющиеся отображениями из множества переходов в комплекты позиций [64] (синонимом термина комплект является понятие мультимножества). Эти функции определяют комплекты позиций {р_i}Î , связанных с переходом t_j Î Т через множество дуг {(p_i, t_j)_l}, где l£ ½ {(p_i, t_j)_l: i, j = const}½ £ W, и комплекты позиций {р_k} Î , связанных с переходом t_j Î Т через множество_дуг {(t_j, p_k)_l}, где l£ ½ {(t_i, p_k)_l: j, k = const}½ £ W. Здесь W – мультичисло графа S; – пространство комплектов, заданное на множестве функциями Е и В; {(p_i, t_j)_v} – v-я дуга, выходящая из позиции p_i и входящая в переход t_j, {(t_i, p_k)_v – v-я дуга, выходящая из перехода t_j и входящая в позицию p_k.

Таким образом, теперь структура S сети Петри N может быть представлена как четверка: S(P, T, B, E). Представим множество позиций Р как объединение двух пересекающихся множеств: P=IÈ O; IÇ O¹ Æ. Здесь мы через I и О обозначим следующие множества:

I = I(t_j); O = O(t_j),

где I(t_j) = {p_i: B(p_i, t_j) ³ 1, i = }, j = ; O(t_j) = {p_k: E(t_j, p_k)³ 1 k = }, j = ;

(p_i, t_j) – дуга с весом w£ W, выходящая из вершины p_i и входящая в вершину t_j

(t_j, p_k) – дуга с весом w £ W, выходящая из вершины t_j и входящая в вершину p_k то есть I(t_j) и O(t_j) – комплекты соответственно входных и выходных позиций перехода t_j.

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

Начальная маркировка М₀ (как и текущая маркировка М, которая соответствует некоторому состоянию сети в текущий момент модельного времени) определяется одномерной матрицей (вектором), число компонентов которого равно числу позиций сети п, п =|Р |, а значение i-го компонента, 1 £ i £ . п, есть натуральное число m(p_i), которое определяет количество маркеров (меток) в позиции р_i то есть

М₀ = (m₀(p₁), m₀(p₂), …, m₀(p_n));

М = (m(p₁), m(p₂), …, m(p_n)),

где m(p₁) m(p_i)Î Z; Z – множество неотрицательных целых чисел. Маркировку М можно представлять и как множество или комплект с той лишь только разницей, что отсутствие некоторого элемента в множестве будем обозначать специальным элементом – нулём. В этом случае запись вида M_i = M_i_-1 – I(t) означает разность множеств и такое изменение маркировки, при котором на соответствующих местах вектора М_i будут уменьшенные значения.

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

p_iÎ I(t_j): m(p_i)³ (р_i, I(t_j)) – w.

Переход, для которого выполняется это условие, называется возбуждённым. Здесь запись вида #(р_i, I(t_j)) означает число появлений позиций р_i во входном комплекте перехода t_j оно, естественно, равно весу w, если вместо мультиграфа рассматривать взвешенный граф. При срабатывании перехода t_j маркировка М₀ изменяется на маркировку M₁ следующим образом: M₁ = М₀ – I(t_j) + О(t_j). Иначе говоря,

" p_iÎ P: т_i(р_i) – т₀(р_i) - #(р_i, I(t_j)) + #(р_i, О(t_j)).

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

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

Выполнение условия изображается разметкой соответствующей позиции, а именно помещением числа n или изображением n маркеров (фишек) в то место, где п > 0 – ёмкость условия.

Сети Петри могут быть использованы с точки зрения анализа системы на возможность возникновения в ней тупиковых ситуаций. Этот анализ проводится посредством исследования пространства возможных состояний сети Петри. При этом под последним понимается множество возможных маркировок сети. Анализ сетей посредством матричных методов имеет множество проблем, поэтому в основном используется подход, основанный на построении редуцированного до дерева1 графа возможных маркировок [49]. В таком дереве вершины графа – это состояния (маркировки) сети, а ветви дерева, помеченные соответствующими переходами сети, – это возможные изменения состояний сети, то есть срабатывания её переходов. Если взять любую вершину в таком дереве (за исключением корневой), то путь к этой вершине от корня дерева (путь из начальной маркировки к заданной) будет представлять собой последовательность срабатывания переходов.

Говорят, что переход t_j для разметки М является живым, если для всех разметок М' Î s(М) существует последовательность срабатывания переходов, которая приводит к маркировке М' при которой переход t_j может сработать. Сеть Петри называется живой, если все её переходы живы; живучая разметка – это разметка, при которой каждый из её переходов сможет запускаться бесконечное число раз. Когда достигнута такая разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри завершилась (достигнута желаемая конечная маркировка) или же зависла (то есть имеет место тупиковая ситуация).

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

В качестве примера рассмотрим рис. 7.5.

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

Эта сеть соответствует рассмотренному нами ранее примеру тупиковой ситуации (см. рис. 7.2), которая возникает при взаимодействии процессов ПР1 и ПР2 во время передачи сообщений и потреблении ресурса R каждым из процессов. Начальная маркировка для сети, показанной на рис. 7.5, будет равна (1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0). Здесь позиция p₂ означает, что процесс ПР1 получил три единицы ресурса R. Дуга, соединяющая позицию p₆ (число маркеров в ней соответствует количеству доступных единиц ресурса R), имеет вес 3 и при срабатывании перехода t₁ процесс ПР1 получает затребованные 3 единицы ресурса. Переход t₂ представляет посылку процессом ПР1 сообщения для ПР2; переход t_j – приём этого сообщения. Появление маркера в позиции p₇ означает, что процесс ПР2 обработал сообщение и послал ответ процессу ПР1. Срабатывание перехода t_j представляет возврат в систему трёх единиц ресурса, которыми владел процесс ПР1. Рассмотренная сеть не является живой, так как в ней всегда будут мертвы переходы t₃, t_j, t₆, t₇ и t₈.

Рис. 7.6. Сеть Петри для тупиковой ситуации на ресурсах типа SR

Примеру тупиковой ситуации, возникающему при работе с ресурсами типа SR, который мы также уже рассматривали ранее (см. рис. 7.3), соответствует сеть Петри, показанная на рис. 7.6.

В этой сети номера переходов соответствуют отмеченным номерам операторов, которые выполняют процессы ПР1 и ПР2, а позиции p₁ и р₂ – семафорам S₁ и S₂, над которыми выполняются Р- и V-операции. Сеть на рис. 7.6 также не является живой, хотя для неё и существуют такие последовательности срабатывания переходов, что тупиковой ситуации не наступит.

Алгоритм построения дерева достижимости изложен, например, в работе [64].

Вычислительные схемы

Вычислительная схема – это представление в графической форме асинхронной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистов» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления [89].

Граф потока данных (информационный граф) определяет входные и выходные данные для каждого оператора [18]. Дуга (R_i S_k) от регистра R_i к оператору S_k означает, что данные R_i являются элементом входных данных этого оператора; дуга (S_k R_j) определяет данные R_j как выходные. Очевидно, что некоторые данные R могут являться выходными для оператора S_i и входными для оператора S_j. Пример графа потока данных для некоторой вычислительной схемы представлен на рис. 7.7, а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.

Рис. 7.7. Пример вычислительной схемы: а – граф потока данных;

б – граф управления

Граф управления определяет последовательность выполнения операторов. Каждый оператор (представлен кружком) связан с некоторым количеством управляющих счётчиков (представлены прямоугольниками). Каждый из управляющих счётчиков содержит неотрицательное целое число. Текущие значения счётчиков совместно со значениями данных на графе потока данных определяют состояние вычислительной схемы. Пример графа управления представлен на рис. 7.7, б. Если все счётчики, указывающие на оператор S (то есть входные счётчики), имеют ненулевые значения, то говорят, что оператор S определен. В этом случае он может выполниться, изменив свои выходные регистры в соответствии с графом потока данных и изменив счётчики графа управления по следующему правилу:

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

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

Такая последовательность операторов S₁, S₂, ..., S_n, ..., что каждый оператор S, определён (то есть его входные счётчики не равны нулю) при тех значениях счётчиков, которые получаются в результате выполнения предшествующих операторов, называется последовательностью исполнения схемы. Поскольку с операторами не связано никакого особого отсчёта времени (подобно сетям Петри1), то порядок, в котором операторы будут выполняться, не всегда может быть предсказан. Любая допустимая последовательность исполнения является возможной последовательностью событий. Как мы уже знаем, для системы взаимодействующих параллельных процессов результаты вычислений зависят от последовательности исполнения, если не обеспечить взаимное исключение для критических интервалов. В случае, когда вычислительная схема вырабатывает одинаковые результаты для всех допустимых последовательностей исполнения, говорят, что она детерминирована. Схема на рис. 7.7 является детерминированной.

Рассмотрим вычислительную схему на рис. 7.8. Операторы S₁ и S₂как это видно из графа управления, выполняются параллельно и асинхронно. Очевидно, что значение регистра R₃ будет различным в зависимости от того, выполняется ли оператор S₁ раньше или позже оператора S₂. Поскольку граф управления здесь допускает последовательности исполнения, которые приводят к различным результатам, то эта схема не детерминирована.

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

Рис. 7.8. Пример недетерминированной вычислительной схемы

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

⇐ Предыдущая 33 34 35 36 373839 40 41 42 Следующая ⇒