1. Indice

2. Semafori

Per quanto riguarda la condivisione della memoria, nel nostro sistema i processi utente:

Questo tipo di condivisione può essere ottenuta evitando di rimpiazzare la parte di memoria condivisa quando si salta da un processo ad un altro.

Un sistema del genere ha senso se i processi appartengono tutti allo stesso utente e fanno parte di un’unica applicazione, che l’utente ha deciso di strutturare in più attività concorrenti. Da ora in poi ci limiteremo a considerare solo questo caso.

L’utente che scrive un’applicazione strutturata su più processi concorrenti deve affrontare dei problemi molto simili a quelli già affrontati a livello sistema.

In particolare, anche l’utente deve affrontare il problema dell’interferenza: Infatti, mentre un processo sta eseguendo delle modifiche su una struttura dati comune, un altro processo potrebbe inserirsi e cominciare anche lui a modificare la stessa struttura dati. Se l’utente non scrive il codice con attenzione, questo può causare malfunzionamenti come abbiamo già visto.

Si noti che, mentre nel codice di sistema abbiamo risolto il problema ricorrendo all’atomicità realizzata disabilitando le interruzioni mentre il codice è in esecuzione, qui non possiamo fare la stessa cosa, in quanto le interruzioni devono restare abilitate mentre il è in eseuzione il codice utente.

Definiamo quindi due problemi quando ci sono più attività che vogliono essere eseguite in contemporanea:

Per risolvere i problemi di mutua esclusione e sincronizzazione, si suppone di avere delle scatore, chiamate semafori che possono contenere degli oggetti, chiamati gettoni, tutti uguali. Questo nome fu dato da Dijkstra in relazione al fatto che nella prima formulazione ogni semaforo poteva assumere solo due stati:

Nei semafori possono essere eseguite solo due operazioni con i gettoni: Inserimento e Prelievo. Per quanto riguarda l’inserimento, non è necessario che il processo che insersce il gettone lo abbia precedentemente prelevato da qualche parte, può infatti crearlo sul momento. Nel caso invece del prelievo del gettone, se questo non è presente, il processo deve aspettare che qualcun altro ne inserisca uno, entrando in uno stato di attesa dove non può fare nient’altro

2.1. Esempio - Mutua Esclusione

Supponiamo adesso di dover risolvere un problema di mutua esclusione.

Abbiamo:

Vogliamo che le azioni non possano mai essere eseguite contemporaneamente.

Per risolvere questo problema è sufficente avere un semaforo che inizialmente contiene un gettone e imporre la regola che:

“Solo chi ha il gettone può compiere una delle azioni. Al termine dell’azione è obbligatorio reinserire il gettone”

In questo modo, se una persona vuole compiere un’azione deve prendere il gettone, svuotando la scatola. Se una seconda persona volesse compiere la stessa azione troverà il semaforo vuoto, e si troverà costretta attendere che la prima termini la sua.

L’attesa del gettone nella scatola vuota è quello che avevamo precedentemente chiamato come stato bloccato delle procedure.

Possiamo notare come in casi come questo può avvenire preemption. Quando un processo riesce finalmente a recuperare il gettone, torna nella pila pronti, ed è quasi certo che abbia una priorità più elevata del processo attualmente in esecuzione, forzandone lo scambio.

2.2. Esempio - Sincronizzazione

Supponiamo invece un problema di sincronizzazione.

Abbiamo due persone:

Vogliamo inoltre che l’azione B venga eseguita sempre dopo l’azione A.

È sufficiente in questo caso utilizzare due semafori:

Operativamente questo significa che:

  1. Pa deve lasciare un gettone nel secondo semaforo dopo aver eseguito l’azione A.
  2. Prima di eseguire l’azione B, Pb deve prendere un gettone dal secondo semaforo.

Se Pa arriva per primo alla scatola, vi lascia il gettone così che Pb possa prenderlo e proseguire. Se invece arriva per primo Pb, troverà la scatola vuota e dovrà aspettare che Pa vi inserisca un gettone.

In entrambi i casi l’azione B non potrà essere eseguita se prima non è finita l’azione A.

2.3. Comandi Semafori e Gettoni

I comandi per creare i semafori (scatole) e gestirli nella nostra macchina sono:

/**
 * Crea un nuovo semaforo con n gettoni
 * @param n : numero gettoni
 * @return identificatore (0xFFFFFFFF se non è stato possibile crearlo)
 */
sem = sem_ini(n);     
/**
 * Prende un gettone. Blocca il processo se il semaforo è vuoto
 * @param sem : numero del semaforo
 */
sem_wait(sem);
/**
 * Inserisce un gettone, risvegliando uno dei processi bloccati in attesa
 * @param sem: numero del semaforo 
 */
sem_signal(sem);

Uno snippet di codice per la soluzione dei problemi:

Mutua Esclusione

natl mutex = sem_ini(1);
sem_wait(sem);
A_i();        // Azioni di A_i
sem_signal(sem);

Sincronizzazione

natl mutex = sem_ini(1);
natl sync = sem_ini(0);

void A(){
    sem_wait(mutex);
    // ...
    sem_signal(sync);
    sem_signal(mutex);
}

void B(){
    sem_wait(sync);
    sem_wait(mutex);
    // ...
    sem_signal(mutex);
}

Nei casi di sincronizzazione, si può arrivare a sviluppare semafori che hanno funzionamento molto simile a quello degli handshake. Riprendiamo infatti il caso dei due utenti che utilizzano un buffer per comunicare:

Quello che faremo è implementare qualcosa molto simile all’handshake dav_/rfd:

natl S1 = sem_ini(1);
natl S2 = sem_ini(0);
void scrittura(){
    sem_wait(S1);
    // corpo
    sem_signal(S2);
}
void lettura(){
    sem_wait(S2);
    // corpo
    sem_signal(S1);
}

2.4. Realizzazione dei semafori

Per realizzare i semafori prevediamo la seguente struttura dati definita nel codice sistema:

struct des_sem {
	/// se >= 0, numero di gettoni contenuti;
	/// se < 0, il valore assoluto è il numero di processi in coda
	int counter;
	/// coda di processi bloccati sul semaforo
	des_proc* pointer;
};

Dove:

Come tutte le primitive, anche sem_ini(), sem_wait() e sem_signal() sono invocate tramite una istruzione INT, con tutte le conseguenze che abbiamo visto fin’ora.

Possiamo vedere di seguito la parte C++ della primitiva sem_ini():

des_sem array_dess[MAX_SEM * 2];

extern "C" void c_sem_ini(int val){
    natl i = alloca_sem();
    if(i != 0xFFFFFFFF)
        array_dess[i].counter = val;
    esecuzione->contesto[I_RAX] = i;
}

Per l’allocazione dei semafori riserviamo un array di strutture des_sem, chiamato array_dess. Ogni volta che l’utente ci chiede un nuovo semaforo, quello che facciamo è limitarci ad utilizzare una nuova struttura dall’array.

In questo modo, l’array ci permette di risalire facilmente alla struttura des_sem corretta durante la ricerca dell’identificatore del semaforo passato nelle primitive sem_wait() e sem_signal().

Come vedremo, anche il modulo io utilizza dei semafori. Per evitare che l’utente possa erroneamente usare i semafori allocati dal modulo io, i semafori vengono idealmente distinti in

La funzione alloca_sem() allocherà quindi un indice appartenente ad una delle due parti dell’array, in base al livello di privilegio che il processo aveva quando ha invocato la primitiva (nella pila sistema).

Vediamo ora la parte C++ della primitiva sem_wait():

extern "C" void c_sem_wait(natl sem){
    // una primitiva non deve mai fidarsi dei parametri
    if (!sem_valido(sem)) {
		flog(LOG_WARN, "sem_wait: semaforo errato: %u", sem);
		c_abort_p();
		return;
	}

	des_sem* s = &array_dess[sem];
	s->counter--;

	if (s->counter < 0) {
		inserimento_lista(s->pointer, esecuzione);
		schedulatore();
	}
}

Nel caso di semaforo senza gettoni, il processo attualmente in esecuzione viene inserito nella coda del semaforo e ne viene scelto un altro invocando la funzione schedulatore(). Questa non fa altro che estrarre dalla coda pronti il processo a più alta priorità e lo fa puntare dalla variabile esecuzione. In questo modo, la routine carica_stato (che verrà eseguita subito dopo) farà saltare al nuovo processo, di fatto bloccando il precedente.

Vediamo infine la parte C++ della primitiva sem_signal():

extern "C" void c_sem_signal(natl sem)
{
	// una primitiva non deve mai fidarsi dei parametri
	if (!sem_valido(sem)) {
		flog(LOG_WARN, "sem_signal: semaforo errato: %u", sem);
		c_abort_p();
		return;
	}

	des_sem* s = &array_dess[sem];
	s->counter++;

	if (s->counter <= 0) {
		des_proc* lavoro = rimozione_lista(s->pointer);
		inspronti();	// preemption
		inserimento_lista(pronti, lavoro);
		schedulatore();	// preemption
	}
}

Se ci sono processi in coda sul semaforo, la primitiva estrae quello a priorità più alta attraverso la funzione rimozione_lista(). A questo punto la primitiva deve scegliere quale processo deve proseguire, tra quello in esecuzione e quello appena estratto. La cosa più semplice è di inserire entrambi i processi in coda pronti e lasciar scegliere alla funzione schedulatore(), applicando la preemption.

Sia la sem_wait() che la sem_signal(), prima di usare sem, controllano che questo sia un valido identificatore di semaforo, ovvero che sia stato precedentemente restituito da una sem_ini() per il livello corretto, e terminare forzatamente il processo in caso contrario.

2.5. Utilizzo Debugger

Le estensioni del debugger che abbiamo nella nostra macchina QEMU contengono anche alcuni comandi relativi ai semafori:

Lo stato dei semafori è mostrato nella forma: {counter, lista_processi}.