SISTEMI OPERATIVI

<p>Rilevazione di un deadlock adopera strutture dati variabili nel tempo simili a quelle dell'algoritmo del banchiere:</p>
<ul>
  <li>Available: vettore di lunghezza m, indica il numero di risorse disponibili per ogni tipo.</li>
  <li>Allocation: matrice n x m, definisce il numero di risorse di ciascun tipo attualmente assegnate a ogni processo.</li>
  <li>Request: matrice n x m, indica la richiesta corrente di ogni processo. Se Request [i, j] = k, allora il processo P richiede altre k istanze della risorsa di tipo R .</li>
</ul>
<p>L'algoritmo di rilevazione controlla ogni possibile sequenza di allocazione per i processi da completare</p>
<p>Algoritmo di rilevazione:</p>
<ol>
  <li>Supponiamo che Work e Finish siano rispettivamente vettori di lunghezza m e n. Inizializziamo:</li>
  <ul>
    <li>Work = Available</li>
    <li>Per i = 1,2, ..., n, se Allocation [i,·] = 0, allora Finish[i] = false; altrimenti, Finish[i] = true.</li>
  </ul>
  <li>Si cerca un indice i che soddisfi entrambe le condizioni seguenti:</li>
  <ul>
    <li>Finish[i] = false</li>
    <li>Request ≤ Work[i]</li>
  </ul>
  <li>Se una tale i non esiste,</li>
</ol>

passare al punto 4.3. Work = Work + Allocation [i,·]Finish[i] = true

passare al punto 2.4. Se Finish[i] = false per qualche i, ,allora il sistema è in uno stato di deadlock e particolarmente il processo P è in stallo

L'algoritmo richiede 2m x n operazioni per rilevare se il sistema è in un deadlock.

Esempio:

di rilevazione:

Uso dell'algoritmo

Quando e con quale frequenza invocare l'algoritmo di rilevazione dipende da:

▪ Con quale frequenza può accadere un deadlock?

▪ Quanti processi saranno coinvolti nel deadlock quando questo si verificherà?

di rilevazione dovrebbe essere

o Se il sistema è soggetto frequentemente a deadlock, l'algoritmo invocato spesso. Si ricordi che:

▪ Le risorse assegnate a processi in deadlock saranno bloccate fino alla rimozione dello stallo

▪ Il numero di processi coinvolti in un deadlock può crescere nel tempo.

o I deadlock avvengono solo quando una richiesta di risorse

• Il ripristino dal deadlock può avvenire:
  • a carico dell’utente che viene informato dal sistema dell’esistenza di uno stallo o per via automatica;
  • abortendo uno o più processi o requisendo risorse detenute da processi in deadlock.
• Abort di processi:
  • Abortire tutti i processi in deadlock (i risultati parziali dell’elaborazione di tutti i processi coinvoltio devono essere scartati).
  • Abortire un processo alla volta fino ad eliminare il ciclo di

deadlock (è notevole l’overhead poiché dopoo lanciare l’algoritmo di rilevazione).

ogni abort si deveo In quale ordine devono essere terminati i processi?

• Priorità del processo
• Per quanto tempo il processo ha elaborato e per quanto tempo ancora il processo proseguirà primadi completare l’operazione pianificata
• Quanti e quali tipi di risorse sono state adoperate dal processo.
• Di quante altre risorse il processo necessita per completare l’elaborazione
• Quanti processi devono essere terminati
• Caratteristica del processo (interattivo o batch)

Rilascio anticipato delle risorse

Selezione della vittima (minimizzazione del costo)

• I fattori di costo includono:
• Numero di risorse occupate.
• Per quanto tempo il processo ha elaborato e per quanto tempo ancora il processoproseguirà prima di completare l’operazione pianificata.

Rollback (permette di riportare ad una versione o stato precedente)

Prelazionando una risorsa da un processo occorre riportarlo ad uno stato sicuro e far ripartire il processo da quello stato.

La soluzione più semplice è un rollback totale del processo.

Starvation

In un sistema in cui la selezione della vittima è basata soprattutto sui fattori costo, alcuni processi potrebbero essere sempre scelti come vittime.

Occorre verificare che un processo possa essere selezionato solo un numero limitato di volte.

Il numero di rollback viene incluso nei fattori costo

CAPITOLO 9: MEMORIA CENTRALE

• Per essere eseguito un programma deve essere portato dalla memoria di massa in memoria centrale e essere attivato come processo.
• La memoria è sostanzialmente un vettore di word ciascuna delle quali è accessibile singolarmente (dotata di un indirizzo specifico).
• Ciclo istruzione-esecuzione:
• Prelievo di una istruzione dalla memoria centrale in base al valore del program counter
• Decodifica dell'istruzione

Prelievo di operandi dalla memoria ed esecuzioneo Memorizzazione dei risultati in memoria

• Dal punto di vista della memoria, in ingresso/uscita abbiamo solo un flusso di indirizzi
• Coda di entrata: processi su disco che sono in attesa di essere caricati in memoria centrale perl'esecuzione.
• I programmi utente passano attraverso più stadi prima di essere eseguiti (compiling, linking, loading)

Collegamento degli indirizzi:

Il collegamento delle istruzioni e dei dati agli indirizzi di memoria viene effettuato mediante la seguente successione di passi:

• Fase di compilazione: se in fase di compilazione si conosce l'alocazione del processo in memoria, allora si può generare un codice assoluto; se la locazione di partenza cambia bisogna ricompilare il codice.
• Fase di caricamento: se al momento della compilazione non è nota l'alocazione del processo in memoria, il compilatore deve generare un codice rilocabile

Il linking finale è rinviato

fino all'istante di caricamento

Modificandosi l'indirizzo di partenza, c'è la necessità di modificare il solo codice utente per incorporare il valore cambiato.

• Fase di esecuzione: se il processo può essere spostato, durante l'esecuzione, da un segmento di memoria a un altro, allora il collegamento dell'esecuzione deve essere ritardato fino al momento dell'esecuzione.

Necessita di un hardware specifico.

Indirizzamento logico e fisico:

• Spazio di indirizzamento logico (insieme di tutti gli indirizzi logici generati da un programma).