Анализ проблемы производитель – потребитель с точки зрения синхронизации по общему буферу

История синхронизации

Методы синхронизации процессов рассматривались еще в 1960-х гг. в пионерской работе Э. Дейкстры [17]. Было отмечено, что совместный доступ параллельных процессов к общим данным может привести к нарушению их целостности. Поддержание целостности общих данных требует реализации и использования механизмов упорядочения работы взаимодействующих процессов (или потоков).

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

Вспомним представление ограниченного буфера на языке Си (см. "Методы взаимодействия процессов ") и расширим его переменной counter:

#define BUFFER_SIZE 1000 /* или другое конкретное значение */

typedef struct {

...

} item;

item buffer[BUFFER_SIZE];

int in = 0;

int out = 0;

int counter = 0;

Теперь модифицируем реализации процесса-производителя и процесса-потребителя (см. "Методы взаимодействия процессов "), добавив соответствующие изменения переменной counter:

Процесс-производитель:

item nextProduced; /* следующий генерируемый элемент */

while (1) { /* бесконечный цикл */

while (counter == BUFFER_SIZE) == out)

; /* ждать, пока буфер переполнен */

buffer[in] = nextProduced; /* генерация элемента */

in = (in + 1) % BUFFER_SIZE;

counter++;

}

Процесс-потребитель:

item nextConsumed; /* следующий используемый элемент */

while (1) { /* бесконечный цикл */

while (counter == 0)

; /* ждать, пока буфер пуст */

nextConsumed = buffer[out]; /* использование элемента */

out = (out + 1) % BUFFER_SIZE;

counter--;

}

Возникает вопрос: насколько корректны модифицированные алгоритмы, использующие переменную counter? Не вполне. Проблема в том, что counter фактически является общим ресурсом, к которому одновременно обращаются два параллельных процесса. Если при этом обращение произойдет одновременно, то переменная counter может в итоге оказаться в некорректном состоянии. Поэтому необходимо, чтобы каждый из процессов при увеличении или уменьшении ее значения имел бы к ней монопольный доступ, и другой процесс не мог бы в это время "испортить" значение переменной. Иными словами, операции counter++ и counter— должны выполняться атомарно (см. главу 9). Напомним, что атомарная операция – это такая операция, которая должна быть выполнена полностью, без каких-либо прерываний; при этом операция, выполняемая одним из процессов, должна быть неделимой, с точки зрения другого процесса.

Операции count++ и count— могут быть реализованы на языке ассемблерного уровня следующим образом:

count++:

register1 = counter

register1 = register1 + 1

counter = register1

count--:

register1 = counter

register1 = register1 - 1

counter = register1

где register1 – регистр аппаратуры.

Проблема в том, что если и производитель, и потребитель пытаются изменить переменную counter одновременно, то указнные ассемблерные операторы тоже должны быть выполнены совместно (interleaved).

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

Рассмотрим эффект interleaving на конкретном примере. Предположим, что начальное значение переменной counter в некоторый момент равно 5. Исполнение процессов в совместном режиме (interleaving) может привести к следующему эффекту:

производитель: register1 = counter (register1 = 5)

производитель: register1 = register1 + 1 (register1 = 6)

потребитель: register2 = counter (register2 = 5)

потребитель: register2 = register2 – 1 (register2 = 4)

производитель: counter = register1 (counter = 6)

потребитель: counter = counter2 (counter = 4)

Таким образом, значение counter в итоге может оказаться равным 6 или 4, в то время как правильное значение counter равно 5.

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

Дата добавления: 2014-01-20