Параллельное программирование: Учебное пособие, страница 41

И, наконец, подведем итог программным ухищрениям по взаимному исключению доступа процессов к разделяемым данным. Все усложнения, которые возникали в процедурах except-1 – except-3 и mutex, связаны с тем, что проверка значений флажков и установка их значений в процессорных устройствах происходит на разных тактах собственных тактовых генераторов. Как только это было понято, появились предложения реализовать аппаратно такие области памяти для специальных переменных (семафоров), обращение к которым объединяло бы в себе одновременно операции проверки и присвоения значения с уменьшением или увеличением последнего в течение одного элементарного кванта дискретного времени процесса. Этим обеспечивалась бы неделимость группы из нескольких операций. Такие группы были названы процедурами P(смф) и V(смф). Их аргументом стала общая целочисленная переменная – семафор.

Действия, выполняемые над неотрицательной целой переменной смф, могут быть определены следующим образом:

proc P(смф)

integer смф;             /*  */

begin

     if (смф-1) < 0 then 0 else  смф := смф – 1

end

proc V(смф)

integer с;

begin

c := смф;   с := с + 1;   смф := с

end

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


Рисунок 2.22.

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

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

2.4.4  Ограниченные ресурсы и критические секции

Разделяемые области памяти, к которым обращаются в том или ином порядке параллельные процессы при взаимодействии, обычно называют буферами. Пока негласно предполагалось, что в разделяемых областях ничего разрушительного с данными произойти не может, так как процедуры взаимного исключения не позволяют находиться в критическом интервале более, чем одному процессу, и любой процесс в любом количестве и произвольном порядке может помещать, видоизменять или использовать их для своих целей. Буфер должен обеспечить добавление порций данных, на которые разбит весь поток данных взаимодействия, отражать их линейную упорядоченность, изъятие или видоизменение порций, сглаживая неравномерность таких действий, как со стороны поставщика, так и потребителя данных. Хорошо известны способы организации буферов по принципу “первый пришел – первый ушел” и “первый пришел – последний ушел”. В данном случае процессу более важно получать от ограниченного по объему буфера ответ на вопрос: можно ли поместить очередную порцию данных в буфер или остановиться и ждать освобождения места? А для процесса-потребителя важен ответ на вопрос: есть порции данных для использования или остановиться и ждать, когда они в пустой буфер будут помещены?

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

На рисунке 2.23 приведен фрагмент схемы алгоритма для некоторой параллельной программы, описывающей взаимодействие N процессов-поставщиков и любое число процессов потребителей, в том числе и из группы процессов-поставщиков. Общими переменными, обеспечивающими работу с буфером лишь одному из заданного множества процессов, являются n, bb и job, значения которых равны 0 или 1. Из них bb – простая переменная, а остальные – переменные семафорного типа, составные операции над которыми являются неделимыми. Кроме этого, каждый из процессов-поставщиков снабжен собственным семафором, который предназначен для реализации функций взаимного исключения одновременного входа нескольких процессов в критический интервал, и простую переменную для временного хранения числа порций информации, которая представляет ячейку очереди для записи в буфер. Эти пары переменных организованы в одномерные массивы с именами смф (семафоры) и wish (желания).