Теория операционных систем
Примеры реализаций средств гармонического взаимодействия
Программные каналы Unix
Одним из наиболее типичных средств такого рода является труба (pipe) или
программный канал — основное средство взаимодействия между процессами
в ОС семейства Unix. В русскоязычной литературе трубы иногда ошибочно
называют конвейерами. В действительности, конвейер — это группа процессов,
последовательно соединенных друг с другом однонаправленными трубами.
Труба представляет собой поток байтов. Поток этот имеет начало (исток)
и конец (приемник). В исток этого потока можно записывать данные, а из
приемника — считывать. Нить, которая пытается считать данные из пустой
трубы, будет задержана, пока там что-нибудь не появится. Наоборот, пишущая
нить может записать в трубу некоторое количество данных, прежде чем труба
заполнится, и дальнейшая запись будет заблокирована. На практике труба
реализована в виде небольшого (несколько килобайтов) кольцевого буфера.
Передатчик заполняет этот буфер, пока там есть место. Приемник считывает
данные, пока буфер не опустеет.
Трубу можно установить в режим чтения и записи без блокировки. При этом вызовы, которые в других условиях были бы остановлены и вынуждены были бы ожидать партнера на другом конце трубы, возвращают ошибку с особым кодом.
По-видимому, трубы являются одной из первых реализаций гармонически взаимодействующих процессов по терминологии Дейкстры.
Самым интересным свойством трубы является то, что чтение данных из и запись в нее осуществляется теми же самыми системными вызовами read и write, что и работа с обычным файлом, внешним устройством или сетевым соединением (сокетом). На этом основана техника переназначения ввода-вывода, широко используемая в командных интерпретаторах UNIX. Она состоит в том, что большинство системных утилит получают данные из потока стандартного ввода (stdin) и выдают их в поток стандартного вывода (stdout). При этом, указывая в качестве этих потоков терминальное устройство, файл или трубу, мы можем использовать в качестве ввода, соответственно: текст, набираемый с клавиатуры, содержимое файла или стандартный вывод другой программы. Аналогично мы можем выдавать данные сразу на экран, в файл или передавать их на вход другой программы.
Так, например, компилятор GNU С состоит из трех основных проходов: препроцессора, собственно компилятора, генерирующего текст на ассемблере, и ассемблера. При этом внутри компилятора, на самом деле, также выполняется несколько проходов по тексту (в описании перечислено восемнадцать), в основном для оптимизации, но нас это в данный момент не интересует, поскольку все они выполняются внутри одной задачи. При этом все три задачи объединяются трубами в единую линию обработки входного текста — конвейер (pipeline), так что промежуточные результаты компиляции не занимают места на диске.
В системе UNIX труба создается системным вызовом pipe(int flldes;2]) Этот вызов создает трубу и помещает дескрипторы файлов, соответствующие входному и выходному концам трубы, в массив fildes. Затем мы можем вы полнить fork, в различных процессах переназначить соответствующие конць трубы на место stdin и stdout и запустить требуемые программы (пример 7.7). При этом мы получим типичный конвейер — две задачи, стандартный ввод и вывод которых соединены трубой. Пример 7.7. Код, создающий конвейер при помощи труб
#include <unistd.h>
void pipeline(void) {
/* stage 1 */
int pipel[2];
int childl;
int pipe2[2];
int child2;
int child3;
pipe(pipel);
if ((childl=fork())==0) {
close(pipel[0]); /* Закрыть лишний конец трубы */
closed); /* Переназначить стандартный вывод */
dup(pipel[1]);
close(pipel[1]);
/* Исполнить программу */
execlpC'du", "du", "-s", ".", NULL);
/* Мы можем попасть сюда только при ошибке exec */
perror("Cannot exec");
exit(0);
}
close(pipel [1] ) ;
if (childl==-l) {
perror("Cannot fork");
}
/* stage 2 */
pipe(pipe2);
if ( (child2=fork() )==0) { '. close (0) ; /J" Переназначить стандартный
ввод */
dup(pipel[0]} ; close (pipel [0] ) ;
•'close (pipe2 [0] ) ; /* Закрыть лишний конец трубы */ close (1) ; /*
Переназначить стандартный вывод */
close (pipe2 [1] ) ;
/* Исполнить программу */
execlp ("sort", "sort", "-nr", NULL);
/* Мы можем попасть сюда только при ошибке exec */
perror ("Cannot exec");
exit(O) ;
}
close (pipel [0] ) ;
close (pipe2 [1] ) ;
if (child2==-l) {
perror ("Cannot fork");
}
/* stage 3 */
if ( (child3=fork() )==0) {
close (0) ; /* Переназначить стандартный ввод */
dup(pipe2 [0] ) ;
close (pipe2 [0] ) ;
/* Исполнить программу */
execlp ("tail", "tail", "-1", NULL) ;
/* Мы можем попасть сюда только при ошибке exec */
perror ("Cannot exec");
exit (0) ;
}
close (pipe2 [0] ) ;
if (child3==-l) {
perror ("Cannot fork");
}
while (wait (NULL) !=-!) ;
return ;
}
Понятно, что такие трубы можно использовать только для связи родственны
задач, т. е. таких, которые связаны отношением родитель-потомок или являются
потомками одного процесса.
Для связи между неродственными задачами используется другое средство.
именованные трубы (named pipes) в System V и UNIX domain sockets в BSD
UNIX. В разных системах именованные трубы создаются различными систем
ными вызовами, но очень похожи по свойствам, поэтому стандарт POSIX пред
лагает для создания именованных труб библиотечную функцию mkfifc
{c--ls. char * name, mode_t flags);. Эта функция создает специальный
файл" Открывая такой файл, программа получает доступ к одному из
концов трубы Когда две программы откроют именованную трубу, они смогут
использовать ее для обмена данными точно так же, как и обычную.
Современные системы семейства Unix предоставляют возможность для одновременной
работы с несколькими трубами (а также с другими объектами, описываемыми
дескриптором файла — собственно файлами, сокетами и т. д.)_, системный
вызов select. Этот вызов возвращает список дескрипторов файлов, которые
способны передать или принять данные. Если ни один из дескрипторов не
готов к обмену данными, select блокируется.
Трубы широко используются системами семейства Unix, и они внесены в стандарт
POSIX. Ряд операционных систем, не входящих в семейство Unix, например
VxWorks, также предоставляют этот сервис.
Почтовые ящики VMS
Система VMS предоставляет средства, отчасти аналогичные трубам, называемые
почтовые ящики (mailbox). Почтовый ящик также представляет собой кольцевой
буфер, доступ к которому осуществляется теми же системными вызовами, что
и работа с внешним устройством. Системная библиотека языка VAX С использует
почтовые ящики для реализации труб, в основном совместимые с UNIX и стандартом
POSIX. Широко используемый сервис сетевой передачи данных, сокеты протокола
TCP, также очень похожи на трубу.
Линки транспьютера
В микропроцессорах семейства Transputer микропрограммно реализованы линки
(link — связь) — синхронный примитив, отчасти похожий на трубы.
Линки бывают двух типов — физические и логические. Операции над линками
обоих типов осуществляются одними и теми же командами. Физический линк
представляет собой последовательный интерфейс RS432, реализованный на
кристалле процессора. С линком также ассоциировано одно слово памяти,
смысл которого будет объяснен далее.
Современные транспьютеры имеют четыре физических линка. Физические линки
могут передавать данные со скоростью до 20 Мбит/с и могут использоваться
как для соединения транспьютеров между собой (рис. 7.7), так и для подключения
внешних устройств. Благодаря этому физический линк может использоваться
как для связи между процессами на разных транспьютерах, так и для синхронизации
процесса с внешними событиями и даже просто для ввода-вывода.
Рис. 7.7. Сеть транспьютеров, соединенных физическими линками
Логический линк— это просто структура данных, выделенная
в физическом адресном пространстве процессора. С точки зрения программы,
физический и логический линки ничем не отличаются, кроме того, что описатель
физического линка привязан к определенному физическому адресу. Логический
линк может использоваться только для связи между процессами (напоминаем,
что по принятой в транспьютере терминологии, нити называются процессами),
исполняющимися на одном транспьютере.
Транспьютер Т9000 предоставляет также виртуальные линки— протокол, позволяющий
двум транспьютерам организовать несколько линий взаимодействия через один
физический линк, или даже через цепочку маршрутизаторов.
При передаче данных в линк процесс должен исполнить команду out. Эта команда
имеет три операнда: адрес линка, адрес массива данных и количество данных.
Для передачи операндов используется регистровый стек процессора. Процесс,
исполнивший такую команду, задерживается до тех пор, пока все данные не
будут переданы (рис. 7.8).
Рис. 7.8. Передача данных через линк
Аналогично, при приеме данных из линка, процесс должен
исполнить команду in. Эта команда также имеет
три операнда — адрес линка, адрес буфера, куда необходимо поместить данные,
и размер буфера. При исполнении такой команды процесс блокируется до тех
пор, пока буфер не будет заполнен данными. При этом приемник и передатчик
могут использовать буферы разного размера, т. е. приемник может считывать
большой массив данных в несколько приемов и т. д.
Существует также команда alt, позволяющая процессу
ожидать данные из нескольких линков одновременно. В качестве одного из
ожидаемых событий можно также использовать сигнал от системного таймера.
Слово, связанное с линком, содержит указатель на дескриптор процесса,
ожидающего приема или передачи данных через линк. Кроме того, это слово
может принимать значение NotProcessP, указывающее,
что соединения никто не ждет. Остальная информация, такая, как указатель
на буфер и размер буфера, хранится в дескрипторе процесса.
Направление передачи данных определяется командой, которую исполнит очередной
процесс при обращении к линку. Например, если исполняется команда out,
предназначенные для записи данные копируются в буфер ожидающего процесса.
При этом указатель буфера продвигается, а счетчик размера уменьшается
на количество скопированных данных. Если же в линке записано значение
NotProcessP, процесс переводится в состояние
ожидания и указатель на его дескриптор помещается в линк (рис. 7.9).
Рис. 7.9. Алгоритм работы команд in и out
Аналогично обрабатываются запросы на чтение. Если мы имеем
более двух процессов, пытающихся использовать один линк, то возникает
серьезная проблема: внимательный читатель должен был заметить, что мы
не сказали, где хранится информация о том, чего ожидает текущий процесс:
чтения или записи. Проблема состоит в том, что эта информация нигде не
хранится. Если процесс попытается записать данные в линк, на котором кто-то
уже ожидает записи, то данные второго процесса будут записаны поверх данных
ожидавшего. Если размеры буферов совпадут, то ожидавший процесс будет
пребывать в убеждении, что он успешно передал все данные. Поэтому линки
рекомендуется использовать только для однонаправленной передачи данных
между двумя (не более!) процессами.
При работе с физическим линком данные не копируются, а передаются или
принимаются через физический канал в режиме прямого доступа к памяти.
Если на другом конце линка находится другой транспьютер, это все-таки
можно считать копированием, но к линку может быть подключено и какое-то
другое устройство.
В середине 90-х, в эпоху расцвета микропроцессоров этого семейства, фирма
Inmos поставляла широкий набор трэмов (trem — TRansputer Extension module)
— устройств ввода-вывода с линком в качестве интерфейса. В частности,
поставлялись трэмы, позволявшие подключить к транспьютеру через линк адаптеры
Ethernet или SCSI.
Взаимодействие с внешним устройством через линк позволяет транспьютеру
синхронизовать свою деятельность с этими устройствами без использования
механизма прерываний. В [INMOS 72 TRN 203 02] приводится пример программной
имитации векторных прерываний с передачей вектора по линку
и мониторным процессом, который принимает эти векторы из линка и вызывает
соответствующие обработчики.
