Sistemi operativi: algoritmo del banchiere, Starvation, definizione di Page Fault, Buddy System, barriere

Argomenti più comuni esame di Sistemi Operativi (Ingegneria informatica ed elettronica)

22. Algoritmo del banchiere

Stato sicuro: uno stato si dice sicuro se esiste una sequenza di altri stati che porta tutti i processi ad ottenere le risorse necessarie (e quindi terminare) altrimenti viene detto non sicuro. Per evitare i deadlock è sufficiente evitare gli stati non sicuri.

Algoritmo del banchiere. Tratta risorse multiple. Ogni processo deve dichiarare il numero massimo di risorse necessarie (prima del suo avvio). Se un processo richiede una risorsa che non è disponibile, rimane in attesa che essa venga riassegnata. Dopo che un processo ha ottenuto tutte le risorse necessarie, le deve rilasciare in un tempo finito. Una richiesta viene evasa solo se porta in uno stato ancora sicuro altrimenti il processo deve attendere. Tuttavia,

Questo algoritmo presuppone una conoscenza completa del sistema (svantaggio). Inoltre, una richiesta viene evasa solo se porta in uno stato ancora sicuro, altrimenti il processo deve attendere.

Mutua esclusione: se non vi sono risorse assegnate in modo esclusivo ad un singolo processo, allora non vi saranno deadlock.

Hold and Wait: occorre evitare che processi che detengono risorse rimangano in attesa di ulteriori risorse.

Ci possono essere varie soluzioni: un processo richiede immediatamente tutte le risorse di cui ha bisogno, se non sono disponibili attende. Nascono nuovi problemi: un processo non sempre sa quello di cui ha bisogno nel corso dell'esecuzione; l'uso delle risorse non è ottimizzato (rimangono risorse spesso inutilizzate); vi è il rischio che un processo che ha bisogno di molte risorse rimanga in attesa per tempi molto lunghi. Un modo leggermente diverso è quello di imporre che un processo rilasci temporaneamente le risorse detenute prima di una nuova.

richiesta. "nessun prerilascio" La terza condizione è di fatto inutilizzabile. Attesa Circolare: può essere eliminata in vari modi: un processo può richiedere una sola risorsa per volta; le risorse sono numerate e possono essere richieste solo secondo l'ordine numerico (il filosofo 4 non può richiedere la forchetta 4 prima della forchetta 1). Una variante richiede semplicemente che la nuova risorsa debba avere una etichetta maggiore di tutte quelle detenute.

23. Starvation A differenza del deadlock, il quale coinvolge necessariamente più processi legati tra loro che si bloccano l'uno l'altro, la Starvation è relativa al blocco del singolo processo. Un processo non può procedere perché altri processi detengono sempre una risorsa di cui ha bisogno (la richiesta del processo non viene mai soddisfatta). Tecnicamente, il processo potrebbe ottenere la risorsa, ma non l'ottiene perché: - Ha bassa

priorità – La temporizzazione della richiesta della risorsa è errata – L'algoritmo per l'allocazione delle risorse è costruito male

Esempi di starvation:

• processi batch con bassa priorità in un sistema time-sharing
• attraversare una strada trafficata (trasmissione su bus, protocollo di token)

Soluzioni:

• opportunità: ogni processo ha una percentuale adeguata di tutte le risorse
• tempo: la priorità del processo viene aumentata se il processo aspetta per un tempo troppo lungo

Definizione di Page Fault

Se una pagina non mappata in memoria fisica viene richiesta, la MMU genera un interrupt della CPU al SO detto PAGE FAULT, dopo il quale il SO dovrà occuparsi di individuare un frame da rimpiazzare con la pagina virtuale richiesta. Il SO sceglie un frame di pagina poco utilizzato e salva il suo contenuto su disco, quindi recupera la pagina referenziata e la alloca nel frame appena liberato (fetching della pagina).

cambia la mappa e riparte con l'istruzione bloccata.