:strip_icc():strip_exif()/u/126096/crop580e4f8566fec_cropped.jpeg?f=community)
Zoals ik misschien al aangegeven heb vind ik het de laaste tijd interessant om van vrij simpele algoritmen een multithreaded variant te maken, gewoon als oefening.
Nu ben ik op dit moment bezig met MergeSort. Eerst even de singelthreaded variant gemaakt, die werkt prima. Daarna aan de slag gegaan met de multithreaded versie. Maar nu stuit ik op het volgende probleem.
-Elke keer splits MergeSort de huidige lijst in 2 lijsten, de twee nieuwe lijsten laat ik weer spliten door 2 nieuwe threads (enqueuen in een threadpool). Hier laat ik het vorige thread op wachten via WaitHandle.WaitAll,
Elke keer als ik iets in de wachtrij van de ThreadPool stop geef ik deze een nieuw manualResetEvent, zoals hier te zien is.
Uiteindelijk komt de mergesort 'in het diepste thread' uit op de volgende code. Die helemaal in het begin staat.
Hier returned hij dus zonder 2 nieuwe threads aan te maken en in de wacht te schieten.
Het returnen komt uit op de volgende methode:
Zoals te zien is signaleer ik hier via doneEvent.Set() dat dit thread klaar is. Als de 2 diepste threads een signaal hebben gegeven zou WaitHandle.WaitAll het thread net hier boven verder moeten laten gaan, en zo voorts.
Alleen blijkt nu dat de WaitHandle niet, of iig niet lang genoeg het bovenste thread in de wacht zet. Als ik namelijk na WaitHandle.WaitAll de volgende code zet:
Print hij slechts 1x "DAT: 3,3" (ik start met een rij van 6 ints). Hij loopt dus meteen door, komt niet in de andere threads, of start iig de andere threads zonder te wachten en komt nooit voorbij de WaitHandle in de andere threads.
Ik heb zelf al even lopen kijken, en dus al aardig wat gedebugged, maar ik kom er niet uit waarom die WaitAll niet werkt. zoals gezecht maak ik telkens 2 nieuwe manualResetEvents.
De voorbeeld code die ik gebruik hebt is: http://msdn.microsoft.com/en-us/library/3dasc8as(VS.80).aspx waar ze haast dezelfde techniek gebruiken.
Ziet iemand het?
Voor de volledigheid nog even alle relevante code onder elkaar zodat ik niet net wat mis (geprobeerd zo kort mogelijk te houden).
Nu ben ik op dit moment bezig met MergeSort. Eerst even de singelthreaded variant gemaakt, die werkt prima. Daarna aan de slag gegaan met de multithreaded versie. Maar nu stuit ik op het volgende probleem.
-Elke keer splits MergeSort de huidige lijst in 2 lijsten, de twee nieuwe lijsten laat ik weer spliten door 2 nieuwe threads (enqueuen in een threadpool). Hier laat ik het vorige thread op wachten via WaitHandle.WaitAll,
Elke keer als ik iets in de wachtrij van de ThreadPool stop geef ik deze een nieuw manualResetEvent, zoals hier te zien is.
C#:
1
2
3
4
5
6
7
8
9
10
11
| ManualResetEvent[] doneEvents = new ManualResetEvent[2]; doneEvents[0] = new ManualResetEvent(false); doneEvents[1] = new ManualResetEvent(false); MergeSort<T> contextLeft = new MergeSort<T>() { data = left, doneEvent = doneEvents[0] }; MergeSort<T> contextRight = new MergeSort<T>() { data = right, doneEvent = doneEvents[1] }; ThreadPool.QueueUserWorkItem(ThreadPoolCallback, contextLeft); ThreadPool.QueueUserWorkItem(ThreadPoolCallback, contextRight); WaitHandle.WaitAll(doneEvents); |
Uiteindelijk komt de mergesort 'in het diepste thread' uit op de volgende code. Die helemaal in het begin staat.
C#:
1
2
3
4
| if (data.Length <= 1) { return data; } |
Hier returned hij dus zonder 2 nieuwe threads aan te maken en in de wacht te schieten.
Het returnen komt uit op de volgende methode:
C#:
1
2
3
4
5
6
| private void ThreadPoolCallback(object threadContext) { MergeSort<T> context = (MergeSort<T>)threadContext; context.data = context.MultiThreaded(context.data); doneEvent.Set(); } |
Zoals te zien is signaleer ik hier via doneEvent.Set() dat dit thread klaar is. Als de 2 diepste threads een signaal hebben gegeven zou WaitHandle.WaitAll het thread net hier boven verder moeten laten gaan, en zo voorts.
Alleen blijkt nu dat de WaitHandle niet, of iig niet lang genoeg het bovenste thread in de wacht zet. Als ik namelijk na WaitHandle.WaitAll de volgende code zet:
C#:
1
| Console.Out.WriteLine("DAT: " + left.Length + ", " + right.Length); |
Print hij slechts 1x "DAT: 3,3" (ik start met een rij van 6 ints). Hij loopt dus meteen door, komt niet in de andere threads, of start iig de andere threads zonder te wachten en komt nooit voorbij de WaitHandle in de andere threads.
Ik heb zelf al even lopen kijken, en dus al aardig wat gedebugged, maar ik kom er niet uit waarom die WaitAll niet werkt. zoals gezecht maak ik telkens 2 nieuwe manualResetEvents.
De voorbeeld code die ik gebruik hebt is: http://msdn.microsoft.com/en-us/library/3dasc8as(VS.80).aspx waar ze haast dezelfde techniek gebruiken.
Ziet iemand het?
Voor de volledigheid nog even alle relevante code onder elkaar zodat ik niet net wat mis (geprobeerd zo kort mogelijk te houden).
C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| //Helper variables protected T[] data; protected ManualResetEvent doneEvent; public T[] MultiThreaded(T[] data) { if (data.Length <= 1) { return data; } int mid = data.Length / 2; T[] left = new T[mid]; T[] right = new T[data.Length - mid]; T[] result; for (int i = 0; i < mid; ++i) { left[i] = data[i]; } for (int i = mid; i < data.Length; i++) { right[i - mid] = data[i]; } //Interesting part ManualResetEvent[] doneEvents = new ManualResetEvent[2]; doneEvents[0] = new ManualResetEvent(false); doneEvents[1] = new ManualResetEvent(false); MergeSort<T> contextLeft = new MergeSort<T>() { data = left, doneEvent = doneEvents[0] }; MergeSort<T> contextRight = new MergeSort<T>() { data = right, doneEvent = doneEvents[1] }; ThreadPool.QueueUserWorkItem(ThreadPoolCallback, contextLeft); ThreadPool.QueueUserWorkItem(ThreadPoolCallback, contextRight); WaitHandle.WaitAll(doneEvents); Console.Out.WriteLine("DAT: " + left.Length + ", " + right.Length); left = contextLeft.data; right = contextRight.data; if (left[left.Length - 1].CompareTo(right[0]) > 0) { result = Merge(left, right); } else { result = Append(left, right); } return result; } private void ThreadPoolCallback(object threadContext) { MergeSort<T> context = (MergeSort<T>)threadContext; context.data = context.MultiThreaded(context.data); doneEvent.Set(); } |
:strip_icc():strip_exif()/u/43400/avatar.jpeg?f=community){kind=avatar}
./u/249034/arrow.png?f=community){kind=icon}
Kijk eens naar /u/112490/crop5821eafeac2b9_cropped.png?f=community)
:strip_icc():strip_exif()/u/12461/crop65b195553d948.jpg?f=community)
:strip_icc():strip_exif()/u/89806/avatar_spockz.jpg?f=community){kind=avatar}