Problema dei lettori e degli scrittori

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

Convivendo #2

Ricordarsi sempre di svuotare il contenitore dove fate defluire l'acqua del condizionatore.
Non per niente, rischiate di trovarvi con i piedi nell'acqua mentre siete a pranzo.

Convivendo #1

E' bellissimo finire di lavorare e tornare a casa tua.
Non alla casa dove sei cresciuto, non in quella dei tuoi, ma a casa TUA.
Quella dove vivi solo con la tua ragazza. Tornare ed avere solo lei ad aspettarti, decidere di cenare insieme, prepararsi qualcosa, guardare la tv, parlare del più e del meno...
Poi ci pensi, è il momento di una bella doccia. Si!!! E' quello che ci vuole!!!

...e la caldaia decide di bloccarsi (come sempre) mentre sei sotto la doccia calda.
Tu chiaramente non puoi uscire di corsa e bagnare mezza casa per sbloccarla.
Tag utilizzati: convivendo

Ci siamo

E' passata da poco la mezzanotte. Sono arrivato ufficialmente al 10 luglio 2009, data in cui inizio la convivenza.
Non è ancora iniziata, ma è come se lo fosse.
Ultima notte a casa dei miei, con mia sorella, poi tutto cambierà.
Per sempre.

Stranamente non sono agitato, nè preoccupato, nè rattristato.
Andrà bene, me lo sento. Non sono mai stato così convinto di qualcosa come adesso.

Come cambiano le situazioni... Da un estremo all'altro, per amore. Solo per quello.

Notte blog, notte a tutti. Da domani sono ufficialmente accasato.

Ti amo piccina mia!!!



Un Darkbyte che è arrivato il giorno
Tag utilizzati: convivenza, pensieri e parole

Il fotografo della domenica #54

photos/darkbyte/3693195715/2673/3693195715_3bc9be8262.jpg
Stefania e Stewie

In quei minuti che...

In quei minuti che qualcun altro farebbe qualcos'altro, tipo cazzeggiare o robe simili, in quei minuti là, ecco io in quei minuti invece faccio qualcosa.
Cioè scrivo su questo ormai semi-deserto blog.
Prima di tutto per ricordare a tutti che ho avuto la fortuna di ri-incontrare una persona stupenda come Stefania, con la quale sto benissimo e che mi accetta così come sono senza se e senza ma (e quei pochi se e ma se li tiene per sè) (purtroppo) (ma forse ripensandoci è meglio così, l'esperienza insegna).
E poi perchè tra meno di sei giorni andremo finalmente a vivere insieme, e non vedo l'ora.
Finalmente una vita tutta mia, anzi tutta nostra.
Perchè d'ora in poi non si parlerà più di me o di lei ma di Noi.

Io più te fa noi, la somma.
Io distratto e tu perfetta, tu...

That's all, Folks! (cit.)