Параллельное программирование

Содержание

Введение 3

1. Завершение процесса. Ресурсы процессов.     4
2. Декомпозиция задачи и инкапсуляция ее решения.                              10

Заключение 17

Список использованной литературы 18

 

Введение

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

 

 

1. Завершение процесса. Ресурсы процессов.

Процесс (process) — это некоторая часть (единица) работы, создаваемая операционной системой. Важно отметить, что процессы и программы — необязательно эквивалентные понятия. Программа может состоять из нескольких процессов. В некоторых ситуациях процесс может быть не связан с конкретной программой. Процессы - это артефакты операционной системы, а программы — это артефакты разработчика. Такие операционные системы, как UNIX/Linux позволяют управлять сотнями или даже тысячами параллельно загружаемых процессов.

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

Когда процесс завершается, его блок БУП разрушается, а используемое им адресное пространство и ресурсы  освобождаются. Код завершения помещается в главную таблицу процессов. Как только родительский процесс  примет этот код, соответствующая структура  таблицы процессов будет удалена. Процесс завершается, если соблюдены  следующие требования:

• все инструкции выполнены;

• процесс явным образом передает управление родительскому процессу или вызывает системную функцию, которая завершает процесс;

• сыновние процессы могут завершаться автоматически при завершении родительского процесса;

• родительский процесс посылает сигнал о завершении своих сыновних процессов;

 

Аварийное завершение процесса может произойти в случае, если процесс выполняет недопустимые действия:

• процесс требует больше памяти, чем система может ему предоставить;

• процесс пытается получить доступ к неразрешенным ресурсам;

• процесс пытается выполнить некорректную инструкцию или запрещенные вычисления;

Завершение процесса может  быть инициировано пользователем, если этот процесс является интерактивным.

Родительский процесс  несет ответственность за завершение (освобождение) своих потомков. Родительский процесс должен ожидать до тех  пор, пока не завершатся все его сыновние процессы. Если родительский процесс  выполнит считывание кода завершения сыновнего процесса, процесс-потомок  покидает систему нормально. Процесс  остается в «зомбированном» состоянии  до тех пор, пока его родитель не примет соответствующий сигнал. Если родитель никогда не примет сигнал (поскольку он уже успел сам  завершиться и выйти из системы  или не ожидал завершения сыновнего  процесса), процесс-потомок остается в «зомбированном» состоянии  до тех пор, пока процесс init (исходный системный процесс) не примет его код завершения. Большое количество «зомбированных» процессов может негативно отразиться на производительности системы.

 

Ресурсы процессов

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

Чтобы процесс получил  доступ к ресурсу, он должен сначала  сделать запрос, обратившись с  ним к операционной системе. Если ресурс свободен, операционная система  позволит процессу его использовать. После использования ресурса  процесс освобождает его, чтобы  он стал доступным для других процессов. Если ресурс недоступен, запрос отвергается, и процесс должен подождать его  освобождения. Как только ресурс станет доступным, процесс активизируется. Таков базовый подход к распределению  ресурсов между процессами. На рисунке показан граф распределения ресурсов, по которому можно понять, какие процессы удерживают ресурсы, а какие их ожидают. Так, процесс В делает запрос на ресурс 2, который удерживается процессом С. Процесс С делает запрос на ресурс 3, который удерживается процессом D.

Если удовлетворяется  сразу несколько запросов на получение  доступа к ресурсу, этот ресурс является совместно используемым,  или разделяемым . Процесс А разделяет ресурс R 1 с процессом D. Разделяемые ресурсы могут допускать параллельный доступ сразу нескольких процессов или разрешать доступ только одному процессу в течение ограниченного промежутка времени, после чего аналогичным доступом сможет воспользоваться другой процесс. Примером такого типа разделяемых ресурсов может служить процессор. Сначала процессор назначается одному процессу в течение короткого интервала времени, а затем процессор «получает» другой процесс. Если удовлетворяется только один запрос на получение доступа к ресурсу, и это происходит после того, как ресурс освободит другой процесс, такой ресурс является неразделяемым,  а о процессе говорят, что он имеет монопольный доступ (exclusive access) к ресурсу. В многопроцессорной среде важно знать, какой доступ можно организовать к разделяемому ресурсу: параллельный или последовательный (передавая «эстафету» поочередно от ресурса к ресурсу). Это позволит избежать ловушек, присущих параллелизму.

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

Граф распределения ресурсов.

Графы распределения ресурсов — это направленные графы, которые  показывают, как распределяются ресурсы  в системе. Такой граф состоит  из множества вершин V множества  ребер E. Множество вершин делится  на две категории:

P = {P 1 , P 2 ,..., Pn)

R = {R 1 , R 2 ,..., Rm}

Множество P— это множество  всех процессов, а R— это множество  всех ресурсов в системе Ребро, направленное от процесса к ресурсу, называется ребром запроса,  а ребро, направленное от ресурса к процессу, называется ребром назначения.  Направленные ребра  обозначаются следующим образом:

P i R j  Ребро запроса:  процесс Р i запрашивает экземпляр типа ресурса R j

R j P i . Ребро назначения: экземпляр  типа ресурса R j выделен процессу P i ;

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

Граф распределения ресурсов, отображает следующее.

Множества P, R и E

P={P a , P b , P c , P d }

R={R 1 ,R 2 ,R 3 }

E = {R 1 P a , R 1 P d , P b R 2 , R 2 P c , P c R 3 , R 3 P d }

 

Типы ресурсов

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

Некоторые аппаратные ресурсы прерываются, чтобы разрешить доступ к ним различных процессов. Например, прерывания процессора позволяют различным процессам выполняться по очереди. Оперативное запоминающее устройство, или ОЗУ (RAM),- это еще один пример ресурса, разделяемого посредством прерываний. Когда процесс не выполняется, некоторые страничные блоки, которые он занимает, могут быть выгружены во вспомогательное запоминающее устройство, а на их место загружены данные, относящиеся к другому процессу. В любой момент времени весь диапазон памяти может быть занят страничными блоками только одного процесса.

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

Информационные ресурсы  —  к ним относятся данные (например, объекты), системные данные (например, переменные среды, файлы и дескрипторы) и такие глобально определенные переменные, как семафоры и мьютексы, — являются разделяемыми ресурсами, которые могут быть модифицированы процессами. Обычные файлы и файлы, связанные с физическими устройствами (например, принтером), могут открываться с учетом ограничивающего типа доступа со стороны процессов. Другими словами, процессы могут обладать правом доступа только для чтения, или только для записи, или для чтения и записи. Сыновний процесс наследует ресурсы родительского процесса и права доступа к ним, существующие на момент создания процесса-потомка. Сыновний процесс может переместить файловый указатель, закрыть, модифицировать или перезаписать содержимое файла, открытого родителем. Доступ к совместно используемым файлам и памяти с разрешением записи должен быть синхронизирован. Для синхронизации доступа к разделяемым ресурсам данных можно использовать такие разделяемые данные, как семафоры и мьютексы.

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

Проектирование объектно-ориентированного программного обеспечения — это  процесс перевода требований к ПО в проект, в котором с помощью объектов моделируется каждый аспект разрабатываемой системы и выполняемой ею работы. Центральное место в этом проекте отводится структуре и иерархии коллекций объектов, а также их взаимоотношениям и взаимодействиям. Для поддержки понятия модели ПО в С++ используется ключевое слово class. Существует два базовых типа моделей. Первый тип модели — масштабированное представление некоторого процесса, концепции или идеи. Этот тип модели используется для анализа или экспериментирования. Например, класс применяется для разработки модели молекулы, т.е. с помощью концепции С++-класса можно смоделировать гипотетическую структуру некоторого химического процесса, происходящего в молекулах. Программным путем можно затем изучить поведение молекулы при внедрении новых групп атомов. Второй тип модели ПО — воспроизведение некоторой реальной задачи, процесса или идеи. Цель этой модели — заставить некоторую часть системы ПО или приложения функционировать подобно ее «прототипу». В этом случае ПО занимает место некоторого компонента или некоторого физического предмета в неавтоматизированной системе. Например, мы можем использовать концепцию класса для моделирования калькулятора. При корректном моделировании всех его характеристик и поведения можно создать экземпляр этого класса и использовать в качестве настоящего калькулятора. Программный калькулятор здесь будет играть роль реального калькулятора. Таким образом, смоделированный нами класс может служить в качестве виртуального лублера некоторого реального лица, места, предмета или идеи. Главное в программной модели — ухватить суть реального предмета.

 

2. Декомпозиция задачи и инкапсуляция ее решения.

 

Декомпозиция — это  процесс разбиения задачи и ее решения на части. Иногда части группируются в логические области (т.е. поиск, сортировка, вычисление, ввод и вывод данных и т.д.). В других случаях части  группируются по логическим ресурсам (т.е. файл, связь, принтер, база данных и т.д.). Декомпозиция программного решения часто сводится к декомпозиции работ (work breakdown structure — WBS). Декомпозиция работ определяет, что должны делать разные части ПО. Одна из основных проблем параллельного программирования — идентификация естественной декомпозиции работ для программного решения. Не существует простого и однозначного подхода к идентификации WBS. Разработка ПО — это процесс перевода принципов, идей, шаблонов, правил, алгоритмов или формул в набор инструкций, которые выполняются, и данных, которые обрабатываются компьютером. Это, в основном, и составляет процесс моделирования. Программные модели — это воспроизведение в виде ПО некоторой реальной задачи, процесса или идеала. Цель модели— сымитировать или скопировать поведение и характеристики некоторой реальной сущности в конкретной предметной области. Процесс моделирования вскрывает естественную декомпозицию работ программного решения. Чем лучше модель понята и разработана, тем более естественной будет декомпозиция работ. Наша цель — обнаружить параллелизм и распределение с помощью моделирования. Если естественный параллелизм не наблюдается, не стоит его навязывать насильно. На вопрос, как разбить приложение на параллельно выполняемые части, необходимо найти ответ в период проектирования, и правильность этого ответа должна стать очевидной в модели решения. Если модель задачи и решения не предполагает параллелизма и распределения, следует попытаться найти последовательное решение. Если последовательное решение оказывается неудачным, эта неудача может дать ключ к нужному параллельному решению.