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

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

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

Program example_semaphore2;

Var S: semaphore;

Procedure process_1;

Begin

While true Do

Begin

...

P(S); {ждать сигнала от процесса 2}

...

End;

End;

Procedure process_2;

Begin

While true Do

Begin

...

V(S); {послать сигнал процессу 1}

...

End;

End;

Begin

InitSem(S,1);

Parbegin

process_1;

process_2;

Parend

End.

Процесс_1 можно рассматривать как потребляющий некоторый ресурс, обозначенный S, посредством команды P(S), а процесс_2 – как производящий этот ресурс посредством команды V(S).

Процесс-производитель вырабатывает информацию и затем добавляет её в буферную память; параллельно с этим процесс-потребитель удаляет информацию из буферной памяти и затем обрабатывает её. Например, потребитель является процессом вывода, удаляющим запись асинхронно из буферной памяти и затем печатающим её.

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

Пусть буферная память состоит из n буферов одинакового размера, причём каждый буфер может хранить одну запись. Предположим, что добавление к буферу и изъятие из него информации образуют критические секции. Для подсчёта имеющихся в наличии свободных буферов будем использовать семафор empty. Пусть b – двоичный семафор, используемый для взаимного исключения. Тогда процессы производитель и потребитель могут быть описаны следующим образом (этот вариант работает не совсем верно, как мы увидим ниже):

Program example_semaphore3;

Var empty, b: semaphore;

Procedure producer;

Begin

While true Do

Begin

Создать следующую запись;

P(empty); {уменьшить кол-во свободных буферов}

P(b); Добавить запись в буфер; V(b);

End;

End;

Procedure consumer;

Begin

While true Do

Begin

V(empty); {*} {увеличить кол-во свободных буферов}

P(b); Взять запись из буфера; V(b);

{**} Обработать запись;

End;

End;

Begin

InitSem(empty, n); InitSem(b,1);

Parbegin

producer;

consumer;

Parend

End.

В рассмотренном варианте может сложиться следующая ситуация: если буфер окажется полностью заполнен, а процесс-потребитель будет прерван после выполнения операции V(empty) (в программе обозначено {*}), то производитель сможет повторно записать информацию в последнюю ячейку, хотя она оттуда ещё не считана. Кроме того, consumer может запуститься раньше и начнёт читать из пустого буфера. Если переместить операцию V(empty) после чтения из буфера (обозначено {**}), то первый недостаток будет устранён, но второй все равно останется.

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

Program example_semaphore4;

Var empty, full, b: semaphore;

Procedure producer;

Begin

While true Do

Begin

Создать следующую запись;

P(empty); {уменьшить кол-во свободных буферов}

P(b); Добавить запись в буфер; V(b);

V(full); {увеличить кол-во занятых буферов}

End;

End;

Procedure consumer;

Begin

While true Do

Begin

P(full); {уменьшить кол-во занятых буферов}

P(b); Взять запись из буфера; V(b);

V(empty); {увеличить кол-во свободных буферов}

Обработать запись;

End;

End;

Begin

InitSem(empty, n); InitSem(full,0);

InitSem(b,1);

Parbegin

producer;

consumer;

Parend

End.

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

Мониторы Хоара

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

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

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

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

Основные характеристики:

1. Локальные переменные монитора доступны только его процедурам.

2. Процесс входит в монитор путём вызова одной из его процедур.

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

Пример монитора:

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

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

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

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

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

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

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

Пример монитора Хоара:

Monitor Resource;

condition free; {условие – свободный}

Var busy: Boolean;

Procedure Request; {запрос}

Begin

If busy then WAIT(free);

busy:=true;

TakeOff; {выдать ресурс}

End;

Procedure Release;

Begin

TakeOn; {взять ресурс}

busy:=false;

SIGNAL(free)

End;

Begin

busy:=false;

End

Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам REQUEST и RELEASE.

Если процесс обращается к REQUEST в тот момент, когда ресурс используется, то значение busy=true, и REQUEST выполнит операцию монитора WAIT(free). Обратившийся процесс помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free.

Когда процесс, использующий ресурс, обращается к RELEASE, операция монитора SIGNAL(free) деблокирует процесс из начала очереди. Он готов сразу после операции WAIT(free), которая его и блокировала, возобновить выполнение процедуры REQUEST. Если же SIGNAL(free) выполняется в то время, когда нет ожидающего условия free процесса, то никакие действия не выполняются.

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

Преимущества монитора перед другими средствами синхронизации:

§ в форме монитора легко реализовать любой механизм;

§ повышается наглядность;

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

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

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

Решение задачи производителя-потребителя при помощи монитора

Рассмотрим задачу производителя-потребителя в той же постановке: буферная память состоит из n буферов одинакового размера, каждый буфер может хранить одну запись, а добавление к буферу и изъятие из него информации образуют критические секции. Пусть считывание из буферной памяти выполняется по принципу FIFO (First In – First Out), а сама буферная память имеет кольцевую организацию. Это означает, что после заполнения (считывания) элемента с номером N соответствующий указатель перемещается на начало буфера. Тогда для контроля за состоянием буфера потребуется два указателя – номер очередного элемента для записи (назовем его NextIn) и номер очередного элемента для считывания – NextOut, а также счетчик количества элементов в буфере Count. Условия обозначим через NotFull и NotEmpty.

Монитор под названием Buffers будет содержать процедуры добавления элемента в буфер и считывания элемента из буфера: Append и Take. Общими переменными являются массив буферных элементов Buf, а также счетчик Count и указатели NextIn, NextOut. Программная реализация задачи с помощью монитора будет иметь вид:

Monitor Buffers;

Condition NotFull, NotEmpty;

Var Buf: Array [1..N] Of Char;

NextIn, NextOut, Count: Integer;

Procedure Append(X: Char);

Begin

If Count = N Then WAIT(NotFull); {буфер полон}

Buf[NextIn]:= X;

NextIn:= NextIn mod N + 1;

inc(Count);

SIGNAL(NotEmpty); {возобновление работы потребителя}

End;

Procedure Take(Var X: Char);

Begin

If Count = 0 Then WAIT(NotEmpty); {буфер пуст}

x:= Buf[NextOut];

NextOut:= NextOut mod N + 1;

dec(Count);

SIGNAL(NotFull); {возобновление работы производителя}

End;

Begin {тело монитора}

NextIn:= 0;

NextOut:= 0;

Count:= 0;

End;

Procedure Producer;

Var X: Char;

Begin

While true Do

Begin

Produce(X); {выработка X}

Append(X);

End;

End;

Procedure Consumer;

Var X: Char;

Begin

While true Do

Begin

Take(X);

Consume(X); {обработка X}

End;

End;

Begin {main}

Parbegin;

Producer;

Consumer;

Parend;

End;

Обмен сообщениями

Передача сообщений – один из способов обеспечения синхронизации процессов. Он пригоден для реализации в различных системах (однопроцессорных, многопроцессорных, распределенных).

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

Синхронизация

Рассмотрим, что происходит после выполнения примитивов. После выполнения SEND существует две возможности: выполнивший его процесс блокируется или продолжает работу. После примитива RECEIVE. Те же две возможности. Но при этом:

§ если сообщение уже было отправлено ранее, то процесс получает его и продолжает работу;

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

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

1. Блокирующее отправление, блокирующее получение (рандеву) – случай тесной синхронизации процессов.

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

3. Неблокирующее отправление, неблокирующее получение.

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

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

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

Адресация

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

При прямой адресации:

Примитив SEND() указывает конкретного получателя. Для примитива RECEIVE возможны два варианта. 1) явное указание отправителя, если процессы сотрудничают; 2) неизвестно, откуда может прийти сообщение. Например, когда сервер печати принимает сообщения – запросы на печать, то неизвестно, от какого из процессов они могут поступить. В таком случае используется неявная адресация, т.е. "отправитель" получит конкретное значение только после выполнения операции RECEIVE.

При косвенной адресации:

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

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

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

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

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

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

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

Основные достоинства почтовых ящиков:

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

§ два процесса могут обмениваться более чем одним сообщением за один раз;

§ ОС может гарантировать невмешательство в общение двух процессов;

§ очереди буферов позволяют процессу-отправителю продолжать работу, не обращая внимание на получателя.

Недостатки:

§ Появление ещё одного ресурса, которым нужно управлять;

§ Статический характер этого ресурса.

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