9.4. Мультипрограммное выполнение параллельных процессов

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

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

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

параллельное. Предположим, что в нашем распоряжении имеется два параллельных процесса имеющих соответственно допустимые переходы (рис. 9.5).

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

Рис. 9.5. Параллельные процессы

Таким образом, мультипрограммное выполнение не отражает реального параллелизма. Это является следствием того, что при мультипрограммном выполнении команды содержат слишком много событий и не являются «атомарными». (Атомарными мы называем те команды или переходы, которые происходят без вмешательства каких-либо других.) Выполнение каждой из этих команд включает в себя: выбор значения распределяемой переменной, вычисление выражения, стоящего справа, присвоений значения распределяемой переменной.

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

Разделим все переменные на две группы:

локальные, или частные, переменные процесса — это те переменные, которые изменяются только этим процессом;

распределяемые переменные — это те переменные, к которым имеют доступ другие процессы.

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

Рис. 9.6. Модифицированные параллельные процессы

модифицирующая ссылка на переменную, к которой имеется ссылка доступа со стороны другого процесса;

ссылка доступа к. переменной, на которую имеется модифицирующая ссылка со стороны другого процесса.

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

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

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

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

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

9.4.1. Семафоры

Семафоры являются особыми атомарными командами, для которых делается необходимое в этом случае исключение из правила единственности

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

Команда занять эквивалентна предложению

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

Команда освободить эквивалентна предложению

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

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

Пример. Рассмотрим модель параллельных процессов следующего вида:

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

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

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

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

на две:

Подобным образом команду

разобьем на две:

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

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

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

9.4.2. Справедливость

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

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

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

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

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