close

Вход

Забыли?

вход по аккаунту

?

твп отчет 4 практика 3

код для вставкиСкачать
ЛАБОРАТОРНО-ПРАКТИЧЕСКАЯ РАБОТА 3
МОДЕЛИРОВАНИЕ ВЗАИМОДЕЙСТВИЯ
ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ
С ИСПОЛЬЗОВАНИЕМ СЕТЕЙ
Цель работы: приобретение навыков моделирования взаимодействия параллельных процессов с помощью сетей Петри.
Техническое обеспечение: ПЭВМ на базе Intel-80486.
Программное обеспечение: OS Windows XP.
Время выполнения: 4 часа.
1. В чем суть концепции параллелизма вычислительных про-
цессов?
Принцип организации вычислительного процесса, сформулированный фон Нейманом, называется также "управление потоком команд", поскольку стержень процесса образуется последовательностью (потоком) команд, задаваемых программой. По фон Нейману, данные занимают подчиненное положение, последовательность и способ их обработки определяется командами программы, т.е. ход выполнения вычислительного процесса определяется только потоком команд.
Довольно длительное время принцип фон Неймана предполагал единственную, как тогда казалось, архитектуру компьютера: процессор по очереди выбирает команды программы, по очереди их декодирует и также по очереди обрабатывает данные. Все строго последовательно, просто и понятно. Однако очень скоро выяснилось, что компьютерные вычисления обладают естественным параллелизмом, т.е. большая или меньшая часть команд программы может выполняться одновременно и независимо друг от друга. Вся дальнейшая история вычислительной техники развивалась в соответствии с логикой расширения параллелизма программ и компьютеров, и каждый новый шаг на этом пути предварялся теоретическим анализом.
Известный специалист по архитектуре компьютеров М.Флин (M.Flynn) обратил внимание на то, что существует всего две причины, порождающие вычислительный параллелизм - независимость потоков команд, одновременно существующих в системе, и несвязанность данных, обрабатываемых в одном потоке команд. Если первая основа параллелизма вычислительного процесса достаточно известна (это "обычное" мультипроцессирование) и не требует особых комментариев, то на параллелизме данных следует остановиться более подробно, поскольку в большинстве случаев он существует скрыто от программистов и используется ограниченным кругом профессионалов. Простейшим примером параллелизма данных является последовательность из двух команд:
A=B+C;
D=ExF;
Если строго следовать принципу фон Неймана, то вторая операция может быть запущена на исполнение только после завершения первой операции. Однако очевидно, что порядок выполнения этих команд не имеет никакого значения - операнды A, B и C первой команды никак не связаны с операндами D, E и F второй команды. Другими словами, обе операции являются параллельными именно потому, что операнды этих команд не связаны между собой. Можно привести множество примеров последовательности из трех и более команд с несвязанными данными, которые приведут к однозначному выводу: практически любая программа содержит группы операций над параллельными данными.
Итак - параллелизм верхнего уровня достигается за счет множества независимых командных потоков и реализуется с помощью многопроцессорной архитектуры;
- параллелизм нижнего уровня обязан своим существованием наличием несвязанных потоков данных и реализуется за счет конвейерной обработки различных фаз операций.
2. Какими аппаратными средствами обеспечивается эффектив-
ное использование внутреннего параллелизма задачи?
поддержка упреждающего выполнения команд на основе прогноза направления ветвления (control speculation);
поддержка выполнения по прогнозу данных (data speculation);
поддержка условного выполнения (predicated execution)
3. Какие отношения между процессами определяют правила
синхронизации?
Реализация синхронизирующих правил осуществляется с помощью механизмов (средств) синхронизации. Такие механизмы весьма многочисленны по способам реализации. Чаще всего они имеют программно-аппаратную форму реализации и основаны на использовании специальных переменных, разделяемых и глобально доступных параллельным взаимодействующим процессам. В большинстве своем механизмы синхронизации выполняют двоякую роль - обеспечивают не только способ упорядочения развития процессов (отрабатывают тип отношения следования процессов), но и взаимодействие между процессами, выражающееся в передаче информации между ними.
Особенности каждого конкретного взаимодействия между двумя и более параллельными процессами определяются задачей синхронизации. Количество различных задач синхронизации неограничено. Однако некоторые из них являются типовыми. К ним относятся: взаимное исключение, производители-потребители, читатели-писатели, обедающие философы и т. д. Большинство задач в реальных ОС по согласованию параллельных процессов можно решить либо с помощью этих типовых задач, либо с помощью их модификаций.
4. Задача "взаимного исключения", ее сущность.
Взаимоисключение одновременного доступа процессов к данным необходимо применить при работе нескольких параллельных процессов с общими данными. При этом участки программ процессов для работы с разделяемыми данными образуют так называемые критические области (секции).
5. Задача "производители-потребители", ее сущность.
Общий вид постановки задачи "производитель-потреби-
тель". Необходимо согласовать работу двух процессов при одностороннем (в простейшем случае) обмене сообщениями по мере развития процессов таким образом, чтобы удовлетворить следующим требованиям:
- выполнять требования задачи взаимного исключения по отношению к критическому ресурсу - обобщенной памяти для хранения сообщения;
- учитывать состояние обобщенной области памяти, характеризующей возможность или невозможность посылки (принятия) очередного сообщения;
- попытка процесса-производителя поместить очередное сообщение в область, из которой не было считано предыдущее сообщение процессом-потребителем, должна быть блокирована.
Процесс-производитель должен быть:
либо оповещен о невозможности помещения сообщения;
либо переведен в состояние ожидания возможности поместить очередное сообщение через некоторое время в область памяти, по мере ее освобождения;
- попытка процесса-потребителя считать сообщение из области в ситуации, когда процесс-производитель не поместил туда очередного сообщения, должна быть заблокирована. Процесспотребитель должен быть:
либо оповещен о невозможности считывания сообщения;
либо переведен в состояние ожидания поступления очередного сообщения;
- если используется вариант с ожиданием изменения состояния обобщенной области для хранения сообщений, необходимо обеспечить перевод ожидающих процессов в состояние готовности всякий раз, когда изменится состояние области:
либо процесс-производитель поместит очередное сообщение в область, и оно теперь может быть считано ожидающим процессом-потребителем;
либо процесс-потребитель считал очередное сообщение из области и обеспечил возможность ожидающему процессупотребителю послать очередное сообщение.
6. Задача "читатели-писатели", ее сущность.
Существует несколько вариантов этой задачи, однако их основная структура остается неизменной.
Имеется система параллельных процессов, которые взаимодействуют друг с другом следующим образом:
- все процессы делятся на два типа: процессы-читатели и процессы-писатели. Процессы работают с общей областью памяти;
- процессы-читатели считывают, а процессы-писатели записывают информацию в общую область памяти;
- одновременно может быть несколько активных процессов-читателей;
- при записи информации область памяти рассматривается
как критический ресурс для всех процессов, то есть, если работает процесс-писатель, то он должен быть единственным активным процессом.
Задача состоит в определении структуры управления, которая не приведет к тупику и не допустит нарушения критерия взаимного исключения.
Наиболее характерная область использования этой задачи построение файловых систем.
7. Задача "обедающие философы", ее сущность.
Название и формулировка этой задачи носят несколько абстрактный характер, но такая задача синхронизации также имеет место при построении систем распределения ресурсов в составе операционной системы. В рамках этой задачи формулируются требования на синхронизацию работы процессов, которые совместно используют пересекающиеся группы ресурсов.
Рассмотрим формулировку задачи "обедающие философы" в терминологии, предложенной Э. Дейкстрой (Edsser Wybe Dijkstra).
За круглым столом расставлены пять стульев, на каждом из которых сидит определенный философ, Фi (рис. 3.1).
В центре стола - большое блюдо спагетти, а на столе лежат пять вилок В1...В5 - каждая между двумя соседними тарелками.
Каждый философ может находиться только в двух состояниях - либо он размышляет, либо ест спагетти. Начать думать философу ничто не мешает. Но чтобы начать есть, философу нужны две вилки: одна в правой руке, другая в левой. Закончив еду, философ кладет вилки слева и справа от своей тарелки и опять начинает размышлять до тех пор, пока снова не
проголодается.
8. Какие средства синхронизации предпочтительнее использо-
вать при решении каждой из вышеуказанных задач?
Объект Семафор (Semaphore)
Объект Критическая секция (Critical section)
Объект Мьютекс (Mutex)
Объект Событие (Event)
1. Разработайте сеть Петри, которая моделирует механизм взаимного исключения для процессов P1 и P2.
Дано: два процесса P1 и P2 работают с разделяемым ресурсом, используя значение х из данного разделяемого объекта. При этом процесс P1 вычисляет значение х'= f(x), а процесс P2 - значение х"= g(x), оба процесса заносят полученные значения в разделяемый объект.
П р и м е ч а н и е. Если процессы, при отсутствии синхронизации, в одно и то же время пытаются выполнить требуемые действия, то содержимое разделяемого ресурса может быть непредсказуемым. Так, если процессы P1 и P2 в одно и то же время пытаются выполнить такую последовательность действий, то могут возникнуть искажения данных.
Например, возможна следующая последовательность:
1) процесс P1 считывает значение х из разделяемого объекта;
2) процесс P2 считывает значение х из разделяемого объекта;
3) процесс P1 вычисляет новое значение х'= f(x);
4) процесс P2 вычисляет новое значение х"= g(x);
5) процесс P1 записывает х' в разделяемый объект;
6) процесс P2 записывает х" в разделяемый объект, уничтожая значение х.
Результат вычисления процесса P1 потерян.
Документ
Категория
Разное
Просмотров
59
Размер файла
22 Кб
Теги
практике, отчет, твп
1/--страниц
Пожаловаться на содержимое документа