Разделяемая память. Проблема производителя и потребителя

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

Для того, чтобы проиллюстрировать концепцию взаимодействия процессов с использованием разделяемой памяти, рассмотрим так называемую проблему производителя и потребителя («producer-consumer»), также известную как проблема ограниченного буфера. Процесс-производитель производит информацию, которую обрабатывает процесс-потребитель. Например, программа вывода на печать производит последовательность символов, которые потребляются драйвером принтера, или компилятор производит ассемблерный код, который затем потребляется ассемблером.

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

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

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

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

var n; [количество элементов буфера]

type item.=...; [тип элементов буфера]

var buffer: array [0..n - 1] of item;

in,out: 0..n-1;

где n - количество адресуемых элементов буфера, item – имя типа элемента буфера, in, out - указатели, характеризующие заполненность буфера. Начальное значение переменных in и out равно нулю.

Очевидно, что буфер пуст, если выполняется условие in = out. Буфер будет полностью заполнен, если (in + 1) mod n = out.

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

Repeat

........

[формируется очередной элемент в nextp]

........

while (in+1) mod n = out do no-op;

buffer [in]:= nextProduced;

in:=(in+1) mod n;

until false;

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

Repeat

while in = out do no-op

nextConsumed: = buffer [out];

out: = (out+1) mod n;

......

[потребляется очередной элемент из nextc]

......

until false;

Взаимодействие путем передачи сообщений

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

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

Функция системы обмена сообщениями – предоставление процессам возможности обмениваться информацией без использования общих переменных. Система обмена сообщениями предоставляет для этого две операции: Send и Receive.

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

Для организации взаимодействия процессы должны ссылаться друг на друга. Возможны системы непосредственного обмена (direct communication) и системы опосредованного обмена (indirect communication). Система непосредственного обмена сообщениями предполагает, что одновременно в обмене могут участвовать только два процесса. Система опосредованного обмена предполагает, что в обмене могут участвовать более двух процессов.

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

Send (P, message) – отправить сообщение с именем message процессу с именем Р.

Receive (Q, message) – получить сообщение с именем message от процесса с именем Q.

Приведем решение задачи «Производитель-потребитель» с использованием схемы непосредственного обмена сообщениями:

Процесс-производитель:   repeat .......... [Формируется очередной элемент в nextp] .......... send (Consumer, nextp); .......... untilfalse;

Процесс-потребитель   repeat .......... Receive (Producer, nextc); .......... [Потребляется очередной элемент из nextc] .......... untilfalse.

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

Send (P, message) – отправить сообщение с именем message процессу с именем Р.

Receive (id, message) – получить сообщение с именем message от некоторого процесса. Здесь переменная id содержит имя процесса, от которого получено сообщение.

В случае опосредованного обмена сообщения пересылаются и получаются из так называемых почтовых ящиков (mail boxes), часто называемых портами (ports). Каждый почтовый ящик имеет уникальное имя. Несколько процессов могут взаимодействовать друг с другом в том случае, если они имеют общий почтовый ящик. В этом случае примитивы Send и Receive имеют вид

Send (A, message) – пересылать сообщение с именем message в почтовый ящик с именем А.

Receive (A, message) – получить сообщение с именем message из почтового ящика с именем А.

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

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

­ Разрешить пользование почтовым ящиком только двум процессам.

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

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

Буферизация

Существуют три стратегии реализации очередей сообщений с точки зрения длины буфера:

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

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

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

Исключительные ситуации

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

Остановка процесса

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

Рассмотрим две ситуации:

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

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

Потерянные сообщения

Сообщение от процесса P к процессу Q может быть потеряно вследствие ошибок в оборудовании или на линии связи. Существует три основных метода поведения в этой ситуации:

1. ОС несет ответственность за выявление этого события и за повторную передачу сообщения.

2. Процесс-отправитель отвечает за выявление сбоя и за повторную передачу, если это ему требуется.

3. ОС выявляет ситуацию и сообщает процессу-отправителю о случившемся. Процесс-отправитель может обработать ситуацию.

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

Искажение сообщения

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

Вызов удаленных процедур (RPC)

Идея вызова удаленных процедур (Remote Procedure Call - RPC) состоит в расширении хорошо известного и понятного механизма передачи управления и данных внутри программы, выполняющейся на одной машине, на передачу управления и данных через сеть.

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

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

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

Эти и некоторые другие проблемы решает широко распространенная технология RPC, лежащая в основе многих распределенных операционных систем.

Контрольные вопросы

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

2. Какие события вызывают перепланировку процессов (потоков)?

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

4. Опишите модели межпроцессного взаимодействия:

- разделяемая память;

- передача сообщений.

5. Каковы стратегии реализации очередей сообщений с точки зрения длины буфера?

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

7. Опишите механизм RPC. Каковы различия между реализацией удаленных вызовов и реализацией вызовов локальных процедур?

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

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

Параллельный доступ к данным может нарушить их целостность. Вернемся к задаче «Производитель-потребитель». Изменим несколько ее решение, добавив счетчик элементов counter, с тем, чтобы использовать весь объем буфера.

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

Repeat

........

[формируется очередной элемент в nextp]

........

while counter = n do no-op;

buffer [in]:= nextp;

in:=(in+1)mod n;

counter:= counter + 1;

until false;

 

Приведем теперь схему работы потребителя:

repeat

while counter= 0 do no-op

next c: = buffer [out];

out: = (out+1) mod n;

counter:= counter - 1;

........

[потребляется очередной элемент из nextc]

.........

until false;

 

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

Оператор counter:= counter + 1 реализуется на машинном языке следующим набором команд:

register₁:= counter; (T₀)

register₁:= register₁ + 1; (T₁)

counter:= register₁; (T₂)

Аналогичным образом реализуется оператор counter:= counter – 1:

register₂:= counter; (T₃)

register₂:= register₂ - 1; (T₄)

counter:= register₂; (T₅)

Заметим, что register₁ и register₂ могут быть одним и тем же физическим регистром.

Если последовательность выполнения команд будет T₀, T₁, T₂, T₃, T₄, T₅, то переменная counter получит верное значение 5. При последовательности выполнения T₀, T₁, T₃, T₄, T₅, T₂ переменная counter получит значение 6, а при последовательности выполнения T₃, T₄, T₀, T₁, T₂, T₅ - значение 4. Некорректность получилась за счет того, что мы разрешили обоим процессам работать с переменной counter параллельно.

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

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