<br><br><div class="gmail_quote">On Feb 8, 2008 7:17 PM, Andreas Raab <<a href="mailto:andreas.raab@gmx.de">andreas.raab@gmx.de</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">Igor Stasenko wrote:<br>> I'd like to emphasize this (please, increase the font size, when you<br>> reading following phrase):<br>><br>> ... a program that relies on a particular implementation of<br>
> scheduling is wrong.<br><br></div>Sorry but that's complete nonsense. If you really believe this then I'll<br>challenge you to write a program that you believe is "correct" for the<br>following problem: Create a program that will write the numbers 1<br>
through five from five concurrent threads into an array in the order 1,<br>2, 3, 4, 5. Something that today you could do for example via:<br><br>result := Array new: 5.<br>1 to: 5 do:[:i|<br> [result at: i put: i] forkAt: Processor activePriority+1.<br>
].<br><br>*Regardless* of your implementation I will define a scheduling mechanism<br>that breaks your program, e.g., make it behave "wrong". In other words<br>if you believe what you write above you won't *ever* be able to write<br>
correct multi-threaded code.<br></blockquote><div><br><br>Complete with Squeak-isms:<br><br>n := 5.<br>result := Array new: n.<br>semaphores := Array new: n.<br>1 to: n do: [ :each | semaphores at: each put: Semaphore new ].<br>
<br>1 to: n do: [ :each | [<br> (semaphores at: each) wait.<br> result at: each put: each.<br> (each >= semaphores size) ifFalse: [<br> (semaphores at: each+1) signal.<br> ] <br> ] fixTemps fork.<br>
].<br>(semaphores at: 1) signal. <br></div></div><br>I'm mostly sure it's correct, but as with most concurrent code there's probably a bug there somewhere. It's an algorithm that's unable to take advantage of any concurrency because you make the requirement that items get added sequentially. <br>
<br>If items could be added in any order, then the following should work:<br><br>n := 15.<br>result := Array new: n.<br><br>1 to: n do: [ :each | [<br> result at: each put: each. "Should be an atomic operation"<br>
] fixTemps fork.<br>].<br><br>
Of course, even on a multi-CPU system, the following would execute faster because of the overhead of making Processes:<br>
<br>
result := (1 to: 5) asArray.<br><br>This next version should fill the array, efficiently using the hypothetical CPU cores available:<br><br>go<br> | anArray numProcesses step |<br> anArray := Array new: 60000. "Assume an even larger number for realistic examples"<br>
numProcesses := 32. <br> step := anArray size // numProcesses.<br> 1 to: anArray size by: step do: [ :i |<br> [ <br> i to: (i+numProcesses-1) do: [ :j |<br> anArray at: j put: j ]<br>
] fixTemps fork.<br> ].<br> ^ anArray.<br><br>However, it doesn't work except for small numbers. I'd be happy if somebody would be able to provide a fixed version; I can't work it out.<br><br>Gulik.<br>
<br clear="all"><br>-- <br><a href="http://people.squeakfoundation.org/person/mikevdg">http://people.squeakfoundation.org/person/mikevdg</a><br><a href="http://gulik.pbwiki.com/">http://gulik.pbwiki.com/</a>