On Feb 8, 2008 7:17 PM, Andreas Raab <andreas.raab at gmx.de> wrote:

> Igor Stasenko wrote:
> > I'd like to emphasize this (please, increase the font size, when you
> > reading following phrase):
> >
> > ...  a program that relies on a particular implementation of
> > scheduling is wrong.
>
> Sorry but that's complete nonsense. If you really believe this then I'll
> challenge you to write a program that you believe is "correct" for the
> following problem: Create a program that will write the numbers 1
> through five from five concurrent threads into an array in the order 1,
> 2, 3, 4, 5. Something that today you could do for example via:
>
> result := Array new: 5.
> 1 to: 5 do:[:i|
>   [result at: i put: i] forkAt: Processor activePriority+1.
> ].
>
> *Regardless* of your implementation I will define a scheduling mechanism
> that breaks your program, e.g., make it behave "wrong". In other words
> if you believe what you write above you won't *ever* be able to write
> correct multi-threaded code.
>


Complete with Squeak-isms:

n := 5.
result := Array new: n.
semaphores := Array new: n.
1 to: n do: [ :each | semaphores at: each put: Semaphore new ].

1 to: n do: [ :each | [
        (semaphores at: each) wait.
        result at: each put: each.
        (each >= semaphores size) ifFalse: [
            (semaphores at: each+1) signal.
        ]
    ] fixTemps fork.
].
(semaphores at: 1) signal.

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.

If items could be added in any order, then the following should work:

n := 15.
result := Array new: n.

1 to: n do: [ :each | [
        result at: each put: each. "Should be an atomic operation"
    ] fixTemps fork.
].

Of course, even on a multi-CPU system, the following would execute faster
because of the overhead of making Processes:

result := (1 to: 5) asArray.

This next version should fill the array, efficiently using the hypothetical
CPU cores available:

go
    | anArray numProcesses step |
    anArray := Array new: 60000. "Assume an even larger number for realistic
examples"
    numProcesses := 32.
    step := anArray size // numProcesses.
    1 to: anArray size by: step do: [ :i |
        [
            i to: (i+numProcesses-1) do: [ :j |
                anArray at: j put: j ]
        ] fixTemps fork.
    ].
    ^ anArray.

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.

Gulik.


-- 
http://people.squeakfoundation.org/person/mikevdg
http://gulik.pbwiki.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20080208/f2affb56/attachment.htm