Эдсгер В. Дейкстра

Структура мультипрограммной системы THE

Введение

В связи с условием обязательной публикации статей - "регулярных отчетов по исследованиям и разработкам" я попробую представить отчет о состоянии работ по мультипрограммированию на факультете Математики в Технологическом университете Эйндховена, Нидерланды.

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

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

Таким образом, я попытаюсь далее отчитаться в том, что мы сделали и как и попытаюсь также сформулировать, чему мы научились.

Мне хочется закончить введение двумя краткими замечаниями об условиях работы, я делаю их для полноты картины. Далее я не буду акцентировать внимание на этих пунктах.

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

Другое замечание - о том, что члены группы - в основном математики - были до этого очень хорошими студентами университета, проучившимися от 5 до 8 лет, и имели уровень магистра или Ph.D. Менее квалифицированный молодой человек, первоначально включенный в группу, нашел нашу деятельность превышающей его мыслительные способности и оставил группу. Я отмечаю это потому, что, по крайней мере в Голландии, интеллектуальный уровень, требуемый для проектирования систем обычно весьма преуменьшается. Я более чем убежден, что этот вид работы очень труден и что любые попытки выполнять ее иначе как с лучшими людьми обречены либо на провал, либо на незначительный успех при значительных затратах.

Инструментарий и цель

Система разрабатывалась для голландской машины EL X8 (N.V. Electrologica, Rijswijk (ZH)). Характеристики конфигурации следующие:

1. оперативная память: время цикла - 2.5 мксек, 27 бит, 32К.
2. [магнитный] барабан на 512K слов, 1024 слов на дорожке, время оборота 40 мсек.
3. механизм косвенной адресации, хорошо приспособленный к реализации стека
4. хорошая система управляемой периферии и управления прерываниями
5. потенциально большое число каналов с низкой пропускной способностью, десть из которых используются (3 считывателя с перфоленты со скоростью 1000 символов/сек, 3 ленточных перфоратора со скоростью 150 символов/сек, 2 телетайпа, плоттер и строчный принтер)
6. отсутствие многих неуклюжих и бесполезных свойств.

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

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

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

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

Отчет о состоянии

Мы сделали несколько мелких ошибок обычного типа (например, уделили слишком много внимания ускорению того, что на самом деле не было узким местом) и две большие ошибки.

Наша первая большая ошибка состояла в том, что мы слишком долгое время ограничивали наше внимание "идеальным оборудованием"! со временем, когда мы стали рассматривать, что делать, если, скажем, одно из периферийных устройств выйдет из строя, мы столкнулись с серьезными проблемами. Забота о "патологиях" потребовала больше энергии, чем мы предполагали, и часть наших трудностей была прямым следствием наших ранних решений, то есть сложности тех ситуаций, в которые система могла сама себя завести. Если бы мы уделяли внимание патологии на ранней стадии проекта, наши правила управления были бы несколько менее изощренными.

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

Как капитан команды, я имел больший опыт (датированный 1958 годом) работы с базовым программным обеспечением обработки прерываний реального времени, и я знал на собственном горьком опыте, что в результате невоспроизводимости моментов прерываний программные ошибки могут вводить в заблуждение и представляться как случайные сбои оборудования. Этого я ужасно боялся. Имея такие опасения относительно отладки, мы решили быть настолько внимательными, насколько это возможно и - предупреждение лучше, чем исправление! - постараться предотвратить внесение ошибок в программу.

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

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

Обзор структуры системы

Выделение памяти В классической машине фон Неймана информация идентифицируется адресом ячейки памяти, ее содержащей. Когда мы начали думать об автоматическом управлении вторичной памятью, мы были хорошо знакомы с системой (а именно - с GIEK ALGOL), в которой информация идентифицировалась ее адресом на [магнитном] барабане (как в классической машине фон Неймана) и в которой функция оперативной памяти состояла не более, чем в том, чтобы сделать информацию постранично доступной.

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

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

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

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

Это дало нам возможность разрабатывать всю систему в терминах абстракции "последовательных процессов". Их гармоничное взаимодействие регулировалось посредством явных операторов взаимной синхронизации. С одной стороны, эта явная взаимная синхронизация была необходима, поскольку мы не делали никаких предположений о соотношениях скоростей, с другой стороны, эта взаимная синхронизация была возможна, поскольку "временная задержка выполнения другого процесса" не может согласовываться с внутренней логикой задерживаемого процесса. Фундаментальным следствием этого подхода - т.е. явной взаимной синхронизации - было то, что гармоничное взаимодействие набора таких последовательных процессов может быть установлено дискретными рассуждениями; дальнейшее следствие - все гармоническое сообщество взаимодействующих последовательных процессов не зависит от реального числа участвующих в нем процессоров, обеспечивая возможность переключения доступных процессоров с процесса на процесс.

Иерархия системы Вся система имеет четкую иерархическую структуру.

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

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

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

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

На уровне 4 мы находим независимые программы пользователей, на уровне 5 - оператора (не реализован нами).

Структура системы была описана так длинно для того, чтобы сделать понятным следующий раздел.

Опыт проектирования

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

Стадия конструирования была традиционной, возможно даже старомодной: обычный машинный код. Перепрограммирование из-за изменения спецификаций были редки, обстоятельство, которое должно подтвердить применимость "парового метода". Тот факт, что первые две стадии заняли больше времени, чем планировалось, отчасти был скомпенсирован задержкой в предоставлении нам машины.

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

Я не стану отрицать, что конструирование этих тестовых программ потребовало значительных интеллектуальных усилий, так как убедиться самим, что не было пропущено никакое "показательное состояние" и что тестовые программы генерируют их все, было непростым делом. Обнадеживающей вещью является то, что это (насколько мы знаем!) может быть сделано.

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

Как было установлено, последовательные процессы реализованы именно такими, какими они должны быть. Тестирование контроллера сегментов на уровне 1 означало, что все "показательные состояния" могут быть сформулированы в терминах последовательных процессов, производящих (в разных комбинациях) требования на оперативные страницы, ситуация, которая может быть вызвана явной синхронизацией тестовых программ. На этом этапе существование часов реального времени - хотя они все время генерировали прерывания - было настолько неощутимым, что один из проверяющих даже забыл об их существовании! После этого мы реализовали корректную реакцию при (взаимно несинхронизированных) прерываниях от часов реального времени и барабана. Если бы мы не ввели раздельные уровни 0 и 1 и не создали бы терминологию ("абстрактных" последовательных процессов), в которой существование прерывания от часов может быть отброшено, но пытались бы вместо этого создать неирархическую конструкцию, в которой бы центральный процессор непосредственно реагировал бы при любой временной последовательности этих двух прерываний, количество "показательных состояний" могло бы разрастись до такой степени, что исчерпывающее тестирование их было бы иллюзией. (Не говоря уже о том, что скорость барабана и скорость часов были вне нашего контроля и неясно было, есть ли у нас средства для генерации прерываний от них.) Для полноты я должен отметить еще одно счастливое следствие. Как было определено раньше, над уровнем 1 оперативные и барабанные страницы теряют свою идентификацию и буферизация входных и выходных потоков (на уровне 5) поэтому выполняется в терминах сегментов. При тестировании уровней 2 или 3 аппаратура канала барабана довольно часто ломалась, но тестирование могло продолжаться путем такого ограничения количества сегментов, чтобы все они могли поместиться в оперативной памяти. При построении выходного потока строчного принтера он может быть реализован как "сбрасывание на барабан" а реальная печать как "печать с барабана", это преимущество стало бесспорным для нас.

Заключение

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

Должен с сожалением сказать, что, по моему опыту, промышленные производители программного обеспечения склонны реагировать на это со смешанными чувствами. С одной стороны, они склонны оценивать то, что мы сделали, как своего рода модель, с другой стороны, они выражают сомнение в том, что использованные нами приемы применимы вне благоприятной атмосферы Университета и выражают мнение, что мы смогли сделать это только благодаря скромным масштабам всего проекта. Я не намерен недооценивать организационные возможности, необходимые для значительно большей работы с числом людей вдесятеро и более больше, но я рискну предположить, что чем больше проект, тем важнее структурирование! Иерархия из пяти логических уровней может быть на практике развита на большую глубину, если разрабатывать систему более сознательно, чем это делали мы, с целью сделать программное обеспечение легко адаптируемым к (возможно, значительным) расширениями конфигурации.

Приложение

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

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

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

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

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

Следствие 2. P-операция представляет собой потенциальную задержку, комплиментарная ей V-операция представляет собой преодоление барьера.

Примечание 1. P- и V-операции являются "неделимыми действиями"; т.е. если они встречаются "одновременно" в параллельных процессах, они не накладываются друг на друга, в том смысле, что их можно рассматривать как выполняемые одна после другой.

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

Примечание 3. Следствием описанного выше механизма является то, что процесс, чье выполнение разрешено может потерять этот статус только при реальном выполнении, т.е. выполнив P-операцию на семафоре, значение которого неположительное.

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

Взаимное исключение

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

 begin semaphore mutex; mutex := 1; 
 parbegin
 begin L1: P(mutex); критическая секция 1; V(mutex);
 остаток цикла 1; go to L1
 end;
 begin L2: P(mutex); критическая секция 2; V(mutex);
 остаток цикла 2; go to L2
 end
 parend
 end

В результате P- и V-операций на "mutex" действия, отмеченные как "критические секции", взаимно исключают друг друга во времени; данная схема допускает простое расширение на более чем два параллельных процесса, максимальное значение mutex равно 1, минимальное значение равно -(n-1), если мы имеем n параллельных процессов.

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

Частные семафоры

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

Когда процесс достигает стадии, на которой разрешение на его выполнение зависит от текущего значения переменных состояния, он следует такому шаблону:

 P(mutex); 
 "проверка и модификация переменных состояния,
 включая условное V(частный семафор)"; 
 V(mutex); 
 P(частный семафор). 

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

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

 P(mutex); 
 "модификация и проверка переменных состояния, включая ноль 
 или более V-операций на частных семафорах других процессов"; 
 V(mutex). 

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

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

Обеспечение гармоничного взаимодействия

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

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

Гармоничное взаимодействие в основном обеспечивается на трех стадиях.

1. Обеспечивается то, что хотя процесс, выполняющий задачу, может в процессе этого генерировать конечное число задач для других процессов, единственная начальная задача не может вырасти в бесконечное число задач. Доказательство простое: поскольку процесс может генерировать задачи только для процессов на более низких уровнях иерархии, то круговорот задач исключен. (Если процесс, которому нужен сегмент с барабана, генерирует задачу для контроллера сегментов, должны быть приняты специальные меры, чтобы гарантировать, что запрошенный сегмент останется в оперативной памяти по крайней мере до тех пор, пока запрашивающий процесс будет обращаться к этому сегменту. Без этих мер конечная задача может быть вынуждена генерировать бесконечное число задач для контроллера сегментов, и система может застрять в непродуктивной перетасовке сегментов.)
2. Обеспечивается невозможность того, чтобы все процессы вернулись в свои исходные позиции в то время, как где-то в системе еще ожидает порожденная, но не принятая задача. (Это обеспечивается через уже описанную неустойчивую ситуацию.)
3. Обеспечивается то, что после принятия начальной задачи все процессы в конце концов будут (опять) в своей исходной позиции. Каждый процесс, блокированный в ходе выполнения задачи получает помощь от других процессах в преодолении барьера. В сущности, доказательством этого является демонстрация отсутствия "циклического ожидания": процесс P ожидает процесса Q, ожидающего процесса R, ожидающего процесса P. (Наше обычное название для циклического ожидания - "смертельное объятие".) В более общем случае, чем наша система, это доказательство превращается в доказательство при помощи индукции (для уровня иерархии, начиная с уровня 0), как показал в тезисах своей докторской работы А.Н.Габерман.