Конвейеры и очереди сообщений Конвейеры

Программный канал связи (pipe), или, как его иногда называют, конвейер, транс­портер, является средством, с помощью которого можно обмениваться данными

Конвейеры и очереди сообщений_______________________________________ 243

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

Конвейер имеет определенный размер¹, который не может превышать 64 Кбайт и работает циклически. Вспомните реализацию очереди на массивах, когда имеются указатели начала и конца очереди, которые перемещаются циклически по массиву. То есть имеется некий массив и два указателя: один показывает на первый элемент (указатель на начало — head), а второй — на последний (указатель на конец — tail).

В начальный момент оба указателя равны нулю. Добавление самого первого эле­мента в пустую очередь приводит к тому, что указатели на начало и на конец при­нимают значение, равное 1 (в массиве появляется первый элемент). В последую­щем добавление нового элемента вызывает изменение значения второго указателя, поскольку он отмечает расположение именно последнего элемента очереди. Чте­ние (и удаление) элемента (читается и удаляется всегда первый элемент из со­зданной очереди) приводит к необходимости модифицировать значение указате­ля на ее начало. В результате операций записи (добавления) и чтения (удаления) элементов в массиве, моделирующем очередь элементов, указатели будут переме­щаться от начала массива к его концу. При достижении указателем значения ин­декса последнего элемента массива значение указателя вновь становится единич­ным (если при этом не произошло переполнение массива, то есть количество элементов в очереди не стало большим числа элементов в массиве). Можно ска­зать, что мы как бы замыкаем массив в кольцо, организуя круговое перемещение указателей на начало и на конец, которые отслеживают первый и последний эле­менты в очереди. Сказанное иллюстрирует рис. 7.4. Именно так функционирует конвейер.

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

¹ Механизм конвейеров, впервые введенный в UNIX-системах, имеет максимальный размер 64 Кбайт, поскольку в 16-разрядных мини-ЭВМ, для которых создавалась эта ОС, нельзя было иметь массив данных большего размера.

244________ Глава 7. Организация параллельных взаимодействующих вычислений

Рис. 7.4. Организация очереди в массиве

В качестве иллюстрации приведем основные системные запросы для работы с кон­вейерами, которые имеются в API OS/2.

- Функция создания конвейера:

DosCreatePipe (SReadHandle. SWriteHandle. PipeSize):

Здесь ReadHandle — дескриптор чтения из конвейера, WriteHandle —

дескриптор записи в конвейер, PipeSize — размер конвейера.

- Функция чтения из конвейера:

DosRead (&ReadHandle. (PVOID)&Inform. sizeof(Inform), &BytesRead): Здесь ReadHandle — дескриптор чтения из конвейера, Inform — переменная любого типа, sizeof(Inform) — размер переменной Inform, BytesRead — количество прочитанных байтов. Данная функция при обращении к пустому конвейеру будет ожидать, пока в нем не появится информация для чтения.

- Функция записи в конвейер:

DosWrite (&WriteHandle. (PVOID)&Inform. sizeof(Inform). &BytesWrite):

Здесь WriteHandle — дескриптор записи в конвейер, BytesWrite — количество

записанных байтов.

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

Очереди сообщений

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

Конвейеры и очереди сообщений_______________________________________ 245

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

Работа с очередями сообщений отличается от работы с конвейерами. Во-первых, очереди сообщений предоставляют возможность использовать несколько дисцип­лин обработки сообщений:

- FIFO — сообщение, записанное первым, будет первым и прочитано; - LIFO — сообщение, записанное последним, будет прочитано первым; - приоритетный доступ — сообщения читаются с учетом их приоритетов;

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

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

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

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

- идентификатор процесса (Process Identifier, PID), который передал сообщение;
- адрес и длина переданного сообщения;

- признак необходимости ждать, если очередь пуста;

- приоритет переданного сообщения;

- номер освобождаемого семафора, когда сообщение передается в очередь.

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

- CreateQueue — создание новой очереди;

- OpenQueue — открытие существующей очереди;

- ReadQueue — чтение и удаление сообщения из очереди;

- PeekQueue — чтение сообщения без его последующего удаления из очереди;

- WriteQueue — добавление сообщения в очередь;

- CloseQueue — завершение использования очереди;
- PurgeQueue — удаление из очереди всех сообщений;

- QueryQueue — определение числа элементов в очереди.

246________ Глава 7. Организация параллельных взаимодействующих вычислений

Контрольные вопросы и задачи

1. Какие последовательные вычислительные процессы мы называем параллель­
ными и почему? Какие параллельные процессы называются независимыми,
а какие — взаимодействующими?

2. Изложите алгоритм Деккера, позволяющий разрешить проблему взаимного
исключения путем использования одной только блокировки памяти.

3. Объясните, как действует команда проверки и установки. Расскажите о рабо­
те команд BTS и BTR, которые имеются в процессорах с архитектурой ia32.

4. Расскажите о семафорах Дейкстры. Чем обеспечивается взаимное исключе­
ние при выполнении примитивов Р и V?

5. Изложите, как могут быть реализованы семафорные примитивы для мульти­
процессорной системы?

6. Что такое мьютекс?

7. Изложите алгоритм решения задачи «поставщик-потребитель» при исполь­
зовании семафоров Дейкстры.

8. Изложите алгоритм решения задачи «читатели-писатели» при использова­
нии семафоров Дейкстры.

9. Что такое «монитор Хоара»? Приведите пример такого монитора.

10. Что представляют собой почтовые ящики?

11. Что представляют собой конвейеры (программные каналы)?

12. Что представляют собой очереди сообщений? Чем отличаются очереди сооб­
щений от почтовых ящиков?