Esercizio - Priorità, semaforo FIFO e code (eserciziario, esercizi 13 e 44)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 13 e 44, lo stesso problema in due edizioni). Un sistema ha il semaforo sem e i thread $P_1$ (priorità 1), $P_2$ (priorità 1) e $P_3$ (priorità 2). Lo scheduling è a priorità con prelazione: assegna il processore al processo pronto di priorità più alta (a pari priorità, FIFO). La politica del semaforo è FIFO. Al tempo $t$: $P_1$ è in esecuzione, $P_2$ è pronto, sem vale 0 e la sua coda contiene $P_3$. Dopo $t$ avvengono, in sequenza:

1. $P_1$ esegue P(sem) (wait);
2. il processo in esecuzione esegue V(sem) (signal);
3. il processo in esecuzione esegue P(sem);
4. il processo in esecuzione esegue V(sem).

Si specifichi quale processo è in esecuzione dopo ogni evento e come cambiano il valore e la coda del semaforo e la coda dei pronti. Teoria: Semafori, monitor e problemi classici di sincronizzazioneUn semaforo è un intero accessibile solo con due operazioni atomiche, wait (P: aspetta finché S > 0 e decrementa) e signal (V, in POSIX sem_post: incrementa); il semaforo contatore ha valori illimitati, quello binario vale 0 o 1; con valore iniziale 1 realizza la mutua esclusione, con valore iniziale 0 impone un ordine di esecuzione (S1 prima di S2); senza attesa attiva ogni semaforo ha una coda di processi sospesi (sleep e wakeup); i semafori si usano male con facilità (ordine sbagliato, omissioni); il monitor è un tipo di dato astratto in cui un solo processo alla volta è attivo e le variabili condizione x.wait()/x.signal() sospendono e risvegliano (in POSIX mutex più pthread_cond_t); le anomalie di liveness sono deadlock, starvation e inversione di priorità; i problemi classici sono produttore-consumatore a buffer limitato (mutex, vuote = n, piene = 0; l'ordine delle wait è importante), lettori-scrittori (rw_mutex, mutex, read_count; i lettori possono far morire di fame gli scrittori) e filosofi a cena (la soluzione ingenua con un semaforo per bacchetta va in deadlock; si evita limitando a n-1 filosofi, rompendo la simmetria o ordinando le risorse), con soluzioni in C (POSIX) e in Go (canali e sync).Semafori, monitor e problemi classici di sincronizzazione →, Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →.

Convenzioni. Si usa il valore del semaforo non negativo (0 se qualcuno aspetta); alcune slide scrivono invece il valore negativo = numero di processi in coda (tra parentesi nella tabella). Un V con coda non vuota risveglia il primo della coda (FIFO) senza incrementare il valore; il processo risvegliato diventa pronto e la priorità decide se prelaziona. Nella coda del semaforo ordine di arrivo, nei pronti conta la priorità.

Stato iniziale

Svolgimento

1) $P_1$ esegue P(sem). sem è 0: $P_1$ si blocca e va in fondo alla coda del semaforo: coda sem $= P_3, P_1$. Lo scheduler sceglie il processo pronto: $P_2$.

2) $P_2$ esegue V(sem). C'è una coda: si risveglia il primo, $P_3$, che diventa pronto con priorità 2 > 1: prelaziona $P_2$, che torna nei pronti. In esecuzione $P_3$; pronti $P_2$; coda sem $= P_1$; valore 0.

3) $P_3$ esegue P(sem). Il valore è 0: $P_3$ si blocca e finisce in coda dopo $P_1$: coda sem $= P_1, P_3$. Il processore passa a $P_2$ (l'unico pronto); pronti vuota.

4) $P_2$ esegue V(sem). Si risveglia il primo della coda, $P_1$, che diventa pronto con priorità 1, uguale a quella di $P_2$ in esecuzione: la prelazione avviene solo per priorità maggiore, quindi $P_2$ continua; pronti $= P_1$; coda sem $= P_3$; valore 0.

Questa è la tabella del corso. La priorità conta solo tra i processi pronti: la coda del semaforo è un semplice FIFO per ordine di arrivo.

Domande d'esame

Perché al passo 4 $P_2$ non viene prelazionato da $P_1$? Traccia. $P_1$ ha la stessa priorità di $P_2$; con priorità uguale vale FIFO e il processo in esecuzione non viene interrotto: $P_1$ resta in coda ai pronti.