50615

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

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

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

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

Русский

2014-01-27

86 KB

7 чел.

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


 

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

36380. Схемы внешних электрических и трубных проводок. Основные требования и правила выполнения 36 KB
  Схемы внешних электрических и трубных проводок. Схема соединений внешних проводок это комбинированная схема на которой показывают электрические и трубные связи между приборами и средствами автоматизации установленными на технологическом оборудовании вне щитов и на щитах а также подключения проводок к приборам и щитам. Схему подключения допускается не выполнять если все подключения могут быть показаны на схеме соединений внешних проводок. При необходимости раздельного изображения электрических и трубных проводок цеха участка...
36381. Учет персонала 29.58 KB
  Учет персонала. Взаимосвязи подсистемы Учет персонала : Из подсистемы АНАЛИЗ и УПРАВЛЕНИЕ приказы нормативы и запросы на получение информации. Информация из бухгалтерии о расходах на содержание персонала отчеты по начислениям з платы и прочие денежные выплаты. Различные отчеты и сводки для подсистемы АНАЛИЗ и УПРАВЛЕНИЕ об использовании персонала численность и качественный состав работников данные для статистики расходы на содержание персонала и т.
36382. Экстремальные регуляторы 51.93 KB
  Задача поиска экстремума разбивается на две части 1 определение отклонений от точки экстремума изучение объекта 2 организация движения к точке экстремума. ЭР с запоминанием экстремума: ЭР вкл в себя ЗУ – зап. В резте устанавливается автоколебательный режим работы регра около точки экстремума. Если Х0 сигнум – реле не меняет направление вращения ИМ если Х0 то производится реверс ИМ изменяется направление поиска экстремума.
36383. Дайте классификацию и поясните сущность интегральных критериев качества 35.68 KB
  Наибольшее распространение получили три интегральных критерия: А линейный Б квадратичный В квадратичная оценка отклонения от эталона А Линейный критерий качества 6 6 где отклонение переходного процесса от устойчивого значения; Уmt – функция веса ε1tmemtedttm Возможности критерия 7: 1У0t=t0=1 7 Критерий J10 7 – площадь под кривой переходного процесса с учетом знака рис. 2 Критерий J10 7 пригоден только для анализа апериодических процессов. В этом случае J10=min...
36384. Моделирование на ЭВМ типовых звеньев САУ 59.29 KB
  Моделирование на ЭВМ типовых звеньев САУ В состав структурных схем большинства систем автоматического управления САУ входит достаточно ограниченный набор типовых звеньев. В основу процедуры моделирования многих типовых звеньев положен метод РунгеКутта. Апериодическое звено первого порядка Реальное дифференцирующее звено Пропорциональноинтегральное звено Структурные схемы некоторых типовых звеньев. При моделировании более сложных звеньев таких как апериодическое пропорциональноинтегральное дифференциальное и т.
36385. Принцип действия термопары и термометра сопротивления 37.39 KB
  Термопара – два разнородных с различной концентрацией свободных электронов металлических проводника – термоэлектроды соединенных пайкой или сваркой на измерительном рабочем конце подвергаемом воздействию измеряемой температуры и разомкнутых на контрольном свободном конце находящемся под воздействием известной температуры и подключаемом к измерительному прибору. Принцип действия термопреобразователей сопротивления или резистивных детекторов температуры основан на способности металлов или полупроводниковых материалов изменять...
36386. Техническое обеспечение САПР 12.99 KB
  Выделяют автоматизированные рабочие места АРМ трех классов: микро АРМ для решения простых конструкторских и технологических задач в автономном режиме в составе средств двухуровневой САПР. Средние АРМ помимо задач выполняемых микро АРМ посредством графического процессора позволяют представлять объект проектирования в двух и трехмерном виде имеют пакеты прикладных программ инвариантные к различным видам объекта проектирования. Супер АРМ способны решать весь комплекс задач САПР в масштабе предприятия. Все вычислительные комплексы САПР в том...
36387. Универсальные CADCAMCAE-системы 12.71 KB
  Универсальные CDCMCEсистемы. Системы проектирования в масштабах предприятия за рубежом принято определять как CD CM CE – системы функции автоматизированного проектирования распределяются в них следующим образом: модули CD Computer ided Design – для геометрического моделирования и машинной графики модули подсистемы CM Computer ided Mnufcturing – для технологической подготовки производства а модули CE Computer ided Engineering – для инженерных расчетов и анализа с целью поверки проектных решений. Все универсальные CD CM CE –...
36388. Электрические принципиальные схемы систем и средств автоматизации. Назначение и правила выполнения 24.29 KB
  Электрические принципиальные схемы систем и средств автоматизации. Принципиальные электрические схемы определяют полный состав приборов аппаратов и устройств а также связей между ними действие которых обеспечивает решение задач управления регулирования защит измерения и сигнализации. Эти схемы служат для изучения принципа действия системы они необходимы при производстве наладочных работ и в эксплуатации. Схемы выполняются применительно к определенным самостоятельным элементам установкам или участкам автоматизированной системы...