3.9. Параллельное выполнение процессов. Формулировка задачи «производитель-потребитель» и методы ее решения

3.9. ПАРАЛЕЛЬНЕ ВИКОНАННЯ ПРОЦЕСІВ. ФОРМУЛЮВАННЯ ЗАДАЧІ «ВИРОБНИКИ-СПОЖИВАЧІ» ТА МЕТОДИ ЇЇ ВИРІШЕННЯ.

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

Основной задачей управления параллельным выполнением является задача  взаимного  исключения  (mutual  exclusion,  сокращенно  - mutex):  два процесса не могут выполнять одновременный  доступ  к разделяемым  ресурсам.  Взаимное  исключение является расширением задачи транзактивности на любые ресурсы. Если процессор одновременно получает два запроса, то он выполняет их последовательно. Каждая процессорная команда имеет свойства транзакции: она или выполняется полностью,  или вообще не выполняется. Задача семафоров использует блокировку ожидающего процесса - перевод его из списка процессов, планируемых  на выполнение (готовых) в список ожидающих (заблокированных). Этим экономится процессорное время, в противном случае попусту  растрачиваемое в занятом ожидании, а затраты сводятся к переключению процессов.

Такая возможность обеспечивается:

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

б). добавлением к набору элементарных  действий,  из  которых строятся процессы,  операций над семафорами: V-операции и P-операции. V-операция есть  операция с одним операндом,  который должен быть семафором.

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

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

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

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

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

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