Одна из основных целей в параллельном программировании — разбить всю работу, предусмотренную для выполнения программой, на множество задач, которые могут при необходимости выполняться с определенной степенью параллелизма. Эта цель труднодостижима. Довольно сложно так провести декомпозицию работ (Work Breakdown Structure— WBS), чтобы создать соответствующий фундамент для параллелизма и обеспечить корректные и эффективные результаты работы. Для достижения этой цели мы используем методы моделирования и специальные архитектурные решения. На практике на этапе моделирования самой задачи и ее решения стараются выявить естественный параллелизм. Не следует в решение вносить параллелизм искусственно. Если задача и ее решение смоделированы надлежащим образом, то необходимый параллелизм обнаружится сам собой. Архитектура «классной доски» облегчает такой процесс моделирования. В частности, модель «классной доски» позволяет организовать и концептуализировать параллельность и взаимодействие компонентов в системе, которая требует применения параллельного или распределенного программирования.
Модель «классной доски»
Модель «классной доски» — это технология совместного решения задач. «Классная доска» используется для регистрации и координации действий, а также организации взаимодействия между двумя или больше программными решателями задач. Таким образом, в модели «классной доски» существует два основных типа компонентов: «классная доска» и решатели задач.
«Классная доска» представл я ет собой централизованный объект, к которому имеет доступ каждый из решателей задач. Решатели задач могут считывать содержимое «классной доски» и изменять его. Содержимое «классной доски» в различные моменты времени различно. Исходное содержимое «классной доски» включает задачу, которую необходимо решить, а также информацию, представляющую начальное состояние задачи, ее ограничения, цели и требования. По мере того как решатели задач продвигаются к получению решения, на «классной доске» фиксируются промежуточные результаты, гипотезы и выводы. Промежуточные результаты, записанные одним решателем задач, могут действовать как катализатор для других решателей задач, считывающих содержимое «классной доски». На «классную доску» записываются предварительные решения. Решения, признанные неудовлетворительными, «стираются», и процесс поиска новых решений продолжается. В отличие от сеансов непосредственной связи, решатели задач используют «классную доску» не только для передачи частичных результатов, но и поиска друг друга. В некоторых конфигурациях «классная доска» действует как рефери, информируя решателей задач о факте достижения решения или выдавал сигнал начать либо завершить работу. «Классная доска»— это активный объект, а не просто область памяти. В некоторых случаях «классная доска» определяет, каких решателей задач нужно привлечь и какое ее содержимое следует принять или отвергнуть. «Классная доска» может преобразовывать или интерпретировать результаты, полученные от решателей задач одной группы, чтобы ими могли воспользоваться решатели задач другой группы.
Решатель задач — это про г раммное средство, которое обычно обладает специальными знаниями или возможностями обработки получаемой информации в пределах некоторой предметной области. Решатель задач может быть довольно простой функцией, которая, например, переводит значение температуры по Цельсию в значение по Фаренгейту, или достаточно сложным интеллектуальным агентом, который обрабатывает медицинские диагнозы. В модели «классной доски» эти решатели задач называются источниками знаний. Чтобы решить задачу с использованием «классной доски», необходимо наличие двух или больше источников знаний, которые обычно обладают различной специализацией. Модель «классной доски» более подходит для задач, разделяемых на отдельные подзадачи, которые можно решать независимо (или почти независимо) от других. В базовой конфигурации архитектуры «классной доски» каждый решатель занимается «своей» частью задачи, т.е. он «видит» только часть общей задачи, с которой работает. Если решение одной части задачи зависит от решения другой ее части, то «классная доска» используется для координации действий решателей задач и объединения частных решений. Решатели задач, задействованные в архитектуре «классной доски», не должны быть одинаковыми. Каждый из них может быть реализован по своему. Например, одни решатели задач могут быть реализованы с использованием объектно-ориентированных технологий, а другие — как функции. Более того, решатели задач могут использовать совершенно различные парадигмы решения. Например, решатель А для решения своей подзадачи может применять метод обратного построения цепочки (т.е. ведения рассуждений от целевой гипотезы к исходным посылкам), а решатель В — метод от противного. При этом также необязательно, чтобы решатели задач были реализованы с помощью одного и того же языка программирования.
Модель «классной доски» не определяет никакой конкретной структуры ни для самой «классной доски», ни для источников знаний. Как правило, структура «классной доски» зависит от конкретной задачи.1 Реализация источников знаний также зависит от специфики решаемой задачи. «Классная доска» — это концептуальная модель, описывающая отношения без представления структуры самой «классной доски» и источников знаний. Модель «классной доски» не диктует количество используемых источников знаний или их назначение. «Классная доска» может быть единственным глобальным или распределенным объектом, компоненты которого расположены на нескольких компьютерах. Системы «классной доски» могут состоять из нескольких «классных досок», и каждая из них «занимается» решением определенной части исходной задачи. Это делает модель «классной доски» чрезвычайно гибкой. Модель «классной доски» поддерживает параллельное и распределенное программирование. Во-первых, источники знаний, работая над решением части общей задачи, могут выполняться одновременно. Во-вторых, источники знаний могут быть реализованы в различных потоках или отдельных процессах одного или нескольких компьютеров.
«Классная доска» может быть разделена на несколько отдельных частей, позволяющих параллельный доступ со стороны нескольких источников знаний. «Классная доска» легко поддерживает такие архитектурные варианты, как CREW (concurrent read, exclusive write — параллельное чтение и монопольнал запись), EREW (exclusive read, exclusive write — монопольное чтение и монопольная запись) и MIMD (multiple-instruction, multiple-data — множество потоков данных и множество потоков команд). Мы реализуем «классную доску» как глобальный объект или коллекцию объектов, а источники знаний — как отдельные потоки. Поскольку потоки разделяют одно и то же адресное пространство, к «классной доске», реализованной как глобальный объект или семейство объектов, будут получать доступ все потоковые источники знаний. Если источники знаний реализовать как отдельные процессы, выполняющиеся на одном или нескольких компьютерах, то «классную доску» имеет смысл реализовать как CORBA-объект или как коллекцию CORBA-объектов. Вспомните, что CORBA-объекты можно использовать для поддержки как параллельной, так и распределенной модели вычислений. Здесь мы используем технологию CORBA для поддержки «классной доски» как разновидность распределенной памяти, совместно используемой задачами, выполняющимися в различных адресных пространствах. Эти задачи могут быть PVM-типа (Рагаllеl Virtual Machine — параллельная виртуальная машина), задачами, порождаемыми традиционными fork-exec-вызовами функций, или задачами, порождаемыми библиотечными функциями posix_spawn (). Две конфигурации памяти для реализации технологии «классной доски» показаны на рис. 13.1.
В обоих случаях (см. рис. 13.1) все источники знаний имеют доступ к «классной доске». Источники знаний, размещенные в различных адресных пространствах, должны иметь сетевую связь с «классной доской», реализованной как один или несколько CORBA-объектов. Если источники зна н ий реализова н ы как PVM-задачи. то их связь с «классной доской» можно построить на основе передачи сооб щ ений. Такая конфигурация обеспечивает чрезвычайно гибкую модель решения задач.
| #img_84.png Рис.13.1. Две конфигурации памяти для реализации технологии «классной доски» (ИЗ — источник знаний) |
Методы структурирования «классной доски»
Методов структурирования «классной доски» не существует. Однако большинство реализаций этой технологии имеют определенные характеристики и атрибуты. Исходное содержимое «классной доски» обычно включает часть пространства решения задачи. Пространство решений должно содержать все частные и полное решения задачи. Например, предположим, что у нас есть механизм поиска изображений автомобилей в Internet. Этот механизм поиска может обрабатывать растровое или векторное изображение, чтобы определить, содержит ли оно изображение автомобиля, и если содержит, то отвечает ли оно параметрам поиска. Допустим, этот механизм поиска разработан с использованием модели «классной доски». Каждый источник знаний имеет свою специфику: один — специалист в области идентификации изображений покрышек, другой — идентифицирует зеркала задней обзорности, третий — эксперт по дверным ручкам для автомобилей и т.д. Каждая деталь автомобиля представляет малую часть пространства решений. Одни части пространства решений содержат полное изображение автомобиля с различных точек зрения (т.е. сверху, снизу, под углом 45° и т.д.), а другие — только отдельные детали автомобилей, например, фронтальную и заднюю части, крышу или багажник. На «классной доске» размещается растровое или векторное изображение, и отдельные источники знаний пытаются идентифицировать детали изображения, которые могут быть частями автомобиля. Если некоторая часть пространства решений совпадает с какой-нибудь частью изображения, эта часть изображения будет записана в другую часть «классной доски» как частное решение. Один источник знаний может поместить на «классную доску» дверную ручку идентифицируемого автомобиля, другой — дверцу. Если эти две части информации оказались на «классной доске», то какой-нибудь третий источник знаний может использовать эту информацию как вспомогательную при идентификации передней части автомобиля в исследуемом изображении. После того как будет идентифицирована передняя часть, она также размещается на «классной доске». Каждый из этих различных способов идентификации изображения автомобиля представляет часть пространства решений.
Пространство решений иногда организуется иерархически. В нашем примере с автомобилем на вершине иерархии могут находиться полные изображения автомобиля, следующий уровень может состоять из различных видов передних и задних частей, еще один уровень может содержать двери, багажники, капоты, ветровые стекла и колеса. Каждый уровень описывает в этом случае меньшее, возможно, менее характерное изображение некоторой части автомобиля. Источники знаний могут работать одновременно на нескольких уровнях иерархии. Пространство решений также можно организовать в виде графа, в котором каждый узел представляет некоторую часть решения, а каждое ребро — отношения между двумя частными решениями. Пространство решений может быть представлено в виде одной или нескольких матриц, а каждый элемент матрицы будет содержать в этом случае полное или частное решение. Представление пространства решений— это важный компонент архитектуры «классной доски». Именно характер задачи часто определяет, как должно быть распределено пространство решений. Помимо компонента пространства решений, «классная доска» обычно имеет один или несколько компонентов (эвристических) правил. Компонент правил используется для определения того, какие источники знаний стоит использовать и какие решения принимать или отвергать. Компонент правил можно также применить для перевода частных решений с одного уровня иерархии пространства решений на другой. Компонент правил позволяет назначать приоритеты источникам знаний. Некоторые источники знаний могут «зайти в тупик». «Классная доска» может «снять отметку» с одной группы источников знаний в пользу другой, а также использовать компонент правил, чтобы предложить источникам знаний более потенциально подходящие гипотезы на основе уже сгенерированных частных гипотез. Помимо пространства решений и компонента правил, «классная доска» часто содержит начальные значения, значения ограничений и вспомогательные цели. В некоторых случаях «классная доска» может содержать одну или несколько очередей событий, используемых для приема входных данных либо из пространства задачи, либо от источников знаний. Логическая схема базовой архитектуры «классной доски» показана на рис. 13.2.
| #img_85.png Рис. 13.2. Логическая схема базовой архитектуры «классной доски» |
«Классная доска» (см. рис. 13.2) имеет ряд сегментов, а каждый сегмент — различные реализации. Это говорит о том, что «классная доска» — это нечто большее, чем просто область глобальной памяти или традиционные базы данных. Хотя на рис. 13.2 показаны только основные компоненты, которые имеют многие «классные доски», этот вид архитектуры не ограничивается таким составом. К числу дополнительных компонентов потенциально можно отнести модели контекстов задачи и модели предметной области, которые могут оказаться полезными для решателей задач при навигации по пространству решений. С++-поддержка объектно-ориентированного проектирования и программирования прекрасно сочетается с требованиями гибкости, которые обычно предъявляются к модели «классной доски». Большинство архитектур «классной доски» может быть смоделировано с использованием С++-классов. Вспомните, что классы можно использовать для моделирования человека, местности, предмета или идеи, а»классные доски» используются для решения задач, в которых часто участвуют люди, местности, предметы или идеи. Поэтому весьма уместно применять С++-классы для моделирования объектов, которые содержит «классная доска». В своих реализациях модели «классной доски» мы используем преимущества контейнерных С++-классов и стандартных алгоритмов. Помимо встроенных классов, мы создаем интерфейсные классы для мьютексов и других переменных синхронизации, используемых в реализации «классной доски». Поскольку к «классной доске» могут получить доступ сразу несколько источников знаний одновре м енно, это означает, что она является критически м раздело м, доступ к которо м у нуждается в синхронизации. Поэто м у в м есте с дру г и м и ко м понента м и «классной доски» м ы буде м испо л ьзовать здесь и объекты синхронизации.
Анатомия источника знаний
Источники знаний представляются как объекты, процедуры, множества правил, логические утверждения, а в некоторых случалх и целые программы. Источники знаний включают часть условий и часть действий. Если «классная доска» содержит информацию, которая удовлетворяет части условий некоторого источника знаний, то его часть действий активизируется. Инглемор (Englemore) и Морган (Morgan) в своей работе [14] четко описывают обязанности источника знаний.
Каждый источник знаний отвечает за знание условий, при которых он может внести свой вклад в решение. Каждый источник знаний имеет предусловия, т.е. условия, которые должны быть записаны на «классной доске» и существовать до того, как будет активизировано тело источника знаний. Источник знаний можно рассматривать как большое правило. Главное, чем отличается правило от источника знаний, состоит в степени детализации знаний. Часть условий этого большого правила называется предусловием источника знаний, а часть действий — его телом.
Здесь Инглемор и Морган не определяют ни единой детали части условий или части действий источника знаний. Они представляют собой логические конструкции. Часть условий может иметь форму простого значения булевого флага на «классной доске» или сложной последовательности событий, поступающих в очередь событий в пределах определенного периода времени. Аналогично часть действий источника знаний может быть выражена простой инструкцией, выполняющей операцию присваивания переменной некоторого выражения, или механизмом прямого построения цепочки в экспертной системе. Это описание широты диапазона еще раз подчеркивает гибкость модели «классной доски». Для наших целей вполне достаточно конструкции С++-класса и понятия объекта. Каждый источник знаний должен быть объектом. Часть действий источника знаний должна быть реализована в виде методов объекта, а часть условий — в виде его членов данных. Если объект находится в определенном состоянии, то его часть действий должна быть активизирована. Проще говоря, мы реализуем источники знаний в виде потоков или процессов. Следовательно, для каждого потока и для каждого процесса должен существовать только один источник знаний. Применяя к «классной доске» PVM-механизм, источник знаний будет эквивалентом PVM-задачи. Логическая схема источника знаний показана на рис. 13.3.
Часть «Условия» каждого источника знаний обновляется «из закромов» «классной доски», а часть «Действия» источников знаний обновляет ее содержимое. Обратите внимание на то (см. рис. 13.3), что между пространством процесса и источником знаний (или между пространством потока и источником знаний) существует взаимно однозначное отношение. Важным атрибутом источника знаний является его автономность. Каждый источник знаний является специалистом в своей области и почти не зависит от других решателей задач. Это составляет одно из требуемых качеств для параллельной программы. В идеале задачи в параллельной программе могут выполняться одновременно, почти не нуждаясь во взаимодействии с другими задачами. Такое поведение в точности описывает схему модели «классной доски». Источники знаний действуют независимо, и любое взаимодействие осуществляется посредством «классной доски». Поэтому источник знаний (с его точки зрения) действует в одиночку, получал дополнительную информацию от «классной доски» и записывал на «классную доску» свои изыскания. О деятельности других источников знаний и их стратегиях поведения ему ничего не известно. В модели «классной доски» задача делится на ряд автономных или полуавтономных решателей задач. В этом и состоит преимущество модели «классной доски» перед другими моделями. В самой гибкой конфигурации источники знаний должны быть интеллектуальными агентами. Агент должен быть совершенно самодостаточным и способным действовать самостоятельно при минимальной потребности к взаимодействию с «классной доской». Именно интеллектуальный агент представляет самую грандиозную перспективу для реализации крупномасштабного параллелизма.
| #img_86.png Рис. 13.3. Логическая схема источника знаний |
Стратегии управления для «классной доски»
В реализации модели «классной доски» прелусмотрено несколько уровней управления, обеспечивающих возможность параллельного функционирования источников знаний. На самом нижнем уровне их схемы синхронизации должны защищать целостность «классной доски». «Классная доска» является критическим разделом, поскольку она представляет собой совместно используемый модифицируемый ресурс. В параллельной среде доступ со стороны источников знаний для чтения и записи должен быть скоординирован и синхронизирован. Координация и синхронизация может включать блокировку файлов, семафоры, мьютексы и т.д. Этот уровень управления не включается непосредственно в решение, над которым работают источники знаний. Его можно назвать вспомогательным уровнем управления, и он не должен зависеть от специфики задачи, решаемой с помощью «классной доски». В нашем архитектурном подходе этот уровень управления реализуется интерфейсными классами (например, классами мьютекса и семафора, использованными в главе 11). Вспомните, что действия, инкапсулированные в этих классах, не зависят от приложения, в котором они используются. Для параллельных реализаций «классной доски» на этом уровне выбирается один (или больше) из четырех типов параллельного доступа, которыми должны обладать алгоритмы или эвристические правила источников знаний для физической реализации «классной доски». Другими словами, пользователи «классной доски» могут использовать EREW-, CREW-, ERCW- или CRCW-доступ. Именно характер доступа определяет, как будут использованы примитивы синхронизации. Описание упомянутых здесь типов доступа приведено в табл. 13.1.
Таблица 13.1. Четыре типа параллельного доступа, используемых в модели «классной доски»
EREW Exclusive Read Exclusive Write (монопольное чтение и монопольная запись)
CREW Concurrent Read Exclusive Write (параллельное чтение и монопольная запись)
ERCW Exclusive Read Concurrent Write (монопольное чтение и параллельная запись)
CRCW Concurrent Read Concurrent Write (параллельное чтение и параллельная запись)
При разделении «классной доски» на части будет определено, какие из типов параллельности (см. табл. 13.1) подходят больше всего. Самый гибкий тип (CRCW) доступа может быть достигнут в зависимости от структуры «классной доски». Например, если используется 16 источников знаний, и каждый из них получает доступ к собственному сегменту «классной доски», то такие источники знаний могут параллельно считывать данные с «классной доски» и записывать их туда, не испытывал проблем «гонки» данных.
Следующий уровень управления включает выбор источников знаний. При этом определяется, какие из них следует включить в поиск решения и какие аспекты задачи им поручить. На этом уровне управления принимается решение перенести центр (фокус) внимания на ту или иную область задачи, что и определяет выбор соответствующих источников знаний. При решении задач любого типа всегда ставятся сле-лующие вопросы: «с чего начать?» и «что нужно для этого знать?». Уровень центра внимания отвечает за начальные условия задачи, а также определяет, какие источники знаний необходимо использовать и в какой момент они должны «вступить в игру». «Классной доске» должно быть известно, какими источниками знаний она может располагать, и обычно источники знаний принимают сообщения или параметры, которые предписывают, как им действовать или в какой области пространства решений следует начинать поиск. Для параллельных реализаций этот уровень управления определяет базовую модель параллелизма (распределение решателей задачи). Обычно для «классной доски» используется модель MPMD (Multiple Programs Multiple Data — множество программ и множество потоков данных), известнал также как MIMD (multiple-instruction, multiple-data — множество потоков команд и множество потоков данных), поскольку каждый источник знаний (решатель задачи) имеет собственную область специализации. Однако сама природа задачи иногда может дать право на использование такой популярной модели, как SPMD (Single Program Multiple Data —одна програ мм а, неско л ько потоков дан н ых). В это м с л учае урове н ь управ л е н ия породит N одинаковых источников знаний, но передаст им различные параметры.
На слелующем уровне управления определяется, что делать с решением или частными решениями, записанными на «классной доске». Этот уровень управления должен оценить, могут ли источники знаний остановить работу, и является ли сгенерированное решение приемлемым, неприемлемым, частично приемлемым и т.д. Именно этим уровнем управления завершается видимость «классной доски» и всех частных или предварительных решений. Именно здесь осуществляется руководство общими стратегиями решения задач коллективными усилиями. В соответствии со структурой «классной доски» и источников знаний модель «классной доски» предполагает существование компонента управления, но не определяет, как он должен быть структурирован. Иногда компонент управления является частью «классной доски», а иногда он реализуется источниками знаний. В некоторых случаях компонент управления реализуется модулями, которые являются внешними по отношению к «классной доске». Компонент управления также может быть реализован любым сочетанием предыдущих вариантов. Источники знаний совместно ищут решение задачи. Следует отметить, что некоторые задачи имеют несколько решений. Одни из них могут находиться глубже в пространстве поиска, чем другие; поиск одних решений может быть более затратным по сравнению с поиском других, а некоторые решения могут быть недостаточно хорошо продуманы. Компонент управления не только руководит коллективными стратегиями поиска, выполняемого источниками знаний, но и контролирует частные или предварительные решения, чтобы убедиться, что источники знаний не реализуют какую-нибудь непрактичную стратегию поиска. Компонент управления выявляет бесконечные циклы, тупики или рекурсивные регрессии. Более того, компонент управления включается в выбор наилучших или наиболее подходящих источников знаний для данной задачи. По мере продвижения источников знаний к искомому решению компонент управления может разгрузить одни источники знаний за счет других. Стратегия управления должна быть тесно связана с со стратегиями поиска, которыми руководствуются источники знаний. Важно помнить, что все источники знаний могут использовать различные стратегии поиска и методы решения задачи. И хотя они работают с общей «классной доской», источники знаний по своей сути автономны и самодостаточны. Следовательно, этот уровень управления имеет двустороннее взаимодействие с источниками знаний. Возможные конфигурации управления и их уровни в архитектуре «классной доски» показаны на рис. 13.4.
Обратите внимание на то, что в первой из представленных конфигураций (см. рис. 13.4) механизм управления содержится в самой «классной доске», а не в отдельном модуле и не в источниках знаний. В этой конфигурации блок управления проектируется как часть класса «классной доски». Поскольку на уровнях 2 и 3 необходимо двустороннее взаимодействие, имеет смысл, чтобы «классная доска» порождала процессы или потоки, которые будут содержать источники знаний. Если «классная доска» порождает процессы или потоки, ей нетрудно получить доступ к идентификационному номеру любого потока или процесса. Это позволяет «классной доске» легко передавать сообщения источникам знаний и осуществлять управление процессами и потоками. Если «классной доске» по некоторой причине нужно прекратить деятельность конкретного источника знаний, то доступ к идентификатору потока или процесса делает эту задачу очень простой. Обратите внимание на то, что в одном из представленных на рис. 13.4 вариантов блок управления яв л яется внешни м по отношению к «к л ассной доске» и источника м зна н ий. В это м случае иде н тификационный но м ер потока и л и процесса должен быть явным образом связан с модулями управления.
| #img_87.png Рис. 13.4. Конфигурации управления и их уровни в архитектуре «классной доски» |
Реализация модели «классной доски» с помощью CORBA-объектов
Вспомните, что CORBA-объект (см. главу 8) является независимым от платформы распределенным объектом. К CORBA -объектам могут получать доступ процессы, выполняющиеся на одном или на разных компьютерах, подключенных к сети. Это делает CORBA-объекты кандидатами для использования в PVM-средах, когда программа делится на ряд процессов, которые могут (или не могут) выполняться на одном и том же компьютере. Обычно PVM-среда используется для передачи сообщений при вторичной роли общей памяти (если она вообще существует). Введение понятия разделяемого и доступного по сети объекта существенно усиливает вычислительные мощности PVM-среды. Следует иметь в виду, что с помощью CORBA-объектов можно смоделировать все, что позволяют смоделировать не распределенные объекты. Это означает, что PVM-задачи, которые имеют совместный доступ к CORBA-объектам, могут получать доступ к контейнерным объектам, объектам оболочки, шаблонов, доменов и другим видам вспомогательных объектов. В данном случае мы хотели бы, чтобы PVM-задачи имели доступ к объектам «классной доски». Поэтому модель передачи сообщений мы дополняем совместным доступом к сложным объектам. Помимо PVM-задач, получающих доступ к распределенным CORBA-объектам, к ним также могут обращаться задачи, порожденные функциями posix_spawn() или fork-exec. Эти задачи выполняются в отдельных адресных пространствах одного и того же компьютера, но могут, тем не менее, связываться с CORBA-объектами, которые расположены либо на том же, либо на другом компьютере. Поэтому, несмотря на то что все задачи, созданные с помощью функций posix_spawn () или fork-exec, должны размещаться на одном компьютере, CORBA-объекты могут располагаться на любом компьютере.
Пример использования CORBA-объекта «классной доски»
Чтобы продемонстрировать наше представление о CORBA-ориентированной «классной доске», рассмотрим ее реализацию, предложенную разработчиками из компании Ctest Laboratories. И хотя полное описание этого варианта выходит за рамки нашей книги, мы все же остановимся на самых важных аспектах «классной доски» и источников знаний, имеющих отношение к нашему архитектурному подхолу к параллельному программированию. «Классная доска» реализует услуги программно-ориентированного консультанта по составлению расписания учебных курсов. «Классная доска» решает задачи планирования учебных курсов для студента типичного колледжа. Студенты часто сталкиваются с проблемой «неудобного» расписания занятий. Во время регистрации курсов всегда существует конкуренция за места в аудиториях. В какой-то момент важные для студента курсы попросту «закрываются». Ведь не зря существует печально известное правило, соответствующее дисциплине обслуживания очереди: «первым пришел — первым обслужен». Поэтому во время регистрации, когда десятки тысяч студентов пытаются записаться на ограниченное количество курсов, важным фактором выступает своевременность. Студент желает пройти курсы, которые дают право на получение диплома. В идеале эти курсы должны быть разнесены во времени. Кроме того, студент хотел бы поддерживать определенную учебную нагрузку и иметь свободное время для домашних и факультативных занятий.
Проблема состоит в том, что, когда студент готов взять выбранный им курс, прием на него может уже оказаться закрытым, и вместо него ему предлагаются другие курсы, которые его интересуют в меньшей степени. Курсы-заменители увеличивают стоимость и продолжительность обучения студента в колледже, что с точки зрения студента является негативным фактором. Но если курсы-заменители отвечают «посторонним» интересам студента (имеются в виду хобби или перспективные цели), то такие курсы-заменители могут оказаться допустимыми. Кроме того, существует ряд факультативных кусов, которые могут также давать право для «выхода на диплом». Студент хотел бы получить оптимальный набор курсов, который бы позволил ему в запланированные сроки (или досрочно) претендовать на диплом, оставаясь при этом в рамках намеченного бюджета с максимальной гибкостью участвуя в учебном процессе. Для решения этой задачи студент использует работающую в реальном масштабе времени программу составления расписания учебных курсов, основанную на технологии «классной доски».
Важно отметить, что «классная доска» имеет доступ реального времени к академической характеристике студента и текущим курсам (с открытым или закрытым приемом) в любой момент периода регистрации. Кроме того, «классная доска» имеет доступ к дипломному плану студента, академическим требованиям для реализации этого плана, расписанию «готовности» студента посещать занятия, данным о его целях и предпочтениях и т.д. Все эти элементы моделируются с помощью С++- и CORBA-классов и образуют компоненты «классной доски». Для упрощения нашего примера мы рассмотрим только следующие четыре источника знаний:
• консультант по общеобразовательным курсам;
• консультант по основным курсам;
• консультант по факультативным курсам;
• консультант по непрофилирующим курсам.
Итак, рассмотрим фрагмент CORBA-интерфейса «классной доски».
// Листинг 13.1. CORBA-объявления, необходимые для нашего // класса «классной доски»
typedef sequence
interface black_board{
//. . .
void suggestionsForMajor(in courses Major);
void suggestionsForMinor(in courses Minor);
void suggestionsForGeneral(in courses General);
void suggestionsForElectives(in courses Electives);
courses currentDegreePlan();
courses suggestedSchedule();
//. . .
};
Главная цель интерфейса black_board — обеспечить доступ для чтения и записи со стороны источников знаний. В данном случае при разделении «классной доски» необходимо предусмотреть сегменты для каждого источника знаний. Это позволяет источникам знаний получать доступ к «классной доске» посредством CRCW-стратегии. Другими словами, несколько типов источников знаний могут получить доступ к «классной доске» одновременно, но источники знаний одинакового типа должны быть ограничены применением CREW-стратегии. Любой метод или функция-член, с помощью которого источники знаний будут получать доступ к»классной доске», должен быть определен в интерфейсном классе black_board. Класс courses объявляется с использованием типа CORBA, и поэтому его можно применять в качестве параметра и значений, возвращаемых методами при взаимодействии между источниками знаний и «классной доской». Поэтому эти объявления класса black_board
courses Minor; courses Major;
будут использованы для представления информации, которая либо записывается на «классную доску», либо считывается с нее. Тип courses — это синоним для CORBA-типа sequence
allocbuf() freebuf() get_buffer() length() operator[] release() replace() maximum ()
Источники знаний будут взаимодействовать с «классной доской» с помощью этих методов. Объявление sequence
Реализация интерфейсного класса
black_board
Обратите внимание на то, что в интерфейсном классе (см. листинг 13.1) нет объявлений переменных. Вспомните, что интерфейсный класс в CORBA-реализации ограничивается только объявлением методов. В интерфейсном классе не существует компонентов, предназначенных для хранения информации. CORBA-классы должны тесно контактировать с С++-реализациями до конца работы приложения. Реальные реализации методов и необходимых переменных вносятся в производный класс (выведенный из этого интерфейсного класса). Производный класс, выведенный из интерфейсного класса black_board, представлен в листинге 13.2.
// Листинг 13.2. Фрагмент класса реализации для
// интерфейсного класса black_board
#include «black_board.h»
#include
class blackboard : virtual public POA_black_board{
protected:
//. . .
set
set
set
set
courses Schedule; courses DegreePlan;
public:
blackboard(void); ~blackboard(void);
void suggestionsForMajor(const courses &X);
void suggestionsForMinor(const courses &X);
void suggestionsForGeneral(const courses &X);
void suggestionsForElectives(const courses &X);
courses *currentDegreePlan(void);
courses *suggestedSchedule(void);
//. . .
} ;
Этот класс реализации используется для предоставления реальных определений методов, объявленных в интерфейсном классе. Помимо реализации методов, производный класс может содержать компоненты данных, поскольку они не объявлены в качестве интерфейса. Обратите внимание на то, что класс реализации black_board, представленный в листинге 13.2, наследует непосредственно не интерфейсный класс black_board, а класс POA_black_board, который является одним из тех классов, которые создает IDL-компилятор от имени интерфейсного класса black_board. Объявление класса POA_black_board приведено в листинге 13.3.
// Листинг 13.3. Фрагмент объявления класса POA_black_board,
// созданного idl-компилятором для
// интерфейсного класса black_board
class POA_black_board : virtual public PortableServer::StaticImplementation
{
public:
virtual -POA_black_board (); black_board_ptr _this ();
bool dispatch (CORBA::StaticServerRequest_ptr); virtual void invoke (CORBA::StaticServerRequest_ptr); virtual CORBA::Boolean _is_a (const char *); virtual CORBA::InterfaceDef_ptr _get_interface (); virtual CORBA::RepositoryId _primary_interface
(const PortableServer::ObjectId &, PortableServer::POA_ptr);
virtual void * _narrow_helper (const char *); static POA_black_board * _narrow (
PortableServer::Servant); virtual CORBA::Object_ptr _make_stub (PortableServer::
POA_ptr,
CORBA::Object_ptr);
//.. .
virtual void suggestionsForMajor (const courses& Major)
= 0;
virtual void suggestionsForMinor (const courses& Minor)
= 0;
virtual void suggestionsForGeneral (
const courses& General) = 0;
virtual void suggestionsForElectives (
const courses& Electives) = 0;
virtual courses* currentDegreePlan() = 0;
virtual courses* suggestedSchedule() = 0;
//. . . protected:
POA_black_board () {}; private:
POA_black_board (const POA_black_board &); void operator= (const POA_black_board &);
};
Обратите внимание на то, что класс в листинге 13.3 является абстрактны м, поскольку он содержит чисто виртуальные функции-члены, напри м ер:
virtual courses* suggestedSchedule() = 0;
Это означает, что данный класс нельзя использовать напря м ую. Из него необходи м о вывести производный класс, в которо м будут определены реальные функции-члены для всех объявлений чисто виртуальных функций. Класс POA_black_board, представленный в листинге 13.2, содержит требуе м ые определения для всех чисто виртуальных функций-членов. Что касается нашего класса «классной доски*', то для реализации действий са м ой «доски» и источников знаний используются С ++-м етоды. Однако источники знаний реализованы частично в языке С++ и частично в языке логического про г ра мм ирования Prolog. Но поскольку С++ под д ерживает мультиязыковую и мультипарадигматическую разработку, к средствам С++ можно вполне добавить достоинства языка Prolog. В С++ мы можем либо породить Prolog-задачи (с помощью posix_spawn() - или fork-exec-функций), либо получить доступ к среде Prolog через ее интерфейс с незнакомыми языками программирования, который позволяет Prolog-среде общаться непосредственно с С++ и наоборот. Независимо от того, на каком языке создана реализация источников знаний — С++ или Prolog, объект «классной доски» должен взаимодействовать только с С++-методами.
Порождение источников знаний в конструкторе «классной доски»
«Классная доска» реализуется как распределенный объект, использующий CORBA-протокол. В данном случае одной из основных целей «классной доски» является порождение источников знаний. Это важный момент, поскольку «классная доска» должна иметь доступ к идентификационным номерам задач. Начальное состояние «классной доски» (оно устанавливается в конструкторе) включает информацию о студенте, его академической характеристике, текущем семестре, требованиях для получения диплома и т.д. С помощью «классной доски», исходя из начального состояния, определяется, какие источники знаний следует запустить в работу. Иначе говоря, оценив начальную задачу и исходное состояние системы, «классная доска» составляет список запускаемых на выполнение источников знаний. Каждый источник знаний имеет соответствующий двоичный файл, а для хранения имен этих файлов «классная доска» использует контейнер Solvers. Позже, при функционировании конструктора, с по м ощью функционального объекта (или объекта-функции) и алгоритма for_each() порождаются источники знаний. Вспомните, что любой класс, в котором определена операторная функция operator(), м ож н о испо л ьзовать как функциональный объект. Объекты-функции, как прави л о при м еняют сов м естно со стандартны м и алгорит м а м и в м есто функций и л и в допо л нение к ни м. Обычно везде, где м ожно использовать обычную функцию, ее м ожно за м енить объекто м -функцией. Чтобы определить собственный функциональный объект, необходи м о определить операторный м етод operator (), придав е м у соответствующий с м ысл, указав список пара м етров и тип возвращае м ого и м значения. Наша CORBA-реализация «классной доски» м ожет под д ерживать источники знаний, реализованные с по м ощью PVM-задач, традиционных UNDC/Linux-задач или от д ельных потоков, использующих библиотеки POSIX thread. По типу задач, порождае м ых в конструкторе, м ожно определить, с каки м и и м енно задача м и будет работать «классная доска»: с POSIX-потока м и, традиционны м и UNIX/Linux-процесса м и или PVM-задача м и.
Порождение источников знаний с помощью PVM-задач
Конструктор «классной доски» содержит следующий вызов алгоритма, for_each(Solve.begin(),Solve.end(), Task);
Алгоритм for_each () применяет операторный метод объекта функции (созданного для класса задачи) к каждому элементу контейнера Solve. Этот метод используется для порождения источников знаний в соответствии с моделью MIMD, при реализации которой все источники знаний имеют различную специализацию и работают с различными наборами данных. Объявление этого класса задач приведено в листинге 13.4.
// Листинг 13.4. Объявление класса задачи
class task{
int Tid[4];
int N;
//. . .
public:
//. . .
task(void) { N = 0; } void operator()(string X);
};
void task::operator()(string X) {
int cc; pvm_mytid();
cc = pvm_spawn(const_cast
N++;
}
blackboard::blackboard(void) {
task Task;
vector
//.. .
// Determine which KS to invoke
//. . .
Solve.push_back(KS1);
Solve.push_back(KS2);
Solve.push_back(KS3);
Solve.push_back(KS4);
for_each(Solve.begin(), Solve.end(), Task);
}
Этот класс task инкапсулирует порожденный процесс. Он содержит идентификационный но м ер задачи (поскольку у нас используется PVM-задача). В случае при м енения стандартных UNDC/Linux-процессов или Pthread-потоков, он должен содержать идентификационный но м ер процесса или потока. Этот класс действует как интерфейс между создаваемым процессом или потоком и «классной доской». «Классная доска» здесь является основным компонентом управления. Она может управлять PVM-задачами с помощью их идентификационных номеров. Кроме того, «классная доска» может использовать групповые PVM-операции для синхронизации PVM-задач с использованием барьеров, организации PVM-задач в логические группы, которые должны отрабатывать определенные аспекты решаемой задачи, и сигнализации членов группы с помощью соответствующих тегов сообщений. Групповые PVM-операции перечислены и описаны в табл. 13.2.
Особый интерес для нашей «классной доски» представляют операции pvm_barrier() и pvm_joingroup(), поскольку существуют ситуации, в которых «классная доска» не запускает новые источники знаний до тех пор, пока определенная группа источников знаний не завершит свою работу. Для блокирования вызывающего процесса до нужного момента (до окончания обработки данных соответствующими источниками знаний) можно использовать операцию pvm_barrier (). Например, «классная доска» в качестве консультанта по выбору курсов обучения не будет активизировать источник знаний, отвечающий за составление расписания, до тех пор, пока не представят свои предложения источники знаний, которые специализируются на основных, общеобразовательных, второстепенных и факультативных курсах. Поэтому «классная доска» будет использовать операцию pvm_barrier () для ожидания завершения работы этой группы PVM-задач. На рис. 13.5 представлена UML-диаграмма видов деятельности, которая позволяет понять, как синхронизируются источники знаний и «классная доска».
Барьер синхронизации здесь реализуется с помощью операций pvm_barrier () и pvm_joingroup (). Реализация операторной функции для объекта задачи приве д ена в л истин г е 13.5.
Таблица 13.2. Групповые PVM-операции
int pvm_joingroup (char *groupname); Вносит вызывающий процесс в группу groupname, а затем возвращает int-значение, которое представляет собой номер процесса в этой группе
int pvm_lvgroup (char *groupname); Удаляет вызывающий процесс из группы groupname
int pvm_gsive (char *groupname); Возвращает int-значение, которое представляет собой количество членов в группе groupname
int pvm_gettid (char *groupname, int inum); Возвращает int-значение, равное идентификационному номеру задачи, выполняемой процессом, который идентифицируется именем группы groupname и номером экземпляра inum
int pvm_getinst (char *groupname, int taskid); Возвращает int-значение, которое представляет собой номер экземпляра, связанный с именем группы groupname и процессом, выполняющим задачу с идентификационным номером taskid
int pvm_barrier (char *groupname, int count); Блокирует вызывающий процесс до тех пор, пока count членов в группе groupname не вызовут эту функцию
int pvm_bcast (char *groupname, int messageid); Передает всем членам группы groupname сообщение, хранимое в активном буфере отправки, связанном с номером messageid
int pvm_reduce (void *operation, void *buffer, int count, int datatype, int messageid, char *groupname, int root); Выполняет глобальную операцию operation во всех процессах группы groupname
| #img_88.png Рис.13.5. UML-диаграмма видов деятельности, отображающая синхронизацию «классной доски» и источников знаний |
// Листинг 13.5. Определение функции operator() // в классе task
void task::operator()(string X) {
int cc; pvm_mytid();
cc = pvm_spawn(const_cast
N++;
}
Функция-оператор operator () используется для порождения PVM-задач. Имя задачи содержится в элементе X. data (). При обращении к функции pvm_spawn () (см. листинг 13.5) создается одна задача, а ее идентификационный номер сохраняется в элементе Tid[N] . (Подробнее о функции pvm_spawn () и вызове PVM-задач см. гла-вуб.) Класс task используется для создания функциональных объектов (объектов-функций). При выполнении алгоритма
for_each(Solve.begin(),Solve.end(),Task);
вызывается функция operator (), которая выполняет объект Task. Эта операция заставляет активизироваться источники знаний, содержа щ иеся в контейнере Solve. Алгоритм for_each () гарантирует активизацию всех источников знаний. Если используется м одель SIMD, то в алгоритме for_each () нет никакой необходимости. Вместо него прямо в конструкторе «классной доски» мы используем вызов функции pvm_spawn(). В листинге 13.6 как раз и показано, как при использовании модели SIMD можно запустить множество PVM-задач из конструктора «классной доски».
// Листинг 13.6. Запуск PVM-задач из конструктора
// класса task
void task::operator()(string X) {
int cc; pvm_mytid();
cc = pvm_spawn(const_cast
}
Связь «классной доски» и источников знаний
Согласно коду, приведенному в листинге 13.6, порождается 20 источников знаний. Сначала все они выполняют одинаковый код. После их порождения «классная доска» должна отправить сообщения с указанием, какую роль они будут играть в процессе решения задачи. При использовании данной конфигурации источники знаний и «классная доска» являются частью PVM-среды. После создания источники знаний будут взаимодействовать с «классной доской» путем соединения с портом, на котором она размещается, или по ее адресу в сети intranet или Internet. Для этого источникам знаний понадобится объектная ссылка на «классную доску». Эти ссылки можно «зашить» в код источников знаний, или они могут прочитать их из файла конфигурации либо получить из службы имен. Имея ссылку, источник знаний взаимодействует с ORB-брокером (Object Request Broker — брокер объектных запросов), чтобы найти удаленный объект, содержащий реальные данные (знания) и активизировать его. Для нашего примера мы назначаем «классной доске» конкретный порт и запускаем CORBA-объект «классной доски» с помощью следующей ко м анды,
blackboard -ORBIIOPAddr inet:porthos:12458
По этой команде запускается наша программа «классной доски» с подключением к порту 12458 хоста porthos. Запуск CORBA-объекта зависит от используемой CORBA-реализации. В данном случае мы используем «открытую» CORBA-реализацию Mico При выполнении программы blackboard реализуется экземпляр «классной доски», который в свою очередь порождает источники знаний. В созданных источниках знаний жестко закодирован номер порта, по которому они будут связываться с «классной доской». Фрагмент кода реализации источника знаний, который связывается с CORBA - ориентированным объектом «классной доски», представлен в листинге 13.7.
// Листинг 13.7. Код источника знаний, который связывается
// с CORBA-ориентированной «классной доской»
1 #include «pvm3.h»
2 using namespace std;
3 #include
4 #include
5 #include
6 #include
7 #include «black_board_impl.h» 8
9 int main(int argc, char *argv[])
10 {
11 CORBA::ORB_var Orb = CORBA::ORB_init(argc, argv,«mico-local-orb»);
12 CORBA::Object_yar Obj =Orb->bind(«IDL:black_board:1.0»,«inet:por thos:12 4 5 8»);
13 courses Courses;
14 //...
15 //...
16 black_board_var BlackBoard = black_board::_narrow(Obj);
17
18 int Pid;
19 //...
20 //... 21
22 cout « «Источник знаний создан.» « endl;
23 Courses.length(2);
24 Courses[0] = 255551;
25 Courses[l] = 253212;
26 string FileName;
27 strstream Buffer;
28 Pid = pvm_mytid();
29 Buffer « «Результат.» « Pid « ends;
30 Buffer » FileName;
31 ofstream Fout(FileName.data());
32 BlackBoard->suggestionsForMajor(Courses);
33 Fout.close();
34 pvm_exit();
35 return(0);
36 } 37
В строке 11 (см. листинг13.7) инициализируется ORB брокер . При выполнении строки 12 осу щ ествляется связывание имени объекта black_board с портом 12458 и возвра щ ается ссылка на CORBA-объект в переменной Obj. Строку 16 можно расценивать как разновидность операции приведения типа, чтобы Переменная BlackBoard ссылалась на объект «правильного размера». После того как источник знаний реализовал объект BlackBoard, он может вызывать любой метод, объявленный в интерфейсе black_board, код которого приведен в листинге 13.1. Обратите внимание на создание в строке 13 объекта Courses. Вспомните, что тип courses изначально был определен как CORBA-тип sequence. Здесь источник знаний использует класс courses, созданный во время IDL-компиляции. Добавление элементов в этот класс можно представить как добавление элементов в любой массив. При выполнении строк 24 и 25 в объект Courses добавляются два элемента, а в строке 32 содержится вызов метода, которому в качестве параметра передается объект Courses: BlackBoard->suggestionsForMaj or(Courses)
При выполнении этого вызова информация о курсах обучения записывается на «классную доску». Аналогично следующие методы
courses currentDegreePlan(); courses suggestedSchedule();
можно использовать для считывания информации с «классной доски». Поэтому для об щ ения с «классной доской» источнику знаний достаточно иметь ссылку на объект Black_board. Объект Black_board может располагаться в любом м есте сети intranet или Internet. Найти реальное м естоположение удаленного объекта — забота исключительно ORB-боркера. (Процесс отыскания и активизации CORBA-объектов расс м атривается в главе8.) Поскольку объект Black_board и м еет идентификационные но м ера PVM-задач, он м ожет управлять эти м и задачами и обмениваться сообщениями (отправлять и получать их) непосредственно с источниками знаний. Аналогично источники знаний могут напрямую взаимодействовать друг с другом, используя традиционный обмен PVM-сообщениями. Важно отметить следующее: после того как окажется, что не существует больше никаких системных PVM-вызовов, деструктор объекта Black_board должен вызвать м етод pvm_exit(), а каждый источник знаний — м етод pvm_exit (). Те м са м ы м из PVM-среды будут удалены ненужные больше объекты, но обработкаданных, не связанная с эти м и объекта м и, м ожет продолжаться.
Активизация источников знаний с помощью POSIX-функции
spawn()
Реализация источников знаний в ра м ках PVM-задач особенно полезна в ситуации, если задачи должны выполняться на разных компьютерах. Каждый источник знаний в этом случае может воспользоваться преимуществами любого специализированного ресурса, которым может быть оснащен конкретный компьютер. К таким ресурсам можно отнести быстродействующий процессор, базу данных, специальное периферийное оборудование и наличие нескольких процессоров. PVM-задачи можно также использовать на одном компьютере с несколькими процессорами. Но поскольку взаимодействие с нашей «классной доской» легко реализовать путем подключения к порту, для реализации источников знаний, не мудрствуя лукаво, мы можем также использовать традиционные UNDC/Linux-процессы. Если источники знаний создаются в стандартных UNIX/Linux-процессах, а компьютер содержит несколько процессоров, то источники знаний могут выполняться параллельно на этих процессорах. Но если источников знаний больше, чем процессоров, возникает необходимость в многозадачности. На рис. 13.6 показаны два простых архитектурных варианта, которые можно использовать с CORBA-ориентированной «классной доской» и UNIX/Linux-процессами.
| #img_89.png Рис. 13.6. Два архитектурных варианта использования CORBA-ориентированной «классной доски» и UNIX/Linux-процессов |
В варианте 1 CORBA-объект и источники знаний размещаются на одном компьютере, и каждый источник знаний имеет собственное адресное пространство. Другими словами, каждый источник знаний порожден с помощью функции posix_spawn() или семейств а функций fork-exec. В варианте 2 CORBA-объект размещается на одном компьютере, а все источники знаний — на другом, но в различных адресных пространствах. В обоих вариантах CORBA-объект действует как разновидность общей памяти для источников знаний, поскольку все они получают доступ к нему и могут обмениваться информацией через «классную доску». При этом важно помнить о существовании основного преимущества CORBA-объекта — он имеет более высокую организацию, чем простой блок памяти. «Классная доска» — это объект, который может состоять из структур данных любого типа, объектов и даже других «классных досок». Такой вид организации не может быть реализован простым использованием базовых функций доступа к общей памяти. Поэтому CORBA-реализация обеспечивает идеальный способ разделения сложных объектов между процессами. В подразделе 13.5.3.1 описано создание PVM-задач, которые реализуют источники знаний. Здесь мы изменяем конструктор, включал в него вызовы функции posix_spawn () (с той же целью можно использовать алгоритм for_each () и функциональный объект задачи для вызова функции posix_spawn()). В варианте 1 (см. рис. 13.6) «классная доска» может порождать источники знаний при реализации конструктора. Но в варианте 2 это невозможно, поскольку «классная доска» расположена на отдельном компьютере. Поэтому в варианте 2 «классной доске» для вызова функции posix_spawn () приходится прибегать к услугам посредника. Посредничество можно организовать разными способами, например, «классная доска» может вызвать другой CORBA-объект, расположенный на одном компьютере с источниками знаний. С той же целью можно использовать удаленный вызов процедуры (Remote Procedure Call — RPC) или MPI- либо PVM-задачу, которая должна вызвать программу, содержащую обращение к функции posix_spawn (). (Описание вызовов функции posix_spawn () приведено в главе 3.) Как можно использовать функцию posix_spawn() для активизации одного из источников знаний, показано в листинге 13.8.
// Листинг 13.8. Использование функции posix_spawn() для
// запуска источников знаний
#include
//.. .
pid_t Pid;
posix_spawnattr_t M;
posix_spawn_file_actions_t N;
posix_spawn_attr_init(&M);
posix_spawn_file_actions_init(&N);
char *const argv[] = {«knowledge_source1»,NULL};
posix_spawn(&Pid,«knowledge_source1»,&N,&M,argv,NULL);
//. . .
}
В листинге 13.8 инициализируются атрибуты и действия, необходимые для порождения задач, после чего с помощью функции posix_spawn() создается отдельный процесс, который предназначен для выполнения источника знаний knowledge_source1. После создания этого процесса «классная доска» получает к нему доступ через его идентификационный номер, сохраняемый в параметре Pid. Кроме «классной доски», используемой в качестве средства связи, возможно и стандартное межпроцессное взаимодействие (IPC), если «классная доска» расположена на одном компьютере с источниками знаний. «Классная доска» — самый простой способ взаимодействия между источниками знаний, хотя в конфигурации размещения «классной доски» на отдельном компьютере можно использовать с этой целью сокеты. В этом случае управление, осуществляемое «классной доской» над источниками знаний, будет более жестким и обусловленным в любой момент времени содержимым «классной доски», а не сообщениями, передаваемыми непосредственно источникам знаний. Прямую пересылку сообщений легче реализовать при использовании «классной доски» в сочетании с PVM-задачами. В этом случае источники знаний сами настраивают себя на основе содержимого «классной доски». Но «классная доска» все же имеет определенный «рычаг»управления источниками знаний, поскольку ей «известны» идентификационные номера всех процессов, содержащих источники знаний. Как модель MPMD (MIMD), так и модель SPMD (SIMD), также поддерживаются использованием функции posix_spawn(). В листинге 13.9 представлен класс, который можно использовать в качестве объекта-функции при выполнении алгоритма for_each ().
// Листинг 13.9. Использование класса child_process как
// объекта-функции при запуске источников
// знаний
class child_process{
string Command;
posix_spawnattr_t M;
posix_spawn_file_actions_t N;
pid_t Pid;
//.. .
public:
child_process(void);
void operator()(string X);
void spawn(string X);
};
void child_process::operator()(string X) {
//.. .
posix_spawnattr_init(&M);
posix_spawn_file_actions_init(&N);
Command.append("/tmp/");
Command.append(X);
char *const argv[] = {const_cast
posix_spawn(&Pid,Command.data(),&N,&M,argv,NULL);
Command.erase(Command.begin(), Command.end()); //.. .
}
Мы инкапсулируем атрибуты, необходимые для функции posix_spawn() , в классе child_process. Инкапсуляция всех данных, требуемых для вызова этой функции в классе, упро щ ает ее использование и обеспечивает естественный интерфейс с атрибутами процесса, который создается с ее помощью. Обратите внимание на то, что в классе child_process мы определили функцию operator () (см. листинг 13.9). Это означает, что класс child_process можно использовать в качестве функционального объекта при выполнении алгоритма for__each (). По мере того как «классная доска» решает, какие источники знаний необходимо активизировать для решения задачи, она сохраняет их имена в контейнере Solve. Позже при выполнении конструктора «классной доски» нужные источники знаний активизируются с помощью алгоритма for_each ().
// Конструктор.
//...
child_process Task;
for_each(Solve.begin(), Solve.end(), Task);
При выполнении этого конструктора для каждого элемента контейнера Solve вызывается метод operator (), код которого приведен в листинге 13.9. После активизации источники знаний получают доступ к ссылке на объект «классной доски» и могут приступать к решению свой части задачи. И хотя источники знаний здесь не являются PVM-задачами, они связываются с «классной доской» таким же способом (см. подраздел 13.5.3.2) и так же выполняют свою работу. Дело в том, что межпроцессное взаимодействие между стандартными UNIX/Linux-процессами отличается от межпроцессного взаимодействия, которое возможно с использованием PVM-среды. Кроме того, PVM-задачи могут располагаться на разных компьютерах, в то время как процессы, созданные с помощью функции posix_spawn(), могут существовать только на одном и том же компьютере. Если процессы, созданные функцией posix_spawn() (либо семейством функций fork-exec), необходимо использовать в сочетании с моделью SIMD, то в дополнение к объекту «классной доски» для назначения источникам знаний конкретных областей задачи, которые они должны решать, можно использовать параметры argc и argv. В случае, когда «классная доска» находится на одном компьютере с источниками знаний, и она активизирует источники знаний в своем конструкторе, то формально «классная доска» является для них родителем, а потомки наследуют от родителя переменные среды. Переменные среды «классной доски» можно использовать в качестве еще одного способа передачи информации источникам знаний. Этими переменными среды можно легко управлять, используя следующие функции.
#include
//.. .
setenv();
unsetenv();
putenv();
Если источники знаний реализуются в процессах, которые созданы с помощью функции posix_spawn () (или fork-exec), то их программирование не выходит за рамки обычного CORBA-программирования с доступом ко всех средствам, предлагаемым CORBA-протоколом.
Реализация модели «классной доски» с помощью глобальных объектов
Выбор CORBA-ориентированной «классной доски» вполне естествен в условиях, когда источники знаний должны быть реализованы в среде intranet или Internet, или когда в целях соблюдения модульного принципа организации, инкапсуляции и так далее каждый источник знаний реализуется в отдельном процессе. Однако в распределении «классной доски» необходимость возникает не всегда. Если источники знаний можно реализовать в рамках одного процесса или на одном компьютере, то лучше всего в этом случае организовать несколько потоков, поскольку при таком варианте быстродействие выше, расходы системных ресурсов меньше, а сама работа (настройка) — проще. Взаимодействие между потоками легче организовать, поскольку потоки разделяют одно адресное пространство и могут использовать глобальные переменные. Ведь тогда «классную доску» можно реализовать как глобальный объект, доступный всем потокам в процессе. При реализации источников знаний в виде потоков в рамках одной программы отпадает необходимость в межпроцессном взаимодействии, использовании сокетов или какого-либо другого типа сетевой связи. Кроме того, в этом случае оказывается ненужным дополнительный уровень CORBA-протокола, поскольку можно обойтись разработкой обычных C++-классов. Если многопоточная программа рассчитана на использование одного компьютера с несколькими процессорами, то потоки могут выполняться параллельно на доступных процессорах. В SMP- и МРР-системах потоковая конфигурация «классной доски» весьма привлекательна. В общем случае при использовании потоков достигается самая высокая производительность. Потоки часто называют облегченными процессами, поскольку они не требуют таких же расходов системных ресурсов, как традиционные UNIX/Linux-процессы. В библиотеке POSIX threads (Pthreads) предусмотрено практически все, что нужно для создания источников знаний и управления ими. На рис. 13.7.1-13.7.3 представлены три базовые конфигурации распределения процессов для «классной доски» и источников знаний.
| #img_90.png Рис. 13.7. Базовая конфигурация распределения процессов для «классной доски» и источников знаний |
Поскольку «классная доска» реализована в многопоточной среде, то для синхронизации доступа к «классной доске» можно использовать Pthread-мьютексы и переменные условий, которые необходимо инкапсулировать в интерфейсных классах, как описано в главе 11. Кроме того, для координации и синхронизации работы, выполняемой источниками знаний, можно использовать функции pthread_cond_signal () и pthread_cond_broadcast (). Поскольку «классная доска» сама создает потоки, ей будет нетрудно получить доступ к идентификационным номерам всех источников знаний. Это означает, что «классная доска» может при необходимости аннулировать поток, используя функцию pthread_cancel (). Кроме того, «классная доска» способна синхронизировать выполнение источников знаний с помощью функции pthread_join(). Помимо уже перечисленных достоинств многопоточной реализации (высокое быстродействие и простота использования потоков и глобального объекта «классной доски»), существует также проблема обработки ошибок и исключительных ситуаций.
В общем случае эта проблема решается проще в рамках одного процесса и одного компьютера, чем при использовании нескольких процессов и нескольких компьютеров. На рис. 13.8 показаны уровни сложности, связанные с обработкой ошибок и исключительных ситуаций при использовании различных конфигураций.
| #img_91.png Рис. 13.8. Уровни сложности при обработке ошибок и исключений |
Если источники знаний реализованы в отдельных потоках одного и того же процесса, то обработка возможных ошибок или исключительных ситуаций в этом случае относится к уровню сложности 2. Эту степень сложности необходимо учитывать еще на этапах проектирования и разработки программы, особенно в случае, если она требует параллельного программирования. Простейшее архитектурное решение, использующее модель «классной доски», состоит в реализации «классной доски» в виде глобального объекта, а источников знаний — в виде потоков. Рассмотрим фрагмент объявления класса blackboard.
// Листинг 13.10. Фрагмент объявления класса blackboard,
// разработанного для многопоточной среды
class blackboard{ protected: //.. .
set
set
set
set
set
set
mutex Mutex[10];
//.. .
public:
blackboard(void) ;
~blackboard(void);
void suggestionsForMajor(set
void suggestionsForMinor(set
void suggestionsForGeneral(set
void suggestionsForElectives(set
set
set
//.. .
};
Класс blackboard предназначен для реализации в качестве глобального объекта, к которому смогут получать доступ все потоки в программе. Обратите внимание на то, что класс blackboard в листинге 13.10 включает массив мьютексов. Эти мьютексы используются для защиты критических разделов «классной доски». При реализации источников знаний практически нет необходимости беспокоиться о синхронизации доступа к критическим разделам, поскольку код синхронизации инкапсулирован в классе blackboard.
Активизация источников знаний с помощью потоков
В этом разделе рассматривается реализация источников знаний в отдельных потоках. Потоки создаются здесь при выполнении конструктора класса «классной доски» (blackboard), и каждому потоку назначается конкретный источник знаний. Тем самым реализуется модель MIMD. Фрагмент кода конструктора класса blackboard приведен в листинге 13.11.
// Листинг 13.11. Конструктор класса blackboard,
// используемый для создания потоков,
// содержащих источники знаний
blackboard::blackboard(void) {
pthread_t Tid[4];
//.. .
try{
pthread_create(&Tid[0],NULL,suggestionForMajor, NULL);
pthread_create(&Tid[l],NULL, suggestionForMinor, NULL);
pthread_create(&Tid[2], NULL,suggestionForGeneral, NULL);
pthread_create(&Tid[3],NULL, suggestionForElective, NULL);
pthread_join(Tid[0],NULL);
pthread_join(Tid[l],NULL);
pthread_join(Tid[2],NULL);
pthread_join(Tid[3],NULL);
}
//. . .
}
Обратите внимание на то, что конструктор вызывает функцию pthread_join(). Этот вызов заставляет конструктор ожидать завершения работы всех четырех потоков. Эти потоки могут активизироваться и с помощью других функций-членов класса blackboard. Но те действия, которые выполняют источники знаний «в рамках» конструктора, представляют своего рода предварительную инициализацию «классной доски», поэтому весьма уместно не продолжать работу по созданию объекта «классной доски» до тех пор, пока эти потоки не доведут до конца свою работу. Такой подход к созданию потоков в конструкторе заставляет задуматься об обработке ошибок и исключительных ситуаций. Что произойдет, если по какой-то причине при выполнении потоков случится сбой? Поскольку конструкторы не возвращают никаких значений, то здесь просто необходимо позаботиться об обработке исключительных ситуаций. Каждый поток связывается со «своей» функцией.
void *suggestionForMajor(void *X);
void *suggescionForMinor(void *X);
void *suggestionForGeneral(void *X);
void *suggestionForElective(void *X);
Эти четыре функции используются потоками для реализации действий соответствующих источников знаний. Поскольку «классная доска» является глобальным объектом, каждая из этих функций имеет непосредственный доступ к функциям-членам класса blackboard. Поэтому источники знаний могут вызывать функции-члены «классной доски» напрямую.
//...
Combination.generateCombinations(1,9, Courses);
Result = Combination.element(9);
//.. .
Blackboard.suggestionsForMinor(Value);
//.. .
Поскольку некоторые разделы «классной доски» имеют ограниченный доступ для отдельных источников знаний, то к этим разделам можно применить CRCW-стратегию доступа (рис. 13.9).
Тип параллелизма, представленный на рис. 13.9, вполне естествен для систем, реализующих модель «классной доски», поскольку «классная доска» часто делится на разделы, относящиеся к определенным частям задачи или подзадачи. Обычно одной проблемной области соответствует один источник знаний, поэтому параллельный доступ к этим разделам вполне уместен.
Резюме
| #img_92.png Рис. 13.9. Четыре источника знаний могут параллельно считывать информацию из соответствующих разделов «классной доски» и записывать ее туда |
Модель «классной доски» поддерживает параллелизм, который присутствует как в структуре «классной доски», так и в отношениях между «классной доской» и источниками знаний, а также между самими источниками знаний. Модель «классной доски» — это модель решения некоторой задачи. Общая задача делится на части, соответствующие конкретным областям знаний. Каждой области назначается источник знаний, или решатель задач. Источники знаний обычно отличаются самодостаточностью (автономностью) и не требуют интенсивного общения с другими источниками знаний. Необходимое взаимодействие осуществляется через «классную доску». Следовательно, источники знаний позволяют организовать обработку данных в рамках программы по модульному принципу. Такие своеобразные модули могут работать отдельно и параллельно, не требуя сложной синхронизации. «Классную доску» можно реализовать в виде CORBA-объектов. В этом случае источники знаний могут быть распределены в сетях intranet или Internet. «Классная доска» действует как разновидность общей распределенной па м яти д ля за д ач, выполняе м ых в сре д е PVM-типа. В м о д ель «классной д оски» легко вписываются м о д ели MPMD (MIMD) и SPMD (SIMD). Концепция «классной д оски» побуж д ает разработчика раз д елить работу, которую должна выполнить програ мм а, на области знаний. После проведения деко м позиции работ «классная доска» должна содержать м одели ПО пред м етной области и пространства решений. Эти м одели ПО позволяют проектировщику и разработчику вскрыть параллелиз м, который необходи м о реализовать в програ мм е. После классической м одели распределенного програ мм ирования «клиент-сервер» м одель «классной доски» является одной из м о щ ных м оделей, доступных как для распределенного, так и д л я парал л е л ьного програ мм ирования. Источники знаний, и л и решате л и задач, в м оде л и «классной доски» зачастую реализуются как агенты.