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 -


 

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

83631. Перечислить мероприятия предотвращающие электромагнитную наводку на кабели в ОРУ и устройства в ЗРУ 29.45 KB
  Должны выполняться мероприятия исключающие электростатические и электромагнитные наводки на металлических элементах расположенных в помещениях аккумуляторных батарей а также заносы туда высоких потенциалов. Для защиты от электростатической индукции на указанных элементах достаточно надежно присоединить к общему заземляющему устройству электростанций и подстанций гладкие трубы в помещениях аккумуляторных батарей предназначенные для отопления и выдержать расстояния от токоведущих шин до частей здания и других заземленных элементов не менее...
83632. Назначение кабельного журнала и что отражено на листах кабельного журнала 30.27 KB
  В кабельном журнале описывается маркировка каждого кабеля откуда и куда он идет его марка длина кабельной линии и его назначение. Назначение: Всю необходимую информацию о кабелях можно представить непосредственно на схемах: можно указать марку длину способ прокладки кабеля. Однако при построении достаточно большой системы во избежание перегруженности чертежей удобнее вынести эти данные в отдельную таблицу оставив на схемах лишь присвоенные кабелям обозначения. Во время монтажа в кабельный журнал заносятся следующие сведения: номер...
83633. Выполнение чертежей оперативной блокировки на ПС. Что должно быть отражено на чертеже. Какие виды блокировки коммутационных оборудований используются на ПС 30.11 KB
  Основные требования к оперативной блокировке: Блокзамки блокировки должны запирать приводы разъединителей только в крайних положениях включено и отключено; они не должны запирать привод разъединителя в промежуточном положении; Оперативная блокировка не должна давать ложное разрешение на операции с разъединителями при исчезновении напряжения оперативного тока или неисправностях самой оперативной блокировки. Механическая блокировка это блокировка непосредственного действия которая может быть выполнена на близко...
83634. Нелинейные магнитные цепи при постоянных потоках 161 KB
  Для концентрации магнитного поля и придания ему желаемой конфигурации отдельные части электротехнических устройств выполняются из ферромагнитных материалов. Векторные величины характеризующие магнитное поле Наименование Обозначение Единицы измерения Определение Вектор магнитной индукции Тл тесла Векторная величина характеризующая силовое действие магнитного поля на ток по закону Ампера Вектор намагниченности А м Магнитный момент единицы объема вещества Вектор напряженности магнитного поля А м где Гн м магнитная постоянная Основные...
83635. Общая характеристика задач и методов расчета магнитных цепей 128 KB
  При этом для наглядности можно составить эквивалентную электрическую схему замещения исходной магнитной цепи с использованием которой выполняется расчет. При расчете магнитных цепей на практике встречаются две типичные задачи: задача определения величины намагничивающей силы НС необходимой для создания заданного магнитного потока заданной магнитной индукции на каком либо участке магнитопровода задача синтеза или ldquo;прямаяldquo; задача; задача нахождения потоков магнитных индукций на отдельных участках цепи по заданным...
83636. Нелинейные цепи переменного тока в стационарных режимах 136.5 KB
  Когда постоянная времени нагрева τ одного порядка с Т соотношения между переменными составляюшими напряжения и тока являются более сложными определяющими сдвиг по фазе между ними. Другой важной особенностью нелинейных элементов в цепи переменного тока является вызываемое ими появление высших гармоник даже при наличии в цепи только источников синусоидального напряжения и или тока. На этом принципе строится например ряд умножителей частоты а также преобразователей формы тока или напряжения.
83637. Графический метод с использованием характеристик по первым гармоникам 130 KB
  Основные этапы расчета: строится график зависимости нелинейного элемента для первых гармоник; произвольно задаются амплитудой одной из переменных например связанной с нелинейным элементом и по характеристике последнего находят другую переменную определяющую режим работы нелинейного элемента после чего принимая все величины синусоидально изменяющимися во времени на основании построения векторной диаграммы определяется амплитуда первой гармоники переменной на входе цепи; путем построения ряда векторных диаграмм для различных...
83638. Метод кусочно-линейной аппроксимации 134 KB
  Для каждого участка ломаной определяются эквивалентные линейные параметры нелинейного элемента и рисуются соответствующие линейные схемы замещения исходной цепи. Расчет каждой из полученных линейных схем замещения при наличии в цепи одного нелинейного элемента и произвольного числа линейных не представляет труда. При наличии в цепи переменного источника энергии рабочая изображающая точка будет постоянно скользить по аппроксимирующей характеристике переходя через точки излома.
83639. Метод эквивалентных синусоид (метод расчета по действующим значениям) 181 KB
  Катушка с ферромагнитным сердечником Нелинейная катушка индуктивности изображена на рис. Различают параллельную и последовательную схемы замещения катушки с ферромагнитным сердечником. Схемы замещения уравнения и векторные диаграммы для катушки c ферромагнитным сердечником Схема замещения Уравнения и соотношения для параметров Векторная диаграмма Параллельная Последовательная где где Примечание. Трансформатор с ферромагнитным сердечником Трансформатор с ферромагнитным сердечником изображен на рис.