Как написать список копирования при записи в .NET

Как написать потокобезопасный список, используя модель копирования при записи в .NET?

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

class CopyOnWriteList
{
    private List<string> list = new List<string>();

    private object listLock = new object();

    public void Add(string item)
    {
        lock (listLock)
        {
            list = new List<string>(list) { item };
        }
    }

    public void Remove(string item)
    {
        lock (listLock)
        {
            var tmpList = new List<string>(list);
            tmpList.Remove(item);
            list = tmpList;
        }
    }

    public bool Contains(string item)
    {
        return list.Contains(item);
    }

    public string Get(int index)
    {
        return list[index];
    }
}

ИЗМЕНИТЬ

Чтобы быть более конкретным: является ли приведенный выше код потокобезопасным, или я должен добавить что-то еще? Кроме того, все потоки в конечном итоге увидят изменение в ссылке list? Или, может быть, мне следует добавить ключевое слово volatile в поле списка или Thread.MemoryBarrier в методе Contains между доступом к ссылке и вызовом метода на нем?

Вот, например, реализация Java, выглядит как моя приведенный выше код, но является ли такой подход потокобезопасным в .NET?

И здесь тот же вопрос, но тоже на Java.

Здесь еще один вопрос, связанный с Вот этот.


person Rafał Kłys    schedule 28.06.2013    source источник
comment
Правильнее использовать ConcurrentBag, без необходимости заново изобретать велосипед   -  person cuongle    schedule 28.06.2013
comment
Попробуйте проверить этот вопрос: Какая библиотека .NET поддерживает копирование при записи коллекции?   -  person Alvin Wong    schedule 28.06.2013
comment
@Cuong Le: Согласно MSDN, ConcurrentBag оптимизирован для сценариев, в которых один и тот же поток будет создавать и потреблять данные. Мне нужна оптимизация для редкой записи и частого чтения, копирование при записи может дать мне это.   -  person Rafał Kłys    schedule 28.06.2013
comment
@Элвин Вонг: Это не то, что мне нужно. 1) я не хочу использовать библиотеки F# 2) неизменяемая коллекция — это только часть копирования при записи   -  person Rafał Kłys    schedule 28.06.2013


Ответы (3)


Реализация правильная, так как присвоение ссылок является атомарным в соответствии с Атомарность ссылок на переменные. Я бы добавил volatile к list.

person Vlad I.    schedule 28.06.2013
comment
Спасибо за ваш ответ, но я хотел бы добиться чтения без блокировки из списка. В настоящее время я использую ReaderWriterLockSlim, но надеюсь научиться делать это без него, используя шаблон копирования при записи. - person Rafał Kłys; 28.06.2013
comment
Спасибо, теперь возникает вопрос: нужна ли «изменчивость», чтобы все потоки видели изменения в ссылке «список»? - person Rafał Kłys; 01.07.2013
comment
Посмотрите на volatile в MSDN. Он говорит Fields that are declared volatile are not subject to compiler optimizations that assume access by a single thread. This ensures that the most up-to-date value is present in the field at all times., т.е. чтение и запись гарантированно выполняются в том порядке, в котором они появляются, а чтение\запись гарантированно атомарны. так оно тебе надо? - да. - person Vlad I.; 01.07.2013

Ваш подход выглядит правильным, но я бы рекомендовал использовать string[], а не List<string> для хранения ваших данных. Когда вы добавляете элемент, вы точно знаете, сколько элементов будет в результирующей коллекции, поэтому вы можете создать новый массив точно требуемого размера. При удалении элемента вы можете получить копию ссылки list и найти в ней свой предмет, прежде чем делать копию; если окажется, что предмета не существует, удалять его не нужно. Если он существует, вы можете создать новый массив точного требуемого размера и скопировать в новый массив все элементы, предшествующие или следующие за элементом, который необходимо удалить.

Еще одна вещь, которую вы, возможно, захотите рассмотреть, - это использовать int[1] в качестве флага блокировки и использовать шаблон, например:

static string[] withAddedItem(string[] oldList, string dat)
{
  string[] result = new string[oldList.Length+1];      
  Array.Copy(oldList, result, oldList.Length);
  return result;
}
int Add(string dat) // Returns index of newly-added item
{
  string[] oldList, newList;
  if (listLock[0] == 0)
  {
    oldList  = list;
    newList = withAddedItem(oldList, dat);
    if (System.Threading.Interlocked.CompareExchange(list, newList, oldList) == oldList)
      return newList.Length;
  }
  System.Threading.Interlocked.Increment(listLock[0]);
  lock (listLock)
  {
    do
    {
      oldList  = list;
      newList = withAddedItem(oldList, dat);
    } while (System.Threading.Interlocked.CompareExchange(list, newList, oldList) != oldList);
  }
  System.Threading.Interlocked.Decrement(listLock[0]);
  return newList.Length;
}

Если нет конкуренции за запись, CompareExchange преуспеет без необходимости получения блокировки. Если есть конфликт записи, записи будут сериализованы блокировкой. Обратите внимание, что блокировка здесь не является ни необходимой, ни достаточной для обеспечения корректности. Его цель состоит в том, чтобы избежать пробуксовки в случае конфликта записи. Возможно, что поток № 1 может пройти свой первый тест «если» и получить отключение задачи задачи, в то время как многие другие потоки одновременно пытаются записать список и начать использовать блокировку. Если это произойдет, поток № 1 может "сюрпризовать" поток в блокировке, выполнив свою собственную операцию CompareExchange. Такое действие приведет к тому, что lock-удерживающий поток будет вынужден тратить время на создание нового массива, но такая ситуация должна возникать достаточно редко, чтобы случайные затраты на дополнительную копию массива не имели значения.

person supercat    schedule 04.10.2013
comment
Я посмотрел на копирование при записи, потому что в моем случае добавление и удаление из списка происходит редко (например, раз в месяц), но проверка существования элемента происходит очень часто (много раз в секунду). Мне не нужна оптимизация блокировки в Add и Remove, мне нужна производительность в методе Contains. Копирование при записи обещает это, но я не уверен, что моя вышеприведенная реализация сохраняет потоки в модели памяти .NET. - person Rafał Kłys; 18.10.2013
comment
@RafałKłys: Ваш код попадает в действительно раздражающую серую зону, поскольку большинство реализаций .NET работают на модели памяти x86, которая немного более строга со стороны реализации (более снисходительна для пользователя), чем .NET. Чтобы быть в полной безопасности, может потребоваться добавить явный барьер памяти (я думаю, System.Threading.Thread.MemoryBarrier()) между tmpList.Remove и list = tmpList; Я почти уверен, что в модели x86 это не требуется, но если программа запускалась в какой-либо реализации .NET, отличной от x86, она может понадобиться. - person supercat; 18.10.2013

Да, это потокобезопасно:

  1. Модификации коллекций в Add и Remove выполняются в отдельных коллекциях, что позволяет избежать одновременного доступа к одной и той же коллекции из Add и Remove или из Add/Remove и Contains/Get.

  2. Назначение новой коллекции выполняется внутри lock, который является просто парой Monitor.Enter и Monitor.Exit, которые оба создают полный барьер памяти, как указано здесь, что означает, что после блокировки все потоки должны соблюдать новое значение поля list.

person Rafał Kłys    schedule 23.02.2016