[C#] List<T> thread safe maken.

[Snake]

Hi,

ik probeer al een week een List<T> thread safe te maken, omdat ik wil enumereren over de list, en toch ondertussen data toevoegen:

ik heb de volgende concept code uitgewerkt:

C#:

using System;
using System.Collections.Generic;
using System.Threading;

namespace TimerTest
{
    class Program
    {
        static void Main(string[] args)
        {
            (new Program()).Start();
        }

        public void Start()
        {
            List<int> list = new List<int>();

            Random r = new Random();

            for (int x = 0; x < 10; x++)
            {
                list.Add(r.Next(1, 100));
            }

            Thread t = new Thread(() =>
                       {
                           
                           System.Threading.Timer timer = new Timer(
                               delegate
                               {
                                   list.Add(r.Next(1, 100));
                               }, null, 1000, 1000);
                       });
            t.Start();

            while (true)
            {
                lock (list)
                {
                    foreach (int item in list)
                    {
                        Console.WriteLine(item.ToString());
                    }
                }
            }

        }
    }
}

En ik heb veel gelezen over thread safety, en het kwam er dus op neer van lock te gebruiken. Maar dan geeft hij nog steeds een invalid operation op de foreach.

Ik had al gelezen over BlockingCollection<T> in het parallel framework van .NET 4.0, maar deze is momenteel nog niet final, dus die gebruik ik liever niet.

Wat vergeet ik?

[Flard]

Je moet de list ook locken in je add-thread, zodat die ook 'blockt' als je aan het uitlezen bent.

[Robinski]

Volgens mij is het probleem met de InvalidOperation met de foreach, dat je de list juist veranderd terwijl je bezig bent in de foreach.

Elke keer als je de List veranderd gaat de Enumerator onderuit

[Woy]

Dit zal beter werken. Je moet zowiezo locken op de SyncRoot van de List, want die is daar voor bedoeld, al kan het natuurlijk ook op de list zelf.

C#:

using System;
using System.Collections.Generic;
using System.Threading;

namespace TimerTest
{
    class Program
    {
        static void Main(string[] args)
        {
            (new Program()).Start();
        }

        public void Start()
        {
            List<int> list = new List<int>();

            Random r = new Random();

            for (int x = 0; x < 10; x++)
            {
                lock(list.SyncRoot)
                {
                    list.Add(r.Next(1, 100));
                }
            }

            Thread t = new Thread(() =>
                       {
                           
                           System.Threading.Timer timer = new Timer(
                               delegate
                               {
                                lock(list.SyncRoot)
                                {
                                    list.Add(r.Next(1, 100));
                                }
                               }, null, 1000, 1000);
                       });
            t.Start();

            while (true)
            {
                lock (list.SyncRoot)
                {
                    foreach (int item in list)
                    {
                        Console.WriteLine(item.ToString());
                    }
                }
            }

        }
    }
}

Voor meer info
http://msdn.microsoft.com/en-us/library/bb356596.aspx

Maar het toevoegen van elementen tijdens het enumereren gaat niet lukken. Dat heeft niet met de Thread-Safety van de List te maken, maar met het feit van dat de Enumerator niet met wijzigende collections overweg kan.

Je zult dus zelf een enumerator moeten maken, of gewoon op index itereren ( Let dan wel op dat je niet out of bounds gaat ).

[ Voor 24% gewijzigd door Woy op 29-12-2008 11:12 ]

[prototype]

@Snake:
In het algemeen is locken op retrieves best nutteloos aangezien aangezien je vaak ook met stale updates te maken hebt. Synchroniseren is daarbij niet zo nuttig (wat je bij de foreach probeert te doen).

Verder heb ik helaas geen intieme kennis van de C# stdlib, maar het zou zomaar kunnen zijn dat de iterator niet direct gebacked is met de elementen van de list zelf, maar met een kopie ervan. Bij het wijzigen van de list kan het dus zo zijn dat er een nieuwe iterator object gemaakt moet worden. De vraag is hier dan ook bij of de foreach wel WEET dat hij nu van die andere iterator object gebruik moet maken. Dit zul je nog eventueel moeten onderzoeken als je met zo'n constructie verder wil gaan.

Zelf zou ik eerder met de klassieke wait-notifyAll concurrency mechanismen aan de haal gaan om dit werkend te krijgen. Je zou hierbij een console-writeline-thread kunnen laten wachten op veranderingen in de list en de list de console-writeline-thread kunnen laten notifyen wanneer er een verandering is in de list (in dit geval dus wanneer er een add operatie is uitgevoerd). Als het niet concurrent hoeft, gebruikt dan de observer pattern.

[Woy]

prototype schreef op maandag 29 december 2008 @ 11:28:
Verder heb ik helaas geen intieme kennis van de C# stdlib, maar het zou zomaar kunnen zijn dat de iterator niet direct gebacked is met de elementen van de list zelf, maar met een kopie ervan. Bij het wijzigen van de list kan het dus zo zijn dat er een nieuwe iterator object gemaakt moet worden. De vraag is hier dan ook bij of de foreach wel WEET dat hij nu van die andere iterator object gebruik moet maken. Dit zul je nog eventueel moeten onderzoeken als je met zo'n constructie verder wil gaan.

Op het moment dat je de lijst wijzigt worden idd alle itterators die op dat moment bestaan invalid, en zul je dus zelf een nieuwe aan moeten maken. Als je toch nog verder itereert zal je een InvalidOperationException krijgen.

prototype schreef op maandag 29 december 2008 @ 11:28:
Zelf zou ik eerder met de klassieke wait-notifyAll concurrency mechanismen aan de haal gaan om dit werkend te krijgen. Je zou hierbij een console-writeline-thread kunnen laten wachten op veranderingen in de list en de list de console-writeline-thread kunnen laten notifyen wanneer er een verandering is in de list (in dit geval dus wanneer er een add operatie is uitgevoerd). Als het niet concurrent hoeft, gebruikt dan de observer pattern.

Dat is idd een betere oplossing.

[Zoijar]

Wat wil je eigenlijk precies doen? Welke data zie je waar? Zelfs als het geen fouten gaf dan gaat het nu mis lijkt me. Eerst draait je main thread, list is leeg, die exit. Einde?

Maar ik denk dat je een producer-consumer zoekt (zoals wel vaker ). http://www.albahari.com/threading/part4.aspx

[Verwijderd]

Ik heb voor dit probleem een implementatie van IList<T> geschreven die al het locken afhandelt bij de methods uit die interface. Je krijgt dan, heel simpel, dit soort regels:

C#:

public void Add(T item)
{
    lock (syncRoot)
        innerList.Add(item);
}

Met de enumerator is het lastiger. Je kunt wel een eigen IEnumerator<T> implementatie maken die bij Dispose de lock vrijgeeft, maar wellicht wil je niet dat je bij elke enumeration die hele list gelockt blijft.

Daarom heb ik een Copy method toegevoegd die thread-safe die lijst kopieert naar een nieuwe list. De enumerator loopt over deze lijst, terwijl de wijzigingen in de originele lijst gedaan worden. Die Copy heeft een parameter die aangeeft of je wilt lezen of schrijven, wat afhangt hoe de enumerator de list lockt m.b.v. ReaderWriterLock. Zo kun je dus de list wijzigen in je loops én is het thread-safe.

[ Voor 3% gewijzigd door Verwijderd op 29-12-2008 13:59 ]

[Snake]

Als ik lock bij de add operation werkt het inderdaad, thanks

Ik moet wel de list eerst casten naar Collection, want SyncRoot wordt blijkbaar niet over-ge-erft.

Ik ga in ieder geval die link van Zoijar doornemen, en eventueel opteren zelf een IList<T> threadsafe te maken.

En eens met reflector kijken naar die BlockingCollection<T>.

[Woy]

Snake schreef op maandag 29 december 2008 @ 14:12:
Als ik lock bij de add operation werkt het inderdaad, thanks

Je kan dan echter niet "Adden" op het moment dat je aan het itereren ben.

Ik moet wel de list eerst casten naar Collection, want SyncRoot wordt blijkbaar niet over-ge-erft.

Hij word wel "over-ge-erft" maar hij is expliciet geimplementeerd.

[Zoijar]

Snake schreef op maandag 29 december 2008 @ 14:12:
en eventueel opteren zelf een IList<T> threadsafe te maken.

Dat is niet zo makkelijk... je moet dan een specificatie van het gedrag geven onder verschillende omstandigheden. Waarschijnlijk invalidate je dan ook alle uitstaande iterators bij een modificatie.

[Snake]

Zoijar schreef op maandag 29 december 2008 @ 20:06:
[...]

Dat is niet zo makkelijk... je moet dan een specificatie van het gedrag geven onder verschillende omstandigheden. Waarschijnlijk invalidate je dan ook alle uitstaande iterators bij een modificatie.

Dus 2 keuzes eigelijk: locken bij adden (wachten tot er niet meer geitereerd wordt), of bij het adden de iterator niet invalidaten right?

[MSalters]

Nou - het hele idee van locken is dat je het op twee plaatsen doet, toevoegen en itereren. Door de lock voorkom je dat je tegelijkertijd toevoegt en itereert.

Je hebt wel gelijk dat er grofweg twee opties genoemd zijn. Dat is namelijk per-element locken bij de iteratie, of per-iteratie. In het eerste geval ziet de iteratie het nieuwe element (mits dat verderop in de collectie wordt toegevoegd natuurlijk). In het tweede geval wordt het element pas toegevoegd nadat de iteratie is afgelopen. Ga zelf maar na hoe dat dan met locks werkt. Een derde variant bestaat in theorie ook, die neerkomt op Copy-on-Write. Vanuit de thread die het element toevoegt is de operatie synchroon en unlocked, maar de itererende thread heeft een andere view van de container. Dit kan snel complex worden, zeker om te implementeren. Ook debuggen is niet meer triviaal, al was het alleen maar omdat de vraag "wat zit er in deze collectie?" dan twee antwoorden heeft.

[EfBe]

MSalters schreef op maandag 29 december 2008 @ 23:40:
Nou - het hele idee van locken is dat je het op twee plaatsen doet, toevoegen en itereren. Door de lock voorkom je dat je tegelijkertijd toevoegt en itereert.

Je hebt wel gelijk dat er grofweg twee opties genoemd zijn. Dat is namelijk per-element locken bij de iteratie, of per-iteratie. In het eerste geval ziet de iteratie het nieuwe element (mits dat verderop in de collectie wordt toegevoegd natuurlijk). In het tweede geval wordt het element pas toegevoegd nadat de iteratie is afgelopen. Ga zelf maar na hoe dat dan met locks werkt. Een derde variant bestaat in theorie ook, die neerkomt op Copy-on-Write. Vanuit de thread die het element toevoegt is de operatie synchroon en unlocked, maar de itererende thread heeft een andere view van de container. Dit kan snel complex worden, zeker om te implementeren. Ook debuggen is niet meer triviaal, al was het alleen maar omdat de vraag "wat zit er in deze collectie?" dan twee antwoorden heeft.

.NET iterators gooien een exception wanneer de source waarover ze iteraten is gewijzigd, dus de iteratie het nieuwe element laten zien kan niet: je moet altijd OF helemaal itereren en writers blocken OF iterators blocken en writers toelaten.

Aangezien dit dus neerkomt op single thread programming, is het wellicht helemaal niet zo handig om deze list in een multi-threaded omgeving te gaan gebruiken: het is dan wellicht beter om readonly collections te gebruiken voor data consumption en dan bv die consumption logic op te delen in meerdere stukken over meerdere threads.

Anderzijds, als de topicstarter per se de list wil sharen tussen multiple threads en de performance naar beneden wil laten gaan door de bottleneck die gecreeerd wordt, dan is het zoals Zoijar al zei wel belangrijk wat je gaat doen, want als er veel readers zijn en nauwelijks writers dan is een reader/writer lock wellicht efficienter dan een low-level monitor.enter.

[MSalters]

Ik heb m'n betoog met opzet technologie-neutraal gehouden. Er zijn meer methoden om over een collectie te itereren dan .NET iterators. Een andere gangbare methode is het gebruiken van indices op een random-access container. Als je het aantal elementen in de collectie niet als vast beschouwt, dan mag je tijdens de iteratie elementen toevoegen (aan het eind, uiteraard)

[Snake]

Ik probeer hier te snappen wat er gezegd wordt, en ik lees het zeker, maar gemakkelijk is het niet hoor

[Zoijar]

Snake schreef op dinsdag 30 december 2008 @ 18:23:
Ik probeer hier te snappen wat er gezegd wordt, en ik lees het zeker, maar gemakkelijk is het niet hoor

Concurrency is ook een van de moeilijkste onderwerpen in de informatica; wen er maar aan

[HawVer]

MSalters schreef op dinsdag 30 december 2008 @ 18:10:
Ik heb m'n betoog met opzet technologie-neutraal gehouden. Er zijn meer methoden om over een collectie te itereren dan .NET iterators. Een andere gangbare methode is het gebruiken van indices op een random-access container. Als je het aantal elementen in de collectie niet als vast beschouwt, dan mag je tijdens de iteratie elementen toevoegen (aan het eind, uiteraard)

Hmm threaded programming intereseert mij wel Maar ik kan geen info vinden over een random access container op google oid. Kun je eens wat meer vertellen?

[user109731]

HawVer schreef op dinsdag 30 december 2008 @ 21:36:
[...]

Hmm threaded programming intereseert mij wel Maar ik kan geen info vinden over een random access container op google oid. Kun je eens wat meer vertellen?

Hij bedoelt een container waarbij je een willekeurig element in constante tijd kunt benaderen, dus zonder iterator te gebruiken (die kan ongeldig worden bij het toevoegen van elementen aan je collectie). Arrays en ArrayLists bijvoorbeeld, in tegenstelling tot dingen als linked lists. Zie ook Wikipedia: Random access

Het idee is dat thread A itereert over de eerste x elementen terwijl thread B elementen daarachter kan toevoegen.

[ Voor 31% gewijzigd door user109731 op 30-12-2008 22:53 ]

[Sebazzz]

Zoijar schreef op dinsdag 30 december 2008 @ 20:35:
[...]

Concurrency is ook een van de moeilijkste onderwerpen in de informatica; wen er maar aan

En nu multicore processors eraan komen met acht cores of meer wordt het ook steeds meer een issue.
Helaas is parallel denken / ontwerpen niet iets waar de mens goed in is.

[Snake]

Sebazzz schreef op dinsdag 30 december 2008 @ 22:57:
[...]

En nu multicore processors eraan komen met acht cores of meer wordt het ook steeds meer een issue.
Helaas is parallel denken / ontwerpen niet iets waar de mens goed in is.

.NET 4.0 heeft een beter threading framework, dus dat is al positief

[HawVer]

JanDM schreef op dinsdag 30 december 2008 @ 22:41:
[...]

Hij bedoelt een container waarbij je een willekeurig element in constante tijd kunt benaderen, dus zonder iterator te gebruiken (die kan ongeldig worden bij het toevoegen van elementen aan je collectie). Arrays en ArrayLists bijvoorbeeld, in tegenstelling tot dingen als linked lists. Zie ook Wikipedia: Random access

Het idee is dat thread A itereert over de eerste x elementen terwijl thread B elementen daarachter kan toevoegen.

Ah precies, ik snap het. Random access was een term die ik nog niet kende. Maar het is vrij eenvoudig. Bedankt voor je uitleg.

[Zoijar]

Sebazzz schreef op dinsdag 30 december 2008 @ 22:57:
En nu multicore processors eraan komen met acht cores of meer wordt het ook steeds meer een issue.
Helaas is parallel denken / ontwerpen niet iets waar de mens goed in is.

Ja, het is ook haast te verwachten dat de software kwaliteit eventjes enorm omlaag gaat, vanwege inefficiente programma's en/of race-conditie achtige bugs. (bijna elk threaded stukje code dat ik op dit forum bv gepost zie worden is gewoon fout)

[ Voor 9% gewijzigd door Zoijar op 31-12-2008 07:26 ]

[HawVer]

Zoijar schreef op woensdag 31 december 2008 @ 07:23:
[...]

Ja, het is ook haast te verwachten dat de software kwaliteit eventjes enorm omlaag gaat, vanwege inefficiente programma's en/of race-conditie achtige bugs. (bijna elk threaded stukje code dat ik op dit forum bv gepost zie worden is gewoon fout)

Het is best complexe stof die je in de meeste starters boeken van programmeertalen niet tegen zult komen. Voor je daar een goede kennis van hebt zul je zelf op onderzoek uit moeten gaan. En dat is iets wat de meeste ontwikkelaars voor zich uit schuiven.

Daarnaast is het multi threaded opzetten van een applicatie vaak overbodig. (in mijn vakgebied) Het kan zelfs averechts werken. De meeste programma's zijn single threaded prima uit te voeren. Het beperkt zich meestal tot synchroon uitvoeren van taken. De zwaardere programma's zoals een Photoshop, 3d studio's, film bewerkings software hebben er meer baat bij.

[Snake]

@Zoijar: heb je aanraders qua boeken, vooral in de richting van .NET over threaded programmeren?

[EfBe]

MSalters schreef op dinsdag 30 december 2008 @ 18:10:
Ik heb m'n betoog met opzet technologie-neutraal gehouden. Er zijn meer methoden om over een collectie te itereren dan .NET iterators. Een andere gangbare methode is het gebruiken van indices op een random-access container. Als je het aantal elementen in de collectie niet als vast beschouwt, dan mag je tijdens de iteratie elementen toevoegen (aan het eind, uiteraard)

Klopt, het punt is echter dat het een kwestie van tijd is voordat topicstarter ook een element wil verwijderen in een andere thread. M.a.w. via indices itereren kan natuurlijk, maar het is IMHO beter om het probleem fundamenteler aan te pakken, nl. te kijken wat de topicstarter nu feitelijk wil doen en of de datastructuur wel gedeeld moet worden tussen threads.

[Zoijar]

Snake schreef op woensdag 31 december 2008 @ 09:46:
@Zoijar: heb je aanraders qua boeken, vooral in de richting van .NET over threaded programmeren?

Ik heb het geleerd uit syllabi met collecties artikelen... en ook veel uit de tanenbaum boeken ("modern operating systems" geloof ik) en uit "distributed systems: principles and paradigms", Tanenbaum, van Steen.

[Snake]

Zoijar schreef op woensdag 31 december 2008 @ 10:49:
[...]

Ik heb het geleerd uit syllabi met collecties artikelen... en ook veel uit de tanenbaum boeken ("modern operating systems" geloof ik) en uit "distributed systems: principles and paradigms", Tanenbaum, van Steen.

Oke Ik zal daar eens naar kijken . Iig moet het niet doorgestreept zijn, maar small

[whoami]

Op het net vind je ook wel een reeks interessante artikels ivm threading & .NET.

Even in m'n favorites duiken, levert dit op:

klik
klik
klik

[roy-t]

Kijk ook even naar de parralels library voor .Net, deze library zal in .Net4.0 standaard worden maar is nu ook al te gebruiken en te downloaden. Zie ook het officieele blog van het MS team wat hierachter zit: http://blogs.msdn.com/pfxteam/default.aspx