cerca
Sistemi Operativi - Appunti caotici
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Sistemi Operativi - Appunti caotici

Torna alla pagina di Sistemi Operativi


 :: Appunti caotici ::

Lezione 2 Variabili di lock

Pag 1

Sommario

...

Pag 2

Variabile di turno

E' una variabile condivisa tra i processi che interagiscono per accedere in modo condiviso alla risorsa, stabilendone il turno (ovvero a quale processo spetta il diritto di uso in un certo istante).

Sincronizzazione di due processi concorrenti mediante variabile di turno

Nell'utilizzo dei buffer andava tutto bene fin tanto che si leggeva e si scriveva, il problema nasce quando bisogna effettuare degli aggiornamenti. Il problema nello specifico è che se il buffer era pieno il processo si bloccava per depositare il suo messaggio e si impediva l'aggiornamento dell'indice. Ecco perchè devo garantire una sincronizzazione che effettuo con la variabile di turno.

Pag 3

Algoritmo 1

Questo algoritmo scritto in java prevede l'uso di una variabile di turno condivisa.

Commentiamo alcune parti del codice:

  • public Algorithm 1() {
       turn = TURN 0;
    }

    Inizializza a 0 la variabile di turno, quindi dà la possibilità al processo 0 di accedere alla propria porzione critica
  • public void enteringCriticalSection (int t) {
       while (turn != t)
          Thread.yield();
    }

    Il processo 0 può accedere all'uso della risorsa condivisa. A un qualsiasi altro processo (con valore t diverso da 0) viene invece impedito l'accesso, rimanendo bloccato nella funzione di attesa yield().
  • public void leavingCriticalSection (int t) {
       turn = 1 - t;
    }

    Quando il processo 0 avrà terminato le sue operazioni nella porzione critica, concederà l'uso delle risorse condivise all'altro processo assegnando alla variabile turn il nuovo valore. Avendo in questo caso due soli processi, l'alternanza dei valori della variabile viene realizzata con "1-t".

Caratteristiche dell'algoritmo:

  • garantisce la mutua esclusione dei processi, dal momento che quando è in esecuzione uno, l'altro è in attesa
  • impone una stretta alternanza dei processi, con tutti gli svantaggi che questo comporta. Se ad esempio ho un produttore che vuole deporre più informazioni durante il suo turno, non potrà farlo perché dovrà prima aspettare che il consumatore esaurisca il suo (e viceversa)
  • non garantisce il progresso, dato che non lascio evolvere il processo fino ai suoi limiti naturali. Nel caso del consumatore il limite naturale è l'aver letto tutte le informazioni, mentre per il produttore è ritrovarsi col buffer pieno.

Algoritmo 2

Anche in questo caso commentiamo alcune porzioni di codice:

  • private volatile boolean flag0, flag1

Utilizzo due variabili booleane di flag per riferirmi allo stato dei processi

  • public Algorithm 2() {
       flag0 = false; flag1 = false;
    }

    Inizializza entrambi i flag a false per indicare che i processi non vogliono ancora entrare nella sezione critica.
  • public void enteringCriticalSection (int t) {
       if (t == 0) {
          flag0 = true;
          while (flag1 == true)
             Thread.yield();
       }
       else {
          flag1 = true;
          while (flag0 == true)
             Thread.yield();
       }
    }

    Se il processo che vuole accedere alla risorsa è lo 0, marchio flag0 a true e nel caso in cui flag1 sia a true (nel caso cioè che un altro processo stia già usando la risorsa condivisa) attendo che finisca.
  • public void leavingCriticalSection (int t) {
       if(t == 0) flag0 = false; else flag1 = false;
    }

    Quando un processo termina le sue operazioni sulla sezione condivisa, pone il proprio flag uguale a false.

Caratteristiche dell'algoritmo:

  • non impone stretta alternanza dei processi, dato che chi arriva controlla dai valori dei flag se può accedere alla risorsa
  • mutua esclusione garantita dal punto precedente
  • non garantisce il progresso
  • possibile attesa infinita

Pag 4

Algoritmo 3

Anche in questo caso commentiamo alcune porzioni di codice:

  • public void enteringCriticalSection (int t) {
       int other = 1 - t;
       turn = other;
       if (t == 0) {
          flag0 = true;
          while (flag1 == true && turn == other)
             Thread.yield();
       }
       else {
          flag1 = true;
          while (flag0 == true && turn == other)
             Thread.yield();
       }
    }

    Grazie all'assegnamento turn = other, la prossima volta che viene lanciata la funzione passo other come parametro (l'altro processo) così che se non deve fare nulla ripassa immediatamente il turno all'altro, altrimenti esegue le operazioni che deve fare nel suo turno.

Caratteristiche dell'algoritmo:

  • garantisce la mutua esclusione
  • garantisce il progresso

Variabile di lock

La variabile di lock non guarda più lo stato di uso dei processi, quindi il diritto d'uso di un processo, ma lo stato di uso di una risorsa.

Pag 5

Uso ad interruzioni disabilitate

Acquisizione della risorsa:

  • disabilito le interruzioni
  • leggo la variabile di lock
  • se la risorsa libera (lock = 0), la marco in uso ponendo lock = 1 e riabilito le interruzioni, tanto ormai è stato marcato nel sistema operativo
  • se la risorsa è in uso (lock = 1), riabilito le interruzioni e pongo il processo in attesa che la risorsa si liberi

Notare come questi passaggi siano sequenze di operazioni assembler, quindi interrompibili per definizione. Devo perciò garantire che siano loro stesse una porzione critica, disabilitando appunto le interruzione.

Rilascio della risorsa:

  • pongo lock = 0

Hardware per la sincronizzazione

Vegono in pratica introdotti nell'hardware del processore dei meccanismi per ottenere la sincronizzazione.

L'istruzione atomica TEST-AND-SET traduce la sequenza di istruzioni precedenti in una sola.

Se però la soluzione vista nella slide precedente è percorribile dal programmatore, questa è perseguibile esclusivamente dal progettista del processore.


Torna alla pagina di Sistemi Operativi