Mutua_esclusione

I processi spesso necessitano di scambiare tra di loro informazioni per coordinarsi.

Le questioni fondamentali da considerare nell’IPC sono:

• scambio di informazioni: come un processo trasferisce dati ad un altro processo
• mutua esclusione: assicurarsi che due o più processi non interferiscano tra di loro quando accedono a risorse condivise
• sequenziamento corretto: garantire che le operazioni avvengano nell'ordine giusto, quindi definire regole di sincronizzazione quando sono presenti delle dipendenze tra processi

Race conditions

I processi che lavorano insieme possono avere una risorsa condivisa, come uno storage comune dove ognuno può scrivere e leggere.

Esempio del print spooler

Quando un processo vuole stampare un file, inserisce il nome del file nella spooler directory. Un processo daemon, periodicamente controlla questa directory e se ci sono file, li stampa e rimuove il nome del file stampato. Immaginiamo ora che esistano due variabili :

• out : punta al prossimo file da stampare
• in : punta al prossimo slot disponibile per un nome di file

In un certo istante gli slot da 0 a 3 sono disponibili e da 4 a 6 sono pieni. Quasi contemporaneamente due processi A e B vogliono inserire un nuovo nome file da stampare :

Quello che può succedere è :

• A legge in=7 e memorizza 7 in una sua variabile next_free_slot
• un clock interrupt blocca A e la CPU decide di switchare a B
• B fa la stessa cosa di A e anche lui in una sua variabile next_free_slot memorizza 7
• B continua e scrive il nome del file nello slot 7 e aggiorna in=8, e poi va a fare altro
• A riprende da dove era, vede next_free_slot=7 e scrive il nome del file nello slot 7, sovrascrivendo quello di B e poi aggiorna in=8 in questo caso il processo B non avrà mai un output della stampa del file che voleva.

Situazioni del genere si chiamano race conditions, dove la lettura/aggiornamento di dati condivisi non sono azioni atomiche portando ad errori.

Regioni critiche :luc_alert_circle:

Per evitare che più processi accedano a dati condivisi nello stesso momento, dobbiamo utilizzare la mutua esclusione.

Affinché una soluzione di mutua esclusione sia considerata efficiente, devono essere soddisfatte 4 condizioni:

• mutua esclusione : solo un processo può trovarsi all’interno della sua regione critica (con “sua” si intende che è lui che possiede la regione critica) #review
• assenza ipotesi: nessuna ipotesi deve essere fatta sulle velocità dei processi o sul numero di CPU del sistema
• no-blocco esterno: un processo fuori la sua regione critica non deve bloccare altri processi
• attesa limitata: nessun processo deve stare in attesa all’infinito per entrare nella sua regione critica

Per esempio consideriamo due processi A e B che tentano di accedere ad una risorsa critica (comportamento desiderato):

• tempo T1: A sta eseguendo dei calcoli e accede alla memoria condivisa (regione o risorsa critica)
• tempo T2: B tenta di accedere alla memoria condivisa, ma viene bloccato finché A non finisce con la risorsa critica in questione
• tempo T3: A ha finito di utilizzare la risorsa e esce, quindi B può accedere alla risorsa critica

Mutua esclusione con busy waiting :luc_timer_reset:

Per ottenere la mutua esclusione è possibile utilizzare le tecniche del busy waiting (attesa attiva), che si basano sull’idea che mentre un processo è nella regione critica, gli altri continuano a girare in un loop attivo controllando ripetutamente se risorsa è libera, invece di essere sospesi dal kernel.****

Le possibili tecniche sono:

• disabilitare gli interrupt
• utilizzare delle variabili per il lock (blocco)
• alternanza stretta
• soluzione di Peterson #review
• istruzione TSL (Test and Set Lock)

Disabilitare gli interrupt :luc_zap_off:

Il principio di funzionamento di questa tecnica è che ciascun processo:

1. disabilita tutti gli interrupt dopo essere entrato nella sua regione critica
2. ri-abilita gli interrupt subito prima di uscirne

Grazie alla disabilitazione degli interrupt, alla CPU non arrivano i clock interrupt (e altri tipi di interrupt), e quindi non può commutare il controllo su un altro processo.

Il problema è che funziona solo per sistemi a CPU singola.

Variabili di lock :luc_lock: :luc_unlock:

Si tratta di una tecnica software semplice, ovvero quello di utilizzare una variabile condivisa (lock) per bloccare la risorsa:

• lock=1 $⟹$ risorsa occupata (blocked)
• lock=0 $⟹$ risorsa libera (unblocked)

Il problema è che le “corse” si verificano ora sulla variabile condivisa.

Alternanza stretta (o rigorosa) :luc_separator_vertical:

La tecnica dell’alternanza stretta si basa sull’utilizzo di variabile interna condivisa chiamata turn, che indica a quale processo è permesso entrare nella regione critica.

Il problema di questa tecnica, è che se supponiamo che:

1. P0 entra nella sua RC (regione critica) ed esce impostando turn=1
2. P0 va ora nella usa RNC (regione NON critica) a fare altro (e ci rimane per un po)
3. arriva P1 che vuole entrare nella sua RC, e ci entra siccome turn=1, fa il suo lavoro ed esce e imposta turn=0
4. P1 ora va nella sua RNC
5. P1 vuole rientrare nella RC, ma ancora turn=0 (siccome toccherebbe a P0 entrare nella sua RC) quindi si crea un blocco, siccome P1 deve aspettare che P0 rientri nella sua RC, esca e imposti turn=1.

Soluzione di Peterson :luc_pocket:

\Nel 1981, Peterson scoprì un modo per realizzare la mutua esclusione, che combina l’idea dell’alternanza dei turni e quella delle variabili lock.

L’idea di basa su :

1. enter_region(process): processo chiama questa funzione prima di accedere nella sua regione critica
2. leave_region(process): processo chiama questa funzione dopo che ha terminato con la sua regione critica
3. turn: indica a chi spetta di entrare nella regione critica
4. interested[N]: indica quali sono i processi “interessati” ad entrare nella regione critica (N=2, avremo due processi inizialmente settati a 0 e 0)

#define N 2
#define TRUE 1
#define FALSE 0
 
int turn;  // stabilisce a chi tocca
int interested[N];  //interesse tutti inizialmente a 0
 
void enter_region(int process){
	
	int other = 1 - process;
	interested[process] = TRUE;
	turn = process;
	while (turn == process && interested[other] == TRUE);
	
}
 
void leave_region(int process){
 
	interested[process] = FALSE;
}

Anche se i due processi invocassero, quasi contemporaneamente la procedura, grazie alla condizione del while, il primo partirebbe appena il secondo cambia turn.

---

Semafori_Mutex