Пример 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] приводится пример программной имитации векторных прерываний с передачей вектора по линку
и мониторным процессом, который принимает эти векторы из линка и вызывает соответствующие обработчики.

Системы, управляемые событиями

В начале 70-х годов появилась новая архитектура многозадачных систем довольно резко отличающаяся от вышеописанной модели последовательных процессов. Речь идет о так называемых системах, управляемых событиями (event-driven systems).
На первый взгляд, концепция систем, управляемых событиями, близко родственна гармонически взаимодействующим процессам. Во всяком случае, одно из ключевых понятий этой архитектуры, очередь событий, мы упоминали в числе средств гармонического межпоточного взаимодействия. Различие между этими архитектурами состоит, скорее, во взгляде на то, что представляет собой программа.
В модели гармонически взаимодействующих потоков процесс исполнения программного комплекса представляет собой совокупность взаимодействующих нитей управления. В системе, управляемой событиями, программа представляет собой совокупность объектов, обменивающихся сообщениями о событиях, а также реагирующих на сообщения, приходящие из внешних источников.
В идеале, объекты взаимодействуют между собой только через сообщения. Приходящие сообщения побуждают объект изменить свое состояние и, возможно, породить некоторое количество сообщений, предназначенных для других объектов. При такой модели взаимодействия нам неважно, исполняются ли методы объектов как параллельные (или псевдопараллельные) нити, или же последовательно вызываются единой нитью, менеджером или диспетчером сообщений.
Впервые эта архитектура была реализована в экспериментальных настольных компьютерах Alto, разработанных в 1973 году в исследовательском центре PARC фирмы Xerox. Целью эксперимента было создание операционной среды, удобной для создания интерактивных программ с динамичным пользовательским интерфейсом.
В этих системах впервые была реализована многооконная графика, когда пользователь одновременно видит на экране графический вывод нескольких программ и может активизировать любую из них, указав на соответствующее окно при помощи манипулятора-"мыши".
При каждом движении мыши, нажатии на ее кнопки или клавиши на клавиатуре генерируется событие. События могут также генерироваться системным таймером или пользовательскими программами. Нельзя не упомянуть "визуальные" события, которые порождаются в ситуации, когда пользователь
сдвинул или закрыл одно из окон и открыл при этом часть окна, находившегося внизу. Этому окну посылается событие, говорящее о том, что ему нужно перерисовать часть себя (рис. 7.10).

Рис. 7.10. Визуальное событие

Каждое сообщение о событии представляет собой структуру данных, которая содержит код, обозначающий тип события: движение мыши, нажатие кнопки и т. д., а также поля, различные для различных типов событий. Для "мышиных" событий — это текущие координаты мыши и битовая маска, обозначающая состояние кнопок (нажата/отпущена). Для клавиатурных событий — это код нажатой клавиши, обычно, ASCII-код символа для алфавитно-цифровых и специальные коды для стрелок и других "расширенных" и "функциональных" клавиш — и битовая маска, обозначающая состояние различных модификаторов, таких как SHIFT, CNTRL, ALT и т. д. Для визуальных событий — это координаты прямоугольника, который нужно перерисовать, и т. д.
Все сообщения о событиях помещаются в очередь в порядке их возникновения.
В системе существует понятие обработчика событий. Обработчик событий Представляет собой объект, т. е. структуру данных, с которой связано несколько подпрограмм — методов. Один из методов вызывается при поступлении сообщения. Обычно он также называется обработчиком событий. Некоторые системы предлагают объектам-обработчикам предоставлять различные методы для обработки различных событий — например, метод onClick будет вызываться, когда придет событие, сигнализирующее о том что кнопка мыши была нажата и отпущена, когда курсор находился над областью, занимаемой объектом на экране.
Рассмотрим объект графического интерфейса, например меню. При нажатии на кнопку мыши в области этого меню вызывается обработчик события Он разбирается, какой из пунктов меню был выбран, и посылает соответствующее командное сообщение объекту, с которым ассоциировано меню Этот объект, в свою очередь, может послать командные сообщения каким-то другим объектам. Например, если была выбрана команда File/Open, меню передаст обработчику основного окна приложения сообщение FILEOPEN, а тот, в свою очередь, может передать команду Open объекту, отвечающему за отрисовку и обработку файлового диалога.
Таким образом, вместо последовательно исполняющейся программы, время от времени вызывающей систему для исполнения той или иной функции, мы получаем набор обработчиков, вызываемых системой в соответствии с желаниями пользователя. Каждый отдельный обработчик представляет собой конечный автомат, иногда даже вырожденный, не имеющий переменной состояния. Код обработчика и по реализации обычно похож на конечный
автомат, и состоит m большого оператора switch, выбирающего различные действия в зависимости от типа пришедшего сообщения (пример 7.8).

Пример 7.8. Обработчик оконных событий в OS/2 Presentation Manager

/* фрагмент примера из поставки IBM Visual Age for C++ 3.0.
* Обработчик событий меню предоставляется системой,
* а обработку командных событий, порождаемых меню,
* вынужден брать на себя разработчик приложения. */
/****************************************************************
Copyright (С) 1992 IBM Corporation
ОТКАЗ ОТ ГАРАНТИЙ. Следующий код представляет собой пример кода созданный IBM Corporation. Этот пример кода не является частью ни одного стандарта или продукта IBM и предоставляется вам с единственной целью — помочь в разработке ваших приложений. Код предоставляется "КАК ЕСТЬ", без каких-либо гарантий. IBM не несет ответственности за какие бы то ни было повреждения, возникшие в результате использования вами этого кода, даже если она и могла предполагать возможность таких повреждений.

/****************************************************************
* Имя: MainWndProc *
Описание: Оконная процедура главного окна клиента. *
* Концепции: Обрабатывает сообщения, посылаемые главному
окну клиента. Эта процедура обрабатывает основные сообщения, которые должны обрабатывать все клиентские окна, и передает все остальные [функции] UserWndProc, в которой разработчик может обработать любые другие
сообщения. *
API: He используются
* Параметры: hwnd — Идентификатор окна, которому адресовано сообщение
* msg — Тип сообщения
* mpl — Первый параметр сообщения
* тр2 — Второй параметр сообщения.
* Возвращаемое значение: определяется типом сообщения
*/
****************************************************************
MRESULT EXPENTRY MainWndProc(HWND hwnd, USHORT msg, MPARAM mpl,
MPARAM mp2)
{
switch(msg) {
case WM_CREATE:
return(InitMainWindow(hwnd, mpl, mp2)};
break;
case WM_PAINT:
«
MainPaint(hwnd); break;
case WM_COMMAND:
MainCommand(mpl,. mp2); break;
case WM_INITMENU:
Ini tMenu(mpl, mp2); break;
case HM_QUERY_KEYS_HELP:
return (MRESULT)PANEL_HELPKEYS;/* Вернуть Id панели подсказки ' break;
/*
* Все необработанные сообщения передаются
* пользовательской процедуре окна.
* Она отвечает за передачу всех необработанных
* сообщений функции WinDefWindowProc(); */
default:
return(UserWndProc(hwnd, msg, mpl, mp2)); break;
return (MRESULT)O; /* Все оконные процедуры должны по умолчанию возвращать 0 */
} /* Конец MainWndProc() */

/****************************************************************
* Имя: MainCommand
* Назначение: Главная процедура окна, обрабатывающая WM_COMMAND *
* Концепции: Процедура вызывается, когда сообщение WM_COMMAND
* отправляется главному окну. Оператор switch
* переключается в зависимости от id меню, которое
* породило сообщение и предпринимает действия,
* соответствующие этому пункту меню. Все id меню,
* не являющиеся частью стандартного набора команд,
* передаются пользовательской процедуре обработки
* WM_COMMAND.
* API: WinPostMsg *
* Параметры: mpl — Первый параметр сообщения
тр2 — Второй параметр сообщения *
* Возвращает: VOID *
\*************+**************************************************^
VOID MainCommand(MPARAM mpl, MPARAM mp2)
switch(SHORT1FROMMP(mpl))
I
case IDM_EXIT:
WinPostMsg(hwndMain, WM_QUIT, NULL, NULL break;
case IDM__FILENEW: FileNew(mp2); break;
case IDM_FILEOPEN: FileOpen(mp2); break;
case IDM_FILESAVE: FileSave(mp2); break;
case IDM_FILESAVEAS: FileSaveAs(mp2); break;
case IDM_EDITUNDO: EditUndo(mp2); break;
case IDM_EDITCUT: EditCut(mp2); break;
case IDM_EDITCOPY: EditCopy(mp2); break;
case IDM_EDITPASTE: EditPaste(mp2); break;
case IDM_EDITCLEAR: EditClear(mp2); break;
case IDM_HELPUSINGHELP: HelpUsingHelp(mp2); break;
case IDM_HELPGENERAL: HelpGeneral(mp2); break;
case IDM_HELPKEYS: HelpKeys(mp2); break;
case IDM_HELPINDEX: Helplndex(mp2); break;
case IDM_HELPPRODINFO: HelpProdInfo(mp2); break; /*
* Здесь вызывается пользовательская процедура
* обработки команд, чтобы обработать те id',
* которые еще не были обработаны. */
default:
UserCammand(mpl, mp2); break;)
} /* MainCommand() */

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

Рис. 7.12. Менеджер и обработчики событий

В такой ситуации (а при написании реальных приложений она возникает сплошь и рядом) мы и вынуждены задуматься о том, что же в действительности представляют собою обработчики — процедуры, синхронно вызываемые единственной нитью менеджера событий, или параллельно исполняющиеся нити. Первая стратегия называется синхронной обработкой сообщений, а вторая, соответственно, — асинхронной.
Графические интерфейсы первого поколения — Mac OS, Winl6 — реализовывали синхронную обработку сообщений, а когда обработчик задумывался надолго, рисовали неотъемлемый атрибут этих систем — курсор мыши в форме песочных часов.
Несколько более совершенную архитектуру предлагает оконная подсистема OS/2, Presentation Manager. PM также реализует синхронную стратегию обработки сообщений (менеджер событий всегда ждет завершения очередного обработчика), но в системе, помимо менеджера событий, могут существовать и другие нити. Если обработка события требует длительных вычислений или других действий (например, обращения к внешним устройствам или к сети), рекомендуется создать для этого отдельную нить и продолжить обработку асинхронно. Если же приложение этого не сделает (например, обработчик события просто зациклится или заснет на семафоре), системная очередь сообщений будет заблокирована и ни одно из графических приложений не сможет работать. Современные версии РМ предоставляют в этом случае возможность отцепить "ненормальное" приложение от очереди или паже принудительно завершить его.
Асинхронные очереди сообщений предоставляют Win32 и оконная система X Window. Впрочем, и при асинхронной очереди впавший в философские размышления однопоточный обработчик событий — тоже малоприятное зрелище, ведь он не может перерисовать собственное окно, поэтому передвижение других окон по экрану порождает любопытные спецэффекты (к сожалению, запечатлеть эти эффекты при помощи утилит сохранения экрана невозможно — все известные автору средства дожидаются, пока все попавшие в сохраняемую область окна перерисуются. А фотографии монитора обычно имеют низкое качество). Разработчикам приложений для названных систем также рекомендуется выносить длительные вычисления в отдельные нити.
Большинство реальных приложений для современных ОС, имеющих пользовательский интерфейс, таким образом, имеют двух- или более слойную архитектуру. При этом архитектура ближайшего к пользователю стоя (frontend), как правило, тяготеет к событийно-управляемой, а следующие слои (backend) обычно состоят из более традиционных взаимодействующих (не всегда, впрочем, строго гармонически) параллельно исполняющихся нитей, зачастую даже разнесенных по разным вычислительным системам.

Глава 8. Реализация многозадачности на однопроцессорных компьютерах

• Реализация многозадачности на однопроцессорных компьютерах
• Кооперативная многозадачность
• Вытесняющая многозадачность
• Планировщики с приоритетами
• Монолитные системы и системы с микроядром

Реализация многозадачности на однопроцессорных компьютерах

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

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

Кооперативная многозадачность

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

• struct Thread; В тексте будет обсуждаться, что должна представлять собой эта структура, называемая дескриптором нити.
• Thread * ThreadCreate(void (*ThreadBody)(void)); Создать нить, исполняющую функцию ThreadBody.
• void Threadswitch(); Эта функция приостанавливает текущую нить и активизирует очередную, готовую к исполнению.
• void ThreadExit (); Прекращает исполнение текущей нити.

Сейчас мы не обсуждаем методов синхронизации нитей и взаимодействия
между ними (для синхронизации были бы полезны также функции void
DeactivateThread(); И void ActivateThread(struct Thread *);). Нас интересует только вопрос: что же мы должны сделать, чтобы переключить нити?
функция ThreadSwitch называется диспетчером или планировщиком (scheduler) и ведет себя следующим образом.

• Она передает управление на следующую активную нить.
• Текущая нить остается активна, и через некоторое время снова получит управление.
• При этом она получит управление так, как будто ThreadSwitch представляла собой обычную функцию и возвратила управление в точку, из которой она была вызвана.

Очевидно, что функцию ThreadSwitch нельзя реализовать на языке высокого уровня, вроде С, потому что это должна быть функция, которая не возвращает [немедленно] управления в ту точку, из которой она была вызвана. Она вызывается из одной нити, а передает управление в другую. Это требует прямых манипуляций стеком и записью активизации и обычно достигается использованием ассемблера или ассемблерных вставок. Некоторые ЯВУ (Ada, Java, Occam) предоставляют примитивы создания и переключения нитей в виде специальных синтаксических конструкций.
Самым простым вариантом, казалось бы, будет простая передача управления на новую нить, например, командой безусловной передачи управления по указателю. При этом весь описатель нити (struct Thread) будет состоять только из адреса, на который надо передать управление. Беда только в том, что этот вариант не будет работать.
Действительно, каждая из нитей исполняет программу, состоящую из вложенных вызовов процедур. Для того чтобы нить нормально продолжила исполнение, нам нужно восстановить не только адрес текущей команды, но и стек вызовов (см. разд. Косвенно-регистровый режим со смещением). Поэтому мы приходим к такой архитектуре.