cerca
Sistemi Operativi - Appunti caotici
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.SO-Mod3-5-Lez2 History

Hide minor edits - Show changes to markup

Changed lines 19-20 from:

...

to:

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.

Added lines 112-131:

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.

Changed lines 86-98 from:

Sezione critica

La sezione critica è una porzione di codice che può generare errori se eseguita in modo concorrente; se infatti fosse eseguita da processi separati funzionerebbe correttamente.

Condizioni da soddisfare:

  • mutua esclusione, in modo da essere certo di non usare in modo scorretto le varie risorse
  • progresso
  • attesa limitata, ovvero non devo avere processi che attendono in modo indefinito di evolversi

Sincronizzazione di processi cooperanti

I processi cooperanti, lo dice il nome stesso, non competono ma lavorano insieme per uno scopo comune. Per realizzarli si rende però necessaria la sincronizzazione dell'evoluzione della computazione.

Nello schema, P1 svolge delle operazioni e a un certo punto vuole fare sapere al processo P2 (prima di eseguire una determinata istruzione) a che punto dello stato di computazione si trova. Analogamente P2 avrà un punto del codice in cui smetterà di computare, fino a quando non gli arriva da P1 le informazioni sul suo stato di computazione. In questo modo i due processi si sincronizzano, dal momento che sanno con esattezza quali blocchi di operazioni sono già stati eseguiti dall'uno e dall'altro.

to:

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.

Changed lines 49-55 from:

Corse critiche

Le corse critiche sono quelle operazioni che possono portare a inconsistenza delle informazioni in caso di processi concorrenti. Notare come queste non conducano sempre ad errori ad ogni esecuzione, ma potrebbero farlo, dunque bisogna evitarle. Prevenire è meglio che curare.

Nell'esempio del produttore-consumatore queste non sono dovute ai soliti problemi legate a operazioni contemporanee di lettura e scrittura (dato che ognuna avviene nello spazio di indirizzamento del proprio processo), ma ai possibili errori nell'aggiornamento dei puntatori del buffer. Tale operazione è infatti realizzata con una sequenza di istruzioni assembler, interrompibile proprio in quanto sequenza e quindi corsa critica.

Bisogna sempre garantire che la sequenza di operazione sia eseguita in modo corretto.

to:

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
Added lines 1-71:

(:title 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

...

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.

Corse critiche

Le corse critiche sono quelle operazioni che possono portare a inconsistenza delle informazioni in caso di processi concorrenti. Notare come queste non conducano sempre ad errori ad ogni esecuzione, ma potrebbero farlo, dunque bisogna evitarle. Prevenire è meglio che curare.

Nell'esempio del produttore-consumatore queste non sono dovute ai soliti problemi legate a operazioni contemporanee di lettura e scrittura (dato che ognuna avviene nello spazio di indirizzamento del proprio processo), ma ai possibili errori nell'aggiornamento dei puntatori del buffer. Tale operazione è infatti realizzata con una sequenza di istruzioni assembler, interrompibile proprio in quanto sequenza e quindi corsa critica.

Bisogna sempre garantire che la sequenza di operazione sia eseguita in modo corretto.

Pag 4

Sezione critica

La sezione critica è una porzione di codice che può generare errori se eseguita in modo concorrente; se infatti fosse eseguita da processi separati funzionerebbe correttamente.

Condizioni da soddisfare:

  • mutua esclusione, in modo da essere certo di non usare in modo scorretto le varie risorse
  • progresso
  • attesa limitata, ovvero non devo avere processi che attendono in modo indefinito di evolversi

Sincronizzazione di processi cooperanti

I processi cooperanti, lo dice il nome stesso, non competono ma lavorano insieme per uno scopo comune. Per realizzarli si rende però necessaria la sincronizzazione dell'evoluzione della computazione.

Nello schema, P1 svolge delle operazioni e a un certo punto vuole fare sapere al processo P2 (prima di eseguire una determinata istruzione) a che punto dello stato di computazione si trova. Analogamente P2 avrà un punto del codice in cui smetterà di computare, fino a quando non gli arriva da P1 le informazioni sul suo stato di computazione. In questo modo i due processi si sincronizzano, dal momento che sanno con esattezza quali blocchi di operazioni sono già stati eseguiti dall'uno e dall'altro.


Torna alla pagina di Sistemi Operativi