我目前正在研究一个写时复制集实现,并希望确认它是线程安全的。我敢肯定,唯一可能不这样做的方法是允许编译器在某些方法中重新排序语句。例如,Remove
方法看起来像:
public bool Remove(T item)
{
var newHashSet = new HashSet<T>(hashSet);
var removed = newHashSet.Remove(item);
hashSet = newHashSet;
return removed;
}
其中hashSet定义为
private volatile HashSet<T> hashSet;
所以我的问题是,假设hashSet是volatile
,这是否意味着新集合上的Remove
发生在写入成员变量之前?如果没有,那么其他线程可能会在删除之前看到该集。
我实际上在生产中没有看到任何问题,但我只想确认它是安全的。
更新
更具体地说,还有另一种方法可以获得IEnumerator
:
public IEnumerator<T> GetEnumerator()
{
return hashSet.GetEnumerator();
}
因此,更具体的问题是:是否可以保证返回的IEnumerator
永远不会从移除中抛出ConcurrentModificationException
?
更新2
很抱歉,答案都是来自多个作者的线程安全问题。有人提出了好的观点,但这不是我想在这里找到的。我想知道是否允许编译器将Remove
中的操作重新排序为这样的内容:
var newHashSet = new HashSet<T>(hashSet);
hashSet = newHashSet; // swapped
var removed = newHashSet.Remove(item); // swapped
return removed;
如果这是可能的,这意味着线程可以在分配hashSet
之后,但在删除item
之前调用GetEnumerator
,这可能导致在枚举期间修改集合。
乔·达菲有一篇博客文章说:
负载时易失性意味着ACQUIRE,不多也不少。(有额外的编译器优化限制,当然,比如不允许在环外吊装,但让我们关注MM方面目前。)ACQUIRE的标准定义是存储器操作可以在ACQUIRE指令之前不移动;例如。给定{ld.acq X,ld-Y},ld-Y不能出现在ld.acqX之前。然而,以前的内存操作肯定会在它之后移动;例如。给定{ldX,ld.acqY},ld.aqY确实可以出现在ld之前X.当前运行的唯一处理器Microsoft.NET代码这实际上是IA64,但这是CLRMM比大多数机器都弱。接下来,.NET上的所有商店都是RELEASE(与volatile无关,即volatile在jit方面是无操作代码)。RELEASE的标准定义是以前的记忆RELEASE操作之后,操作可能不会移动;例如给定{stX,st.rel Y},st.rel Y不能出现在stX之前。然而,后续的内存操作确实可以在它之前移动;例如给定{st.rel X,ld Y},ld Y可以在st.rel X.之前移动
我读到的方式是,对newHashSet.Remove
的调用需要ld newHashSet
,而对hashSet
的写入需要st.rel newHashSet
。根据RELEASE的上述定义,在存储RELEASE之后,任何加载都不能移动,因此语句不能重新排序!有人能确认一下吗?请确认一下我的解释是正确的?
考虑使用Interlocked.Exchange(它将保证排序)或Interlocked.CompreExchange(它作为一个侧面好处将允许您检测(并可能从中恢复)对集合的同时写入。很明显,它添加了一些额外的同步级别,因此它与当前代码不同,但更容易推理。
public bool Remove(T item)
{
var old = hashSet;
var newHashSet = new HashSet<T>(old);
var removed = newHashSet.Remove(item);
var current = Interlocked.CompareExchange(ref hashSet, newHashSet, old);
if (current != old)
{
// failed... throw or retry...
}
return removed;
}
在这种情况下,我认为您仍然需要volatile hashSet
。
编辑:
感谢您澄清Remove调用(以及其他集合突变)的外部锁的存在。
由于RELEASE语义,您最终不会将新值存储到hashSet
,直到变量removed
的值被分配后(因为st removed
不能在st.rel hashSet
之后移动)。
因此,GetEnumerator
的"快照"行为将按预期工作,至少对于以类似方式实现的Remove和其他变体而言。
我不能代表C#,但在C中volatile原则上表示并且仅表示变量的内容可以随时更改。它对编译器或CPU重新排序没有任何限制。您所得到的只是编译器/CPU将始终从内存中读取值,而不是信任缓存版本。
然而,我相信在最近的MSVC(因此很可能是C#)中,读取易失性充当加载的内存屏障,而写入充当存储的内存屏障。例如,CPU将停滞,直到所有加载都完成,并且没有任何加载可以通过在易失性读取之下重新排序来逃避这一点(尽管后来的独立加载仍然可能向上移动到内存屏障之上);并且CPU将停滞直到存储已经完成,并且没有存储可以通过在易失性写入之下被重新排序来逃避这一点(尽管稍后的独立写入仍然可以向上移动到存储器屏障之上)。
当只有一个线程在写一个给定的变量(但许多线程在读)时,只有内存屏障才能正确操作。当多个线程可能对给定的变量进行写入时,必须使用原子操作,因为CPU设计基本上在写入时存在竞争条件,因此写入可能会丢失。