Теперь рассмотрим более сложную задачу: пусть параллельно выполняющиеся задачи имеют статус полноценного вычислительного процесса, а не потока и, кроме этого, организуем обращение к соответствующим системным механизмам непосредственно на уровне API. Схема взаимодействия программ для этого примера изображена на рис. 6.7.
На этом рисунке программа с именем А в точке 1 порождает сразу четыре параллельно выполняющихся задачи (вычислительных процесса): В, С, I и J. Процессы В и С завершаются и должны запустить, в свою очередь, два параллельных процесса D и Е. В точке 2, в которой происходит синхронизация задач В и С, процессы D и Е должны быть запущены той из задач В или С, которая закончит
свое выполнение раньше, но только после момента окончания второй. Далее, в точке 3 необходимо запустить программы G и Н. Запускает их первая завершившая свою работу программа (D, Е или I), но дождавшись завершения остальных программ. Точка 4 синхронизирует выполнение процессов F, G, H и J, при этом программу К запускает последний из завершившихся процессов.
Для решения поставленной задачи будем использовать соответствующие механизмы, описанные нами выше (применительно к OS/2), а именно конвейер (pipe) и семафоры. В нашей задаче через конвейер передается переменная типа Parent-Info:
Parentlnfo — хранит имя программы-предка; LaunchTime — содержит время запуска текущей программы программой-предком (время, когда программа-предок выполнила функцию DosExecPgn); переменная Number указывает, для какого числа программ предназначена переменная Parentlnfo.
Читать из конвейера мы можем при помощи функции DorRead, но при этом уничтожается запись в конвейере, и мы обязаны перезаписывать данные в конвейер для других программ. Каждая программа читает данные из конвейера и затем уменьшает значение Number. Программа, установившая значение 1, является последней программой, прочитавшей данные из конвейера; она посылает сигнал предку о завершении инициализации необходимых ресурсов. Программа пишет в конвейер данные только в том случае, если именно она будет запускать следующие программы.
Для чтения и записи в конвейер необходимы переменные WriteHandle и ReadHandle, указывающие на описатели записи и чтения в конвейер. Необходимо, чтобы значения этих переменных, полученных в процессе А, были известны остальным процессам для совместного использования. Для этого значения этих переменных мы можем передать процессам-потомкам в качестве строк аргументов.
При попытке считывания информации из пустого конвейера процесс переводится в состояние ожидания. После записи информации в конвейер другим процессом ожидающий процесс считывает поступившую информацию и продолжает свою работу.
Поскольку программы, которые мы сейчас рассматриваем, созданы для операционной системы OS/2, приведем краткое описание использованных механизмов, которые имеют отличия от вышеописанных общих принципов и схем.
где "\\SEM\\PIPESEM" — имя семафора, PipeSem — идентификатор семафора, 1 — параметр совместного использования семафора (DC_SEM_SHARED), 0 — зарезервированный системный параметр.
D Функция открытия семафора:
DosOpenEventSem ("\\SEM\\PIPESEM". SPipeSem):
где "\\SEM\\PIPESEM" — имя семафора, PipeSem — идентификатор семафора.
О Функция установки семафора: DosPostEventSem (PipeSem): где PipeSem — идентификатор семафора.
Q Функция сброса семафора:
DosResetEventSem (PipeSem. &NPost):
где PipeSem — идентификатор семафора, NPost — количество обращений к установке семафора с момента последнего сброса.
Q Функция ожидания установки семафора:
DosPostEventSem (PipeSem. -1):
где PipeSem — идентификатор семафора, -1 — ожидание семафора до его установки (положительное значение — это задержка в миллисекундах).
Для синхронизации процессов и обработки критических участков программ необходимы семафоры, к которым имеют доступ все работающие программы. Программа-потомок может унаследовать семафор от программы-предка, которая создала или открыла необходимый семафор. Но это произойдет только тогда, когда программа-предок дождется момента открытия семафора в программе-потомке. Это обеспечивается за счет дополнительных семафоров ExitSeml, ExitSem2, ExitSemS. Когда последняя программа-потомок прочитывает данные из конвейера (работа с конвейером) и обнаруживает, что она последней прошла участок открытия уже созданных семафоров, она устанавливает необходимый семафор, принадлежащий программе-предку: Программа-предок, ожидающая установки семафора, завершает свою работу.
Для управления запуском и завершением программ также используются соответствующие функции.
DosExecPgm (FailFile, sizeof(FailFile), 1, Argument, 0, ResCode, "progr_b.exe") — функция запуска программы-потомка, где
Q Fail File — буфер для'помещения имени объекта, из-за которого возникла ошибка запуска программы, sizeof(FailFile) — размер буфера;
Q 1 означает, что процесс-потомок следует выполнять асинхронно с процессом-предком, Argument — строки аргументов программы, 0 — строки среды, ResCode — результирующие коды запуска программы, "progr_b.exe" — имя запускаемой (планируемой на выполнение) программы;
D DosExit — функция завершения процесса (и всех его подпроцессов);
Q DosSetPriority — установка приоритета программы (и всех его подпроцессов).
Каждую программу в соответствии с заданием создаем как независимую, то есть имеющую свое локальное адресное пространство. Благодаря этому переменные в текстах программ, имеющие одинаковые имена (см. листинги в приложении Б), фактически являются разными переменными.
Программа с именем А является начальной, стартовой. Именно она создает те системные объекты, которыми потом пользуются ее потомки для своей синхронизации. Имена системных объектов они получают в наследство при своем порождении.
Для совместного использования вычислительными процессами одного файла необходимо правильно его открыть в программе А. После корректного открытия или создания файла к нему могут обращаться все программы, имеющие идентификатор открытого файла. Значение этого идентификатора передается запускающимся процессам в строке аргументов, сопровождающих вызов.
В соответствии с заданием каждая программа записывает в файл время своего запуска, имя процесса-предка и время завершения своей работы. Поскольку файл используется всеми программами и запись производится в строгой последовательности, часть программы, которая обеспечивает запись в файл, должна быть признана нами как критический участок программы (критический интервал). Алгоритм обработки этого участка описан ниже. Если не пытаться регулировать доступ процессов к файлу, может возникнуть беспорядочная запись в файл. При регулировании записи каждый процесс производит сразу все три записи в файл.
Опишем теперь алгоритм обработки критических участков программ — записи в файл и работы с конвейером.
Q Критический участок — работа с конвейером.
Приведем фрагмент программы, обеспечивающий чтение из конвейера.
Программа А создает семафор PipeSem, который затем используют все программы для прохождения критической части программы, связанной с чтением и записью в конвейер.
В строке 1 программа ожидает установки семафора PipeSem; после того как этот семафор будет установлен, программа переходит к строке 2. Переменная гс возвращает код ошибки при попытке сбросить семафор в строке 2. Это сделано со следующей целью: если после завершения строки 1 будет выполняться другая программа и она успеет сбросить семафор, то когда программа вновь продолжит свое выполнение, она обнаружит в строке 2, что семафор уже сброшен и гс не будет равно нулю; затем цикл повторится. Так будет продолжаться до тех пор, пока гс не станет равно нулю, то есть текущая программа первой сбросила семафор. Тогда в строке 4 программа считывает из конвейера данные и сигнализирует об освобождении ресурса в строке 5.
Для записи в конвейер используется аналогичный алгоритм. Q Критический участок — запись в файл.
Здесь использован такой же алгоритм, как и при работе с конвейером, но задействован специально созданный для этого семафор FileSem.
Теперь рассмотрим алгоритмы, решающие задачи синхронизации в каждой из точек нашей схемы (см. рис. 6.7). Начнем с прохождения точки 2. Приведем фрагмент исходного текста программы (см. приложение Б).
В точке 2 программы D, E, и F должны быть запущены процессом, который первым завершит свою работу. Для определения последовательности завершения работы программ (В или С) нами используется семафор PointlSem. В строке 1 производится установка данного семафора. Если значение гс не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если гс равно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В строке 3 осуществляется запись в конвейер. Строка 4 — создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 8, затем семафор закрывается. В строках 5—7 осуществляется запуск программ D, E, F.
Теперь приведем алгоритм прохождения точки 3. Фрагмент исходного текста программы изображен ниже.
В точке 3 программы G и Н запускаются той программой, которая первой завершает свою работу, но только после того, как работу завершат остальные программы. Для определения последовательности завершения работы программ (I, D или Е) используется семафор Point2Sem. В строке 1 производится установка данного семафора. Если значение гс не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если гс равно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В этой строке подсчитывается количество обращений к данному семафору. Цикл повторяется до тех пор, пока количество обращений не станет равно 3, то есть когда все остальные программы завершили свою работу. После этого в строке 5 осуществляется запись в конвейер. Строка 6 — создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров
в программах-потомках. Ожидание открытия семафоров происходит в строке 9. В строках 7 и 8 осуществляется запуск программ G и Н соответственно.
Наконец, приведем еще алгоритм прохождения точки 4. Фрагмент исходного текста программы, реализующей эту задачу, приведен ниже.
Итак, в точке 4 программа К запускается задачей, которая последней завершила свою работу. Для определения последовательности завершения работы программ (J, G, Н или F) используется семафор Point3Sem. Каждая программа должна обратиться к данному семафору, установить его и проверить количество обращений к нему. Но при выполнении этих двух операций другие программы могут также установить семафор, и значение обращений к семафору в текущей программе окажется неверным. Для доступа к семафору PointSSem используется семафор PointlSem. В строке 1 программа ожидает установки семафора PointlSem, который сигнализирует о доступности неразделяемого ресурса Point3Sem. В строке 2 семафор сбрасывается, но если другие программы успели сбросить семафор, то об этом сообщит значение гс. Если текущей программе удалось завладеть ресурсом, то есть значение гс равно нулю, то дальше в строках 4, 5 производится установка семафора Poi nt3Sem и подсчет количества обращений. Строка 6 сигнализирует о завершении работы критической части программы установкой семафора PointlSem. Затем, как и в предыдущих алгоритмах, программа записывает информацию в транспортер (строка 8), создает семафор ожидания открытия семафоров в программах-потомках (строка 9), запускает программу К (строка 10) и ожидает открытия семафоров в программе К (строка 11).
Тексты четырех программ (А, В, D и G), действующих по рассмотренным алгоритмам, приведены в приложении Б. Остальные программы аналогичны им и отличаются только использованием других имен.
Контрольные вопросы и задачи
Вопросы для проверки
1. Какие последовательные вычислительные процессы мы называем параллельными и почему? Какие параллельные процессы называются независимыми, а какие — взаимодействующими?
2. Изложите алгоритм Деккера, позволяющий разрешить проблему взаимного исключения путем использования одной только блокировки памяти.
3. Объясните команду «проверка и установка».
4. Расскажите о семафорах Дейкстры. Чем обеспечивается взаимное исключе ние при выполнении Р- и V-примитивов?
5. Изложите, как могут быть реализованы семафорные примитивы для мульти процессорной системы.
6. Что такое мьютекс (mutex)?
7. Изложите алгоритм решения задачи «поставщик — потребитель» при исполь зовании семафоров Дейкстры.
8. Изложите алгоритм решения задачи «читатели — писатели» при использова нии семафоров Дейкстры.
9. Что такое «монитор Хоара»? Приведите пример такого монитора.
10. Что представляют собой «почтовые ящики»?
11. Что представляют собой «конвейеры» (программные каналы)?
12. Что представляют собой «очереди сообщений»? Чем отличаются очереди со общений от почтовых ящиков?