Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. —М.: Мир, 1989.— 264 с., ил. ISBN 5-03-001043-2 Книга известного системного программиста и теоретика информатики (Великобритания), последовательно излагающая теорию взаимодействующих процессов; эта тематика тесно связана с такими реальными понятиями, как операционные системы, мультипроцессорные комплексы и сети ЭВМ, Автор рассматривает параллелизм в языках высокого уровня АДА, Симула 67, Паскаль. Для специалистов в области системного программирования, теоретической информатики, математической логики, аспирантов и студентов вузов. От автора
Эта книга — для ищущего программиста, программиста, который стремится глубже понять и лучше овладеть практическим искусством своей наукоемкой профессии. Прежде всего книга взывает к естественному любопытству, возникающему благодаря новому подходу к хорошо знакомым вещам. Этот подход иллюстрируется большим числом практических примеров, взятых из самого широкого круга приложений: от торговых автоматов, игр и сказочных историй до операционных систем ЭВМ. В основе изложения лежит математическая теория, описанная в виде систематического набора алгебраических законов. Конечной целью является выработка у читателя особой проницательности, которая даст ему возможность увидеть как текущие, так и будущие проблемы в новом свете, что позволит решать эти проблемы экономнее и надежнее и, что еще важнее, порой избегать их.
Наиболее очевидной сферой применения новых идей служит спецификация, разработка и реализация вычислительных систем, которые непрерывно действуют и взаимодействуют со своим окружением. Основная идея заключается в том, что эти системы без труда можно разложить на параллельно работающие подсистемы, взаимодействующие как друг с другом, так и со своим общим окружением. Параллельная композиция подсистем ничуть не сложнее последовательного сочетания строк или операторов в обычных языках программирования.
Такой подход обладает целым рядом преимуществ. Во-первых, он позволяет избежать многих традиционных для параллельного программирования проблем, таких, как взаимное влияние и взаимное исключение, прерывания, семафоры, многопоточная обработка и т. д. Во-вторых, он включает в себя в виде частных случаев многие из актуальных идей структурирования, которые используются в современных исследованиях по языкам и методологии программирования; мониторы, классы, модули, пакеты, критические участки, конверты, формы и даже заурядные подпрограммы. И наконец, этот подход является надежной основой для избежания таких
ошибок, как расходимость, тупиковые ситуации, зацикливание, а также для доказательства правильности при проектировании и разработке вычислительных систем.
Я стремился изложить свои мысли в определенной логической и психологической последовательности, начиная с простых элементарных операторов и постепенно переходя к более сложным приложениям. Усердный читатель, возможно, прочтет всю книгу целиком, от корки до корки. Но у многих одни разделы вызовут больший интерес, чем другие; в помощь им, чтобы облегчить разумный выбор, материал каждой главы тщательно структурирован.
(1) Каждая новая идея предварена ее неформальным описанием и проиллюстрирована рядом небольших примеров, полезных, вероятно, всем читателям.
(2) Алгебраические законы, описывающие основные свойства различных операций, будут интересны читателям, ценящим в математике красоту. Они окажутся полезными также тем, кто хочет оптимизировать разработку своих систем с помощью преобразований, сохраняющих корректность.
(3) Необычность предложенных способов реализации состоит в том, что в них используется очень простое и чисто функциональное подмножество языка программирования ЛИСП. Это доставит особенное удовольствие тем, кто работает с ЛИСПом, и благодаря этому получит возможность реализовать и испытать свои замыслы.
(4) Определения протоколов и спецификаций заинтересуют специалистов-системщиков, которым приходится специфицировать требования заказчика, прежде чем приступать к исполнению. Эти понятия пригодятся также ведущим программистам, перед которыми стоит задача проектирования системы путем разбиения ее на подсистемы с четко описанными интерфейсами.
(5) Правила доказательств будут интересны тем, кто серьезно относится к стоящей перед ними задаче написания надежных- программ по заданной спецификации в установленные сроки и с фиксированными затратами.
(6) И наконец, эта математическая теория дает строгие определения понятия процесса и способов построения процессов. Эти определения лежат в основе алгебраических законов, реализаций и правил доказательства.
Читатель может, либо придерживаясь своей системы, либо выборочно, опускать или откладывать на потом те из перечисленных разделов, которые или менее интересны, или вызывают трудности в понимании.
Структура книги позволяет взыскательному читателю либо ограничиться беглым просмотром, либо определить порядок
чтения и выбор глав. Первые разделы гл. 1 и 2 представляют собой введение, необходимое для всех читателей, тогда как их последующие разделы допускают более поверхностное знакомство или же могут быть отложены до следующего прочтения. Главы 3, 4 и 5 не связаны друг с другом, и знакомство с ними может происходить в любом порядке и комбинации В зависимости от интересов и намерений читателя. Поэтому, если на некотором этапе возникнут трудности с пониманием, желательно продолжить чтение со следующего раздела или даже главы, так как, вполне вероятно, пропущенный материал не потребуется немедленно. Если же потребность в нем возникает, то, как правило, дается явная ссылка на предыдущий материал, которой при необходимости можно воспользоваться. Я надеюсь, что в конце концов все в этой книге окажется интересным и полезным, однако порядок чтения и проработки может быть индивидуальным.
Примеры, выбранные для иллюстрации заключенных в книге идей, покажутся очень простыми. Это сделано сознательно. Первые примеры, иллюстрирующие каждую новую идею, должны быть просты настолько, чтобы сложность и необычность самого примера не могли затемнить идею. Некоторые из последующих примеров отличаются большей тонкостью; стоящие за ними проблемы способны породить немало путаницы и сложностей. Простоту их решения следует отнести за счет мощности используемых понятий и элегантности выражающей их нотации.
Тем не менее каждый читатель знаком (возможно, до боли знаком) с проблемами куда более сложными, обширными и важными, нежели те, которые служат примерами во вступительной части. Может показаться, что эти проблемы не под силу никакой математической теории. Мой совет — не поддаваться ни гневу, ни отчаянию, а попробовать испытать на этих проблемах новый метод. Начните с самого упрощенного случая какой-нибудь выбранной вами стороны проблемы и постепенно усложняйте ее в меру необходимости. Просто удивительно, как часто изначально переупрощенная модель позволяет увидеть путь к решению всей проблемы в целом. Возможно, ваша модель послужит структурой, на которую в дальнейшем без риска будут накладываться разные усложнения. И главным сюрпризом будет то, что многие из этих усложнений, вероятно окажутся попросту ненужными. В этом случае усилия по освоению нового метода вознаграждаются особенно щедро.
Обозначения часто служат причиной недовольства. Студент, начинающий изучение русского языка, жалуется на трудности запоминания незнакомых букв кириллицы, осочбенно из-за того, что многие из них имеют непривычное произношение. В порядке утешения скажу, что эта проблема — далеко не главная. Вслед за алфавитом вам предстоит изу« чить грамматику, накопить словарный запас, затем овладеть знанием идиом и стиля, а после этого — обрести способность свободно выражать на этом языке свои мысли. Все это требует старания, тренировки и времени, и поспешности здесь не место. Так же и в математике. Поначалу символы могут оказаться серьезным препятствием, однако истинная проблема состоит в постижении смысла и свойств этих символов, того, как можно и как нельзя их использовать, в умении свободно обращаться с ними при описании новых задач, решений и доказательств. В конце концов у вас выработается вкус к хорошему математическому стилю. К тому времени символы станут невидимыми; сквозь них вы будете видеть именно то, что они означают. Большое преимущество математики в том, что правила ее значительно проще, а словарь— гораздо скупее, чем в естественных языках. Вследствие этого, сталкиваясь с незнакомыми вещами, путем логической дедукции или удачного приема вы сами сможете найти решение, не обращаясь к справочникам и специалистам.
Вот почему математика, как и программирование, доставляет порой истинное наслаждение. Но достичь этого бывает нелегко. Даже математик испытывает трудности при изучении новых направлений в своей пауке. Теория взаимодействующих процессов — новое направление в математике; программист, приступающий к изучению этой теории, не окажется в невыгодном положении по сравнению с математиком; в конце же он обретет явное преимущество, имея возможность найти полученным знаниям практическое применение.
Материал этой книги неоднократно апробировался как на рабочих семинарах, так и на основных курсах лекций. Сначала он был задуман в качестве семестрового спецкурса по технологии программирования, хотя большая его часть может быть изложена на последнем и даже на втором году общего курса по информатике. Перечень исходных знаний ограничивается некоторым знакомством со школьной алгеброй, понятиями теории множеств и символикой исчисления предикатов. Книга может быть использована также в качестве интенсивного недельного курса для профессиональных программистов. В таком курсе следует делать упор на примеры и определения, оставляя математические обоснования для последующей самостоятельной работы. Материал первых двух глав вполне пригоден и для более компактного курса, и даже часовой обзор книги может быть полезен при условии тща-
ит автора
тельного отбора материала, достаточного для разбора весьма поучительной истории о пяти обедающих философах.
Надо сказать, что чтение лекций и проведение семинаров по теории взаимодействующих процессов доставляет огромное удовольствие, а рассмотрение примеров дает широкие возможности для развития сценического искусства лектора. Каждый пример — это маленькая драма, которая может быть поставлена с должным учетом эмоций действующих лиц. Особую реакцию аудитории вызывают шуточные сценки на темы дедлока. Однако нужно постоянно предупреждать слушателей об опасности антропоморфизма. Математические формулы сознательно абстрагированы от всех мотивов, предпочтений и эмоциональных реакций, к которым прибегает лектор «для придания художественного правдоподобия повествованию бесцветному и малоубедительному» '>. Так что нужно учиться концентрировать внимание на сухом тексте математических формул и развивать умение восхищаться прелестью их абстрактности. В частности, это относится к некоторым рекурсивно определенным алгоритмам, чья красота в чем-то сродни захватывающей дух красоте фуг И. С. Баха.
" Гильберт В, Микадо, Кибернетика, 6, 1969 (пер, А. Ф. Papa),— Прим. перев.
Оглавление
Зт редактора перевода .................. 5
Чредисловие ..... .................. 7
Эт автора........................ 9
Краткое содержание................... 14
Глава 1. Процессы.................... 18
1.1. Введение..................... 18
1.2. Рисунки..................... 29
1.3. Законы...................... 31
1.4. Реализация процессов................ 33
1.5. Протоколы.................... 36
1.6. Операции над протоколами.............. 38
1.7. Реализация протоколов................42
1.8. Протоколы процесса................. 44
1.9. Дальнейшие операции над протоколами......... 50
1.10. Спефицикации...................54
Глава 2. Параллельные процессы . . . ........... 60
2.1. Введение...................... 60
2.2. Взаимодействие................... 60
2.3. Параллелизм.................... 63
2.4. Рисунки....................• . . 68
2.5. Пример: обедающие философы............. 69
2.6. Переименование................... 76
2.7. Спецификации................... . 86
2.8. Математическая теория детерминированных процессов .... 87
Глава 3. Недетерминизм.................. 95
3.1. Введение...................... 95
3.2. Недетерминированный выбор.............. 96
3.3. Генеральный выбор................. 101
3.4. Отказы...................... ЮЗ
3.5. Сокрытие..................... 105
3.6. Чередование.................... 114
3.7. Спецификации.................. 117
3.8. Расходимость.................... 121
3.9. Математическая теория недетерминированных процессов . . . 125
Глава 4. Взаимодействие................. 129
4.1. Введение...................... '29
4.2. Ввод и вывод.............,...... 130
4.3. Взаимодействия................... 138
4.4. Транспортеры.................... 147
4.5. Подчинение..................... 158
Глава 5. Последовательные процессы............. 168
5.1. Введение...................... 168
5.2. Законы...................... 172
5.3. Математическая трактовка . ....... ......... 174
5.4. Прерывания.................... 177
5.5. Присваивание.................... 184
Глава 6. Разделяемые ресурсы............... 195
6.1. Введение...................... 195
6.2. Поочередное использование ,............. 196
6.3. Общая память ................... 201
6.4. Кратные ресурсы.................. 204
6.5. Операционные системы ,............... 215
6.6. Планирование ресурсов.............. 221
Глава 7. Обсуждение..................... . . . . . 225
7.1. Введение...................... 225
7.2. Общая память .................... 225
7.3. Взаимодействие .................... 238
7.4. Математические модели . . .......'-.-"-...... 247
Избранная литература......• • •......... 2°
Указатель символов................... 255
Предметный указатель . . . .............. 259