50615

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

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

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

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

Русский

2014-01-27

86 KB

6 чел.

Лабораторная работа 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 -


 

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

20451. Диаграмма кооперации (collaboration diagram) 122.5 KB
  Прежде всего на диаграмме кооперации в виде прямоугольников изображаются участвующие во взаимодействии объекты содержащие имя объекта его класс и возможно значения атрибутов. В отличие от диаграммы последовательности на диаграмме кооперации изображаются только отношения между объектами играющими определенные роли во взаимодействии. Кооперация Понятие кооперации collaboration является одним из фундаментальных понятий в языке UML.
20452. MySQL 122 KB
  MySQL является собственностью компании Oracle Corporation получившей её вместе с поглощённой Sun Microsystems осуществляющей разработку и поддержку приложения. MySQL является решением для малых и средних приложений. Обычно MySQL используется в качестве сервера к которому обращаются локальные или удалённые клиенты однако в дистрибутив входит библиотека внутреннего сервера позволяющая включать MySQL в автономные программы.
20453. Диаграмма деятельности (activity diagram) 136 KB
  Для моделирования процесса выполнения операций в языке UML используются диаграммы деятельности. Каждое состояние на диаграмме деятельности соответствует выполнению некоторой элементарной операции а переход в следующее состояние выполняется только при завершении этой операции. Таким образом диаграммы деятельности можно считать частным случаем диаграмм состояний.
20454. Разработка и эксплуатация информационных систем 273.62 KB
  Объект сущность в адресном пространстве вычислительной системы появляющаяся при создании экземпляра класса например после запуска результатов компиляции и линковки исходного кода на выполнение. Конечным продуктом этапа проектирования являются: схема базы данных на основании erмодели разработанной на этапе анализа; набор спецификаций модулей системы они строятся на базе моделей функций. На основании системного проекта осуществляется: составление перечня автоматизированных рабочих мест предприятия и способов взаимодействия между...
20455. Кнопкові форми 24.5 KB
  На кнопкову форму виносять форми які відкривають формизвіти або активізують інші кнопкові формизакривабть поточну базу даних. Кнопокі форми можуть містити малюнкинаписи тощо. Кнопкові форми можна створити за допомогою диспетчера кнопкових форм за його допомогою на форму можна помістити до 8 кнопок.
20456. Комбінований метод хорд та дотичних 35.5 KB
  Характерна особливість методів дотичних і хорд та що послідовності їх наближень монотонні. Причому якщо для даного рівняння послідовність наближень методу хорд монотонно спадна то послідовність наближень методу дотичних – монотонно зростаюча і навпаки. У даному випадку за початкове наближення в методі хорд вибирають точку x=a а в методі дотичних – точку b.
20457. Множина́ 41.69 KB
  Основні поняття: Множина вважається означеною якщо про кожен об'єкт що розглядається можна казати що він або належить або не належить множині. Наприклад: ℕ множина натуральних чисел ℤ множина цілих чисел ℚ множина раціональних чисел ℝ множина дійсних чисел ℂ множина комплексних чисел. Нехай А множина. Множина B всі елементи якої належать множині А називають підмножиною множини A або частиною множини А і позначають цей факт символами B ⊆ A A ⊇ B.
20458. Основні задачі та проблеми проектування програмних продуктів 13.41 KB
  Пр428 Основні задачі та проблеми проектування програмних продуктів. Проектування – це процес розробки проекту тобто комплекту документації призначену для створення проекту його удосконалення та ліквідації а також для перевірки або відтворення проміжних і кінцевих рішень. Проектування – тривалий процес і включає етапи від підготовки технічного завдання до випробування. Процес створення програмного забезпечення ПЗ також включає в себе методи проектування.
20459. Каскадна (послідовна) модель 22.61 KB
  Вона передбачає послідовне виконання всіх етапів проекту в строго фіксованому порядку. Вимоги визначені на стадії формування вимог строго документуються у вигляді технічного завдання і фіксуються на весь час розробки проекту. Етапи проекту відповідно до каскадної моделлю: Формування вимог; Проектування; Реалізація; Тестування; Впровадження; Експлуатація та супровід. Недоліки: В Водоспадної моделі перехід від однієї фази проекту до іншого передбачає повну коректність результату виходу попередньої фази.