Semafori

TPSI

I semafori

Open Ended

Che cos'è l'interferenza e che situazione si genereano in caso in cui accada? (come sono i processi tra loro?)

Premessa: quando è necessario
sincronizzare?

Si possono verificare casi di interferenza nel caso di processi interagenti

•siano essi in competizione, cioè che chiedono l’uso di una risorsa comune
riusabile e di molteplicità finita per i propri
scopi

•siano in cooperazione per raggiungere un obiettivo comune

Premessa: quando è necessario
sincronizzare?

● Possiamo classificare in quattro gruppi la

casistica di situazioni possibili e per ogni
gruppo indicare l’azione che è
necessario effettuare

Premessa: quando è necessario
sincronizzare?

● Noi ci occuperemo di:

•situazioni in cui la competizione tra i processi

ci porta a interferenze che possono provocare
situazioni inaccettabili e che quindi devono
essere gestite con la mutua esclusione
•casi in cui i processi collaborano e quindi

devono scambiarsi informazioni attraverso
aree di memoria condivisa e con accesso
regolato da meccanismi di sincronizzazione

Open Ended

Che cosa sono la mutua esclusione e la sezione critica?

Premessa: quando è necessario
sincronizzare?

● Il frammento di programma che utilizza la

risorsa R che deve essere gestita in mutua
esclusione si dice sezione critica o regione
critica rispetto alla risorsa R

● è necessario garantire che un processo

acceda alla risorsa da solo

● esegua la sezione critica con la certezza di

essere l’unico utilizzatore che volta per volta
esegue il codice che utilizza la risorsa

Premessa: quando è necessario
sincronizzare?

● La sezione critica viene gestita in modo:

•un processo che deve accedere a una regione

critica deve chiedere l’autorizzazione
• se la risorsa fosse libera il gestore ne assicura

un uso esclusivo per tutta la durata
dell’elaborazione
• se la risorsa fosse occupata il gestore ne

impedisce l’accesso gestendo la richiesta, per
esempio, con una coda di attesa

Premessa: quando è necessario
sincronizzare?

•quando un processo termina di utilizzare

una risorsa deve effettuare operazioni per
rilasciarla in modo che possa essere
utilizzata dagli altri processi

Premessa: quando è necessario
sincronizzare?

● Con apposite primitive che regolino l’accesso e

il rilascio della risorsa si garantisce che:
•la risorsa o è libera oppure è utilizzata da un solo

processo (condizione di mutua esclusione);
•i processi devono sempre poter accedere alla

risorsa richiesta e portare a termine il proprio lavoro
(condizione di fairness);
•i processi non devono avere cicli di ritardo non

necessari che possano rallentare l’accesso alla
regione critica da parte di un altro processo.

Premessa: quando è necessario
sincronizzare?

●

I meccanismi che permettono di regolare l’accesso alla
regione critica risolvendo di fatto il problema della mutua
esclusione sono essenzialmente tre:
◗ gli spin lock (o semafori binari);
◗ P(S) & V(S) ovvero i semafori di Dijkstra;
◗ i monitor.

Semafori di basso livello e spin lock()

● Il primo meccanismo che analizziamo è quello

che associa a ogni risorsa una variabile x

● in base al suo valore assume il seguente

significato:
•x = 1 risorsa libera, cioè nessun processo la sta

utilizzando
•x = 0 risorsa occupata da un processo

Semafori di basso livello e spin lock()

● Il flag fa la funzione di un semaforo:

◗x = 1 semaforo verde, è possibile accedere
alla risorsa;
◗x = 0 semaforo rosso, la risorsa è occupata
ed è necessario mettersi in attesa che si
liberi.

Semafori di basso livello e spin lock()

● Allocazione di una risorsa: lock() o P()

Semafori di basso livello e spin lock()

● Rilascio di una risorsa unlock() o V():

● La primitiva unlock() deve semplicemente modificare il

valore del semaforo da rosso a verde:

● La mutua esclusione si ottiene facendo precedere la lock(x)

a una sezione critica e facendola seguire da una unlock().

Semafori di basso livello e spin lock()

● Problema della indivisibilità

Per come abbiamo scritto l’istruzione di lock()
potrebbe verificarsi situazione di interleaving

●

Semafori di basso livello e spin lock()

● Problema della indivisibilità

Per evitare questa situazione è necessario rendere
indivisibile l’esecuzione delle istruzioni della funzione
lock(x): la soluzione potrebbe essere quella di
disabilitare le interruzioni all’inizio e al termine di
questa funzione in modo che diventi ininterrompibile.

Semafori di basso livello e spin lock()

● Problema della indivisibilità

Analogo problema potrebbe verificarsi per interleaving
anche sulla primitiva di unlock(x):

Semafori di basso livello e spin lock()

● Problema della indivisibilità

Riscriviamo le due primitive utilizzando
queste due nuove istruzioni:

Semafori di basso livello e spin
lock()

Semafori di basso livello e spin
lock()

Multiple Select

In un semaforo binario a seconda del valore di x abbiamo

• x=1 risorsa libera

• x=0 risorsa libera

• x=1 risorsa occupata

• x=0 risorsa occupata

Multiple Choice

L'istruzione TestAndSet(x):

• Modifica il valore di un bit in modo ininterrompibile

• Modifica il valore di un byte in modo ininterrompibile

• Modifica il valore di x in modo ininterrompibile

• Tutte le affermazioni precedenti sono valide, dipende dall'applicazione

Multiple Choice

L'istruzione TestAndSet(x)

• risolve il problema dell'attesa attiva

• risolve il problema della starvation

• risolve il problema dell'interleaving

• non risolve nessun problema

Multiple Choice

Se la mancanza di sincronizzazione provoca danni trascurabili, la miglior strategia è ignorare il problema

• Vero

• Falso

Multiple Choice

La serializzazione può essere ottenuta introducendo cicli di ritardo

• Vero

• Falso

Multiple Choice

L'istruzione di lock su uno spin può generare una situazione di attesa attiva

• Vero

• Falso

Multiple Choice

Per evitare situazioni di interleaving l'istruzione di lock si esegue a interruzioni disabilitate

• Vero

• Falso

Multiple Choice

La primitiva di unlock(x), essendo una sola istruzione, non richiede interruzioni disabilitate

• Vero

• Falso

Multiple Choice

Le primitive P(S) e V(S) non necessitano di essere indivisibili in quanto sono atomiche

• Vero

• Falso

Multiple Choice

La P(S) su un semaforo rosso sospende il processo e lo mette in coda

• Vero

• Falso

Multiple Choice

La V(S) su un semaforo verde mette il semaforo a rosso senza sospendere il processo

• Vero

• Falso

Multiple Choice

Diversi processi possono accedere alla stessa area di memoria, e se un processo sta eseguendo una test-and-set, nessun altro processo può iniziare un'altra test-and-set finché il primo processo non ha terminato la propria

• Vero

• Falso

Multiple Choice

TestandSet e disabilitazione degli interrupt hanno lo scopo di creare sezioni critiche

• Vero

• Falso

Semafori di Dijkstra

● Dijkstra ha proposto due primitive che

permettono la soluzione di qualsiasi
problema di interazione fra processi:
•la primitiva P(S), che riceve in ingresso un numero

intero S non negativo (semaforo), che viene
utilizzata per accedere alla risorsa
•la primitiva V(S), che riceve anch’essa in ingresso

un numero intero S non negativo (semaforo), che
viene utilizzata per rilasciare la risorsa

Semafori di Dijkstra

● Introduciamo quindi un nuovo tipo di dato:

● dove vi (vi≥0) è il valore iniziale

● il valore 0 corrisponde al rosso

Semafori ferroviari

●

Semafori di Dijkstra

● Lo schema a blocchi delle due istruzioni è:

Semafori di Dijkstra

● La pseudocodifica:

Semafori di Dijkstra

● Un processo che esegue una P(S) può

avanzare solo se trova S > 0
•altrimenti deve accodarsi per attendere

passivamente una V(S)

● Un processo che esegue una V(S), se non

esistono processi in attesa dentro la coda, ha
come unico effetto quello di incrementare S
•altrimenti risveglia uno dei processi che attendono

nella coda:

● La realizzazione delle due primitive è:

Semafori di Dijkstra

Semafori binari vs semafori di
Dijkstra

● I semafori di Dijkstra vengono anche chiamati

semafori generalizzati (o a conteggio) per
distinguerli dai semafori binari

● In letteratura si trovano spesso i nomi down(S)

e up(S) per indicare rispettivamente P(S) e
V(S)
•l’istruzione P(S) decrementa di 1 il valore del

semaforo ->down(S)
•l’istruzione V(S) invece la incrementa ->up(S)

Semafori binari vs semafori di
Dijkstra

● Molteplicità di una risorsa

● I semafori a conteggio vengono utilizzati per

controllare l’accesso a una risorsa disponibile
in un numero finito di esemplari

●