2020-01-15
177
Схемы транзактов – это одно из средств описания параллельных динамических процессов, имитируемым движением абстрактного динамического объекта транзакта по графу состояний системы, образованному из операционных блоков. Каждый блок определяется специальными свойствами, например, начало движение, задержка на время, задержка до выполнения условия и т.п. Концепция транзактов строится на событийной основе. В календарь событий (список будущих событий) включаются транзакты, управляемый императивно. В список текущих событий включаются транзакты, управляемые интерраготивно. Понятие события остается прежним изменением состояния, происходящим мгновенно в модельном времени. Однако концепция транзакта, как основного элемента динамического процесса связывает любое событие с перемещением транзакта по блокам модели. А состояние системы в любой момент времени характеризуется тем, в каком блоке находится транзакт и какую часть модели он прошел. Передвижка транзакта рассматривается как пара событий: «транзакт вошел в блок» (событие IN), «транзакт вышел из блока» (событие OUT). Событие OUT и следующее событие IN рассматриваются как одновременные, поэтому схема потока событий выглядит следующим образом: если транзакт вышел из блока, то он должен обязательно куда-то войти.
|
|
|
OUT -IN; OUT-IN; OUT- IN
OUT - транзакт вышел из особого блока генерации событий.
IN – транзакт входит в особый блок уничтожения событий.
Если транзакт не может немедленно войти в следующий блок, он находится в специальной списковой структуре этого блока, являющейся частью блока.
Одновременно в модели могут присутствовать несколько транзактов, каждый из которых развивает свой собственный процесс
Модели очередей, возникающих при задержке движения транзактов
Возникновение очередей является следствием многих причин: типы потоков событий, интенсивности потоков, структура модели и т.д. Каждый блок, который может задержать транзакт – потенциальное место возникновения очередей. Очереди самопроизвольно возникают и могут самопроизвольно исчезнуть. Основные причины управления очереди:
FIFO, LIFO, приоритетная FIFO, Первом пришел – первым обслужен, последним пришел - последним обслужен. Основные характеристики очереди: средняя длина и средняя время пребывания транзакта.
| Блок i |
| Блок j |
| да |
| да |
| хвост голова |
| Очередь существует |
| Очередь существует |
Важными видами очередей являются очереди ограниченной длины с ограниченным времени пребывания транзактов.
| Блок i |
| Блок j |
| Очередь существует |
| Текущая длина max? |
| Текущее время пребывания max? |
| … |
| Простая очередь |
| Событие: «выйти из очереди» |
| да |
| да |
| да |
| Ограниченная очередь |
|
|
|
Если возникает событие «выйти из очереди» обработка его определяется организацией монитора моделирования. Транзакт может или покинуть модель или предпринять попытку вновь встать в очередь – это определяется вероятностным механизмом.
Структура динамического объекта транзакта:
| Идентификатор т/а (N) Дата рождения Время пребывания т/а в модели Идентификатор блока, в котором нах-ся т/а Параметры т/а |
Проблемы тупиков
Тупики, как и очереди, имеют стохастическую природу возникновения, но в отличие от очередей сами исчезнуть не могут.
Пример, иллюстрирующий схему программы, которая может привести к возникновению тупика.
| ;Процесс i Занять ресурс А на время t1; Освободить А; Ждать (В не используется); Занять В на время t2; Освободить B; | ;Процесс j Занять ресурс B на время t3; Освободить B; Ждать (A не используется); Занять A на время t4; Освободить A; |
Появление тупика (взаимная блокировка) зависит от многих факторов:
· от организации вычислительного процесса;
· от того, в какой момент времени процесс i и процесс j войдут в первый блок – одновременно или нет;
· от значений переменных t1, t2, t3, t4.
Наличие тупика в модели не означает, что процессы обязательно в него войду.
Существует два метода борьбы с тупиками, их предотвращение и обнаружение. Предотвращение заключается в ограничениях на конструирование самих процессов. Обнаружение предусматривает трассы взаимодействия процессов и при обнаружении тупика производится откат до момента, когда процессы могут продолжать свое развитие.
Предотвращение тупиков
1) Линейное упорядочивание типов ресурсов, необходимых процессам. Создается иерархия ресурсов R1<R2<…<Rn, n – число типов ресурсов. Если процесс уже использует ресурс Ri, то он может запросить только такой ресурс Rj, для которого выполняется условие Ri<Rj. При освобождении ресурс Rj раньше Ri. При таком использовании ресурсов тупик возникнуть не может.
2) С использованием матриц запросов и матриц используемых ресурсов. Пусть имеется n-процессов R1<R2<…<Rn, n – количество процессов и R1<R2<…<Rm, m – количество ресурсов. Каждый ресурс типа Ri имеет количество единиц Ci. Использование ресурсов характеризуется матрицей запросов Z=(Z1, Z2,…, Zn), где вектор Z(j) задает максимальное количество единиц ресурсов типа об необходимое процессу Ri. €, где вектор Ui(j) задает количество единиц ресурса j уже используемых процессом i. В начале вычислительного процесса U=0. Каждый процесс последовательно проходит этапы запроса ресурсов, использования и освобождения. Последовательность выдачи ресурсов процессам считается допустимой, если при очередной выдачи ресурса запрос процесса не превышает числа свободных единиц по каждому требуемому ресурсу.
