Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 18.Calculus of Communicating Systems (CCS)


Overview

  • Introduzione al CCS
  • Analogie tra CSP e CCS
  • Significato di concorrenza
  • Cenni al CSP
  • I processi CCS
  • Operazioni e azioni del CCS
  • Sintassi e semantica del CCS
  • Cenni al CCS puro
  • Cenni al π-calcolo
  • Conclusioni

CCS: un’introduzione

  • Il CCS (Calculus of Communicating System), fu introdotto da Robin Milner intorno al 1980.
  • Il CCS ha avuto un forte impatto sullo studio teorico del parallelismo.
  • Il CCS, insieme al CSP ed a IMPGC, fa parte dei modelli di comunicazione tra sistemi che condividono variabili.
  • Il linguaggio formale CCS è dotato di primitive per la descrizione della composizione parallela, scelte tra azioni e restrizioni di ambito.
Robin Milner

Robin Milner


CSP e CCS

  • Il CSP (Communicating Sequential Process), fu introdotto da Tony Hoare, nella seconda metà degli anni ‘70, contemporaneamente al CCS, ma in maniera indipendente.
  • Ciò che CSP e CCS hanno in comune è dovuto al fatto che sia Hoare (CSP), che Milner (CCS), individuarono un’azione atomica di sincronizzazione, con possibilità di scambio di valori, come la primitiva essenziale per la comunicazione (indipendente dal mezzo usato per la comunicazione).

Concorrenza (o parallelismo)

  • In informatica, per concorrenza si intende la condivisione di risorse tra più computazioni che vengono eseguite sovrapposte nel tempo.
  • L’efficienza della concorrenza risulta essere strettamente legata alle tecniche utilizzate per:
    • coordinare l’esecuzione delle computazioni;
    • scambiare i dati;
    • allocare memoria;
    • schedulare i processi.
  • Esempi di sistemi concorrenti sono i “sistemi operativi”, che sono progettati per operare, in teoria, all’infinito, senza la possibilità di terminare in modo inatteso.
  • I sistemi concorrenti sono, ovviamente, non-deterministici.

Uno sguardo al CSP

  • Il CSP, a differenza di IMPGC, prevede delle primitive di comunicazione (IPC) tra processi (o threads):
    • per quanto riguarda i processi, la comunicazione avviene mediante lo scambio di messaggi;
    • per quanto riguarda i threads, è prevista la possibilità di utilizzare memoria condivisa.
  • Lo scambio dei messaggi avviene tramite canali, che permettono:
    • scambio di valori tra i processi;
    • sincronizzazione dei processi.
  • Il numero dei canali è fisso.

Rappresentazione dei processi CCS

  • Un processo CCS comunica con il suo ambiente attraverso i canali connessi alle sue porte, proprio come avviene con CSP.
  • Un processo p, disposto ad eseguire un input dai canali α e β e un output sui canali α e γ può essere visualizzato come indicato in figura, con le sue porte etichettate nel modo opportuno.

Operazione di restrizione sui processi CCS

  • La composizione parallela di p con q, un processo che sia disposto ad eseguire un input da α e un output su β e δ, può essa stessa essere vista come un processo p||q, con porte α?, α!, β?, β!, γ!, γ!.
  • L’operazione di restrizione nasconde un determinato insieme di porte.
  • Ad esempio, effettuando una restrizione sulle porte specificato dall’insieme di etichette {α, γ} del processo p, si ottiene un processo p{α γ} disposto solamente ad eseguire input sul canale β. La rappresentazione del processo p sarà quindi differente dalla precedente:
Il processo p prima dell’operazione di restrizione.

Il processo p prima dell'operazione di restrizione.

Il processo p dopo l’operazione di restrizione.

Il processo p dopo l'operazione di restrizione.


Ridenominazione dei canali

  • Spesso può risultare utile generare più copie di uno stesso processo, ridenominando, però, alcuni canali.
  • Una funzione di ridenominazione è una funzione sui nomi dei canali.
  • Dopo essere stato dalla funzione f, con f(α)= γ, f(β)=δ e f(γ)=γ, il processo p diventa il processo p[f].
Il processo p prima della ridenominazione.

Il processo p prima della ridenominazione.

Il processo p dopo la ridenominazione.

Il processo p dopo la ridenominazione.


CCS: sintassi (1)

  • In aggiunta alle comunicazioni α?n e α!n sul canale α esiste un’altra azione τ che può:
    • svolgere il ruolo del comando skip;
    • rappresentare azioni di comunicazione interna.
  • Siccome i normali assegnamenti sono stati eliminati, gli stati σ, utilizzati in tutti i linguaggi esaminati in precedenza (IMP, IMPP, IMPGC e CSP), non sono più necessari: è possibile, dunque, utilizzare le variabili x, y, … in luogo delle locazioni.
  • I processi vengono indicati con gli identificatori di processo P,Q,…, che permettono di definire il comportamento ricorsivo di questi.
  • Si definisce una sintassi per le espressioni aritmetiche a e per le espressioni booleane b, con le variabili al posto delle locazioni.

CCS: sintassi (2)

La sintassi dei processi p, p0,p1,… è quella indicata in figura.

dove:

  • a e b sono rispettivamente espressioni aritmetiche e booleane;
  • x è una variabile che indica un generico valore;
  • L è un sottoinsieme dei nomi di canale;
  • f è una funzione di ridenominazione;
  • P sta per un processo con parametri a1, …, ak (quando la lista dei parametri è vuota si scrive solo P).

CCS: sintassi (3)

  •  Formalmente, α?x→p è come una lambda astrazione su x, ed ogni occorrenza della variabile x in p è legata da α?x, a condizione che tali variabili non siano presenti in sottotermini della forma β?x→q:
    • le variabili che non sono in questo senso legate vengono dette libere.
  • Agli identificatori di processo P sono associate definizioni, scritte come indicato in figura; dove tutte le variabili libere di p compaiono nella lista x1, …, xk di variabili distinte.
  • Il comportamento di un processo viene determinato dalle definizioni associate agli identificatori di processo che esso contiene.

CCS: semantica

Di seguito viene utilizzato λ che assume valori nell’insieme delle azioni α?n, α!n e τ.


Cenni sul CCS puro

  • Alla base del lavoro di Milner, c’è un calcolo ancora più fondamentale, che prende il nome di CCS puro.
  • Il CCS puro si ottiene eliminando le variabili dal CCS, ed assumendo che i valori comunicati durante le sincronizzazioni siano numeri:
    • nel CCS puro il ruolo dei valori può essere svolto dai nomi delle porte: questo significa che l’input del valore n sulla porta α, ossiaα?n, viene visto come una pura sincronizzazione, senza alcuno scambio di valori.
  • Nel CCS puro le azioni possono avere tre tipi di nomi:
    • le azioni ℓ, corrispondenti alle azioni α?n e α!n;
    • le azioni complementari ℓ-, corrispondenti al fatto che α?n è complementare a α!n, e viceversa;
    • le azioni interne τ.

Dal CCS al π-calcolo

  • Il punto di forza del CCS è nel contempo il suo punto debole:
    • in concorrenza spesso si vorrebbe avere la possibilità di effettuare comunicazioni, cioè scambi di messaggi, tra processi.
  • Un nuovo concetto importante che si vorrebbe poter gestire è pertanto lo scambio di informazioni.
  • Un messaggio, ossia l’oggetto della comunicazione, può essere definito come un elemento di un certo tipo di dato:
    • nel caso del CCS, l’aspetto principale di un messaggio è il suo valore;
    • nel caso del π-calcolo, invece, l’aspetto su cui ci si sofferma sono le funzionalità che il messaggio conferisce al ricevente.

Cenni sul π-calcolo

  • L’idea fondamentale del π-calcolo è che i processi si scambiano tra loro messaggi che portano delle funzionalità:
    • nel CCS la computazione è essenzialmente una serie di sincronizzazioni tra processi;
    • nel π-calcolo una computazione è una sequenza di comunicazioni su canali.
  • Una funzionalità è la possibilità di fare una comunicazione che prima non era possibile, magari perché non si conosceva il canale:
    • il risultato è che i canali sono allo stesso tempo il mezzo di comunicazione e l’oggetto della comunicazione stessa.

Conclusioni

  • In definitiva è possibile affermare che CSP e CCS, benché definiti indipendentemente, e con una formulazione leggermente differente, hanno molti punti in comune, in quanto condividono:
    • le stesse primitive di comunicazione;
    • lo stesso set di azioni base: il CCS, come abbiamo visto, ne definisce anche altre.
  • Il CCS di Milner, si ispira ad un altro linguaggio, il CCS puro:
    • la differenza sostanziale sta nel fatto che in quest’ultimo non ci sia uno scambio di variabili, ma di numeri (o valori in generale)
  • Successivamente il CCS è stato anche esteso da altri linguaggi, tra i quali il π-calcolo:
    • l’esigenza di quest’ultimo era quella di estendere il significato di messaggio: i messaggi non vengono solo visti come lo strumento per scambiarsi solo dei valori, ma anche funzionalità.
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion