авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 ||

«взаимодействующие поеледрвателш процессы Prentice-Hall InfernaHoB^il Series in Compuler Science Coitimtihicating Sequential Processes ...»

-- [ Страница 6 ] --

Р Блок внутри Р, требующий вывести файл на печатающее устройство, выглядит как instance мой : ацпусист.виртуальн;

b e g i n...мой.использ{1\);

,..мой.использ{12);

,..end 234 Гл. 7. Обсуждение Необходимые действия по занятию и освобождению печатаю­ щего устройства вставляются виртуальным монитором авто­ матически до и после этого использующего блока так, чтобы воспрепятствовать антиобщественному использованию этого устройства. В принципе воможно, чтобы использующий блок состоял из параллельных процессов, каждый из которых использует мой экземпляр виртуального монитора, но здесь такая цель, вероятно, не ставилась. Монитор, предназначен­ ный для использования единственным процессом, называется в PASCAL PLUS конвертом и может быть более эффективно реализован без использования исключения или синхрониза­ ции;

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

Значение этих экземпляров описаний можно вычислить последовательным применением правила копирования, в ре­ зультате чего мы получим:

var ацпусист. своб : Boolean;

procedure ацпусист.занят;

when ацпусист.своб do ацпу сист. своб := false;

procedure ацпусист.свободен;

begin ацпу сист. своб := true end;

begin ацпусист.своб := true begin procedure мой. ацпу сист. использ{1\ line);

b e g i n... end;

ацпусист.занят;

aunucucT.занят:

... мой.ацпусист.использ{1\);

...мой.ацпусист.использ{12);

ацпусист. свободен;

end;

end Явное копирование приводится здесь только в качестве пояс­ нения для начинающих;

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

Эти обозначения использовались в 1975 г. для описания операционной системы, аналогичной н а к 1 е й из разд. 6.5;

позже они были реализованы в языке PASCAL P L U S. Сочетанием пометки звездочкой и вложенности можно достигнуть весьма 7.2. Общая память изощренных эффектов, однако обозначения, основанные на языках Паскаль и Симула, выглядят довольно неуклюже, а рассуждения в терминах подстановок и переименований вос­ принимаются не лучшим образом. Критика Э. Дейкстрой именно этих особенностей и навела меня впервые на мысль о создании теории взаимодействующих последовательных процессов.

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

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

7.2.6. Ада™ Предлагаемые в Аде средства параллельного программи­ рования представляют собой слияние понятия дистанцион­ ного вызова процедуры в языке PASCAL PLUS с менее структурированной формой взаимодействия посредством вво­ да и вывода. Процессы называются задачами и взаимодейст­ вуют с помощью операторов вызова call (напоминающих вы­ зовы процедуры с входными и выходными параметрами) и операторов приема accept (синтаксически и цо своему дейст­ вию напоминающих описания процедур). Типичный пример оператора приема:

accept put(y^: in integer: PREVi out integer) do Pf^EV:=K;

K:=V end Соответствующий вызов может иметь вид put {37, X) Идентификатор put называется именем входа.

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

( 1 ) Входные параметры копируются из вызова в прини­ мающий процесс.

(2) Исполняется тело оператора приема.

( 3 ) Значения выходных параметров копируются обратно в оператор вызова.

236 Гл. 7. Обсуждение (4) Обе задачи продолжают исполнение своих очередных операторов.

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

Аналогом операции П служит в Аде оператор выбора select, который имеет вид select accept get{v : out integer) do v :== B[i] end;

r : = / + I ;

...

or accept put{v : in integer) do B[j] := v end;

/ : = = / + 1 ;

.. • or...

end select Для исполнения будет выбрана ровно одна из альтернатив, разделенных знаком or в зависимости от выбора, сделанного вызывающей задачей (или задачами). Остальные операторы выбранной альтернативы, следующие за закрывающей скоб­ кой end ее accept-части, исполняются по окончании рандеву параллельно с продолжением вызывающей задачи. На выбор альтернативы можно налагать ограничение, вводя перед ней условие, начинающееся с when, например:

when not поло« =^ a c c e p t...

Этим достигается эффект условного критического участка.

Одна из альтернатив в операторе выбора может начи­ наться не с оператора приема, а с оператора задержки delay.

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

Одной из альтернатив в операторе выбора может быть оператор завершения terminate. Эта альтернатива выбирает­ ся, когда все задачи, которые могли бы вызывать данную, завершились;

в этом случае завершается и она. Это не так удобно, как внутренний оператор в PASCAL PLUS, позво 7.2. Общая память ляющий монитору, закончив работу, приводить себя в по­ рядок.

Оператор выбора может иметь альтернативу, начинаю­ щуюся с else, которая выбирается, если все остальные аль­ тернативы не могут быть выбраны немедленно, либо когда ложны все условия when, либо потому, что в других задачах нет соответствующего готового ожидающего вызова. Это, ви­ димо, эквивалентно альтернативе с нулевой задержкой.

Оператор вызова также может быть защищен от произ­ вольно долгой задержки оператором delay или else-частью.

Это может привести к некоторой неэффективности при реали­ зации на распределенной сети процессов.

Задачи в Аде описываются аналогично подчиненным про­ цессам (разд. 4. 5 ), но, как и мониторы в PASCAL PLUS, каждая может обслуживать любое число вызывающих про­ цессов. Кроме того, программист должен заботиться о нор­ мальном окончании задачи. Определение задачи разбивается на две части —спецификацию и тело. Спецификация дает имя задаче, а также задает имена и типы параметров всех входов, обращениями к которым эта задача может быть вы­ звана. Эта информация требуется тому, кто пишет програм­ му, использующую данную задачу, и транслятору этой про­ граммы. Тело задачи задает ее поведение и может быть транслировано независимо от использующей программы.

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

Признак приоритета называется указанием;

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

Ада располагает рядом дополнительных средств. Имеется возможность узнать, сколько вызовов ожидается на данном входе. Одна задача может вызвать принудительное прекра­ щение другой задачи (оператор abort), при котором прекра­ щаются и все ее подчиненные. Задачи могут считывать и из­ менять значения общих переменных. Результат этих действий будет еще более непредсказуемым, если учесть, что трансля тор имеет право откладывать, переупорядочивать и объеди^ нять подобные действия над переменными так, как если бы 238 Гл. 7. Обсуждение ОНИ не были общими. Есть некоторые дополнительные слож­ ности и эффекты взаимодействий другого рода, которые я не упомянул.

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

7.3. ВЗАИМОДЕЙСТВИЕ Исследование возможности придания программе струк­ туры сети взаимодействующих процессов мотивировалось, помимо всего прочего, впечатляющими успехами развития вычислительной техники. Появление' микропроцессоров на несколько порядков снизило стоимость вычислительных мощ­ ностей. Однако индивидуальная мощность каждого отдель­ ного микропроцессора оставалась все-таки несколько ниже, чем мощность типичного традиционного и по-прежнему доро­ гого вычислительного устройства. Поэтому наиболее эконом­ ным способом получения большей мощности представлялось использование для выполнения одного задания нескольких взаимодействующих микропроцессоров. Микропроцессоры со­ единялись обыкновенными проводами, по которым они могли друг с другом взаимодействовать. Каждый микропроцессор имел собственную локальную оперативную память с высокой скоростью доступа к ней, что позволяло избегать неэконом­ ных узких мест, обычно возникающих, когда процессоры имеют доступ к общей памяти только по очереди.

7.3.1. Транспортеры Простейшей схемой взаимодействия между элементар­ ными процессорами является однонаправленная передача сообщений от каждого процесса его соседу по линейному транспортеру, как это описано в разд.

4. 4. Впервые эта идея была предложена Конвеем, проиллюстрировавшим ее на при­ мерах, аналогичных 4. 4 Х2 и ХЗ, с той разницей, что в них предполагалось, что все компоненты транспортера вместо того, чтобы работать бесконечно, успешно завершаются. Он предложил использовать структуру транспортера при напи­ сании многопроходного транслятора. На машине с оператив­ ной памятью достаточного объема одновременно активны все проходы, и управление передается между ними вместе с со­ общениями, моделируя таким образом параллельное испол­ нение. Нл машине с меньшим объемом оперативной памяти одновременно активен только один проход, который посылает 7.3. Взаимодействие С В О И выходные данные в файл во внешней памяти. По завер­ шении каждого прохода начинается следующий, берущий входные данные из файла, выработанного его предшествен­ ником. Окончательный результат работы транслятора, однако, будет в точности тем же, несмотря на все отличия в способе его получения. Удачная абстракция в программировании как раз и характерна тем, что она допускает несколько различ­ ных способов реализации, эффективных при различных об­ стоятельствах. В данном случае предложение Конвея могло бы оказаться очень полезным при программной реализации для машинных конфигураций с широким диапазоном воз­ можных размеров памяти.

Транспортер является также стандартным способом взаи­ модействия в операционной системе UNIX™, где он назы­ вается программным каналом, а вместо обозначения ис­ пользуется |.

7.3.2. Множественные буферизованные каналы Конструкция транспортера позволяет линейной последо­ вательности процессов передавать сообщения только в одном направлении независимо от того, буферизована ли последо­ вательность сообщений или нет. Естественным обобщением транспортера будет позволить любому процессу взаимодейст­ вовать с любым другим процессом в обоих направлениях;

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

Когда схема взаимодействия между процессами от линей­ ной последовательности обобщается до, возможно, цикли­ ческой сети, наличие или отсутствие буферизации может оказаться для логического поведения системы жизненно важ­ ным. Наличие буферизации не всегда желательно: можно, например, написать программу, которая придет в тупиковое состояние, если позволить размеру буфера превышать пять, точно так же, как и другую программу, где дедлок бу­ дет наступать, если не позволять размеру буфера превы­ шать пяти. Д л я того чтобы справляться со всеми такими 240 Гл. 7. Обсуждение нерегулярностями, длина всех буферов должна быть неогра­ ниченной. К сожалению, если оперативная память оказы­ вается забитой буферизованными сообщениями, возникают серьезные проблемы в смысле эффективной реализации. За­ труднения возникают и в математическом плане, так как каждая сеть в этом случае представляет собой бесконечный автомат, даже если число составляющих процессов конечно.

И наконец, буферы становятся препятствием на пути быст­ рого и управляемого взаимодействия между человеком и ма­ шиной, поскольку могут порождать задержки между сигна­ лом и ответом на него. Если при обработке буферизованного сигнала что-нибудь случится, будет гораздо труднее просле­ дить и исправить ошибку. Буферизация— это техника пакет­ ной обработки, и там, где скорость взаимодействия важнее, чем полнота загрузки процессора, ее следует избегать.

7.3.3. Функциональная мультипроцессорная обработка Детерминированный процесс можно определить в терми­ нах математического отображения из множества его входных каналов во множество выходных каналов. Каждый канал отождествляется с бесконечно продолжаемой последователь­ ностью передаваемых по нему сообщений. Такие функции задаются обычным образом, рекурсией по структуре входных последовательностей, за исключением того, что не рассматри­ вается случай пустой входной последовательности. Опреде­ лим, например, процесс, выводящий результат умножения каждого входного числа на п:

произвп{лев) = {пХ левоУпроиЗп{лев') Функция, получающая в качестве параметров два упорядо­ ченных потока (без повторяющихся элементов) и выдающая их упорядоченное слияние (с удаленными повторяющимися элементами), определяется как слияние2{лев1,лев2) = if лeвloлeв2Q {\\еп{лев\^^слияние2{левУ,лев2) else if лев2^^ лев\^ then {лев2^'^слияние2{лев\,лев2') else {лев2^^слияние2{левУ,лев2') Ациклическую сеть можно представить в виде композиции таких функций. Например, функцию слияния трех упорядо­ ченных входных потоков можно определить как слияниеЗ{лев\,лев2уЛевЗ) == = слияние2{лев\,слияние2{лев2,левЪ)) На рис. 7,1 показана коммутационная схема этой функции, 7.3. Взаимодействие Циклическую сеть можно задать системой взаимно рекур­ сивных уравнений. Рассмотрим в качестве примера задачу, приписываемую Дейкстрой Хеммингу, а именно: определить функцию, выдающую возрастающую последовательность всех чисел, имеющих нетривиальными множителями только 2, 3 и слияние м8г слияние Z \тяние Рис. 7. 5. Первое такое число — 1, и если х —такое число, то и 2Х-^»

3 X х и 5 X л: будут такими числами. Поэтому для порожде­ ния этих произведений мы будем использовать три процесса [(произв2у произвг и произвъ), а затем подавать их результаты обратно процессу слияние^, обеспечивающему их окончатель­ ный вывод в нужном порядке (рис. 7.2), Щизв^ слияние произб^ произВ^ — Рис. 7. Функция, выдающая требуемый результат, не имеет вхо­ дов. Она определяется просто как Хемминг = {1Усл ияниеЗ{произв2{Хемминг),произв^{Хемминг), произв^{Хемминг)) Функциональный подход к мультипроцессорным сетям имеет значительные отличия от рассмотренного в этой книге в следующих отношениях:

242 Гл. 7. Обсуждение (1) Реализация во всей ее общности требует неограничен-^ ной буферизации каналов.

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

(3) Процесс не имеет возможности ожидать одного из двух вводов в зависимости от того, какой придет первым, (4) Все процессы детерминированы.

Недавние исследования были направлены на снижение неэффективности (1) и (2) и на ослабление ограничений (3) и (4).

7.3.4. Небуферизованное взаимодействие Уже много лет назад я принял решение взять за основу небуферизованное (синхронное) взаимодействие. Сделано это было по следующим соображениям:

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

(2) Оно весьма точно соответствует эффекту вызова и возврата из подпрограмм внутри единственного процессора с копированием значений параметров и результатов.

(3) В случае необходимости буферизация может быть реализована как обыкновенный процесс;

при этом програм­ мист может точно задать степень буферизации.

( 4 ) Другие недостатки буферов уже обсуждались в конце разд. 7.3.2.

Разумеется, ни один из этих аргументов не является абсо­ лютно убедительным. Например, если взять за основу буфе­ ризованное взаимодействие, то все эти соображения не имеют значения для общего случая вызовов и возвратов подпро­ грамм;

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

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

(1) Параллельная композиция Каналы не именованы. Вместо этого составные процессы в параллельной конструкции имеют различные имена, пред 7,8. Взаимодействие шествующие им и отделенные от них парой двоеточий!

[a::P\\b::Q\l,Mc-R] Внутри процесса Р команда b\v выводит значение i;

процессу с именем Ь. Это значение вводится командой ах внутри про* цесса Q. Имена процессов локальны по отношению к парал­ лельной команде, в которой они введены, а взаимодействия между составляющими процессами скрыты.

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

Но она имеет и некоторые недостатки как в практическом, так и в теоретическом плане.

( 1 ) Серьезным практическим недостатком является то, что подчиненному процессу требуется знать имя использую* щего его процесса;

это затрудняет построение библиотеки подчиненных процессов.

(2) Недостаток математической основы состоит в том, что параллельная композиция представляет собой операцию с переменным числом параметров и не может быть сведена к ассоциативному двуместному оператору типа ||.

(2) Автоматическое завершение В ранней версии предполагалось, что все процессы в па­ раллельном операторе завершаются. Основанием к этому служила надежда, что корректность процесса можно описать так же, как и корректность обычной программы, с помощью постусловия, т. е. предиката, который должен быть истинным при успешном завершении. (Надежда эта не оправдалась, и теперь более приемлемыми кажутся другие методы доказа­ тельства (см. разд. 1. 1 0 ). ) Требование завершения подчинен­ ного процесса налагает на использующий процесс обремени­ тельное обязательство сигнализировать о своем завершении всем своим подчиненным процессам. Поэтому было введено следующее соглашение. Цикл вида *[a?JC-Pn6?jc-QH...] завершается автоматически по завершении всех процессов Ь,..., от которых запрашивается ввод. Это позволяет под- чиненному процессу завершить перед окончанием всю необ­ ходимую реинициализацию кода — средство, оправдавшее себя в языках Симула и PASCAL PLUS.

244 Гл. 7. Обсуждение Проблема с этим соглашением состоит в том, что его труд­ но строго описать и реализовать, а методы доказательства правильности программ с ним оказываются не проще, чем без него. Теперь мне кажется (как и в разд. 4.5), что лучше снять ограничение об обязательном завершении простых под­ чиненных процессов, а в более сложных случаях (разд. 6.4) принимать другие меры.

7.3.6. Оккам В противоположность Аде язык Оккам очень прост, и по­ строен он на основе принципов, очень близких к изложенным в этой книге. Из различий прежде всего бросаются в глаза отличия в обозначениях. Синтаксис Оккама создавался в рас­ чете на экранный синтаксически ориентированный редактор;

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

SEQ соответствует (P;

Q;

/?) Р Q R PAR соответствует {P\\Q \\R) Р Q R ALT соответствует (с?л:-Р11 d?f/-Q) с?х Р Q IF соответствует (Pj;

BJQ) В Р NOT В Q WHILE В соответствует (В*Р) Р Конструкция ALT соответствует оператору выбора в Аде и содержит аналогичный набор альтернатив. Возможность выбора альтернативы может зависеть от истинности некото­ рого логического условия В:

В&с}х Р 7.3. Взаимодействие Ввод М О Ж Н О заменить на ПРОПУСК;

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

В языке Оккам не предусмотрено специальных обозначе­ ний для транспортеров (разд. 4.4), подчиненных (разд. 4.5) или разделяемых (разд. 6.4) процессов. Все необходимые схемы взаимодействия достигаются явным отождествлением имен каналов. Для этих целей имеется возможность описы­ вать процедуры с каналами в качестве параметров. Напри­ мер, простой процесс копирования можно описать как PROC KonupiCHAN лев,прав) = WHILE TRUE VAR х:

SEQ лев?х npaelx:

Теперь можно определить двойной буфер К О П И Р Ж О П И Р :

CHAN СРЕДИ:

PAR копир{ЛЕВ,с РЕДН) копир{СРЕДНУПРАЕ) Цепочка из п буферов строится при помощи вектора из п ка­ налов и итеративной формы параллельной конструкции, объ­ единяющей п—1 процесс, соответствующий значениям i от О до п — 2 включительно:

CHAN средн[п--1]:

PAR копир{лее,средн[0]) PAR / = [0 FOR п-2] копир(СРЕДН[1],ср^ДН[1 + 1]) копир{СРЕДН[п — 2],прав) Поскольку Оккам предполагает реализацию со статическим размещением памяти при фиксированном числе процессоров, величина п в предыдущем примере должна быть постоянной.

По этой же причине не допускаются рекурсивные процедуры, 246 Гл. 7. Обсуждение Эффект подчиненного процесса может быть достигнут с помощью аналогичной конструкции, например:

PROC удвоить{лев,прав) — WHILE TRUE VAR х:

SEQ лев?х прав\{х + л:):

Этот процесс можно описать как подчиненный по отношению к единственному использующему процессу Р:

CHAN удв.лев^удв.прав:

PAR удвоить{удв. лев, удв. прав) Р Внутри Р удвоение числа производится с помощью команд удв.лев\А\ удв.прав?у]...

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

CHAN слож,интеграл[П'— I]:

PAR VAR сумма,х:

SEQ сумма := О ALT i:=[0 FOR п] сложЩ^х SEQ сумма := сумма + х интег рал сумма PAR i:=[0 FOR п]...процессы-пользователи...

Так же как и Ада, Оккам позволяет программисту припи­ сывать процессам, объединенным параллельной композицией, относительные приоритеты. Для этого вместо PAR исполь­ зуется конструкция PRI PAR;

при этом приоритет процесса определяется его местом в списке (чем ближе к началу, тем выше приоритет). Предоставляемые языком средства экран 7.4. Математические модели редактирования позволяют при необходимости переупо­ НОГО рядочивать процессы. Аналогичный выбор предоставляется и для конструкции ALT, которая в этом случае имеет вид PRI ALT. Она обеспечивает, что если к моменту выбора го­ товы несколько альтернатив, то из них будет выбрана тек­ стуально первая;

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

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

7.4. МАТЕМАТИЧЕСКИЕ М О Д Е Л И Идея того, что язык программирования должен обладать точным математическим смыслом или семантикой, была осо­ знана еще в начале 1960-х годов. Математика предоставляет надежную, недвусмысленную, точную и стабильную специ­ фикацию языка, которая может служить согласованным ин­ терфейсом между его пользователями и его реализаторами.

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

В конце 1960-х годов сложилось понимание еще более важной роли математической семантики, а именно как сред­ ства, помогающего программисту реализовать свою ответст­ венность в установлении правильности его программы. Флойд высказал идею, что семантику удобнее формулировать в виде набора корректных правил доказательства, нежели в виде яв­ ной математической модели. Эта идея была реализована в спецификации языков Паскаль, Евклид и Джипси.

Ранняя версия теории взаимодействующих последователь­ ных процессов (разд. 7.3.5) не имела математической семан­ тики и оставляла открытыми ряд вопросов, существенных для разработчика, например:

(1) Допустима ли вложенность одной параллельной ко­ манды в другую?

(2) Если да, то можно ли написать рекурсивную процеду­ ру, которая вызывает себя параллельно?

248 Гл. 7. Обсуждение (3) Имеется ли теоретическая возможность использовать команды вывода в предваряющем выражении?

Представленная в этой книге математическая теория дает положительные ответы на все эти вопросы.

7.4.1. Исчисление взаимодействующих систем Решающий успех в математическом моделировании пара­ ллелизма был достигнут Робином Милнером. Целью его ис­ следования было предоставить основу для построения и срав­ нения различных моделей, обладающих разной степенью абстракции. Поэтому для начала он определил базисный синтаксис выражений для обозначения процессов и ввел ряд эквивалентностей между этими выражениями, наиболее важ­ ными из которых являются: сильная эквивалентность, наблю­ даемая эквивалентность, наблюдаемая конгруэнтность. Каж­ дая эквивалентность задает свою модель параллелизма. Под известным сокращением CCS (Calculus of Communicating Systems) обычно подразумевается модель, где за определе­ ние отношения равенства процессов берется наблюдаемая конгруэнтность.

Основные обозначения в CCS можно проиллюстрировать следующими соотношениями!

а.Р соответствует выражению а~Р (a.P) + (6.Q) соответствует выражению (a-P\b-^Q) NIL соответствует выражению СТОП По сравнению с этими различиями в обозначениях гораздо более важной является разница в трактовке упрятывания.

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

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

Вторым (возможно, менее значительным) преимуществом яв­ ляется то, что процессы, которые могут участвовать в беско­ нечной последовательности т-событий, не обязательно экви­ валентны процессу ХАОС;

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

7.4. Математические модели Среди элементарных операторов в CCS отсутствует ана­ лог операции П. Однако недетерминизм можно промоделиро­ вать с помощью т-событий, например:

(x,P)-\'{x,Q) соответствует выражению P P I Q (т. Р) 4-. Q) соответствует выражению Р П (Р П (а - Q Правда, эти соответствия неточны, поскольку в CCS недетер­ минизм, определенный в терминах т, не будет ассоциативным, что иллюстрируется рис. 7.3, где деревья различны.

Рис. 7. Кроме того, префиксация не дистрибутивна относительно недетерминизма. В качестве примера приведены деревья на рис. 7.4, которые различны, если PФQ.

Рис. 7. Эти примеры показывают, что между процессами, которые в данной книге рассматривались как тождественные, в CCS может существовать много различий. Причина в том, что CCS призвана служить основой для целого семейства моде­ лей, в каждой из которых могут вводиться дополнительные 250 Гл. 7. Обсуждение ПО сравнению с CCS отождествления, но не могут нару­ шаться уже имеющиеся. Во избежание сужения диапазона получаемых моделей в CCS вводятся лишь те отождествле­ ния, которые представляются наиболее существенными. В этой книге при построении математической теории мы пре­ следовали прямо противоположную цель — м ы делали как можно больше отождествлений, оставляя лишь наиболее су­ щественные различия. Поэтому наш набор алгебраических законов неизмеримо богаче. Мы надеемся, что эти законы принесут практическую пользу в рассуждениях, касающихся разработки и реализации;

в частности, они допускают больше преобразований и оптимизаций, чем CCS.

Основной оператор параллельной комбинации в CCS обозначается одной чертой ( | ). Он намного сложнее опера­ тора II в силу того, что наряду с синхронизацией он включает в себя элсхменты упрятывания, недетерминизма и чередова­ ния. Каждое событие в CCS имеет две формы — простую {а)] и с чертой (а). Когда два процесса объединяются для парал­ лельного исполнения, синхронизация возникает только тогда, когда один из процессов исполняет событие с чертой, а дру­ гой — соответствующее простое событие. Их совместное участие в этом общем событии тотчас же скрывается, преоб­ разуясь в т. Синхронизация, однако, не является обязатель­ ной;

каждое из двух событий может происходить явно и не­ зависимо при взаимодействии с внешним окружением. Таким образом, в CCS {a.P)\{b.Q) = a.{P\{b,Q)) + b.{(a.P)\Q) {a.P)\{a.Q) = a.{P\{a.Q)) + a,{{a.P)\Q) {a.P)\{a.Q) = x.{P\Q) + a.{P\{a.Q)) + a.{{a.P)\Q) Следовательно, синхронизованное взаимодействие может про­ изойти только между двумя процессами;

если готовы больше двух процессов, выбор пары происходит недетерминированно:

{a.P)\{a.Q)\{a.R) = x,{P\{a.Q)\R) + x.{{a.P)\Q\R) + a.{P\{a.Q)\{a,R)) + a.{(a.P)\Q\{a.R)) + a.{{a.P)\{a,Q)\R) Благодаря дополнительной сложности параллельного опе­ ратора не возникает необходимости в операторе упрятыва­ ния. Вместо него имеется оператор сужения \, который просто не допускает наступления соответствующих событий и удаляет их из алфавита процесса вместе с их надчеркну 7А. Математические модели тым вариантом. Его действие иллюстрируется следующими ааконами CCS:

(а.Р)\{а} =(а.Р)\{а} ^NIL (Р + Q) \ {а) = (Р \ [а]) + (Q \ {а}) ((a.P)|(a.Q))\{a} = т.((Р |Q) \ {а}) ((а. Р) I (а. Q) I (а. R)) \ {а} = т. ((Р | (а. Q) | /?) \ {а}) + x,{{{a,P)\Q\R)\{a}) Последний из этих законов иллюстрирует мощность парал­ лельного комбинирующего оператора в CCS, позволяющую достигнуть эффекта разделения процесса {a.R) между двумя использующими процессами (а.Р) и {a.Q)\ Целью CCS и яв­ лялось достижение максимальной выразительной мощности средствами как можно меньшего числа различных элемен­ тарных операций. Это составляет источник элегантности и силы CCS и сильно упрощает исследование семейств моделей, задаваемых различными отношениями эквивалентности.

В данной книге избран противоположный подход. Здесь простота достигается за счет создания единственной простой модели, в терминах которой легко определить столько опера­ ций, сколько может потребоваться для исследования спектра различных понятий. Например, операция недетерминирован­ ного выбора П задает недетерминизм в его самом чистом виде и совершенно не зависит от совершаемого обстановкой выбора, представленного операцией {х : В Р{х)). Анало­ гично, операция || задает параллелизм и синхронизацию, со­ вершенно независимые как от недетерминизма, так и от упрятывания, каждое из которых в свою очередь представ­ лено отдельной операцией. На тот факт, что соответствующие понятия различны, указывает, пожалуй, простота алгебраи­ ческих законов. Для успешной практической реализации математических теорий нам необходим достаточно широкий спектр операций. Минимизация набора операций, однако, тоже бывает полезной, особенно в теоретических исследова­ ниях.

Для спецификации наблюдаемого поведения процесса Милнер ввел особую форму модальной логики. Модальность g описывает процесс, который может выполнить действие а, а затем вести себя в соответствии с S, а двойственная модаль­ ность описывает процесс, который, начав с а, должен затем вести себя в соответствии с 5. Вводится исчисление коррект Гл. 7. ОбсуоФдение ности, позволяющее доказать, что процесс Р соответствует спецификации 5 — ф а к т, выраженный в традиционных обо­ значениях логики:

Это исчисление существенно отличается от того, которому подчиняется отношение уд, потому что оно базируется, ско­ рее, на структуре спецификации, нежели на структуре про­ граммы. Например, правило для отрицания имеет вид если неверно, что P[=^^^ то P[==ip.

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

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

Милнер сделал это, введя понятие наблюдаемой эквивалент­ ности. Оно включает определение множества наблюдений или экспериментов, которые можно провести над процессом;

тогда два процесса эквивалеЦ'тны, если не существует эксперимен­ та, который можно сделать над одним из них и невозможно сделать над другим — хорошее приложение философского принципа отождествления неразличимого. Этот принцип был взят за основу математической теории в этой книге, где про­ цесс отождествляется с множеством возможных наблюдений за его поведением. Признаком успешного применения этого принципа служит то, что два процесса P n Q эквивалентны' тогда и только тогда, когда они удовлетворяют одним и тем же спецификациям:

V5.PHS = QHS К сожалению, это не всегда так просто. Если два процес­ са решено считать равными, равными должны быть и резуль 7.^. Математические модели таты преобразования их с помощью одной и той же функ­ ции, т. е.


{P^Q)=^{F{P)^F{Q)) Поскольку предполагается, что событие т скрыто, из естест­ венного определения наблюдения должна следовать эквива­ лентность (т.Р) = Р Однако процесс {х.Р + X.NIL) не должен быть эквивалентен процессу {P + NIL), равному Р, поскольку первый из них может недетерминированно выбрать дедлок вместо того, что­ бы вести себя как Р.

Для решения этой проблемы Милнер предложил вместо эквивалентности использовать понятие конгруэнтности. Один из экспериментов, которые можно провести над процессом Р, состоит в помещении его в обстановку Р ( Р ) (где F строится из других процессов средствами операторов языка), а за­ тем—наблюдении за поведением полученной системы. Про­ цессы PnQ называются (наблюдаемо) конгруэнтными, если для каждой выразимой в языке обстановки F процесс Р ( Р ) наблюдаемо эквивалентен процессу P ( Q ). Согласно этому определению, т.Р не конгруэнтен Р. Открытие полного набора законов конгруэнтности является важным математическим достижением.

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

соот­ ветственно оно ведет к гораздо более слабой эквивалентности и более мощному набору алгебраических законов, чем CCS.

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

поиРАННАЯ ЛИТЕРАТУРА Conway W. Е. Design of a Separable Transition-Diagram Compiler, Comm, ACM 6 (7), 8 - 1 5 (1963).

Классическая работа, посвященная сопрограммам.

Hoare С. А. R. Monitors: An Operating System Structuring Concept, Comm. ACM 17 (10), 549—557 (1974).

Языковое средство построения операционных систем.

Hoare С. А. R. Communicating Sequential Processes, Comm. ACM 21 {8У, 6 6 6 - 6 7 7 (1978).

Разработка языка программирования, являющаяся ранней версией разработки, представленной в этой книге.

Milner R. А Calculus of Communicating Systems, Lecture Notes in Computer Science 92, Springer-Verlag, New York (1980).

Ясная математическая трактовка общей теории паралле­ лизма и синхронизации.

Kahn G. The Semantics of a simple language for Parallel Program­ ming. In Information Processing, 74, North Holland, Am­ sterdam, pp. 471—475 (1974).

Изящная трактовка функционального мультипрограмми­ рования.

Welsh J., Structured System Programming, Prentice-Hall, London, McKeag R. M. pp. 324 (1980).

Сообщение о языке PASCAL P L U S и его использовании в структурировании операционных систем и транслято­ ров.

Filman R. Е., Coordinated Computing, Tools and Techniques for Distri Friedman D. P. buted Software, McGraw-Hill, pp. 370 (1984), Полезный обзор и дальнейшая литература.

Dahl O.-J. Hierarchical P r o g r a m Structures, in Structured Program­ ming, Academic Press, London, pp. 175—220 (1982).

Знакомство с основными идеями языка Симула 67.

(INMOS Ltd.) оссат^^ Programming Manual, Prentice-Hall International, pp. 100 (1984).

(ANSI/MIL- ЛсГа^м Reference Manual.

STD 1815A) В главе 9 описан механизм задач.

Brookes S. D., A Theory of Communicating Sequential Processes, Journal Hoare C. A. R., ACM 31 (7), 5 6 0 - 5 9 9 (1984).

Roscoe A. W. Рассматриваются математические аспекты недетерминиро­ ванных процессов, за исключением расходимости.

Brookes S. D., An Improved Failures Model for Communicating Sequen Roscoe A. W. tial Processes, in Proceedings NSF—SERC Seminar on Concurrency, Springer-Verlag, New York, Lecture Notes in Computer Science (1985).

Здесь вводится понятие расходимости.

УКАЗАТЕЛЬ СИМВОЛОВ Логика Пример Обозначение Значение =х X равно ХФХ+\ отлично от Р и Q (истинны оба) х+ PSLQ Х^Х+ \&Х Ф Р или Q (истинно одно Р VQ или оба) П не Р (Р не истинно) ПР д: у=^х^у если Р, то Q Р тогда и только тогда, P^Q XУ^УX когда Q Зх,х у существует х, такой, что Р Зх.Р У/х.хх+ Р для всех д;

У/х.Р существует х из множества •Вх-.А.Р Л, такой, что Р Р для всех X из множества \fx:A.P Л Множества Пример Значение Обозначение Наполеон е человечество принадлежит Наполеон е русские не принадлежит " 1 Наполеон s {} пустое множество (не со­ О держащее элементов) х^{а}^х==а одноэлементное множество, {а} состоящее из а;

а — его единственный элемент с^{а,Ь,с} множество с элементами а, {а,Ь,с} Ь. с {а} = {х\х = а} множество из всех х, таких, {х\Р(х)} что Р(л-) x^AVx^B] объединение А я В х^А&х^В} пересечение А я В лпв х^А&'Пх^В) А минус В yfx:A,x^B А содерлится в В Л^В В^А А содержит В А^В множество X из Л, таких, {х:А\Р(х)} что Р(х) {0,1,2,...} множество натуральных чи­ N сел 256 Указатель символов Множества Обозначение Значение Пример РЛ РА = [Х\Х^ А] множество-степень А У Ап = {х\3п^0.х^An) объединение семейства мно­ жеств П ^п-=^{х\У/п-^О.х^Ап} пересечение семейства мно­ п жеств функции Значение Обозначение Пример I: Л-В f — функция, отображаю­ квадрат: N - N щая каждый элемент А в некоторый элемент В 1(х) т о т э л е м е н т Б, в к о т о р ы й / о т о б р а ж а е т х ( и з Л) x^y=f(x)=f(y) инъективная функция /, отображающая функция различные элементы А в различные элементы В функция обратная к инъек- x = f{y)^ y==f~\x) г' тивной функции / {f(x) 1 Р множество, образованное {y\3x.y==f(x)&P{x)} (X)} применением / к о в с е м л:, таким, что Р(х) т к в а д р а т ( { 3, 5 } ) = {9,25} о б р а з С при о т о б р а ж е н и и / f'gix) = f(g(x)) композиция fug Хх.Пх) (Kx,f(x)) (3) = /(3) функция, отображающая к а ж д о е значение х в f(x) Протоколы Раздел Обозначение Значение 1.5 пустой протокол 1.5 протокол, содержащий (одноэлементная после­ только а довательность) 1.5 {a.b,c) протокол из трех сим­ а,потом Ь,потом с волов 1.6.1 {а,Ь,с) = {а,ЬГ{ Г (с) ззтем (между протоко­ лами) 1.6.1 'а^ЬУ=^{а,Ь,а,Ь) S, повторенный п раз 1.6.2 s\A 'b,c,d,a)\ {а,с} = (с,а) с у ж е н и е s на Л 1.6.5 S является префиксом T n 4.2.2 S — префикс T и короче е г о не более, чем на п символов 1.6.5 s ъt (cd) в {b,c,d,a,b) S содержится в / 1.6.6 ф{Ь,с,Ь,а) = длина S 1.6.6 (6,с,6,а)|г = число вхождений симво­ ла 6 в протокол S 1.9.6 (с.1,а.4,с.3,с?.1 г=г взаимодействия по кана­ л у с, з а ф и к с и р о в а н н ы е в =0,3) протоколе S 1-9.2 ^/(«,^),(),^» = (а,6,с) конкатенация s 1.9.7 S, з а к о т о р ы м с л е д у е т T Указатель символов Протоколы Раздел Обозначение Значение Л* = {515Г Л = 5} А* 1.6.4 множество последова тельностей элементами из А а, 6, с)о == а 1.6.3 голова S So (а,Ь,сУ==(Ь,с) 1.6.3 хвост S {a,b,c)[\]==b 1.9.4 i-й элемент s s[i] квадрат*«1,5,3))== 1.9.1 / со звездочкой от s =(1,25,9) {a,b,c) = {c,b,a) обратная последователь 1.9. ность к S Специальные события Значение Раздел Обозначение успех (успешное завершение) V 1.9. участие процесса с именем / в событии а 2.6.2 La взаимодействие (передача или прием) по каналу о c,v 4. величины V канал с процесса с именем / Lc 4. передача (прием) сообщения v по каналу Lc Lev 4. катастрофа (молния) 5.4. ® смена 5.4. © контрольная точка для последующего восстанов­ 5.4. ления захват ресурса занят 6. освобождение ресурса свободен 6. Процессы Раздел Обозначение Значение 1Л аР алфавит процесса Р 4.1 ас множество сообщений, которые можно переда­ вать по каналу с 1.1.1 а-Р Р за а 1.1.3 (а - Р I 6 - Q) Р за а или Q за b (при условии, что а Ф Ь) 1.1.3 (х: А-Р(х)) Р от д;


за л: (выбранным) из Л 1.1.2 \iX: A,F(X) процесс X с алфавитом А, такой, что X — F{Xl 1.8.3 P/s Р после (участия в событиях из протокола) s 2.3 P\\Q Р параллельно с Q 2.6.2 /: Р Р с именем / 2.6.4 L:P Р с именами из множества L 3.2 РПQ Р или Q (недетерминированно) 3.3 Р ПQ выбор между Р и Q 3.5 Р\С р без С (упрятывание) 3.6 Р II Q I чередование PnQ 4.4 Р Q сцепление Р с Q Р /IQ Р — подчиненный к Q 4. / : : р /I Q 6.4 дистанционное подчинение 51 PlQ Q следует за Р 5.4 P^Q р прерывается Q Р, а в случае катастрофы Q 5.4.1 P'^l Q 5 42 Р перезапускаемый Р 5.4.3 Р@Q сменяющие друг друга Р и Q Й8 Указатель символов Процессы Раздел Обозначение Значение 5.5 если b, то P иначе — Q *Р 5.1 повторение P 5.2 b*P пока b повторять P 5.4 х:=е X получает значение е 4.2 вывод (значения) е по (каналу) b b\e 4.2 X присвоить значение, поступившее по кана­ b?x лу b 6.2 lle?x вызов разделяемой подпрограммы с именем /, с входными параметрами е и записью результа­ тов в X 1.10.1 P уд S (процесс) Р удовлетворяет (спецификации) S 1.10.1 пр произвольный протокол специфицируемого процесса 3.7 отк произвольный отказ специфицируемого про­ цесса.V 5.5.2 конечное значение х, вырабатываемое специ­ фицируемым процессом 5.5.1 nep{P) множество переменных, которым Р может присваивать значения 5.5.1 дост{Р) множество переменных, значения которых до­ ступны для Р 2.8.2 (детерминированный процесс) Q может делать по крайней мере столько же, сколько Р (недетерминированный процесс) Q не хуже Р 3. и, возможно, лучше 5.5.1 выралчение е определено Алгебра Термин (свойство) Указанным свойством обла­ дает xRx рефлексивность отношение такое, что xRy & yRx^ у X= отношение R, такое, что антисимметричность xRy & yRz^xRz отношение такое, что транзитивность отношение которое реф­ частичный порядок лексивно, антисимметрично и транзитивно элемент JL, такой, что наименьший элемент функция f, сохраняющая монотонность '^y-f{x)^f{L') частичный порядок функция /, такая, что строгость f(-L) = J.

xfx = X двуместный оператор f та­ идемпотентность кой, что xfy = yfx симметричность двуместный оператор f, та­ кой, что xKyfz)^(xfy)fz ассоциативность двуместный оператор f, та­ кой, что xf{ygz)==(xfy)g{xfz) дистрибутивность / дистрибутивна относитель­ A(ygz)fx={yfx)g(zfx) но если xf\ = 1/л: = л;

единица элемент I такой, что xfO = 0/;

c = нуль элемент О такой, что предметный указатель Ада (Ada) 235 выходной канал (output channel) активационные записи (activation records) алгебраические законы (algebraic генеральный выбор (general choi­ laws) 101 ce) Алгол 60, главный процесс (main process-, алфавит (alphabet) master) альтернатива (alternative) голова (head) ангельский недетерминнзм (angelic non-determinism) двоичное дерево (binary tree) бесконечный перехват (infinite over­ двоичный семафор (binary exclu­ taking) 75 sion semaphore) блок управления (control block) 212 двойной буфер (double buffer) бронирование авиабилетов (flight дедлок (deadlock) reservation) 197 детерминированный процесс (deter^ буфер (buffer) 155 ministic process) БУФЕР (BUFFER) 134 Джипси (Gypsy) дистанционный вызов (remote call) ввод в подкачкой (spooled input) 218 дистрибутивная функция (distribu­ вершина (node) 29 tive function) взаимная рекурсия (mutual recur­ длина (length) sion) 28 дополнительная память (backing взаимное влияние (interference) 202 storage) взаимодействие (communication;

in­ допускающий процесс (accepting teraction) 60, 129 process) взвешенная сумма (weighted sum) дост (асе) 141 дуга (arc) ВИЛКА (FORK) виртуальный ресурс (virtual resour­ единственное решение (unique so-* ce) lution) вложение мониторы (nested moni­ tors) 232 законы (laws) внутреннее предложение (inner sta­ замыкание (livelock) tement) 231 занят (acquire) вспомогательный файл (scratch file) защита (protection) 209 звездочка (star) вставка битов (bit stuffing) входной канал (input channel) 130 или J (or I) выбор (choice) 24 или 2 (or 2) выбор 2 (choice 2) 34 или 3 (or 8) выборка (selection) 52 имя входа (entry name) вывод с откачкой (spooled output) индекс (subscipt) 218 ИСПА (RVNA) Предметный указатель непересекающиеся процессы (disjo­ канал (channel) int processes) катастрофа (catastrophe) неподвижная точка (fixed point) класс (class) непредваренная рекурсия (unguar­ композиция (composition) ded recursion) конгруэнтность (congruence) конечное множество (finite set) 162 непрерывный (continuous) НЕСТОП (NONSTOP) конкатенация (concatenation) конструктивная функция (construc­ неудачи (failures) НОВПАНСИОН (NEWCOLLEGE) tive function) контекстно-свободная грамматика (context-free grammar) контрольные точки (checkpoints) обедающие философы (dining phi­ losophers) координатный коммутатор (crossbar область (domain) switch) КОПИБИТ (COPYBIT) 26 общая память (shared storage) ОБЩИЙ ЛАКЕИ (SHARED LAC­ КОПИР (COPY) KEY) критический участок (critical re­ одноэлементная последовательность gion) 203, (singleton) Оккам (occam) ЛАКЕЙ (LACKEY) 84 оператор приема (accept) Л И С П (LISP) операционная система (operating ЛИСПкит (LISPkit) system) 196, ЛОГ (BOOL) 81 основной процесс см. главный про­ локальный вызов процедуры (lo­ цесс cal procedure call) 206 отказы (refusals) отложенные вычисления (lazy eva­ luation) математическая семантика (mathe­ matical semantics) МЕДЛЧАСТН (LONGQUOT) меню (menu) 27 пакетная коммутация (packet swit­ меню (menu) 35 ching) многократный выбор (multiple choi­ пакетная обработка (batch proces­ ce) 98 sing) ПАНСИОН (COLLEGE) многопоточная обработка (multi­ threading) 227 параллелизм (concurrency) МНОЖ (SET) 162 передатчик (transmitter) множества готовности (ready sets) перезапуск (restart) 104 переименование (change of symbol) множественная пометка (multiple пер (var) labelling) ПЕРЕМ (VAR) множественные контрольные точки переход (transition) (multiple checkpoints) Пиджингол (PIDGINGOL) модульность (modularity) планирование (scheduling) монитор (monitor) повторно входимая программа (re­ мониторная система для Фортрана entrant subroutine) (FORTRAN monitor system) подкачка/откачка см. спулинг монотонная функция (monotonic подпрограмма (subroutine) 159.

function) подтверждение (acknowledgement) наблюдаемая эквивалентность (ob­ подчинение (subordination) servational equivalence) подчиненный процесс (slave, subor-* наименьшая верхняя грань (least dinate process) upper bound) полный частичный порядок (complex недеструктивный (nondestructive) 93 te partial order) предметный указатель пометка процесса (process label­ реализация (implementation) ling) 81 реальный ресурс (actual resource) после (after) 48 последовательная композиция (se­ регулярные выражения (regular ex­ quential composition) 172 pressions) последовательное программирование рекурсия (recursion) (sequential programming) 184 рисунки (pictures) 29, последовательно переиспользуемый ресурс (serially reusable resour­ ce) 204 свободен (release) свободные переменные (free va­ постусловие (post-condition) riables) потоковый (data flow) сдвиг влево (left shift) пр (tr) сектор (sector) правило копирования (copy rule) семафор (semaphore) сеть ARPA (ARPA net) предваренный процесс (guarded символические вычисления (symbo­ process) lic execution) предваренный слева процесс (left Симула 67 (SIMULA 67) guarded process) синхронизация (synchronisation) предел (limit) система управления базой данных предложение (sentence) предусловие (precondition) 190 (data base system) систолический массив (systolic ar­ прерывания (interrupts) ray) префикс (prefix) префикс ли {isprefix) 44 скалярное произведение (scalar pro­ duct) приемник (receiver) СЛИЯНИЕ (MERGE) признак конца файла (end-of-file marker) 209 слой (layer) слуга (footman) приоритет (priority) совместно используемое устройство присваивание (assignment) ПРОВОД (WIRE) 156 считывания перфокарт (shared card reader) программный канал (pipe) сокрытие (concealment) продуктивность (fairnoss) сообщ (message) ПРОПУСК (SKIP) состояние (state) просмотр с возвратом (backtrac­ спецификация (specification) king) спрячь (hide) ПО протокол (protocol, trace) 36, 37, спулинг (spooling) статическое связывание (static bin­ протокол ли (istrace) ding) процедура (procedure) стек (stack) процесс (process) СТОПА (STOPA) путь (path) строгий (strict) 38, структура данных (data structure) развертка (unfolding) структурный конфликт (structure разделение времени (timesharing) clash) сужение (restriction) разделяемая структура данных схема коммутационная (connection (shared data structure) diagram) 68, 143, рандеву (rendezvous) сцепление (chaining) РАСПАК (UNPACK) распределенная обработка данных (distributed processing) Т АДОВ ЕР (VMCRED) расходимость (divergence) ТАП (VMS) расходится (diverges) ТАП2 (VMS2) расширение алфавита (alphabet ех-»

ТАС (VMC) tension) 262 Предметный указатель Хемминг (Hamming) ТАШИ (VMCT) ТАШУМ (NOISYVM) транспортер (pipe) транспортный протокол связей цепь (chain) • (transport communication proto­ ЦЕПЬ2 (CHAIN2) col) 138 цикл (loop) тупиковая ситуация см. дедлок циклический процесс (cyclic pro-* cess) УДВ (DOUBLE) указание (pragma) 237 частичный порядок (partial order) указатель (pointer) 212 41, У ПАК (PACK) 132 ЧАСТИ (QUOT) управление потоками (flow cont­ ЧАСЫ (CLOCK) rol) 158 чередование (alternation, interlea** условный критический участок (con­ ving) 51, 114, ditional critical region) условный оператор (conditional) 184 экземпляр (instance) успех (success) успешное завершение (successful termination) 53 язык (language) фазовое кодирование (phase enco­ CCS ding) 154 cobegin. coend факториал (factorial) 161 CT 137 FCFS ФИБ (FIB) FIFO ФИЛ (PHIL) fork функциональная мультипроцессор­ join ная обработка (functional multip­ LABEL rocessing) NIL PASCAL PLUS ХАОС (CHAOS) 122 RC4000 хвост (tail) 40 UNIX^M 227, Оглавление От редактора перевода Предисловие От автора Краткое содержание Глава 1. Процессы 1.1. Введение 1.2. Рисунки 1.3. Законы. 1.4. Реализация процессов,.. 1.5. Протоколы 1.6. Операции над протоколами 1.7. Реализация протоколов 1.8. Протоколы процесса ^ 1.9. Дальнейшие операции над протоколами 1.10. Спефицикации. Глава 2. Параллельные процессы 2.1. Введение 2.2. Взаимодействие. 2.3. Параллелизм 2.4. Рисунки 2.5. Пример: обедающие философы 2.6. Переименование 2.7. Спецификации •' oS 2.8. Математическая теория детерминированных процессов.... Глава 3. Недетерминизм 3.1. Введение 3.2. Недетерминированный выбор 3.3. Генеральный выбор 3.4. Отказы 3.5. Сокрытие { 3.6. Чередование JJ 3.7. Спецификации loT 3.8. Расходимость, } 3.9. Математическая теория недетерминированных процессов... Глава 4. Взаимодействие 4.1. Введение | 4.2. Ввод и вывод 264 Оглавление 4.3. Взаимодействия, 4.4. Транспортеры 4.5. Подчинение Глава 5. Последовательные процессы 5.1. Введение 5.2. Законы 5.3. Математическая трактовка, • 5.4. Прерывания 5.5. Присваивание, 1^ Глава 6. Разделяемые ресурсы, 6.1. Введение 1^^ 6.2. Поочередное использование 6.3. Общая память.. 6.4. Кратные ресурсы 6.5. Операционные системы, 6.6. Планирование ресурсов Глава 7. Обсуждение., 7.1. Введение •.. 7.2. Общая память 7.3. Взаимодействие. 7.4. Математические модели. Избранная литература Указатель символов Предметный указатель Научное издание Ч а р л ь з Энтони Р и ч а р д Х о а р ВЗАИМОДЕЙСТВУЮЩИЕ ПОСЛЕДОВАТЕЛЬНЫЕ ПРОЦЕССЫ Заведующий р е д а к ц и е й чл.-корр. А Н С С С Р И. Арнольд З а м. з а в. р е д а к ц и е й А. С. П о п о в Н а у ч н. р е д. М. В. Х а т у н ц е в а Мл. р е д. Т. Ю. Д е х т я р е в а, Т. А. Д е н и с о в а, Н. С. П о л я к о в а Х у д о ж н и к О. С. В а с и л ь к о в а, Х у д о ж е с т в е н ы й р е д а к т о р В, И. Ш а п о в а л о в Технический р е д а к т о р Е. В. А л е х и н а Корректор Т. П. П а ш к о в с к а я И Б № С д а н о в набор 08.02.88. П о д п и с а н о к печати 12.10.88. Формат 60Х907»з. Бумага к н и ж н о ж у р н а л ь н а я. Печать высокая. Гарнитура литературная. О б ъ г м 8,25. б у м. л. Усл. печ. л.

16,50. Усл. кр.-отт. 16,85. Уч.-изд. л. 14,03. И з д. № 1/5694. Тираж 12 300 э к з. З а к а з № 952.

Ц е н а 1 р у б. 20 коп.

Издательство «Мир» • В/О «Союзэкспорткнига» Государственного комитета СССР По д е л а м и з д а т е л ь с т в, п о л и г р а ф и и и к н и ж н о й торговли. 129820, ГСП, Москва, И-ПО, 1-й Р и ж с к и й пер., 2.

Л е н и н г р а д с к а я т и п о г р а ф и я № 2 головное п р е д п р и я т и е о р д е н а Т р у д о в о г о Красного З н а м е н и Л е н и н г р а д с к о г о о б ъ е д и н е н и я «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Г о с у д а р с т в е н н о м к о м и т е т е С С С Р по д е л а м и з д а т е л ь с т в, полиграфии и книжной торговли. 198052, г. Ленинград, Л-52^ Измайловский проспект, 29,

Pages:     | 1 |   ...   | 4 | 5 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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