Лекция вычислительные процессы icon

Лекция вычислительные процессы


1 чел. помогло.
Смотрите также:
Учебно-методический комплекс дисциплины вычислительные системы...
Курс лекций Казань 2005 оглавление лекция 1 введение 4 Глава Цели и задачи математического...
Учебно-методический комплекс по дисциплине вычислительные системы...
Программа дисциплины Вычислительные системы и телекоммуникации для направления 080700...
Лекция 2 часа, самостоятельная работа 2 часа, пр...
Планы лекций по дисциплине «организационное поведение» Лекция...
Программа дисциплины Вычислительные системы и телекоммуникации для направления 080700...
3 Лекция Бортовые цифровые вычислительные устройства и машины проф. Акаев А. Б. ауд. 5-208...
Рабочая программа...
Лекция: Спецификация функциональных требований к ис: Процессные потоковые модели...
1. Раскрыть сущность понятия «вычислительные приемы»...
Учебно-методический комплекс по дисциплине вычислительные системы...



Лекция 5. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ


 5.1. Взаимодействие и управление процессами

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

При выполнении программ явно выделяются три объекта:

        последовательность команд или процедура, которая определяет программу;

        процессор, который выполняет процедуру;

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

К среде относятся, например, память, универсальные и управляющие регистры ЭВМ, поскольку они могут и восприниматься, и изменяться программой.

Можно выделить следующие свойства программы:

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

                    среда полностью управляется программой, а следовательно, и изменяется только в результате шагов, выполненных программой;

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

                    совершенно не имеет значения, выполняется ли программа целиком на одном процессоре, лишь бы не изменялась среда программы.

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

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

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

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

5.1.1. Понятие процесса и состояния

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

Процесс есть тройка (Q, f, g), где Q – множество состояний процесса; f – функция действия f : Q  Q; g  Q – начальное состояние процесса.

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

Перечислим некоторые свойства процесса:

        процесс не является закрытой системой и может взаимодействовать с другими процессами, воспринимая или изменяя часть среды, которую он с ними разделяет;

        каждый процесс живет лишь временно. Имеется и "главный" процесс, выполняемый вручную при включении компьютера, который начинает всю цепочку процессов;

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

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

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

Опишем эти состояния.

ОЖИДАНИЕ. Процесс ожидает выполнения какого-либо события (например, завершения операции I/0).

ГОТОВНОСТЬ. Процесс готов к выполнению, но процессов больше, чем процессоров, и он должен ждать своей очереди.





ВЫПОЛНЕНИЕ. Процессору выделены все ресурсы, в том числе и процессор, и его программы выполняются в настоящее время. Схема на рис. 5.1. предполагает, что процессы уже существовали в памяти компьютера и будут существовать всегда. На практике пользователь должен эти процессы (задания) предоставить системе. Тогда реальная схема будет выглядеть так (рис. 5.2). Здесь дополнительно введены состояния: предоставление, хранение и завершение. Поясним их. Рис. 5.1. Схема перехода процессов из одного состояния в другое



Рис. 5.2. Полная схема обработки процесса

 ПРЕДОСТАВЛЕНИЕ. Пользователь предоставляет задание системе, на которое она должна отреагировать.

ХРАНЕНИЕ. Задание преобразовано во внутреннюю форму, понятную компьютеру, но ресурсы еще не выделены (например, задание записано на диск). Процесс в случае выделения ресурсов переходит в состояние готовности.

ЗАВЕРШЕНИЕ. Процесс завершил свои вычисления и все выделенные процессу ресурсы могут быть освобождены и возвращены системе.
^

5.1.2. Управление процессами в многопроцессорном
компьютере


Рассмотрим проекты ВС, включающие три компоненты: среду, процессоры и управление. Отметим, что центральный процессор управляется последовательностью команд, вызываемых откуда-то из среды, а периферийный процессор действует в соответствии с фиксированной, встроенной последовательностью команд.

ПРОЕКТ 1. Предположим, что имеется достаточное количество процессоров различного типа, чтобы обслуживать любой родившийся процесс (рис. 5.3).




Рис. 5.3. Структура МВС (проект 1)

 Управление будет состоять из центрального процессора (ЦП), управляемого процедурой, расположенной в памяти. Управляющий процессор соединен линиями связи с другими процессорами, запуская их и получая всю информацию о их состоянии. Обычное состояние ЦП – ожидание какого-нибудь события. При возбуждении управления оно определяет причину возбуждения, обрабатывает ее и, если возможно, запускает этот и/или другой процесс. Закончив обслуживание какого-то устройства, ЦП, прежде чем перейти в режим ожидания, проверяет, пуста ли очередь на обслуживание.

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

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

ПРОЕКТ 3. На третьем этапе из-за того, что УП часто простаивает, мы можем функции УП распределять между всеми ЦП. Центральные процессоры, работая в обычном режиме, выполняют какой-то процесс и могут быть прерваны ЦП, работающим в режиме управления. Последний не может быть прерван. Работой всех ЦП в управляющем режиме руководит одна и та же управляющая процедура.

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

Возбуждение управляющей процедуры (УП) может происходить одним из следующих способов:

        если процесс, выполняющийся в ЦП, выдает сигнал связи, то этот же ЦП переключается в управляющий режим и выполняет соответствующие действия;

        освободившийся от управления ЦП передает себя какому-нибудь процессу;

        прерывание от периферийного устройства переводит один из ЦП в режим управления.

Просмотр всех ЦП происходит поочередно, и если все они находятся в режиме управления, прерывание помещается в очередь.

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

 5.1.3. Управление процессами в однопроцессорном компьютере

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

Рассмотрим абстрактную ВС с ОП, одним ЦП, устройством ввода и устройством печати. Структура такой ВС дана на рис. 5.4.



Рис. 5.4. Структура ВС с одним ЦП

 Пусть в исходном состоянии все периферийные устройства (ПУ) находятся в состоянии покоя, а ЦП выполняет процесс Pi, управляемый последовательностью команд. Если в момент ti этот процесс выдает код, возбуждающий процесс в ПУ, то ЦП переходит в управляющий режим и посылает сигнал по линии связи A1, A2 или A3. Затем ЦП возвращается к выполнению своего процесса. По окончании работы одно из ПУ посылает сигнал прерывания по линии Bi, устанавливая тем самым i-й разряд регистра прерываний в соответствующее состояние. ЦП переходит в управляющий режим, анализирует состояние регистра прерываний для опознания ПУ, вызвавшего прерывания,

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

 5.1.4. Форматы таблиц процессов

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

        адрес, по которому выбирается следующая команда;

        адрес страницы (блока) данных, который следует прибавлять к каждой ссылке на данные во время обращения.

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

 

Процесс

Тип требуемого процессора

Параметры




Статус
процесса

 Рис. 5.5. Структура записи процесса

 Статус процесса указывает, готов ли процесс к обработке или он ждет выполнения некоторого условия.

Действия управляющей процедуры сводятся к обработке этих записей. Рассмотрим некоторые события процесса и действия управляющей процедуры на эти события (табл. 5.1)

 Таблица 5.1. Примеры действий управляющей процедуры

п/п

Событие процесса
^

Реакция управляющей процедуры


1

Сигнал (запрос)

образования

нового процесса

Формирует новую запись формата (рис.7.5) и добавляет ее в список записей процессов

2

^ Запрос прерывания процесса до выполнения некоторого условия

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

3

Сигнал прекращения процесса

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

4

Сигнал изменения значения семафора

Изменяет значение семафора. Проверяет все записи прерванных процессов, не ждут ли они изменения состояния этого семафора и если да, то изменяет их статус на "готов".

 

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

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

^ 5.2 Синхронизация процессов

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

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

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

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




Рис. 5.6. Пример тупиковой ситуации

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

Пример. Пусть программе А нужен ресурс R1. Она запрашивает его и получает. Программе В нужен ресурс R2. Она запрашивает его и получает (рис. 5.6). Далее, пусть программа А, не отпуская R1, запрашивает R2, а программа В, не отпуская R2, запрашивает R1. Налицо типичный клинч, если только один из ресурсов R1 или R2 не может быть освобожден до момента завершения обработки соответствующего процесса.

Рис. 5.6. Пример тупиковой ситуации

Для разрешения подобных проблем наиболее часто используют простейшие приемы синхронизации процессов, тесно связанные с аппаратным оборудованием.

Простейший прием – стандартные операции типа WAIT (ЖДАТЬ) и SIGNAL (ОПОВЕСТИТЬ). Операция WAIT позволяет: временно заблокировать процесс, а SIGNAL информирует систему о необходимости разблокирования процесса, задержанного из-за невыполнения условия. Следует отметить такие приемы, как БЛОКИРОВКА ПАМЯТИ (для реализации взаимного исключения одному процессу разрешается выполнить операцию над памятью, а другому ждать, пока первый не завершит работу); ПРОВЕРКА и УСТАНОВКА (аппаратная операция, к которой обращаются с двумя параметрами: ЛОКАЛЬНЫЙ И ОБЩИЙ). Эти приемы хотя и решают задачу взаимного исключения, однако неэффективно используют процессорное время из-за необходимости пребывания в активном состоянии процесса, ожидающего разрешения продолжить работу. Наиболее эффективным и простым средством синхронизации процессов, исключающим состояние "активного" ожидания, является семафор.
^

5.2.1. Операции P и V над семафорами


В 1968 г. Э. Дейкстра предложил удобную форму механизма захвата/освобождения ресурсов, которую он назвал операциями P и V над считающими семафорами. Считающим семафором называют целочисленную переменную, выполняющую те же функции, что и байт блокировки. Однако в отличие от последнего она может принимать кроме "0" и "1" и другие целые положительные значения.

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

Операции P и V над семафором S могут быть определены следующим образом.

P(S):

1. Уменьшить значение S на 1, т. е. S : = S – 1.

2. Если S < 0, выполнить ОЖИДАНИЕ (S).

V(S):

1. Увеличить значение S на 1, т. е. S : = S + 1.

2. Если S  0, выполнить ОПОВЕЩЕНИЕ (S).

Операция ОЖИДАНИЕ (S) (WAIT) блокирует обслуживание процесса, делает соответствующую отметку об этом и связывает процесс со значением переменной S.

Операция ОПОВЕЩЕНИЕ (S) (SIGNAL) просматривает связанный с переменной S список блокированных процессов. Если в списке есть процессы, ожидающие освобождения некоторого ресурса, управляемого (сигнализируемого) S, один из них переводится в состояние готовности, а в соответствующей ему записи делается отметка. С этого момента процесс становится опять доступным планировщику.

По определению, ожидание, связанное с операцией P(S), не является ожиданием "зависания", так как ожидающие процессы не используют центральный процессор. Так как несколько процессов могут ожидать операцию P(S) над отдельным семафором, во время приращения должен быть осуществлен выбор, какую контрольную точку процесса сделать доступной. Алгоритм выбора не определен, за исключением требования равнодоступности процессов, т. е. никакой процесс не может быть "забыт".

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

Наиболее употребительные операции над семафорами:

    создать семафор;

    запросить состояние семафора;

    изменить состояние семафора;

    уничтожить семафор.

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

Наиболее показательно аппарат семафоров можно применить на следующей задаче.

Три курильщика сидят за столом. У одного есть табак, у другого – бумага, у третьего – спички. На столе могут появиться извне два из трех упомянутых предмета. Появившиеся предметы забирает тот курильщик, у которого будет полный набор предметов. Он сворачивает папиросу, раскуривает ее и курит. Новые два предмета могут появиться на столе только после того, как он кончит курить. Другие курильщики в это время не могут начать курение.

Задание. Описать с помощью P и V – операций над семафорами – систему процессов, которая моделирует взаимодействия этих курильщиков.

Указание. Выделить шесть процессов, три из которых соответствуют трем курильщикам X, Y, Z, а три других имеют следующее назначение: А – поставляет спички и бумагу, В – табак и спички, С – бумагу и табак.

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

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

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

5.2.2. Графическое представление процессов


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

Пример 1. Изобразим графически действия автомата, продающего билеты (рис. 5.7, а), и действия автомата, продающего билеты и расписание (рис. 5.7, б).







Рис. 5.7. Графическое изображение действий автомата:

а – автомат, продающий билеты; б – автомат, продающий билеты и расписание

На рис. 5.7 введены следующие сокращения: мон – опустить монету; бил – получить билет; расп – получить расписание.

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

Пример 2. Представим автомат, изображенный на рис.5.7, б в более компактной графической форме (рис. 5.8, а).

Доказать графически, что рис. 5.8, а и рис.5.8, б иллюстрируют в точности один и тот же процесс.

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

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




Рис. 5.8, а Рис. 5.8, б

Обычно протокол обозначают последовательностью символов, заключенных в угловые скобки: < > – пустая последовательность, не содержащая событий;

< x > – последовательность, содержащая единственное событие x;

< x,y > – последовательность, состоящая из двух событий: x и следующего за ним y.

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

< мон; бил; мон; бил >.

Протокол того же автомата перед тем, как второй покупатель вынул билет, будет

  < мон; бил; мон >.

Понятие протокола сегодня широко используется и в компьютерных сетях. Например, в сети Internet, состоящей из множества сетей различной природы: от ЛВС типа Token Ring до глобальных сетей типа NSFNET, базовым протоколом является TCP/IP (Transmission Control Protocol / Internet Protocol). TCP отвечает за доставку сообщений по указанному адресу, а IP поддерживает адресацию сетевых узлов.

Вообще говоря, TCP/IP – это семейство протоколов и прикладных
программ.

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

5.3.3. Почтовые ящики


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

Если процесс p1 желает послать процессу p2 некоторое сообщение, он записывает его в одно из гнезд почтового ящика, откуда p2 в требуемый момент времени может его извлечь. Иногда оказывается необходимым процессу p1 получить подтверждение, что p2 принял переданное сообщение. Тогда образуются почтовые ящики с двусторонней связью. Известны и другие модификации почтовых ящиков, в частности порты, многовходовые почтовые ящики и т. д. Для установления связей между процессами широко используются почтовые ящики. Примером такого применения может служить операционная система IPMX86 ВС фирмы Intel для вычислительных комплексов на основе микропроцессоров IAPX86 или IAPX88. Для целей синхронизации разрабатываются специальные примитивы создания и уничтожения почтовых ящиков, отправки и запроса сообщений.

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

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

5.3.4. Монитор Хоара


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

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

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

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

Иногда монитор задерживает обратившийся к нему процесс. Это происходит, например, в случае обращения за занятым ресурсом. Монитор блокирует процесс с помощью команды "ЖДАТЬ", а в случае освобождения ресурса выдает команду "СИГНАЛ". При этом освободившийся ресурс предоставляется одному из ожидавших его процессов вместе с разрешением на продолжение работы. Управление передается команде монитора, непосредственно следующей за операцией "ЖДАТЬ".

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

5.3.5. Проблема тупиков

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

Подобную ситуацию можно хорошо продемонстрировать на примере работы двух процессов p1 и p2 с одним читающим R1 и одним печатающим R2 устройствами.

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

Комплекс программ, объединенных под общим названием ОБРА-БОТКА ТУПИКОВ (ОТП), как правило, выполняет следующие функции:

    анализирует возможности избежания тупиков и предотвращает их, если возможно;

    определяет множество процессов, находящихся в состоянии тупика;

    определяет способы и принимает меры для выхода из тупика.

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

5.3.6. Тупик в случае повторно используемых ресурсов


 Повторно используемые ресурсы SR (Second hand resource) – это конечное множество одинаковых ресурсов, обладающихследующими свойствами:

        количество единиц ресурсов постоянно;

        каждая единица ресурса или распределена, или доступна только одному процессу;

        процесс может освободить единицу ресурса (или сделать его доступным) при условии, если он ранее получал эту единицу.

^ Примеры SR-ресурсов: ОП, ВнП, периферийные устройства и, возможно, процессоры, а также такое ПО, как файлы данных, таблицы и "разрешение войти в критическую секцию".

Графы SR. В случае SR-ресурсов граф типа "процесс-ресурс", отображающий состояние OS, называют графом повторно используемых ресурсов. Направленный граф – это пара < N, E >, где N – множество вершин, а E – множество упорядоченных пар (a, b), называемых ребрами, a, bN. В случае SR интерпретация графа следующая.

1. Множество N разделено на два непересекающихся класса:^ = {p1, p2, ..., pn} – множество вершин для отображения процессов и = {R1, R2, ..., Rm} – множество вершин для представления ресурсов.

2. Граф является двудольным по отношению к P и . Каждое ребро e  E соединяет вершину из P с вершиной из . Если e = (pi, Rj), то e – ребро запроса от процесса pi на единицу ресурса Rj. Если же e = (Rj, pi), то e – ребро назначения единицы ресурса Rj процессу pi.

3. Для каждого Ri целое неотрицательное число ti, обозначает количество единиц ресурса Ri.

Пусть | (a, b) | – число ребер, направленных от вершины a к вершине b. Тогда система должна работать всегда при следующих ограничениях:

    может быть сделано не более чем ti назначений для Ri, т. е.   для всех i;

    | (Ri, pj) | + | (pj, Ri) |  ti, для  i, j,

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

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

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

Чтобы распознать состояние тупика, для каждого процесса необходимо определить, сможет ли он когда-либо снова развиваться. Наиболее благоприятные действия для незаблокированного процесса pi могут представляться сокращением (редукцией) графа SR.

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





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

Рис. 5.9. Последовательность сокращений графа

 Теорема. Состояние S есть состояние тупика тогда и только тогда, когда SR-граф в состоянии S не является полностью сокращаемым.

Следствие 1. Если S есть состояние тупика по SR-ресурсам, то по крайней мере два процесса находятся в тупике в S.

Следствие 2. Процесс pi не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором pi не заблокирован

^ 5.3 Процессы последовательные и параллельные

Мы привыкли к последовательному образу мышления, к компьютерам последовательного действия, а следовательно, к разработке последовательных алгоритмов и соответственно к последовательной обработке данных. И как следствие этого, разработаны и широко используются "последовательные" языки программирования – ФОРТРАН, АЛГОЛ, ПАСКАЛЬ и многие другие.

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

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

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

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

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

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

5.3.1. Отношение предшествования процессов


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

Впервые, по-видимому, мы услышали о параллельном программировании в 1958 г. после выхода статьи Гилла (S. Gill) "Параллельные программы". Если система имеет только одну начальную (В) и только одну конечную (F) вершину (арех), то отношения предшествования, которые возможны между процессами p1, p2, ... , pn, показаны на рис. 8.1.

Каждый граф на рис. 5.1 описывает трассу развития процесса во времени и указывает на отношение предшествования. Такие графы называют графами развития процесса.

Пример 1. Вычислить значение выражения

(a + b) • (c + d) – (e/f)

(1)





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

Рис. 5.1. Граф развития процесса:





а – последовательные процессы;б – параллельные процессы;

в – последовательно-параллельные процессы

Рис. 5.2. Дерево для выражения (1)

Рис. 5.3. Граф развития процесса
для вычисления выражения (1)

 

Н. Вирт (1966) предложил для описания параллелизма использовать простую конструкцию and. Тогда предложения программы для вычисления выражения (1) (рис. 8.3) могут быть следующими:

begin

S1: = a + b and S2: = c + d and S4: = e/f;

S3: = S1 • S2;

S5: = S3 – S4 

end.

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

В качестве упражнения полезно построить граф развития процесса для примеров 2 и 3 и решить пример 4.

Пример 2. Сортировка слиянием. Во время i-го прохода в стандартной сортировке слиянием второго порядка пары сортируемых списков длины 2i–1 сливаются в списке длины 2i. Все слияния в пределах одного прохода могут быть выполнены параллельно.

Пример 3. Умножение матриц. При выполнении умножения матриц A = B  • C, все элементы матрицы A могут быть вычислены одновременно.

Пример 4. Оценить требуемое минимальное время как функцию n для вычисления выражения a1 + a2 + ... + an , n  1, в предположении, что:

        параллельно может быть выполнено любое число операций
сложения;

        каждая операция (включая выборку операндов и запись результата) занимает одну единицу времени.
^

5.3.2. Типы параллелизма


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

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

Например, вычисление скалярного произведения для n-мерных векторов



включает два типа операций: попарное произведение компонент векторов и затем "интегральную операцию" (операция над n-мерным вектором) – суммирование между собой всех компонент этого вектора. Исходными операндами интегральных операций являются векторы или функции, или множества объектов, а результатом – число.

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



во всех точках внутри некоторой области на плоскости x, y при заданных значениях  (x, y) на границах области.

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

При параллелизме множества объектов аналогичное положение встречается сравнительно часто.

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

^ Параллелизм независимых ветвей – количество независимых частей (участков, ветвей) задачи, которые при наличии в ВС соответствующих средств могут выполняться параллельно (одновременно одна с другой).

Ветвь программы Y не зависит от ветви X, если:

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

        между ними нет связи по рабочим полям памяти;

        они должны выполняться по разным программам;

        независимы по управлению, т. е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

^ Параллелизм смежных операций. Суть его в следующем.

Если подготовка исходных данных и условий исполнения i-й операции заканчивается при выполнении (i–k)-й операции (где k = 2, 3, 4, ...), то i-ю операцию можно совместить с (i–k + 1)-й, (i–k + 2)-й , ... , (i–1)-й.

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

 














а













б

в

Рис.5.4. Сценарий обработки процессов:

а – последовательный процесс; б – последовательно–параллельный процесс: здесь  порядок выполнения программы,  – ожидание некоторого условия, – отдельные фрагменты программ;

в – параллельные процессы

Вместе с развитием теории взаимодействующих процессов прослеживаются две концептуальные цепочки проектирования структуры компьютера:

1

Задача



последовательный

алгоритм



последовательный

язык



последова-тельное

мышление



последо-вательная

ЭВМ

 

 

 

 

 

 

 

 

 

 

2

Задача



параллель-

ный

алгоритм



параллель-

ный

язык



нетрадици-

онное

мышление

 



паралель-

ные ЭВМ



^

5.4. Направления повышения эффективности компьютеров


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

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

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

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

    параллельность выполнения большого количества операций,

    автоматическая настраиваемость структуры на решаемую задачу,

    конструктивная однородность,

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

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

На сегодня установилась классификация ВВС, базирующихся на порядке поступления потоков команд и данных на обработку. Их структуры образуют следующие четыре класса:

        одиночный поток команд – одиночный поток данных (SISD). Сюда относятся типичные машины последовательного действия;

        одиночный поток команд – множественный поток данных (SIMD). Это матричные и ассоциативные структуры;

        множественный поток команд – одиночный поток данных (MISD). Он включает конвейерные или магистральные структуры;

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

На сегодняшний день разработан и функционирует целый спектр ВВС, начиная от машин серии ЕС, ПС, Эльбрус, имеющих производительность от нескольких миллионов и сотен миллионов операций в секунду, до многопроцессорной ВС Suprenum, включающей 256 процессорных узлов общего назначения с максимальной производительностью 5 млрд операций в секунду (оп/с) и машин типа Teraflop-1 с пиковой производительностью 1000 млрд оп/с.

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

Опыт разработки и исследования конвейерной архитектуры от ЭВМ Star 100, IBM 360/91, Cyber 205 до ETA Systems, Cray Research и ряда других показывает многообразие структурных решений, способствующих значительному увеличению максимальной производительности. Однако существенное увеличение быстродействия на конвейерных ВВС может быть достигнуто лишь для задач, векторизуемых более чем на 90 %. Векторизация в реальных задачах не превышает 70 %. Выход из этой ситуации, как правило, ищут в двух направлениях. С одной стороны, акцентируется внимание на повышении мощности скалярных вычислений в векторных ВВС. Здесь показательны, например, разработки фирмы Cray Research. Так, если первые ее модели Cray X-HP, Cray-2 имели до четырех процессоров, то Cray-3 содержала 16 процессоров, а Cray-4 уже 64.

Интерес представляет суперкомпьютер CrayT3E/1200 – масштабируемая массово-параллельная система, состоящая из отдельных процессорных элементов (РЕ), которую производит компания CrayResearch, подразделение SiliconGraphics. В нем используются процессоры DECchip (DECAlphaEV5) с тактовой частотой 600 MГц и пиковой производительностью 1200Mflops. СистемыT3E масштабируются до нескольких тысяч процессоров. Каждый процессорный элемент располагает своей памятью (DRAM) объемом от 256Mб до 2Гб. При этом память системы глобально адресуема. Процессорные элементы связаны высокопроизводительной сетью с топологией трехмерного тора и двунаправленными каналами. Скорость обмена достигает 480 Mб/c в каждом направлении. Поддерживается явное параллельное программирование через пакет CrayMessagePassingToolkit (MPT), включающий высокопроизводительные реализации интерфейсов MPI и PVM, а также библиотеку Shmem разработки CrayResearch для работы параллельных процессов над общей памятью. Для Фортран-программ возможно также неявное распараллеливание в моделях CRAFT и HPF. Среда разработки включает также набор визуальных средств для анализа и отладки параллельных программ. Компьютер работает под управлением операционной системы UNICOS/mk.

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

При разработке параллельных компьютеров существенную трудность представляет решение задачи разбиения алгоритмов на значительные по объему вычислений фрагменты, которые были бы информационно независимы. Большое затруднение здесь вызывают условные переходы, встречающиеся через каждые 8–10 команд. Решением проблемы условных переходов стал компилятор планирования трассы Trace Scheduling (фирма Multiflow Computer), который позволяет прогнозировать направление переходов в программах для решения инженерно-технических задач на основе аппарата статистического анализа.

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

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

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

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

2.                  Разработка общих методов построения параллельных алгоритмов и распараллеливание последовательных алгоритмов. Исследование сложности параллельных алгоритмов в различных областях применений.

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

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

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

    машины Тьюринга;

    машины с управлением потоком данных (data flow);

    модели, базирующиеся на сетях Петри и схемах синхронизации, и т. д.

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

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

В теории параллельных вычислений имеется ряд открытых проблем. Основная из них – это возможность эффективного распараллеливания алгоритмов. Она формулируется как соотношение классов NC и P. Это вопрос такой же важности, как соотношение классов P и NP в теории сложности вычислений, и очень далек от своего решения, ибо предполагает получение сверхполилогарифмических оценок параллельной сложности решения некоторых задач из класса P.

К конкретным задачам, для которых неизвестна их принадлежность ни к NC, ни к P-классу, относится, например, задача возведения целого в степень: для заданных n-битовых чисел a, b и m вычислить amod m
^

5.5. Предпосылки создания систем параллельного действия


 

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

ЭВМ и их МО являются на сегодня, пожалуй, самыми дорогостоящими продуктами производства, поэтому эффективность их применения требует бóльшего внимания. Работа современных ЭВМ в пакетном режиме использует это дорогостоящее оборудование крайне неэффективно. Речь идет не только о том, что простои оборудования в среднем достигают 50 %, но и о том, что половина оставшегося времени идет на отладку программ. Если сюда присовокупить время на процессы трансляции, сборки, редактирования связей – необходимые этапы подготовки задачи к счету, то доля полезного времени для обработки данных по отлаженной программе окажется совсем незначительной.

За время развития вычислительной техники накладные расходы на каждую с пользой выполненную команду программы выросли на 3–4 порядка. (Раньше роль транслятора, сборщика, редактора играл сам программист.) Созданные за это время средства автоматизации проектирования программ и их подготовки к обработке лишь в 40–50 раз повышают производительность работы программиста. Поэтому проблема изменения соотношения времени, затрачиваемого ЭВМ на подготовку задач и на получение "полезных результатов" в пользу последнего, является актуальной. Изменение указанного соотношения можно осуществить через преобразование структуры компьютера.

Для универсальных ЭВМ характерен широкий набор команд и данных. Во время трансляции, например, главным образом используется небольшое подмножество этих команд, связанное с преобразованием текстов. Возможности АУ по выполнению арифметических операций с плавающей точкой и удвоенной точностью не используются, при выполнении вычислений все обстоит наоборот. Что касается операции ввода-вывода, то на разных этапах ее используются только определенные возможности компьютера. Поэтому целесообразно иметь хотя бы два процессора в ЭВМ: один использовать только для обработки данных, а другой – для подготовительных работ. Основная трудность двухпроцессорной организации заключается в сбалансировании ее работы. Аналогичную картину можно проследить с использованием памяти, отдельные участки которой простаивают длительное время из-за отсутствия к ним обращений. При анализе динамики обращений к памяти при решении некоторых классов вычислительных задач было установлено, что ОЗУ активно используется лишь на 10–15 %.

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

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

Пусть надо вычислить значение r по формуле

r = x + y z.

(*)

Формулу (*) можно рассматривать как некоторый преобразователь чисел x, y, z в некоторое другое число r = x + y • z. Пусть все числа заданы в двоичной форме (на общность рассуждений это не влияет). Таким образом, речь идет о преобразовании некоторого набора нулей и единиц, представляющих собой последовательность чисел x, y, z в некоторый другой набор нулей и единиц для r. Из алгебры логики известно, что для любой функции можно построить дизъюнктивную нормальную форму (ДНФ). В свою очередь, i-й двоичный разряд результата r можно рассматривать как логическую функцию

ri = r (x1, x2, ..., xn, y1, y2, ..., yn, z1, z2, ..., zn),

где xi, yi, zi, – двоичные разряды, представляющие возможные значения x, y, z.

Так как любая функция (вычисление любого разряда ri) i =  может быть представлена ДНФ (через И, ИЛИ, НЕ), то можно построить n схем (n процессоров), которые, работая одновременно, выдают все n разрядов результата r. Ясно, что подобные рассуждения носят абстрактный характер и ими трудно воспользоваться на практике, ибо количество конкретных алгоритмов – бесконечное множество. Но тем не менее подобный подход позволяет рассматривать с общих позиций попытку реализовать вычислительные среды – многопроцессорные системы, динамически настраиваемые на конкретный алгоритм. Принципиальная возможность распараллелить любой алгоритм оправдывает те усилия, которые предпринимаются сегодня для решения этой задачи.

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

Технические предпосылки для создания МВС накапливались постепенно. Скажем, идея комплексирования ЭВМ через общую память была апробирована в многомашинном комплексе "Минск-222" в 1966 г. Внутри машин ряда I серии ЕС ЭВМ были заложены основы комплексирования ЭВМ, правда, с некоторыми ограничениями. Более широкие возможности комплексирования ЭВМ серии ЕС представлены в машинах ряда 2 и 3.

Можно выделить три основных направления по созданию машин следующих поколений.

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

2. Создание новых структур – МВС. При этом внутреннюю систему команд компьютеров приближают к языкам высокого уровня.

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

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

^ 5.6 Некоторые примеры параллельных программ.

Развитие точных методов в программировании привело к возникновению различных формальных моделей программ, в том числе и моделей параллельных программ.

Рассмотрим модели параллельных программ, прототипом которых явились операторные схемы программ, в частности схемы Янова.

В.Е.Котовым и А.С.Нариньяни была предложена формальная модель параллельных вычислений, названная асинхронной моделью.

Асинхронная программа над памятью M (A-программа) представляет собой множество X блоков и массивов блоков. Блок x образован парой (y, 0), где y – предикат над MCM, M– управляющая память, O – оператор над памятью M. С O-оператором связаны входные и выходные наборы переменных из М. По входному набору О-оператор вычисляет значение переменных выходного набора. Предикат y– спусковая функция блока x.

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

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

Пусть A– множество операторов над памятью M.

Для каждого момента t множество операторов вычислительного процесса можно разбить на 4 непересекающихся множества:

+At  – включающиеся в t;

-At– выключающиеся в t;

pAt находящиеся во включенном состоянии;

0At– находящиеся в выключенном состоянии.

Q = {q} – множество состояний метасистемы, q0– начальное состояние.

F– функция, однозначно сопоставляющая каждому множеству   одно из его подмножеств в соответствии с состоянием q.

 – функция, ставящая в соответствие каждому набору   некоторое состояние q ( – предыстория процесса Р до момента t включительно).

Каждому оператору aiA сопоставляется счетчик ci с начальным значением . Текущее значение счетчика ciфиксирует разность между числом имевших место включений и числом имевших место выключений оператора ai.

Тогда модель Котова–Нариньяни можно записать в виде рекурсивных соотношений:

qt = (M0, P||t-1);

At=At-1\+At-1 -At-1;

*At=F1(0At, qt);

+A *At;

рAt=рAt-1\-At-1 +At;

-A рAt.

В основу модели Карпа – Миллера легло представление программы как множества элементарных операторов, использующих ячейки памяти и воздействующих на них, для которых указаны правила включения и выключения. Формально параллельная схема программы R = (M, A,  ) определяется следующим образом.

1. М – множество ячеек памяти.

2. A={a,b,...} – конечное множество операторов; для каждого оператора из А заданы:

K(a) – количество символов выключения оператора a (целое положительное число);

Д (а)  М – множество входных ячеек оператора а;

Т (а)  М – множество выходных ячеек оператора а.

3.Четверка Г = (а, q0,,)  – управление схемы,

где  q0– выделенное начальное состояние.

При этом каждому оператору а сопоставлены один символ включения   и множество символов выключения {a1, ..., ak(a)};  

где

,



 – функция переходов – частичная функция из Qx в Q, всюду определенная на Qxt.

Управление Г формирует последовательность выполнения операторов. Элементы из i обозначают акты включения операторов, элементы из t– акты выключения. Включение оператора а допустимо лишь в таком состоянии q, что значение  (q, a) определено. После включения оператора завершение его работы допустимо в произвольном состоянии, поскольку функция  всюду определена на Qxt. При включении оператор а использует значения ячеек из Д (а), при выключении он засылает свои результаты в ячейки из Т(а) и формирует символ выключения, который соответствует одному из K(а) направлений условной передачи.

Полезным для эффективного распознавания свойств параллельных схем программ является класс счетчиковых схем.

Счетчиковой схемой называется схема R=(M, A, Г ), для которой управление Г задается следующим образом.

Пусть k – целое неотрицательное число;

 – конечное множество;

S – множество с выделенным элементом S0;

k, где – множество неотрицательных целых чисел;

v – функция из  в k, такая, что если t, то v()0;

: SxS – частичная функция, всюду определенная на Sxt.

Полагая, что значение ((S,x),) определено, если определено (S,) и выполнено x+v()0. Если значение определено, то полагается ((S,x),)=((S,), x+v()).

Более простыми и наглядными являются параллельные операторные схемы – частный случай счетчиковых схем.

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

1) S = {S0};

2) для каждого  значение (S0,) определено;

3) если  – символ выключения, то каждая компонента вектора v() равна 0 или 1;

4) если  – символ включения, то каждая компонента вектора v() равна 0 или -1;

5) для любых двух неравных символов включения ,  из v()i= -1 следует v()i=0.

Параллельную операторную схему можно представить в виде ориентированного графа с операторными вершинами Оа, Оb, Оc,... и вершинами-счетчиками d1, d2, ..., dk. Каждый счетчик di помечается числом i, которое является начальным значением этого счетчика. Дуги графа направлены либо от операторных вершин к счетчикам, либо от счетчиков к операторным вершинам. Дуги сопоставлены ненулевым компонентам векторов v().

Если (v(aj))i=1, то выключение оператора а с символом выключения aj увеличивает значение счетчика i на 1. Если (v())i= –1, то включение оператора а уменьшает значение счетчика i на 1. Условие 5 из определения параллельной операторной схемы означает, что из произвольного счетчика выходит не более чем одна дуга.

Пример. Пусть необходимо перемножить матрицу

  на вектор ,

а результат поместить в (с1, с2).

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

Рассмотрим теперь другие модели программ, которые в меньшей мере опираются на понятие операторных схем программ.

В качестве модели программы иногда предлагается пара R=(M,C), где M определяет ее информационную, а С – управляющую структуру. Для представления информационной структуры М используются простые вычислительные модели, а для представления управляющей структуры – сети Петри. Сеть Петри – двудольный граф, множество вершин которого состоит из переходов tjT и позиций piP. Кроме того, заданы две функции инцидентности:

F : PxT{0,1};

B : TxP{0,1}.

Они задают множество дуг, ведущих из позиций в переходы и из переходов в позиции. N0 : P{0,1,2,...} – начальная разметка сети. Сеть Петри функционирует, переходя от одной разметки к другой. Каждая разметка – это функция N : P{0,1,2,...}. Схема разметок происходит в результате срабатывания одного из переходов. Переход t может сработать, если для него выполнено условие срабатывания (N(p)–F(p,t))0 p. После того как переход t срабатывает, разметка N сменяется разметкой N по следующему правилу:

p(N(p)=N(p)–F(p,t)+B(p,t)).

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

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





Рис. 5.5. Графовые структуры

    безусловные, которые не зависят от текущих значений переменных в исполняемой программе;

      условные, которые принимают во внимание текущие значения
данных.

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









Скачать 431.88 Kb.
оставить комментарий
Дата28.09.2011
Размер431.88 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

Рейтинг@Mail.ru
наверх