ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ. Теория вычислительных процессов
 Скачать 2.17 Mb.
|
|
Условные критические участки Предположим, например, что один процесс изменяет некоторую переменную с целью, чтобы другой процесс считывал ее новое значение. Второй процесс не должен считывать значения переменной до тех пор, пока оно не будет изменено. Аналогично, первый процесс не должен изменять значение переменной до тех пор, пока все остальные процессы не считают ее предыдущие значения. Для решения этой проблемы предложено удобное средство, называемое условным критическим участком. Он имеет вид: with общперем when условие dо критический участок. При входе в критический участок проверяется значение условия. Если оно истинно, критический участок исполняется как обычно, но если условие ложно, данный вход в критический участок задерживается, чтобы позволить другим процессам войти в свои критические участки и изменить общую переменную. По завершении каждого такого изменения происходит перепроверка условия. Если оно стало истинным, отложенному процессу позволяют продолжать исполнение своего критического участка; в противном случае процесс вновь откладывается. Если можно запустить более чем один из приостановленных процессов, выбор между ними произвольный. Мониторы Своим возникновением и развитием мониторы обязаны понятию класса. Основной идеей является то, что все осмысленные операции над данными (включая их инициализацию) должны быть собраны вместе с описанием структуры и типа самих данных; активизация этих операций должна происходить при вызове процедуры всякий раз, когда этого требуют процессы, совместно использующие данные. Важной характеристикой монитора является то, что одновременно может быть активным только одно из его процедурных тел; даже когда два процесса одновременно делают вызов процедуры (одной и той же или двух различных), один из вызовов («ждет») откладывается до завершения другого. Таким образом, тела процедур ведут себя как критические участки, защищенные одним и тем же семафором. Приведем пример очень простого монитора, ведущего себя как счетчиковая переменная. В обозначениях языкаPASCAL он имеет вид Пример 3.31. 1 monitor счет; 2 vаr n: integer 3 рrocedure* вверх; begin n := n + 1 еnd; 4 рrocedure* вниз; when > 0 dо begin n := n - 1 еnd; 5 function* приземл.Вооlеаn;begin приземл:= (n = 0) еnd; 6 begin n := 0; 7 ...; 8 if n ≠1 then рrint(n) 9 еnd Строка 1 описывает монитор с именем счет. Строка 2 описывает локальную для монитора общую переменную n. Она доступна только внутри самого монитора. Строки 3 - 5 описывают три процедуры и их тела. Звездочки обеспечивают вызов этих процедур из программы, использующей монитор. Строка 6 здесь начинается исполнение монитора. Строка 7 три жирные точки обозначают внутреннее предложение, соответствующее блоку, который будет использовать монитор. Строка 8 при выходе из использующего блока печатается конечное значение n (если оно ненулевое). Новый экземпляр монитора может быть описан локальным для блока Р: instanсе ракетa: счет; Р. Внутри блока Р можно вызывать помеченные звездочками процедуры, используя команды: ракета.вверх;... ракета.вниз;. ..;, if ракета.приземл then... Непомеченная же процедура или такая переменная, как n,недостижимы из Р. Свойственное мониторам взаимное исключение позволяет вызывать процедуру монитора любому числу процессов внутри Р без взаимного влияния при изменении n. Заметим, что попытка вызватьракета.вниз при n = 0 будет отложена до тех пор, пока некоторый другой процесс внутри Р не вызовет ракета.вверх. Это гарантирует, что значение n никогда не станет отрицательным. Неэффективность повторяющейся проверки входных условий привела к появлению мониторов с более сложной схемой явного ожидания и явной подачей сигнала о возобновлении ожидающего процесса. Эти схемы даже позволяют приостанавливаться процедурному вызову в процессе его исполнения под воздействием автоматически возникающего исключения до того момента, когда некоторый последующий вызов процедуры другим процессом подаст сигнал о возобновлении приостановленного процесса. Таким путем можно эффективно реализовать множество оригинальных способов планирования, которые реализуются программой-планировщиком. Так как в мониторе ожидающих процессов может быть несколько, простой порядок обслуживания очереди состоящий в том, что освобождается процесс, ожидающий дольше всех, гарантирует, что ни один из обратившихся процессов не будет задержан на неопределенное время. Модели параллельных вычислений Параллельное программирование представляет дополнительные источники сложности - необходимо явно управлять работой тысяч процессоров, координировать миллионы межпроцессорных взаимодействий. Для того решить задачу на параллельном компьютере, необходимо распределить вычисления между процессорами системы, так чтобы каждый процессор был занят решением части задачи. Кроме того, желательно, чтобы как можно меньший объем данных пересылался между процессорами, поскольку коммуникации значительно больше медленные операции, чем вычисления. Часто, возникают конфликты между степенью распараллеливания и объемом коммуникаций, то есть чем между большим числом процессоров распределена задача, тем больший объем данных необходимо пересылать между ними. Среда параллельного программирования должна обеспечивать адекватное управление распределением и коммуникациями данных. Из-за сложности параллельных компьютеров и их существенного отличия от традиционных однопроцессорных компьютеров нельзя просто воспользоваться традиционными языками программирования и ожидать получения хорошей производительности. Рассмотрим основные модели параллельного программирования, их абстракции адекватные и полезные в параллельном программировании.
Обмен сообщениями В этой модели программы, возможно различные, написанные на традиционном последовательном языке исполняются процессорами компьютера. Каждая программа имеют доступ к памяти исполняющего ее процессора. Программы обмениваются между собой данными, используя подпрограммы приема/передачи данных некоторой коммуникационной системы. На сегодняшний деньмодель обмен сообщениями является наиболее широко используемой моделью параллельного программирования. Программы этой модели, подобно программам модели процесс/канал, создают множество процессов, с каждым из которых ассоциированы локальные данные. Каждый процесс идентифицируется уникальным именем. Процессы взаимодействуют, посылая и получая сообщения. В этом отношение модель обмен сообщениямиявляется разновидностью модели процесс/канал и отличается только механизмом, используемым при передаче данных. Модель не накладывает ограничений ни на динамическое создание процессов, ни на выполнение нескольких процессов одним процессором, ни на использование разных программ для разных процессов. Просто, формальные описания систем обмена сообщениями не рассматривают вопросы, связанные с манипулированием процессами, Однако, при реализации таких систем приходится принимать какое-либо решение в этом отношении. На практике сложилось так, что большинство систем обмена сообщениями при запуске параллельной программы создает фиксированное число идентичных процессов и не позволяет создавать и разрушать процессы в течение работы программы. В таких системах каждый процесс выполняет одну и ту же программу (параметризованную относительно идентификатора либо процесса, либо процессора), но работает с разными данными. Параллелизм данных В этой модели единственная программа задает распределение данных между всеми процессорами компьютера и операции над ними. Распределяемыми данными обычно являются массивы. Как правило, языки программирования, поддерживающие данную модель, допускают операции над массивами, позволяют использовать в выражениях целые массивы, вырезки из массивов. Распараллеливание операций над массивами, циклов обработки массивов позволяет увеличить производительность программы. Компилятор отвечает за генерацию кода, осуществляющего распределение элементов массивов и вычислений между процессорами. Каждый процессор отвечает за то подмножество элементов массива, которое расположено в его локальной памяти. Программы с параллелизмом данных могут быть оттранслированы и исполнены как на MIMD, так и на SIMD компьютерах. Модель также является часто используемой моделью параллельного программирования. Название модели происходит оттого, что она эксплуатирует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных. Например, «умножить все элементы массива M на значение x», или «снизить цену автомобилей со сроком эксплуатации более 5-ти лет». Программа с параллелизмом данныхсостоит из последовательностей подобных операций. Поскольку операции над каждым элементом данных можно рассматривать как независимые процессы, то степень детализации таких вычислений очень велика, а понятие «локальности» (распределения по процессам) данных отсутствует. Следовательно, компиляторы языков с параллелизмом данных часто требуют, чтобы программист предоставил информацию относительно того, как данные должны быть распределены между процессорами, другими словами, как программа должны быть разбита на процессы. Модель общей памяти В этой модели все процессы совместно используют общее адресное пространство. Процессы асинхронно обращаются к общей памяти как с запросами на чтение, так и с запросами на запись, что создает проблемы при выборе момента, когда можно будет поместить данные в память, когда можно будет удалить их. Для управления доступом к общей памяти используются стандартные механизмы синхронизации - семафоры и блокировки процессов. В модели все процессы совместно используют общее адресное пространство, к которому они асинхронно обращаются с запросами на чтение и запись. В таких моделях для управления доступом к общей памяти используются всевозможные механизмы синхронизации типа семафоров и блокировок процессов. Преимущество этой модели с точки зрения программирования состоит в том, что понятие собственности данных (монопольного владения данными) отсутствует, следовательно, не нужно явно задавать обмен данными между производителями и потребителями. Эта модель, с одной стороны, упрощает разработку программы, но, с другой стороны, затрудняет понимание и управление локальностью данных, написание детерминированных программ. В основном модель используется при программировании для архитектур с общедоступной памятью.
Контрольные вопросы и задания 1.Расскажите об общем понятии процесса как математической абстракции взаимодействия системы и ее окружения. 2.Покажите, как с помощью механизма рекурсии можно описывать протяженные во времени и бесконечные процессы. 3.Объясните, как можно представить поведение процесса в виде протокола последовательности его действий. 4.Какие свойства протоколов и операции над ними Вам известны? 5.Каковы правила, помогающие получить реализации процессов, сопровожденные доказательством их соответствия исходным спецификациям? 6.Каковы способы построения из отдельных процессов систем, компоненты которых взаимодействуют друг с другом и с общим окружением? 7.Как можно избежать многих традиционных для параллельного программирования проблем, таких, как взаимное влияние и взаимное исключение, прерывания, зацикливание, многопоточная обработка и т. п.? 8.Как следует вводить понятие параллелизма? 9.Изложите суть проблем, возникающих в модели системы, описанной притчей о пяти обедающих философах. 10. Расскажите о понятии взаимодействия как об особом способе взаимосвязи двух процессов. 11. Каким образом достигается синхронизация и буферизация взаимодействия? 12. Расскажите о понятии подчинения и подчиненного процесса. 13. Объясните, каким образом совокупность обычных операторов последовательного программирования может быть взята за основу структуры последовательных взаимодействующих процессов. 14. Как известные объекты структурного и объектного программирования, такие, как мониторы, классы, модули, критические участки и заурядные подпрограммы, могут реализовываться в виде последовательных взаимодействующих процессов? 15. Как с помощью модели последовательных взаимодействующих процессов доказывается правильность при проектировании и разработке вычислительных систем? 16. Расскажите о структуре и способе построения системы, в которой ограниченное число физических ресурсов, таких, как диски и печатающие устройства, разделено между большим количеством процессов с переменной потребностью в этих ресурсах. 17. Дайте понятие виртуального ресурса. 18. Какова роль семафоров и мониторов, реальных и виртуальных процессов? 19. Расскажите о моделях параллельных вычислений и их свойствах. 20. Объясните, в чем заключаются недостатки модели общей памяти и как их следует преодолевать. СЕТИ ПЕТРИ Введение в сети Петри Сети Петри это инструмент для математического моделирования и исследования сложных систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы. Эта информация может использоваться для оценки моделируемой системы и выработки предложений по ее усовершенствованию. Впервые сети Петри предложил немецкий математик Карл Адам Петри. Сети Петри предназначены для моделирования систем, которые состоят из множества взаимодействующих друг с другом компонент. При этом компонента сама может быть системой. Действиям различных компонент системы присущ параллелизм. Примерами таких систем могут служить вычислительные системы, в том числе и параллельные, компьютерные сети, программные системы, обеспечивающие их функционирование, а также экономические системы, системы управления дорожным движением, химические системы, и т. д. В одном из подходов к проектированию и анализу систем сети Петри используются, как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект снова моделируется и анализируется. Цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху. Другой подход предполагает построение проекта сразу в виде сети Петри. Методы анализа применяются только для создания проекта, не содержащего ошибок. Затем сеть Петри преобразуется в реальную рабочую систему. В первом случае необходима разработка методов моделирования систем сетями Петри, а во втором случае должны быть разработаны методы реализации сетей Петри системами. |