Зміна ConcurrentDictionary під час перебору

Нещодавно вирішив розібратися з внутрішнім пристроєм потокобезопасных колекцій, відправною точкою у вивченні пристрою ConcurrentDictionary була обрана опублікувати на Хабре. Принцип його роботи описані просто і зрозуміло, за що окреме спасибі автору.

Мені здалося, один момент у публікації висвітлено не досить повно і я вирішив заповнити цю прогалину.

Потокобезопасные колекції розраховані на використання многопоточной середовищі і повинні мати можливість зміни в будь-який момент часу. Відповідно, їх можна змінювати навіть у момент їх перебору. Звідси у мене виникло питання, якщо під час перебору колекція буде змінена, побачить ітератор ці зміни?

Звернемося до статті, зазначеної вище:
GetEnumerator — може повертати старі значення у випадку, якщо зміни були зроблені іншим потоком після виклику методу і того як ітератор пройшов цей елемент.
Ну досить логічно, що зміни елементів, які ітератор вже пройшов не будуть враховані при переборі колекції. А що буде, якщо змінити елемент до якого ітератор ще «не дійшов» або якщо вставити новий елемент в колекцію?
Звернемося до MSDN (російський переклад цієї замітки зроблений не дуже добре, тому я вставлю замітку мовою оригіналу):
Перечислитель, повернений зі словника, безпечно застосовувати одночасно з читанням зі словника і записом в нього, проте він не являє собою моментальний знімок словника. Вміст, доступне через перечислитель, може містити зміни, внесені до словника, після виклику GetEnumerator.

The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.
Мене, як людини з технічною освітою, бентежить формулювання «може містити». Тобто може мати, а може і не містити? Давайте перевіримо:

ConcurrentDictionary<int, string> dictionary = new ConcurrentDictionary<int, string>();
dictionary.TryAdd(0, "item0");
int x = 1;
foreach (var element in dictionary)
{
var tmp = x++;
if (!dictionary.TryAdd(tmp, "item" + tmp.ToString()))
{
throw new Exception("Вставити елемент не вдалося");
}
Console.WriteLine(element);
}


Що ж буде виведене на консоль? Один елемент або програма увійде в нескінченний цикл? Ні те, ні інше. Буде виведено наступне:

[0, item0]
[1, item1]
[2, item2]
[3, item3]
[4, item4]
[5, item5]
[6, item6]
[7, item7]
[8, item8]
[9, item9]
[10, item10]
[11, item11]
[12, item12]
[13, item13]
[14, item14]
[15, item15]
[16, item16]

Виключення не виникло, відповідно, 17 елемент в колекцію був вставлений успішно, але ітератор його не побачив, чому?

Давайте заглянемо в джерело даної колекції, а саме на реалізацію методу GetEnumerator:

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
Node[] buckets = m_tables.m_buckets;

for (int i = 0; i < buckets.Length; i++)
{
// The Volatile.Read ensures that the load of the fields of 'current' doesn't move before the load from buckets[i].
Node current = Volatile.Read<Node>(ref buckets[i]);

while (current != null)
{
yield return new KeyValuePair<TKey, TValue>(current.m_key, current.m_value);
current = current.m_next;
}
}
}

Поле m_tables позначається ключовим словом volatile, тому зміна міститься в ньому масиву Node[] m_buckets видно всім потокам. Кожен елемент цього масиву представляє собою перший елемент у односвязном списку і містить посилання на наступний елемент списку. Далі легко здогадатися, що до тих пір, поки додавання/зміна елементів призводить до зміни самих однозв'язних списків, ітератор «бачить» ці зміни, але зміни самого масиву для ітератора не видно.

Зміна масиву m_buckets відбувається в двох випадках. Перший — це збільшення розміру вставлення елементів, другий — виклик методу Clear() (скидає розмір масиву до значення за замовчуванням).
Операції Update і Remove не змінюють розміру масиву і, відповідно, ці зміни завжди будуть видні для ітератора (звичайно, якщо мова йде про зміну елемента, до якого ітератор ще «не дійшов»).

Висновок
Незважаючи на те, що ми тепер знаємо, коли зміни, внесені під час перебору колекції, буде видно, а коли ні, враховувати ці знання при програмуванні з використанням ConcurrentDictionary не варто. Найкраще дотримуватися правила описаного на MSDN, що внесені зміни можуть бути видні, а можуть і ні.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.