Semafori_Mutex

Sleep e wakeup 😴 ⏰

Sebbene l’uso di soluzioni basate sul busy waiting, siano corrette, presentano due gravi problemi:

• spreco di tempo CPU (spin lock)
• inversione della priorità: consideriamo un processo L (priorità bassa) e H (priorità alta) :
  • L utilizza la risorsa
  • arriva H e L viene messo in sospeso (non rilascia la risorsa)
  • ma ora H tenta di usare la risorsa bloccata da L che è in sospeso, e quindi H entra in busy waiting
  • il blocco: H continua a stare in busy waiting consumando tempo CPU e L non sarà mai ripreso (siccome CPU è occupata con H)

Per risolvere queste problematiche (no busy waiting) esistono due primitive:

• sleep() : system call che blocca il processo chiamante, sospendendolo finché un altro processo non lo “sveglia”
• wakeup(p) : system call che "sveglia" il processo p (in sleep)

Problema del produttore-consumatore 🏭 🧍‍♂️

Consideriamo un buffer comune tra un processo “produttore” e “consumatore” :

• il produttore inserisce elementi nel buffer
• il consumatore toglie gli elementi dal buffer
• se il buffer è pieno il produttore va in sleep e poi viene risvegliato dal consumatore
• se il buffer è vuoto il consumatore va in sleep e poi viene risvegliato dal produttore

#define N 100
int count = 0
 
void producer(void){
	int item;
	while(TRUE){
		item = produce_item();
		if (count == N) sleep(); // se il buffer è pieno, sleep
		insert_item(item);
		count++;
		if (count == 1) wakeup(consumer); // se il buffer era vuoto (0) risveglia il consumatore 
	
	}
}
 
void consumer(void){
	int item;
	while(TRUE){
		if (count == 0) sleep();  // se buffer vuoto => sleep
		item = remove_item(); 
		count--;
		if (count == N-1) wakeup(producer); // se il buffer era pieno (N) risveglia il produttore
		consume_item(item);
		
	}
	
}

Consideriamo ora il seguente scenario :

• il buffer è vuoto e il consumatore è avviato, trova quindi il contatore a 0 (no elementi)
• supponiamo che lo scheduler decide di interrompere il consumatore, prima dello sleep (poiché ha trovato il contatore a 0) e avvia il produttore
• il produttore inserisce un elemento nel buffer e incrementa il contatore (count=1)
• il produttore cerca di wakeup (svegliare) il consumatore, ma che non sta dormendo, quindi è un caso perso
• il produttore si metterà in sleep (perché ha inserito nel buffer)
• a questo punto lo scheduler riattiva il consumatore, che andrà subito in sleep

In questo modo entrambi saranno in sleep e non succede nulla. Il problema è che un wakeup inviato al consumatore (processo sveglio ma interrotto) va perso.

La soluzione potrebbe essere nel aggiungere un bit di attesa wakeup :

• quando il wakeup è stato inviato ad un processo sveglio, il sistema imposta questo bit a 1, altrimenti a 0
• quando il processo tenta di andare in sleep controlla questo bit :
  • se 1 $⟹$ lo azzera e rimane sveglio (assorbendo il risveglio)
  • se 0 $⟹$ va in sleep

Semafori🚦

La soluzione dell’aggiunta del bit di wakeup non è efficiente quando abbiamo più di un processo, anche se aumentiamo il numero di bit di wakeup.

Un’altra soluzione è quella del semaforo (Dijkstra), dove l'idea di base è di contare il numero di risvegli.

Il semaforo può essere:

• $0$ : non ci sono risvegli salvati
• $\ge 1$ : ci sono uno o più risvegli in attesa (pendenti)

Su un semaforo sono possibili due operazioni:

• down() (generalizzazione di sleep): decrementa/aspetta
  • se valore $\ge 1$ $⟹$ lo decrementa (consumando un risveglio salvato) e il processo chiamante continua l’esecuzione
  • se valore $=0$ $⟹$ il processo chiamate viene bloccato (sleep) senza completare il down()
• up() (generalizzazione di wakeup): incrementa/segnala
  • incrementa il valore del semaforo
  • se ci sono poi processi bloccati sul semaforo, uno di essi (scelto a caso dal sistema) viene risvegliato e completa la sua operazione down()

review

Le operazioni di down() e up() sono atomiche, questo vuol dire che una volta che una delle operazione è iniziata, altri processi non possono accedere al semaforo finché l’operazione non è terminata.

Vediamo un esempio di utilizzo che risolvere il problema del producer-consumer :

#define N 100
typedef int sempaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
 
void producer(void){
	int item;
	
	while(TRUE){
		item = produce_item();
		down(&empty);
		down(&mutex);   // entra nella regione critica
		insert_item(item);
		up(&mutex);     // esce dalla regione critica
		up(&full);     // sveglia il consumer
	}
}
 
void consumer(void){
	int item;
	
	while(TRUE){
		down(&full);
		down(&mutex);   // entra nella regione critica
		item = get_item();
		up(&mutex);     // esce dalla regione critica
		up(&empty);
		consume_item(item);
	}
}

Questa soluzione utilizza 3 tipi di semafori :

• mutex : per avere la mutua esclusione sul buffer, quindi garantire che producer e consumer non accedano al buffer nello stesso momento
• full : per contare il numero di slot pieni
• empty : per contare il numero di slot vuoti

Il semaforo con mutex = 1 è un semaforo binario, siccome assume solo due valori (0 e 1) e fa in modo che solo un processo alla volta entra nella sezione critica.

Esempio readers/writers

• regola base : in qualsiasi momento possono essere ammessi :
  • $R$ lettori
  • $1$ solo scrittore
• esempio : si possono avere più letture da un database, ma un solo scrittore
• funzionamento sintetico :
  • il primo lettore che arriva, blocca l’accesso al db per lo scrittore (o scrittori)
  • lettori successivi incrementano un contatore di quanti sono
  • l’ultimo lettore libera l’accesso al db cosi lo scrittore (o scrittori) può accederci

typedef int semaphore;
semaphore mutex = 1;  // "protegge" rc (readcount) (semaforo binario)
semaphore db = 1; // (semaforo binario)
int rc = 0;  // readcount
 
void reader(){
	while(TRUE){
		down(&mutex); 
		rc++;
		if (rc == 1) down(&db);  // primo lettore blocca accesso db per lo scrittore
		up(&mutex);  // rilascia scrittura su readcount
		read_db();
		down(&mutex);
		rc--;
		if (rc == 0) up(&db); // ultimo lettore rilascia il db per lo scrittore
		up(&mutex);
		use_data_read();
	}
}
 
void writer(){
	while(TRUE){
		think_up_data();
		down(&db);
		write_db();
		up(&db);
	}
}
 

Materiale per capire come funziona sempahore.h (programmazione in C):

• 6.2_producer_consumer_sempahore.c
• 6.3_reader_writer_semaphore.c
• spiegazione di come funziono i semafori Introduction to semaphores in C

---

Mutex 🔑

I mutex (Mutual Exclusion) sono una versione semplificata del semaforo e servono solo per gestire la mutua esclusione di risorse condivise o porzioni di codice.

Il mutex può trovarsi in solo due stati :

• :luc_unlock: unlocked (sbloccato) : valore 0
• :luc_lock: locked (bloccato) : valore 1 (o diverso da 0)

Quando un processo (o thread) necessita di accedere ad una risorsa (gestita da mutex) si utilizzano due procedure:

• mutex_lock():
  • se il mutex è unlocked, può entrare e utilizzare la risorsa, e il lock viene impostato atomicamente per impedire ad altri processi di entrare
  • se il mutex è locked, il processo viene bloccato
• mutex_unlock():
  • rilascia la risorsa dopo che il processo chiamante ha finito
  • se ci sono processi bloccati sul mutex, uno di essi viene scelto a caso dal sistema e gli viene consentito di acquisire il lock della risorsa

review

Assenza di busy waiting : se un thread non può acquisire un lock, chiama thread_yield per cedere (volontariamente) la CPU ad un altro thread. A differenza della funzione di prima enter_region che continuava a “provare” di acquisire il lock.

Considerazioni aggiuntive

• i mutex possono essere implementati nello spazio utente, con l’istruzione atomica TSL (o XCHG)
• alcuni pacchetti thread offrono la chiamata mutex_trylock che "tenta" di acquisire il lock o restituisce un errore, ma senza bloccare
• i mutex sono efficaci tra thread che operano nello stesso spazio di indirizzi, ma se vogliamo utilizzare mutex tra processi (spazi indirizzi distinti)?
  1. risorse condivise vengono memorizzate e gestite nel kernel
  2. OS moderni permettono ad un processo di condividere porzioni del loro spazio di indirizzi con altri processi
  3. utilizzare file condivisi (nel caso peggiore)

Mutex in Pthreads

Nella libreria POSIX threads Pthread, le principali chiamate per la sincronizzazione con il mutex sono :

Ma quando dobbiamo usare pthread_mutex_lock e quando pthread_mutex_trylock?

• lock : quando l’accesso esclusivo è necessario e possiamo attendere se il lock non è disponibile
• trylock : quando vogliamo solo “tentare” di acquisire il lock senza aspettare, proseguendo con altro se il lock è già in uso

if (pthread_mutex_trylock(&mutex) == 0){
	printf("Evviva ho ottenuto il lock, eseguo operazioni protette")
	sleep(2); // simulazione operazioni lunghe 
	printf("Ho terminato");
	pthread_mutex_unlock(&mutex);
}else{
	printf("Altre operazioni e non ho avuto il lock");
}

Variabili di condizione

Queste chiamate sono utilizzate insieme alle variabili condizione, in modo da bloccare i processi se non si verificano determinate condizioni. Infatti con solo quelle chiamate possiamo avere la seguente problematica :

• due thread vogliono accedere a una variabile condivisa (es. un contatore), il mutex garantirà che un solo thread possa accederci
• ma se uno dei due thread ha bisogno di accedere alla variabile solo se raggiunta una certa condizione (es. contatore $\ge 10$), il mutex da solo non è sufficiente per far attendere il thread in modo efficiente

I pthread_cond permettono ai thread di mettersi in attesa di un evento specifico e di essere notificati quando questo evento si verifica (es. producer-consumer).

review Un thread può attendere con pthread_cond_wait su una variabile di condizione :

• durante l’attesa, il thread rilascia “temporaneamente” il mutex, permettendo a gli altri thread di accedere alla risorsa (e magari di soddisfare la condizione attesa)
• caso producer-consumer : il consumer utilizzando una variabile condizionale, può rimanere in attesa finché il buffer non è pieno (o almeno se c’è qualcosa da consumare), senza sprecare tempo sulla CPU

Senza pthread_cond_wait

Se utilizziamo solo il mutex, il thread (es. consumer) deve continuatamente ricontrollare la condizione (busy-waiting).

Per esempio :

pthread_mutex_lock(&mutex);
while(buffer == 0){   // continua a controllare (inefficiente)
	pthread_mutex_unlock(&mutex);
	usleep(1000);
	pthread_mutex_lock(&mutex);
}
consume(buffer);
pthread_mutex_unlock(&mutex);

Infatti in questo caso se mentre il consumer dorme (usleep(1000)) non c’è NESSUN producer che acquisire il mutex e aumenta il buffer, il consumer dopo lo usleep(1000) si risveglia, riprende il mutex e ricontrolla INUTILMENTE il buffer che sarà ancora = 0.

Con pthread_cond_wait

Con le variabili condizionali il thread può sospendersi in modo efficiente.

Per esempio :

pthread_mutex_lock(&mutex);
while(buffer == 0){
	pthread_cond_wait(&condp, &mutex);
}
consume(buffer);
pthread_mutex_unlock(&mutex);

in questo modo il consumer si sospende finché il producer non segnala (con pthread_cond_signal) che il buffer non è più vuoto. PS : Il while è necessario siccome il thread potrebbe risvegliarsi anche se la condizione in attesa non è soddisfatta (“false sveglie”).

Inoltre a differenza dei semafori, con l'utilizzo delle variabili di condizione, non si ha memoria. Se viene mandato un segnale su una variabile di condizione sul quale nessun thread è in attesa, il segnale sarà perso.

---

Vediamo ora un esempio completo di producer-consumer :

/* Dichiarazione di mutex e variabili condizionali */
pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;  /* Usate per segnalare tra produttore e consumatore */
 
int buffer = 0;  /* Buffer utilizzato tra produttore e consumatore */
 
/* Funzione del produttore */
void *producer(void *ptr) {
    int i;
    for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);  /* Ottiene l'accesso esclusivo al buffer */
 
        /*
        NOTA: La ragione per cui viene utilizzato un ciclo while invece di un semplice 
        if è legata alla necessità di gestire le cosiddette "false sveglie" 
        (spurious wakeups) che possono accadere con pthread_cond_wait. 
        Ci assicuriamo che ogni volta che il thread viene svegliato, 
        ricontrolli effettivamente la condizione.
        */
        while (buffer != 0) {
            pthread_cond_wait(&condp, &the_mutex);
        }
 
        buffer = i;  /* Inserisce l'elemento nel buffer */
        printf("Producing:\t%d\n", i);
        sleep(rand()%2);
        pthread_cond_signal(&condc);  /* Sveglia il consumatore */
        pthread_mutex_unlock(&the_mutex);  /* Rilascia l'accesso al buffer */
    }
 
    pthread_exit(0);
}
 
/* Funzione del consumatore */
void *consumer(void *ptr) {
    int i;
    for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);  /* Ottiene l'accesso esclusivo al buffer */
 
        while (buffer == 0) {
            pthread_cond_wait(&condc, &the_mutex);
        }
 
        printf("Consuming:\t%d\n", i);
        buffer = 0;  /* Preleva un elemento dal buffer e lo reinizializza */
        sleep(rand()%2);
        pthread_cond_signal(&condp);  /* Sveglia il produttore */
        pthread_mutex_unlock(&the_mutex);  /* Rilascia l'accesso al buffer */
    }
 
    pthread_exit(0);
}
 
int main(int argc, char **argv) {
    pthread_t pro, con;  /* Threads del produttore e consumatore */
 
    /* Inizializzazione di mutex e variabili condizionali */
    pthread_mutex_init(&the_mutex, NULL);
    pthread_cond_init(&condc, NULL);
    pthread_cond_init(&condp, NULL);
 
    /* Creazione dei threads */
    pthread_create(&con, NULL, consumer, NULL);
    pthread_create(&pro, NULL, producer, NULL);
 
    /* Attesa che i threads completino l'esecuzione */
    pthread_join(pro, NULL);
    pthread_join(con, NULL);
 
    /* Pulizia e distruzione di mutex e variabili condizionali */
    pthread_cond_destroy(&condc);
    pthread_cond_destroy(&condp);
    pthread_mutex_destroy(&the_mutex);
 
    return 0;
}

Semafori VS Mutex

Mutex

Il mutex serve a proteggere una risorsa. Ha un proprietario: solo il thread che ha fatto lock può fare unlock.

Thread A: lock → usa la risorsa → unlock
Thread B: aspetta... aspetta... → lock → usa la risorsa → unlock

La domanda a cui risponde il mutex è: “chi può accedere adesso?”

Semaforo

Il semaforo non ha proprietario. Chiunque può fare up o down, indipendentemente da chi lo ha modificato prima. Serve a coordinare e sincronizzare thread diversi.

È come un parcheggio con N posti: un contatore tiene traccia dei posti liberi. Chi entra decrementa, chi esce incrementa. Non importa chi sei.

La domanda a cui risponde il semaforo è: “è successo qualcosa? quante volte?“

---

necessità	mutex o semaforo	perchè?
proteggere una variabile/struttura dati da scritture simultanee	mutex	è nato apposta per questo
far aspettare un thread finché un altro non ha finito un’operazione	semaforo o mutex	ha il concetto di “evento”, quindi permette a thread diversi di comunicare tra di loro (“Ehi ho finito”). Ma anche i mutex con le variabili di condizione è possibile
limitare l’accesso a N risorse identiche (es. massimo 3 download in contemporanea).	semaforo	puoi inizializzarlo al numero N che ti serve

---

Monitor