Abbiamo visto come i lock possono essere utili per la sincronizzazione, ma possono essere anche problematici ( es. inversione delle priorità).
Una filosofia alternativa è quella del “i migliori lock sono quelli che non si usano”.
In alcuni casi (non sempre) è possibile utilizzare la tecnica del ready-copy-update, che permette a gli scrittori di aggiornare una struttura dati mentre i lettori la stanno usando e garantire che ogni lettore veda o la versione vecchia o la versione nuova del dato, e mai un “mix” fra le due versioni.
Vediamo l’implementazione con albero binario :
Considerando che i lettori partono dal alto (A) verso il basso.
Inserimento
L’inserimento di un nuovo nodo X come figlio di A :
- lo scrittore inizializza X separatamente (non visibile ancora) e gli collega il nodo E
- i lettori che stanno percorrendo l’albero continuano a seguire i vecchi puntatori (A E)
- quando X è completamente inizializzato, lo scrittore esegue un’unica operazione di aggiornamento atomica per modificare il puntatore di A, facendolo puntare non più a E ma a X
- i lettori presenti in A prima di questo update, continueranno a seguire la vecchia versione (AE)
- i lettori che arrivano in A dopo questa modifica, seguiranno la nuova versione (A X E)
Rimozione
La rimozione dei nodi B e D (dopo inserimento di X) :
- scrittore fa un update atomico al puntatore di A che punta a B, e lo fa puntare a C
- lettori presenti in A prima del update e magari già nel sotto-albero B-D, continueranno a seguire quel sotto-albero (vecchia versione)
- lettori che presenti in A dopo l’update, seguiranno la nuova versione (A C)
- ora in B e in D (disconnessi) ci potrebbero essere ancora dei lettori e finché uno solo di loro è presente li dentro, non possiamo liberare la memoria di B e D. Dobbiamo aspettare quindi che tutti i lettori escano dai due nodi
- dopo che non ci sono più lettori nei nodi da rimuovere, possiamo liberare la memoria di B e D
Grace period
Ma come facciamo ad essere certi che tutti i lettori abbiano lasciato i nodi da rimuovere? La tecnica del RCU definisce delle sezioni critiche di lettura, queste sezioni hanno la proprietà che il thread che le esegue non può essere sospeso o bloccato (neanche da OS con context switch)
Il ragionamento è: un lettore che era dentro B o D prima della disconnessione, prima o poi uscirà dalla sezione critica. Quando lo fa, è vulnerabile al context switch. Quando quel context switch avviene, lo scrittore sa che quel lettore è uscito.
Quindi viene definito questo intervallo chiamato grace period, in cui abbiamo la certezza che ogni singolo thread sia uscito almeno una volta dalla sua sezione critica di lettura.
La tecnica del RCU non è comune per i processi utente, ma molto diffusa nei kernel dei OS moderni. In particolare nel kernel linux la sua implementazione (API RCU) è utilizzata in molti sotto-sistemi come :
- networking
- file system
- driver
- gestione della memoria