Appunti per Scuola e Università
humanisticheUmanistiche
Appunti e tesine di tutte le materie per gli studenti delle scuole medie riguardanti le materie umanistiche: dall'italiano alla storia riguardanti le materie umanistiche: dall'italiano alla storia 
sceintificheScientifiche
Appunti, analisi, compresione per le scuole medie suddivisi per materie scientifiche, per ognuna troverai appunti, dispense, esercitazioni, tesi e riassunti in download.
tecnicheTecniche
Gli appunti, le tesine e riassunti di tecnica amministrativa, ingegneria tecnico, costruzione. Tutti gli appunti di AppuntiMania.com gratis!
Appunti
informatica
CComputerDatabaseInternetJava
Linux unixReti


AppuntiMania.com » Informatica » Appunti di computer » Il meccanismo semaforico

Il meccanismo semaforico




Visite: 1355Gradito:apreciate stela [ Medio appunti ]
Leggi anche appunti:

Il modello relazionale


La PROGETTAZIONE LOGICA RELAZIONALE consiste nella conversione del modello ER in

La gestione della memoria


La gestione della memoria        Quando un processo diventa Running, è necessario

Struttura di un sistema operativo


STRUTTURA DI UN SISTEMA OPERATIVO Un SO è schematizzabile come una 'cipolla',
immagine di categoria



Scarica gratis Il meccanismo semaforico

IL MECCANISMO SEMAFORICO


Soffermiamoci ora sul modello di programmazione a memoria globale. Un meccanismo elementare messo a disposizione dal SO per risolvere conflitti nell'attribuzione delle risorse è quello dei SEMAFORI. Un semaforo è, come ogni risorsa, una struttura dati corredata di due procedure che consentono di utilizzarla.



Il primo modello di semaforo fu ideato da Dijkstra ed era un semaforo booleano: in pratica, una variabile booleana condivisa fra tutti i processi. Il semaforo generalizzato è invece costituito da una variabile intera che può assumere valori in un certo range.


Indicando con s un semaforo, su s è possibile effettuare le seguenti due operazioni:


WAIT(s)  REPEAT UNTIL s > 0 ;

s : = s - 1


SIGNAL(s) : s : = s + 1


Wait ritarda il processo finché s diviene maggiore di 0 ("semaforo verde"), e quindi lo decrementa di 1. Signal incrementa il semaforo di 1. Si tratta di operazioni atomiche, cioè non interrompibili, che sono parte del nucleo del SO. Le definizioni appena date hanno un senso generale e nella realtà vengono implementate in modo diverso e diversamente a seconda del contesto. Ad esempio, la wait, che viene invocata dai processi per tentare di aggiudicarsi l'attribuzione di una risorsa, nella versione generale comporterebbe una ripetizione continua dell'esame del valore del semaforo. Questo costituisce un'evidente spreco di tempo e perciò viene evitato. La signal ha l'effetto, quando invocata da un processo, di liberare una risorsa e quindi di renderla disponibile per altri processi, inclusi quelli che in precedenza erano stati sospesi in fase di wait proprio perché quella risorsa era occupata ('risveglio' di un processo).

In un semaforo binario può 'passare' un solo processo per volta. In uno intero, con s I (0, 1, , N), ne possono passare fino a N.


Vediamo adesso come si realizzano i semafori nei sistemi multiprocessore e monoprocessore.


SISTEMI MULTIPROCESSORE (una sola memoria e più processori). Supponiamo che un processo A giri sul processore P1 e simultaneamente un secondo processo B giri sul processore P2. Il SO mette a disposizione un semaforo binario. Ad un certo punto, per aggiudicarsi l'attribuzione di una risorsa, A effettua una WAIT(s).


s

MEMORIA



A P1 B P2 P3 . . . . .



Già ora si comprende l'importanza che sia garantita l'atomicità di tale primitiva.. Infatti la WAIT(s) comporta che si prelevi s dalla memoria e si testi il suo valore. Supponiamo sia s = 1. Può darsi che subito dopo anche B effettui una WAIT. Può accadere allora che B legga il valore s = 1 prima ancora che A abbia il tempo di effettuare il decremento s : = s - 1, e quindi entrambi i processi passerebbero, cosa non possibile, avendo supposto binario il semaforo. Quindi occorre un meccanismo che blocchi l'accesso al BUS da parte di qualunque altro processo mentre A sta leggendo s.

Allo scopo è spesso usata l'istruzione TEST AND SET, che legge s e nello stesso ciclo di bus lo pone in ogni caso a 0. Se s valeva 1, si ottiene il cambiamento di stato del semaforo. Se era s = 0, non cambia nulla.

Dunque, la WAIT(s) si può realizzare mediante un loop sull'istruzione TEST AND SET, che dura fintantoché s = 0 (e quindi si interrompe non appena s = 1). Il loop si effettua mediante un istruzione di salto, tipo JUMP. Fra TEST & SET e JUMP devono esserci delle NOP (no operation), poiché bisogna dare il tempo agli altri processi di porre, eventualmente, s = 1[1].





SISTEMI MONOPROCESSORE. A causa della non-interrompibilità, su di un sistema a monoprocessore questa istruzione non può essere realizzata direttamente come a pag. 32. Invocando infatti WAIT(s) con s = 0, il sistema si 'impallerebbe' perché, dato che un simile sistema può far girare un solo processo per volta, verrebbe meno ogni possibilità di rendere la s positiva, uscendo dal REPEAT. Se si ha a disposizione un sistema multiprocesso si può usare il meccanismo dei processori virtuali e far sì che la WAIT operi un'attesa non sul processore reale, ma su un processore virtuale. In tal modo, l'attesa generata dal REPEAT.. UNTIL potrà terminare, poiché sarà sufficiente che un altro processo in esecuzione incrementi s tramite l'operazione SIGNAL(s).


Più in generale, le due primitive vengono realizzate come segue.


WAIT(s) : begin

if s = 0 then

< il processo viene sospeso e il suo descrittore inserito nella coda Qs >

else s : = s - 1

end


Il ricorso all'istruzione WAIT genera un'interruzione. D'altra parte, la end della WAIT corrisponde sempre all'istruzione RTE (return ecception - ritorno da interruzione).

In breve, l'operazione WAIT viene usata per verificare lo stato di un semaforo. Se è positivo, questo viene decrementato di un'unità e il processo prosegue l'esecuzione. Se è nullo, il processo viene sospeso e l'unità di elaborazione così liberata viene assegnata ad un altro processo.


SIGNAL(s) : begin

if < esiste un processo in coda > then

< il suo descrittore è rimosso da Qs ed il suo stato diviene READY >

else s : = s + 1

end


La coda Qs contiene i descrittori dei processi in attesa di ricevere il 'via libera' dal semaforo. Essa è gestita, solitamente, mediante una classica lista dinamica.

In questo caso, il semaforo è un record a due campi: uno di essi è una variabile booleana che rappresenta il semaforo vero e proprio. L'altro campo contiene due puntatori: uno punta alla testa della coda Qs, ossia al processo in attesa che sarà servito per primo, il secondo punta all'ultimo processo in attesa. Si noti il prospetto seguente, dove figura anche un terzo campo, non indispensabile ma utile, contenente il numero dei processi presenti nella coda.



VALORE DEL SEMAFORO


puntatore puntatore

testa coda


(NUMERO PROCESSI)


descrittore descrittore

processo processo





Ogni transizione dei processi fra gli stati running, ready e wait prevede il trasferimento del descrittore del processo coinvolto fra due diverse code: la Qs appena menzionata, detta CODA DI ATTESA o anche CODA DEI SEMAFORI, e la CODA DEI PROCESSI READY (pronti).


Il nucleo del SO dispone di un'area stack, ossia gestita come una pila (secondo la disciplina LIFO). [Inoltre, ad ogni processo è associata, all'interno della regione privata di memoria ed esso riservata, una propria area stack, contenente ad esempio le variabili temporanee usate dal processo]. L'invocazione di una primitiva come la WAIT o la SIGNAL da parte di un processo corrisponde ad una supervisor call, il che genera, come si è detto, un'interruzione. Il program counter (PC) e il registro di stato del processo vengono quindi messi in testa allo stack del kernel.


Se in particolare la primitiva richiesta è la WAIT, si provvede innanzitutto all'esame del semaforo.

Se esso è diverso da zero, viene percorso il ramo else il che comporta in tempi brevi il proseguimento del processo in esame. Infatti la WAIT si limita in questo caso a decrementare il semaforo. Subito dopo il kernel rimette in esecuzione il processo (RTE) ripristinando il PC e lo stato del processo temporaneamente interrotto, contenuti nel suo stack.

Più articolato è l'andamento dei fatti nel caso in cui il valore del semaforo sia invece uguale a zero. Viene percorso il ramo then, il che comporta la trasformazione del processo da running a wait ed il ripristino di un diverso processo. In questo caso infatti la primitiva provvede a salvare nel descrittore del processo il PC, lo stato (che si trovano nello stack; ciò è indispensabile, dato che lo stack è un'area temporanea) e il 'contesto' (valori dei registri di macchina). Questo salvataggio è possibile, dal momento che fintantoché un processo è running la posizione del suo descrittore in memoria (puntatore) è conosciuta.

Successivamente, il descrittore viene messo nella coda dei processi di attesa e si dà la parola allo SCHEDULER dei processi. Lo scheduler determina il processo da rendere running, prende il suo stato, il suo PC e il suo contesto - memorizzato nel descrittore - e li pone nello stack, dopodiché fa puntare il puntatore al processo running corrente al suo descrittore. Quindi mediante la RTE quest'ultimo viene messo in esecuzione.

Il processo prescelto è il processo che si trova in testa alla coda dei processi pronti, o comunque quello considerato a maggiore priorità (cfr. nota 7 a pag. 15). Il vantaggio di usare una coda anziché il meccanismo delle priorità sta nel fatto che se viene seguito l'ordine di sospensione dei processi è impossibile che si verifichi un fenomeno di attesa indefinita da parte di un processo (che potrebbe non riuscire mai ad avere la priorità).


Si ricordi che la primitiva WAIT è non interrompibile. Di conseguenza, tutte le operazioni che ne fanno parte vengono eseguite con le interruzioni disabilitate. Un'eccezione a questa regola si applica quando lo scheduler non trova processi ready, giacché la coda è vuota. In tal caso lo scheduler abilita le interruzioni. A questo punto, potrebbe iniziare ad effettuare un proprio ciclo di attesa. Tipicamente, però, si preferisce seguire una diversa strategia: si inserisce fra i processi di sistema un apposito processo 'fittizio' (dummy process) che ha la priorità più bassa, in modo da essere chiamato solo quando non ci sono altri ready, ed è sempre nello stato ready. In generale un processo dummy si limita ad eseguire un ciclo senza fine e rimane in esecuzione fino a quando un qualunque altro processo non diviene ready. Nel nostro caso, l'interruzione del dummy è garantita dal fatto che, come abbiamo precisato, la WAIT termina sempre con una RTE [2].


Un processo sospeso può venire 'risvegliato' come conseguenza dell'esecuzione da parte di un altro processo di una SIGNAL sullo stesso semaforo. Se non vi sono processi in attesa nella coda associata al semaforo, la SIGNAL si limita ad incrementare il valore del semaforo. Se ce ne sono, il descrittore del processo che si trova in testa alla coda dei processi in attesa viene trasferito nella coda dei processi ready. In tutti e due i casi il processo che ha invocato la SIGNAL prosegue la sua esecuzione [3].





Tale algoritmo non è molto chiaro, ma può essere spiegato come segue. In base al Silberschatz-Galvin, pag.163, TEST & SET è una funzione booleana e quindi può assumere anch'essa i valori 0,1 (alias di false, true). In particolare, essa assume il valore di s e pone s = 0. Subito dopo si controllerà il valore di TEST & SET, vi saranno delle NOP e quindi una JUMP che riconduce nuovamente all'istruzione TEST & SET (il che dà luogo al loop summenzionato). Se un processo pone s = 1 durante una delle NOP, alla ripresa del ciclo TEST & SET varrà 1 e il successivo controllo produrrà l'uscita dal ciclo stesso. Questa è però solo una mia interpretazione dei fatti.

Occorre verificare la correttezza di questa osservazione.


Diversamente accade se si adotta la tecnica delle priorità, o una combinazione di questa e della tecnica delle code (Ancilotti-Boari pag. 309 § b2). In tal caso occorre confrontare la priorità del processo che ha eseguito la SIGNAL con la priorità del processo che si trova in testa alla Qs. Se quest'ultimo ha maggiore priorità, è il processo che ha eseguito la SIGNAL ad essere messo nella coda dei processi ready, mentre l'altro viene mandato in esecuzione. (Si noti dunque che tale processo compie una doppia transizione: wait - ready - running). Una SIGNAL del genere prende il nome di SIGNAL CON PRERILASCIO. Il termine prerilascio si usa per indicare il fatto che un processo perde l'uso della CPU pur un motivo diverso dalla sua terminazione o dalla non disponibilità di una risorsa. Il fenomeno del prerilascio interviene anche nei sistemi a divisione del tempo di assegnazione della CPU: a determinati intervalli di tempo il processo in esecuzione viene sospeso e la sua priorità viene confrontata con il processo ready più importante. Se quest'ultimo risulta più prioritario, prende il posto dell'altro, che viene prerilasciato, e va a finire nella coda dei processi ready.

Scarica gratis Il meccanismo semaforico
Appunti su:











Scarica 100% gratis e , tesine, riassunti



Registrati ora

Password dimenticata?
  • Appunti superiori
  • In questa sezione troverai sunti esame, dispense, appunti universitari, esercitazioni e tesi, suddivisi per le principali facoltà.
  • Università
  • Appunti, dispense, esercitazioni, riassunti direttamente dalla tua aula Universitaria
  • all'Informatica
  • Introduzione all'Informatica, Information and Comunication Tecnology, componenti del computer, software, hardware ...