Gestione della Concorrenza e Deadlock nei Sistemi Operativi

Parbegin e Parend

Parbegin / Parend è una struttura utilizzata per indicare l'esecuzione parallela, definendo l'inizio e la fine di una selezione di esecuzione concorrente:

• Una dichiarazione che indica che l'esecuzione sequenziale deve essere suddivisa tra diversi flussi di esecuzione parallela.

La sua forma globale (secondo Dijkstra) è la seguente:

parbegin Proposizione1; Proposizione2; Proposizione n; parend

Mutex (Mutua Esclusione)

Il Mutex si verifica quando un processo, durante la condivisione dei dati, impedisce l'accesso a tutti gli altri processi contemporaneamente. Si applica quando un processo accede ai dati condivisi; in questo caso, gli altri processi che eseguono operazioni non in conflitto sono autorizzati a procedere simultaneamente.

Sezioni Critiche

Si parla di sezioni critiche quando un processo sta accedendo a dati condivisi. Quando un processo si trova in una sezione critica:

• Tutti gli altri processi sono esclusi dalle proprie sezioni critiche.
• Gli altri processi possono continuare l'esecuzione al di fuori delle loro sezioni critiche.
• Quando un processo lascia la sua sezione critica, deve essere consentito il passaggio al successivo processo in attesa di entrare nella propria sezione critica.
• Viene concesso uno stato speciale al processo, il quale ha accesso esclusivo ai dati condivisi, mentre tutti gli altri processi che richiedono l'accesso restano in attesa.
• Un programma non dovrebbe mai essere bloccato indefinitamente nella sua sezione critica; pertanto, le sezioni critiche devono essere accuratamente codificate.
• Al termine, sia in modo volontario che involontario (per pulizia dopo un recesso), il sistema operativo deve rilasciare il mutex in modo che altri processi possano accedere alle loro sezioni critiche.

Deadlock (Stallo)

Il Deadlock si verifica quando un processo è in attesa di un particolare evento che non si verificherà mai. In una situazione di stallo, il sistema si trova in una condizione di blocco che coinvolge uno o più processi.

Esempio di struttura: OPZIONI PROCEDIMENTO (compito principale), attendere (eventi); FINE;

Traffico e Deadlock

Lo standard più comune sulla strada prevede che un'auto a un incrocio di quattro strade debba cedere la precedenza alla vettura che si trova alla propria destra. Questa regola funziona anche se sono presenti solo due o tre auto. Per esempio, se arrivano solo auto da nord e da ovest, l'auto a nord attende il passaggio di quella a ovest. Tuttavia, se quattro vetture arrivano contemporaneamente, tutte potrebbero astenersi dall'impegnare l'intersezione, causando un deadlock. Se, al contrario, tutte ignorano le regole e avanzano contemporaneamente, ogni vettura occuperà una risorsa (un quadrante dell'incrocio) ma non potrà proseguire perché la risorsa successiva è già occupata da un'altra vettura. Anche in questo caso, si verifica un punto morto.

Deadlock di una risorsa semplice

Molte delle situazioni di stallo in un sistema operativo si sviluppano a causa della ritenzione di risorse standard (ovvero risorse utilizzabili da un solo utente alla volta, talvolta chiamate risorse utilizzabili in serie):

• La risorsa può essere usata da un solo utente alla volta.
• Ogni processo è in attesa che l'altro liberi una risorsa.
• La risorsa detenuta non sarà rilasciata finché l'altro utente non rilascia la propria.
• L'ultimo processo non rilascia la risorsa sospesa finché l'utente non rilascia il primo processo mantenuto.
• Si genera quindi un'attesa circolare.

Rilevazione del Blocco e Indefinito Rinvio

La rilevazione del blocco consiste nell'identificare quali processi e risorse sono parte di uno stallo. Qualsiasi processo che faccia parte di un ciclo è bloccato; se non ci sono cicli, il sistema non è in deadlock.

Il problema del Rinvio Indefinito (Starvation)

Si tratta di uno stato del sistema in cui un processo non riesce mai a ottenere le risorse necessarie a causa delle decisioni di pianificazione (scheduling). È causato spesso da politiche di allocazione sbilanciate. Per evitare ciò, si utilizza l'invecchiamento (aging), che aumenta gradualmente la priorità di un processo in attesa di una risorsa.

Interlock nei sistemi di Spool

I sistemi di spool vengono utilizzati per aumentare la capacità di esecuzione del sistema, dissociando un programma dalla lentezza dei dispositivi di output. Tuttavia, sono soggetti a deadlock:

• Per accelerare l'esecuzione, le linee di uscita vengono inviate a un dispositivo veloce (disco), dove restano temporaneamente fino alla stampa.
• Diversi lavori parzialmente completati possono bloccarsi se lo spazio su disco si riempie prima del completamento.
• Recuperare da tale stallo potrebbe richiedere il riavvio del sistema con la perdita del lavoro svolto.
• Un modo meno drastico è l'eliminazione di uno o più processi per liberare spazio nel file di spool.
• In fase di generazione del sistema operativo, viene indicato lo spazio libero per i file di spool.
• Per ridurre la probabilità di deadlock, è consigliabile fornire uno spazio notevolmente maggiore del necessario.
• Una soluzione comune è limitare lo spooler impedendo ulteriori letture quando i file raggiungono il 75% della capacità.
• I sistemi attuali sono più sofisticati: permettono l'inizio della stampa prima della fine del lavoro, svuotando dinamicamente lo spazio.

Le quattro condizioni di Deadlock

Coffman, Elphick e Shoshani hanno identificato quattro condizioni necessarie affinché si produca uno stallo:

1. Mutua esclusione: i processi rivendicano il controllo esclusivo delle risorse.
2. Possesso e attesa: i processi mantengono le risorse già assegnate mentre attendono di ottenerne altre.
3. Non prelazionabilità (No preemption): le risorse non possono essere sottratte ai processi finché non vengono rilasciate volontariamente.
4. Attesa circolare: esiste una catena chiusa di processi in cui ogni processo detiene una risorsa richiesta dal successivo.

Recupero dal Deadlock

Esistono diversi fattori che ostacolano il recupero da una situazione di stallo:

• Potrebbe non essere chiaro se il sistema sia effettivamente bloccato.
• Mancanza di mezzi efficaci per sospendere e riprendere un processo senza un sovraccarico eccessivo.
• Il recupero di uno stallo su larga scala richiede un'enorme quantità di lavoro.

Criteri di eliminazione dei processi

I processi possono essere eliminati secondo un ordine di priorità, ma sorgono delle difficoltà:

• Se le priorità non esistono, l'operatore deve prendere una decisione arbitraria.
• Le priorità possono essere confuse da scadenze imminenti (pianificazione a tempo determinato).
• La decisione ottimale su quale processo rimuovere può richiedere un notevole sforzo computazionale.