Вычислительные процессы взаимодействие и управление процессами

Вид материала

Лекция

Содержание 5.1.2. Управление процессами в многопроцессорном компьютере Реакция управляющей процедуры Запрос прерывания процесса до выполнения некоторого условия 5.2 Синхронизация процессов 5.2.1. Операции P и V над семафорами 5.2.2. Графическое представление процессов 5.3.3. Почтовые ящики 5.3.4. Монитор Хоара 5.3.6. Тупик в случае повторно используемых ресурсов Примеры SR-ресурсов Графы SR. P = {p1, p2, ..., pn} – множество вершин для отображения процессов и 5.3 Процессы последовательные и параллельные 5.3.1. Отношение предшествования процессов 5.3.2. Типы параллелизма Параллелизм множества объектов Параллелизм независимых ветвей – Параллелизм смежных операций. 5.4. Направления повышения эффективности компьютеров 5.5. Предпосылки создания систем параллельного действия ... Полное содержание

Подобный материал:

• Программа дисциплины "Управление инновационными процессами " для специальностей 080502, 123.7kb.
• Е. А. Подольская управление социальными процессами издательство нуа народная украинская, 3428.66kb.
• Учебно-методический комплекс дисциплины опд. Ф. 09. «Управление системами и процессами», 1084.9kb.
• «управление проектами в сфере бизнеса», 21.93kb.
• Управление инвестиционными процессами в регионе чуб борис Андреевич Монография Москва, 2307.38kb.
• Курсовая работа по химии на тему: «управление химическими процессами», 382.99kb.
• Управление процессами повышения эффективности государственных инвестиций в развитие, 383.31kb.
• Рабочей программы дисциплины психология малой группы по направлению подготовки 080400, 28.47kb.
• Программа спецкурса "Неупругое взаимодействие ионов с поверхностью", 27.54kb.
• Государственное и муниципальное управление в социальной сфере в рамках освоения данного, 13.32kb.

Лекция 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, управляемый последовательностью команд. Если в момент t_i этот процесс выдает код, возбуждающий процесс в ПУ, то ЦП переходит в управляющий режим и посылает сигнал по линии связи A₁, A₂ или A₃. Затем ЦП возвращается к выполнению своего процесса. По окончании работы одно из ПУ посылает сигнал прерывания по линии B_i, устанавливая тем самым 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. Почтовые ящики

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

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

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

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

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

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

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

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

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

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

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

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

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

Подобную ситуацию можно хорошо продемонстрировать на примере работы двух процессов p₁ и p₂ с одним читающим R₁ и одним печатающим R₂ устройствами.

Тупиковая ситуация возникает при мультипроцессировании, когда процессы p₁, p₂, ... , p_n, заблокированные по одному и тому же ресурсу Z_m, не могут быть разблокированы, так как их запросы на этот ресурс никогда не могут быть удовлетворены. Подобные конфликтные ситуации разрешаются либо ликвидацией процессов, зашедших в тупик, либо освобождением ресурса принудительным образом.

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

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

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

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

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

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

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

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

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

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

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

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

1. Множество N разделено на два непересекающихся класса: P = {p₁, p₂, ..., p_n} – множество вершин для отображения процессов и = {R₁, R₂, ..., R_m} – множество вершин для представления ресурсов.

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

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

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

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

    | (R_i, p_j) | + | (p_j, R_i) |  t_i, для  i, j,

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

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

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

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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Впервые, по-видимому, мы услышали о параллельном программировании в 1958 г. после выхода статьи Гилла (S. Gill) "Параллельные программы". Если система имеет только одну начальную (В) и только одну конечную (F) вершину (арех), то отношения предшествования, которые возможны между процессами p₁, p₂, ... , p_n, показаны на рис. 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-го прохода в стандартной сортировке слиянием второго порядка пары сортируемых списков длины 2^i–1 сливаются в списке длины 2ⁱ. Все слияния в пределах одного прохода могут быть выполнены параллельно.

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

Пример 4. Оценить требуемое минимальное время как функцию n для вычисления выражения a₁ + a₂ + ... + a_n , 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	Задача		параллель- ный алгоритм		параллель- ный язык		нетрадици- онное мышление		паралель- ные ЭВМ