Модель общей памяти

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

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

Основные выводы и результаты  Даны формальные описания понятия «процесс» и его реализации, введены соответствующие обозначения, сформулированы законы, характеризующие разнообразные свойства процессов.  Определены понятия «протокола» и «спецификации» процесса, а также их свойства и действия с ними.  Рассмотрены системы помеченных параллельных взаимодействующих процессов, сформулированы законы и реализация различных видов взаимодействия.  Приведена и всесторонне исследована одна из трактовок задачи предложенной Дейкстрой об обедающих философах. На примере данной задачи обсуждены основные проблемы параллельных вычислений, такие как «тупик», «взаимное исключение», «бесконечный перехват» и другие, а также меры исключения этих проблем при проектировании соответствующих программ.  Исследован один специальный класс событий, называемых взаимодействиями, которые состоят в передаче сообщений. Рассмотрены варианты взаимодействий: ввод – вывод, чередование, подчинение.  Подробно рассмотрена проблема разделяемых ресурсов. Произведено сравнение и выявлены достоинства и недостатки различных видов организации разделения ресурсов, в том числе и кратных. Даны рекомендации для планирования ресурсов.  Рассмотрены основные способы взаимодействия процессов (обмен сообщениями, обмен через общую память, прямой доступ к удаленной памяти), наиболее желательные признаки параллельных алгоритмов и программ.  Рассмотрена техника многопоточной обработки и организации условных критических участков. Исследованы разновидности «мониторов» - программ со сложной схемой явного ожидания и явной подачей сигнала о возобновлении ожидающего процесса. С помощью мониторов можно эффективно реализовать множество оригинальных способов планирования.  Дан анализ основных моделей параллельных вычислений, их абстракций адекватных и полезных в параллельном программировании:процесс/канал, обмен сообщениями, параллелизм данных, модель общей памяти.

Контрольные вопросы и задания

1.Расскажите об общем понятии процесса как математической абстракции взаимодействия системы и ее окружения.

2.Покажите, как с помощью механизма рекурсии можно описывать протяженные во времени и бесконечные процессы.

3.Объясните, как можно представить поведение процесса в виде протокола последовательности его действий.

4.Какие свойства протоколов и операции над ними Вам известны?

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

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

7.Как можно избежать многих традиционных для параллельного программирования проблем, таких, как взаимное влияние и взаимное исключение, прерывания, зацикливание, многопоточная обработка и т. п.?

8.Как следует вводить понятие параллелизма?

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

10. Расскажите о понятии взаимодействия как об особом способе взаимосвязи двух процессов.

11. Каким образом достигается синхронизация и буферизация взаимодействия?

12. Расскажите о понятии подчинения и подчиненного процесса.

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

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

15. Как с помощью модели последовательных взаимодействующих процессов доказывается правильность при проектировании и разработке вычислительных систем?

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

17. Дайте понятие виртуального ресурса.

18. Какова роль семафоров и мониторов, реальных и виртуальных процессов?

19. Расскажите о моделях параллельных вычислений и их свойствах.

20. Объясните, в чем заключаются недостатки модели общей памяти и как их следует преодолевать.

СЕТИ ПЕТРИ

Введение в сети Петри

Сети Петри это инструмент для математического моделирования и исследования сложных систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы. Эта информация может использоваться для оценки моделируемой системы и выработки предложений по ее усовершенствованию. Впервые сети Петри предложил немецкий математик Карл Адам Петри.

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

В одном из подходов к проектированию и анализу систем сети Петри используются, как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект снова моделируется и анализируется. Цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху.

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

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

Основные определения