Межзадачное взаимодействие

Определения

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

Понятие программы интуитивно очевидно - это набор команд, который можно загрузить в память и на который можно передать управление. Часто программой называют цельный загрузочный модуль. Для систем типа MS DOS или UNIX такое определение может быть разумным, и в этом смысле мы можем назвать MS DOS многопрограммной системой, но для систем с динамической сборкой оно просто не имеет смысла.

Процесс представляет собой программу, которая исполняется последовательно. При этом ее исполнение может быть прервано передачей управления другому процессу, но после этого оно должно быть возобновлено с той точки, где прервалось. В операционных системах OS/2 и Windows NT определенному таким образом процессу соответствует понятие нити (thread).

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

Точнее говоря, задачи могут разделять код программы, но каждая задача обязана иметь собственную копию локальных (auto в терминах языка C) и статических (static и extern) данных. Вообще-то задачи могут иметь разделяемые данные, но такое разделение организуется специальными средствами.

Понятно, что в рамках одной задачи может исполняться несколько процессов. С другой стороны, можно привести пример многозадачной однопроцессной операционной системы - MS Windows 3.x.

Действительно, в MS Windows 3.1 в standard и enhanced режимах каждая запущенная программа формирует отдельную задачу со своим адресным пространством. Однако для этой программы не создается иллюзии последовательного исполнения. Напротив, программа представляет собой набор обработчиков событий - объектов, часто представляющих собой простые конечные автоматы. С каждым таким объектом связан соответствующий модуль программы. В документации такой модуль называется callback.

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

Во многих операционных системах, например в UNIX, понятия задачи и процесса почти совпадают - с каждым процессом ассоциировано свое виртуальное адресное пространство. Новый процесс формируется системным вызовом fork, который также формирует и новое виртуальное адресное пространство.

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

Example:

    int pid; /* Идентификатор порожденного процесса */

    switch(pid = fork())
    {
        case 0: /* Порожденный процесс */
           ......
        break;
        case -1: /* Ошибка */
           perror("Cannot fork");
           exit(1);
        default: /* Родительский процесс */
           ......
        /* Здесь мы можем ссылаться на порожденный процесс,
         *  используя значение pid */
    }

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

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

Example:

  int pid; /* Идентификатор порожденного процесса */

  switch(pid = fork())
  {
     case 0: /* Порожденный процесс */
        dup2(1, open("ls.log", O_WRONLY | O_CREAT));
        /* Перенаправить открытый файл #1
         * (stdout) в файл ls.log */

        execl("/bin/sh", "sh", "-c", "ls", "-l", 0);

     /* Сюда мы попадаем только при ошибке! */
     /* fall through */
     case -1: /* Ошибка */
         perror("Cannot fork or exec");
         exit(1);
     default: /* Родительский процесс */
         ......
     /* Здесь мы можем ссылаться на порожденный
      * процесс, используя значение pid */
  }

Программа в примере 8 запускает командный интерпретатор /bin/sh, известный как Bourne shell, приказывает ему исполнить команду ls -l и перенаправляет стандартный вывод этой команды в файл ls.log.

Техника программирования, основанная на fork/exec, несколько менее красива, чем принятая в современных системах реального времени или в языке Ada, где новый процесс исполняет свою программу, а не ту же самую, что и родительский. Кроме того, на системах без диспетчера памяти fork требует копирования адресных пространств, что приводит к большим накладным расходам, да и просто не всегда возможно.

Наиболее простым аргументом в пользу fork является то, что на основе fork достаточно легко можно смоделировать описанную выше функцию processCreate(void (*processBody)()), а на основе processCreate смоделировать fork нельзя. Такой аргумент звучит не очень серьезно, пока мы не вспомним, что на основе этой техники написано довольно много простых и удобных прикладных и системных программ, например, тот же Bourne shell. Поэтому функция fork внесена в стандарт POSIX и, вообще, охраняется законом и традициями.

Более важная причина, которая, по-видимому, и заставила отцов-основателей Unix остановиться на fork/exec вместо processCreate - это... количество параметров процедуры processCreate, которое могло бы оказаться необходимым. Действительно, в промежутке между вызовами fork и exec родительская программа может настроить многие свойства порождаемой задачи. Каждому из настраиваемых таким образом свойств соответствует параметр эквивалентной функции processCreate. Давайте посмотрим на список настраиваемых свойств:

Эти параметры изменяются почти при каждом вызове fork/exec. Параметры, перечисленные ниже, изменяют не так часто, но они оказывают серьезное воздействие на исполнение порожденной задачи, и нередко бывает необходимо настроить их.

Итак, мы получили более десяти параметров, которые следовало бы передать функции processCreate, не считая имени запускаемой программы и позиционных аргументов (argc/argv). Необходимо также учесть, что многие аргументы представляют собой не скалярные значения, а массивы, каждый элемент которых также нуждается в настройке.

В свете сказанного преимущество fork/exec перед processCreate представляется очевидным.

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

Разделяемая память

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

Самое интересное состоит в том, что можно организовать разделяемую память и для задач, исполняющихся на различных машинах. Для этого необходим блок двухпортовой памяти, подключенный к системным шинам обеих машин. Такое решение часто используется в многопроцессорных системах, особенно когда нам нужно организовать быстрый обмен большими (десятки мегабайт) объемами данных. Например, по такой схеме организован обмен между основным(и) процессорами и видеопроцессором в графических станциях Silicon Graphics.

Можно создать разделяемую между машинами память и в том случае, если машины не имеют физической общей памяти. Для этого необходимо использовать диспетчер памяти. Реализация относительно проста: диспетчер памяти отслеживает все записи в ``разделяемый'' сегмент, а затем системы тем или иным способом обеспечивают синхронизацию содержимого измененных сегментов. Беда только в том, что этот метод требует относительно больших накладных расходов.

Теоретики не очень любят разделение памяти, потому что оно влечет за собой все проблемы, перечисленные в предыдущем разделе: необходимость синхронизации, критические секции и т.д. На практике, однако, оно часто оказывается необходимым, так как обеспечивает наибольшую скорость обмена данными - до сотни мегабайт в секунду для современных компьютеров. Тем не менее, используя разделяемую память, мы должны также использовать для синхронизации какие-либо другие средства. В OS/2, Windows NT и системах типа VxVorks чаще всего используются семафоры.

Средства для гармонического межпроцессного взаимодействия

Ряд систем предоставляет более простые в использовании средства, предоставляющие обмен данных одновременно с синхронизацией. Одним из наиболее типичных средств такого рода является труба (pipe) или программный канал - основное средство взаимодействия между процессами в ОС семейства Unix.

Трубы (програмные каналы)

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

Читающий процесс может проверить наличие данных в трубе и предпринять какие-то действия в случае их отсутствия. Пишущий процесс также может проверять трубу на переполнение.

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

Самым интересным свойством трубы является то, что чтение данных из трубы и запись в нее осуществляется теми же самыми системными вызовами read и write, что и работа с обычным файлом или внешним устройством типа терминала. На этом основана техника переназначения ввода-вывода, широко используемая в командных интерпретаторах UNIX. Эта техника состоит в том, что большинство системных утилит получают данные из потока стандартного ввода (stdin) и выдают их в поток стандартного вывода (stdout). При этом, подсовывая в качестве этих потоков терминальное устройство, файл или трубу, мы можем использовать в качестве ввода, соответственно: текст, набираемый с клавиатуры, содержимое файла или стандартный вывод другой программы. Аналогично мы можем выдавать данные сразу на экран, в файл или передавать их на вход другой программы.

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

Трубы широко используются системами семейства Unix и они внесены в стандарт POSIX. Ряд операционных систем, не входящих в семейство Unix, например VxWorks, также предоставляют этот сервис.

Система VMS предоставляет средства, отчасти аналогичные трубам, называемые почтовые ящики (mailbox). Почтовый ящик также представляет собой кольцевой буфер, доступ к которому осуществляется теми же системными вызовами, что и работа с внешним устройством. Системная библиотека языка VAX C использует почтовые ящики для реализации труб, в основном совместимые с UNIX и стандартом POSIX.

В системе UNIX труба создается системным вызовом pipe(int fildes[2]). Этот вызов создает трубу и помещает дескрипторы файлов, соответствующие входному и выходному концам трубы, в массив fildes. Затем мы можем выполнить fork, в различных процессах переназначить соответствующие концы трубы на место stdin и stdout и запустить требуемые программы. При этом мы получим типичный конвейер - две задачи, стандартный ввод и вывод которых соединены трубой.

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

Для связи между неродственными задачами используется другое средство - именованные трубы (named pipes) в System V и UNIX domain sockets в BSD UNIX. В разных системах именованные трубы создаются различными системными вызовами, но очень похожи по свойствам. Поэтому стандарт POSIX предлагает для создания именованных труб библиотечную функцию mkfifo(const char * name, mode_t flags);. Эта функция создает специальный файл. Открывая такой файл, программа получает доступ к одному из концов трубы. Когда две программы откроют именованную трубу, они смогут использовать ее для обмена данными точно так же, как и обычную.

Линки

В транспьютерах микропрограммно реализован линки (links - связь): механизм, отчасти похожий на трубы.

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

Физический линк представляет собой последовательный интерфейс RS432, реализованный на кристалле процессора. С линком также ассоциировано одно слово памяти, смысл которого будет объяснен ниже.

Современные транспьютеры имеют четыре физических линка. Физические линки могут передавать данные со скоростью до 20 Mbaud и могут использоваться как для соединения транспьютеров между собой, так и для подключения внешних устройств. Поэтому физический линк может использоваться как для связи между процессами на разных транспьютерах, так и для синхронизации процесса с внешними событиями, и даже просто для ввода/вывода.

Логический линк - это просто структура данных, выделенная в физическом адресном пространстве процессора. С точки зрения программы физический и логический линки ничем не отличаются, кроме того, что описатель физического линка привязан к определенному физическому адресу. Логический линк может использоваться только для связи между процессами, исполняющимися на одном транспьютере.

Транспьютер T9000 предоставляет также виртуальные линки - протокол, позволяющий двум транспьютерам организовать несколько линий взаимодействия через один физический линк, или даже через цепочку маршрутизаторов.


*
Как уже говорилось, процессы взаимодействуют через физические, логические и виртуальные линки совершенно одинаково. Поэтому мы можем отладить параллельную программу в однопроцессорной системе, а потом запустить ее в гиперкубе из 64К транспьютеров - и она будет вести себя точно также, только начнет работать в 64К раз быстрее.
*

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

Аналогично, при приеме данных из линка, процесс должен исполнить команду in. Эта команда также имеет три операнда - адрес линка, адрес буфера, куда необходимо поместить данные и размер буфера. При исполнении такой команды процесс блокируется до тех пор, пока буфер не будет заполнен данными. При этом приемник и передатчик могут использовать буфера разного размера, т.е. приемник может считывать большой массив данных в несколько приемов и т.д.

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

Слово, связанное с линком, содержит указатель на дескриптор процесса, ожидающего на линке. Кpоме того, это слово может пpинимать значение NotProcessP, указывающее, что линка никто не ждет. Остальная инфоpмация, такая, как указатель на буфер и pазмер буфера, хpанится в дескpиптоpе пpоцесса.

Hапpавление пеpедачи данных опpеделяется командой, котоpую исполнит очеpедной пpоцесс пpи обpащении к этому линку. Hапpимеp, если исполняется команда out, предназначенные к записи данные копируются в буфер ожидающего пpоцесса. При этом указатель буфера продвигается, а счетчик размера уменьшается на количество скопированных данных. Если же в линке записано значение NotProcessP, пpоцесс пеpеводится в состояние ожидания и указатель на его дескpиптоp помещается в линк.

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

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

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

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


*
Интересно, что в версиях ОС Unix, основанных на микроядре, трубы реализованы именно таким образом: микроядро предоставляет низкоуровневые операции send и receive, функционально очень похожие на команды in и out транспьютера. Системные вызовы read и write представляют собой относительно высокоуровневый интерфейс к командам микроядра. Эти вызовы обмениваются данными через буферный процесс, создаваемый в ядре системы при инициализации трубы.
*

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

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

В начале 70-х годов появилась новая архитектура многозадачных систем, довольно резко отличающаяся от вышеописанной модели последовательных процессов. Речь идет о так называемых системах, управляемых событиями (event-driven systems).

Впервые эта архитектура была реализована в экспериментальных настольных компьютерах Alto, разработанных в 1973 году в исследовательском центре PARC фирмы Xerox. Целью эксперимента было создание операционной среды, удобной для создания интерактивных программ.

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

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

Каждое событие представляет собой структуру данных, которая содержит код, обозначающий тип события: движение мыши, нажатие кнопки и т.д., а также поля, различные для различных типов событий: для ``мышиных'' событий это текущие координаты мыши и битовая маска, обозначающая состояние кнопок (нажата/отпущена). Для клавиатурных событий это код нажатой клавиши - обычно, ASCII для алфавитно-цифровой клавиатуры и специальные коды для стрелок и других ``расширенных'' клавиш - и битовая маска, обозначающая состояние различных модификаторов, таких как SHIFT, CNTRL, ALT и т.д.; для визуальных событий это координаты прямоугольника, который нужно перерисовать, и так далее.

Все события помещаются в очередь в порядке их возникновения.

В системе существует понятие обработчика событий. Обработчик событий представляет собой объект, то есть структуру данных, с которой связано несколько программных модулей - методов. Один из методов вызывается при поступлении события и называется callback (дословно - ``вызов назад'').

Представим себе простой объект, такой как меню. При нажатии на кнопку мыши в области этого меню вызывается callback. Он разбирается, какой из пунктов меню был выбран, и вызывает соответствующую функцию обработки этого пункта. Таким образом, вместо последовательно исполняющейся программы, время от времени вызывающей систему для исполнения той или иной функции, мы получаем набор callback'ов, вызываемых системой в соответствии с желаниями пользователя. Отсюда, видимо, и происходит термин ``callback'' - это ``системный вызов, идущий в обратном направлении''.

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

Легко понять, что менеджер и обработчики событий достаточно органично вписываются в традиционную многозадачную ОС. События становятся дополнительным средством синхронизации и передачи данных, удобным для организации пользовательского интерфейса. В других ситуациях программист может пользоваться другими средствами. Так устроены Windows NT и оконная подсистема OS/2 - Presentation Manager. Особенно любопытен в этом отношении опыт сетевой оконной системы X Windows, где передача событий реализована на основе стандартных средств межпроцессного взаимодействия: труб или разделяемой памяти при работе в пределах одной машины и сокетов при взаимодействии с удаленной машиной.

Однако наиболее распространенные в настоящее время событийные системы: MS Windows 3.x и MacOS реализуют иной подход.

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

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

В Windows 3.x для этой цели предоставляется возможность регистрировать так называемые VxD - модули, исполняющиеся с привилегиями ядра системы. Такие модули могут непосредственно обрабатывать внешние события и реагировать на них, не отдавая управления ядру. В Windows 3.x и Windows 95 VxD являются единственным средством, пригодным для реализации приложений, нуждающихся в жесткой синхронизации, например, для синхронизации звука и изображения в multimedia.

Это техническое решение очень характерно для фирмы Microsoft: вместо полноценной реализации той или иной функции предоставлять разработчикам приложений недокументированные ``задние двери''. Занятно, что большинство таких задних дверей так или иначе относятся к многопроцессности, синхронизации и межпроцессному взаимодействию.

Так, вместо защиты ядра MS DOS от повторных вызовов и нормального сервиса для обработки прерываний, Microsoft реализовал недокументированный флаг занятости ДОС.

Вместо вытесняющей многопроцессности в Windows 3.x предоставлен системный вызов getNextEvent

Вместо полноценных средств синхронизации и быстрой реакции на события в Windows 3.x предоставлены VxD, то есть возможность искажения работы ядра системы.

Самым интересным во всем этом является тот печальный факт, что программы, использующие VxD, не могут исполняться в ОС Windows NT, которую Microsoft рекламирует в качестве ``системы будущего''... 


Next: Реализация многопроцессности на традиционных (однопроцессорных) компьютерах Up: Contents

Т.Б.Большаков: tbolsh@inp.nsk.su
Д.В.Иртегов fat@cnit.nsu.ru
latex2html conversion Thu Mar 27 14:44:19 NSK 1997