Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 66
Текст из файла (страница 66)
рис. 8.4).Формальные модели для изученияпроблемы тупиковых ситуацийПроблема борьбы с тупиками становится все более актуальной ^сложной по мереразвития и внедрения параллельных вычислительных систем и сетей. При проектировании таких систем разработчики стараются проанализировать возможныенегативные ситуации, используя специальные модели и методы.К настоящему времени разработано несколько десятков различных моделей, предназначенных для анализа и моделирования систем с параллельными асинхронными процессами, для которых возможность возникновения тупиковых ситуацийявляется очень серьезной проблемой. Изложение и сравнительный анализ этихмоделей может составить большую монографию, поэтому здесь мы лишь краткорассмотрим только три из них — сети Петри, модель пространства состояний и ужеупомянутую нами модель Холта.Сети ПетриСреди многих существующих методов описания и анализа параллельных систем ужеболее 35 лет значительное место занимают сетевые модели, восходящие к сетям специального вида, предложенным в 1962 году Карлом Петри для моделирования асинхронных информационных потоков в системах преобразования данных [36].Взаимодействие событий в параллельных асинхронных дискретных системах IINет, как правило, сложную динамическую структуру.
Эти взаимодействия описваются проще, если указывать не непосредственные связи между событиями, аситуации, при которых данное событие может реализоваться. При этом глооаформальные модели для изучения проблемы тупиковых ситуаций255е ситуации в системе формируются с помощью локальных операций, называемых условиями возникновения событий. Определенные сочетания условий допус' ают возникновение некоторого события {предусловия события), а реализацияобытия изменяет некоторые условия {постусловия события), то есть события взаимодействуют с условиями, а условия — с событиями. Таким образом, предполагается, что для решения задач достаточно представить системы как структуры, образованные из элементов двух типов: событий и условий.
Удобное обобщение этого,предложенное Петри, было развито А. Холтом, который назвал его сетью Петри,В сетях Петри события и условия представлены абстрактными символами из двухнепересекающихся алфавитов, называемых соответственно множеством переходови множеством позиций. Имеется несколько формальных представлений сетей Петри:О теоретико-множественное представление;нЫа графово-бихроматический (двудольный ориентированный) граф и, соответственно, графическое представление;• матричное представление.При использовании теоретико-множественного подхода к описанию сети Петри(поскольку эта модель представляет и структуру, и функционирование системы)она формально может быть определена как двойка вида N = <S, М0>. Здесь 5 — этоструктура сети, которая представляется двудольным ориентированным мультиграфом S=(V, U), где V— вершины этого графа, U— его дуги.
М0 — это начальноесостояние сети Петри, которое также называется начальной маркировкой. СетьПетри может функционировать и соответственно изменять свое состояние.В силу того что граф 5 является двудольным, можно перейти к формальному описанию структуры сети Петри в виде тройки:5 = < Р , Т, Y>.Здесь Р — конечное множество позиций, Р = {р;}, i = l,n; Г— конечное множествопереходов, Т = {tt}, j = 1, m; Т U P = V, Т П Р = 0 , то есть Г и Р - это два типа вершин биграфа S\Y — конечное множество дуг, заданное отношениями между вершинами графа 5:Ye{P-T)\j{T-P)..Посколькутгвудольный мультиграф 5 является ориентированным, то любой переход tj, j = \,m, соединяется с позициями pt e P через входные и выходные дуги,которые задаются через функцию предшествования В : {Р • Т) —> {0,1, 2,...} и функцию следования Е :{Т • Р) —> {0,1, 2,...}, являющиеся отображениями из множествапереходов в комплекты позиций [36] (синонимом термина «комплект» являетсяонятие мультимножества).
Эти функции определяют комплекты позицийiPii&P, связанных с переходом ^ е Г через множество дуг {(р,-/7-)/}> г Д е~ l'(Pi>f;)/ : i,j - const} < W, и комплекты позиций {рк}£ Р , связанных с переходом tj G Г через множестводуг {(tj,pk)l), где 1 < \{{tj,pk)t : j,k = const}| < W. Здесь~ мультичисло графа 5; Р — пространство комплектов, заданное на множестве РФункциями Ей В; {pj,tj)v — v-я дуга, выходящая из позициир, и входящая в пере-256Глава 8, Проблема тупиков и методы борьбы с нимиход t;, (tp pk)v — v-я дуга, выходящая из перехода t; и входящая в позициюр к .
Такимобразом, теперь структура S сети Петри Сможет быть представлена как четверка:5 = <Р, Т, В, Е>.Представим далее множество позиций Р как объединение двух пересекающихсямножеств: P = I\JO; If)O*0. Здесь мы через 1ч О обозначили следующие множества:mmЗдесьI(tj) = {Pi : B(pt,tj) > 1, i = Гя}, j = t m ; 0(£ ; ) = { A : £ ( f J , A ) £ U = u } , .7 = t m ;7где (pj, ^.) —дугасвесом да< U , выходящая из вершины/?, и входящая в вершину ц(tj<Pk) ~ ДУ га с весом w < W, выходящая из вершины t} и входящая в вершинурк,то есть I(tj) и 0(tj) — комплекты входных и выходных позиций перехода ^соответственно .Элементы множества Г обычно представляют собой те возможности (возможныеситуации, условия), при которых могут быть реализованы интересующие нас процессы (действия).Начальная маркировка М0 (как и текущая маркировка М, которая соответствуетнекоторому состоянию сети в текущий момент модельного времени) определяется одномерной матрицей (вектором), число компонентов которой равно числу позиций сети п, п = \Р\, а значение i-го компонента (1 < i < п ) есть натуральное число тп(р{), которое определяет количество маркеров (меток) в позиции р;.М 0 =(ш 0 (р 1 ),тл 0 (/з 2 ),...,т 0 (/?„));М=(m(pt),m(p2),...,m(p„)).Здесь mu(/j,), m(/?,) e Z ; Z — множество неотрицательных целых чисел.
Ее же (маркировку М) можно также представлять как множество или комплект с той разницей, что отсутствие некоторого элемента в множестве будем обозначать специальным элементом — нулем. В этом случае запись вида М; = М(_, - I(t) означаетразность множеств и такое изменение маркировки, при котором на соответствующих местах вектора М, будут уменьшенные значения.Передвижение маркеров по сети осуществляется посредством срабатывания еепереходов. При срабатывании перехода изменяется маркировка в его входных и выходных позициях. Получается, что срабатывание возбужденного перехода, являющееся локальным актом, в целом ведет к изменению маркировки сети, то есть к изменению ее состояния.
Таким образом, если в сети задана начальная маркировкаМ0, при которой хотя бы один переход возбужден, то в сети начинается движениемаркеров, отображающее смену состояний сети. Переход tj может сработать, если^ррмальные модели для изучения проблемы тупиковых ситуаций257р, € Щ) : m(Pi) > #{Pi, I(tj)) - w .Переход, для которого выполняется это условие, называется возбужденным.
Здесьп И с ь вида #(pi,I(t )) означает число появлений позиций р, во входном компакте перехода t/, оно, естественно, равно весу w соответствующей дуги, если вместо мультиграфа рассматривать взвешенный граф. При срабатывании перехода Цмаркировка М0 изменяется на маркировку М{ следующим образом:Иначе говоря:\/Pi е Р : Щ(р,) = т0(р,) - #{р„ /(£,)) + #(р„ Щ)) •Из последнего выражения видно, что количество маркеров, которое переход tj изымает из своих входных позиций, может не равняться количеству маркеров, которое этот переход помещает в свои выходные позиции, так как совсем не факт, чточисло входных дуг перехода равняется числу его выходных дуг.В графическом представлении сетей (оно наиболее наглядно и легко интерпретируемо) переходы изображаются вертикальными или горизонтальнымипланками (черточками), а позиции — кружками (см.
далее). Условия-позициии события-переходы связаны отношением непосредственной зависимости (непосредственной причинно-следственной связи), которое изображается с помощью направленных дуг, ведущих из позиций в переходы и из переходов в позиции.Позиции, из которых ведут дуги на данный переход, называются его входнымипозициями, а позиции, на которые ведут дуги из данного перехода, — выходными позициями.Выполнение условия представляется разметкой соответствующей позиции, а именно помещением числа п в это место или изображением там п маркеров (фишек),где п — емкость условия (п > 0).Говорят, что некоторый переход £• для разметки М является живым, если для всехразметок М\ достижимых из разметки М, существует последовательность срабатывания переходов, приводящая к маркировке М', при которой переход tj можетсработать.
Сеть Петри называется живой, если живы все ее переходы; живучая разметка — это разметка, при которой каждый из ее переходов сможет запускатьсябесконечное число раз. Когда достигнута такая разметка, при которой ни один изпереходов не может быть запущен, говорят, что сеть Петри завершилась (достигнута желаемая конечная маркировка) или же зависла (то есть имеет место тупиковая ситуация).Сети Петри очень удобны для описания процессов синхронизации и альтернатив.Например, семафор может быть представлен входной позицией, связанной с пеКолькими взаимоисключающими переходами (критическими секциями).
СетиетРИ позволяют моделировать асинхронность и недетерминизм параллельныхезависимых событий, параллелизм конвейерного типа, конфликтные взаимодейТ в и яМежду процессами. Говорят, что два перехода конфликтуют, если они взаНоисключают друг друга, то есть они не могут быть запущены оба одновременно.258Глава 8. Проблема тупиков и методы борьбы с нимиДва перехода, готовые к срабатыванию, находятся в конфликте, если они связаныс общей входной позицией.В качестве примера рассмотрим рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
