Теория вычислительных процессов Задачи синхронизации Преподаватель: Веретельникова Евгения Леонидовна 1

Механизмы синхронизации процессов Для более глубокого понимания существа использования аппарата сетей Петри при описании совместной работы совокупности параллельных взаимодействующих процессов рассмотрим основные типы взаимодействия и синхронизации процессов. Взаимодействие процессов требует распределения ресурсов между ними. Чтобы система работала правильно распределением ресурсов необходимо управлять. Это управление в основном сводится к задачам синхронизации взаимодействия процессов. При этом изучается ряд задач синхронизации ставших классическими: 2

Механизмы синхронизации процессов задача о взаимном исключении; задача о производителе/потребителе; задача об обедающих мудрецах; задача о чтении/записи; P - и V- операции над семафорами. Другие механизмы синхронизации процессов включают решение перечисленных задач. Знание этих задач и приобретение навыков их применения позволяет успешно справляться с весьма не простым делом описания функционирования систем сетями Петри. 3

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

Задача о взаимном исключении Возможна следующая последовательность: 1. Первый процесс считывает значение х из разделяемого объекта; 2. Второй процесс считывает значение х из разделяемого объекта; 3. Первый процесс вычисляет новое значение х' = f(x); 4. Второй процесс вычисляет новое значение х" = g(x); 5. Первый процесс записывает х' в разделяемый объект; 6. Второй процесс записывает х" в разделяемый объект, уничтожая учение х'. Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им должно было быть либо f (g (x)), либо g ( f(x)). ( Представьте себе, что g(x) – «снять со счета х 1000 долл.», f (х) – «поместить на счет х 1000 долл.», а процессы 1 и 2 – банковские операции.) 5

Задача о взаимном исключении Для предотвращения проблем такого рода необходимо обеспечить механизм взаимного исключения. Взаимное исключение – это метод создания таких программ, что одновременно не более чем один процесс имеет доступ к разделяемому объекту данных. Участок кода, в котором осуществляется доступ к разделяемому объекту и который требует защиты от вмешательства других процессов, называется критической секцией. Идея состоит в том, что когда процесс готов выполнить свою критическую секцию, он сначала ждет, пока другой процесс не выполнит свою соб- ственную критическую секцию. Затем он «блокирует» доступ к критической секции, не давая возможности никакому другому процессу войти в свою критическую секцию. Он входит в критическую секцию, выполняет ее и, выйдя из нее, освобождает ее для доступа со стороны других процессов. 6

Задача о взаимном исключении Эта задача может быть решена такой сетью Петри 7 Рис Взаимное исключение

Задача о взаимном исключении Позиция т представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в р 1 или в р 2, соответственно, свидетельствующую о желании попасть в критическую, а также должна существовать фишка в m, дающая разрешение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t 1 и t 2 вступят в конфликт, и только один из них сможет запуститься. Запуск t 1 запретит переход t 2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию m. 8

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

Задача о производителе/потребителе 10 Рис Задача о производителе/потребителе

Задача о производителе/потребителе Один из вариантов этой задачи – это задача о нескольких производителях/нескольких потребителях. В этом случае несколько производителей порождают элементы данных, помещаемые в общий буфер, для нескольких потребителей. На рис представлено решение этой задачи в виде сети Петри. Эта сеть совпадает с сетью на рис. 2.14, за исключением того, что для представления s производителей и t потребителей мы начали выполнение сети с s фишками в начальной позиции процесса-производителя и t фишками в начальной позиции процесса-потребителя. 11

Задача о производителе/потребителе 12 Рис Много производителей / потребителей

Задача о производителе/потребителе Таким образом мы заставляем s производителей и t потребителей, реализуемых реентерабельными совместно используемыми программами. Альтернативой было бы дублирование программного кода для процессов производителя и потребителя, однако результатом этого при том же самом поведении была бы гораздо большая сеть. В другом варианте задачи о производителе /потре- бителе используется буфер ограниченного размера. При такой постановке задачи буфер между произво- дителем и потребителем ограничен, т.е. имеет только n ячеек для элементов данных. 13

Задача о производителе/потребителе 14 Рис Ограниченный буфер

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

Задача об обедающих мудрецах Задача об обедающих мудрецах была предложена Дейкстрой и связана с пятью мудрецами, которые попеременно то думали, то ели. Мудрецы сидят за большим круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Однако для приема китайской пищи необходимо две палочки, следовательно, каждый мудрец должен взять палочку слева и палочку справа: проблема, конечно, заключается в том, что если все мудрецы возьмут палочки слева и затем будут ждать, когда освободятся палочки с правой стороны, то они будут ждать вечно и умрут от голода (состояние тупика). 16

Задача об обедающих мудрецах 17 Рис Задача об обедающих мудрецах

Задача об обедающих мудрецах На рис показано решение этой задачи с помощью сети Петри. Позиции С 1,..., С 5 представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной маркировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями M i и E i для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел состояния размышления в состояние принятия пищи, обе палочки (слева и справа) должны быть свободны. Это легко моделируется сетью Петри. 18

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

Задача о чтении/записи Ниже иллюстрируется решение задачи в том случае, когда количество процессов чтения ограничено величиной n. Если в системе количество процессов чтения не ограничено, то только n процессов могут выполняться в одно и то же время. 20 Рис Задача о чтении/записи

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

Р и V операции над семафорами Одним из распространенных механизмов синхронизации процессов являются Р - и V - операции над семафорами. Семафор это переменная, которая может принимать только неотрицательные целые значения. V - операция увеличивает значение на единицу, а Р-операция уменьшает его на единицу. Р-операция может выполняться только в том случае, когда полу- ченное значение семафора остается неотрицательным. Таким образом, если значение семафора равно 0, то Р-операция долж- на ждать, пока какой-нибудь другой процесс не выполнит V - операцию. Р- и V -операции определены как примитивные, то есть никакая другая операция не может изменять значения семафора одновременно с ними. На рис.5.8 показано как такие операции моделируются сетью Петри. Каждый семафор модели- руется позицией, количество меток r в позиции показывает значение семафора. Р-операции используют позицию семафора в качестве входа, а V-операции в качестве выхода. 22

Р и V операции над семафорами Рис Операции над семафором. Механизм семафоров 23

Химические системы Химические системы – другой пример систем, которые могут быть промоделированы сетями Петри. Химические уравнения моделируются переходами; вещества, участвующие в реакции, – позициями. Количество фишек в позиции указывает на количество данного вещества в системе. Например, сеть |Петри на рис представляет окислительно-восстанови- тельную реакцию между щавелевой кислотой и пероксидом водорода, в результате которой получаются вода и диоксид углерода. Т.е. она представляет два химических уравнения: Н 2 С 2 О 4 2СО 2 + 2Н + + 2е –.2е – + 2Н + + Н 2 О 2 2Н 2 О. 24

Химические системы Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н 2 + С 2 Н 4 С 2 Н 6 ) только в присутствии платины. Это также отражено на рис Рис Модели химических реакций

Расширенные и ограниченные сети Петри Можно представить и реакции катализа. Соединение водорода и этилена образует этан (Н 2 + С 2 Н 4 С 2 Н 6 ) только в присутствии платины. Это также отражено на рис Рис Модели химических реакций