🗊Презентация Моделирование взаимодействия процессов

Моделирование взаимодействия процессов. Лекция 10

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

Способы реализации параллельных вычислений Каждый вычислительный процесс может быть реализован: в виде отдельного процесса операционной системы,  в виде отдельного потока выполнения внутри одного процесса ОС

Способы реализации параллельных вычислений Параллельные программы могут физически исполняться: последовательно на единственном процессоре — перемежая по очереди шаги выполнения каждого вычислительного процесса; параллельно с выделением каждому вычислительному процессу одного или нескольких процессорных ядер

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

Моделирование сетями Петри Сети Петри, изначально созданные для моделирования динамических дискретных систем, являются одним из наиболее удобных способов описания асинхронного выполнения параллельных вычислительных процессов

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

//программа, вычисляющая Y! и //произведение всех чётных чисел Y!! cin >> Y; X1=1; X2=1; while (Y>0) { if (Y % 2 ==0) X1 *= Y; X2 *= Y--; } cout << X1 << “\t” << X2;

cin >> Y; X1=1; X2=1; Y>0 Y % 2 ==0 X1 *= Y; X2 *= Y--; cout << X1 << “\t” << X2;

В сети Петри, моделирующей блок-схему, узлы блок-схемы представляются переходами сети Петри, а дуги блок-схемы – позициями сети Петри Фишка в сети Петри представляет счетчик команд блок-схемы

Параллельная система может строиться несколькими способами Один из способов состоит в простом объединении процессов, без взаимодействия во время их одновременного выполнения Однако, такой способ введения параллелизма имеет низкое практическое значение

Моделирование взаимодействия процессов Поэтому далее будем рассматривать системы процессов, допускающие взаимодействие процессов во время их параллельного выполнения Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей памяти; посредством передачи сообщения различных видов Необходимо уметь моделировать различные механизмы синхронизации процессов

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

Например, возможна следующая последовательность: Процесс P1 считывает значение x из разделяемого объекта; Процесс P2 считывает значение х из разделяемого объекта; Процесс P1 вычисляет новое значение x’ = f(x); Процесс P2 вычисляет новое значение x’’ = g(x); Процесс P1 записывает x’ в разделяемый объект; Процесс P2 записывает x’’ в разделяемый объект, уничтожая значение x’ Результат вычисления процесса P1 потерян

Критическая секция Для решения подобных проблем используется метод взаимного исключения, основанный на понятии критическая секция Критическая секция – это участок кода процесса, на котором он осуществляет доступ к разделяемому объекту данных

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

Моделирование взаимного исключения

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

Моделирование буфера обмена

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

Проблема тупика В задаче об обедающих философах возможна ситуация, в которой каждый философ возьмет вилку слева, а затем будет ждать, когда освободится вилка с правой стороны Так они будут ждать, пока не умрут от голода Тем самым, это состояние системы «обедающие философы» является тупиковым

Решение проблемы тупика Проблема тупика в этой системе может быть решена путем следующей модификации ее правил поведения Пусть философ при переходе из состояния размышления в состояние приема пищи берет одновременно обе вилки (слева и справа), если они свободны

Моделирование разрешения тупиковой ситуации

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

Свойство ограниченности Позиция сети Петри c начальной разметкой является -ограниченной, если для любой достижимой разметки Сеть Петри ограниченна, если все ее позиции ограниченны Требование ограниченности естественно возникает, если интерпретировать позиции как буферы накопления данных, либо сигналов

Свойство безопасности Позиция сети Петри c начальной разметкой является безопасной, если она является 1-ограниченной Сеть Петри безопасна, если безопасны все позиции сети Требование безопасности актуально при моделировании аппаратных систем, когда каждый переход нужно реализовать одним триггером

Свойство консервативности Сеть Петри c начальной разметкой является сохраняющей, если для любой достижимой разметки справедливо следующее равенство:

Уровни активности переходов Тупик в сети Петри – один или множество переходов, которые не могут быть запущены Определим для сети Петри с начальной разметкой следующие уровни активности переходов Уровень 0: Переход обладает активностью уровня 0 и называется мёртвым, если он никогда не может быть запущен; такой переход может быть исключен из сети

Уровни активности переходов Уровень 1: Переход обладает активностью уровня 1 и называется потенциально живым, если существует такая разметка , что разрешён в Уровень 2: Переход обладает активностью уровня 2 и называется живым, если для всякой разметки переход является потенциально живым для сети Петри c начальной разметкой Сеть Петри называется живой, если все её переходы являются живыми