рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Then begin

Then begin - раздел Программирование, Математические основы программирования. Теория схем программ. Семантическая теория программ X1:=X1*y; End; X2:=X2*y; Y:=Y-1;...

X1:=X1*Y;

end;

X2:=X2*Y;

Y:=Y-1;

end;

write(X1);

write(X2);

endРисунок 4.5.

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

Стандартный способ представления структуры программы и потока управления в ней - это блок-схемы, которые в свою очередь могут быть представлены сетями Петри. Блок-схема программы состоит из узлов двух типов (принятия решения, обозначаемых ромбами, и вычисления, обозначаемых прямоугольниками) и дуг между ними. Блок-схема программы изображена на рисунке 4.5, где блоки:

a: read(Y); X1:=1; X2:=1;

b: Y>0

c: mod(Y,2)=0

d: X1:=X1*Y;

e: X2:=X2*Y; Y:=Y-1;

f: write(X1); write(X2);

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

Рисунок 4.6.

 

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

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

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

Существуют различные виды взаимодействия (синхронизации) процессов, в том числе: взаимодействие посредством общей памяти; - посредством передачи сообщения различных видов.

Таким образом, для моделирования сетями Петри параллельных систем процессов, помимо последовательных процессов, необходимо уметь моделировать различные механизмы взаимодействия (синхронизации) процессов.

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

4.3.3.3. Задача о взаимном исключении.

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

1. Процесс P1 считывает значение х из разделяемого объекта;

2. Процесс P2 считывает значение х из разделяемого объекта;

3. Процесс P1 вычисляет новое значение х'=f(x);

4. Процесс P2 вычисляет новое значение х"=g(x);

5. Процесс P1 записывает х' в разделяемый объект;

6. Процесс P2 записывает х" в разделяемый объект, уничтожая значение х

Результат вычисления процесса P1 потерян.

 
 

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

Рисунок 4.7.

Следующая сеть Петри (рисунок 4.7) моделирует механизм взаимного исключения для двух процессов P1 и P2. Она легко обобщается на произвольное число процессов.

Позиция mпредставляет условие «критическая секция свободна», разрешающее вход в критическую секцию. Попытка процесса P1 (P2) войти в критическую секцию осуществляется после помещения фишки в его позицию s1 (s2). Такая попытка может увенчаться успехом, если в позиции m содержится фишка. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск t1 запретит запуск перехода t2, вынуждая процесс P2 ждать, пока процесс P1 выйдет из своей критической секции, и возвратит фишку обратно в позицию m.

4.3.3.4. Задача о производителе/потребителе.

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

Позиция B представляет буфер, каждая фишка соответствует сообщению, которое произведено, но еще не использовано.

Рисунок 4.8.

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

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

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

В этой сети Петри позиция пi, i Î {1,2,3,4,5}, представляет условие «i-тая вилка свободна». В начальной маркировке каждая из этих позиций имеет фишку. Каждому философу i Î {1,2,3,4,5} соответствует две позиции: позиция дi– представляющая условие «i-тый философ думает»; и позиция еi – представляющая условие «i-тый философ ест». В начальной маркировке все позиции дi содержат фишку, а все позиции еi пусты.

 
 

Каждому философу i Î {1,2,3,4,5} также соответствует два перехода: переход начi – представляющий событие «начало приема пищи i-тым философом»; и переход завi – представляющий событие «завершение приема пищи i-тым философом».

Рисунок 4.9.

 

– Конец работы –

Эта тема принадлежит разделу:

Математические основы программирования. Теория схем программ. Семантическая теория программ

Следуя А П Ершову мы употребляем термин теоретическое программирование в качестве названия математической дисциплины изучающей синтаксические.. В настоящее время сложились следующие основные направления исследований.. Математические основы программирования Основная цель исследований развитие математического аппарата..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Then begin

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Программа как формализованное описание процесса обработки данных
Целью программирования является описание процессов обработки данных (в дальнейшем - просто процессов). Данные - это представление фактов и идей в формализованном виде, пригодном для п

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

Стандартные схемы программ
1.2.1. Базис класса стандартных схем программ Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы. Базис класса фиксирует символы, из которых строятся схем

Свойства и виды стандартных схем программ
1.3.1. Эквивалентность, тотальность, пустота, свобода ССП S в базисе В тотальна (пуста), если для любой интерпретации I базиса В программа (S, I) останавливается (зацикливает

Моделирование стандартных схем программ
1.4.1. Одноленточные автоматы Конечный одноленточный (детерминированный, односторонний) автомат обнаруживают ряд полезных качеств, используемых в теории схем программ для установлен

Рекурсивные схемы
1.5.1. Рекурсивное программирование Среди упомянутых выше методов формализации понятия вычислимой функции метод Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего

Трансляция схем программ
1.6.1. О сравнении класс сов схем. Программы для ЭВМ, будь-то программы, записанные на операторном языке, или программы на рекурсивном языке, универсальны в том смысле, что любую вычислиму

Обогащенные и структурированные схемы
1.7.1 Классы обогащенных схем Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами. Классы счетчиковых и магази

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

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

Языки формальной спецификации.
Языки и методы формальной спецификации, как средство проектирования и анализа программного обеспечения появились более сорока лет назад. За это время было немало попыток разработать как универсальн

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

Правила верификации К. Хоара.
Сформулируем правила (аксиомы) К.Хоара, которые определяют предусловия как достаточные предусловия, гарантирующие, что исполнение соответствующего оператора при успешном завершении приведет к желае

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

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

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

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

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

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги