Раздел 3. Параллельное выполнение программ

3.1. Концепция процесса

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

Процессор простаивал в ожидании завершения ввода/вывода, поэтому появилось естественное желание занять его на это время другими задачами.

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

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

Существует два пути реализации такой системы в зависимости от архитектуры компьютера.

Пусть N - число процессов, а М - число процессоров.

1. Если М >= N, то можно говорить о подлинной параллельности.

2. Если M < N, а чаще всего, М = 1, то можно говорить о временном разделении.

Представим это графически.

1) Компьютер - многопроцессорная машина - подлинно параллельное выполнение процессов:

2) Компьютер - однопроцессорная машина – псевдопараллельное выполнение процессов:

В этом случае используется временное разделение (time-sharing) и говорят о псевдопараллельности.

Для сравнения приведем и третий вариант выполнения – последовательное выполнение процессов

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

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

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

Так вот решение такой задачи не зависит от того, по какой схеме выполняются процессы - по схеме 1 или по схеме 2.

Учитывая два приведенных фактора:

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

2. Сходство проблем синхронизации для схемы 1 и схемы 2

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

Здесь вводятся понятия аппаратного и логического параллелизма.

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

Такие рассуждения приводят к появлению более строгого понятия ПРОЦЕСС, чем то, интуитивное, которым мы пользовались до этого момента.

Существует несколько определений понятия ПРОЦЕСС, некоторые из которых приведены ниже:

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

2. Процесс - это программа в состоянии выполнения.

3. Процесс - это пара <процессор, программа> при выполнении.

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

Для процесса есть другое название - задача.

Целесообразно выделить два аспекта понятия ПРОЦЕСС - практический и теоретический.

Практический аспект - что понимают под процессом в реальных операционных системах.

Теоретический аспект - математические модели понятия процесс.

Практический аспект понятия ПРОЦЕСС

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

Иерархия уровней параллелизма выглядит следующим образом:

1. Сеанс - запуск прикладных программ.

2. Процесс - выполнение одной программы

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

1. На самом высоком уровне находится понятие СЕАНС. Это запуск прикладной программы. Сеансов может быть несколько, но только один из них активный, захватывающий экран и клавиатуру. Остальные фоновые, но выполняющиеся. Над сеансами стоит МЕНЕДЖЕР СЕАНСОВ (например, диспетчер задач).

2. Следующий уровень – ПРОЦЕСС (выполнение программы). При запуске одного процесса из другого между ними существует отношение РОДИТЕЛЬ/ПОТОМОК с определенным протоколом заимствования ресурсов.

3. Нижний уровень - НИТЬ или МИНИЗАДАЧА или ПОТОК. Это параллельно выполняющиеся процедуры в рамках одного процесса.

Графически эти уровни сопоставляются следующим образом.

Сеанс

Процесс 1

Нить 1

Процесс 2

Создать процесс

Нить 1

Создать нить Нить 2

Выход

Процесс 3

Создать процесс

Нить 1

Уничтожить процесс

Выход

Теоретические аспекты понятия ПРОЦЕСС

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

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

Вводится понятие СОБЫТИЕ. Это первичное понятие, поэтому ему не дается определения. Но даются имена событиям X, Y и т. д.

Вводится понятие ПРОЦЕСС, как объект, реагирующий на события. Процессам тоже даются имена, например, P, Q и т. д.

Вводится формальная запись вида:

X -> P,

означающая, что событие воздействует на процесс.

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

Для описания такой последовательности используется рекурсия:

P = ( X -> P ).

В таком рекурсивном уравнении могут быть выполнены формальные подстановки:

P = (X->(X->P)) = (X->(X->(X->P)))

и так до бесконечности.

Например, ЧАСЫ - это объект, генерирующий событие ТИК, и после этого ведущий себя опять так же:

ЧАСЫ = (ТИК->ЧАСЫ).

Используя рекурсию, получаем описание потенциально бесконечного поведения объекта ЧАСЫ:

ТИК->ТИК->ТИК->ТИК->ТИК->ТИК->...

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

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

Другое определение понятия ПРОЦЕСС.

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

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

Факт изменения состояния машины называется событием.

Если есть неделимое действие А, то НАЧ(А) и КОН(А) – это события. При этом,

Т_НАЧ(А) < Т_КОН(А)

Выполнение программы представляется последовательностью действий

А₁ , А₂ , ... , А_i , ... ,

для которой

Т_{КОН (Аi)} < Т_{НАЧ(Аi+1)}

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

Далее рассмотрим совокупность двух (для простоты) последовательных процессов.

Может быть три варианта выполнения совокупности процессов:

Для схем 2) и 3):

Т_{КОН (p)} > Т_НАЧ(q)

Cхемы 1), 2), 3) - это:

1. последовательное выполнение;

2. псевдопараллельное выполнение;

3. параллельное выполнение - нужно два процессора.

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

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