Графическое представление процессов
Чаще всего полезно представить процесс в виде некоторого графа, включающего кружки-вершины, соединенные стрелками-дугами. По традиции (терминологической) вершины представляют собой состояния процесса, а дуги – переходы между ними, при этом корневая вершина соответствует начальному состоянию процесса. Дуги помечаются именем события, соответствующего данному переходу.
 |
Пример 1. Изобразим графически действия автомата, продающего билеты (рис. 7.7, а), и действия автомата, продающего билеты и расписание (рис. 7.7, б).
Рис. 7.7. Графическое изображение действий автомата:
а – автомат, продающий билеты; б – автомат, продающий билеты и расписание
На рис. 7.7 введены следующие сокращения: мон – опустить монету; бил – получить билет; расп – получить расписание.
Вершина без выходных дуг соответствует состоянию СТОП. А если процесс обладает неограниченным поведением, то для его изображения необходимо ввести непомеченную дугу, ведущую из висячей вершины назад к некоторой вершине графа.
Пример 2. Представим автомат, изображенный на рис.7.7, б в более компактной графической форме (рис. 7.8, а).
Доказать графически, что рис. 7.8, а и рис.7. 8, б иллюстрируют в точности один и тот же процесс.
Слабость графической формы состоит в том, что с ее помощью трудно представить процесс с очень большим количеством состояний. Для отображения событий, в которых участвовал процесс, существует понятие протокола.
Протоколом поведения процесса называют конечную последовательность символов, фиксирующую события, в которых процесс принял участие до некоторого момента времени.
Обычно протокол обозначают последовательностью символов, заключенных в угловые скобки:
< > – пустая последовательность, не содержащая событий;
 |
Рис. 7.8, а Рис. 7.8, б
< x > – последовательность, содержащая единственное событие x;
< x,y > – последовательность, состоящая из двух событий: x и следующего за ним y.
Пример. Для автомата, продающего билеты, после обслуживания первых двух покупателей протокол будет иметь вид
< мон; бил; мон; бил >.
Протокол того же автомата перед тем, как второй покупатель вынул билет, будет
< мон; бил; мон >.
Понятие протокола сегодня широко используется и в компьютерных сетях. Например, в сети Internet, состоящей из множества сетей различной природы: от ЛВС типа Token Ring до глобальных сетей типа NSFNET, базовым протоколом является TCP/IP (Transmission Control Protocol / Internet Protocol). TCP отвечает за доставку сообщений по указанному адресу, а IP поддерживает адресацию сетевых узлов.
Вообще говоря, TCP/IP – это семейство протоколов и прикладных
программ.
Графическая форма представления протоколов позволяет легче анализировать взаимодействие процессов и разрешать (или предупреждать) различные возникающие ситуации, в частности тупики и гонки.
