Уточнение чтения и записи в словаре C #

Question

В контексте этого утверждения

Словарь может поддерживать несколько читателей одновременно, как долго так как коллекция не изменена. Несмотря на это, перечисляя через коллекция изначально не потокобезопасная процедура. В редких случай, когда утверждается перечисление с доступом записи, коллекция должен быть заблокирован в течение всего перечисление. Разрешить сбор быть доступным для нескольких потоков для читать и писать, вы должны реализовать собственную синхронизацию.

Что означает чтение и запись? Насколько я понимаю, чтение - это операция, которая ищет ключ и предоставляет ссылку на его значение, а запись - это операция, которая добавляет или удаляет пару ключ-значение из словаря. Тем не менее, я не могу найти ничего убедительного в этом отношении.

Таким образом, большой вопрос в том, что при реализации многопоточного словаря будет ли операция, которая обновляет значение для существующего ключа в словаре, считаться читателем или писателем? Я планирую, чтобы несколько потоков обращались к уникальным ключам в словаре и изменяли их значения, но потоки не будут добавлять / удалять новые ключи.

Очевидное следствие того, что изменение существующего значения не является операцией записи в словарь, заключается в том, что моя реализация многопотокового словарей может быть намного более эффективной, поскольку мне не нужно будет получать эксклюзивную блокировку каждый раз Попробуйте обновить значение до существующего ключа.

Использование ConcurrentDictionary из .Net 4.0 не вариант.

Answer 1

Важным моментом, еще не упомянутым, является то, что, если TValue является типом класса, вещи, удерживаемые Dictionary<TKey,TValue>, будут идентичностями TValue объектов . Если кто-то получает ссылку из словаря, словарь не будет ни знать, ни заботиться о том, что он может делать с объектом, на который он ссылается.

Один полезный маленький служебный класс в тех случаях, когда все ключи, связанные со словарем, будут известны заранее для кода, который должен его использовать:

class MutableValueHolder<T>
{
   public T Value;
}

Если кто-то хочет, чтобы многопоточный код подсчитывал, сколько раз различные строки появляются в куче файлов, и кто-то заранее знает все интересующие строки, тогда можно использовать что-то вроде Dictionary<string, MutableValueHolder<int>> для этой цели. Как только словарь загружен со всеми надлежащими строками и экземпляром MutableValueHolder<int> для каждого из них, любое количество потоков может извлечь ссылки на MutableValueHolder<int> объекты и использовать Threading.Interlocked.Increment или другие подобные методы для изменения связанного Value с каждым без необходимости писать в словарь вообще.

Answer 2

перезапись существующего значения должна рассматриваться как операция записи

Answer 3

Операция чтения - это все, что получает ключ или значение из Dictionary, операция записи - это все, что обновляет или добавляет ключ или значение.Таким образом, процесс обновления ключа считается автором записи.

Простой способ создать потокобезопасный словарь - создать собственную реализацию IDictionary, которая просто блокирует мьютекс и затем пересылает вызовреализация:

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
}

Вы можете заменить мьютекс блокировкой чтения-записи, если некоторые потоки читают словарь.

Также обратите внимание, что Dictionary объектыподдержка смены ключей;единственный безопасный способ добиться желаемого - удалить существующую пару ключ / значение и добавить новую с обновленным ключом.

Answer 4

Обновление значения концептуально является операцией записи.При обновлении значения с одновременным доступом, когда чтение выполняется до завершения записи, вы считываете старое значение.При конфликте двух записей может храниться неправильное значение.

Добавление нового значения может вызвать увеличение объема основного хранилища.В этом случае выделяется новая память, все элементы копируются в новую память, добавляется новый элемент, объект словаря обновляется для обращения к новой ячейке памяти для хранения, а старая память освобождается и доступна для сбора мусора.В течение этого времени больше записей может вызвать большие проблемы.Две записи одновременно могут инициировать два экземпляра этого копирования памяти.Если вы будете следовать логике, вы увидите, что элемент будет потерян, поскольку только последний поток, обновляющий ссылку, будет знать о существующих элементах, а не о других элементах, которые пытались добавить.

ICollection предоставляет элемент для синхронизации доступа , и ссылка остается действительной для всех операций увеличения / сжатия.

Answer 5

Все, что может повлиять на результаты другого чтения, следует считать записью.

Смена ключа - это, безусловно, запись, поскольку она заставит элемент перемещаться во внутреннем хеше или индексе, или же словари выполняют свои O (log (n)) вещи ...

Что вы можете сделать, это посмотреть на ReaderWriterLock

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

Answer 6

Изменение значения является записью и вводит условие гонки.

Допустим, исходное значение mydict [5] = 42. Один поток обновляет mydict [5] до 112. Другой поток обновляет mydict [5] быть 837.

Каким должно быть значение mydict [5] в конце?В этом случае важен порядок потоков, т. Е. Нужно либо убедиться, что порядок явный, либо они не записываются.