Interazioni tra processi e primitiva Join

Interazioni tra processi e primitiva Join

Le interazioni tra processi sono di 3 tipi: competizione, cooperazione (o concorrenza) e interferenza. Il SO deve prevedere meccanismi in grado di risolvere la competizione, che è una forma di interazione indesiderata ma prevedibile quando si usano risorse comuni: il SO si fa carico di gestire la sincronizzazione implicita tra processi che intendono utilizzare risorse da esso direttamente gestite e mette a disposizione meccanismi di sincronizzazione implicita dei processi che usano risorse gestite a livello applicazione (un modo banale di procedere può essere il rendere invisibile la risorsa a tutti i processi che potrebbero richiederne l'uso fuorchè ad un singolo processo dedicato, che diverrà quindi destinatario e mediatore delle richieste). Il SO deve inoltre permettere ed agevolare la cooperazione, una forma di interazione desiderata (perchè aumenta il parallelismo dell'elaborazione) e prevista quando i processi sono tra loro logicamente collegati o interdipendenti (condizione necessaria è l'esistenza almeno di un ordinamento parziale tra processi concorrenti, viceversa un ordinamento totale impone un'elaborazione strettamente sequenziale): la cooperazione richiede una sincronizzazione esplicita tra processi cooperanti, che possono scambiarsi messaggi di pura sincronizzazione o di sincronizzazione e dati, e il SO si fa carico di gestire la cooperazione tra processi utente e processi del SO e mette a disposizione meccanismi per la cooperazione tra processi utente. Il SO deve infine prevenire le interferenze quando dovute a errori di soluzione a problemi di competizione e cooperazione: il SO può prevenire solo interferenze macroscopiche (ad esempio la violazione della memoria) ma in presenza di veri e propri bug di programmazione può fare poco o nulla.

Un tipo particolare di interazione tra due processi si presenta quando uno di essi tenta di sincronizzare il proprio flusso di controllo con la terminazione dell'altro. A questo scopo esiste la primitiva Join che determina la confluenza o ricongiunzione di due o più flussi di controllo, e il cui algoritmo è schematizzabile in pascal-like in due distinte versioni:

Procedure join(count);

begin

count:=count - 1;

if count>0 then

begin

<termina il processo chiamante>

Scheduling_CPU; Ripristino_Stato;

//In pratica si effettua un Context_Switch con contemporanea

//terminazione del processo corrente

end;

end;

Procedure join(pid);

begin

if stato(pid) <> terminated then

begin

<poni il processo chiamante in attesa che il processo PID termini>

Context_Switch;

end;

end;

La primitiva Join(count) consente la confluenza di N flussi di controllo ma non consente di denotare esplicitamente i processi con cui ci si vuole sincronizzare: valutando l'esempio seguente in pascal concorrente, non è difficile convincersi che non è detto che i processi figli terminino tutti prima del processo padre e quindi non è detto che siano i flussi di controllo dei figli a confluire nel flusso di controllo del padre

begin

count:=3;

fork label_1;

fork label_2;

goto label_3;

label_1:

label_2:

label_3: join(count);

Fine:

end;

l'unica cosa di cui si può essere certi è che tra i 3 processi (al massimo) in esecuzione contemporaneamente, un solo di essi sfuggirà al suicidio previsto dalla Join e arriverà ad eseguire l'istruzione della label Fine (quale sia tra essi non lo possiamo però sapere in anticipo). La primitiva Join(pid) consente viceversa la confluenza di soli 2 flussi di controllo ma permette di indicare esplicitamente chi si sincronizza con chi: nell'esempio seguente in pascal concorrente il processo padre crea il processo figlio (il cui PID è memorizzato in P) e poi eseguendo la Join si arresta nell'attesa che il figlio termini (Join non termina forzatamente alcun processo, aspetta che esso termini spontaneamente), ovvero in pratica sospende la sua esecuzione per sincronizzarsi col completamento del processo figlio

var P:process;

procedure X;

begin

end; produce una SVC per la terminazione del processo (exit)

begin Main

P:= fork(X);

join(P);

end;

Esempio: programma di Lettura-Elaborazione-Scrittura di Array[N]

Per il programma introdotto all'inizio (nel paragrafo sui processi) è possibile costruire un grafo di precedenza dei processi di Lettura, Elaborazione e Scrittura che ha la forma di un reticolo rettangolare a 3 (larghezza) x N (altezza) nodi, in cui da ogni nodo partono (se possibile) archi orientati verso i due nodi alla destra e in basso: in pratica Lettura(i) precede logicamente Elaborazione(i) e Lettura(i+1), Elaborazione(i) precede logicamente Scrittura(i) e Elaborazione(i+1) e Scrittura(i) precede logicamente Scrittura(i+1). In pratica le letture possono avvenire in modo sequenziale senza vincoli, mentre le elaborazioni e le scritture devono verificare vincoli di precedenza (nel primo caso perchè l'elaborazione di un dato successivo può dipendere dall'elaborato di un dato precedente, nel secondo caso perchè i dati vano scritti sequenzialmente nello stesso ordine in cui sono stati letti). L'ordinamento parziale dei nodi di questo grafo consente lo sviluppo di un algoritmo concorrente, di cui il seguente è un semplice esempio realizzativo

var R : array[1..N] of T; Array di N elementi

i : 1..N; Variabile di indice

PE, PS : array[1..N] of process; Array di puntatori a processi

N puntatori a processi Elaborazione e N a processi Scrittura

procedure E(k : 1..N);

begin

if k>1 then Join( PE[k-1] ); Se non ci troviamo sulla prima riga del grafo sincronizzati

con l'elaborazione del campo precedente

Elabora( R[k] ); Elabora il campo corrente

PS[k]:=Fork( S(k) ); Genera il nodo alla destra di quello corrente

end; Exit

procedure S(k : 1..N);

begin

if k>1 then Join( PS[k-1] ); Se non ci troviamo sulla prima riga del grafo sincronizzati

con la scrittura del campo precedente

Scrivi( R[k] ); Scrivi il campo corrente

end; Exit

begin

for i:=1 to N do begin Ciclo di lettura sequenziale dei campi con "forking laterale"

Leggi( R[i] ); del grafo, per dare inizio all'elaborazione dei campi

PE[i]:=Fork( E(i) );

end;

end;