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

Предоплата всего

Подписываем
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
«Примеры создания параллельных
взаимодействующих вычислительных
процессов с помощью системы программирования Borland Delphi»
Содержание
Введение
Рассмотрим учебный пример, в котором ставится задача создания комплекса параллельно выполняющихся взаимодействующих программ. Пример не будет иметь содержательного смысла в том плане, что никакой полезной работы программные модули, взаимодействующие между собой не выполняют. Они только синхронизируют друг друга по предопределенной схеме, демонстрируя главным образом способы организации взаимодействующих вычислений взаимное исключение при выполнении критических интервалов, обмены синхросигналами и данными.
Пусть в нашем примере каждая программа (при своем исполнении либо как самостоятельный вычислительный процесс, либо как задача) должна сообщить время начала своей работы, время окончания работы и, возможно, имена тех программ, которые она (при определенных условиях) должна будет запланировать на выполнение.
Для иллюстрации различий в организации взаимодействия полноценных вычислительных процессов и многозадачных (многопотоковых) приложений приведем два примера реализации, что позволит увидеть разные механизмы.
Начнем с более простого случая, когда создается обычное мультитредовое приложение, причем воспользуемся не средствами API, а методами, специально созданными для системы программирования. Второй пример будет иллюстрировать применение более мощных средств для организации взаимного исключения и обмена сообщениями; здесь будут использованы средства самой ОС.
Пример создания многозадачного приложения с помощью системы программирования Borland Delphi
Рассмотрим пример использования механизмов, специально созданных для организации взаимного исключения, которые имеются в системе программирования Borland Delphi 3.0. Эта система программирования, будучи ориентированной на создание приложений в многозадачной операционной системе Microsoft Windows 9x, содержит в себе стандартные классы, позволяющие без особых усилий использовать многопоточные возможности этих ОС. Воспользуемся стандартным классом TThread (thread нить это независимый поток управления, выполняемый в контексте некоторого процесса) Объект, создаваемый на основе этого класса, можно охарактеризовать следующими теперь уже очевидными для нас свойствами:
Итак, пусть необходимо создать многопоточное приложение, схема взаимодействия отдельных потоков в котором (в рамках единого вычислительного процесса) приведена на рис.1.
Так, согласно этому рисунку, процесс А после своего завершения запускает задачи D, С и Е. Считаем, что задачи В, D и С завершаются примерно в одинаково время. По крайней мере, нам не известно, какой из потоков должен быть первым, а какой последним. Однако по условиям задачи пусть поток F будет запускаться тем из перечисленных тредов, который завершается первым, но только после того, как завершатся два оставшихся треда, приходящие в «точку синхронизации». Наконец, пусть задача G запускается последним закончившим работу потоком Е или F.
Все указанные задачи создадим как потомки объекта TThread. Поскольку, согласно условию, действия, выполняемые задачами, для нас не имеют значения, представим исполняемую часть простейшим циклом с соответствующей задержкой. Для наглядности внутри цикла можно организовать вывод текущего состояния выполнения задачи в процентах на «строке состояния», для чего используем компонент TGauge. Благодаря тому, что все семь тредов похожи (используют одни и те же методы) и отличаются только в части принятия решения о синхронизации, опишем организацию базового объекта-треда.
Базовый объект (TTreadProgress) является потомком объекта TTread. При этом он имеет следующие поля:
В базовом объекте объявлены следующие процедуры:
Все треды (от А до G) являются потомками этого объекта и перекрывают единственный метод процедуру завершения процесса. В исполняемой части задачи после завершения цикла задержки, имитирующего выполнение полезной работы, устанавливается признак завершения и вызывается процедура завершения задачи, которая и выполняет соответствующие действия.
Общую схему работы программы, реализующей задание, можно описать следующим образом. Все задачи инициализируются соответствующей процедурой одновременно, но в режиме ожидания запуска. В качестве параметров инициализации в создаваемый поток передаются его имя, длительность и имя запускающего объекта (если оно известно заранее). Сразу после инициализации запускаются задачи А и В. Обе задачи сигнализируют об этом соответствующим сообщением. После своего завершения поток А запускает задачи (потоки) С, D и Е. Далее все идет в соответствии с заданной блок-схемой. Задача, запускающая другую задачу, передает ей свое имя, обращаясь непосредственно к полю этого объекта. Информацию о том, завершился тот или иной поток, можно получить, обратившись к соответствующему полю признаку завершения задачи.
Естественно, что при подобной организации доступа к полям тредов вероятно возникновение разного рода критических ситуаций. Напомним, основная причина их возникновения заключена в том, что несколько задач (в нашем случае потоков) реально имеют возможность обращения к общим ресурсам практически одновременно, то есть с таким интервалом времени, за который этот ресурс не успеет изменить свое состояние. В результате задачи могут получать некорректные значения, о чем мы уже немало говорили.
Каждый процесс имеет связь с так называемыми VCL-объектами видимыми компонентами. В данном случае такими являются строка состояния TGauge и поле сообщений TMemo. Для того чтобы в процессе работы нескольких параллельно выполняющихся задач не возникало критических ситуаций с выводом информации на эти видимые на экране объекты, к ним необходимо обеспечить синхронизированный доступ. Это довольно легко достигается с помощью стандартного для объекта TThread метода Synchronize. Метод имеет в качестве параметра имя процедуры, в которой производится вывод на VCL-объекты. При этом сама эта процедура нигде в программе не должна вызываться напрямую без использования метода Synchronize. В нашей программе такими процедурами является прорисовка строки состояния (Do Visual Progress) и вывод текстового сообщения (WriteToMemo). Подобное использование метода Synchronize обеспечивает корректную работу нескольких параллельных процессов с VCL-объектами.
Однако метод Synchronize не помогает в случае совместного доступа к другим общим ресурсам. Поэтому необходимо применять другие средства для организации взаимного исключения. Главная цель этих средств заключается в обеспечении монопольного доступа для каждой задачи к общим ресурсам, то есть пока один поток не закончил обращение к подобному ресурсу, другой не имеет право этот ресурс использовать.
В системе программирования Delphi для этой цели имеется довольно-таки простой в использовании достаточно эффективный метод критической секции с помощью объекта TCriticalSection. Этот метод заключается в следующем:
Очевидно, что такой метод надежно обеспечивает задачам монопольный доступ к общим (критическим) ресурсам.
Метод критической секции имеет ряд преимуществ перед его аналогами. Так, например, использование семафоров (Semaphore) сложнее в реализации. Другой метод взаимных исключений mutex в целом похож на метод критической секции, но он требует больше системных ресурсов и имеет свое время тайм-аута, по истечении которого ожидающий процесс может все-таки войти в защищенный блок, в то время как в критической секции подобного механизма нет.
Пример создания комплекса параллельных
взаимодействующих программ, выступающих
как самостоятельные вычислительные процессы
Теперь рассмотрим более сложную задачу: пусть параллельно выполняющиеся задачи имеют статус полноценного вычислительного процесса, а не потока и, кроме этого, организуем обращение к соответствующим системным механизмам непосредственно на уровне API. Схема взаимодействия программ для этого примера изображена на рис. 2.
На этом рисунке программа с именем А в точке 1 порождает сразу четыре параллельно выполняющихся задачи (вычислительных процесса): В, С, I и J. Процессы В и С завершаются и должны запустить, в свою очередь, два параллельных процесса D и Е. В точке 2, в которой происходит синхронизация задач В и С, процессы D и Е должны быть запущены той из задач В или С, которая закончит свое выполнение раньше, но только после момента окончания второй. Далее, в точке 3 необходимо запустить программы G и Н. Запускает их первая завершившая свою работу программа (D, Е или I), но дождавшись завершения остальных программ. Точка 4 синхронизирует выполнение процессов F, G, H и J, при этом программу К запускает последний из завершившихся процессов.
Для решения поставленной задачи будем использовать соответствующие механизмы, описанные нами выше (применительно к OS/2), а именно конвейер (pipe) и семафоры. В нашей задаче через конвейер передается переменная типа ParentInfo:
struct Parentlnfo
{ char ParentName [15];
char LaunchTime [12];
int Number;
}
Parentlnfo хранит имя программы-предка; LaunchTime содержит время запуска текущей программы программой-предком (время, когда программа-предок выполнила функцию DosExecPgm); переменная Number указывает, для какого числа программ предназначена переменная Parentlnfo.
Читать из конвейера мы можем при помощи функции 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") функция запуска программы-потомка, где
Каждую программу в соответствии с заданием создаем как независимую, то есть имеющую свое локальное адресное пространство. Благодаря этому переменные в текстах программ, имеющие одинаковые имена, фактически являются разными переменными.
Программа с именем А является начальной, стартовой. Именно она создает те системные объекты, которыми потом пользуются ее потомки для своей синхронизации. Имена системных объектов они получают в наследство при своем порождении.
Для совместного использования вычислительными процессами одного файла необходимо правильно его открыть в программе А. После корректного открытия или создания файла к нему могут обращаться все программы, имеющие идентификатор открытого файла. Значение этого идентификатора передается запускающимся процессам в строке аргументов, сопровождающих вызов. В соответствии с заданием каждая программа записывает в файл время своего запуска, имя процесса-предка и время завершения своей работы. Поскольку файл используется всеми программами и запись производится в строгой последовательности, часть программы, которая обеспечивает запись в файл, должна быть признана нами как критический участок программы (критический интервал). Алгоритм обработки этого участка описан ниже. Если не пытаться регулировать доступ процессов к файлу, может возникнуть беспорядочная запись в файл. При регулировании записи каждый процесс производит сразу все три записи в файл.
Опишем теперь алгоритм обработки критических участков программ записи в файл и работы с конвейером.
Критический участок работа с конвейером.
Приведем фрагмент программы, обеспечивающий чтение из конвейера.
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, который затем используют все программы для прохождения критической части программы, связанной с чтением и записью в конвейер (рис.3).
В строке 1 программа ожидает установки семафора PipeSem; после того как этот семафор будет установлен, программа переходит к строке 2. Переменная гс возвращает код ошибки при попытке сбросить семафор в строке 2. Это сделано со следующей целью: если после завершения строки 1 будет выполняться другая программа и она успеет сбросить семафор, то когда программа вновь продолжит свое выполнение, она обнаружит в строке 2, что семафор уже сброшен и гс не будет равно нулю; затем цикл повторится. Так будет продолжаться до тех пор, пока гс не станет равно нулю, то есть текущая программа первой сбросила семафор. Тогда в строке 4 программа считывает из конвейера данные и сигнализирует об освобождении ресурса в строке 5.
Для записи в конвейер используется аналогичный алгоритм (рис. 4).
Критический участок запись в файл.
Здесь использован такой же алгоритм, как и при работе с конвейером, но задействован специально созданный для этого семафор FileSem.
Теперь рассмотрим алгоритмы, решающие задачи синхронизации в каждой из точек нашей схемы (см. рис. 2). Начнем с прохождения точки 2. Приведем фрагмент исходного текста программы.
1: rc=DosPostEventSem(PointlSem);
2: if (re = = 0)
3: { DosWrite(WriteHandle.(PVOID)&NewInform,sizeof(NewInform),
&BytesWritten);
4: DosCreateEventSem("\\SEM32\\EXITSEM2", &ExitSem2,
DC_SEM_SHARED, 0);
5: DosExecPgm(FailFileb,sizeof(FailFileb),l. Argument,0, &ResCodeb,
"progr_d.exe");
6: DosExecPgm(FailFileb.sizeof(FailFileb),1. Argument,0, &ResCodeb,
"progr_e.exe");
7: DosExecPgm(FailFileb.sizeof(FailFileb),1.Argument,0, &ResCodeb,
"progr_f.exe");
8: DosWaitEventSem(ExitSem2,-l);
9: DosCloseEventSem(ExitSem2); }
В точке 2 программы D, E, и F должны быть запущены процессом, который первым завершит свою работу. Для определения последовательности завершения работы программ (В или С) нами используется семафор Point1Sem (рис. 5). В строке 1 производится установка данного семафора. Если значение гс не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если гс равно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В строке 3 осуществляется запись в конвейер. Строка 4 создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 8, затем семафор закрывается. В строках 57 осуществляется запуск программ D, E, 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),1,Argument,0, &ResCodeb, "progr_g.exe");
8: DosExecPgm(FailFileb, sizeof(FailFileb),1,Argument,0, &ResCodeb,"progr_h.exe");
9: DosWaitEventSem(ExitSem3, -l);
В точке 3 программы G и Н запускаются той программой, которая первой завершает свою работу, но только после того, как работу завершат остальные программы. Для определения последовательности завершения работы программ (I, D или Е) используется семафор Point2Sem (рис. 6). В строке 1 производится установка данного семафора. Если значение гс не равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Если гс равно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В этой строке подсчитывается количество обращений к данному семафору. Цикл повторяется до тех пор, пока количество обращений не станет равно 3, то есть когда все остальные программы завершили свою работу. После этого в строке 5 осуществляется запись в конвейер. Строка 6 создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 9. В строках 7 и 8 осуществляется запуск программ G и Н соответственно.
Наконец, приведем еще алгоритм прохождения точки 4 (рис. 7). Фрагмент исходного текста программы, реализующей эту задачу, приведен ниже.
1: do { DosWaitEventSem(Point1Sem, -l);
2: rc=DosResetEventSem(Point1Sem, &BytesReaden);
3: } while (rc!=0);
4: DosPostEventSem(Point3Sem);
5: DosQueryEventSem(Point3Sem, &BytesWritten);
6: DosPostEventSem(PointlSem);
7: if (BytesWritten = = 4)
8: { DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform),&BytesWritten);
9: DosCreateEventSem("\\SEM32\\EXITSEM4", &ExitSem4, DC_SEM_SHARED, 0);
10: DosExecPgm(FaiIFileb, sizeof(FaiIFileb),1, Argument,0, &ResCodeb, "progr_k.exe");
11: DosWaitEventSem(ExitSem4,-1);
Итак, в точке 4 программа К запускается задачей, которая последней завершила свою работу. Для определения последовательности завершения работы программ (J, G, Н или F) используется семафор Point3Sem. Каждая программа должна обратиться к данному семафору, установить его и проверить количество обращений к нему. Но при выполнении этих двух операций другие программы могут также установить семафор, и значение обращений к семафору в текущей программе окажется неверным. Для доступа к семафору Point3Sem используется семафор Point1Sem. В строке 1 программа ожидает установки семафора Point1Sem, который сигнализирует о доступности неразделяемого ресурса Point3Sem. В строке 2 семафор сбрасывается, но если другие программы успели сбросить семафор, то об этом сообщит значение гс. Если текущей программе удалось завладеть ресурсом, то есть значение гс равно нулю, то дальше в строках 4, 5 производится установка семафора Point3Sem и подсчет количества обращений. Строка 6 сигнализирует о завершении работы критической части программы установкой семафора Point1Sem. Затем, как и в предыдущих алгоритмах, программа записывает информацию в транспортер (строка 8), создает семафор ожидания открытия семафоров в программах-потомках (строка 9), запускает программу К (строка 10) и ожидает открытия семафоров в программе К (строка 11).
Использование семафоров в Unix для синхронизации процессов
Выше были представлены примеры создания параллельных процессов на уровне исходных кодов и блок-схем. Теперь же вкратце ознакомимся с некоторыми основными функциями ОС UNIX, использующими семафоры для управления и синхронизации процессов.
Механизм семафоров, реализованный в ОС UNIX, является обобщением классического механизма семафоров общего вид, предложенного более 25 лет тому назад профессором Дейкстрой.
Семафор в ОС UNIX состоит из следующих элементов:
Для работы с семафорами поддерживаются три системных вызова:
Основным системным вызовом для манипулирования семафором является semop: oldval=semop(id, oplist, count);
где id это где-то ранее полученный дескриптор группы семафоров (через вызов semget), oplist массив описателей операций над семафорами группы, а count размер этого массива.
Значение, возвращаемое этим системным вызовом, является значением последнего обработанного семафора. Каждый элемент массива oplist имеет следующую структуру:
Если проверка прав доступа проходит нормально, и указанные в массиве oplist номера семафоров не выходят за пределы общего размера набора семафоров, то системный вызов выполняется следующим образом. Для каждого элемента массива oplist значение соответствующего семафора изменяется в соответствии со значением поля «операция».
значение семафора увеличивается на единицу, а все процессы, ожидающие увеличения значения семафора, активизируются.
если значение семафора также равно нулю, выбирается следующий элемент массива oplist. Если же значение семафора отлично от нуля, то ядро увеличивает на единицу число процессов, ожидающих нулевого значения семафора, а обратившийся процесс переводится в состояние ожидания.
ядро прибавляет это отрицательное значение к значению семафора. Если в результате значение семафора стало нулевым, то ядро активизирует все процессы, ожидающие нулевого значения этого семафора. Если же значение этого семафора меньше абсолютной величины поля операции, то ядро увеличивает на единицу число процессов, ожидающих увеличение значения семафора и откладывает («усыпляет») текущий процесс до наступления этого события.
Основным поводом для введения массовых операций над семафорами было стремление дать программистам возможность избегать тупиковых ситуаций в связи с семафорной синхронизацией. Это обеспечивается тем, что системный вызов semop, каким бы длинным он ни был (по причине потенциально неограниченной длины массива oplist) выполняется как атомарная операция, то есть во время выполнения semop ни один другой процесс не может изменить значение какого-либо семафора.
Среди флагов-параметров системного вызова semop может содержаться флаг с именем IPC_NOWAIT, наличие которого заставляет ядро ОС UNIX не блокировать текущий процесс, а лишь сообщать в ответных параметрах о возникновении ситуации, приведшей бы к блокированию процесса при отсутствии флага IPC_NOWAIT.
Список литературы
A
B
C
D
E
F
G
Точка 1
очка 2
Точка 2
Точка 1
Точка 4
Точка 3
Рис.2. Схема № 2 взаимодействия параллельно выполняющихся вычислительных процессов
Рис. 1. Схема № 1 взаимодействия параллельно выполняющихся задач
A
B
C
D
E
G
H
I
J
F
Рис. 3 . Блок-схема «Чтение из конвейера»
Нет
Да
Конец
Освобождение ресурса - конвейера
Чтение данных из конвейера
Была ли попытка сбросить семафор?
Начало
Ожидание установки PipeSem
Рис. 4 . Блок-схема «Запись в конвейер»
Нет
Конец
Освобождение ресурса - конвейера
Запись данных в конвейер
Была ли попытка сбросить семафор?
Начало
Ожидание установки PipeSem
Рис. 5 . Блок-схема «Синхронизация процессов в точке 2»
Удачно.
Неудачно. Семафор уже установлен другой программой.
Конец
Создание «семафора ожидания» ExitSem2
Запись в конвейер
Установка семафора «определения последовательности завершения работы программ B и С»
Начало
Запуск программ D, E, F
Ожидание открытых семафоров
Закрытие «семафора ожидания»
Все программы завершили свою работу?
Ожидание открытых семафоров
Запуск программ G и H
Неудачно. Семафор уже установлен другой программой.
Рис. 6 . Блок-схема «Прохождение точки 3»
Удачно.
Конец
Создание «семафора ожидания» ExitSem3
Запись в конвейер
Установка семафора Point2Sem
Начало
Да
Нет
Запуск программы К
Создание «семафора ожидания»
Ожидание открытия семафоров в программе-потомке K
Запись в конвейер
Завершение работы критической части программы (установка Point1Sem)
Нет. Неразделяемый ресурс Point3Sem недоступен.
Рис. 7 . Блок-схема «Прохождение точки 4»
Да. Программа завладела ресурсом.
Конец
Подсчет числа обращений к ресурсу
Установка семафора Point3Sem
Семафора Point1Sem установлен?
Начало
K