10 Теория взаимодействующих процессов. Определение операций над процессами.

Набор операций

Процесс не может сам перейти из одного состояния в другое. Изменением состояния процессов занимается операционная система, совершая операции над ними. Количество таких операций в нашей модели пока совпадает с количеством стрелок на диаграмме состояний. Удобно объединить их в три пары:

Создание процесса — завершение процесса;

Приостановка процесса (перевод из состояния исполнение в состояние готовность) — запуск процесса (перевод из состояния готовность в состояние исполнение);

Блокирование процесса (перевод из состояния исполнение в состояние ожидание) — разблокирование процесса (перевод из состояния ожидание в состояние готовность);

Изменение приоритета процесса.

Операции создания и завершения процесса являются одноразовыми, так как применяются к процессу не более одного раза (некоторые системные процессы никогда не завершаются при работе вычислительной системы). Все остальные операции, связанные с изменением состояния процессов, будь то запуск или блокировка, как правило, являются многоразовыми.

Операция присоединения символа .

Если P - процесс , а c P , то (c->P) определяется как процесс , который начинается с события c , а затем выполняется как процесс P .

Формально это определяется так :(c->P) = _df {<>}  { (c -> s) | c P & s P } .

Альтернативная операция .

Если P и Q -процессы , то операция P | Q определяется как P или Q .Формально эта операция определяется следующим образом :P | Q= _df P  Q , где  (P | Q ) = P  Q .

Начальное состояние процесса .

Если P - процесс , то определим P⁰ как множество символов ,опреде-ляющих стартовое состояние процесса :P⁰ = _df { c | < c >  P }

Операция "после". Если s - след процесса P , определим P/s (P после s) как множество следов , определяющее поведение процесса P после следа s :P/s = _df { t | st  P } .

Последовательная композиция . Если P и Q -процессы , то последовательная композиция (P; Q) выполняется как процесс P до успешного завершения P , затем выполняется как процесс Q . Если процесс P не завершается успешно , то переход на выполнение процесса Q не может быть осуществлен . Признаком успешного завершения процесса (следа ) является событие успешного завершения , обозначаемое символом . Формально последовательная композиция определяется следуюшим образом :

(P; Q) = _df { s; t | s P & t Q } .

Определим процесс SKIP = _df { <> , <  > } , который понадобится нам в дальнейших рассуждениях . Также , как процесс FAIL , процесс SKIP" ничего не делает ", но в отличие от процесса FAIL завершается всегда

успешно .

Параллельная композиция. Пусть P - процесс в алфавите A , а Q - процесс в алфавите B . Тогда через P_A || _B Q обозначается операция параллельной композиции процессов P и Q в алфавите (A  B) . Каждое событие , принадлежащее пересечению алфавитов (A  B) и соответственно являющееся общимсобытием , определяет точку взаимодействия параллельно выполняемых процессов P и Q . Событие из множества A-B предполагает участие только процесса P , а событие из множества B-A предполагает участие только процесса Q . Отсюда следует , что любой след процесса P_A || _B Q после удаления из него событий из множества B-A превращается в след процесса P , а после удаления из него событий из A-B превращается в след процесса Q . Приведенные выше рассуждения обосновывает следующее определение параллелизма :

P_A || _B Q = _df { s | s (A B) ^* & s  A  P & s  A  Q }

Взаимодействие параллельных процессов. Пусть P и Q - параллельно выполняемые процессы . Если

P  Q =  , то это означает , что процессы P и Q не взаимодействуют друг с другом. Однако этот случай не представляет особого интереса в исследовании свойств параллельных процессов , поскольку с точки зрения математической модели при отсутствии взаимодействия безразлично , параллельно выполняются процессы или выполняются последовательно друг за другом. Поэтому будем рассматривать случай , когда P  Q   .Взаимодействие параллельно выполняемых процессов осуществляется путем обмена сообщениями , то есть один из процессов передает сообщение , а другой принимает его. Для передачи данных от одного процесса к другому в теории CSP используются каналы передачи данных . Вводятся две операции : c ! m -операция передачи сообщения m через канал c , c ? x -операция приема сообщения из канала с в переменную x . В теории CSP рассматривается случай синхронного взаимодействия процессов , который предусматривает одновременное выполнение операций c ! m и c ? x . Таким образом одновременное выполнение этих операций позволяет трактовать его как единое неделимое событие взаимодействия процессов . Последнее определяется следующим соотношением :

( c!m-> P ) || ( c?x-> F(x) ) = c-> ( P || F(m) ) .