Физическая поддержка связей.
Эквивалентность подразумевает взаимнооднозначное соответствие элементов двух различных множеств. Для такого вида связи элементов традиционно используются простые структуры. Простой структурой мы будем считать последовательные записи значений элементов фиксированного размера. Эквивалентность элементов нескольких множеств порождает новую сущность и означает их полную парную эквивалентность. Как известно, её можно отразить на минимальном базисе (дереве смежности), что и происходит в записи.
Множества могут быть представлены как контейнеры. Для пары контейнеров-векторов (при известном адресе их дескрипторов) нам можно пользоваться неотрицательными целочисленными индексами 0, 1, ...,S-1 (S – размер вектора) для указания логических адресов их элементов. В случае контейнера-списка мы будем использовать физические адреса, т.е. указатели на элементы как простые структуры.
Вариант объектно-ориентированной бдвв приложения.
Мы рассмотрим вариант “не совсем чистой” объектной модели данных. В роли объектов у нас будут выступать:
место - состояние (ключ – его идентификатор, свойство – текущее количество меток);
место – переход (ключ – его идентификатор, свойство – время задаержки);
входная ветвь места-перехода, она же выходная для места-состояния (ключ – пара связей с её местом состоянием и местом-переходом, свойство – количество захватываемых меток);
выходная ветвь места-перехода, она же входная для места-состояния (ключ – пара связей с её местом состоянием и местом-переходом, свойство – количество сбрасываемых меток);
событие внешнего воздействия (ключ-пара связей с местом-состоянием и каталогом моментов времени, свойство – количество добавляемых или забираемых из места-состояния меток);
внутреннее событие сети (ключ – пара связей с местом переходом и моментом временни окончания активности перехода, т.к. момент начала жестко ним им связан).
Понятие календаря событий вводится как элемент трактовки времени в имитационной системе. С его помощью мы используем так называемую латентность активности схемы во времени и пространстве (т.к. в произвольный момент времени основная часть переходов обычно пассивна). В чисто объектном подходе нам следовало бы хранить прогноз окончания для каждого элемента (в том числе и пасивных) в его объекте и сообщать ему текущее время с некоторым шагом (но это - слишком большие потери эффективности).
Календарь событий.
Особая роль календаря событий поддерживается его организацией в виде списка кортежей. Все остальные структуры данных – вектора кортежей. Связи между объектами (кортежами) статической части сети поддерживаются явно. Сложнее с описанием внешних воздействий и активности в протоколах. На рисунке в предидущем заголовке продемострирован “экстремизм” – время сделано общим для всех значимых событий сети. Но это не совсем отвечает сущности алгоритма! Мы можем считать время внешних событий их свойством и описать это явно.
Можно упорядочить в векторе протокола внешних воздействий их в порядке возрастания по времени (первое условие) и при совпадении момента - по возрастанию порядка в S (второе условие), т.е. сделать сортировку по составному критерию (это уменьшит затраты на поиск). Его можно сразу формировать как реляционное отношение. В отличие от календаря событий оба наших протокола обрабатываются алгоритмом последовательно и проходятся в порядке возрастания времени единственный раз!
Ясно, что есть случаи, когда разумно хранить некоторые данные в реляционной форме и во внутреннем представлении. У нас описание статической сети играет роль параметров задачи (неизменных во времени), а внешние воздействия – векторная функция на местах-состояниях в дискретном времени.
Описание структуры объектной БДВВ на С++.
Учитывая все изложенные выше соображения мы теперь можем описать объектную БДВВ как структуру классов на языке С++. Статическая часть данных сети Петри будет построена на контейнерах-векторах, кортежи которых описаны ниже. Интересней вопрос о связях между элементами контейнеров. Есть два конкурирующих подхода к этой проблеме (каждый со своими достоиствами и недостатками). В первом случае элемент контейнера включает в себя поля поддерживающие связи, а во втором – контейнер содержит только ссылку (указатель) на элемент. Второй способ более гибкий и мы используем его в организации календаря событий. Вместе с этим статическое описание схемы содержит данные, формируемые в потоках использования, ввода или вывода и т.д. Поэтому мы можем поддержать связь с помощью вспомогательного вектора индексов. Это решение намного проше и понятнее. Кроме того, если мы пожелаем сохранить БДВВ в бинарном виде на внешних носителях данных (самый быстрый способ), то не потребуется преобразования индексов (они относительны по своей логической природе).
class cS {public:
string SN; // имя мест-состояния
int N; // текущее количество меток
vector< int > Os; // вектор индексов выходных связей ST
vector< int > Is; // вектор индексов входных связей TS
};
class cT {public:
string TN; // имя места-перехода
int TD; // задержка срабатывания места-перехода
vector< int > Ot; // вектор индексов выходных связей TS
vector< int > It; // вектор индексов входных связей ST
сEC *L; // указатель на послед.элемент списка.
};
class cST {public:
int Os; // индекс состояния, откуда захватили
int It; // индекс перехода, начавшего работу
int TI; // количество захватываемых меток
};
class cTS {public:
int Ot; // индекс перехода, завершившего работу
int Is; // индекс состояния, куда сбрасывать
int TO; // количество сбрасываемых меток
};
Протокол внешних воздействий SP и активности TP мы по прежднему храним в виде реляционных отношений в оперативной памяти (что уже мы делали). Но эти реляционные отношения в нашей задаче заслуживают особого отношения, т.к. это и семантические составляющие понятия “задача” (как входные данные - Input и выходные данные - Output). Остается выделить статическую часть – собственно неживую схему, и мы будем иметь следующее описание БДВВ сети Петри на языке С++.
class cInput {public:
vector< cSP > input; // указатель вектора кортежей
сInput (void);
~сInput (void);
void read(istream&); // чтение по формату из текстового файла
void write(ostream&); // запись по формату в текстовый файла
...
};
class cOutput {public:
vector< cTP > output; // указатель вектора кортежей
сOutput (void);
~сOutput (void);
void read(istream&); // чтение по формату из текстового файла
void write(ostream&); // запись по формату в текстовый файла
...
};
class cScheme {public:
vector< cS > *state; // вектор мест-состояний
vector< cT > *trans; // вектор мест-переходов
vector< cST > *state; // вектор связей S->T
vector< cTS > *state; // вектор связей T->S
сScheme(void);
~сScheme(void);
void read(istream&); // чтение по формату из текстового файла
void write(ostream&); // запись по формату в текстовый файла
...
};
Календарь событий позволяет показать, как можно совмещать динамическую структуру данных (список легко допускает размещение элементов в порядке вознастания времени окончания активности, добавлять и удалять элементы в нужное место) и статическую (неизменную) структуру данных. Ясно, что на элемент списка мы должны иметь указатель.
Остается сформировать класс объектов - процессов решения задачи.
class cTask {public:
cInput *input; // указ. объекта внеш.возд.
cScheme *scheme; // указ. объекта принцип. схемы
list< cEC* > *ecalen; // указатель календаря событий
cOutput *output; // указатель объекта результата
cTask(...);
~cTask(...);
void run(void);
...
};
Особенностью данной организации БДВВ является возможность одновременного хранения в оперативной памяти нескольких задач имитационного моделирования. При этом описание самой схемы не дублируется, а каждому варианту внешнего воздействия формируется свой протокол активности сети Петри. Заметим, что поддержание потока процессов решения задач сама непростая задача. Она связана с необходимостью описания на метауровне истории получения конкретных данных и в САПР БИС получила название задачи организации и поддержания маршрута проектирования.