Взаимодействующих вычислительных

Процессов

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

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

Для иллюстрации различий в организаций взаимодействия полноценных вычис­лительных процессов и многозадачных (многопотоковых) приложений приведём два примера реализации, что позволит увидеть разные механизмы.

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

 

Пример создания многозадачного приложения с помощью системы программирования Borland Delphi

Рассмотрим пример использования механизмов, специально созданных для ор­ганизации взаимного исключения, которые имеются в системе программирования Borland Delphi 3.0. Эта система программирования, будучи ориентирован­ной на создание приложений в многозадачной операционной системе Microsoft Windows 9x, содержит в себе стандартные классы, позволяющие без особых уси­лий использовать многопоточные возможности этих ОС. Воспользуемся стан­дартным классом TThread. Объект, создаваемый на основе этого класса, можно охарактеризовать следующими теперь уже очевидными для нас свойствами:

¨ каждый тред имеет свою, при необходимости уникальную, исполняемую часть;

¨ каждый тред для своего исполнения требует отдельного процессорного времени, то есть диспетчер задач принимает во внимание только приоритет треда;

¨ диспетчеризация выполнения тредов осуществляется операционной системой и не требует вмешательства программиста;

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

Итак, пусть необходимо создать многопоточное приложение, схема взаимодейст­вия отдельных потоков в котором (в рамках единого вычислительного процесса) приведена на рис. 6.6.

Рис. 6.6. Схема №1 взаимодействия параллельно выполняющихся задач

Так, согласно этому рисунку, процесс А после своего завершения запускает зада­чи D, С и Е. Считаем, что задачи В, D и С завершаются примерно в одинаковое время. По крайней мере, нам не известно, какой из потоков должен быть первым, а какой – последним. Однако по условиям задачи пусть поток F будет запус­каться тем из перечисленных тредов, который завершается первым, но только после того, как завершатся два оставшихся треда, приходящие в «точку синхро­низации». Наконец, пусть задача G запускается последним закончившим работу потоком Е или F.

Все указанные задачи создадим как потомки объекта TThread. Тексты всех про­граммных модулей приведены в приложении А. Поскольку, согласно условию, действия, выполняемые задачами, для нас не имеют значения, представим исполняемую часть простейшим циклом с соответствующей задержкой. Для нагляд­ности внутри цикла можно организовать вывод текущего состояния выполнения задачи в процентах на «строке состояния», для чего используем компонент TGauge. Благодаря тому, что все семь тредов похожи (используют одни и те же методы) и отличаются только в части принятия решения о синхронизации, опишем орга­низацию базового объекта-треда.

Базовый объект (TTreadProgress) является потомком объекта TTread. При этом он имеет следующие поля:

¨ имя треда;

¨ строка состояния треда;

¨ «длина» треда (время его работы в отсутствие конкурентов);

¨ текущее состояние треда;

¨ признак завершения треда;

¨ имя запустившего треда;

¨ строка для вывода сообщений в компонент TMemo.

В базовом объекте объявлены следующие процедуры:

¨ исполняемая часть;

¨ завершающая часть;

¨ процедура прорисовки строки состояния;

¨ процедура вывода сообщения;

¨ конструктор объекта.

Все треды (от А до G) являются потомками этого объекта и перекрывают един­ственный метод – процедуру завершения процесса. В исполняемой части задачи после завершения цикла задержки, имитирующего выполнение полезной работы, устанавливается признак завершения и вызывается процедура завершения задачи, которая и выполняет соответствующие действия.

Общую схему работы программы, реализующей задание, можно описать следую­щим образом. Все задачи инициализируются соответствующей процедурой одновременно, но в режиме ожидания запуска. В качестве параметров инициализа­ции в создаваемый поток передаются его имя, длительность и имя запускающего объекта (если оно известно заранее). Сразу после инициализации запускаются задачи А и В. Обе задачи сигнализируют об этом соответствующим сообщением. После своего завершения поток А запускает задачи (потоки) С, D и Е. Далее всё идет в соответствии с заданной блок-схемой. Задача, запускающая другую зада­чу, передаёт ей свое имя, обращаясь непосредственно к полю этого объекта. Ин­формацию о том, завершился тот или иной поток, можно получить, обратившись к соответствующему полю – признаку завершения задачи.

Естественно, что при подобной организации доступа к полям тредов вероятно возникновение разного рода критических ситуаций. Напомним, основная причи­на их возникновения заключена в том, что несколько задач (в нашем случае – потоков) реально имеют возможность обращения к общим ресурсам практиче­ски одновременно, то есть с таким интервалом времени, за который этот ресурс не успеет изменить своё состояние. В результате задачи могут получать некор­ректные значения, о чем мы уже немало говорили.

Каждый процесс имеет связь с так называемыми VCL-объектами – видимыми компонентами. В данном случае такими являются строка состояния TGauge и поле сообщений TMemo. Для того чтобы в процессе работы нескольких парал­лельно выполняющихся задач не возникало критических ситуаций с выводом информации на эти видимые на экране объекты, к ним необходимо обеспечить синхронизированный доступ. Это довольно легко достигается с помощью стан­дартного для объекта TThread метода Synchronize. Метод имеет в качестве пара­метра имя процедуры, в которой производится вывод на VCL-объекты. При этом сама эта процедура нигде в программе не должна вызываться напрямую без ис­пользования метода Synchronize. В нашей программе такими процедурами явля­ются прорисовка строки состояния (Do Visual Progress) и вывод текстового сообщения (WriteToMemo). Подобное использование метода Synchronize обес­печивает корректную работу нескольких параллельных процессов с VCL-объектами.

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

В системе программирования Delphi для этой цели имеется довольно-таки про­стой в использовании и достаточно эффективный метод критической секции с помощью объекта TCriticalSection. Этот метод заключается в следующем:

¨ участок кода каждого потока, в котором производится обращение к общему ресурсу, заключается в «скобки» критической секции – используются мето­ды Enter и Leave;

¨ если какой-либо тред уже находится внутри критической секции, то другой поток, который дошел до «открывающей скобки» Enter, не имеет права вхо­дить в критическую секцию до тех пор, пока первый поток находится в ней. Когда первый тред выйдет из критической секции, второй сможет войти в неё и, в свою очередь, обратиться к критическому ресурсу.

Очевидно, что такой метод надежно обеспечивает задачам монопольный доступ к общим (критическим) ресурсам.

Метод критической секции имеет ряд преимуществ перед его аналогами. Так, например, использование семафоров (Semaphore) сложнее в реализации. Другой метод взаимных исключений – mutex – в целом похож на метод критической секции, но он требует больше системных ресурсов и имеет своё время тайм-аута, по истечении которого ожидающий процесс может всё-таки войти в защищён­ный блок, в то время как в критической секции подобного механизма нет.

Текст всей программы с необходимыми комментариями приведен в приложении А.

 

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

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

Рис. 6.7. Схема № 2 взаимодействия параллельно выполняющихся вычислительных процессов

На этом рисунке программа с именем А в точке 1 порождает сразу четыре парал­лельно выполняющихся задачи (вычислительных процесса): В, С, I и J. Процессы В и С завершаются и должны запустить, в свою очередь, два параллельных процесса D и Е. В точке 2, в которой происходит синхронизация задач В и С, процессы D и Е должны быть запущены той из задач В или С, которая закончит свое выполнение раньше, но только после момента окончания второй. Далее, в точке 3 необходимо запустить программы G и Н. Запускает их первая завершившая свою работу программа (D, Е или I), но дождавшись завершения остальных программ. Точка 4 синхронизирует выполнение процессов F, G, Н и J, при этом программу К запускает последний из завершившихся процессов.

Для решения поставленной задачи будем использовать соответствующие меха­низмы, описанные нами выше (применительно к OS/2), а именно конвейер (pipe) и семафоры. В нашей задаче через конвейер передается переменная типа

ParentInfo:

struct ParentInfo

{

char ParentName [15];

char LaunchTime [12];

int Number;

}

Parentlnfo – хранит имя программы-предка; LaunchTIme – содержит время запус­ка текущей программы программой-предком (время, когда программа-предок выполнила функцию DosExecPgm); переменная Number указывает, для какого числа программ предназначена переменная ParentInfo.

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

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

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

Поскольку программы, которые мы сейчас рассматриваем, созданы для операци­онной системы OS/2, приведём краткое описание использованных механизмов, которые имеют отличия от вышеописанных общих принципов и схем.

¨ Функция создания семафора:

DosCreateEventSem (“\\SEM\\PIPESEM”, & PipeSem, 1, 0);

где " \\SEM\\PIPESEM" – имя семафора, PipeSem – идентификатор семафора, 1 – параметр совместного использования семафора (DC_SEM_SHARED), 0 – зарезер­вированный системный параметр.

¨ Функция открытия семафора:

DosOpenEventSem (" \\SEM\\PIPESEM", & PipeSem);

где ''\\SEM\\PIPESEM" – имя семафора, PipeSem – идентификатор семафора.

¨ Функция установки семафора:

DosPostEventSem (PipeSem);

где PipeSem – идентификатор семафора.

¨ Функция сброса семафора:

DosResetEventSem (PipeSem, & NPost);

где PipeSem – идентификатор семафора, NPost – количество обращений к установке семафора с момента последнего сброса.

¨ Функция ожидания установки семафора:

DosPostEventSem (PipeSem, -1):

где PipeSem – идентификатор семафора, -1 – ожидание семафора до его установки (положительное значение – это задержка в миллисекундах).

Для синхронизации процессов и обработки критических участков программ не­обходимы семафоры, к которым имеют доступ все работающие программы. Программа-потомок может унаследовать семафор от программы-предка, которая создала или открыла необходимый семафор. Но это произойдет только тогда, когда программа-предок дождётся момента открытия семафора в программе-по­томке. Это обеспечивается за счёт дополнительных семафоров ExitSem1, ExitSem2, ExitSem3. Когда последняя программа-потомок прочитывает данные из конвейера (работа с конвейером) и обнаруживает, что она последней прошла участок открытия уже созданных семафоров, она устанавливает необходимый семафор, принадлежащий программе-предку. Программа-предок, ожидающая установки семафора, завершает свою работу.

Для управления запуском и завершением программ также используются соответствующие функции.

DosExecPgm (FailFile, sizeof( FailFile), 1, Argument, 0, ResCode, " progr_b.exe" ) – функция запуска программы-потомка, где

¨ FailFile – буфер для помещения имени объекта, из-за которого возникла ошиб­ка запуска программы, sizeof( FailFile) – размер буфера;

¨ 1 означает, что процесс-потомок следует выполнять асинхронно с процессом-предком, Argument – строки аргументов программы, 0 – строки среды, ResCode – результирующие коды запуска программы, " progr_b.exe" – имя запускаемой (планируемой на выполнение) программы;

¨ DosExit – функция завершения процесса (и всех его подпроцессов);

¨ DosSetPriority – установка приоритета программы (и всех его подпроцессов).

Каждую программу в соответствии с заданием создаём как независимую, то есть имеющую своё локальное адресное пространство. Благодаря этому переменные в текстах программ, имеющие одинаковые имена (см. листинги в приложении Б), фактически являются разными переменными. Программа с именем А является начальной, стартовой. Именно она создаёт те системные объекты, которыми потом пользуются её потомки для своей синхро­низации. Имена системных объектов они получают в наследство при своём по­рождении.

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

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

Опишем теперь алгоритм обработки критических участков программ – записи в файл и работы с конвейером.

¨ Критический участок – работа с конвейером.

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

1: do { DosWaitEventSem (PipeSem, -1);

2: rc=DosResetEventSem (PipeSem, & NPost);

3: } while (rc! =0);

4: DosRead(ReadHandle, (PVOID)& OldInform, sizeof(Oldlnform),

BytesReaden);

5: DosPostEventSem(PipeSem);

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

В строке 1 программа ожидает установки семафора PipeSem; после того как этот семафор будет установлен, программа переходит к строке 2. Переменная rc возвращает код ошибки при попытке сбросить семафор в строке 2. Это сде­лано со следующей целью: если после завершения строки 1 будет выполнять­ся другая программа и она успеет сбросить семафор, то когда программа вновь продолжит своё выполнение, она обнаружит в строке 2, что семафор уже сброшен и rc не будет равно нулю; затем цикл повторится. Так будет про­должаться до тех пор, пока rc не станет равно нулю, то есть текущая програм­ма первой сбросила семафор. Тогда в строке 4 программа считывает из кон­вейера данные и сигнализирует об освобождении ресурса в строке 5.

Для записи в конвейер используется аналогичный алгоритм.

¨ Критический участок –запись в файл.

Здесь использован такой же алгоритм, как и при работе с конвейером, но задействован специально созданный для этого семафор FileSem. Теперь рассмотрим алгоритмы, решающие задачи синхронизации в каждой из точек нашей схемы (см. рис. 6.7). Начнем с прохождения точки 2. Приведём фрагмент исходного текста программы (см. приложение Б).

1: rc=DosPostEventSem(Point1Sem):

2: if (rc==0)

3: { DosWrite(WriteHandle, (PVOID)& NewInform, sizeof(NewInform), & BytesWr1tten);

4: DosCreateEventSem(" \\SEM32\\EXITSEM2", & ExitSem2, DC_SEM_SHARED, 0);

5: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, & ResCodeb, " progr_d.exe" );

6: DosExecPgm(FaiIFileb, sizeof(FailFileb), 1, Argument, 0, & ResCodeb, " progr_e.exe" );

7: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, & ResCodeb, " progr_f.exe" );

8: DosWaitEventSem(ExitSem2, -1);

9: DosCloseEventSem(ExitSem2); }

В точке 2 программы D, Е, и F должны быть запущены процессом, который пер­вым завершит свою работу. Для определения последовательности завершения работы программ (В или С) нами используется семафор Point1Sem. В строке 1 производится установка данного семафора. Если значение rc не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если rc равно нулю, то текущая программа закончила работу пер­вой и осуществляется переход к строке 3. В строке 3 осуществляется запись в конвейер. Строка 4 – создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание откры­тия семафоров происходит в строке 8, затем семафор закрывается. В строках 5–7 осуществляется запуск программ D, Е, F.

Теперь приведём алгоритм прохождения точки 3. Фрагмент исходного текста программы изображен ниже.

1: rc=DosPostEventSem(Point2Sem);

2: if (гс==0)

3: { do{ DosQueryEventSem(Point2Sem, & BytesWritten);

4: }while (BytesWritten< =2);

5: DosWrite(WriteHandle, (PVOID)& NewInform, sizeof(NewInform),

& BytesWritten);

6: DosCreateEventSem(" \\SEM32\\EXITSEM3", & ExitSem3,

DC_SEM_SHARED, 0);

7: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, & ResCodeb,

" progr_g.exe" );

8: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, & ResCodeb,

" progr_h.exe" );

9: DosWaitEventSem(ExitSem3, -1);

В точке 3 программы G и Н запускаются той программой, которая первой завер­шает свою работу, но только после того, как работу завершат остальные програм­мы. Для определения последовательности завершения работы программ (I, D или Е) используется семафор Point2Sem. В строке 1 производится установка данного семафора. Если значение rc не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если rc равно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В этой строке подсчитывается количество обращений к данному семафору. Цикл повторяется до тех пор, пока количество обращений не станет равно 3, то есть когда все остальные программы завершили свою работу. После этого в строке 5 осуществляется запись в конвейер. Строка 6 – создание семафо­ра ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 9. В строках 7 и 8 осуществляется запуск программ G и Н соответственно.

Наконец, приведём ещё алгоритм прохождения точки 4. Фрагмент исходного текста программы, реализующей эту задачу, приведён ниже.

1: do { DosWaitEventSem(Point1Sem, -1);

2: rc=DosResetEventSem(Point1Sem, & BytesReaden);

3: } while (rc! =0);

4: DosPostEventSem(Point3Sem);

5: DosQueryEventSem(Point3Sem, & BytesWritten);

6: DosPostEventSem(Point1Sem);

7: if (BytesWritten==4)

8: { DosWrite(WriteHandle, (PVOID)& NewInform, sizeof(NewInform),

& BytesWritten);

9: DosCreateEventSem(" \\SEM32\\EXITSEM4", & ExTtSem4,

DC_SEM_SHARED, 0);

10: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, & ResCodeb,

" progr_k.exe" ):

11: DosWaitEventSem(ExitSem4, -1);

Итак, в точке 4 программа К запускается задачей, которая последней завершила свою работу. Для определения последовательности завершения работы программ (J, G, Н или F) используется семафор Point3Sem. Каждая программа должна обра­титься к данному семафору, установить его и проверить количество обращений к нему. Но при выполнении этих двух операций другие программы могут также установить семафор, и значение обращений к семафору в текущей программе окажется неверным. Для доступа к семафору Point3Sem используется семафор Point1Sem. В строке 1 программа ожидает установки семафора Point1Sem, который сигнализирует о доступности неразделяемого ресурса Point3Sem. В строке 2 сема­фор сбрасывается, но если другие программы успели сбросить семафор, то об этом сообщит значение rc. Если текущей программе удалось завладеть ресурсом, то есть значение rc равно нулю, то дальше в строках 4, 5 производится установка семафора Point3Sem и подсчёт количества обращений. Строка 6 сигнализирует о завершении работы критической части программы установкой семафора Point1Sem. Затем, как и в предыдущих алгоритмах, программа записывает информацию в транспортёр (строка 8), создает семафор ожидания открытия семафоров в про­граммах-потомках (строка 9), запускает программу К (строка 10) и ожидает открытия семафоров в программе К (строка 11).

Тексты четырех программ (А, В, D и G), действующих по рассмотренным алго­ритмам, приведены в приложении Б. Остальные программы аналогичны им и отличаются только использованием других имён.

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

Вопросы для проверки

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

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

3 Объясните команду «проверка и установка».

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

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

6 Что такое мьютекс (mutex)?

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

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

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

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

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

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

 

⇐ Предыдущая31323334353637383940Следующая ⇒

Поделиться:

Популярное:

1. Выполнении параллельных вычислительных процессов
2. Кафедра электронных вычислительных машин
3. Лабораторная работа №5. Программирование циклических вычислительных процессов с использованием массивов и матриц
4. Нейросетевых вычислительных систем (слд 173)
5. ОПЕРАТОР ЭЛЕКТРОННО-ВЫЧИСЛИТЕЛЬНЫХ И ВЫЧИСЛИТЕЛЬНЫХ МАШИН
6. Тексты программы параллельных взаимодействующих задач
7. Тема. Программирование вычислительных процессов с ветвлением. Оператор CASE
8. Тема. Разработка блок-схем алгоритмов различных вычислительных процессов
9. Тема. Реализация разветвляющихся вычислительных процессов. Оператор IF
10. Фон Неймановская архитектура вычислительных систем.