Geekly articles weekly

Сoncurrentcollections in 10 minutes

图片
摄影： Robert V. Ruggiero

主题不是新的。 但是问一个问题：什么是并发集合以及何时使用它们？ 在面试或代码审查中，我几乎总是得到一个一句话的答案：“它们完全保护我们免受种族条件的影响”（即使从理论上讲也是不可能的）。 或者：“这就像普通的收藏，但是里面的所有东西都被锁住了”，这也不完全符合现实。

本文的目的是在10分钟内弄清主题。 快速熟悉一些细节将很有用。 或在面试前刷新您的记忆。

首先，我们将快速浏览一下System.Collections.Concurrent命名空间的内容。 然后，我们讨论并发和经典集合之间的主要区别，注意一些不明显的地方。 总之，我们讨论了可能的陷阱以及什么时候值得使用哪些类型的集合。

System.Collections.Concurrent中的内容


Intellisense告诉您一些信息：

图片

让我们简要讨论每个课程的目的。

ConcurrentDictionary ：适用于多种情况的线程安全的通用集合。

ConcurrentBag，ConcurrentStack，ConcurrentQueue ：专用集合。 “专业”包括以下几点：

  • 缺少用于访问任意元素的API
  • 众所周知， Stack和Queue具有添加和提取元素的给定顺序
  • 每个线程的ConcurrentBag维护自己的集合以添加项目。 检索时，如果当前流的集合为空，它将从相邻流中“窃取”元素

IProducerConsumerCollection - BlockingCollection类使用的协定（请参见下文）。 由ConcurrentStack ， ConcurrentQueue和ConcurrentBag集合实现。

BlockingCollection-在某些流填充集合而另一些流从集合中提取元素的场景中使用。 一个典型的例子是补充任务队列。 如果在请求下一个元素时集合为空，则读取器将进入新元素的等待状态（轮询）。 通过调用CompleteAdding（）方法，我们可以指示将不再补充集合，那么在读取时将不会执行轮询。 您可以使用IsAddingCompleted （如果不再添加数据， 则为 true ）和IsCompleted （如果不再添加数据且集合为空），则检查集合的状态。

Partitioner，OrderablePartitioner，EnumerablePartitionerOptions-用于实现集合分割的基本构造。 由Parallel.ForEach方法使用，以指定如何在处理线程之间分配项目。

在本文的后面，我们将重点介绍以下集合： ConcurrentDictionary和ConcurrentBag / Stack / Queue 。

并发和经典集合之间的区别


保护内部状态


经典集合的设计考虑了最大性能，因此它们的实例方法不能保证线程安全。

例如，看一下Dictionary.Add方法的源代码。
我们可以看到以下几行（为便于阅读，该代码已简化）：

if (this._buckets == null) { int prime = HashHelpers.GetPrime(capacity); this._buckets = new int[prime]; this._entries = new Dictionary<TKey, TValue>.Entry[prime]; }

如我们所见，字典的内部状态不受保护。 从多个线程添加项目时，可能出现以下情况：

  1. 线程1称为Add ，在输入if条件后立即停止执行
  2. 线程2名为Add ，初始化了集合，添加了项目
  3. 流1恢复工作，重新初始化集合，从而破坏了流2添加的数据。

也就是说，经典收藏不适合从多个流进行记录。

API可以容忍集合的当前状态。


众所周知，不能将重复的键添加到Dictionary中 。 如果我们使用相同的键两次调用Add ，则第二次调用将抛出ArgumentException 。

此保护在单线程方案中很有用。 但是，对于多线程，我们不能确定集合的当前状态。 自然地，只有当我们不断地将自己包裹在锁中时，以下检查才可以拯救我们：

 if (!dictionary.ContainsKey(key)) { dictionary.Add(key, “Hello”); }

基于异常的API是一个错误的选择，并且在多线程方案中将不允许稳定的，可预测的行为。 相反，您需要一个API，该API不对集合的当前状态作出假设，不引发异常，并决定调用者对特定状态的可允许性。

在并发集合中，API建立在TryXXX模式上。 我们使用TryAdd ， TryGetValue和TryRemove方法来代替通常的Add ， Get和Remove 。 并且，如果这些方法返回false ，那么我们将决定这是否是例外情况。

值得注意的是，经典集合现在也具有状态容忍方法。 但是在经典集合中，这样的API是不错的补充，而在并发集合中，这是必须的。

API将竞争条件降至最低


考虑最简单的元素更新操作：

 dictionary[key] += 1;

为了简单起见，代码执行三个动作：从集合中获取值，加1，然后写入新值。 在多线程执行中，代码可能会检索一个值，执行一个增量，然后安全地擦除运行增量时另一个线程写入的值。

为了解决此类问题，并发集合API包含许多帮助程序方法。 例如， TryUpdate方法具有三个参数：键，新值和预期的当前值。 如果集合中的值与期望的值不匹配，则将不执行更新，并且该方法将返回false 。

考虑另一个例子。 从字面上看，以下代码的每一行（包括Console.WriteLine ）都可能导致多线程执行问题：

 if (dictionary.ContainsKey(key)) { dictionary[key] += 1; } else { dictionary.Add(key, 1); } Console.WriteLine(dictionary[key]);

添加或更新值，然后对结果执行操作是一项非常典型的任务。 因此，并发字典具有AddOrUpdate方法，该方法在一个调用中执行一系列操作，并且是线程安全的：

 var result = dictionary.AddOrUpdate(key, 1, (itemKey, itemValue) => itemValue + 1); Console.WriteLine(result);

有一点值得了解。

AddOrUpdate方法的实现调用上述的TryUpdate方法，并将当前值从集合传递给它。 如果更新失败（相邻线程已经更改了值），则重复尝试，并使用更新后的当前值再次调用传输的更新委托。 也就是说， 可以多次调用update委托 ，因此它不应包含任何副作用。

无锁算法和粒度锁


Microsoft在并发集合的性能方面做得很好，而不仅仅是用锁来包装所有操作。 通过研究源代码，您可以看到许多使用粒度锁的示例，使用有能力的算法代替锁，使用特殊指令以及比Monitor更为“轻松”的同步原语的示例。

并发收集不提供什么


从上面的示例中可以明显看出，并发集合不能提供针对竞争条件的完整保护，因此我们必须相应地设计代码。 但这还不是全部，有几点需要了解。

多态与经典收藏


与经典集合一样，并发集合实现IDictionary ， ICollection和IEnumerable接口。 但是，根据定义，这些接口的API的一部分不能是线程安全的。 例如，上面我们讨论过的Add方法。

并发收集在没有线程安全的情况下执行此类合同。 为了“隐藏”不安全的API，他们使用接口的显式实现。 当我们将并发集合传递给接受输入的方法（例如ICollection）时，这一点值得记住。

而且，并发集合不符合关于经典集合的Liskov替代原则 。

例如，经典集合的内容不能在迭代期间进行修改，以下代码将为List类抛出InvalidOperationException ：

 foreach (var element in list) { list.Remove(element); }

如果我们谈论并发集合，那么在枚举时进行修改不会导致异常，因此我们可以从不同的流中同时进行读写。

此外，并发收集在枚举期间以不同方式实现了修改的可能性。 ConcurrentDictionary根本不执行任何检查，也不保证迭代结果，并且ConcurrentStack / Queue / Bag锁定并创建当前状态的副本，并进行迭代。

可能的性能问题


上面我们提到， ConcurrentBag可以“窃取”相邻线程中的元素。 如果您从不同的线程写入和读取ConcurrentBag ，则可能导致性能问题。

同样，并发集合在查询整个集合的状态（ Count ， IsEmpty ， GetEnumerator ， ToArray等）时会施加完全锁定，因此比经典的集合要慢得多。

结论：只有在真正有必要的情况下使用并发集合才值得，因为这种选择不是“免费的”。

什么时候使用什么类型的集合


  • 单线程脚本：仅具有最佳性能的经典集合。
  • 从多个流中记录：仅并发集合可以保护内部状态，并具有合适的API进行竞争性记录。
  • 从多个线程读取：没有明确的建议。 并发收集可能会对整个收集的密集状态请求产生性能问题。 但是，对于经典集合，Microsoft甚至不保证读取操作的性能。 例如，集合的内部实现可能具有在读取数据时启动的惰性属性，因此，从多个线程读取数据时，有可能破坏内部状态。 一个好的平均选择是使用不可变的集合 。
  • 并从多个线程进行读写：唯一并发的集合，同时实现状态保护和安全的API。

结论


在本文中，我们简要地研究了并发集合，何时使用它们以及它们具有哪些细节。 当然，本文不会穷尽该主题，并且通过认真研究多线程集合，您应该更深入地研究。 最简单的方法是查看所使用集合的源代码。 这是有益的，一点也不复杂，代码非常非常易读。

Source: https://habr.com/ru/post/zh-CN473352/

More articles:


All Articles