#fork and deterministic resumption of the resulting process

> nicolas cellier wrote:
>> Michael van der Gulik a écrit :
>>
>>> Andreas is a great programmer, but the example he posted had a bug in
>>> it and the proposed fix was incorrect.
>>>
>>
>> The patch is correct in its Squeak context.
>
> Unless I've missed some correction to the patch, the patch isn't
> correct. For example, you'll get an "Invalid priority" walkback if you
> try to evaluate the following using the patch:
>     [[Transcript show: 'works'; cr; flush] fork]
>         forkAt: Processor lowestPriority
>
> Furthermore, it allows lower priority processes to run before a process
> forked at a higher priority. For example, here's an example, that should
> open an inspector on #(1 2 3), but with the patch, it opens on inspector
> on #(1 3 2). The process forked at the lowest priority is run before the
> one forked at a higher priority.
>
> [| queue |
> queue := SharedQueue new.
> [queue nextPut: 3] forkAt: Processor lowestPriority.
> queue nextPut: 1.
> [queue nextPut: 2] fork.
> (Delay forSeconds: 1) wait. "Hack to let the blocks finish"
> (Array
>     with: queue next
>     with: queue next
>     with: queue next) inspect] forkAt: Processor lowestPriority + 1
>
>
> To me, the existing behavior is deterministic. When you fork a process
> at the same priority as the running parent process, then the new forked
> process is added to the list of runnable processes at that priority. The
> parent process continues to run until either a higher priority process
> becomes runnable or it yields control. If a higher priority process
> becomes runnable, then the parent process is suspended and added to the
> end of the runnable processes at its priority. Since it is added at the
> end of the runnable processes list, the forked process will resume
> before the parent resumes.
>
>
> John Brant
>
>

>
>
> On Feb 8, 2008 1:32 PM, Yoshiki Ohshima <[hidden email]> wrote:
>
>     >      Yes, the #lowestPriority case would be a problem.  The
>     >     #lowestPriority would be renamed to #reallyLowestPriority and new
>     >     #lowestPriority would return #reallyLowestPriority+1?
>     >
>     > Would you seriously consider changing this in the squeak.org image?
>    
>      I don't know the right answer to this question.  I understand that
>     most of people don't need it and then don't want to have it.  OTOH, I
>     don't mind to have it and that would prevent a few people in the
>     future stumble on the problem...
>
> In that case, the lowest priority idle thread needs to be of a lower priority than #reallyLowestPriority, so I propose
> also adding #actualReallyLowestPriority to be the lowest priority, then #reallyLowestPriority to be #
> actualReallyLowestPriority+1 and #lowestPriority to be #actualReallyLowestPriority+2.

>
>
>
> On Feb 8, 2008 1:32 PM, Yoshiki Ohshima <[hidden email]> wrote:
> >
> > >      Yes, the #lowestPriority case would be a problem.  The
> > >     #lowestPriority would be renamed to #reallyLowestPriority and new
> > >     #lowestPriority would return #reallyLowestPriority+1?
> > >
> > > Would you seriously consider changing this in the squeak.org image?
> >
> >  I don't know the right answer to this question.  I understand that
> > most of people don't need it and then don't want to have it.  OTOH, I
> > don't mind to have it and that would prevent a few people in the
> > future stumble on the problem...
> >
>
>
> In that case, the lowest priority idle thread needs to be of a lower
> priority than #reallyLowestPriority, so I propose also adding
> #actualReallyLowestPriority to be the lowest priority, then
> #reallyLowestPriority to be #actualReallyLowestPriority+1 and
> #lowestPriority to be #actualReallyLowestPriority+2.
>
>

> 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.
> ].
>

> On Feb 7, 2008, at 22:44 , Igor Stasenko wrote:
>
> > And finally, do you really think, that hiding concurrency issues from
> > the eyes of developer helps him to write good thread-safe code?
> > I think, it's doing exactly opposite: makes him think safe and
> > comfortable.
>
> By that reasoning - how about making the image crash on each
> doesNotUnderstand error? That will teach them! The all purpose
> beginners language C does that, too, and actually goes out if its way
> to not be safe nor comfortable, so surely this must be good.
>

>> *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.
>
> Unless you define a scheduling mechanism, which performs program
> actions in random order (not in sequence, which developer defined).
>
> Now answer me, please, is such kind of tasks (where you need to
> perform action only after previous is complete) worth using concurrent
> threads of execution?

> Igor Stasenko wrote:
> > I'll write only a block code, if you don't mind:
>
> Sure.
>
> > [ i == 1 ifTrue:[ result at: i put: i] ifFalse: [ [ (result at: i-1)
> > isNil ] whileTrue: [].
> > result at: i put: i ] ]
> >
> > .. this will work with assumption that each block keeps own, separate
> > copy of i in it's own context. Otherwise there is need to add code to
> > ensure this.
>
> This doesn't even come close. You can easily see this simply by assuming
> that a theoretical scheduler schedules later threads with a slightly
> higher priority and runs them like todays scheduler. So it would be
> roughly equivalent to the following:
>
> 1 to: 5 do:[:i|
>    [ i == 1 ifTrue:[ result at: i put: i] ifFalse: [ [ (result at: i-1)
> isNil ] whileTrue: [].
>    result at: i put: i ] ] forkAt: Processor activePriority - 10 + i.
> ].
>
> This simply won't do. Try again please. (BTW, for clarification, I
> expect that when the "program" completes that the result array is filled
> in).
>

> >> *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.
> >
> > Unless you define a scheduling mechanism, which performs program
> > actions in random order (not in sequence, which developer defined).
> >
> > Now answer me, please, is such kind of tasks (where you need to
> > perform action only after previous is complete) worth using concurrent
> > threads of execution?
>
> It's not. But that's not my point. You claimed you can write "correct"
> code without assuming anything about scheduling. I'm simply disproving
> you. I'm willing to use any other non-trivial example you can come up
> with (with "trivial" being defined as non-interacting processes). I am
> only using the simplest set of interacting processes I could possibly
> think of - a sequence.
>

> If you want , at some point to get all results filled, you can use
> Semaphore, or plain counter (just make sure you get in to ABA mess
> with it):
>
> sema := Semaphore new.
>  1 to: 5 do:[:i|
>     [ i == 1 ifFalse: [ [ (result at: i-1)  isNil ] whileTrue: [] ].
>      result at: i put: i. sema signal ] forkAt: Processor
> activePriority - 10 + i.
> ].
>
> [ sema excessSignals < 5 ] whileTrue: [].
> <here you got your array filled>

>
> > If you want , at some point to get all results filled, you can use
> > Semaphore, or plain counter (just make sure you get in to ABA mess
> > with it):
> >
> > sema := Semaphore new.
> >  1 to: 5 do:[:i|
> >     [ i == 1 ifFalse: [ [ (result at: i-1)  isNil ] whileTrue: [] ].
> >      result at: i put: i. sema signal ] forkAt: Processor
> > activePriority - 10 + i.
> > ].
> >
> > [ sema excessSignals < 5 ] whileTrue: [].
> > <here you got your array filled>
>
> That's a little better. Still not good enough though. Now let's assume
> that my theoretical scheduler has limits for how many threads it can
> have scheduled at the same time (because of memory limits, cores etc).
> Not unusal at all. Would you like to try again?
>

>
>
> On Feb 8, 2008 10:38 PM, Michael van der Gulik <[hidden email]> wrote:
> >
> >
> >
> >
> > 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.
> >
> >
> >
> >
>
>
> That was a really obvious, stupid bug. Try again:
>
>     anArray := Array new: 3200000.
>     numProcesses := 64.
>     step := anArray size // numProcesses.
>      1 to: anArray size by: step do: [ :i |
>         [
>             i to: i+step-1 do: [ :j |
>                 anArray at: j put: j ]
>         ] fixTemps fork.
>     ].
>
>
> Gulik.
>