 |
Моделирование параллельных процессов сетями Петри: задача о взаимном исключении, задача о чтении-записи.
|
|
|
|
1. При работе параллельных процессов с общими данными возникает необходимость взаимоисключать одновременный доступ процессов к данным. При этом участки программ процессов для работы с разделяемыми данными образуют критические области (ресурсы).
В общем виде: необходимо согласовать работу n≥2 параллельных процессов при использовании некоторого критического ресурса таким образом, чтобы удовлетворять следующим требованиям:
- одновременно внутри критической области должно находиться не более одного процесса;
- критические области не должны иметь приоритета в отношении друг друга;
- остановка какого-либо процесса вне его критической области не должно влиять на дальнейшую работу процессов по использованию критического ресурса;
- решение о вхождении процессов в их критическую область при одинаковом времени поступления запросов на такое вхождение и равноприоритетности процессов не откладывается на неопределенное время, а является конечным по времени;
- относительные скорости развития процессов неизвестны и непроизвольны;
- любой процесс может переходить в любое состояние, отличное от активного, вне пределов совей критической области;
- освобождение критического ресурса и выход из критической области должны быть проведены процессом, использующим критический ресурс за конечное время.
Если позиция res маркирована, то семафор открыт; если не маркирована, то закрыт. Позиция idle и cr определяют состояния процессов: если idle маркирован меткой с цветом x, то процесс с индексом x находится вне критической области; если позиция cr маркирована меткой с цветом x, то процесс с индексом x находится в своей критической области.
|
|
|
2. Имеются процессы двух типов: процессы чтения и процессы записи. Все процессы совместно используют общий элемент данных. Процессы чтения не изменяют элемент данных в отличие от процессов записи. Таким образом, процессы записи должны взаимно исключать все другие процессы записи и чтения. При этом несколько процессов чтения могут иметь доступ к разделяемым данным одновременно. Задача состоит в определении структуры управления, которая не приведет к тупику и не допустит нарушения механизма взаимного исключения.
Пусть имеется s процессов чтения и t процессов записи, а количество работающих процессов чтения ограничено n.
В этой сети позиция «чтение» представляет количество одновременно работающих процессов чтения. При инициализации каждого процесса чтения в эту позицию добавляется фишка, а по окончанию процесса фишка удаляется из нее. С помощью позиции G реализуется ограничение на количество одновременно работающих процессов чтения, а также – разрешение на запуск процесса записи (в начальный момент она содержит n фишек). Инициализация процесса записи возможно, если в позиции G находится n фишек (то есть ни один из процессов не работает). В результате запуска такого процесса из позиции G удаляются все n фишек, тем самым блокируется возможность запуска для любого другого процесса. По окончании работы процесса записи n фишек возвращается в позицию G.
Билет 13.
Моделирование параллельных процессов сетями Петри: задача о производителе-потребителе.
В этой задаче присутствует разделяемый объект – буфер, посредством которого реализуется взаимодействие через асинхронную передачу сообщений.
Процесс-производитель создает сообщения, которые помещаются в буфер. Потребитель ждет, пока сообщение не будет помещено в буфер, извлекает его оттуда и использует.
В другом варианте этой задачи несколько производителей порождают сообщения, помещаемые в общий буфер для нескольких потребителей. Сеть Петри такая же, только для представления s производителей и t потребителей используются s фишек в начальной позиции процесса-производителя и t фишек в начальной позиции процесса-потребителя.
|
|
|
Еще в одном варианте задачи используется буфер ограниченного размера, имеющий n ячеек для временного хранения сообщений. Здесь возможна ситуация, когда производитель будет вынужден ждать, если потребитель работает медленно и буфер заполнен.
Ограниченному буферу сопоставляются две позиции: B представляет количество сообщений, которые произведены, но еще не использованы (число заполненных ячеек), и B’ – количество пустых ячеек в буфере. Первоначально B’ имеет n фишек, а B фишек не имеет. Если буфер заполнен, то B’ фишек не имеет, а B имеет n фишек. Если теперь производитель пытается поместить еще одно сообщение в буфер, то он будет остановлен, так как в B’ нет фишек.
Билет 14.
2. Системы массового обслуживания: основные понятия. Примеры.
СМО – система, которая производит обслуживание поступающих в нее требований.
Требование (заявка) – запрос на обслуживание.
Входящий поток требований – совокупность требований, поступающих в СМО.
Время обслуживания – период времени, в течение которого обслуживается требование.
Математическая модель СМО – совокупность математических выражений, описывающих входящий поток требований, процесс обслуживания и их взаимосвязь.
Примеры:
1. Телефонная станция, связанная с большим числом абонентов. Телефонистки станции по мере поступления вызовов соединяли телефонные номера между собой.
2. Система обработки информации содержит мультиплексный канал и несколько ЭВМ. Сигналы от датчиков поступают на мультиплексорный канал, где буферизуются и предварительно обрабатываются. Затем поступают в ту ЭВМ, где очередь минимальна.
3. Система скорой помощи представляет собой пункт, некоторое количество врачей, машин. Пункт работает по требованию.
Билет 15.
1. Понятия факторного пространства и плана. Полный факторный эксперимент, частичные факторные эксперименты.
Факторное пространство – пространство, координатные оси которого соответствуют значениям факторов.
|
|
|
Факторы – независимые переменные (входные параметры), которые варьируются при проведении эксперимента, они изменяются целенаправленно.
План эксперимента – совокупность данных, определяющих количество, условия и порядок реализации опытов.
Полный факторный эксперимент – совокупность нескольких измерений, удовлетворяющих следующим условиям:
· Количество измерений составляет 2n, где n – количество факторов.
· Каждый фактор принимает только два значения – верхнее и нижнее.
· В процессе измерения верхние и нижние значения факторов комбинируются во всех возможных сочетаниях.
(ПФЭ – эксперимент, в котором реализуются все возможные сочетания уровней факторов)
Частичный факторный эксперимент – эксперимент, в котором взаимное влияние всех факторов считают отсутствующим или их эффектом можно пренебречь.
Планы ЧФЭ:
1. Рандомизированный план предлагает выбор сочетаний уровней для каждого прогона случайным образом.
2. Латинский план (латинский квадрат) используется в том случае, когда производится эксперимент с одним первичным фактором и несколькими вторичными.
3. Эксперимент с изменениями факторов по одному. Один из факторов «проходит» все уровни, а остальные факторы остаются постоянными.
4. Дробный ФЭ. Каждый фактор имеет только два уровня – верхний и нижний, поэтому общее число вариантов эксперимента N=2k, k – число факторов.
|
|
|
