BitArray 线程安全性

Question

BitArray 线程安全性

c#parallel-processingthread-safetybitarray

3

我希望您能提供有关在多个线程同时对System.Collections.BitArray类进行写入时，该类的线程安全性的信息。

具体而言，请考虑以下人为构造的示例：

BitArray bits = new BitArray(1000000);

Parallel.For(0, bits.Count, i =>
{
    bits[i] = i % 3 == 0;
});

直觉告诉我，如果两个线程尝试写入位数组的相同基础整数值，则并发未锁定访问将产生不正确的结果。然而，我找不到任何支持它的证据，并且在运行时我也没有遇到任何问题。这是一个安全的操作吗？如果不是，为什么我没有看到此代码失败或产生不正确的输出？

更新：经过进一步测试，我认为以下测试证明在此示例中使用BitArray是不安全的。另一方面，使用bool[]似乎是安全的。

private static bool CompareBitArrays(BitArray a, BitArray b)
{
    if (a.Count != b.Count) return false;
    for (int i = 0; i < a.Count; i++)
    {
        if (a[i] != b[i]) return false;
    }
    return true;
}

static void Main(string[] args)
{
    int numElements = 1000000;

    //create single-threaded bitarray with certifiably correct values.
    BitArray controlGroup = new BitArray(numElements);
    for (int i = 0; i < numElements; i++)
    {
        controlGroup[i] = i % 3 == 0;
    }

    //create a BitArray and bool array of equal size and fill them using Parallel.For.
    BitArray bits = new BitArray(numElements);
    bool[] bools = new bool[numElements];

    Parallel.For(0, numElements, i =>
    {
        bits[i] = bools[i] = i % 3 == 0;
    });

    //Create a BitArray from the bool array
    BitArray boolBits = new BitArray(bools);

    //Check if they contain correct values
    bool isBitArrayCorrect = CompareBitArrays(controlGroup, bits); //FALSE
    bool isBoolArrayCorrect = CompareBitArrays(controlGroup, boolBits); //TRUE
}

正如我之前提到的，我怀疑问题原因是BitArray中32个值共享数组的同一整数值。

这个逻辑正确吗？

出于问题的考虑，请假设除了代码中显示的线程之外，没有其他线程访问该集合。

- Rotem

3个回答

2

查看 BitArray.Set 方法的代码：

public void Set(int index, bool value)
{
    if (index < 0 || index >= this.Length)
    {
        throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
    }
    if (value)
    {
        this.m_array[index / 32] |= 1 << index % 32;
    }
    else
    {
        this.m_array[index / 32] &= ~(1 << index % 32);
    }
    this._version++; // this is definitely thread-unsafe
}

就你通过索引访问集合成员，而不枚举它，我看到的唯一不安全的代码行是最后一行this._version++;。

但是它确实存在，因此您可以将此代码视为不安全的多线程代码。

- Dennis

你不认为位操作方法是不安全的吗？请参见问题中的更新测试。你如何解释这些结果？ - Rotem

@Rotem: BitArray.Set 位操作方法是不安全的，因为其使用了共享状态（ _version 字段）。这在我的帖子中有说明。需要解释结果是什么？ - Dennis

我问这个问题是因为在你的回答中，你写道唯一不安全的部分是 _version++。 - Rotem

@Rotem：没错。因为没有 _version++，BitArray.Set 只是对 bools[i] = i % 3 == 0 的包装。 - Dennis

5

|= 和 &= 操作不是原子操作，因此无论 _version 如何，都不安全。 - Luke Dunstan

1

我编写了一个ThreadSafeBitArray类，它比普通的锁定BitArray类性能更好。也许有人会发现它有用。

public class ThreadSafeBitArray
{
    private static int[] _cachedShifts;

    static ThreadSafeBitArray()
    {
        _cachedShifts = new int[32];

        for (int index = 0; index < 32; index++)
        {
            _cachedShifts[index] = ((int)1 << index);
        }
    }

    private int _length;
    private int[] _arr;

    public ThreadSafeBitArray(int length)
    {
        _length = length;
        _arr = new int[ToUnderlineLength(length)];
    }

    private int ToUnderlineLength(int length)
    {
        int underlineLength = length / 32;

        if (length % 32 != 0)
        {
            underlineLength++;
        }

        return underlineLength;
    }

    public int Length
    {
        get { return _length; }
    }

    public bool this[int index]
    {
        get
        {
            return (Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0) & (_cachedShifts[index & 31])) != 0;
        }
        set
        {
            int prevValue;

            if (value)
            {
                do
                {
                    prevValue = Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0);
                }
                while (Interlocked.CompareExchange(ref _arr[index >> 5], prevValue | (_cachedShifts[index & 31]), prevValue) != prevValue);
            }
            else
            {
                do
                {
                    prevValue = Interlocked.CompareExchange(ref _arr[index >> 5], 0, 0);
                }
                while (Interlocked.CompareExchange(ref _arr[index >> 5], prevValue & ~(_cachedShifts[index & 31]), prevValue) != prevValue);
            }
        }
    }
}

- DxCK

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tony The Lion · Accepted Answer

我认为MSDN上BitArray的这句话应该能告诉你想知道的一切：

“此实现不提供用于BitArray的同步（线程安全）包装器。枚举集合本质上不是线程安全的过程。即使集合已同步，其他线程仍然可以修改集合，这会导致枚举器抛出异常。为了保证枚举期间的线程安全性，您可以在整个枚举期间锁定集合，或者捕获由其他线程所做更改引起的异常。”

我已经加粗了重要的部分。任何遍历集合的操作都不是线程安全的，因此任何元素的修改也不是线程安全的，你应该锁定整个集合或使用一个线程安全的集合。（虽然我不确定是否存在BitArray）