Consideriamo un sistema di n processi {p₀, p₁, ... ,p_n-1}

Ogni processo ha una sezione di codice detta sezione critica:

• Il processo potrebbe cambiare variabili comuni, aggiornare tabelle, scrivere files ecc.

• Quando un processo è in una sezione critica, nessun'altro processo dovrebbe essere nella sua sezione critica

Ogni processo deve chiedere il permesso per entrare nella sezione critica nella entry section.

Morale della favola: Ogni processo ha una porzione di codice in cui dice espressamente di voler agire per conto suo senza che nessun altro processo "gli dia fastidio"; questo perché in questo modo evita di fare danni (come nel caso dell'incremento e decremento di variabili da due processi diversi).

L'idea è la seguente:

do{
    //entry section
        critical section
    //exit section
        remainder section
}while(true);

Ad un certo punto il processo richiede l'ingresso, entra in sezione critica, e poi esce. Il tutto è racchiuso all'interno di un while true.

1. Mutual Exclusion: Se un processo P1 è all'interno della sezione critica, nessun altro processo può eseguire la propria sezione critica.

2. Progresso: Supponiamo che un processo voglia entrare nella sua sezione critica. Se non ci sono altri processi che vogliono entrare nella loro sezione critica, esso non può essere ritardato.

3. Attesa limitata: se il processo è in attesa per entrare nella sua sezione critica, un altro processo non può "scavalcare" il processo in attesa entrando nella sua sezione critica. Indipendentemente dal timing dei processi, prima o poi ogni processo deve avere la possibilità di entrare nella sua sezione critica. Esiste un limite di volte in cui un processo può entrare nella sua sezione critica.

Questa soluzione vale solo per due processi, e sopratutto è una soluzione di tipo software; inoltre potrebbe non funzionare sui sistemi moderni.

L'ipotesi è quella di ragionare solo su due processi, questi due quindi si contendono l'accesso alla propria sezione critica. Assumiamo che le operazioni di load e store in linguaggio macchino siano atomiche (ovvero non possono essere interrotte).

I due processi condividono due variabili:

• una variabile intera che dice di chi è il turno per accedere (turn).

• Variabile booleana, un flag che indica il desiderio di entrare nella sezione da parte dei processi (fag[2]).

while(true){
    flag[i] = true;
    turn = j;
    while(flag[j] && turn == j)
        ;
    /* sezione critica */
    flag[i] = false;
    /* sezione di reminder */
}

Nonappena il processo desidera entrare nella propria sezione critica, pone il proprio flag a true, manifestando quindi l'interesse ad entrare.

Successivamente, assegna la variabile turn all'altro processo, ovvero dice che il turno è dell'altro processo. Dopo questo passaggio c'è un loop che attende vedendo se anche l'altro processo vuole entrare in sezione critica; se flag[j] fosse false, il processo entra direttamente in sezione critica, e turn non viene nemmeno controllata.

Una volta terminata la sezione critica, pone il proprio flag a false, dichiarando di non voler più entrare in sezione critica

Se tutti e due i processi vogliono entrare nella sezione critica, ovvero entrambe le variabili flag sono true, "perde" chi ha salvato per primo il valore turn, e di conseguenza l'altro thread entra nella sua sezione critica (questo perchè ogni processo scrive sulla variabile turn che il turno è dell'altro processo).

🏁 05-14 00:33

I processori moderni, riordinano le istruzioni e le eseguono fuori ordine! Di conseguenza, nel momento in cui il processore non esegue le istruzioni nell'esatto ordine in cui le abbiamo scritte, non c'è nessuna garanzia che il metodo continui a funzionare.

Questo metodo è solo un metodo "didattico", utilizzato per far capire come si può risolvere il problema, anche se essa non è una soluzione plausibile.

La soluzione classica, utilizzata in molti SO quando il processore era singolo, era quello di disabilitare le interruzioni.

Supponiamo di avere un SO tradizionale (CPU singolo); un processo vuole entrare nella sua sezione critica, e quindi non vuole essere interrotto (non vuole perdere la CPU finchè non ha finito). Siccome tutti i meccanismi di commutazione da un processore all'altro, fanno utilizzo del sistema delle interruzioni.

Siccome tutti i processori consentono in hardware di impostare un flag per disabilitare le interruzioni, vuol dire che eventuali segnali di interruzioni vengono congelati finchè questo flag non è nuovamente abilitato.

Questa è sicuramente una soluzione valida per ottenere la mutua esclusione su una piccola porzione di codice. Non è decisamente, però, una soluzione gradevole; questo per diversi motivi, il primo è sicuramente il fatto che è una soluzione funzionante solo su sistemi a singola CPU.

Inoltre la sezione di codice da eseguire in questa modalità deve essere molto breve, proprio perchè in quel periodo il SO è completamente assente.

Ci sono diverse soluzioni hardware adottate sui sistemi moderni:

• Barriere di memoria
• Istruzioni Hardware
• Variabili Atomiche

Il metodo più utilizzato sui sistemi moderni è quello delle istruzioni hardware:

Se in qualche modo mi invento delle operazioni che a livello hardware sono totalmente atomiche e mi permettono di risolvere questo problema, invece di cercare di risolvere il problema via software, risolvo il problema via hardware.

Istruzioni hardware speciali permettono di utilizzare le istruzioni:

• Test-and-set
• Compare-and-swap

boolean test_and_set(boolean *target){
  boolean rv = *target;
  *target = true;
  return rv;
}

Chi progetta il processore, deve garantire di poter eseguire un'operazione simile a quella riportata sopra. Più precisamente, deve garantire che il codice venga eseguito atomicamente, anche in sistemi aventi processori multipli.

Il codice esamina una locazione di memoria, e quindi preleva dalla locazione un valore booleano, del tipo libero/occupato, dopodiché indipendentemente da quello che è stato occupato, scrive all'interno della locazione di memoria "occupato" (true).

Con questo meccanismo si può implementare la sezione critica in maniera molto semplice.

Partiamo dal presupposto che anche su un sistema avente processori multipli, la funzione test_and_set() è sempre una funzione eseguita in maniera atomica, e questo vuol dire che se ci sono due invocazioni della funzione, da due processori diversi sulla stessa locazione di memoria, verrà sempre eseguita prima una e poi l'altra, e mai contemporaneamente.

do{
  while(test_and_set(&lock))
    ;    //do nothing

  // sezione critica

  lock = false;

  // sezione reminder
}while(true);

La sezione critica si può semplicemente proteggere con una test_and_set() che va a prelevare il valore di una variabile lock che originariamente è posta a false.

Questa variabile globale, in condizioni normali (nessun processo vuole accedere alla sezione critica), vale sempre false. Di conseguenza effettuiamo un while su questa variabile, e finchè essa è true (ovvero un processo vuole entrare/è dentro la sua sezione critica) non facciamo nulla.

Appena questa variabile diventa false, vuol dire che possiamo entrare nella nostra sezione critica.

Finita la sezione critica, la variabile lock viene riposta a false, per permettere ad altri processi di accedere alla propria.

il problema di questo tipo di soluzione, è che non è garantita l'attesa limitata; questo perchè un processo potrebbe richiedere (all'infinito) di entrare nella propria sezione critica, lasciando "a bocca asciutta" gli altri processi. Non c'è quindi garanzia che questa soluzione garantisca l'attesa limitata. È possibile utilizzare la test_and_set() che assicuri l'attesa limitata, anche se l'implementazione è più complicata.

La compare_and_swap() è un'altra istruzione che alcuni processori hanno (eseguita atomicamente); questa istruzione effettua uno swap atomico (che non viene interrotto da altri processi).

Servirebbe un'operazione di lettura/scrittura atomica, in modo da leggere il contenuto di una variabile doc e renderlo immediatamente occupato, prima che un altro processo possa "metterci le mani".

La soluzione potrebbe essere quella di usare un'operazione singola o con una coppia di istruzioni atomiche (da eseguire insieme, cosa difficile da fare).

La soluzione realmente adottata sia da RISCV che da MIPS è quella di utilizzare delle istruzioni apposite che permettono di creare una struttura che comunque garantisca l'atomicità, ma utilizzando un "trucco" software.

In particolare, quello che avviene è la presenza di due istruzioni, indipendentemente dalla specifica di formato (lr**.d** rd, dove il .d sta per "double", ovvero un'operazione effettuata a 64bit):

Istruzione load reserved:

lr.d    rd,    (rs1)

Istruzione Store conditional

sc.d    rd, (rs1), rs2

Il load reserved effettua il caricamento in un registro destinazione (rd) a partire da una locazione di memoria indicata dal contenuto di un altro registro (rs1). Fin quì tutto normale (pari al ld).

Questo load è reserved, perchè il processore tiene traccia di quell'indirizzo di memoria; di conseguenza il processore si accorge se un altro processo ha scritto in quel registro prima di me, e posso continua ad effettuare il load finchè non c'è nessun altro che si "mette in mezzo" tra il load e lo store, rendendo il tutto atomico.

Lo store conditional lavora "a braccetto" con l'operazione di load. Questo perchè lo store viene effettuato solo ed esclusivamente se nessun altro, nel frattempo, ha modificato quella locazione di memoria. Se quella locazione di memoria è stata modificata, lo store non viene eseguito, e viene ritornato nel registro rd, che è un terzo registro usato come parametro dell'istruzione, dove viene salvato il risultato dell'operazione, l'esito dell'operazione.

again:    lr.d    a0,    (s4)
                sc.d    a1,    (s4),    s7                // a1 = status
                bne        a1,    zero,    again            //branch if store
                failed
                addi    s7,    a0,    0                        // s7 = loaded value

Viene effettuato un load reserved all'indirizzo s4, dopodiché lo store conditional tenta di scrivere il valore di s7 all'indirizzo s4; in a1 viene ritornato lo stato. Successivamente, controllo sul registro a1 il risultato, e se non è andato a buon fine, salto ad again dove tento nuovamente di effettuare lo store.

🏁 05-14 01:07

L'utilizzo di questo meccanismo per la realizzazione della sezione critica è abbastanza frequente?

Molto spesso capita di avere dei processi che devono accedere alla sezione critica, di conseguenza è ragionevole che il SO fornisca una soluzione nativa.

Di conseguenza capiamo che le soluzioni precedenti sono complicati e generalmente inaccessibili dai programmatori di applicazioni. E' per questo motivo che i progettisti di SO hanno creato dei tool software per risolvere il problema della sezione critica.

la soluzione più semplice è proprio il Mutex Lock:

Proteggiamo la sezione critica prima effettuando un acquire() di un lock, e poi il release() del lock. Una variabile booleana indica se il lock è disponibile oppure no.

Le chiamate acquire() e release() devono essere atomiche, infatti sono solitamente implementate con istruzioni hardware atomiche, come la compare-and-swap.

Ovviamente il problema più chiaro di questa soluzione è proprio l'efficienza, proprio perchè sopratutto sui sistemi a CPU singola, il processo è continuamente in un loop effettuando degli accessi alla memoria, proprio per controllare se la variabile lock è true o false.

In un sistema a CPU singola, quindi, se il processo utilizza la CPU per controllare la variabile, per forza di cose essa non può essere cambiata da altri processi, proprio perchè l'unica CPU disponibile è utilizzata dal processo in questione.

In un sistema a CPU multiple questa soluzione ha senso.

Questa soluzione è ancora in uso tuttora, quindi abbastanza valida. Essa serve a risolvere in modo brillante il problema della mutua esclusione (ovvero entrare in una sezione di codice uno alla volta), ma anche a risolvere problemi di sincronizzazione (ovvero il problema di sincronizzazione su condizione, ovvero attendere finchè non è valida una certa condizione che mi abilita a fare qualcosa).

In qualsiasi sistema operativo, è tuttora presente il supporto ai semafori, possiamo quindi chiamare le due primitive che ci permettono di eseguire operazioni sui semafori. Vengono inoltre utilizzati molto spesso nei sistemi non real time, dove vengono utilizzati altri sistemi di sincronizzazione.

Per "semaforo", in inglese "semaphore", si intende il semaforo utilizzato sulle ferrovie, ben diverso dai semafori stradali, in inglese "traffic light".

Le due operazioni sui semafori, sono chiamate P() e V(), dalle parole olandesi che stanno per rispettivamente wait() e signal().

wait():

wait(S){
    while(S <= 0)
        ; // busy wait
    s--;
}

Pensiamo ad una situazione in cui il semaforo inizialmente vale 1; se l'operazione viene eseguita atomicamente (cosa che accade), e più processi tentano di effettuare una wait(), un solo processo troverà il valore "1", azzera quindi il semaforo con S--, gli altri processi trovano 0 ed attendono.

signal():

Si rilascia la mutua esclusione con questa segnalazione; la signal semplicemente incrementa il valore del semaforo:

signal(S){
    s++;
}

Se voglio effettuare la mutua esclusione, basta che abbia un semaforo inizializzato ad 1, il protocollo di ingresso è chiamare un wait(), il protocollo di uscita è chiamara signal().

Il semaforo non viene mai decrementato al di sotto di zero, questo perchè il codice prevede l'esecuzione di S-- solo nel momento in cui S > 0, e quindi il semaforo vale sempre o zero, o più di zero.

Questo è il modo classico di definire il semaforo.

Diamo per assodato che la wait() e la signal() siano operazioni eseguite atomicamente. Usando questa soluzione, non risolviamo il problema che avevamo con la test-and-set(), ma lo trasferiamo ad un altro livello.

Di conseguenza, per avere la mutua esclusione su queste operazioni, esse dovranno essere implementate a basso livello, con dei meccanismi, come la test-and-set(), che permettano alle operazioni di essere eseguite atomicamente.

Il busy waiting, cosiddetta attesa attiva, è un modo di attendere che il semaforo divenga 1.

Visto che il loop viene implementato a bassissimo livello da chi programma il sistema operativo, possiamo "aspettare" in un modo più intelligente: sospendiamo il processo, e lo riattiviamo finchè la condizione S non ritorna "vera".

Supponiamo che un processo sia entrato nella zona critica (trovando 1), gli altri processi trovano 0, nel momento in cui viene eseguita la segnalazione, chi entra (valore 1)?

Con questa soluzione non è detto che il processo in attesa da più tempo sia il primo ad entrare in zona critica (o altro); il semaforo non prevede una disciplina di risveglio di tipo FIFO.

L'ordine di esecuzione dipende dal modo in cui il semaforo viene implementato.

In generale il semaforo è composto da una variabile intera, in alcune implementazioni viene fornito un semaforo di tipo binario, per la sua facilità di implementazione.

Counting semaphore: valore intero avente range su un dominio non ristretto.

Semaforo binario: valore intero avente range solo tra 0 ed 1; stesso concetto del mutex lock

Consideriamo P1 e P2, ed abbiamo bisogno che S1 avvenga prima di S2; creiamo un semaforo synch inizializzato a zero:

P1:
    S1;
    signal(synch);
P2:
    wait(synch);
    S2;

Bisogna garantire che due processi non possano eseguire wait() e signal() sullo stesso semaforo allo stesso momento.

I semafori possono essere implementati da una terza persona, che a noi non interessa.

Supponiamo che il semaforo sia stato implementato con le operazioni:

• block: pone il processo invocando l'operazione sulla waiting queue appropriata

• wakeup: rimuove uno dei processi nella waiting queue ed pone il processo nella ready queue.

Per eseguire l'operazione in maniera atomica, chi implementa il semaforo sarà costretto ad usare una test-and-set() a basso livello, quindi l'attesa attiva è stata apparentemente eliminata, ma è ancora presente.

Nonostante ciò questo metodo continua ad essere efficiente, proprio perchè l'attesa attiva è presente solo per una piccola porzione di codice, ovvero quella nei "pressi" della test-and-set(), e quindi nella sezione critica (utilizzando i semafori) posso scrivere un codice anche esageratamente lungo.

Tutte le attese regolate da spinning (spin loop, ovvero loop di attesa) sono, e devono, essere tutte attese brevi, mentre tutte le attese regolate da semafori, non richiedono attese regolate da spin loop, e quindi l'efficienza è buona.

wait(semaphore *S){
    S->value--;
    if(S->value < 0){
        add this process to S->list;
        block();
    }
}


signal(semaphore *S){
    S->value++;
    if(S->value <= 0){
        remove a process P from S->list;
        wakeup(P);
    }
}

In questo tipo di implementazione, il semaforo può diventare anche negativo; se ad esempio il semaforo vale -3, vuol dire che ci sono 3 processi in attesa.

Bisogna notare che questo tipo di implementazione è un'invenzione di Silberschatz, e solitamente i semafori sono implementati come detto precedentemente, ovvero con valori pari a zero, o maggiore di zero.

Cosa succede se utilizzo male i semafori?

Solitamente, per entrare nella sezione critica, pongo un wait() prima della sezione, ed un signal() alla fine; ma che succede se dimentico di chiamare signal() dopo aver eseguito la sezione critica?

Esiste un meccanismo ad alto livello che si accorga del mio errore? Risposta breve: no.

Per questo motivo, non bisogna pensare che i semafori siano semplici da usare per via della loro accessibilità; per questo motivo, dopo gli anni 70 si è iniziato a pensare a dei nuovi meccanismi, più facili da usare, per risolvere i problemi di sincronizzazione.

I semafori sono quindi sicuramente una soluzione per la sincronizzazione più ad alto livello della test-and-set() vista precedentemente, ma non è la soluzione perfetta.

FINE LEZIONE 8