3.1. Необходимость в более реалистическом решении

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

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

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

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

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

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

3.2. Синхронизирующие примитивы

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

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

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

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

Определение. V-операция есть операция с одним аргументом, который должен быть семафором. (Если "S1" и "S2" обозначают семафоры, то мы можем написать "V(S1)" и "V(S2)".) Назначение этой операции состоит в увеличении значения аргумента на 1; это действие должно рассматриваться как неделимая операция.

Заметим, что, согласно последнему предложению, "V(81)" не эквивалентно "S1 := S1 + 1"- Предположим, что два процесса А и В содержат оператор "V(S1)", и что оба они хотят выполнить этот оператор в момент, когда, скажем, "S1 = 6". Если исключить влияние на S1 других процессов, то А и В выполнят свои V-операции в некотором неопределенном порядке (во всяком случае, вне нашего контроля), и после завершения второй V-операции окончательное значение S1 будет равно "8". Если S1 не семафор, а только обычная общая целая переменная, и если процессы А и В оба содержат оператор "S1 := S1 + 1" вместо V-операции над S1, то могло бы случиться следующее. Процесс А вычисляет "S1 + 1" и получает "7"; до осуществления, однако, присваивания этого нового значения, процесс В достигает той же точки в программе и вычисляет "S1 + 1", также получая "7". После этого оба процесса присваивают значение "7" переменной S1, и одно из необходимых приращений, таким образом, потеряно. Требование "неделимости операции" предназначено для того, чтобы исключить подобный случай при использовании V-операции.

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

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

Мы будем считать, что P- и V-операции можно реализовать да вычислительной машине.

3.3. Применение синхронизирующих примитивов к задаче взаимного исключения

Построение N процессов, содержащих критические интервалы, которые не должны выполняться одновременно (см. ╖2.2), теперь становится тривиальной задачей. Ее можно решить с помощью единственного двоичного семафора, который назовем, скажем, "свободно". Значение семафора "свободно" равняется числу процессов, которым разрешено в данный момент войти в свои критические интервалы: "свободно = 1" означает, что ни один из процессов не находится в своем критическом интервале; "свободно = 0" означает, что один из процессов находится в своем критическом интервале.

Общая схема программы такова:

begin integer свободно; свободно := 1;
   parbegin
   процесс 1: begin ....... end;
   процесс 2: begin ....... end;
   процесс N: begin ....... end;
   parend
end

процесс i: begin
           Li: P(свободно); критический интервал i;
               V(свободно);
               остаток цикла i; goto Li
           end