Chiarimento di Lettura e Scrittura su un C# dizionario

Question

Nel contesto di questa dichiarazione,

Un dizionario può supportare più lettori simultaneamente, purché come la raccolta non viene modificato. Anche così, l'enumerazione tramite una raccolta non è intrinsecamente una procedura thread-safe . Nel raro caso in cui un'enumerazione contende con accessi in scrittura, la raccolta deve essere bloccata durante l'intera enumerazione . Per consentire alla collezione di accedere a più thread per la lettura e scrittura , è necessario implementare la propria sincronizzazione.

Cosa significa lettura e scrittura? La mia comprensione è che una lettura è un'operazione che cerca una chiave e fornisce un riferimento al suo valore e una scrittura è un'operazione che aggiunge o rimuove una coppia di valori chiave dal dizionario. Tuttavia, non riesco a trovare nulla di conclusivo riguardo a questo.

Quindi la grande domanda è, mentre si implementa un dizionario thread-safe, un'operazione che aggiorna il valore di una chiave esistente nel dizionario dovrebbe essere considerata un lettore o uno scrittore? Ho intenzione di avere più thread che accedono a chiavi univoche in un dizionario e di modificare i loro valori, ma i thread non aggiungeranno/rimuoveranno nuove chiavi.

L'ovvia implicazione, assumendo la modifica di un valore esistente non è un'operazione di scrittura sul dizionario, è che la mia implementazione del threaday dizione sicura può essere molto più efficiente, in quanto non avrei bisogno di ottenere un blocco esclusivo ogni volta Cerco di aggiornare il valore su una chiave esistente.

L'utilizzo di ConcurrentDictionary da .Net 4.0 non è un'opzione.

Answer 1

sovrascrivere un valore esistente dovrebbe essere trattato come un'operazione di scrittura

Answer 2

Modifica di un valore è una scrittura e introduce una condizione di competizione.

Diciamo che il valore originale di mydict [5] = 42. Uno aggiornamenti filo mydict [5] per essere 112. Un altro thread aggiornamenti mydict [5] per essere 837.

cosa dovrebbe il valore di mydict [5] essere alla fine? L'ordine dei thread è importante in questo caso, ovvero è necessario assicurarsi che l'ordine sia esplicito o che non scriva.

Answer 3

Qualsiasi cosa che possa influire sui risultati di un'altra lettura deve essere considerata una scrittura.

Modifica di una chiave è più sicuramente una scrittura in quanto causerà l'elemento di muoversi nel hash interna o di un indice o comunque dizionari fanno il loro O (n log()) ... roba

Cosa si potrebbe desiderare a fare è guardare ReaderWriterLock

http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlock.aspx

Answer 4

Aggiornare un valore è concettualmente un'operazione di scrittura. Quando si aggiorna un valore con accesso concorrente in cui viene eseguita una lettura prima che una scrittura sia completata, si legge un vecchio valore. Quando due scritture sono in conflitto, è possibile memorizzare il valore errato.

L'aggiunta di un nuovo valore potrebbe innescare una crescita della memoria sottostante. In questo caso viene allocata una nuova memoria, tutti gli elementi vengono copiati nella nuova memoria, il nuovo elemento viene aggiunto, l'oggetto dizionario viene aggiornato per fare riferimento alla nuova posizione di memoria per la memorizzazione e la vecchia memoria viene rilasciata e disponibile per la garbage collection. Durante questo periodo, più di una scrittura potrebbe causare un grosso problema. Due scritture allo stesso tempo potrebbero far scattare due istanze di questa copia di memoria. Se segui la logica, vedrai che un elemento andrà perso poiché solo l'ultimo thread per aggiornare il riferimento saprà degli elementi esistenti e non degli altri elementi che stavano cercando di essere aggiunti.

ICollection provides a member to synchronize access e il riferimento rimane valido per tutte le operazioni di crescita/contrazione.

Answer 5

Un'operazione di lettura è tutto ciò che ottiene una chiave o un valore da un Dictionary, un'operazione di scrittura è qualsiasi cosa che aggiorna o aggiunge una chiave o un valore. Quindi un processo che aggiorna una chiave sarebbe considerato uno scrittore.

Un modo semplice per fare un dizionario thread-safe è quello di creare una propria implementazione di IDictionary che blocca semplicemente un mutex e poi inoltra la chiamata ad un'implementazione:

public class MyThreadSafeDictionary<T, J> : IDictionary<T, J> 
{ 
     private object mutex = new object(); 
     private IDictionary<T, J> impl; 

     public MyThreadSafeDictionary(IDictionary<T, J> impl) 
     { 
      this.impl = impl; 
     } 

     public void Add(T key, J value) 
     { 
     lock(mutex) { 
      impl.Add(key, value); 
     } 
     } 

     // implement the other methods as for Add 
} 

Si potrebbe sostituire il mutex con un lettore - Blocco del writer se si stanno avendo dei thread solo per leggere il dizionario.

Si noti inoltre che gli oggetti Dictionary non supportano la modifica delle chiavi; l'unico modo sicuro per ottenere quello che vuoi è rimuovere la coppia chiave/valore esistente e aggiungerne una nuova con la chiave aggiornata.

Answer 6

Un punto importante non ancora menzionato è che se TValue è un tipo di classe, le cose detenuti da un Dictionary<TKey,TValue> saranno i identità dei TValue oggetti. Se si riceve un riferimento dal dizionario, il dizionario non saprà né si preoccuperà di ciò che si può fare con l'oggetto a cui si fa riferimento.

un utile poco classe di utilità nei casi in cui tutti i tasti associati a un dizionario sarà conosciuto in anticipo di codice che ha bisogno di usare è:

class MutableValueHolder<T> 
{ 
    public T Value; 
} 

Se uno vuole avere multi-threaded codice conta quante volte le varie stringhe appaiono in un gruppo di file, e uno sa in anticipo tutte le stringhe di interesse, si può quindi usare qualcosa come un Dictionary<string, MutableValueHolder<int>> per quello scopo. Una volta caricato il dizionario con tutte le stringhe appropriate e un'istanza MutableValueHolder<int> per ciascuna, qualsiasi numero di thread può recuperare riferimenti a oggetti MutableValueHolder<int> e utilizzare Threading.Interlocked.Increment o altri metodi simili per modificare lo Value associato a ciascuno, senza dover scrivere al Dizionario a tutti.