Логический элемент

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) буфер всегда имеет некоторую конечную емкость. Если производитель работает быстрее, то при заполнении буфера он должен приостанавливаться, ожидая освобождения места в буфере. Это легко обеспечить, введя новый семафор, выполняющий роль счетчика свободных мест в буфере.