Использование методологии мониторов для реализации параллельных процессов

Рисунок 13 - ГСА i-го сценария второго уровня

Обозначения внутри блоков ГСА совпадают с обозначениями в выражении 2.

Реализуем далее сценарную модель СМ1 сетью абстрактных машин СеАМ1. Выражения для модулей сети СеАМ1, определяющих сценарную модель СМ1, представим в следующем виде:

(6.3)

(6.4)

(6.5)

(6.6)

(6.7)

(6.8)

(6.9)

(6.10)

(6.11)

(6.12)

(6.13)

Данные логико-алгебраические выражения (6.3)-(6.13) получены на основе формул (6.1) и (6.2) с учетом причинно-следственных связей между подсценариями. Дадим интерпретацию предикатов и функций сети абстрактных машин в логико-алгебраической модели СеАМ1:

- готовность к формированию очередного запроса;

- формирование входной очереди запросов queue(i) к i-му дисковому модулю;

- завершена выборка запроса из входной очереди queue(i) и подготовлена канальная команда записи или чтения данных в i-м дисковом модуле;

- функция, значением которой является число свободных каналов;

- функция, значением которой является число свободных контроллеров;

- готовность к позиционированию головок в i-м дисковом модуле;

- ожидание подхода требуемого сектора накопителя информации;

- i-й дисковый модуль свободен и готов к выполнению операции;

- готовность к поиску записи внутри сектора;

- к моменту подхода требуемого сектора нет ни одного свободного канала или контроллера;

- к моменту подхода требуемого сектора по крайней мере один канал и контроллер готовы к поиску записи внутри сектора;

- операция записи или чтения блока данных в i-м дисковом модуле завершена;

- завершена операция и освобождены канал и контроллер.

Интерпретация модулей сети СеАМ1:

- задержка на время формирования очередного запроса;

- передача команды записи или чтения данных;

- занятие сетевого дискового модуля disk(i); анализ параметров команды записи-чтения данных парой “канал-контроллер”;

- задержка “перемещения” на время позиционирования головок в дисковом модуле;

- задержка “вращения” на время до подхода требуемого сектора, в котором начинается либо требуемый блок данных (при выполнении операции чтения), либо зона для записи блока данных (при выполнении операции записи);

,- неуспешные попытки начать поиск записи внутри сектора; если канал или контроллер заняты, то должен выполниться модуль ;

- подключение канала и контроллера на поиск записи внутри сектора;

- ожидание полного оборота носителя информации для повторной попытки поиска записи внутри сектора;

- запись блока данных на диск или считывание блока данных с диска;

- завершение операции записи-чтения.

В выражениях (6.3)-(6.13) символами обозначены задержки и на выполнение модулей СеАМ. В блоках модулей (блоками называются выражения, заключенные в фигурные скобки) здесь и далее точка с запятой (“;”) используется в качестве символа операции “непосредственное следование”, а запятая (“,”) - в качестве символа операции “выполнить, возможно одновременно”.

Здесь и далее модули реализуют подсценарии соответствующей сценарной модели. Отметим, что подсценарий можно здесь и далее также реализовать и одним модулем , описываемым следующим выражением:

= [p6(ai)&(feq(fchan(a0), 0) feq(fcontr(a0), 0))]({p6(ai)false,

p7(ai)true}RE).

Каждый модуль сети СеАМ представим в виде ГСА. ГСА модулей m1-m11 изображены на рисунках 14-20.

Рисунок 14 - ГСА модулей m1 и m2 сети СеАМ для i-го сценария второго уровня

Рисунок 15 - ГСА модуля m3 сети СеАМ для i-го сценария второго уровня

Рисунок 16 - ГСА модулей m4 и m5 сети СеАМ для i-го сценария второго уровня

Рисунок 17 - ГСА модуля m6,7 сети СеАМ для i-го сценария второго уровня

Рисунок 18 - ГСА модуля m8 сети СеАМ для i-го сценария второго уровня

Рисунок 19 - ГСА модулей m9 и m10 сети СеАМ для i-го сценария второго уровня

Рисунок 20 - ГСА модуля m11 сети СеАМ для i-го сценария второго уровня

5. Микропроцессорная реализация параллельных процессов на основе технологии мониторов (курсовой проект по дисциплине «Микропроцессорные системы»)

5.1 Теоретические основы параллельного программирования

5.1.1 Основные понятия

Процесс - это выполнение отдельной программы с её данными на последовательном процессоре.

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

Задача - единица работы, для выполнения которой предоставляется ЦП.

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

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

5.1.2 Концепция виртуальных ресурсов

В современных ОС используется концепция виртуальных ресурсов. Данная концепция позволяет унифицировать разработку процессов и повысить эффективность использования ресурсов.

Суть концепции состоит в следующем.

ОС использует все реальные ресурсы компьютера и на их основе создаёт новый виртуальный компьютер с заранее определёнными характеристиками, при этом каждый виртуальный ресурс моделируется с учётом его специфики. Виртуальный процессор моделируется на реальном CPU путем выделения квантов времени. Виртуальная память моделируется реальным ОЗУ на основе динамического преобразования адресов. Устройства ввода-вывода используются параллельно.

В результате на базе одного ПК реализуется несколько виртуальных вычислительных систем. Для ОС Windows может быть организована вычислительная системы как для программ, разработанных для самой ОС Windows, так и для программ, разработанных, например, в MS-DOS. Однако, поскольку реально требуется гораздо больше памяти, реальному компьютеру хватает имеющейся в наличии ОП и файла подкачки на диске. Для каждого процесса создаётся собственная виртуальная вычислительная система. В рамках концепции виртуальных ресурсов можно пойти дальше и для каждой виртуальной вычислительной системы создать несколько виртуальных процессоров, каждый из которых будет выполнять свою собственную задачу. Выполнение такой задачи виртуальным процессом называют tread - «нить». В современных ОС различают тяжеловесные и легковесные нити. Тяжеловесные нити - это нити, которые организованы ОС в рамках концепции виртуальных ресурсов. Легковесная нить - это нить, которая организована специальной библиотекой в составе процесса, те часть концепции виртуальных ресурсов переходит от ОС к процессу. Если ПК располагает 2-мя реальными процессорами, то две нити могут выполняться истинно параллельно. Если процессор один, то параллельное исполнение эмулируется с помощью разделения времени. Поскольку все нити одного процесса выполняются в рамках этого процесса, то они разделяют одно и то же адресное пространство, то есть имеют одни и те же глобальные переменные, общие виртуальные устройства, файловые дескрипторы. Это с одной стороны создаёт удобство при написании программы, а с другой требует от программиста особых навыков при написании программ. Кроме того, различные процессы могут взаимодействовать между собой посредством механизмов межпроцессорного взаимодействия. У двух нитей, выполняющихся в рамках одной виртуальной вычислительной системы различаются следующие параметры:

· регистры процессора;

· стек;

· нити-потомки;

· текущее состояние.

Эти параметры называются контекстом нити.

5.2 Применение мониторов для синхронизации параллельных процессов

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

5.3 Распределенные вычисления

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

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

6. Сетевая реализация параллельных процессов с использованием мониторов (курсовой проект по дисциплине «Сети ЭВМ и телекоммуникации»)

6.1 Понятие сокета

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

Следует различать клиентские и серверные сокеты. Клиентские сокеты грубо можно сравнить с оконечными аппаратами телефонной сети, а серверные - с коммутаторами. Клиентское приложение (например, браузер) использует только клиентские сокеты, а серверное (например, веб-сервер, которому браузер посылает запросы) -- как клиентские, так и серверные сокеты.

Интерфейс сокетов впервые появился в BSD Unix. Программный интерфейс сокетов описан в стандарте POSIX.1 и в той или иной мере поддерживается всеми современными операционными системами.

6.1.1 Принципы сокетов

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

Каждый сокет имеет свой адрес. ОС семейства UNIX могут поддерживать много типов адресов, но обязательными являются INET-адрес и UNIX-адрес. Если привязать сокет к UNIX-адресу, то будет создан специальный файл (файл сокета) по заданному пути, через который смогут сообщаться любые локальные процессы путём чтения/записи из него. Сокеты типа INET доступны из сети и требуют выделения номера порта.

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

6.2 Обмен данными в сети с использованием мониторов

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

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

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

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

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

Далее необходимо связать механизм сокетов и механизм мониторов.

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

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

Планирование доступа можно осуществлять, например, по описанным выше концепциям.

Общая схема описанной структуры представлена на рисунке 21.

Рисунок 21 - Обобщенная схема взаимодействия элементов системы

6.3 Распределенные программы

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

Рисунок 22 - Распределенная программа

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

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

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

· на сколько частей разбить приложение;

· какие функции возложить на каждую часть;

· как организовать взаимодействие этих частей, чтобы в случае сбоев и отказов оставшиеся части корректно завершали работу.

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

Заключение

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

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

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

Далее с этими автоматами можно оперировать средствами теории автоматов.

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

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

Список используемых источников

1. Эндрюс Г. Р. «Основы многопоточного, параллельного и распределенного программирования». Пер. с англ. -- М.: Издательский дом “Вильямс”, 2003.

2. Рихтер Дж. «Создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows». Пер. с англ. -- 4_е изд. -- Спб.: «Питер»; М.: Издательство «Русская Редакция»; 2008.

3. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления, СПб; БХВ-Петербург, 2002.

4. Э. Таненбаум, М. ван Стеен «Распределенные системы. Принципы и парадигмы» - Санкт-Петербург: Питер, 2003.

5. Вашкевич Н.П., Вашкевич С.Н. Недетерминированные автоматы и их использование для синтеза систем управления. - Пенза: Изд-во Пенз. гос. техн. ун-та, 1996. - 88 с.

Размещено на Allbest.ru