Procesų algebra

Lygiagretus komponavimas

Lygiagretaus komponavimo metu yra atliekami du procesai \mathit{P} ir \mathit{Q}, kurie paprastai užrašomi kaip P \vert Q, tai yra primityvus proceso skaičiavimų atskyrimas nuo nuoseklių apskaičiavimo modelių. Lygiagretus komponavimas leidžia atlikti skaičiavimus naudojant \mathit{P} ir \mathit{Q}, kad būtų galima dirbti vienu metu ir atskirai. Bet tai taip pat leidžia sukurti sąveiką, kuri sukuria informacijos ir \mathit{P} į \mathit{Q} sinchronizaciją ir tekėjimą. O svarbiausia, priemonė arba procesas gali būti sujungtas su daugiua nei vienu kanalu vienu metu.
Kanalai gali būti sinchroniški arba nesinchroniški. Kai yra kalbama apie sinchroniškus kanalus, priemonė, kuri siunčia pranešimą, palaukia, kol kita priemonė gaus pranešimą. Nesinchroniškiems kanalams nereikia tokios sinchronizacijos. Atliekant kai kuriuos proceso skaičiavimus (π skaičiavimas), kanalai patys gali būti nusiunčiami pranešimų forma per (kitus) kanalus, tokiu būdu yra galima pakeisti proceso susijungimo topologiją. Kai kurie proceso skaičiavimai taip pat gali būti sukuriami apskaičiavimo metu.

Bendravimas

Sąveika gali būti (bet ne visada būna) nukreiptu informacijos srautu. Tai yra, įvestis ir išvestis gali būti atskiriamos, kaip dvigubi sąveikos baziniai elementai. Proceso skaičiavimas, kuris leidžia atlikti tokį atskyrimą, paprastai apibrėžia įvesties operatorių (pvz., x (v)) ir išvesties operatorių (pvz., x(y)), jie abu įvardina sąveikos tašką (čia x), kuris yra naudojamas norint atlikti sinchronizaciją, naudojant dvigubą sąveikos bazinį elementą. Jei norima pakeisti informaciją, ji tekės išvesties proceso metu, kuris pereina į įvesties procesą. Išvesties bazinis elementas patvirtins, kurie duomenys turi būti siunčiami. x(y) tokie duomenys žymimi y. Panašiai yra, jei įvestyje norima gauti duomenis, tada vienas arba daugiau kintamųjų veiks kaip laikikliai, kurie turi būti pakeičiami duomenimis, kai duomenys ateis. x(v) raidė v atlieką šią funkciją. Duomenų, kuriuos norima sukeisti sąveikoje, pasirinkimas yra viena iš esminių savybių, kurios išskiria skirtingus procesų skaičiavimus.

Eilių kompozicija

Kartais sąveikos turi būti laikinai atliekamos. Pvz., galima patvirtinti tokius algoritmus: pirmiausia reikia gauti dalį duomenų į x ir nusiųsti duomenis į y. Nuoseklus komponavimas gali būti naudojamas tokiu tikslu. Jis yra gerai žinomas iš kitų apskaičiavimo modelių. Atliekant proceso skaičiavimą išdėstymo nuosekliai operatorius yra paprastai integruojamas su įvestimi ir išvestimi, arba abiem. Pvz., procesas x(v) .P palauks įvesties x. Tik kai ši įvestis pasirodys, procesas P bus aktyvuotas, o gauti duomenys per x bus pakeisti į vardą v.

Slėpimas

Procesai neriboja jungčių, kurias galima atlikti konkrečiame sąveikos taške, skaičiaus. Tačiau sąveikos taškai lemia tam tikrus trukdžius (pvz., sąveika). Kalbant apie kompaktiškumo sintezę, kai kalbama apie minimalias ir sudėtines sistemas, galimybė riboti trukdžius, yra labai svarbi. Slėpimo operacijos leidžia kontroliuoti jungtis, kurios padaromos tarp sąveikos taškų, kai sudedamosios priemonės yra naudojamos lygiagrečiai. Slėpimas gali būti žymimas įvairiais būdais. Pvz., π skaičiavime x slėpimas P gali būti išreikštas kaip (vx) P, kai CSP gali būti užrašomas kaip P\ {x}.

Negaliojantys (Null) procesai

Proceso skaičiavimai apskritai taip pat apima ir negaliojantį "null procesą" (įvairiai žymimas kaip \mathit{nil}, 0, \mathit{STOP}, \delta, arba kokiu nors kitu atitinkamu simboliu), kuris neturi jokių sąveikos punktų. Jis yra absoliučiai neaktyvus ir jo vienintelė paskirtis yra veikti kaip indukcinis inkaras, virš kurio gali būti vykdomi daug įdomesni procesai.

Atskira ir nuolatinė proceso algebra

Proceso algebra buvo studijuota diskretiniam laikui ir nuolatinis laikas (realus laikas ar tankus laikas).

Istorija

Pirmojoje XX amžiaus pusėje buvo bandoma naudoti įvairius formalizmus, kad būtų galima žymėti neformalią sąvoką skaičiuojamoji funkcija, reiškiančią µ-grįžtamąsias funkcijas, Turingo mašinas ir lambda skaičiavimą, visa tai yra geriausiai žinomi pavyzdžiai šiandien. Stebėtinas faktas, kad šie pavyzdžiai iš esmės yra lygūs, nes jie gali būti įtraukiami vienas į kitą, jie palaiko Church-Turing tezę. Kita visiems bendra savybė yra rečiau aptariama: jie visi yra geriausiai suprantami kaip nuoseklaus apskaičiavimo modeliai, ypač tiksliai jie išreiškia konkurenciją ir komunikaciją. Konkuravimo modeliai, kaip tarkim proceso skaičiavimas, Petri-Nets 1962 m. ir Aktoriaus modelis 1973 m. buvo išvesti iš šio tipo informacijos. Tyrimai proceso skaičiavimo tema buvo pradėti Robin Milner pradiniame darbe Komunikacinių sistemų skaičiavimas (CCS) per laikotarpį tarp 1973 ir 1980 m. A. A. R. Hoare darbas Komunikaciniai nuoseklūs procesai (CSP) pirmą kartą pasirodė 1978 m. ir buvo toliau išplėtotas į pilną procesų skaičiavimą devintojo dešimtmečio pradžioje. Čia buvo matomas idėjų supliekimas tarp CCS ir CSP, kol jie buvo vystomi. 1982 m. Jan Bergstra ir Jan Willem Klop pradėjo dirbti prie to, kas tapo žinoma kaip Komunikacinių procesų algebra (ACP), ir iš čia kilo terminas proceso algebra, kuris išreiškė jų darbą. CCS, CSP ir ACP sudaro tris pagrindines proceso skaičiavimo šeimos šakas: didžioji dalis proceso skaičiavimo gali būti grindžiamas šiais trimis skaičiavimais.

Santykis su kitais panašiai modeliais

Istorinis monoidas yra laisvas objektas, kuris leidžia bendrai išreikšti atskirų komunikacinių procesų istorijas. Proceso skaičiavimas tada yra žinomas, kaip formali kalba, kuri buvo nuosekliai primesta istoriniam monoidui. Tai yra, istorinis monoidas gali fiksuoti įvykių seką, ją sinchronizuojant, bet negali pagrįsti galimos būsenos perdavimo. Taigi, proceso skaičiavimas yra istorinis monoidas, kurį formali kalba išreiškia kaip laisvą monoidą (formali kalba yra visų galimų riboto ilgio alfabeto stygų pogrupis, kurį sukūrė Kleene star). Komunikacijos kanalų naudojimas yra viena iš savybių, kuri atskiria proceso skaičiavimą nuo kitų konkuravimo modelių, kaip tarkim Petri nets ir Actor modelis (žiūrėkite Actor modelį ir proceso skaičiavimą). Viena iš esminių motyvacijų, kuri leidžia į procesą įtraukti kanalus, buvo galimybė panaudoti tam tikras algebros technikas, tokiu būdu suteikiant galimybę lengviau pagrįsti procesus iš algebros pusės.