Vuorovaikutteisten järjestelmien laskenta
Tietojenkäsittelytieteen laskentajärjestelmä ( CCS ) on Robin Milnerin vuonna 1980 kehittämä prosessilaskenta . _ _ Laskenta toimii mallin kanssa erottamattomasta kommunikaatiosta täsmälleen kahden osallistujan välillä. Formaalikieli sisältää primitiivit kuvaamaan rinnakkaista koostumusta, valintoja toimien välillä ja rajoituskehyksiä. CCS on hyödyllinen ominaisuuksien, kuten mutexin tai " livelockin " [1] , laadullisen oikeellisuuden arvioinnissa .
Milnerin mukaan "peruskombinaattoreiden valinnassa ei ole mitään kanonista, vaikka ne onkin valittu taloudellisuutta huolella. Laskellemme ei ole ominaista tarkka kombinaattorien valinta, vaan tulkinnan ja matemaattisen rakenteen valinta .
Kielilausekkeet tulkitaan leimatuksi transitiiviseksi järjestelmäksi . Näiden mallien välillä keskinäistä samankaltaisuutta käytetään semanttisena ekvivalenssina.
Syntaksi
Tietylle toimintonimijoukolle CCS-prosessien joukko määritellään seuraavalla Backus-Naur-kieliopilla :
![{\displaystyle P::=\emptyset \,\,\,|\,\,\,a.P_{1}\,\,\,|\,\,\,A\,\,\,|\ ,\,\,P_{1}+P_{2}\,\,\,|\,\,\,P_{1}|P_{2}\,\,\,|\,\,\,P_ {1}[b/a]\,\,\,|\,\,\,P_{1}{\kenoviiva }a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ead99e00ed96fff0df7c972472973159922c998)
Syntaksin osat yllä annetussa järjestyksessä:
tyhjä prosessi tyhjä prosessi on kelvollinen CCS-prosessi toiminta prosessi voi tehdä toiminnan ja jatkaa prosessina prosessin tunnus kirjoittaa käyttääksesi id :tä viitataksesi prosessiin valinta prosessi voi jatkua joko muodossa , tai muodossa rinnakkainen koostumus prosessit ja jotka ovat olemassa samanaikaisesti uudelleennimeäminen prosessi , jossa toimintoja on nimetty uudelleen rajoitus prosessi ilman toimenpiteitä
![{\displaystyle P_{1}[b/a]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3845d90265f5e16fb07f1cec4e9d827838f4dad)
Aiheeseen liittyvät laskelmat ja mallit
- Vuorovaikutteisten prosessien laskenta ( eng. Communicating Sequential Processes ), CSP on Anthony Hoaren kehittämä kieli , joka ilmestyi samaan aikaan kuin CCS.
- Milnerin 1980-luvun lopulla kehittämä Pi-calculus tarjoaa liikkuvuutta viestintäyhteyksille sallimalla prosessien raportoida itse viestintäkanavien nimet.
- Jane Hillstonin kehittämä PEPA - prosessialgebra esittelee toiminta-ajan ja todennäköisyyspohjaisen valinnan, mikä mahdollistaa suorituskykymittareiden laskemisen.
Jotkut CCS:ään perustuvat merkinnät:
Mallit, joita käytetään CCS-järjestelmien tutkimuksessa:
- Historian monoidi ;_ _
- Näyttelijä malli .
Linkit
- Robin Milner: A Calculus of Communicating Systems , Springer Verlag, ISBN 0-387-10235-3 . 1980.
- Robin Milner, Communication and Concurrency , Prentice Hall, International Series in Computer Science, ISBN 0-13-115007-3 . 1989
- ↑ Suurten tila-avaruuksien torjunta suorituskyvyn mallintamisessa // Suorituskyvyn arvioinnin muodolliset menetelmät / Herzog, Ulrich. - Springer, 2007. - Voi. 4486. - s. 318-370. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-540-72522-0 .