Problema dei lettori e degli scrittori

Data astrale 28.560,29

In tema di accesso concorrenziale alle risorse, può presentarsi (come è successo a me) il problema noto come problema dei lettori e degli scrittori.
In realtà i problemi sono due.

Scenario
Supponiamo di avere una memoria condivisa, e più thread al lavoro su di essa.
Alcuni thread vorranno accedervi soltanto in lettura, altri in scrittura.
E' chiaro che l'accesso alla memoria deve essere esclusivo, cioè non può accadere che i thread lettori possano accedere alla memoria condivisa insieme ad i thread scrittori. In particolare, più thread lettori possono avere accesso alla memoria simultaneamente, ma gli scrittori necessitano di mutua esclusione anche tra di loro.

Primo problema
Potremmo proteggere l'accesso alla memoria tramite un mutex; in questo caso ovviamente nessun thread lettore potrebbe accedere alla memoria nello stesso momento di un thread scrittore, ed il problema sarebbe risolto.
Peccato che la soluzione non sia ottimale. Un lettore R1 potrebbe bloccare il mutex, ed un altro lettore R2 richiedere l'accesso. E' scocciante che il lettore R2 debba aspettare che R1 termini il suo lavoro per poter iniziare il proprio. Sarebbe meglio farlo lavorare immediatamente.
Questo è il primo problema dei lettori/scrittori: nessun thread lettore deve restare in attesa se la risorsa è in uso in lettura. Anche noto come precedenza ai lettori.

Secondo problema
Supponiamo di proteggere l'accesso alla memoria tramite un mutex e di dare la precedenza ai lettori; la soluzione non sarebbe ancora ottimale.
Un lettore R1 potrebbe ottenere l'accesso alla memoria, uno scrittore W potrebbe essere in attesa del suo turno e potrebbe arrivare un altro lettore R2; secondo quanto detto poco fa, il lettore R2 dovrebbe immediatamente mettersi al lavoro, scavalcando l'attesa di W.
A questo punto W rischierebbe di restare in attesa in eterno (o comunque molto a lungo) finchè ci saranno lettori a richiedere l'accesso alla memoria.
Al contrario, W dovrebbe iniziare a lavorare quanto prima.
Questo è il secondo problema dei lettori/scrittori: nessuno scrittore, una volta messo in coda, dovrà aspettare più a lungo del necessario. Noto anche come precedenza agli scrittori.

Una soluzione al problema potrebbe essere quella di mettere in attesa i lettori in arrivo se ci sono già scrittori in attesa; prima o poi i lettori al lavoro cesseranno di lavorare e l'ultimo a farlo risveglierà uno scrittore tra quelli in attesa. Ogni scrittore, al termine del suo lavoro, dovrà sbloccare alcuni (o tutti) lettori in attesa.
Io ho scelto di utilizzare un parametro (r_per_w, cioè readers per writers: quanti lettori sbloccare al termine di ogni scrittore).
Di seguito un mio codice di esempio (in C):

  1. mutex_t m;
  2. semaphore_t sem_r, sem_w;
  3. int waiting_r, waiting_w, working_r, working_w;
  4. int r_per_w = 5;
  5.  
  6. // Tentativo di accesso in lettura
  7. void read_lock()
  8. {
  9.   lock(m);
  10.  
  11.   if (waiting_w || working_w)
  12.     waiting_r++;
  13.   else
  14.   {
  15.     working_r++;
  16.     if (working_r) == 1 down(sem_w);
  17.     up(sem_r);
  18.   }
  19.  
  20.   unlock(m);
  21.   down(sem_r);
  22. }
  23.  
  24. void read_unlock()
  25. {
  26.   lock(m);
  27.  
  28.   working_r--;
  29.   if (working_r == 0) up(sem_w);
  30.  
  31.   unlock(m);
  32. }
  33.  
  34. void write_lock()
  35. {
  36.   lock(m);
  37.  
  38.   if (working_r == 0 && working_w == 0)
  39.     working_w++;
  40.   else
  41.     waiting_w++;
  42.  
  43.   unlock(m);
  44.   down(sem_w);
  45. }
  46.  
  47. void write_unlock()
  48. {
  49.   int n;
  50.  
  51.   lock(m);
  52.  
  53.   working_w--;
  54.   if (waiting_r)
  55.   {
  56.     if (waiting_w)
  57.       n = waiting_r > r_per_w ? r_per_w : waiting_r;
  58.     else
  59.       n = waiting_r;
  60.  
  61.     while (n)
  62.     {
  63.       waiting_r--;
  64.       up(sem_r);
  65.       n--;
  66.     }
  67.   }
  68.   else
  69.     up(sem_w);
  70.  
  71.   unlock(m);
  72. }
Tag utilizzati: programmazione

1 commenti a "Problema dei lettori e degli scrittori"

La compagna di Darkbyte ha scritto:
Quant'è romantico l'amore mio....

u__u''' 

Aggiungi un commento