UniTO/anno2/Sem1/Galla/MCAD/lesson5-11102017.md

# Semafori e Sezioni critiche condizionali (continua)

## Implementazione di Accesso condizionale

Inizializzazione:
```
struttura dati R;
semaphore mutex = 1;
semaphore sem = 0; 	//blocca accesso a sc
int csem = 0; 		//contatore per #processi bloccati su sem
```
Due operazioni: **Richiesta** e **Rilascio**

### Soluzione classica

#### Richiesta

Un processo cerca di entrare nella SC, verificare la condizione (C)  ed eseguire l'operazione
```
public void request () {
	// ingresso in SC
	P (mutex);

	// verifica della condizione
	// finche' non e' verificata, loop
	while (!C) {
		csem++;
		V (mutex); // libero la SC
		P (sem);   // aspetto che sem sia libero
		P (mutex); // rientro in SC
	}
	
	// se arriva qui, C e' verificata e il processo e' nella sezione critica
	<< operazione critica >>
	V (mutex)
}
```
**NOTA**: E' possibile che un processo entri nella sezione critica mentre l'altro e' dentro il loop while. Questo fenomeno si chiama *spiffero*.

#### Rilascio

Rilascio delle risorse dopo aver eseguito l'operazione critica.
```
public void release () {
	P (mutex);
	<< operazione critica >>
	if (csem > 0) {
		csem--;
		V (sem);
	}
	V (mutex);
}
```

### Soluzione alternativa

Questa soluzione, per quanto piu' efficiente,**e' utilizzabile solo quando l'operazione critica cambia il valore della condizione C, permettendo a un altro processo di accedervi**. C deve essere quindi condivisa tra processi.

Due operazioni, come nella soluzione classica.
#### Richiesta
```
public void request () {

	if (!C) { 		// simile alla soluzione classica
		csem++; 	// niente loop perche' assumiamo che eseguire l'OC cambi il valore di C
		V (mutex);
		P (sem);
		csem--; 	// V (sem) puo' essere chiamato qui, o durante il rilascio
	}

	<< operazione critica >>
	V (mutex);
}
```
#### Rilascio 
```
public void release () {
	P (mutex);
	<< operazione critica >>
	if (csem > 0) {
		V (sem);
	} else {
		V (mutex);
	}
}
```
*(vedi esempio con pool di risorse)*

## Producer and Consumer (produttore e consumatore) - Semaforo contatore

Si presenta qui una soluzione alternativa al problema del produttore e consumatore, che utilizza un semaforo contatore per gestire un buffer **circolare**;
Si assume 1 produttore e 1 consumatore.

### Inizializzazione
```
semaphore empty = N;
semaphore full = 0;
T buffer[N];
int head = 0;
int tail = 0;
```
N e' la dimensione del buffer, e empty e' inizializzato ad essa perche' tutte le celle del buffer sono vuote all'inizializzazione. *head* e *tail* sono due contatori, *tail* per il producer e *head* per il consumer, che indicano la cella occupata.

#### Producer (invio di dati)
```
public void send (T data) {
	P (empty);
	buffer[tail] = data;
	tail = (tail++) % N;
	V (full);
}
```

#### Consumer (ricezione di dati)
```
public T receive () {
	P (full);
	T data = buffer[head];
	head = (head++) % N;
	V (empty);
	return data;
}
```
Si nota come il buffer circolare implichi gli incrementi di *head* e *tail* in modulo N.

### Dimostrazione di Correttezza

* Siano:
```
nd(t) = # inserimenti (depositi) da parte del produttore
ne(t) = # estrazioni (ricezioni) da parte del consumatore
```
* La precedente dimostrazione del problema producer-consumer aveva portato:
```
0 <= nd(t) - ne(t) <= 1
```
* Perche' non possono esserci piu' estrazioni che inserzioni, e le inserzioni devono essere al massimo 1 in piu' delle estrazioni.

* Da qui, utilizzando l'invariante semaforico:
```
NP (empty, t) <= NV (empty, t) + N
```
* il che rispecchia l'inizializzazione del problema.

* Per dimostrare la correttezza, supponiamo che esista un istante t in cui il producer deposita e il consumer estrae. Dobbiamo quindi dimostrare che **head != tail**, in quanto non e' possibile che producer e consumer lavorino sulla stessa cella del buffer.

* Siano:
```
p1(t) = # incrementi in coda (tail)
p2(t) = # incrementi in testa (head)
```
* Da questo, la tesi puo' essere riscritta come:
```
1 <= p1(t) - p2(t) <= N-1 
```
* Supponendo che entrambi i processi debbano ancora uscire dalla sezione critica:
```
p1(t) = NV(full, t) = NP (empty, t) - 1 
p2(t) = NV(empty, t) = NP (full, t) - 1
```
* Da cui si puo' utilizzare l'invariante semaforico per ottenere:
```
p2(t) = NP(full,t) - 1 <= NV(full, t) - 1 <= p1(t) - 1 <= NP(empty, t) - 2 <= NV(empty, t) - 2 <= NV(empty, t) - 2 + N <= p2(t) + N - 2
```
* Considerare solo i termini p1, p2:
```
p2(t) <= p1(t) - 1 <= p2 (t) + N - 2
```
* Possiamo sommare 1 a tutti i termini senza cambiare la validita' della disequazione:
```
p2(t) + 1 <= p1(t) <= p2(t) + N - 1
```
* Che, sottraendo a ogni termine p2(t), risulta:
```
1 <= p1(t) - p2(t) <= N - 1
```
* Che e' proprio la tesi di partenza della dimostrazione di correttezza. CVD