Лекция 2. Мат. модель. Системы переходов. Системы с синхронным и асинхронным обменом сообщениями_ ... (1185652), страница 2
Текст из файла (страница 2)
Ìû áóäåì ïðèäåðæèâàòüñÿñëåäóþùåãî ñîãëàøåíèÿ î òåðìèíîëîãèè:I Òåðìèíû ¾ïåðåõîä¿ è ¾êîíôèãóðàöèÿ¿ áóäóòèñïîëüçîâàòüñÿ ïðèìåíèòåëüíî êî âñåé ðàñïðåäåëåííîéñèñòåìå â öåëîì,I Òåðìèíû ¾ñîáûòèå¿ è ¾ñîñòîÿíèå¿ , îáîçíà÷àþùèåðàâíîñèëüíûå ïîíÿòèÿ, áóäóò èñïîëüçîâàòüñÿ, åñëè ðå÷üèäåò î ïðîöåññàõ ñèñòåìû.Ìàòåìàòè÷åñêàÿ ìîäåëü.Ðàñïðåäåëåííàÿ ñèñòåìà ñîñòîèò èç ñîâîêóïíîñòè ïðîöåññîâ èêîììóíèêàöèîííîé ïîäñèñòåìû . Êàæäûé ïðîöåññ ÿâëÿåòñÿñèñòåìîé ïåðåõîäîâ, êîòîðàÿ ìîæåò âçàèìîäåéñòâîâàòü ñêîììóíèêàöèîííîé ïîäñèñòåìîé.
Ìû áóäåì ïðèäåðæèâàòüñÿñëåäóþùåãî ñîãëàøåíèÿ î òåðìèíîëîãèè:I Òåðìèíû ¾ïåðåõîä¿ è ¾êîíôèãóðàöèÿ¿ áóäóòèñïîëüçîâàòüñÿ ïðèìåíèòåëüíî êî âñåé ðàñïðåäåëåííîéñèñòåìå â öåëîì,I Òåðìèíû ¾ñîáûòèå¿ è ¾ñîñòîÿíèå¿ , îáîçíà÷àþùèåðàâíîñèëüíûå ïîíÿòèÿ, áóäóò èñïîëüçîâàòüñÿ, åñëè ðå÷üèäåò î ïðîöåññàõ ñèñòåìû.×òîáû âçàèìîäåéñòâîâàòü ñ êîììóíèêàöèîííîé ïîäñèñòåìîé, âðàñïîðÿæåíèè ïðîöåññà ïîìèìî âíóòðåííèõ ñîáûòèé ,èìåþòñÿ òàêæå ñîáûòèÿ îòïðàâëåíèÿ è ñîáûòèÿ ïðèåìà ,êîòîðûå ïîðîæäàþò èëè èçûìàþò ñîîáùåíèÿ èçêîììóíèêàöèîííîé ïîäñèñòåìû.Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéËîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéZ ýòî ìíîæåñòâî ñîñòîÿíèé ,Ëîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )IÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéZ ýòî ìíîæåñòâî ñîñòîÿíèé ,I ⊆ Z ýòî ïîäìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé ,Ëîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )IIÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéZ ýòî ìíîæåñòâî ñîñòîÿíèé ,I ⊆ Z ýòî ïîäìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé ,`i îòíîøåíèå âíóòðåííåãî äåéñòâèÿ íà ìíîæåñòâåZ ×Z,Ëîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )IIIÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéZ ýòî ìíîæåñòâî ñîñòîÿíèé ,I ⊆ Z ýòî ïîäìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé ,`i îòíîøåíèå âíóòðåííåãî äåéñòâèÿ íà ìíîæåñòâåZ ×Z,`s è `r îòíîøåíèÿ îòïðàâëåíèÿ è ïðèåìà ñîîáùåíèé íàìíîæåñòâå Z × M × Z .Ëîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )IIIIÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îáîçíà÷èì ñèìâîëîì M ìíîæåñòâî âñåõ âîçìîæíûõñîîáùåíèé ; çàïèñü M(M) áóäåò îáîçíà÷àòü ñîâîêóïíîñòüâñåõ ìóëüòèìíîæåñòâ ñ ýëåìåíòàìè èç M .Îïðåäåëåíèå 4.ïðîöåññà íàçûâàåòñÿ ïÿòåðêà, â êîòîðîéI Z ýòî ìíîæåñòâî ñîñòîÿíèé ,I I ⊆ Z ýòî ïîäìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé ,I `i îòíîøåíèå âíóòðåííåãî äåéñòâèÿ íà ìíîæåñòâåZ ×Z,I `s è `r îòíîøåíèÿ îòïðàâëåíèÿ è ïðèåìà ñîîáùåíèé íàìíîæåñòâå Z × M × Z .Äâóõìåñòíîå îòíîøåíèå ` íà ìíîæåñòâå Z îïðåäåëÿåòñÿñîîòíîøåíèåìËîêàëüíûì àëãîðèòìîìisr(Z , I , ` , ` , ` )c ` d ⇐⇒ (c, d) ∈ `i ∨ ∃m ∈ M : (c, m, d) ∈ `s ∪ `r .Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Ïðèìåð ëîêàëüíîãî àëãîðèòìà ïðîöåññàÏðîöåññ p1:var: x: bool;var M: bool;do foreverbegininput(x); M:=x;send(M)endÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Ïðèìåð ëîêàëüíîãî àëãîðèòìà ïðîöåññà'$Ïðîöåññ p1input(x);M:=xs11I`i`ssend(M)Rs12&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 5.äëÿ ñåìåéñòâà ïðîöåññîâáóäåò íàçûâàòüñÿ ñîâîêóïíîñòü ëîêàëüíûõàëãîðèòìîâ, êàæäûé èç êîòîðûõ ñîîòâåòñòâóåò â òî÷íîñòèîäíîìó ïðîöåññó èç P .Ðàñïðåäåëåííûì àëãîðèòìîìP = {p1 , .
. . , pN }Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 5.äëÿ ñåìåéñòâà ïðîöåññîâáóäåò íàçûâàòüñÿ ñîâîêóïíîñòü ëîêàëüíûõàëãîðèòìîâ, êàæäûé èç êîòîðûõ ñîîòâåòñòâóåò â òî÷íîñòèîäíîìó ïðîöåññó èç P .Ïîâåäåíèå ðàñïðåäåëåííîãî àëãîðèòìà îïèñûâàåòñÿïîñðåäñòâîì ñèñòåìû ïåðåõîäîâ ñëåäóþùåãî âèäà. Êàæäàÿêîíôèãóðàöèÿ ñèñòåìû îïðåäåëÿåòñÿ ñîñòîÿíèÿìè âñåõïðîöåññîâ, à òàêæå ñîâîêóïíîñòüþ ñîîáùåíèé, êîòîðûå åùå íåäîñòèãëè àäðåñàòîâ. Ïåðåõîäàìè ÿâëÿþòñÿ âñå ñîáûòèÿïðîöåññîâ, êîòîðûå èçìåíÿþò ñîñòîÿíèÿ ïðîöåññîâ, îêàçûâàþòâëèÿíèå íà ñîâîêóïíîñòü ñîîáùåíèé, èëè ïðåòåðïåâàþòâîçäåéñòâèÿ ýòîé ñîâîêóïíîñòè ñîîáùåíèé. Íà÷àëüíûìèêîíôèãóðàöèÿìè ñ÷èòàþòñÿ âñå òå êîíôèãóðàöèè, â êîòîðûõâñå ïðîöåññû ïðåáûâàþò â íà÷àëüíûõ ñîñòîÿíèÿõ, à ìíîæåñòâîñîîáùåíèé ïóñòî.Ðàñïðåäåëåííûì àëãîðèòìîìP = {p1 , .
. . , pN }Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) .iiiiiÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) .
Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:iiiiiÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) . Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . . .
, cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .iiii1iNÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) . Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . . . , cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .2. → = (∪p∈P →p ) , ãäå →p îáîçíà÷àåò ïåðåõîäû ïðîöåññà p ;ò. å. →p ýòî ìíîæåñòâî âñåõ ïàð âèäà(cp , .
. . , cp , . . . , cp , M1 ), (cp , . . . , cp0 , . . . , cp , M2 )äëÿ êîòîðûõ âûïîëíÿåòñÿ îäíî èç òðåõ óñëîâèé:iiiii1Ni1iN1iNÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) . Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . . . , cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .2.
→ = (∪p∈P →p ) , ãäå →p îáîçíà÷àåò ïåðåõîäû ïðîöåññà p ;ò. å. →p ýòî ìíîæåñòâî âñåõ ïàð âèäà(cp , . . . , cp , . . . , cp , M1 ), (cp , . . . , cp0 , . . . , cp , M2 )äëÿ êîòîðûõ âûïîëíÿåòñÿ îäíî èç òðåõ óñëîâèé:iiiii1Ni1Ii(cpi , cp0 i ) ∈ `ipiNèM1 = M2 ;1iNÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) .
Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . . . , cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .2. → = (∪p∈P →p ) , ãäå →p îáîçíà÷àåò ïåðåõîäû ïðîöåññà p ;ò. å. →p ýòî ìíîæåñòâî âñåõ ïàð âèäà(cp , . . . , cp , . . . , cp , M1 ), (cp , . . . , cp0 , . . .
, cp , M2 )äëÿ êîòîðûõ âûïîëíÿåòñÿ îäíî èç òðåõ óñëîâèé:iiiii1Ni1Ii(cpi , cp0 i ) ∈ `ipiNè1iNM1 = M2 ;I äëÿ íåêîòîðîãî ñîîáùåíèÿ(cpi , m, cp0 i ) ∈ `spim ∈ M èìååòñÿ ñîáûòèåM2 = M1 ∪ {m} ;, è ïðè ýòîìÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, . . . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) . Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . .
. , cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .2. → = (∪p∈P →p ) , ãäå →p îáîçíà÷àåò ïåðåõîäû ïðîöåññà p ;ò. å. →p ýòî ìíîæåñòâî âñåõ ïàð âèäà(cp , . . . , cp , . . . , cp , M1 ), (cp , . . . , cp0 , . . . , cp , M2 )äëÿ êîòîðûõ âûïîëíÿåòñÿ îäíî èç òðåõ óñëîâèé:iiiii1Ni1Ii(cpi , cp0 i ) ∈ `ipiNè1NM1 = M2 ;m ∈ M èìååòñÿ ñîáûòèåM2 = M1 ∪ {m} ;äëÿ íåêîòîðîãî ñîîáùåíèÿ m ∈ M èìååòñÿ ñîáûòèå(cpi , m, cp0 i ) ∈ `rpi , è ïðè ýòîì M1 = M2 ∪ {m} .I äëÿ íåêîòîðîãî ñîîáùåíèÿ(cpi , m, cp0 i ) ∈ `spiIi, è ïðè ýòîìÑèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Îïðåäåëåíèå 6.Ïóñòü çàäàíî ñåìåéñòâî ïðîöåññîâ P = {p1, .
. . , pN } , èëîêàëüíûé àëãîðèòì êàæäîãî ïðîöåññà pi ïðåäñòàâëåí ïÿòåðêîé(Zp , Ip , `ip , `sp , `rp ) . Òîãäà ñèñòåìà ïåðåõîäîâ àñèíõðîííîâçàèìîñâÿçàííûõ ïðîöåññîâ S = (C, →, I) òàêîâà:1. C = {(cp , . . . , cp , M) : (∀p ∈ P : cp ∈ Zp ) è M ∈ M(M)} .2. → = (∪p∈P →p ) , ãäå →p îáîçíà÷àåò ïåðåõîäû ïðîöåññà p ;ò. å. →p ýòî ìíîæåñòâî âñåõ ïàð âèäà(cp , . . . , cp , . . . , cp , M1 ), (cp , . . . , cp0 , . . . , cp , M2 )äëÿ êîòîðûõ âûïîëíÿåòñÿ îäíî èç òðåõ óñëîâèé:iiiii1Ni1Ii(cpi , cp0 i ) ∈ `ipiNè1iNM1 = M2 ;m ∈ M èìååòñÿ ñîáûòèåM2 = M1 ∪ {m} ;äëÿ íåêîòîðîãî ñîîáùåíèÿ m ∈ M èìååòñÿ ñîáûòèå(cpi , m, cp0 i ) ∈ `rpi , è ïðè ýòîì M1 = M2 ∪ {m} .I äëÿ íåêîòîðîãî ñîîáùåíèÿ(cpi , m, cp0 i ) ∈ `spiI3., è ïðè ýòîìI = {(cp1 , .
. . , cpN , M) : (∀p ∈ P : cp ∈ Ip ) ∧ M = ∅}.Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿÏàðû (c, d) ∈ `ip íàçîâåì âíóòðåííèìè ñîáûòèÿìèïðîöåññà p ,Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿÏàðû (c, d) ∈ `ip íàçîâåì âíóòðåííèìè ñîáûòèÿìèïðîöåññà p , à òðîéêè, èç êîòîðûõ ñîñòîÿò îòíîøåíèÿ `sp è `rp ,íàçîâåì ñîáûòèÿìè îòïðàâëåíèÿ è ïðèåìà .Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Çàìå÷àíèÿÏàðû (c, d) ∈ `ip íàçîâåì âíóòðåííèìè ñîáûòèÿìèïðîöåññà p , à òðîéêè, èç êîòîðûõ ñîñòîÿò îòíîøåíèÿ `sp è `rp ,íàçîâåì ñîáûòèÿìè îòïðàâëåíèÿ è ïðèåìà .Ïðèìåð ðàñïðåäåëåííîé ñèñòåìûÏðîöåññ p1:var: x: bool;var M: bool;Ïðîöåññ p2:var: y: bool;var m: bool;do foreverdo foreverbeginbeginendendinput(x); M:=x;send(M)receive(m);y:=m; output(y)Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s11 , s21 , ∅)'Ïðîöåññ p2s11s21I`sp1`ip1RI'$∅`rp&%Êîììóíèêàöèîííàÿ Rñèñòåìà-`ip22s12Rs22&$%&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s12 , s21 , ∅)'Ïðîöåññ p2s11s21IR∅`rp&%Êîììóíèêàöèîííàÿ Rñèñòåìà-s12`ip22Rs22&I'$`sp1`ip1$%&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1(s11 , s21 , {M})'Ïðîöåññ p2s11s21IRM`rp&%Êîììóíèêàöèîííàÿ Rñèñòåìà-s12`ip22Rs22&I'$`sp1`ip1$%&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1'Ïðîöåññ p2(s11 , s22 , ∅)s11s21I`sp1`ip1RI'$∅`rp&%Êîììóíèêàöèîííàÿ Rñèñòåìà-`ip22s12Rs22&$%&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.'$Êîíôèãóðàöèÿ:Ïðîöåññ p1'Ïðîöåññ p2(s11 , s21 , ∅)s11s21I`sp1`ip1RI'$∅`rp&%Êîììóíèêàöèîííàÿ Rñèñòåìà-`ip22s12Rs22&$%&%Ñèñòåìû ñ àñèíõðîííîé ñâÿçüþ.Âîïðîñû1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
