Пример 7.6. Обход ошибки потерянного пробуждения

.globl flag
flag: db 0
jmpbuf: dw 0
proc flag_interrupt
push eax
tst jmpbuf
bz setflagonly
; подменяем адрес возврата
move eax, jmpbuf
move sp[RETURN_ADDRESS_OFFSET], eax setflagonly
move eax, 1
move flag, eax
pop eax
iret endp
proc process!
inove eax, setjmp
move jmpbuf, eax setjmp:
move eax, 1
lock xchg eax, flag
tst eax
bz ok
halt
ok
xor eax, eax move jmpbuf, eax
критическая секция
xor eax, eax move flag, eax
endp

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

Семафоры

Но когда ты проспишься, скрой спой испуг, Это был не призрак, эти был только звук Это тронулся поезд, на который ты не попадешь. Б. Гребенщиков

Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Пытаясь пройти через сема-Фор, нить пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), нить останавливается и ставится в очередь.
Закрытие семафора соответствует захвату объекта или ресурса, доступ к кото-Рому контролируется этим семафором. Если объект захвачен, остальные нити вынуждены ждать его освобождения. Закончив работу с объектом (выйдя из критической секции), нить увеличивает значение семафора на единицу, открывая его. При этом первая из стоявших в очереди нитей активизируется и вычитает из значения семафора единицу, снова закрывая семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первая нить, подошедшая к семафору, успешно проГцет через него. Это действительно похоже на работу железнодорожного семафо. ра, контролирующего движение поездов по одноколейной ветке (рис. 7.6)

Рис. 7.6. Железнодорожный семафор

Наиболее простым случаем семафора является двоичный семафор. Начальное значение флаговой переменной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна нить.
Семафоры общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько нитей могут работать с объектом одновременно, или когда объект состоит из нескольких независимых, но равноценных частей — например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.
Многие системы предоставляют также сервисы, позволяющие просмотреть состояние семафора без его изменения и произвести "неблокируюшуюся" форму захвата, которая возвращает ошибку в ситуации, когда нормальный захват семафора привел бы к блокировке. Теоретики не очень любят такие примитивы, но при разработке сложных сценариев взаимодействия с участием многих семафоров они бывают полезны.
Во многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят более краткое и выразительное имя мутекс (mutex — от MUTnal EXclusion, взаимное исключение). Проследить генезис этого названия автору не удалось, но можно с уверенностью сказать, что оно вошло в широкое употребление не ранее конца 80-х. Так, в разрабатывавшейся в середине 80-х годов OS/2 1.0, двоичные семафоры еще называются семафорами, а в Win32, разработка которой происходила в начале 90-х, уже появляется название mutex. Операции над мутексом называются захватом (acquire) (соответствует входу в критическую секцию) и освобождением (release) (соответствует выходу из нее).
Многие ОС предоставляют для синхронизации семафоры Дейкстры или похожие на них механизмы.

Флаги событий в RSX-11 и VMS
Так, например, в системах RSX-11 и VMS основным средством синхронизации являются флаги событий (event flags). Процессы и система могут очищать (clear) или взводить (set) эти флаги. Флаги делятся на локальные и глобальные. Локальные флаги используются для взаимодействия между процессом и ядром системы, глобальные — между процессами. Процесс может остановиться, ожидая установки определенного флага, поэтому флаги во многих ситуациях можно использовать вместо двоичных семафоров. Кроме того, процесс может связать с флагом события процедуру-обработчик AST (Asynchronous System Trap — асинхронно [вызываемый] системный обработчик).
AST во многом напоминают сигналы или аппаратные прерывания. В частности, флаги событий используются для синхронизации пользовательской программы с асинхронным исполнением запросов на ввод-вывод. Исполняя запрос, программа задает локальный флаг события. Затем она может остановиться, ожидая этого флага, который будет взведен после исполнения запроса. При этом мы получаем псевдосинхронный ввод-вывод, напоминающий синхронные операции чтения/записи в UNIX и MS DOS. Но программа может и не останавливаться! При этом запрос будет исполняться параллельно с исполнением самой программы, и она будет оповещена о завершении операции соответствующей процедурой AST.

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

Семафоры и прерывания

Большинство современных ОС предоставляют сервисы, позволяющие без вреда для остальной системы приостановить и возобновить исполнение пользовательской нити. Однако мало какая ОС предоставляет такой же сервис для обработчиков прерываний. Поэтому если ОС и разрешает использование примитивов синхронизации из прерываний, то всегда с условием, что такое использование не может приводить к блокировке обработчика.
Например, если для синхронизации используется мутекс, обработчик прерывания не может его устанавливать, а может только снимать. Это требование накладывает определенные ограничения на стиль использования семафоров. Если при синхронизации равноправных нитей каждая из них устанавливает семафор в начале критической секции и снимает его в конце, используя его и для взаимоисключения, и для синхронизации, то при взаимодействии нити с обработчиком прерывания для реализации взаимоисключения приходится использовать запрет прерываний, а мутекс — только для синхронизации.
Стандартная техника использования мутекса в обработчике прерывания состоит в следующем (порядок операций важен!): процесс захватывает мутекс, инициирует операцию на устройстве, которая должна завершиться прерыванием, и захватывает мутекс еще раз. Если к этому моменту прерывание уже произошло, мутекс будет свободен и процесс ничего не будет ждать. Если же прерывания еще не происходило, процесс заснет, ожидая его. Обработчик же прерывания только снимает мутекс.

Захват участков файлов

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

Блокировка участков файла в Unix
Захват участков файла в качестве средства синхронизации был известен еще с 60-х годов, но в том виде, который описан в стандартах ANSI и POSIX, он был реализован в ОС UNIX в начале 70-х.
В UNIX возможны два режима захвата: допустимая (advisory) и обязательная (mandatory). Как та, так и другая блокировка может быть блокировкой чтения либо записи. Допустимая блокировка является "блокировкой для честных": она не оказывает влияния на подсистему ввода-вывода, поэтому программа, не проверяющая блокировок или игнорирующая их, сможет писать или читать из заблокированного участка без проблем. Обязательная блокировка требует больших накладных расходов, но запрещает физический доступ к файлу: чтение или запись, в зависимости от типа блокировки.
При работе с разделяемыми структурами данных в ОЗУ было бы удобно иметь аналогичные средства, но их реализация ведет к большим накладным расходам, даже на системах с виртуальной памятью, поэтому ни одна из известных автору систем таких средств не имеет. Библиотека POSIX threads предоставляет своеобразную форму мутекса, read/write lock, который, как и описанные файловые примитивы, может быть многократно захвачен для чтения и лишь однократно — для записи. Однако мы должны заводить такой примитив для каждой единицы разделяемого ресурса и не можем одним вызовом захватить сразу много подобных единиц.
Впрочем, в современных версиях системы UNIX есть возможность отображать файл в виртуальную память. Используя при этом допустимую блокировку участков файла, программы могут синхронизироовать доступ к нему (обязательная блокировка делает невозможным отображение в память).

Мониторы и серверы транзакций

Захват участков файла теоретически позволяет реализовать любую требуемую структуру взаимоисключения для процессов, работающих с этим файлом. Однако, практически, при работе с файлом большого количества нитей (например, многопользовательской системы управления базами данных), различные нити часто оказываются вынуждены ждать друг друга, что приводит к резкому увеличению времени реакции системы. С этим явлением хорошо знакомы разработчики и пользователи файловых СУБД, таких, как FoxPro или dBase IV.
В случае СУБД решение состоит в создании сервера БД, или сервера транзакций, который вместо примитивов захвата участков файлов или таблиц предоставляет пользователям понятие транзакции.
Если пользовательская сессия объявила начало транзакции, изменения, которые она вносит в таблицы, непосредственно в таблицах не отражаются, и другие сессии, которые обращаются к вовлеченным в транзакцию данным, получают их исходные значения. Завершив модификацию, пользовательская сессия объявляет завершение транзакции. Транзакция может завершиться как выполнением (commit), так и откатом (rollback).
В случае отката измененные данные просто игнорируются. В случае же выполнения сервер вносит изменения в таблицы, однако во время изменений он все равно предоставляет другим нитям данные в том состоянии, в котором они были до начала транзакции. Такой подход увеличивает потребности в оперативной и дисковой памяти (все данные, изменяемые в ходе транзакции, должны храниться минимум дважды: в измененном и в исходном видах), но обеспечивает резкое сокращение времени реакции и определенное упрощение кодирования: программист теперь не должен явно перечислять все данные, которые ему надо заблокировать в ходе транзакции. Кроме того, Двойное хранение данных позволяет восстановить либо результат транзакции, либо состояние данных до ее начала, после сбоя системы.
Современные серверы СУБД представляют собой сложные программные Комплексы, которые, кроме собственно "развязки" транзакций предоставляют сложные сервисы оптимизации запросов, индексации и кэширования Данных. Да и точное описание понятия транзакции в современных языках запросов к реляционным СУБД (SQL, RPG и др.) несколько сложнее при-Веденного выше. Однако детальное обсуждение этого вопроса увело бы нас Далеко в сторону от темы книги. Читателю, интересующемуся этой темой, Можно порекомендовать книги [Дейт 1999, Бобровски 1998].
Аналогичный серверам транзакций подход нередко используется и в более простых случаях межпроцессного взаимодействия. С разделяемым ресурсом ассоциируется специальная нить, называемая монитором ресурса. Остальны нити не могут обращаться к ресурсу напрямую и взаимодействуют только с монитором. Монитор может предоставлять нитям-клиентам непротиворечивые состояния контролируемого им ресурса (необязательно совпадающие с текущим состоянием ресурса) и устанавливать очередность запросов на модификацию.
Даже при довольно простой стратегии управления ресурсом, монитор полезен тем, что скрывает (инкапсулирует) структуру и особенности реализации разделяемого ресурса от клиентских нитей. Типичный пример мониторного процесса — драйвер внешнего устройства в многозадачных ОС.

Гармонически взаимодействующие последовательные потоки

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

1. 1. Каждый поток (нить) представляет собой независимый программный модуль, для которого создается иллюзия чисто последовательного исполнения.
2. 2. Нити не имеют разделяемых данных.
3. 3. Все обмены данными и вообще взаимодействие происходят с использованием специальных примитивов, которые одновременно выполняют и передачу данных, и синхронизацию.
4. 4. Синхронизация, не сопровождающаяся передачей данных, просто лит6" на смысла — нити, не имеющие разделяемых структур данных, совершенно независимы и не имеют ни критических точек, ни нереентерабельных модулей.

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

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

Гармоническое взаимодействие, строго говоря, не исключает проблему мертвой блокировки: замкнув гармонически взаимодействующие нити в кольцо (А получает информацию от В, В от С, С от А), мы можем получить классическую трехзвенную мертвую блокировку. Впрочем, в данном случае блокировка требует наличия циклической зависимости данных, которая свидетельствует о серьезных ошибках проектирования программы (и, возможно, о внутренней противоречивости требований к этой программе). Такая ошибка может быть относительно легко обнаружена посредством формального анализа спецификаций и потоков данных.
На практике, впрочем, гармоническое взаимодействие обходит основную массу проблем, возникающих при взаимоисключении доступа ко многим ресурсам — и блокировки, и "проблему голодного философа". Дело в том, что гармонически взаимодействующий поток имеет дело не с разделяемым ресурсом непосредственно, а с копией состояния этого ресурса. Если нам нужны два ресурса, мы (не обязательно одновременно) снимаем с них две копии — для этого нам не надо одновременно захватывать сами ресурсы.
В частности, поэтому групповые операции над примитивами гармонического взаимодействия (оператор select в Ada, системный вызов select в системах семейства Unix, команда alt в транспьютере) работают не по принципу транзакции, а возвращают управление и данные при условии, что хотя бы один из примитивов группы готов эти данные предоставить. Воспроизвести "проблему голодного философа" в этих условиях невозможно.
В современных системах реализован целый ряд средств, которые осуществляют передачу данных совместно с синхронизацией: почтовые ящики (mailboxes) в системах линии RSX-11 — VMS, трубы (pipes) (в русскоязычной литературе их часто называют программными каналами) в UNIX, рандеву (rendesvous — свидание) в языке Ada, линки (link — соединение) в микропроцессорах семейства Transputer и т. д. Большинство этих средств будет обсуждаться подробнее в разд. Примеры реализаций средств гармонического взаимодействия.
Примитивы синхронного обмена данными отличаются большим разнообразием. Основные принципы классификации таковы.

1. 1. Примитивы могут быть двухточечные (допускающие только один прием, ник и один передатчик), либо многоточечные, допускающие несколько приемников и передатчиков. Многоточечность бывает как симметричная когда может быть несколько и приемников, и передатчиков, так и асимметричная: один передатчик и много приемников — широковещательная (broadcast) или групповая (multicast) передача — либо один приемник и много передатчиков.
2. 2. Примитив может передавать неструктурированный поток байтов, либо структурированные данные, разбитые на сообщения определенного размера. В первом случае передатчик может порождать данные блоками одного размера, а приемник — считывать их блоками другого размера Во втором случае приемник всегда обязан прочитать сообщение целиком (возможно, отбросив какую-то его часть). Сообщения могут быть как фиксированного, так и переменного размера.
3. 3. Примитив может быть синхронным, буферизованным или с негарантированной доставкой. В первом случае передатчик вынужден ждать, пока приемник не прочитает все переданные данные. Во втором, данные складываются в буфер и могут быть прочитаны приемником позднее. В третьем случае, если потенциальный приемник не был готов принять сообщение, оно просто игнорируется.

Синхронные примитивы могут использоваться не "только для гармонического взаимодействия, но и для реализации примитивов чистой синхронизации. В частности, в учебниках по языку Ada (например, [Василеску 1990]) и по программированию для транспьютеров (например, [Харп 1993]) почему-то любят приводить примеры реализации семафоров на основе, соответственно, рандеву и линков.
Буферизованные примитивы для синхронизации использованы быть не могут. Зато буферизация полезна, если нам надо согласовать скорости работы нитей, имеющих разные приоритеты — например, если нить реального времени должна быстро обработать событие и передать часть данных для отложенной обработки менее приоритетной нитью, не допустив при этом собственной блокировки.
Буферизованный примитив может быть легко реализован на основе пары синхронных примитивов и нити-монитора буфера (или очереди). В этом смысле, синхронные примитивы являются более низкоуровневыми, чем буферизованные.
Синхронные примитивы по природе своей всегда двухточечные. Да и в случае буферизованных примитивов многоточечное взаимодействие не всегда легко реализуемо, а иногда просто опасно, особенно в случае потоковой передачи данных: операция считывания данных из потока необратима, а естественного разбиения потока на сообщения нет, поэтому если один из приемников по ошибке захватит кусок сообщения, предназначенного не ему, то данные в потоке будут необратимо испорчены.
Впрочем, некоторые потоковые примитивы, например трубы (pipes) в системах семейства Unix, допускают (хотя документация и рекомендует пользо-яться этим с осторожностью) наличие нескольких передатчиков при одном приемнике.
Напротив, симметрично многоточечные очереди сообщений широко распространены. Часто такие примитивы позволяют потребителю отбирать сообщения из очереди по какому-то критерию, например по значению специального поля, называемому типом или тегом. Ряд широковещательных и групповых сервисов передачи данных относится к категории примитивов с негарантированной доставкой.
Второй и третий критерии нашей классификации (если пока отвлечься от сервисов с негарантированной доставкой) практически ортогональны друг другу: существуют все четыре варианта (табл. 7.1). Легко понять, что передавать поток неструктурированных данных в режиме негарантированной доставки бессмысленно: разрывы потока неизбежны, а мы не сможем даже узнать, произошел ли такой разрыв, и если произошел, то где. Все существующие сервисы с негарантированной доставкой передают только сообщения.

Таблица 7.1. Примитивы синхронизованной передачи данных

Примитивы	Синхронные	Буферизованные
Потоковые	Линки (транспьютер)	Трубы (Unix), сокеты (TCP/IP)
Структурированные	Рандеву (Ada)	Очереди сообщений

На первый взгляд, вообще непонятно, почему кому-то может быть полезен сервис с негарантированной доставкой. Но под это описание подходят многие низкоуровневые сетевые протоколы (Ethernet, IP) и некоторые относительно высокоуровневые сетевые сервисы, так называемые дейтаграммные протоколы. Примером такого сервиса является UDP (User Datagram Protocol), входящий в семейство протоколов TCP/IP.
В сетевых протоколах отсутствие гарантии доставки сообщения имеет двоякий смысл — сообщение может быть потеряно не только по невниманию получателя, но и из-за физических ошибок передачи или перегрузки маршрутизаторов и/или каналов связи по дороге от передатчика к приемнику. В этом смысле можно сказать, что разработчики сетевых протоколов вынуждены использовать негарантированную доставку не потому, что им нужна Именно она, а потому, что других средств-то и нет.
В чистом виде негарантированная доставка приемлема для реализации одиночных запросов, на которые должен последовать одиночный же ответ. Если ответа за определенный протоколом интервал времени нет, передатчик повторяет запрос, а после некоторого количества попыток приходит к выводу, что приемник не функционирует, либо вообще отсутствует.
Для реализации надежной связи на основе сервисов с негарантированной доставкой используются различного рода подтверждения, так называемое квитирование. Понятно, что при реализации квитирования необходимо принимать во внимание возможность потери не только самого подтверждаемого сообщения, но и пакета-подтверждения. Понятно также, что в большинстве случаев посылка подтверждения на каждое пришедшее сообщение нецелесообразна. Поэтому реальные протоколы такого рода относительно сложны (см. например [RFC 0793]) и их обсуждение заслуживает отдельной книги. Накладные расходы при реализации таких протоколов значительны, поэтому часто оказывается целесообразно смириться с негарантированной доставкой.
Концепция гармонически взаимодействующих процессов очень привлекательна с теоретической точки зрения и позволяет легко писать правильные программы. Однако все примитивы синхронизованной передачи данных плохи именно тем, что требуют передачи, копирования данных. И передатчик, и приемник вынуждены иметь по буферу, в котором данные следует хранить (в случае буферизованных примитивов данные хранятся трижды). Накладные расходы при копировании данных большого объема также могут оказаться значительными.
Если нити исполняются на разных компьютерах, не имеющих общей памяти и соединенных лишь относительно (по сравнению с системной шиной) низкоскоростными сетевыми каналами, мы так или иначе не можем обойтись без передачи и двойного хранения данных. Впрочем, даже и в этом случае иногда имеет смысл подумать о применении многопортовой памяти или реализаций NUMA или СОМА-архитектуры.
При исполнении же нитей на одной машине, по соображениям производительности и экономии памяти нередко оказывается нецелесообразно отказываться от разделяемой памяти и полностью переходить на примитивы гармонического взаимодействия. Чаще всего это происходит, когда к ресурсу выполняется много обращений для чтения, а модификации относительно редки, и при этом данные имеют большой объем. Даже в этом случае бывает целесообразно заменить прямое разделение памяти на мониторный процесс. а при доступе к данным получать у него лишь непосредственно необходимое их подмножество. Однако ситуации бывают разные, и не всегда такое решение оказывается оптимальным.
В этом смысле разделяемая память напоминает другой предмет ненависти структурных программистов — оператор goto. И то, и другое при неразумном использовании является потенциальным источником ошибок и проблем, но иногда без них оказывается нельзя обойтись.

Примеры реализаций средств гармонического взаимодействия

Программные каналы Unix
Одним из наиболее типичных средств такого рода является труба (pipe) или программный канал — основное средство взаимодействия между процессами в ОС семейства Unix. В русскоязычной литературе трубы иногда ошибочно называют конвейерами. В действительности, конвейер — это группа процессов, последовательно соединенных друг с другом однонаправленными трубами.
Труба представляет собой поток байтов. Поток этот имеет начало (исток) и конец (приемник). В исток этого потока можно записывать данные, а из приемника — считывать. Нить, которая пытается считать данные из пустой трубы, будет задержана, пока там что-нибудь не появится. Наоборот, пишущая нить может записать в трубу некоторое количество данных, прежде чем труба заполнится, и дальнейшая запись будет заблокирована. На практике труба реализована в виде небольшого (несколько килобайтов) кольцевого буфера. Передатчик заполняет этот буфер, пока там есть место. Приемник считывает данные, пока буфер не опустеет.
Трубу можно установить в режим чтения и записи без блокировки. При этом вызовы, которые в других условиях были бы остановлены и вынуждены были бы ожидать партнера на другом конце трубы, возвращают ошибку с особым кодом.
По-видимому, трубы являются одной из первых реализаций гармонически взаимодействующих процессов по терминологии Дейкстры.
Самым интересным свойством трубы является то, что чтение данных из и запись в нее осуществляется теми же самыми системными вызовами read и write, что и работа с обычным файлом, внешним устройством или сетевым соединением (сокетом). На этом основана техника переназначения ввода-вывода, широко используемая в командных интерпретаторах UNIX. Она состоит в том, что большинство системных утилит получают данные из потока стандартного ввода (stdin) и выдают их в поток стандартного вывода (stdout). При этом, указывая в качестве этих потоков терминальное устройство, файл или трубу, мы можем использовать в качестве ввода, соответственно: текст, набираемый с клавиатуры, содержимое файла или стандартный вывод другой программы. Аналогично мы можем выдавать данные сразу на экран, в файл или передавать их на вход другой программы.
Так, например, компилятор GNU С состоит из трех основных проходов: препроцессора, собственно компилятора, генерирующего текст на ассемблере, и ассемблера. При этом внутри компилятора, на самом деле, также выполняется несколько проходов по тексту (в описании перечислено восемнадцать), в основном для оптимизации, но нас это в данный момент не интересует, поскольку все они выполняются внутри одной задачи. При этом все три задачи объединяются трубами в единую линию обработки входного текста — конвейер (pipeline), так что промежуточные результаты компиляции не занимают места на диске.
В системе UNIX труба создается системным вызовом pipe(int flldes;2]) Этот вызов создает трубу и помещает дескрипторы файлов, соответствующие входному и выходному концам трубы, в массив fildes. Затем мы можем вы полнить fork, в различных процессах переназначить соответствующие конць трубы на место stdin и stdout и запустить требуемые программы (пример 7.7). При этом мы получим типичный конвейер — две задачи, стандартный ввод и вывод которых соединены трубой.