Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

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

Формально это определяется так:

(c->P) = _df {<>} È { (c -> s) | cÎ aP & sÎ P }

Справедливо следующее утверждение.

Pr1. Если P -процесс, а cÎ aP, то (c->P) является процессом в алфавите aP. Для доказательства Pr1 достаточно показать выполнение аксиом

P0 - P2 аналогично доказательству свойств P3, P4.

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

Если P и Q -процессы, то операция P | Q определяется как P или Q.

Формально эта операция определяется следующим образом:

P | Q= _df P È Q, где a (P | Q) = aP È aQ.

Cправедливы следующие свойства:

U1. если P и Q -процессы, то P | Q также является процессом;

U2. операция P | Q коммутативна и ассоциативна;

U3. P | (aP) ^* = (aP) ^* ;

U4. P | FAIL = P.

Примеры.

А) (a->(b-> FAIL)) | (b-> FAIL) ={ <>,< a >,< a,b >, < b > }.

Б) Оператор if b then P else Q можно представить в виде

(b->P)| (ù b->Q), где ù b рассматривается как событие отрицания b.

B) Операцию (a->P | b-> Q) можно интерпретировать как меню-диалог,

где { a,b } - меню из двух элементов a,b,где выбор элемента a

активизирует процесс P, выбор элемента b активизирует процесс Q.

Упражнения к разделу. Доказать свойства U1 -U4.

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

Если P - процесс, то определим P⁰ как множество символов,опреде-ляющих стартовое состояние процесса:

P⁰ = _df { c | < c > Î P }

Cправедливы следующие свойства:

O1. (FAIL) ⁰ = { };

O2. (A ^*)⁰ = A;

O3. (c-> P) ⁰ = { c };

O4. (P |Q) ⁰ = P⁰ È Q⁰

Пример. ((a-> P) | (b-> Q)) ⁰ = (a-> P) ⁰ È (b-> Q) ⁰.

Упражнения к разделу. Доказать свойства O1 -O4.

2.5.2.4. Операция "после".

Если s - след процесса P, определим P/s (P после s) как множество следов, определяющее поведение процесса P после следа s:

P/s = _df { t | st Î P }.

Cправедливы следующие свойства:

A1. если P - процесс и sÎ P, то P/s - процесс;

A2. P/<> = P;

A3. stÎ P => P/(st) = (P/s)(P/t);

A4. s Î A ^* => A ^*/s = A ^* ;

A5. s Î P => (c-> P) / (c-> s) = P/s;

A6. c Î P⁰ - Q⁰ => (P | Q) / (c-> s) = (P/< c >) / s;

A7. c Î P⁰ Ç Q⁰ => (P | Q) / (c-> s) = ((P/< c >) |(Q/< c >))/ s;

A8. s Î P ó (s=<>)Ú (s₀Î P⁰ & s' Î P/< s₀>).

Замечание. Свойство A8 означает, что если известно P⁰ и для

любого c Î P⁰ определен процесс P/< c>, то процесс определен полностью. Отсюда следует, что можно ввести другой способ

определения процесса, который предусматривает определение процесса парой (I, F),где множество I -начальное состояние процесса, а функция F отображает каждый элемент c Î I в процесс P/< c > (по аналогии с определением автомата - функция переходов). Отсюда, в дополнение к теоретико-множественному способу определения, вводится так называемое процедурное определение процесса. Процедурное определение процесса является более адекватным с точки зрения реализации процесса в отличие от теоретико - - множественного определения.

С другой стороны для исследования свойств процессов более удобным является теоретико- множественная модель, представляющая достаточ-но эффективную математическую базу для формулировки и доказа-тельства свойств процессов. Существуют также и другие модели представления процессов в теории CSP, которые не рассматриваются в рамках данного пособия.

Примеры процедурного определения.

А) Для процесса R = (c-> P):

R⁰ = { c } &

R /< c > = P

.

Б) Для процесса R = (a-> P) | (b-> Q):

R⁰ = { a, b } &

ì P, если x=a

R /< x > = í

î Q, если x=b.

B) Для процесса R = P | Q:

R⁰ = P⁰ È Q⁰ &

ì P, если x Î P⁰ - Q⁰

R /< x > = í Q, если x Î Q⁰ - P⁰

î P/<x> | Q/<x>, если x Î P⁰ Ç Q⁰ .

Упражнения к разделу. Доказать свойства A1 -A8.

2.5.2.5. Последовательная композиция.

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

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

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

S1. SKIP, (P; Q) являются процессами;

S2 (P;Q); R = P;(Q;R) (свойство ассоциативности);

S3. FAIL; P = FAIL;

S4. SKIP; P = P;SKIP = P;

S5. (c-> P); Q =c-> (P; Q), если с ¹ Ö;

S6. (P | Q); R = (P; R) | (Q; R);

S7. (P; Q) ⁰ = P ⁰, если Ö Ï P ⁰;

S7'. (P; Q) ⁰ = (P ⁰ - { < Ö > }) È Q ⁰, если Ö Î P⁰;

Примеры.

А) if b then P = (b->P) | (ù b -> SKIP);

Б) (b->P) | (ù b -> SKIP); Q = (b-> (P;Q)) | (ù b -> Q)

2.5.2.6. Параллельная композиция.

Пусть 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 }

Cправедливы следующие свойства:

C1. Операция || коммутативна и ассоциативна;

C2. P ||P = P; _____

C3. (P ||P) ⁰ = majority(A Ç B, P⁰, Q⁰ ), где

majority(X, Y, Z) =(XÇ Y) È (YÇ Z) È (ZÇ X);

C4. sÎ P || Q => (P || Q)/s = (P/(s éaP)) || (Q/(s éaQ);

Пусть aÎ A-B, bÎ B-A, c,c0,c1Î A Ç B, c0 ¹c1. Тогда:

C5. (c->P) || (c->Q) = c -> (P || Q);

C6. (c0-> P) || (c1-> Q)= FAIL;

C7. (a-> P) || (c->Q) = a-> (P || (c->Q));

C7'. (c-> P) || (b->Q) = b-> ((c->P) || Q);

C8. (a->P) || (b->Q) = (a-> (P || (b->Q))) | (b-> ((a-> P) ||Q))

Билет №11 Параллельное программирование. Основные понятия на основе теории взаимодействующих процессов.

Появление систем параллельных вычислений было вызвано необходимостью существенного увеличения скорости компьютерного решения задач. Появление многопроцессорных вычислительных комплексов, компьютерных сетей и многозадачных операционных систем, основанных на концепции мультипрограммирования, обеспечили реальную базу для практической реализации параллельных вычислений.Содержательно, идея параллельного программирования сводится к декомпозиции проблемы на несколько подзадач, которые выполняются одновременно. Средства связи между параллельно решаемыми задачами, предусматривающие взаимодействие между соответствующими процессами, обеспечивают кооперативное решение проблемы. Существуют разные модели параллелизма, но наиболее распостраненными являются так называемая конвейерная модель и модели параллелизма данных, основанные на одновременном применение одних и тех же операций к различным частям структуры данных. В настоящее время средства параллельного программирования практически встроены в большинство объектно- ориентированных систем управления базами данных. Задача разработки программных средств, обеспечивающих параллельное выполнение процессов, представляется достаточно сложной и поэтому требует построения адекватных математических моделей, позволяющих всесторонне исследовать природу параллельных процессов с целью принятия правильных решений по разработке и реализации алгоримов параллельных вычислений. К настоящему времени сформировалось множество разных подходов к выбору математического аппарата для исследования параллельных процессов. Один из наиболее интересных подходов, сочетающий математическую строгость и адекватность практической реализации, представляет теория взаимодействующих процессов CSP (Communicating Sequential Processes) [5].

Теория базируется на следующих ниже понятиях.

Событие - спецификация существенного факта, имеющего положение в пространстве и во времени. С точки зрения теории автоматов событие- - это возникновение стимула, который может активизировать переход из одного состояния в другое. Событие является атомарным (неразложимым понятием) теории CSP. Примерами событий могут быть возникновение какой либо ошибки в процессе выполнении программ, выполнение определенного запланированного условия, выбор элемента меню, активация командной кнопки, нажатие функциональной клавиши и т.п.. Каждое событие кодируется определенным символом. Множество символов, определяющее все события, в которых некоторый процесс может участвовать, определяет алфавит процесса.

След (трасса) - последовательность событий, определяющая один из возможных путей поведения некоторого процесса, начиная с началавыполнения процесса до определенного фиксированного момента времени. Процесс определяется множеством следов в некотором фиксированном алфавите.Теория CSP позволяет создавать модели параллельно выполняемых взаимодействующих процессов с целью исследования свойств процессов. Результаты этих исследований могут оказаться полезными для принятия обоснованных решений на последующих стадиях разработки и реализации соответствующего программного продукта.