Похожие публикации

Факультет последипломного образования
Документ
зв...полностью>>

Конкурс проводится в период с 1 октября по 20 ноября 2013 года, в два этапа
Конкурс
Областной конкурс коллажей «Здоровым быть модно» (далее – Конкурс) проводится в рамках областного межведомственного плана мероприятий оперативно – про...полностью>>

Списо к победителей и призеров Открытого международного историко-краеведческого конкурса
Конкурс
Модель: «Линейный корабль «Святой Януарий», (корабль на котором М.Г. Коковцев участвовал в Архипелагской экспедиции, в том числе в знаменитом морском ...полностью>>

Списо к победителей и призеров Открытого международного историко-краеведческого конкурса
Конкурс
Модель: «Линейный корабль «Святой Януарий», (корабль на котором М.Г. Коковцев участвовал в Архипелагской экспедиции, в том числе в знаменитом морском ...полностью>>



Система с общими ресурсами. Задачи о взаимном исключении

  1. Система с общими ресурсами. Задачи о взаимном исключении.

Пусть система включает в себя два ресурса p и q, и два процесса Р1 и Р2. Процесс Р1 запрашивает сначала ресурс q, потом ресурс р, потом их одновременно освобождает. Процесс Р2 запрашивает сначала ресурс р, потом ресурс q, потом их одновременно освобождает. Построить сеть Петри, ГДС и исследовать на наличие/отсутствие дедлоков.

Задача 1.2

Промоделировать вычислительную систему с 3 процессами и 4 ресурсами – ВЗУ, принтер, ПЗУ, и два раздела ОЗУ. Каждый процесс может попасть в каждый раздел.

    • Процесс 1 запрашивает ВЗУ и принтер, затем их оба освобождает ,

    • Процесс 2 запрашивает ВЗУ и ПЗУ, освобождает ВЗУ, запрашивает принтер, освобождает принтер и ПЗУ.

    • Процесс 3 запрашивает принтер и ОЗУ, освобождает OЗУ, запрашивает ПЗУ, потом оба ресурса освобождает.

Исследовать на наличие/отсутствие дедлоков.

Задача 1.3

Промоделировать работу устройства дисковой памяти при наличии одного канала и трех дисководов. Запросы поступают равновероятные ко всем дисководам. Обработка запроса включает установку головки (при этом канал не требуется) и обмен данными через канал. Интервалы времени между поступлениями запросов распределены по экспоненциальному закону с v=6. Время установки головки равномерно распределено в интервале 0 - 50 мс. Время обмена данными равно 1.7 мс (за единицу времени принять 1.7 мс).
Исследовать характеристики модели: средняя и максимальная длина очереди, среднее время нахождения транзакта в системе.

Внести следующие изменения в модель и исследовать характеристики:

  • принять за единицу времени 1 мс;

  • увеличить количество дисководов до 4.

  1. Задача читатели-писатели.

Имеются про­цессы двух типов: процессы чтения и процессы записи. Все процес­сы совместно используют общий файл или переменную или элемент данных. Процессы чтения не изменяют объект в отличие от процес­сов записи. Таким образом, процессы записи должны взаимно ис­ключать все другие процессы чтения и записи, в то время как не­сколько процессов чтения могут иметь доступ к разделяемым дан­ным одновременно. Задача состоит в определении структуры управ­ления, которая не приведет к тупику и не допустит нарушения критерия взаимного исключения.

Будем считать, что количество процессов чтения, выполняющихся одновременно, ограничено величиной п. Начальное количество процессов чтения – s, процессов записи –t.

  1. Задача о производителе – потребителе.

В задаче о производителе/потребителе также присутствует сов­местно используемый объект, но в этом случае разделяемый объект точно определен и является буфером. Процесс-производитель соз­дает объекты, которые помещаются в буфер. Потребитель ждет, пока объект не будет помещен в буфер, удаляет его оттуда и исполь­зует. Позиция В представляет собой бу­фер, каждая фишка соответствует элементу данных, который про­изведен, но еще не использован.

    • Построить сеть Петри

В другом варианте задачи о производителе/потребителе исполь­зуется буфер ограниченного размера. При такой постановке задачи буфер между производителем и потребителем ограничен, т. е. имеет только п ячеек для элементов данных. Следовательно, производи­тель не может постоянно работать с той скоростью, которая ему нуж­на, а вынужден ждать, если потребитель работает медленно и бу­фер заполнен. Огра­ниченному буферу сопоставляются две позиции: В представляет количество элементов данных, которые произведены, но еще не ис­пользованы (число заполненных ячеек), В' — количество пустых ячеек в буфере.

    • Построить сеть Петри

  1. Задача об обедающих философах.

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

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

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

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

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

  2. Легко представить себе ситуацию, когда банда сговорившихся философов завладеет всеми вилками и, передавая их только в своей среде, уморит голодом всех прочих.

Построить сеть Петри и ГДС для вариантов:

  • Каждый философ может находиться в двух состояниях – думает и ест

  • Предусмотреть отсутствие ситуации с – возможности голодания отдельного философа

  • Считать, что каждый философ может находиться в трех состояниях – думает, ожидает наличия ресурсов и ест.

5. Батарея, огонь! или Задача Майхилла

(О синхронизации процессов в среде Windows)

На первый окрик: «Кто идет?» — он стал шутить,
На выстрел в воздух закричал: «Кончай дурить!»
Я чуть замешкался и, не вступая в спор,
Чинарик выплюнул — и выстрелил в упор.
В. Высоцкий

В задаче Майхилла необходимо определить, как нужно действовать стрелкам, построенным в шеренгу, чтобы одновременно открыть стрельбу, если команда «Огонь!» (или «Пли!») подается крайнему в шеренге, а обмен информацией разрешается только между соседями.

Каждый стрелок должен руководствоваться следующим набором указаний.

1. Если ты левофланговый и получил приказ «Шеренга, пли!», то запомни число 1 — свой порядковый номер — и ровно через секунду сообщи его соседу справа.

2. Если ты неправофланговый и сосед слева сообщил тебе число V, запомни число V+1 — свой порядковый номер — и ровно через секунду сообщи его соседу справа.

3. Если ты правофланговый и сосед слева сообщил тебе число n-1, то ровно через секунду ответь ему: «Готов!» и приступай к обратному счету в уме: n, n-1, n-2, ..., отсчитывая по одному числу в секунду.

4. Если ты не правофланговый и сосед справа доложил тебе: «Готов!», то ровно через секунду приступай к обратному счету в уме: V, V-1, V-2, ..., где V — твой порядковый номер, отсчитывая по одному числу в секунду. При этом, если V>1, т.е. если ты не левофланговый, то ровно через секунду после получения сообщения от соседа справа доложи: «Готов!» соседу слева.

5. Досчитав до нуля, стреляй!

  • Построить сеть Петри, синхронизирующую действия стрелков (для наглядности можно взять n = 4)

6. Расширение сетей Петри (сдерживающие дуги)

Спящий брадобрей (рандеву).

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

Когда посетитель заходит и видит парикмахера спящим, он садится в кресло и будит того. Если парикмахер занят, когда прибывает очередной посетитель и в зале есть свободные места (в зале n кресел), то посетитель садится в свободное кресло и спит до тех пор, пока парикмахер не освободится и не разбудит его.

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

  • Построить сеть Петри, описывающую процесс.

  1. Альтернативно - битовый протокол – см.файл ABP.htm.

    • Построить цветную сеть Петри.

    • Включить в сеть таймер.

8. Моделирование решения задач в многопроцессорной ЭВМ

Требуется промоделировать решение задач в двухпроцессорной ЭВМ с общей памятью, разделенной на 4 блока. Каждой задаче отводится при ее решении один блок. Интервалы времени между поступлениями задач распределены равномерно в интервале [2,14] единиц времени, время обработки порции информации подчинено экспоненциальному закону с интенсивностью v1=5 в процессоре CPU1 и с v2=2 в процессоре CPU2.
Между обработкой порций с вероятностью 0.6 возможно обращение к внешней памяти, в которой время обслуживания распределено равномерно в диапазоне [2,8]. С вероятностью 0.4 задачи оказываются решенными и покидают систему. Моделирование выполнить на отрезке времени, соответствующем решению не менее 100 задач.

  1. Исследовать характеристики модели: средняя и максимальная длина очереди, среднее время нахождения транзакта в системе.

  2. Внести следующие изменения в модель и исследовать характеристики:

    • увеличить интервал моделирования до 500 транзактов;

    • ввести генерирование транзактов по экспоненциальному закону с v=2;

    • ввести уход транзактов из системы без обслуживания, если длина очереди А1 превысит 5.

  3. Организовать в модели подсчет заявок, покинувших систему без обработки.