Creazione dei processi

CREAZIONE DEI PROCESSI

I meccanismi basilari che prenderemo in considerazione sono:

FORK = creazione di un processo;

JOIN = ricongiunzione tra processo padre e processo figlio.

Immaginiamo di avere un processo attivo, ossia un programma in esecuzione. Supponiamo che ad un certo punto del flusso di controllo ci sia l'istruzione:

A : FORK X

(A è una label). Questa istruzione genera il descrittore di un nuovo processo figlio; i descrittori del padre e del figlio sono diversi, ma è stata fatta l'ipotesi che i due processi condividono la stessa area di memoria e quindi i relativi descrittori fanno riferimento allo stesso codice, alla stessa area dati ed allo stesso stack [1]. X specifica il 'punto' del codice del padre da cui parte il figlio, per cui si può dire che X è il program counter del nuovo processo da iniziare.

L'istruzione FORK sortisce la nascita di un nuovo processo e quindi fa sì che sullo stesso codice vengono percorsi 'concorrentemente' due flussi di controllo. (Se abbiamo una macchina a monoprocessore, ciò può avvenire solamente a livello virtuale[2]). Due processi che condividono area di codice, area dati e stack ma che procedono su flussi di controllo diversi si definiscono THREAD. Fra due thread si possono creare forti situazioni di competizione e di conflitto .

Dopo che la FORK ha creato il descrittore del figlio, l'esecuzione poi continua anche[4] con il padre. Quindi da A parte una 'biforcazione' che sta ad indicare che da quel punto in poi vengono eseguiti correntemente e in modo ASINCRONO i due processi, contrassegnati nell'esempio seguente dalle label B e X.

A : FORK X                                                                                            A

B : "istruzione successiva alla FORK"                                                    

. B                  X

.

X : "prima istruzione del processo invocato da FORK X"

Dunque l'istruzione FORK è concettualmente simile ad una istruzione di chiamata, tranne per il fatto che il chiamante non viene sospeso ma prosegue parallelamente al chiamato.

L'istruzione JOIN determina la confluenza fra i due processi. Se abbiamo in precedenza creato un processo figlio mediante FORK, con JOIN succede che, non appena termina il processo figlio, si ricongiunge con il padre, ovvero solo quest'ultimo rimane in esecuzione. Questo vale anche se si hanno più processi figli in esecuzione: con l'istruzione JOIN si aspetta che tutti i figli terminino e quando sono completati si lascia in esecuzione il solo processo padre. Si ha dunque la congiunzione di più flussi di controllo indipendenti. Si osservi il seguente esempio.

A

B C

D              E F

G

begin

cont : = 3 ;

A ;

FORK E1 ;

B ;

FORK E2 ;

D ;

goto E3 ;

E1 : C ;

F ;

goto E3 ;

E2 : E ;

E3 : JOIN cont ;

G ;

end.

(Questo linguaggio si chiama Pascal concorrente). Subito dopo l'istruzione FORK E1 potremo avere al massimo due processi attivi, mentre dopo l'istruzione FORK E2 ne potremo avere al massimo tre. Diciamo 'al massimo' perché i figli potrebbero terminare prima del padre.

Nell'esempio appena visto abbiamo fatto uso di una rudimentale versione dell'istruzione JOIN, che viene impiegato unitamente ad un intero, cont:

var cont : integer

JOIN cont

In questo caso JOIN riassume le seguenti operazioni:

cont : = cont - 1

if cont <> 0 then termina processo [soppressione del descrittore]

Questa versione permette di ricongiungere n flussi di controllo, con n qualsiasi, ma non di denotare esplicitamente il (o i) processi con cui ci si vuole sincronizzare. Inoltre, non è detto che l'esecuzione dei processi figli termini prima di quella del padre.

In un'altra definizione, la FORK restituisce un identificatore di processo, che viene successivamente accettato da una JOIN, in modo che sia specificato con quale processo si intende sincronizzarsi. Lo svantaggio di questa definizione è che la JOIN può ricongiungere solo due flussi di controllo. Indicheremo con P una variabile che può assumere come valore il nome (o identificatore) di un processo.

var P : process ;

procedure X ;

begin

.

.

end ; (*)

begin

P : = FORK X ; X

.

.

JOIN P ;

end.

Nel punto marcato da un asterisco è prevista implicitamente una chiamata al supervisore per la terminazione del processo (exit). Solo quando il processo P (figlio) ha già eseguito la sua exit, ossia è terminato, continua il processo padre [5].

Per chiudere, riscriviamo il programma di pag. 17, 18 servendoci della nuova JOIN.

Var P1, P2 : process

procedure E1 ;

begin

C ;

F ;

end ;

procedure E2 ;

begin

E ;

end ;

begin

A ;

P1 : = FORK E1 ;

B ;

P2 : = FORK E2 ;

D ;

JOIN P1 ;

JOIN P2 ;

G

end.

Torniamo all'ultimo esempio fatto la scorsa volta. La variabile P di tipo process introdotta vale 0 per il processo figlio, mentre per il processo padre vale il "process identifier" del figlio (ossia il suo nome). Eccezion fatta per questa variabile P, presente nell'area dati, padre e figlio sono l'uno l'immagine speculare dell'altro.

Facciamo ora un passo indietro e riconsideriamo il semplice programma di pag. 13. Tracceremo il grafo di precedenza del processo, che specifica mediante nodi (rappresentativi degli eventi del processo) e archi orientati l'ordine mediante il quale il processo può svilupparsi. Poiché, come si è precisato, questo programma può essere elaborato in modo concorrente, il grafo evidenzia un ordinamento parziale degli eventi. Indichiamo con L_i l'evento "lettura dell'i-esimo record", con E_i l'elaborazione e con S_i la scrittura dell'i-esimo record.

START

L₁

E₁

S₁

L₂

E₂

S₂

L_n

E_n

S_n

END

Il sistema è dunque organizzato in tre soli processi: uno che legge, uno che effettua la particolare elaborazione e uno che scrive. Ciascuno dei tre riceve in sequenza gli n record, e in questo senso vanno rispettate le precedenze reciproche: ad esempio non si può elaborare il terzo record prima del secondo; esiste un'ovvia regola di precedenza anche in riferimento ai singoli record: un record deve necessariamente essere prima letto, poi elaborato, poi scritto. Tuttavia è ad esempio possibile leggere il secondo record mentre si sta elaborando il primo, o elaborare il terzo record mentre si sta scrivendo il secondo.

Scriviamo ora il relativo programma in Pascal concorrente.

Var BL, BE, BS : array [1..N] of T ;

i : 1..N ;

PE, PS : array [1..N] of process ;

procedure E (k : 1..N) ;

begin

if k <> 1 then JOIN PE[k-1] ;

ELABORA (BE[k]) ;

BS[k] : = BE[k] ;

PS[k] : = FORK S(k)

end ;

procedure S (k : 1..N) ;

begin

if k <> 1 then JOIN PS[k-1] ;

SCRIVI (BS[k]) 

end ;

BEGIN

LEGGI (BL[1]) ;

for i : = 1 to N-1 do

begin

BE[i] : = BL[i] ;

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

LEGGI (BL[i+1]) ;

end ;

BE[N] : = BL[N] ;

PE[N] : = FORK E(N) ;

end.

Le end delle due procedure sono in realtà delle 'exit' che terminano il processo in corso e consentono la ripresa rispettivamente di PE [k-1] e PS [k-1] [6].

Le istruzioni FORK e JOIN possono essere presenti tanto nei SO (per dare luogo ai processi; ad esempio questi costrutti sono presenti in UNIX) quanto in specifici linguaggi di programmazione finalizzati proprio a realizzare i SO. Nel primo caso, tali istruzioni saranno evidentemente a più basso livello.

Il precedente programma non è certo di facile leggibilità. In particolare, non è facile dire in ogni punto del programma, durante la sua esecuzione, quali processi siano attivi. Un'alternativa consiste nell'usare un differente costrutto, COBEGIN COEND, che, come si vedrà, appare più semplice, ma che presenta lo svantaggio di non poter rappresentare tutti i possibili grafi di precedenza. La concorrenza viene espressa nel modo tipico del linguaggio a blocchi:

COBEGIN                                                           A

S₁

S₂ S₁ S₂ . . . S_n

. B

S_n

END

Nel seguito viene riportata l'ovvia implementazione di un semplice grafo.

Begin

S₀ ; S₀

COBEGIN

S₁ ; S₁ S₂ S₃

S₂ ;

S₃ S_n

COEND ;

S₄ 

end.

Esprimiamo, per maggiore chiarezza (in tutti i sensi), il grafo di pag. 18 mediante COBEGIN - COEND.

begin

A ;

COBEGIN A

begin

C ; B C

F ;

end ; D E F

begin

B ; G

COBEGIN

D ;

E ;

COEND ;

end

COEND

end.

Dicevamo però che ci sono grafi di precedenza per i quali le istruzioni COBEGIN e COEND non risultano utilizzabili, per lo meno non da sole. Indichiamo con cammino parallelo una qualunque sequenza di nodi delimitata da un nodo COBEGIN e un nodo COEND. Un grafo, per poter essere espresso soltanto con queste istruzioni, deve essere tale che detti X e Y due nodi COBEGIN e COEND del grafo, tutti i cammini paralleli che iniziano da X terminano con Y e tutti quelli che terminano con Y iniziano con X (o, più sinteticamente, ogni 'sottografo' deve essere del tipo ONE-IN / ONE-OUT) [7]. Il grafo che segue non presenta questa caratteristica e quindi costituisce un controesempio.

A

B E

C D F

H G

I

Il ramo 'incriminato' è B-D-G. Esso rappresenta un cammino parallelo, dato che inizia con un nodo COBEGIN (nodo con più successori) e termina con un nodo COEND (con più predecessori). Ma esistono anche il cammino parallelo B-C-H-I, che pur iniziando con B termina con un diverso nodo, I, e il cammino A-E-F-G, il quale termina col nodo G (come B-D-G) ma inizia col nodo A.