Il Problema Dei Metronomi De-Sincronizzati

Durante lo studio di sistemi operativi, ho trovato un’importante risorsa chiamata The Little Book of Semaphores che illustra svariati esempi di esercizi della programmazione concorrente, in particolare sui semafori.

Per chi è un po’ a digiuno o non ha mai visto nella sua carriera la programmazione concorrente, facciamo un passo indietro. Ogni processo che noi eseguiamo e che viene eseguito per il sistema operativo concorre con tutti gli altri processi in esecuzione per prendere il controllo della risorsa più preziosa: la CPU. L’algoritmo di scheduling decide per quanto tempo il processo può occupare la CPU e in caso di cambio di processi, scegliere il prossimo che avrà diritto alla CPU.

Con gli algoritmi di scheduling time-sharing e multi programmati (il primo su tutti, Round Robin), i processo avanzano in modo concorrente, con l’illusione di essere eseguiti parallelamente. In realtà ciò che avviene all’interno è la rotazione molto veloce dei processi all’interno della CPU in modo che ognuno dei processi faccia un poco del lavoro utile. Finché i processi erano indipendenti (ovvero non influenzavano e non venivano influenzati da nessun altro processo), non si era mai posto il problema della condivisione dei dati. Tuttavia, quando più processi in modo concorrente tra di loro vogliono condividere una risorsa, il modo in cui questi vengono schedulati può influenzare il risultato finale.

Se due processi si vogliono sincronizzare, è necessario adottare delle tecniche che vanno oltre alla semplice “variabile” condivisa dato che più processi, accedendo in modo differente ai dati (sia in lettura che scrittura), possono portare ad inconsistenza dei dati. Tale tecniche si basano sull’utilizzo dei semafori, variabili intere positive manipolabili solo da P() (decrementa il valore del semaforo) e V() (aumenta il valore del semaforo). Inspirato da The Little Book of Semaphores, ho provato ad inventare un problema di sincronizzazione.

Il problema

Problema: Immaginiamo di avere N metronomi, ognuno avente una frequenza di oscillazione diversa. Quando sono posti vicini tra di loro, metronomi di frequenza diversa tendono ad equilibrarsi, ovvero tendono ad avere tutte le frequenze di oscillazione uguali, “in fase”. Tramite semafori, si provi ad implementare il processo metronomo, sapendo che esiste una variabile condivisa chiamata media contenente la media di tutti i valori delle frequenze di N metronomi. Ogni volta che si modifica la frequenza è necessario ricalcolare la media. All’inizio tutti i metronomi hanno una frequenza diversa casuale (valida). L’obiettivo finale è sincronizzare tra di loro i diversi metronomi, ovvero che tutte le frequenze di oscillazione siano uguali.

Buon divertimento :)

Se avete una soluzione e volete sapere se è valida, inviatemela a blog@nicolo.dev.

Traduzioni