[C#] problema con collezione condivisa

[mad_hhatter]

ho il seguente problema:

devo condividere tra più thread una LISTA di oggetti in modo che la scrittura sia mutuamente esclusiva mentre la lettura deve essere NON mutuamente esclusiva.

ho quindi scelto di usare una variabile intera che tiene traccia degli attuali lettori e che inibisce la scrittura qualora il numero dei lettori sia >0. tale variabile intera è protetta da un monitor per la sincronizzazione degli accessi.

il grosso problema è che i lettori devono poter ENUMERARE gli elementi della lista. Il problema che nasce è, allora, impedire che la lista venga modificata mentre ci sono lettori in lettura senza usare due operazioni separate per disabilitare la scrittura e riabilitarla...

qualche idea?
grazie mille!

[mad_hhatter]

stavo pensando di usare un delegate:

l'enumerazione la faccio in un metodo proprio dell'oggetto condiviso e il lavoro da fare ad ogni itarazione lo passo come delegate... il problema è che non credo di poter impedire accessi in scrittura nell'implementazione del delegate.

[PGI-Bis]

A dirla tutta impedire la modifica durante la lettura è solo una delle possibilità. Esiste una "tecnica" detta copy on write che consiste semplicemente nel creare una nuova lista ogni volta che viene inserito o rimosso un elemento.

Non è una soluzione generale. La sua praticabilità dipende dal contesto in cui la lista, solitamente un array, dovrà operare. E' papabile in caso di basso numero di scritture ed alto numero di letture.

[mad_hhatter]

A dirla tutta impedire la modifica durante la lettura è solo una delle possibilità. Esiste una "tecnica" detta copy on write che consiste semplicemente nel creare una nuova lista ogni volta che viene inserito o rimosso un elemento.

Non è una soluzione generale. La sua praticabilità dipende dal contesto in cui la lista, solitamente un array, dovrà operare. E' papabile in caso di basso numero di scritture ed alto numero di letture.

il problema però resta: se mentre sto leggendo sostituisco la lista?

[PGI-Bis]

No, la cambi quando scrivi. On write. C'è anche l'on read.

Per iterare, l'iteratore deve avere un riferimento alla lista.

Quando aggiungi o rimuovi un elemento pigli la vecchia lista (quella su cui gli iteratori stanno lavorando) e la copi. La copia richiede una lettura della lista, operazioni che puoi eseguire in parallelo senza alcun controllo.

Quando hai copiato la lista, prendi la copia, aggiungi o rimuovi l'elemento, poi rimpiazzi (nella lista) il vecchio riferimento ai dati con il nuovo.

A questo punto gli iteratori che stanno lavorando continueranno a farlo con i valori originali. I nuovi iteratori scorreranno invece una lista aggiornata.

L'atomicità della sostituzione dei riferimenti ti permette di fare il tutto senza un solo lock. Il costo è quello della copia. Non è aggratis e per questo devi valutare bene il contesto d'uso della lista.

Ps: la lettura è un'operazione che non richiede mutua esclusione... rispetto ad altre letture.

[mad_hhatter]

come posso assicurarmi che la sostituzione dei riferimenti sia atomica?

inoltre, se io volessi evitare che possano esistere iteratori che leggono i dati vecchi, ma sempre e solo i dati aggiornati?

[PGI-Bis]

Controlla le specifiche del linguaggio o del compilatore.

[mad_hhatter]

e se io volessi evitare che possano esistere iteratori che leggono i dati vecchi, ma sempre e solo i dati aggiornati?

[PGI-Bis]

L'impossibilità che esistano iteratori vecchi significa o che il codice passa da parallelo a sequenziale o che la faccenda diventa piuttosto interessante.

Ci sono un tot di modi per farlo.

Rendere sequenziale la lista significa prendere e creare una coda di richieste. Tipo ADD, REMOVE, ITERATE. Due o più ITERATE adiacenti possono essere svolte in parallelo. La prima richiesta successiva che non sia un ITERATE resta ferma su una barriera che viene liberata quando tutti gli iteratori abbiano concluso il loro lavoro (cioè le richieste ITERATE siano state completamente consumate).

Così facendo escludiamo che sia possibile modificare la lista durante lo scorrimento.

Oppure rendiamo la lista modificabile durante lo scorrimento.

Ci sono due cose da fare. La prima è escludere che l'estrazione di un elemento dalla lista da parte dell'iteratore confligga con l'inserimento o la rimozione di un elemento. E qui ci metti una mutua esclusione.

La seconda è trattare il caso di inserimento di un valore in una sezione della lista già esaminata dall'iteratore. Questo è più delicato. Ciò che dobbiamo fare è dotare l'iteratore di una piccola (o grande) cache in cui immettere i nuovi elementi inseriti nella lista in un punto già visitato. L'iteratore altro non fa che scorrere tutta la lista e poi scorrere la cache degli elementi inseriti in una posizione antecedente al cursore. C'è un grosso inghippo: l'iterazione risulta in questo caso fuori ordine. Il che potrebbe essere un guaio insuperabile se l'ordine sia necessario.

[mad_hhatter]

ti ringrazio per l'aiuto, prezioso come sempre. ora ci penso un po' su :)