Articolo pubblicato sul n. 108 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel giugno 1991

Multitasking:
Il modello CSP

di Andrea de Prisco

CSP sta per Communicating Sequential Process e rappresenta un modello per esprimere la semantica della comunicazione inter process "a nomi espliciti dei moduli" vista lo scorso mese su queste stesse pagine. Vedremo, questo mese, anche alcuni esempi di programmazione multitasking utilizzando appunto il modello CSP. Parleremo dunque di processi, porte, messaggi e del controllo del non determinismo.

Processi Sequenziali

La 'S' di CSP sta appunto per "Sequenzial". Ma non avevamo a che fare con processi "paralleli" ? Sembra che ci sia una bella fregatura, sotto, ma non e' vero. Infatti ogni processo e', in se', sequenziale; ma tanti processi sequenziali eseguiti insieme formano una applicazione parallela. Detto in altre parole ogni processo e' formato da una "sequenza" di istruzioni da eseguire rigorosamente l'una dopo l'altra, ma piu' processi possono essere eseguiti "parallelamente" e sono tra loro in grado di comunicare (non sottovalutate la 'C' di "CSP").
Ora, non e' per stravolgervi immediatamente le idee, sappiate che la "sequenzialita' di un processo CSP e' a livello di processo ma non di istruzioni. Ovvero un processo e' formato da una sequenza di istruzioni, ma queste possono essere al loro interno "parallele".
Il caso limite e' del processo CSP che e' formato da un solo comando parallelo: nel momento in cui il processo parte, tutte le istruzioni che compongono il comando parallelo sono eseguite contempora-neamente. Quindi la sequenzialita' dei processi CSP e' piu' a livello semantico che non nella pratica.

Send e Receive

Nel modello CSP i comandi di Send e Receive per inviare e ricevere messaggi hanno la seguente sintassi:

NomeProcesso! Messaggio

corrisponde a Send(NomeProcesso,Messaggio) mentre:

NomeProcesso?Variabile

corrisponde a Receive(NomeProcesso,Variabile). In pratica, a distinguere il comando di Send da quello di Receive e' solo il segno di interpunzione tra i due parametri che nel primo caso e' un punto esclamativo, nel secondo un punto interrogativo. In figura 1 trovate un esempio di comunicazione tra due processi CSP: il processo mittente invia 100 valori al processo destinatario che provvede a stamparli; la sequenza di valori termina con l'invio della costante 0 (zero) da parte di A che viene riconosciuta da B come marcatore di fine flusso.
La comunicazione, in questo modello, e' simmetrica, sincrona. Ovvero avviene sempre solo tra due partner (un mittente e un destinatario) e l'istante logico in cui l'operazione e' completata e' lo stesso per tutt'e due. Se il mittente o il destinatario arriva in anticipo all'appuntamento per lo scambio messaggio, attendera' il proprio partner prima completare l'operarazione e di procedere con l'istruzione successiva.
Se il partner di una comunicazione (sia questo il mittente oppure il destinatario) termina prima di aver portato a termine la stessa, il comando di I/O fallisce facendo terminare con fallimento anche il processo in attesa. Se ad esempio, tornando nuovamente alla figura 1, a causa di un errore dell'istruzione "write" del processo B questo termina prima di aver ricevuto e stampato tutti i messaggi inviati da A, anche il mittente termina (con fallimento) nel momento in cui tenta di eseguire la send col partner ormai non piu' in esecuzione.

Controllo del nondeterminismo

Sul numero scorso abbiamo anticipato il problema del controllo del nondeterminismo. Ovvero come pilotare adeguatamente le scelte del sistema davanti a situazioni non definibili a priori e riguardanti la comunicazione tra un processo destinatario e molti processi mittenti attraverso altrettanti canali di comunicazione.
Nel modello CSP esistono le cosiddette "guardie" che sono generalmente composte da due componenti: una espressione booleana e un comando di ingresso (una receive). Una guardia puo' anche essere composta da solo una delle due componenti: se il comando di ingresso e' presente la guardia e' detta "guardia di ingresso".
Le guardie sono utilizzate, come vedremo meglio in seguito, in due tipi di comandi: il comando alternativo e il comando ripetitivo. Il primo serve per effettuare un'unica scelta tra un certo numero di possibilita' e poi proseguire nell'elaborazione; il secondo serve per eseguire un loop sulle alternative che ciclo dopo ciclo evolveranno in maniera diversa. Ma per il momento ritorniamo sulle nostre guardie.
Una guardia d'ingresso, dicevamo, e' formata da una coppia "espressione booleana - comando d'ingresso". Essa puo' trovarsi in uno solo dei seguenti tre stati: sospesa, fallita, verificata.
Una guardia e' sospesa quando l'espressione booleana e' vera (o al piu' assente) e il comando d'ingresso attende la comunicazione da parte del partner tuttora in esecuzione (non terminato).
Una guardia e' fallita se l'espressione booleana e' falsa oppure il processo partner indicato nel comando d'ingresso e' terminato.
Una guarda si dice verificata se l'epressione boolena e' vera (o assente) e il mittente indicato ha tentato la comunicazione con noi.
Ad ogni guardia e' associata, sia nel caso del comando alternativo che in quello ripetitivo, una lista di comandi da eseguire in seguito alla scelta da parte del sistema di quella determinata guardia verificata. In pratica il controllo del non determinismo avviene indicando una lista di guardie e una corrispondente serie di liste di comandi da eseguire.
La sintassi del comando alternativo e' questa:

[ G1 -> LC1
[] G2 -> LC2
:
:
[]Gn -> LCn];

dove le varie Gx rappresentano le guardie e LCx le liste di comandi ad esse associate. Facciamo un primo esempio: il processo B riceve messaggi dai processi A1, A2, A3. Questo che segue e' un pezzo di codice CSP per eseguire comandi diversi a seconda del mittente del messaggio ricevuto, senza ulteriore filtro da parte di espressioni booleane.

B::

var msg: integer;

begin
[ A1?msg -> write("ricevo da A1")
[] A2?msg -> write("ricevo da A2")
[] A3?msg -> write("ricevo da A3")
];
end.

l'effetto e' quello di stampare la stringa corrispondente al processo che ha inviato il messaggio. La domanda da porsi, a questo punto, e' sicuramente questa: Cosa succede nel caso in cui nessun mittente sta spedendo messaggi oppure che tutti i mittenti sono terminati o, ancora, che piu' d'un mittente contemporaneamente invia messaggi a B ? E' il caso, per l'appunto, delle guardie tutte sospese, tutte fallite o con piu' d'una guardia verificata. Nel primo caso il processo destinatario semplicemente rimane in attesa che l'attuale situazione di "tutte le guardie sospese" evolga in una delle due possibili ulteriori alternative. Nel caso di guardie tutte fallite, il comando alternativc fallisce e quindi il processo destinatario, conseguentemente, termina anch'esso con fallimento. Il terzo caso, il piu' interessante, e' quello della contemporanea verifica di piu' guardie: in questo caso sara' il sistema a scegliere il comando di ingresso da eseguire e conseguentemente la lista di comandi corrispondente. Da segnalare il fatto che non e' possibile per il processo destinatario (che ha eseguito il comando alternativo) forzare in alcun modo la scelta che spetta di diritto a sistema.
L'unico modo e' quello di utilizzare guardie con espressioni booleane in modo da limitare (al limite ad una sola) le guardie verificabili, fatto salvo pero' il fatto che comunque se ci sono piu' guardie verificata anche aggiungendo le espressioni booleane tocchera' comunque al sistema sceglierne una. Proviamo, nell'esempio appena visto, ad aggiungere anche tre espressioni booleane: tre variabili di tipo bool opportunamente inizializzate.

B::

var msg: integer;
var a1,a2,a3: bool;

begin
a1:= TRUE;
a2:= FALSE;
a3:= TRUE;

[ a1,A1?msg -> write("ricevo da A1")
[] a2,A2?msg -> write("ricevo da A2")
[] a3,A3?msg -> write("ricevo da A3")
];
end.

la seconda guardia "a2,A2?msg" e' fallita (in partenza) valendo FALSE la sua espressione booleana. Dunque sono in gioco solo la prima e la terza guardia. Se avessimo voluto forzare la scelta su un determinato mittente sarebbe bastato porre a TRUE una sola delle tre espressioni booleane. E' chiaro che tutto ha un senso proprio perche' queste espressioni sono pilotabili a tempo di esecuzione, in funzione dello stato interno del processo destinatario.
Dal comando alternativo si esce, dunque, quando almeno una guardia si verifica e, conseguentemente, un comando di ingresso con relativa lista comandi sono eseguiti.
Il comando ripetitivo, dal canto suo, ha una sintassi pressoche' identica a quella del comando alternattivo. L'unica differenza consiste in un asterisco posto all'inizio del comando:

*[ G1 -> LC1
[] G2 -> LC2
:
:
[]Gn -> LCn];

Ben diversa e', invece, la semantica: il comando ripetitivo non viene eseguito una sola volta ma e' continuamente rieseguito fino a quando tutte le guardie non sono fallite. E di solito e' usato proprio per eseguire loop "principali", come nell'esempio di un processo buffer mostrato in figura XX. Il programma CSP che descrive quel processo buffer e' quantomai semplice: si tratta infatti di un buffer ad un solo ingresso ed una sola uscita dove quindi accede un solo processo produttore e un solo processo consumatore. Il buffer vero e' proprio e' contenuto nel processo stesso, sottoforma di un array ad 'n' posizioni. Per semplicita' supponiamo che i dati inviati e prelevati dal buffer siano dei normalissimi interi. Proviamo a scrivere il (semplicissimo) codice:

BUFFER::

var buffer: array[0..255] of integer;
var in, out, tot, tmp : integer;

begin
in := 0;
out := 0;
tot := 0;

*[ tot<256,A?buffer[index]
-> in := (in+1) AND 255;
tot := tot + 1;
[] tot>0,B?tmp
-> B!buffer[out];
out := (out+1) AND 255;
tot := tot - 1;

];
end.

Questo esempio dovrebbe chiarire anche eventuali lacune sul funzionamento delle guardie e del comando ripetitivo. Commentiamolo un po'. Anzi, prima di descrivere il comportamento interno del processo buffer vediamo cosa succede all'esterno. Il processo 'A' (produttore) per inserire i suoi output nel buffer non fa altro che inviare a questo il valore da inserire. In pratica effettua una semplice 'send' sul processo buffer, diciamo cosi':

BUFFER!valore;

il processo 'B' (consumatore) non puo' effettuare direttamente una 'receive' per prelevare i dati dal buffer ma ne effettua richiesta inviando un messaggio di sincronizzazione che ha il solo scopo di comandare al buffer di spedirgli il prossimo valore. In pratica per ricevere il dato 'B' eseguira' la seguente coppia di istruzioni:

BUFFER!dummy;
BUFFER?valore;

dove 'dummy' e' una costante qualsiasi di tipo intero e 'valore' e una variabile targa, sempre di tipo intero, nella quale al termine del comando di ingresso trovera' il valore letto nel buffer. Detto questo la descrizione del processo buffer e' semplicissima: in pratica nel loop indotto dal comando ripetitivo il processo buffer riceve solo richieste di inserimento se il contatore 'tot' (che contiene costantemente il numero di elementi presenti nella coda) e' nullo, solo richieste di estrazione se il contatore e' al suo massimo, 256, di inserimento o di estrazione per valori intermedi. Il tutto "automaticamente regolato" dalle guardie che dinamicamente falliscono, si verificano o sono sospese, a seconda dello stato del buffer e dell'attivita' dei processi produttore e consumatore. Le variabili 'in' e 'out' contengono rispettivamente la posizione di inserimento ed estrazione nel buffer e sono incrementate di volta in volta modulo 255 trattandosi di un buffer circolare. Il comando ripetitivo termina quando tutt'e due le guardie falliscono: non essendo possibile cio' a causa dell'espressione logica (non e' possibile che 'tot' sia contemporaneamente superiore di 255 e inferiore di 1) questa situazione si potra' verificarsi solo in caso di terminazione di almeno uno dei due processi partner e relativo riempimento o completo svuotamento della coda. Cosa che e', evidentemente, piu' che giusta: a che servirebbe mai un buffer conpletamente pieno al quale nessuno accede piu' per svuotarlo oppure un buffer completamente vuoto nel quale nessuno mai inserira' piu' nulla ?

Comando Parallelo

Per finire questa puntata di Multitasking diamo uno sguardo anche al comando parallelo citato all'inizio dell'articolo. Si usa per lanciare in parallelo processi figli: in pratica un processo puo' ad un certo punto lanciare altri processi e continuare la sua esecuzione quando tutti i processi da esso creati sono terminati. Il comando parallelo, infatti, e' un comando come gli altri e dunque l'esecuzione delle istruzioni seguenti puo' avvenire solo a terminazione del comando corrente. La sintassi e' simile a quella dei comandi visti prima, ovviamente non sono presenti guardie:

ProcessoPadre::

[ ProcessoFiglio1
||ProcessoFiglio2
:
:
|| ProcessoFiglioN];

In pratica quando viene incontrato nel processo padre un comando parallelo, l'esecuzione di questa viene sospesa ed inizia quella di tutti i processi figli, in parallelo. Questi sono essi stessi processi a tutti gli effetti e possono creare a loro volta altri figli e/o comunicare tra loro. La relazione di "parentela" col padre permette loro di sostituirsi come mittenti o destinatari di comunicazioni senza che i processi "esterni" si accorgano di cio'. Se al termine di tutti i processi figli (subordinata a loro volta dalla terminazione di eventuali processi nipoti) nessun processo e' fallito il processo padre puo' continuare la sua esecuzione "sequenziale". Nel caso, invece, che uno o piu' processi figli termini con fallimento esistono due possibilita': la prima produce il fallimento anche del processo padre (e quindi il fallimento si propaga) la seconda prevede una lista di comandi per la gestione dell'eccezione.

Conclusione

Dal prossimo numero lasceremo da parte tutti gli sforzi "teorici" per dedicarci piu' da vicino agli aspetti "pratici". Non e' escluso che vi coinvolgeremo anche con quiz e domande su problemi inerenti la programmazione parallela. Il nostro cavallo di battaglia sara' comunque l'OCCAM, il linguaggio di programmazione dei transputer, con il quale vi mostreremo perfino la "magia" del calcolo parallelo. Speriamo solo di non stufarvi tanto presto: le cose da vedere sono ancora tante e, secondo noi, sempre piu' interessanti. Arrivederci.

Impaginato originale...

Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui