Кажется ли это разумным подходом к одновременной комбинации набора/очереди? ⇐ C#

[Anonymous]

Я определенно видел подобные вопросы, заданные здесь по SO, но, что удивительно (учитывая, насколько этот сайт перегружен .NET), похоже, все они были для Java.
Мне нужно по сути, это комбинированный класс set/queue, который является потокобезопасным. Другими словами, это должна быть коллекция FIFO, не допускающая дубликатов (поэтому, если тот же элемент уже находится в очереди, последующие вызовы Enqueue будут возвращать значение false, пока элемент не будет извлечен из очереди).
Я понимаю, что мог бы реализовать это довольно легко с помощью простого HashSet и Queue с блокировкой во всех необходимых местах. Однако мне было интересно реализовать это с помощью классов ConcurrentDictionary и ConcurrentQueue из .NET 4.0 (также доступных как часть расширений Rx для .NET 3.5, что и делает Я использую), которые, как я понимаю, представляют собой коллекции без блокировок*.
Мой основной план состоял в том, чтобы реализовать эту коллекцию примерно так:

Код: Выделить всё

class ConcurrentSetQueue
{
ConcurrentQueue _queue;
ConcurrentDictionary _set;

public ConcurrentSetQueue(IEqualityComparer comparer)
{
_queue = new ConcurrentQueue();
_set = new ConcurrentDictionary(comparer);
}

public bool Enqueue(T item)
{
// This should:
// 1. if the key is not present, enqueue the item and return true
// 2. if the key is already present, do nothing and return false
return _set.AddOrUpdate(item, EnqueueFirst, EnqueueSecond);
}

private bool EnqueueFirst(T item)
{
_queue.Enqueue(item);
return true;
}

private bool EnqueueSecond(T item, bool dummyFlag)
{
return false;
}

public bool TryDequeue(out T item)
{
if (_queue.TryDequeue(out item))
{
// Another thread could come along here, attempt to enqueue, and
// fail; however, this seems like an acceptable scenario since the
// item shouldn't really be considered "popped" until it's been
// removed from both the queue and the dictionary.
bool flag;
_set.TryRemove(item, out flag);

return true;
}

return false;
}
}

Хорошо ли я это обдумал? На первый взгляд, я не вижу каких-либо очевидных ошибок в этой базовой идее, как я написал ее выше. Но возможно я что-то упускаю из виду. Или, возможно, использование ConcurrentQueue с ConcurrentDictionary на самом деле не является разумным выбором по причинам, которые мне не пришли в голову. Или, может быть, кто-то другой уже реализовал эту идею где-нибудь в проверенной в бою библиотеке, и мне просто следует ее использовать.
Любые мысли или полезная информация по этой теме будут очень признательны!
Будем очень признательны!
Любые мысли или полезная информация по этой теме будут высоко оценены!
p>
*Я не знаю, насколько это точно; но тесты производительности показали мне, что они превосходят сопоставимые коллекции, собранные вручную и использующие блокировку со многими потребительскими потоками.

Обновление. Как заметил Брайан, в моей первоначальной идее действительно была проблема с параллелизмом. Это было несколько скрыто сигнатурой метода ConcurrentDictionary.AddOrUpdate, который может убаюкать ленивого мыслителя (вроде меня) и заставить его поверить в то, что все — как добавление набора, так и перемещение в очередь — каким-то образом произойдет все сразу, атомарно (то есть волшебным образом).
Оглядываясь назад, я понимаю, что было глупо с моей стороны иметь такое ожидание. Фактически, независимо от реализации AddOrUpdate, должно быть ясно, что состояние гонки все равно будет существовать в моей первоначальной идее, как отметил Брайан: помещение в очередь произойдет до добавления в набор, следовательно, следующее может произойти последовательность событий:

• Элемент помещен в очередь
• Элемент извлечен из очереди
• Элемент (не) удален из набора
• Элемент добавлен в набор

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

Код: Выделить всё

public bool Enqueue(T item)
{
// This should:
// 1.  return true only when the item is first added to the set
// 2. subsequently return false as long as the item is in the set;
//    and it will not be removed until after it's popped
if (_set.TryAdd(item, true))
{
_queue.Enqueue(item);
return true;
}

return false;
}

При такой структуре вызов Enqueue происходит только один раз — после того, как элемент окажется в наборе. Поэтому дублирование элементов в очереди не должно быть проблемой. И похоже, что, поскольку операции с очередью «записаны» операциями с наборами, то есть элемент помещается только после, когда он добавлен в набор, и извлекается перед он удален из набора — проблемная последовательность событий, описанная выше, произойти не должна.
Что думают люди? Может быть, это решит проблему? (Как и Брайан, я склонен сомневаться в себе и предполагать, что ответ — Нет, и я снова что-то упускаю. Но эй, это не было бы забавным испытанием, если бы оно было простым, верно? ?)

Подробнее здесь: https://stackoverflow.com/questions/382 ... ueue-combo