Go deep into the implementation of thread safe containers
- 2020-05-10 18:43:41
- OfStack
I recently wrote a small program that USES the thread-safe collection in C#4.0. Think back to writing background windows services long ago when developing with C#2.0. In order to implement the producer and consumer models with multiple threads, it is often necessary to encapsulate thread-safe containers such as generic queues and dictionaries. The following is combined with part of the source code of MS and their own development experience to analyze 1 how to implement a thread-safe container and the implementation of thread-safe container easy to produce problems.
1. ArrayList
The thread-safe ArrayList, which was implemented in earlier versions of C#, can be constructed as a list of thread-safe arrays by:
var array = ArrayList.Synchronized(new ArrayList());
We start with the Synchronized method and analyze its source code to see how to achieve thread safety:
Synchronized /// <summary>Returns an <see cref="T:System.Collections.ArrayList" /> wrapper that is synchronized (thread safe).</summary>
/// <returns>An <see cref="T:System.Collections.ArrayList" /> wrapper that is synchronized (thread safe).</returns>
/// <param name="list">The <see cref="T:System.Collections.ArrayList" /> to synchronize. </param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="list" /> is null. </exception>
/// <filterpriority>2</filterpriority>
[HostProtection(SecurityAction.LinkDemand, Synchronization = true)]
public static ArrayList Synchronized(ArrayList list)
{
if (list == null)
{
throw new ArgumentNullException("list");
}
return new ArrayList.SyncArrayList(list);
}
Following along, we found that SyncArrayList is a private class inherited from ArrayList. The implementation of internal thread-safe methods has been analyzed, and many of them are lock (note lock_root object, not array list instance object) 1.
lock (this._root)
You can view the SyncArrayList source code:
SyncArrayList [Serializable]
private class SyncArrayList : ArrayList
{
private ArrayList _list;
private object _root;
public override int Capacity
{
get
{
int capacity;
lock (this._root)
{
capacity = this._list.Capacity;
}
return capacity;
}
set
{
lock (this._root)
{
this._list.Capacity = value;
}
}
}
public override int Count
{
get
{
int count;
lock (this._root)
{
count = this._list.Count;
}
return count;
}
}
public override bool IsReadOnly
{
get
{
return this._list.IsReadOnly;
}
}
public override bool IsFixedSize
{
get
{
return this._list.IsFixedSize;
}
}
public override bool IsSynchronized
{
get
{
return true;
}
}
public override object this[int index]
{
get
{
object result;
lock (this._root)
{
result = this._list[index];
}
return result;
}
set
{
lock (this._root)
{
this._list[index] = value;
}
}
}
public override object SyncRoot
{
get
{
return this._root;
}
}
internal SyncArrayList(ArrayList list)
: base(false)
{
this._list = list;
this._root = list.SyncRoot;
}
public override int Add(object value)
{
int result;
lock (this._root)
{
result = this._list.Add(value);
}
return result;
}
public override void AddRange(ICollection c)
{
lock (this._root)
{
this._list.AddRange(c);
}
}
public override int BinarySearch(object value)
{
int result;
lock (this._root)
{
result = this._list.BinarySearch(value);
}
return result;
}
public override int BinarySearch(object value, IComparer comparer)
{
int result;
lock (this._root)
{
result = this._list.BinarySearch(value, comparer);
}
return result;
}
public override int BinarySearch(int index, int count, object value, IComparer comparer)
{
int result;
lock (this._root)
{
result = this._list.BinarySearch(index, count, value, comparer);
}
return result;
}
public override void Clear()
{
lock (this._root)
{
this._list.Clear();
}
}
public override object Clone()
{
object result;
lock (this._root)
{
result = new ArrayList.SyncArrayList((ArrayList)this._list.Clone());
}
return result;
}
public override bool Contains(object item)
{
bool result;
lock (this._root)
{
result = this._list.Contains(item);
}
return result;
}
public override void CopyTo(Array array)
{
lock (this._root)
{
this._list.CopyTo(array);
}
}
public override void CopyTo(Array array, int index)
{
lock (this._root)
{
this._list.CopyTo(array, index);
}
}
public override void CopyTo(int index, Array array, int arrayIndex, int count)
{
lock (this._root)
{
this._list.CopyTo(index, array, arrayIndex, count);
}
}
public override IEnumerator GetEnumerator()
{
IEnumerator enumerator;
lock (this._root)
{
enumerator = this._list.GetEnumerator();
}
return enumerator;
}
public override IEnumerator GetEnumerator(int index, int count)
{
IEnumerator enumerator;
lock (this._root)
{
enumerator = this._list.GetEnumerator(index, count);
}
return enumerator;
}
public override int IndexOf(object value)
{
int result;
lock (this._root)
{
result = this._list.IndexOf(value);
}
return result;
}
public override int IndexOf(object value, int startIndex)
{
int result;
lock (this._root)
{
result = this._list.IndexOf(value, startIndex);
}
return result;
}
public override int IndexOf(object value, int startIndex, int count)
{
int result;
lock (this._root)
{
result = this._list.IndexOf(value, startIndex, count);
}
return result;
}
public override void Insert(int index, object value)
{
lock (this._root)
{
this._list.Insert(index, value);
}
}
public override void InsertRange(int index, ICollection c)
{
lock (this._root)
{
this._list.InsertRange(index, c);
}
}
public override int LastIndexOf(object value)
{
int result;
lock (this._root)
{
result = this._list.LastIndexOf(value);
}
return result;
}
public override int LastIndexOf(object value, int startIndex)
{
int result;
lock (this._root)
{
result = this._list.LastIndexOf(value, startIndex);
}
return result;
}
public override int LastIndexOf(object value, int startIndex, int count)
{
int result;
lock (this._root)
{
result = this._list.LastIndexOf(value, startIndex, count);
}
return result;
}
public override void Remove(object value)
{
lock (this._root)
{
this._list.Remove(value);
}
}
public override void RemoveAt(int index)
{
lock (this._root)
{
this._list.RemoveAt(index);
}
}
public override void RemoveRange(int index, int count)
{
lock (this._root)
{
this._list.RemoveRange(index, count);
}
}
public override void Reverse(int index, int count)
{
lock (this._root)
{
this._list.Reverse(index, count);
}
}
public override void SetRange(int index, ICollection c)
{
lock (this._root)
{
this._list.SetRange(index, c);
}
}
public override ArrayList GetRange(int index, int count)
{
ArrayList range;
lock (this._root)
{
range = this._list.GetRange(index, count);
}
return range;
}
public override void Sort()
{
lock (this._root)
{
this._list.Sort();
}
}
public override void Sort(IComparer comparer)
{
lock (this._root)
{
this._list.Sort(comparer);
}
}
public override void Sort(int index, int count, IComparer comparer)
{
lock (this._root)
{
this._list.Sort(index, count, comparer);
}
}
public override object[] ToArray()
{
object[] result;
lock (this._root)
{
result = this._list.ToArray();
}
return result;
}
public override Array ToArray(Type type)
{
Array result;
lock (this._root)
{
result = this._list.ToArray(type);
}
return result;
}
public override void TrimToSize()
{
lock (this._root)
{
this._list.TrimToSize();
}
}
}
Summary of ArrayList's thread-safe implementation process: define SyncArrayList as a private implementation of ArrayList, implement thread safety internally through lock synchronous construction of subclasses, and indirectly call subclasses externally through Synchronized in ArrayList.
2. Hashtable
Similarly, the thread-safe Hashtable was implemented in an earlier version of C#, which was also a cache container used in earlier development. You can construct a thread-safe hash table by:
var ht = Hashtable.Synchronized(new Hashtable());
Similarly, we start with the Synchronized method and analyze its source code to see how to achieve thread safety:
Synchronized /// <summary>Returns a synchronized (thread-safe) wrapper for the <see cref="T:System.Collections.Hashtable" />.</summary>
/// <returns>A synchronized (thread-safe) wrapper for the <see cref="T:System.Collections.Hashtable" />.</returns>
/// <param name="table">The <see cref="T:System.Collections.Hashtable" /> to synchronize. </param>
/// <exception cref="T:System.ArgumentNullException">
/// <paramref name="table" /> is null. </exception>
/// <filterpriority>1</filterpriority>
[HostProtection(SecurityAction.LinkDemand, Synchronization = true)]
public static Hashtable Synchronized(Hashtable table)
{
if (table == null)
{
throw new ArgumentNullException("table");
}
return new Hashtable.SyncHashtable(table);
}
Following along, we found that SyncHashtable is a private class inherited from Hashtable and IEnumerable interfaces. After analysis of the implementation of internal thread-safe methods, many of them are like lock (note lock hash SyncRoot Object instance object, not the hash table instance) 1:
lock (this._table.SyncRoot)
Paste 1 SyncHashtable source code:
[Serializable]
private class SyncHashtable : Hashtable, IEnumerable
{
protected Hashtable _table;
public override int Count
{
get
{
return this._table.Count;
}
}
public override bool IsReadOnly
{
get
{
return this._table.IsReadOnly;
}
}
public override bool IsFixedSize
{
get
{
return this._table.IsFixedSize;
}
}
public override bool IsSynchronized
{
get
{
return true;
}
}
public override object this[object key]
{
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
return this._table[key];
}
set
{
lock (this._table.SyncRoot)
{
this._table[key] = value;
}
}
}
public override object SyncRoot
{
get
{
return this._table.SyncRoot;
}
}
public override ICollection Keys
{
get
{
ICollection keys;
lock (this._table.SyncRoot)
{
keys = this._table.Keys;
}
return keys;
}
}
public override ICollection Values
{
get
{
ICollection values;
lock (this._table.SyncRoot)
{
values = this._table.Values;
}
return values;
}
}
internal SyncHashtable(Hashtable table)
: base(false)
{
this._table = table;
}
internal SyncHashtable(SerializationInfo info, StreamingContext context)
: base(info, context)
{
this._table = (Hashtable)info.GetValue("ParentTable", typeof(Hashtable));
if (this._table == null)
{
throw new SerializationException(Environment.GetResourceString("Serialization_InsufficientState"));
}
}
[SecurityCritical]
public override void GetObjectData(SerializationInfo info, StreamingContext context)
{
if (info == null)
{
throw new ArgumentNullException("info");
}
lock (this._table.SyncRoot)
{
info.AddValue("ParentTable", this._table, typeof(Hashtable));
}
}
public override void Add(object key, object value)
{
lock (this._table.SyncRoot)
{
this._table.Add(key, value);
}
}
public override void Clear()
{
lock (this._table.SyncRoot)
{
this._table.Clear();
}
}
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public override bool Contains(object key)
{
return this._table.Contains(key);
}
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public override bool ContainsKey(object key)
{
return this._table.ContainsKey(key);
}
public override bool ContainsValue(object key)
{
bool result;
lock (this._table.SyncRoot)
{
result = this._table.ContainsValue(key);
}
return result;
}
public override void CopyTo(Array array, int arrayIndex)
{
lock (this._table.SyncRoot)
{
this._table.CopyTo(array, arrayIndex);
}
}
public override object Clone()
{
object result;
lock (this._table.SyncRoot)
{
result = Hashtable.Synchronized((Hashtable)this._table.Clone());
}
return result;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this._table.GetEnumerator();
}
public override IDictionaryEnumerator GetEnumerator()
{
return this._table.GetEnumerator();
}
public override void Remove(object key)
{
lock (this._table.SyncRoot)
{
this._table.Remove(key);
}
}
public override void OnDeserialization(object sender)
{
}
internal override KeyValuePairs[] ToKeyValuePairsArray()
{
return this._table.ToKeyValuePairsArray();
}
}
Summary of Hashtable's thread-safe implementation process: define SyncHashtable, the private implementation of Hashtable, the thread-safe implementation of lock through lock synchronous construction inside the subclass, and the external indirect subclass through Synchronized in Hashtable.
3. Thread safe container in 4.0
1, ConcurrentQueue
From the implementation analysis above, encapsulating a thread-safe container doesn't seem like much of a challenge, except for the fear of exception handling in a thread-safe container. Perhaps there is a brighter realization?
In 4.0, there is an System. Collections. Concurrent namespace
<
T
>
, IEnumerable
<
T
>
, ICollection, IEnumerable interface, internally realize thread safety, through SpinWait and through the interlock structure (Interlocked) and SpinWait encapsulation Segment, indirectly realize thread safety. The implementation of Segment is more complex, and thread safety is closely related to the methods of TryXXX, the source code is as follows:
private class Segment
{
internal T[] m_array;
private int[] m_state;
private ConcurrentQueue<T>.Segment m_next;
internal readonly long m_index;
private int m_low;
private int m_high;
internal ConcurrentQueue<T>.Segment Next
{
get
{
return this.m_next;
}
}
internal bool IsEmpty
{
get
{
return this.Low > this.High;
}
}
internal int Low
{
get
{
return Math.Min(this.m_low, 32);
}
}
internal int High
{
get
{
return Math.Min(this.m_high, 31);
}
}
internal Segment(long index)
{
this.m_array = new T[32];
this.m_state = new int[32];
this.m_high = -1;
this.m_index = index;