50615

Моделирование асинхронных вычислительных процессов

Лабораторная работа

Коммуникация, связь, радиоэлектроника и цифровые приборы

Пять философов прогуливаясь и размышляя время от времени испытывают приступы голода. Рис 41 При конструировании управления в этой задаче следует учитывать самые разнообразные варианты поведения философов. Необходимо организовать действия философов так чтобы они все были накормлены и не случилось бы так что пять философов одновременно войдут в столовую возьмут левую вилку и застынут в ожидании освобождения правой вилки. Голодная смерть всех философов неминуема если никто из них не захочет расстаться па время со своей левой вилкой.

Русский

2014-01-27

86 KB

8 чел.

Лабораторная работа 6

Моделирование асинхронных вычислительных процессов

6.1 Цель работы: научится анализировать наличие и отсутствие дедлоков в параллельной системе

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

В современных ОС принято выделять две основных функции управления вычислительным процессом:

  1.  обеспечение вычислительного процесса всеми необходимыми ресурсами (ОЗУ, программные модули и т.д.)
  2.  диспетчеризация процесса (изменение состояния процесса)

При взаимодействии потоков или процессов возможны различные аномалии, то есть некорректное выполнение взаимодействующих потоков/процессов. Например, блокировка, зависание, «голодание» (другие потоки мешают получить доступ к общим ресурсам; более приоритетные захватывают ресурсы).

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

Пример 1: «Сетевая модель взаимной блокировки двух потоков». Ситуация дедлока приведена на рисунке 1.

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

Пример 2: «Семафорный механизм сетевой модели»

Пример 1. Рассмотрим классическую задачу о пяти обедающих философах. Суть задачи такова. Пять философов, прогуливаясь и размышляя, время от времени испытывают приступы голода. Тогда они заходят в столовую, где стоит круглый стол, на нем всегда приготовлены пять блюд. Между соседними блюдами лежит одна вилка (всего лежат ровно пять вилок). Голодный философ:

  1.  входит в столовую, садится за стол и берет вилку слева;
  2.  берет вилку справа;
  3.  ест (обязательно двумя вилками);
  4.  кладет обе вилки на стол, выходит из столовой и продолжает думать.

Рис 41

При конструировании управления в этой задаче следует учитывать самые разнообразные варианты поведения философов. Рассмотрим некоторые из них.

  1.  Необходимо организовать действия философов так, чтобы они все были накормлены и не случилось бы так, что пять философов одновременно войдут в столовую, возьмут левую вилку и застынут в ожидании освобождения правой вилки. Голодная смерть всех философов неминуема, если никто из них не захочет расстаться па время со своей левой вилкой. Будет не лучше, если они одновременно положат левые вилки, а затем вновь одновременно попытаются завладеть необходимыми двумя вилками. Результат, понятно, тот же. Типичный дедлок в результате попытки дозахватить ресурс (вилку)!

Рис 42

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

  1.  Необходимо также предусмотреть, чтобы два философа одновременно не хватали одну и ту же вилку (зная вспыльчивый характер философов, нетрудно предсказать результат).
  2.  Стеснительный философ не должен умирать голодной смертью из-за того, что его вилки постоянно раньше него хватают напористые соседи.
  3.  Легко представить себе ситуацию, когда банда сговорившихся философов завладеет всеми вилками и, передавая их только в своей среде, уморит голодом всех прочих.

Сеть Петри, задающая управление распределением вилок обедающим философам, строится пошагово. Вначале была сконструирована сеть, управляющая поведением одного (любого) философа (рис. 42). Далее она используется для конструирования сети, управляющей поведением нескольких философов. Разделяемые ресурсы - левые и правые вилки - разных фрагментов сети совмещаются.

Пример 6. Другой пример взаимодействующих процессов показан на рис. 44,а. Здесь производитель П производит детали и оставляет их на складе t5, а потребитель Т забирает их со склада, когда они там есть. Регулирует это взаимодействие место t5. Если необходимо принять во внимание ограниченную вместимость склада, тогда в сеть добавляется место t6 (рис 44,б). Оно определяет наличие места для хранения 10 деталей. Взятие фишки из места t6, может интерпретироваться как взятие разрешения поместить очередную деталь на склад (есть свободное место для хранения).

Рис 44

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

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

PAGE  - 1 -


 

А также другие работы, которые могут Вас заинтересовать

24035. Бронхоэктатическая болезнь: клиника, диагностика, лечение 34.59 KB
  Существуют несколько классификаций бронхоэктатической болезни но в клинической практике чаще используется классификация А. Форма болезни: а легкая бронхитическая б выраженная в тяжелая г сухая кровоточащая. Течение болезни: а стационарное б прогрессирующее частота и длительность обострении. При хорошо собранном анамнезе часто удается выявить перенесенную в раннем детском возрасте пневмонию послужившую причиной развития бронхоэктатической болезни.
24036. Симптоматические язвы желудка и двенадцатиперстной кишки: клиника, диагностика 33.68 KB
  Симптоматические язвы желудка и двенадцатиперстной кишки это язвы которые возникают под действием язвопровоцирующего фактора. Их отличает от язвенной болезни то что всегда удается выявить провоцирующий язву фактор и если убрать этот фактор заживление язвы и выздоровление происходит достаточно быстро. Симптоматические язвы бывают: стрессовые лекарственные эндокринные возникшие на фоне заболеваний других внутренних органов.
24037. Ревматоидный артрит: клиника, диагностика, лечение 36.22 KB
  Течение болезни Ревматоидный артрит прогрессирует в трёх стадиях. Критериями неблагоприятного прогноза являются: раннее поражение крупных суставов и появление ревматоидных узелков увеличение лимфатических узлов вовлечение новых суставов при последующем обострении; системный характер болезни; персистирующая активность болезни при отсутствии ремиссии более года; стойкое увеличение СОЭ; раннее появление в течение первого года и высокие титры ревматоидного фактора ранние до четырёх месяцев рентгенологические изменения со стороны поражённых...
24038. Хронические обструктивные болезни легких 33.58 KB
  Мерцание и трепетание предсердий: тактика лечения. Мерцание предсердий хаотичное сокращение отдельных групп мышечных волокон предсердий при этом предсердия в целом не сокращаются а в связи с изменчивостью атриовентрикулярного проведения желудочки сокращаются аритмично обычно с частотой около 100150 в 1 мин. Трепетание предсердий регулярное сокращение предсердий с частотой около 250300 в 1 мин; частота желудочковых сокращений определяется предсердножелудочковой проводимостью желудочковый ритм может быть при этом регулярным или...
24039. Желчекаменная болезнь: этиология, клиника, диагностика 27.21 KB
  АМИЛОИДОЗ ПОЧЕК АП является проявлением общего амилоидоза который представляет собой системное заболевание характеризующееся внеклеточным отложением особого белковополисахаридного комплекса амилоида что приводит в конечном итоге к нарушению функции органов. До сих пор не существует общепринятой классификации амилоидоза. По наличию или отсутствию причинного фактора выделяют следующие формы амилоидоза: 1 идиопатический первичный; 2 наследственный генетический встречающийся при периодической болезни и некоторых формах семейного...
24040. Анемия. Классификации 23.57 KB
  Для этого наиболее удобно делить анемии по единому классификационному признаку цветовому показателю. Классификация анемий Анемии подразделяют на группы по различным признакам. В зависимости от него различают такие анемии: Гипохромные ЦП ниже 085: железодефицитная анемия талассемии Нормохромные ЦП в норме: гемолитические анемии когда скорость разрушения эритроцитов превышает скорость их продукции постгеморрагическая как результат потери крови вследствие кровотечения или кровоизлияния неопластические заболевания костного мозга...
24041. Системная красная волчанка: этиология, клиника, диагностика 26.34 KB
  Системная красная волчанка СКВ болезнь ЛибманаСакса лат. Разумеется эти симптомы не патогномоничны но сочетание с другими более специфическими увеличивает вероятность того что больной страдает СКВ. Дерматологические проявления Кожные проявления имеются у 65 больных СКВ возникают одними из первых однако только у 30 50 отмечается классическая сыпь на щеках в форме бабочки. Гнёздная алопеция и ульцерация полости рта и носа влагалища также в числе возможных проявлений СКВ.
24042. Легочное сердце: этиология, патогенез, классификация 24.69 KB
  ЛЕГОЧНОЕ СЕРДЦЕ патологическое состояние характеризующееся гипертрофией и дилатацией а затем и недостаточностью правого желудочка сердца вследствие артериальной легочной гипертензии при поражениях системы дыхания. Различают: 1 васкулярную форму легочного сердца при легочных васкулитах первичной легочной гипертензии горной болезни тромбоэмболии легочных артерий; 2 бронхолегочную форму наблюдавшуюся при диффузном поражении бронхов и легочной паренхимы при бронхиальной астме бронхиолите хроническом обструктивном бронхите...
24043. Хроническая застойная сердечная недостаточность. Классификации 31.12 KB
  Функциональные болезни пищевода этиология патогенез. Этиология функциональных заболеваний пищевода до настоящего времени неизвестна. Отмечено что весьма часто они сочетаются с грыжами пищеводного отверстия диафрагмы пептическим эзофагитом новообразованиями пищевода и желудка язвенной болезнью и холециститом атеросклерозом бронхиальной астмой паркинсонизмом сахарным диабетом и другими заболеваниями. Таким образом продвижение пищи по пищеводу есть сложный акт осуществляемый за счет перистальтики грудного отдела пищевода и...