Appunti per Scuola e Università
Umanistiche
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 
Scientifiche
Appunti, analisi, compresione per le scuole medie suddivisi per materie scientifiche, per ognuna troverai appunti, dispense, esercitazioni, tesi e riassunti in download.
Tecniche
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 » Algoritmo del banchiere

Algoritmo del banchiere




Visite: 944Gradito: [ Picolo appunti ]
Leggi anche appunti:

Il dispositivo Bus/Memoria


Il dispositivo Bus/Memoria I campi relativi alla configurazione di un bus sono

Modello a Scambio di Messaggi: Interazioni tra processi


Modello a Scambio di Messaggi: Interazioni tra processi        Nel modello

Federico Faggin


Federico Faggin E' conosciuto in tutto il mondo per quella sua intuizione che



Scarica gratis Algoritmo del banchiere

ALGORITMO DEL BANCHIERE


Il nome di questo algoritmo di deve al fatto che esso si fonda sulla strategia che il titolare (avveduto) di una banca di prestiti deve adottare se vuole che la cassa del denaro non rimanga mai vuota. Esso richiede una struttura dati piuttosto articolata, che viene descritta qui di seguito:




n

numero processi

m

numero di risorse disponibili (ovvero, numero di tipi distinti di risorse)

available

vettore di lunghezza m che indica le istanze attualmente disponibili per ciascuna risorsa

max

matrice (n x m) tale che max (i,j) è il numero massimo di istanze della risorsa j che il processo i può richiedere

need

matrice (n x m) che indica per ogni processo i la necessità residua di risorse (j)

allocation

matrice (n x m) che indica per ogni processo i il numero di istanze della risorsa j delle quali è attualmente in possesso; si noti che need(i,j) = max(i,j) - allocation(i,j)

requesti

vettore (lungo m) delle richieste per il processo i

work

vettore (lungo m) inizializzato secondo il contenuto di available

finish

vettore (lungo n) inizializzato con tutti false; i vettori work e finish servono esclusivamente per l’algoritmo di verifica dello stato sicuro



Il codice dell’algoritmo è il seguente (si noti che ad esempio con needi si intende la riga i-esima della matrice need):


Procedure barbiere ;

begin

if (requesti > needi) then < errore >

else if (requesti > availablei) then wait (Pi)

else

begin

verifica_stato_sicuro (Si) ;

if (Si) then alloca_risorse else

begin

wait (Pi) ;

ripristina _struttura_dati

end ;

end ;

end.


Il generico processo effettua una richiesta di risorse; se tale richiesta è superiore alla necessità residua si ha un errore, mentre se è inferiore si passa a confrontare la richiesta con l’effettiva disponibilità. Se le risorse disponibili non sono sufficienti a soddisfare la richiesta, il processo dovrà mettersi in attesa. Contrariamente, si vaglia la possibilità di concedere le risorse: allo scopo si esamina la condizione di stato sicuro (relativamente a ciò che succederebbe se le risorse fossero effettivamente assegnate), richiamando la procedura che segue. Se la condizione di stato sicuro risulta contraddetta il processo dovrà ancora mettersi in attesa, altrimenti si concede l’allocazione. Si noti che in caso di attesa occorre risistemare la struttura dati, che è stata modificata dall’esecuzione della procedure verifica_stato _sicuro.

Nel testo seguente compaiono relazioni di ‘minoranza fra due vettori’. Affermando che un vettore è minore o uguale a un altro intendiamo dire che la relazione di minoranza è verificata componente per componente (ad es.: (2,0,1) < = (5,0,2)).


procedura verifica_stato_sicuro (Si = boolean) ;

var j : integer ;

flag : boolean ;

begin

Si := true ;

/* viene riprodotta la situazione che si verrebbe a creare

in caso di effettiva assegnazione */

available : = available - request;

allocationi : = allocationi + request;

needi : = needi - request;

/* lo stato di arrivo sarebbe sicuro? Le istruzioni seguenti lo verificano */

work : = available ;

for j : = 1 to n do finish [j] : = false ;

repeat

flag : = true ;

for j : = 1 to n do

if finish[j] = false and needj < = work then

begin

work : = work + allocation;

finish[j] : = true ;

flag : = false 

end

until flag ;

j : = 0 ;



repeat

j : = j + 1

until not finish[j] or j = n ;

Si := finish[j] ;

end ;


Affinché le risorse vengano allocate deve risultare ‘Si = true’. L’assegnazione del valore logico ad Si avviene nell’ultima istruzione di questa procedura, e, perché il valore assegnato sia true, il vettore finish deve essere composto interamente da true (si deve cioè giungere alla conclusione che ogni processo possa finire la propria esecuzione). Si consideri allora il primo ciclo Repeat until. Affinché tutti gli n elementi di finish (che vengono inizializzati a false) siano posti a true, devono essere eseguite per ogni j I 1..n le istruzioni contenute nella sezione begin.. end. Se si prospetta l’eventualità che, in seguito all’assegnazione, il fabbisogno degli n processi non possa essere più appagato (needi > work), l’ingresso a tali istruzioni viene precluso. È sufficiente che ciò accada anche per un solo degli indici j perché ne consegua la mancata assegnazione. Si noti per inciso che il ciclo repeat until viene percorso una sola volta unicamente nel caso limite in cui la condizione di fabbisogno insoddisfatto si verifichi per tutti e n i processi, altrimenti sempre due volte.


RILEVAMENTO DEL DEADLOCK E SUO SUPERAMENTO. Supponiamo ora che il sistema non utilizzi alcuno strumento per evitare il deadlock. In tal caso, un eventuale deadlock può essere rilevato solo dopo la sua occorrenza e pertanto il SO deve fornire due algoritmi:

- un algoritmo per rilevare la presenza di un deadlock;

- un algoritmo per eliminare la condizione di deadlock.


L’algoritmo per la rivelazione dello stato di deadlock viene proposto di seguito.


Procedure Test_deadlock (var deadlock : boolean) ;

var i : integer ;

flag : boolean ;

begin

work : = available ;

for i : = 1 to n do

finish [i] : = true ;

if allocationi < > 0 then finish [i] : = false ;

repeat

flag : = true ;

for i : = 1 to n do

if finish [i] = false and requesti < = work then

begin

work : = work + allocation;

finish [i] : = true ;

flag : = false ;

end ;

until flag ;

i : = 0 ;

repeat

i : = i + 1

until not finish [i] or i = n ;

deadlock : = finish [i] ;

end ;


Vengono usati i vettori available, work e finish e la matrice allocation della struttura dati del caso precedente, con identico significato; request è invece una matrice n x m che indica la richiesta attuale dei processi: ‘ request i,j = k ’ significa che il processo i sta richiedendo altre k istanze della risorsa j.

Si noti la notevole somiglianza esistente fra questo algoritmo e quello subito precedente. Cambiano, oltre all’istruzione finale:

- la parte iniziale. In questo caso non c’è evidentemente una situazione da simulare, ma occorre analizzare una situazione già esistente. Quindi, la struttura dati non viene modificata. Inoltre il vettore finish viene posto a false solo per i processi non ancora terminati, ossia laddove allocationi <> 0.

- la condizione needj < = work, che qui diventa requesti < = work. Ai fini dell’ipotesi di terminazione di un processo i viene considerata attendibile la richiesta di risorse piuttosto che l’effettivo bisogno. È evidente che se requesti < = work è garantito il fatto che il processo Pi non è attualmente coinvolto in un deadlock. Naturalmente Pi potrebbe stare effettuando per qualche motivo una richiesta inferiore al bisogno reale, e in un successivo momento potrebbe sovrapporre ulteriori richieste, magari fino al punto di causare un deadlock, ma non c’è problema: ciò sarebbe certamente rilevato alla successiva esecuzione dell’algoritmo.


Quando è consigliabile attivare l’algoritmo di rilevamento del deadlock? Osserviamo che il deadlock può verificarsi solo se accade che un processo fa una richiesta che non può essere immediatamente soddisfatta. Si può pensare quindi di attivare l’algoritmo ogni volta che si presenta questa eventualità, ma tale scelta sarebbe palesemente inopportuna poiché aumenterebbe in maniera intollerabile i tempi di calcolo. Alternative più plausibili consistono nell’attivare l’algoritmo periodicamente (ad es. ogni ora), oppure ogni volta che la CPU risulta sottoutilizzata, ad esempio ogni volta che l’aliquota di utilizzo della CPU scende al di sotto del 40%. Infatti, un deadlock ha generalmente l’effetto di rendere inefficienti le prestazioni del sistema e in particolare di causare una caduta nell’uso del processore.


Veniamo ora brevemente alla questione dell’eliminazione dello stato di deadlock. Un deadlock può essere eliminato in due modi:

1) mediante l’abort di uno o più dei processi che si trovano in attesa circolare. Si può pensare di abortire simultaneamente tutti i processi che si trovano in deadlock, oppure di abortirne uno per volta, verificando dopo ogni abort se esistono ancora processi in deadlock. Entrambe le strategie possono risultare molto dispendiose: la seconda per ovvie ragioni; la prima perché i processi abortiti potrebbero avere effettuato già parecchi calcoli, e i loro risultati vengono così irrimediabilmente persi.

2) mediante prerilascio delle risorse. Si tolgono con la forza le risorse ad uno dei processi bloccati, mettendole a disposizione di altri; se ciò non basta si fa la stessa cosa via via con tutti gli altri. I processi che subiscono il prerilascio vanno posizionati in uno stato dal quale poi possano essere riavviati (ROLLBACK).


Scarica gratis Algoritmo del banchiere
Appunti su:










Accedi al tuo account
Scarica 100% gratis e Invia appunti, 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 ...