|
Articolo pubblicato sul n. 52 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel maggio 1986
Concorrenza, semafori, monitor
Dopo aver discusso lo scorso mese le principali modalità di
multiprogrammazione di un computer, questo mese analizzeremo
il problema della concorrenza di più processi che accedono
a risorse condivise, sia questa un'unità di ingresso
uscita, una struttura dati o semplicemente una variabile.
Se non si prendono le dovute cautele, infatti, possono succedere veramente cose strane: procediamo con ordine... Prologo Per chi non ci ha seguito lo scorso mese, facciamo un attimino il punto della situazione, quantomeno circa la terminologia che useremo nel resto dell'articolo. Innanzitutto un processo è, in parole povere, un "programma che gira" o per essere più precisi, un processo è quanto descritto dal programma mantenuto in memoria e che il processore "processa". Si introduce questa nuova definizione per indicare qualcosa di effettivamente dinamico, nonché capace di provocare il verificarsi di eventi. Di contro, un programma è semplicemente un insieme di istruzioni che descrivono qualcosa, quindi per sua natura è statico. Detto questo, possiamo introdurre il concetto di stato (di un processo). Nei sistemi multiprogrammati infatti più programmi possono essere mantenuti in memoria, e con i meccanismi mostrati lo scorso mese possono essere eseguiti in parallelismo reale o simulato dal o dai processori di cui il calcolatore in considerazione dispone. A causa di alcuni eventi, abbiamo visto, un determinato processo può trovarsi in tre diversi stati: in stato di esecuzione, in stato di pronto o in stato di sospeso. Il primo caso riguarda il processo effettivamente eseguito dal processore nell'istante che stiamo considerando. In stato di sospeso vanno invece quei processi che dovendo attendere passivamente un evento esterno (ad esempio l'arrivo di un dato dall'unità a dischi), liberano la CPU che così può dedicarsi a elaborare dell'altro. Infine in stato di pronto vanno quei processi che hanno ottenuto ciò che aspettavano e sono pronti per ripartire non appena la CPU si libera rilasciando il processo attualmente in esecuzione. Le risorse condivise Se i vari processi che devono essere eseguiti in parallelo sono completamente indipendenti l'uno dall'altro quanto esposto lo scorso mese non fa una grinza. Ciò però è davvero difficile che si verifichi: infatti già le sole periferiche di ingresso uscita rappresentano un punto di contatto (e naturalmente di potenziale collisione) per i vari processi. Immaginate che due processi cerchino di scrivere contemporaneamente qualcosa su disco. Dal canto suo, la periferica può esaudire solo una richiesta per volta: si rende necessario un meccanismo che in qualche modo arbitri tali accessi. Se poi i processi da eseguire in parallelo cooperano usando strutture dati condivise l'affare si complica ulteriormente se non si prendono le opportune cautele. Cooperazione tutt'altro che rara: infatti lo scrivere oggi un sistema operativo di un calcolatore, non corrisponde più a stendere un enorme programmone zeppo di routine che svolgono le funzioni più disparate. La tendenza attuale è quella di multiprogrammare un calcolatore già a livello di sistema operativo: esso stesso sarà una collezione di processi (evolventi in parallelo) che cooperano per svolgere le funzioni volute. Ad esempio avremo un o più processi che controllano l'output su stampante o l'I/O del disco; tramite opportuni meccanismi (alcuni li vedremo subito) sarà poi possibile far comunicare più processi tra di loro per "intendersi" sul da farsi. La cooperazione tra processi può avvenire in due distinti modi: ad ambiente locale o ad ambiente globale. Nel primo caso si instaura un vero e proprio traffico di messaggi: un processo spedisce un messaggio ad un altro eventualmente aspettando anche una risposta. Il nucleo del sistema operativo provvederà a dirigere tali "spedizioni" in modo, per così dire, trasparente al livello dei processi. La cooperazione ad ambiente globale avviene invece tramite zone di memoria, più in generale strutture dati, condivise tra i processi: ad esempio, se il processo A deve comunicare qualcosa al processo B provvederà coi propri mezzi (li vedremo) a scrivere "il qualcosa" in una locazione di memoria, dove B si "recherà" per prelevarlo. E' proprio in casi come questi che si parla di risorse condivise: nel nostro esempio, la risorsa è rappresentata dalla locazione di memoria usata per l'interazione. Sezioni critiche Detto questo, cominciamo a parlare dei problemi che insorgono quando degli oggetti (le risorse) sono manipolate da particolari agenti (i processi) che come abbiamo riportato sono capaci di provocare il verificarsi di eventi. Eventi che possono benissimo essere alcune volte quantomeno indesiderati. Come abbiamo visto lo scorso mese, nei sistemi a divisione di tempo (time-sharing), la CPU veniva concessa ai singoli processi per un determinato periodo di tempo, scaduto il quale il controllo passava per un altro quanto di tempo ad un altro processo prelevato dalla lista "pronto". Scegliendo quanti di tempo sufficientemente piccoli era così possibile simulare un parallelismo anche su computer uniprocessor, o in generale su ogni processor di un computer multiprocessor. Lo scadere dei quanti di tempo, veniva segnalato da un interrupt proveniente da un orologio interno al calcolatore che svolgeva proprio tale funzione. Immaginiamo ora che due processi, P1 e P2, utilizzino una variabile comune, ad esempio X, con la quale contano qualcosa. Ciò in un generico linguaggio ad alto livello si esprime con un comando del tipo: X = X + 1
presente in ciascuno dei due processi. Teniamo a
sottolineare il fatto che la X è uno stesso oggetto
visibile da due processi, non due variabili distinte con lo
stesso nome. In altre parole se P1 pone X=0 e P2 esegue
X=X+1, anche per P1 il valore di X sarà 1 (è stato P2 a
incrementarlo). Focalizziamo la nostra attenzione su due
incrementi effettuati uno da P1 e l'altro da P2. Se
all'inizio X vale 0, dopo l'esecuzione di questi due
comandi, ovviamente, X risulterà incrementata di due.
Questo nella migliore delle ipotesi: infatti può succedere
qualcosa di anormale. Vediamo perché. Del comando X=X+1 al
processore arriverà una traduzione in linguaggio macchina
sia che si tratti di interpretazione che di compilazione del
programma di partenza. Ad esempio, la sequenza di operazioni
corrispondente sarà tipo quella mostrata in Poniamo il caso in cui, non appena si trasferisce il contenuto di X nell'accumulatore, l'orologio mandi l'interrupt alla CPU essendo scaduto il quanto di tempo di P1. Parte così P2 e diciamo che prima del prossimo scadere di tempo esegua anch'esso un X=X+1, questa volta portandolo a termine. Riparte P1 che, dove era stato interrotto, aggiunge 1 al contenuto dell'accumulatore e lo pone in X. Giusto, no? NO!, c'è stato un errore: X al termine non contiene 2 ma 1, in quanto P1 è stato interrotto quando già aveva caricato nell'accumulatore il valore 0, al quale (dopo il risveglio) ha sommato 1 e l'ha scritto in X, assolutamente ignaro del fatto che intanto anche P2 aveva fatto lo stesso. Ciò è dovuto al fatto che per incrementare una variabile si è dovuto compiere non una sola istruzione ma tre, e nessuno ci garantiva che sarebbero state eseguite indivisibilmente. Infatti se non avessimo avuto l'interruzione giusto durante l'incremento, tutto sarebbe andato liscio ottenendo effettivamente il valore 2 in X alla fine delle due esecuzioni. Quindi, quando si accede ad una variabile condivisa per modificarne il contenuto, è bene che non vi siano interruzioni di sorta, che come visto prima possono causare dei veri e propri fallimenti. Per fare ciò bisogna innanzitutto individuare le sezioni (che d'ora in avanti chiameremo "critiche") di programma contenenti modifiche a variabili condivise, per poi implementare opportuni meccanismi che ci garantiscano che se un processo accede ad una di queste sezioni critiche, gli altri non facciano altrettanto finché il primo non ha terminato. Soluzioni Nel caso di calcolatore uniprocessor che simula un ambiente multiprogrammato col meccanismo degli interrupt, un metodo abbastanza semplice per rendere indivisibile l'esecuzione di una sezione critica, consiste nel disabilitare le interruzioni con un apposito comando al processore. Eseguita la sezione critica, un nuovo comando riabiliterà l'ascolto delle interruzioni. Eventuali interrupt ricevuti durante il "coprifuoco" non vengono persi ma restano pendenti in attesa di poter giungere a destinazione. In figura 2 è mostrata la sezione critica discussa prima, avvolta dalle due istruzioni per il processore che settano la disabilitazione dell'interruzioni e infine cancellano tale disabilitazione. Se in tale ipotesi come prima dovesse scadere il quanto di tempo subito dopo l'LDA, la commutazione di contesto (il rilascio di P1 e l'esecuzione di P2) sarà ignorata fino all'istruzione CLI che riabilita le interruzioni quando ormai la sezione critica è terminata. Nel caso di calcolatore multiprocessor, disabilitare le interruzioni del processore che sta eseguendo la sezione critica non basta in quanto P1 e P2 possono evolvere su processori diversi e anche in questo caso bisogna garantire che quando P1 modifica una variabile condivisa P2 non faccia altrettanto. Infatti immaginate che P1 e P2, da due processori diversi, eseguano contemporaneamente il famoso X=X+1 tradotto in linguaggio macchina sempre in figura 1. Come prima sia il caso che X all'inizio valga 0 e se due processi la incrementano di 1 alla fine dovrà valere 2. Sia P1 che P2 caricano il contenuto di X negli accumulatori dei due processor. Contemporaneamente gli sommano 1 (attenzione: ognuno nel proprio accumulatore) e ancora tutt'e due assieme riscrivono il risultato di tale somma in X: sbagliato ancora una volta, così facendo X vale 1, non 2. Brutalmente si potrebbe oltre che disabilitare le interruzioni sul processor che in quell'istante sta eseguendo la sezione critica, bloccare anche gli accessi alla memoria da parte degli altri processor: così saremmo sicuri che nessuno ci rompa (le uova nel paniere). Fatto sta però che se sugli altri processori nessuno aveva intenzione di accedere alla stessa variabile, avremmo inutilmente provocato un arresto temporaneo del rimanente sistema che si è visto negare di colpo l'uso della memoria, senza nessun motivo. L'idea è allora quella di suddividere le sezioni critiche in classi: due sezioni critiche appartengono alla stessa classe se manipolano le stesse strutture dati condivise. A questo punto non bloccheremo l'accesso a tutta la memoria, ma semplicemente, prima di entrare in una sezione critica, chiuderemo a "chiave" la stessa in modo da assicurarci l'esclusiva. Al termine della nostra sezione critica la lascieremo aperta in modo da permettere ad altri l'accesso. L'esempio tipico che si fa per spiegare meglio questo semplice procedimento è quello dell'appartamento coabitato da più persone dove la sezione critica è naturalmente il bagno: prima di entrare si controlla che non vi sia nessun altro, si accede alla risorsa chiudendocisi dentro e all'uscita si lascia la porta ovviamente non chiusa a chiave per permettere ad altri l'accesso. In questo modo resteranno bloccati solo i processi che tentano di accedere alle stesse variabili condivise che sta già manipolando uno dei processi in esecuzione. In particolare vogliamo sottolineare il fatto che se su un altro processore gira un processo che non... vuole andare al bagno, questo potrà tranquillamente continare a fare ciò che stava facendo. Occorrono però dei meccanismi aggiuntivi coi quali accedere, chiudere o aprire sezioni critiche. Non vorremmo essere noiosi, con l'esempio del bagno: provate però a immaginare cosa accadrebbe se una persona trova la porta chiusa. La cosa più semplice è aspettare, magari, lì davanti. Non appena la porta si riapre potremo comodamente accedere.
Il primo schema di apertura/chiusura di sezioni critiche
non si differenzia di molto dall'algoritmo "igienico" appena
visto. Ad ogni sezione critica è associata una chiave (che
chiameremo K) che ad esempio contiene il valore 0 se è
possibile entrare, 1 altrimenti. Un processo che sta per
entrare in sezione critica, esegue oltre al SEI per
disabilitare le interruzioni presso il suo processore (vedi
fig.3) anche l'istruzione LOCK sulla chiave K per
appropriarsi l'accesso
In figura 4 è mostrato in linguaggio BASIC-like il corpo della procedura LOCK e quello della UNLOCK. Il loro funzionamento è assai semplice: la LOCK se K è uguale a 0 lo pone a 1 e basta (vuol dire che la sezione critica era libera quindi l'ha occupata) altrimenti cicla sulla linea 10 finché K non diventa 0 (qualcuno ha lasciato la sezione critica) per poi porlo uguale a 1 alla linea 20 avendo così acquisito l'accesso. La UNLOCK, come è facile immaginarte, è molto più semplice dovendo solo rimettere K=0. Semafori I più attenti avranno certamente notato che nell'algoritmo delle LOCK/UNLOCK c'è qualcosa che non va. Non tanto a livello di funzionamento, quanto nel fatto che un processo che trova la "porta chiusa" sta a ciclare sulla linea 10, tenendo così inutilmente occupata la CPU che non può fare dell'altro. Infatti lo diciamo e lo ridiciamo sempre, i calcolatori devono calcolare, non aspettare. Sempre.
E noi così facendo introduciamo della attesa attiva che
certo non giova, specialmente dopo tutto quello che abbiamo
detto lo scorso mese circa i sistemi multiprogrammati. Lì
dicevamo che quando un processo
Tale meccanismo è detto dei Semafori, per l'aspetto comportamentale assai simile alle ben note "primitive" stradali (forse più a quelle ferroviarie). Associamo un semaforo, come prima, ad ogni sezione critica e, guardacaso, questo sarà verde se è possibile accedervi, rosso altrimenti. La struttura dati corrispondente al semaforo è schematicamente mostrata in figura 5: abbiamo un campo Valore (che come detto assumerà Rosso o Verde a seconda del caso) e associato a questo una coda dove sospendere i task che trovano Rosso.
I Semafori (ovviamente quali strutture per la mutua
esclusione) sono dovuti a E.W.Dajkstra il quale ha anche
provveduto a dare un nome alle relative primitive di accesso
e rilascio della sezione critica. L'opeazione P corrisponde
alla LOCK di prima, V alla UNLOCK e sono ambedue mostrate in
figura 6.
Terminata la sezione critica, il processo esegue la V, mostrata in figura 6b: se la coda del semaforo è vuota pone (linea 20) il campo valore a Verde; altrimenti (linea 10 dopo il THEN, abbiamo capovolto un po' la situazione) si prende un processo dalla coda del semaforo e lo si pone in stato di pronto. In tale caso si lascia il semaforo Rosso in modo che sia proprio questo task e nessun altro ad accedere alla sezione critica per primo, non appena un processore si libera e lo preleva per eseguirlo. Monitor
Cosa c'è ora che non va? Anche i semafori fanno acqua No, non è questo che preoccupa: se usati correttamente i semafori vanno più che bene: correttamente, però. Il problema è appunto questo: fidarsi è bene, non fidarsi è meglio (degli utenti). Infatti, se da una parte è vero che con l'uso delle P e delle V si riescono a trattare facilmente le situazioni di mutua esclusione tra processi, è anche vero che se un utente usa un linguaggio di programmazione concorrente con le P e le V, e non fa molta attenzione al loro uso, può provocare più pasticci di quanti se ne sarebbero verificati senza di esse. Se per esempio dimentica di fare la V dopo la sezione critica, o viceversa, o accede in due sezioni critiche l'una dentro l'altra, facilmente si possono creare situazioni di stallo in cui tutto il sistema si paralizza, tutti i processi risultano sospesi, non vi sono processi pronti né in esecuzione e le CPU stanno con le mani in mano.
Tradotto in altre parole, fino a quanto si tratta di una
variabile condivisa tra
Impaginato originale...
Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui |
