Squeak does not do pre-emptive multitasking.

Hi all.

I had some weird behaviour when doing some multi-threaded coding. I
wrote a test (attached) to test the way the VM schedules processes.

I am not impressed. These were the results of running it several times:

t := TestingScheduler new.
t numProcesses: 10.

#(12127412 12126870 12127386 12127374 12127362 0 0 0 0 0)
#(21112051 21112060 21111787 0 0 0 0 0 0 0)
#(25767847 25768314 25767577 0 0 0 0 0 0 0)
#(31379008 31378493 0 0 0 0 0 0 0 0)

What you are looking at is the result of 10 threads battling it out to
increment their respective array elements.

Either:

- My code is borked, which is entirely possible,
- The ProcessScheduler is buggy, or
- Squeak is meant to work like this.

Which of those is true?

I'm running Squeak 3.8 #6665 on what I believe is the latest Linux VM.

Michael.

'From Squeak3.8 of ''5 May 2005'' [latest update: #6665] on 11 June 2006 at 11:26:35 am'!
Object subclass: #TestingScheduler
        instanceVariableNames: 'processes continue counts'
        classVariableNames: ''
        poolDictionaries: ''
        category: 'playing'!

!TestingScheduler methodsFor: 'as yet unclassified' stamp: 'mvdg 6/11/2006 11:26'!
loop: element
        [[ continue ] whileTrue: [
                counts at: element put: ((counts at: element) + 1).
        ] ] forkAt: 10.
        ! !

!TestingScheduler methodsFor: 'as yet unclassified' stamp: 'mvdg 6/8/2006 22:05'!
numProcesses: num
        continue := true.
        counts := Array new: num.
        1 to: num do: [ :each |
                counts at: each put: 0.
                self loop: each.
        ].
        counts inspect.
        (Delay forSeconds: 15) wait.
        continue := false.! !

!TestingScheduler methodsFor: 'as yet unclassified' stamp: 'mvdg 6/8/2006 21:36'!
stop
        continue := false.! !

> From: Michael van der Gulik
> Subject: Squeak does not do pre-emptive multitasking.

Correct, with the following proviso: higher-priority processes *will* pre-empt lower-priority processes.

> #(12127412 12126870 12127386 12127374 12127362 0 0 0 0 0)
> #(21112051 21112060 21111787 0 0 0 0 0 0 0)
> #(25767847 25768314 25767577 0 0 0 0 0 0 0)
> #(31379008 31378493 0 0 0 0 0 0 0 0)

Interesting - I'd be fascinated to know why the numbers are so similar.  Do you have some higher-priority process interrupting at regular intervals?  That would account for the rough equality of the numbers, as it would perturb the scheduling of the lower-priority threads, causing threads after the first to be scheduled.

> Either:
>
> - My code is borked, which is entirely possible,
> - The ProcessScheduler is buggy, or
> - Squeak is meant to work like this.
>
> Which of those is true?

I've not *found* any bugs in the scheduler, as long as you remember that:

- Higher-priority processes pre-empt lower-priority processes;

- Processes at the same priority do not pre-empt each other;

- A loop that forks processes that run at a higher priority than the loop's process may never complete, as it may fail to get enough cycles to fork the remaining processes after the first (a swift test would be to increment an instance variable in the loop, and see how many you actually get).

Just my £0.02 when tired after a gig - don't take any of this as gospel!

                - Peter

On 10-Jun-06, at 4:53 PM, Peter Crowther wrote:

>> From: Michael van der Gulik
>> Subject: Squeak does not do pre-emptive multitasking.
>
> I've not *found* any bugs in the scheduler, as long as you remember  
> that:
>
> - Higher-priority processes pre-empt lower-priority processes;
>
> - Processes at the same priority do not pre-empt each other;

Exactly. Squeak does do pre-emptive scheduling but does not pre-empt  
within a priority level. When a higher level procees pre-empts, the  
lower process is stuck at the end of the queue of processes waiting  
for time at that priority. Thus you can implement round-robin  
scheduling quite effectively with a Delay in a loop in a high  
priority process. Implementing a scheduler that makes all processes  
get some time depending upon their priority would be a modest  
extension left as an exercise for the student.
>
> - A loop that forks processes that run at a higher priority than  
> the loop's process may never complete, as it may fail to get enough  
> cycles to fork the remaining processes after the first (a swift  
> test would be to increment an instance variable in the loop, and  
> see how many you actually get).
You can certainly get confusing results in some cases.


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful random insult:- He hasn't a single redeeming vice.

tim Rowledge wrote:
Well, I'm not a student anymore, but I might tackle that exercise
because Squeak is pretty lame without it. At the moment I'm just annoyed
that my low priority processes (I assume 10 is low and 80 is high...)
can lock up Squeak. With my 10-process test that I posted, Squeak will
respond to a alt-., but sluggishly if at all. Theoretically it
shouldn't, but it does.

I'm poking around the code now. I guess I'll have to go to the VM code
to work out the finer details. Observations so far:

- Process has a badly named instance variable - "myList".

- The "event tickler" process (EventSensor>>eventTickler) is probably a
good place for some process scheduling seeing that it runs periodically
(currently every 500ms, but that'd need to be 50ms for decent
scheduling). I'd probably start by adding a "timeRunning" variable to
Process which tallies milliseconds spent running and go from there for
fair scheduling.

- Shouldn't the event tickler be running at a higher priority than the
user interupt watcher?

- Processor -> quiescentProcessLists doesn't appear to be used in the
same way as the blue book describes. Infact, it appears to not be used
at all. Where are the process lists? Does the VM not let us see them?

Mikevdg.

If you dig about you will soon find there is only one place in the  
Squeak VM where the process scheduler does the process switch. This  
is at the VM level, not in Smalltalk. Years ago I had a change set  
that altered the VM so that it collected process start time, and  
another instance variable on the process that collected wall clock  
time a process was dispatched.
That way you could collect accurate clock time showing the dispatch  
time for a process because you would update the numbers on each  
process switch.  At this point you could make a more interesting  
decision about which process should be run next however that would  
require a VM change.

As pointed out you could have a high priority task fiddle with the  
processes from time to time. I recall there was a VisualWorks package  
somewhere that altered the VisualWorks default logic. Also consider  
process escalation etc, and let's not forget what happen on Mars.

On 10-Jun-06, at 10:43 PM, Michael van der Gulik wrote:
> Well, I'm not a student anymore, but I might tackle that exercise  
> because Squeak is pretty lame without it. At the moment I'm just  
> annoyed that my low priority processes (I assume 10 is low and 80  
> is high...) can lock up Squeak. With my 10-process test that I  
> posted, Squeak will respond to a alt-., but sluggishly if at all.  
> Theoretically it shouldn't, but it does.

--
========================================================================
===
John M. McIntosh <[hidden email]> 1-800-477-2659
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

> From: Michael van der Gulik
> At the moment I'm just annoyed
> that my low priority processes (I assume 10 is low and 80 is high...)
> can lock up Squeak. With my 10-process test that I posted,
> Squeak will
> respond to a alt-., but sluggishly if at all. Theoretically it
> shouldn't, but it does.

Ah, now I seem to recall that's a different problem.  In order to keep
the speed of bytecode execution high, I recall that not all bytecodes
check for possible context switches *at all*.  There's then a timer in
the VM that triggers much more rarely and forces a check, just in case
of a tight loop that blocks the UI.  Tight loops tend to produce
bytecode sequences that don't trigger checks, as I recall.  Real-life
code wouldn't cause the same problems.

I think a check is made during at least one of the method call and
return sequences.  Bryce would know more if so, as he'll probably have
cursed the fact as he was building Exupery!  I accept that the numbers
would increment more slowly, but a loop of the form "[self increment:
element]" with increment defined as "counts at: element put: ((counts
at: element) + 1)" might yield a more responsive system.

> - Process has a badly named instance variable - "myList".

Given that quiescent Processes are held on LinkedLists, it would seem to
be a reasonable name - what's up with it?

> - Processor -> quiescentProcessLists doesn't appear to be used in the
> same way as the blue book describes. Infact, it appears to
> not be used at all. Where are the process lists?

On my 3.9a image, this shows what I'd expect from last time I
investigated: one LinkedList per *quiescent* process that isn't waiting
elsewhere, such as on a Semaphore.  There's no central registry of
Processes, although a snapshot could always be obtained using Process
allInstances.  Other designs could cause garbage collection of completed
Processes to fail, remembering that this design is far older than any
notion of weak references.

Not saying this is How It Should Be, merely noting why (I think) it's
the way it is.

                - Peter

On Sun, 11 Jun 2006 09:39:30 +0200, Peter Crowther wrote:
>> From: Michael van der Gulik
>> At the moment I'm just annoyed
>> that my low priority processes (I assume 10 is low and 80 is high...)
>> can lock up Squeak. With my 10-process test that I posted,
>> Squeak will
>> respond to a alt-., but sluggishly if at all. Theoretically it
>> shouldn't, but it does.

Michael, how about #(9827655 10007232 9951994 9675033 9841446 9849830  
9671092 9782277 9808366 11128384), resulting from
[ | t |
t := TestingScheduler new.
(t numProcesses: 10) inspect] fork

Some time ago I was thinking about having automagic timesharing in Squeak

- http://people.squeakfoundation.org/article/48.html

With the forked block from above and my timesharing VM hack, the GUI is no  
longer locked up.

> Ah, now I seem to recall that's a different problem.  In order to keep
> the speed of bytecode execution high, I recall that not all bytecodes
> check for possible context switches *at all*.

The change I made to the VM is, after #quickCheckForInterrupts

        "check for possible interrupts at each real send"
        checkCounter _ interruptCheckCounter - 1.
        self quickCheckForInterrupts.
        "kwl 10/15/2005 - time share the CPU"
        (checkCounter = 1)
                ifTrue: [self primitiveYield]

> There's then a timer in
> the VM that triggers much more rarely and forces a check, just in case
> of a tight loop that blocks the UI.  Tight loops tend to produce
> bytecode sequences that don't trigger checks, as I recall.  Real-life
> code wouldn't cause the same problems.
>
> I think a check is made during at least one of the method call and
> return sequences.

Yes, in #executeNewMethod a #quickCheckForInterrupts is done. Another one  
is done in #longUnconditionalJump, but I didn't touch because changing  
#executeNewMethod was already sufficient.

> Bryce would know more if so, as he'll probably have
> cursed the fact as he was building Exupery!  I accept that the numbers
> would increment more slowly, but a loop of the form "[self increment:
> element]" with increment defined as "counts at: element put: ((counts
> at: element) + 1)" might yield a more responsive system.

FWIW the difference between non forked and forked execution was just about  
1%.

/Klaus

"Michael van der Gulik" <[hidden email]> wrote:
> I'm poking around the code now. I guess I'll have to go to the VM code
> to work out the finer details. Observations so far:
>
> - Process has a badly named instance variable - "myList".
For a process that is ready to become the active process, this
variable references a LinkedList. For a process that waits
on a Semaphore, this variable references the semaphore
(note that a Semaphore is a subclass of LinkedList, it
stores a counter of excess signals and a queue of weaiting
processes.) For a process that is neither ready to be continued
not waiting on a Seaphore, this variable is nil.
quiescentProcessesList is an array of 80 LinkedLists - one for each
process priority. This array stores all processes that can be made
the active process. In ProcessorScheduler I find 7 methods that
use this variable.


Greetings,
Boris

Klaus D. Witzel writes:

 > > There's then a timer in
 > > the VM that triggers much more rarely and forces a check, just in case
 > > of a tight loop that blocks the UI.  Tight loops tend to produce
 > > bytecode sequences that don't trigger checks, as I recall.  Real-life
 > > code wouldn't cause the same problems.
 > >
 > > I think a check is made during at least one of the method call and
 > > return sequences.
 >
 > Yes, in #executeNewMethod a #quickCheckForInterrupts is done. Another one  
 > is done in #longUnconditionalJump, but I didn't touch because changing  
 > #executeNewMethod was already sufficient.

quickCheckForInterrupts is the place. It only does a full check
occasionally. At every call it decrements a counter and if the
counter is zero it does a full check. This is because the full
check is slow.

 > > Bryce would know more if so, as he'll probably have
 > > cursed the fact as he was building Exupery!  I accept that the numbers
 > > would increment more slowly, but a loop of the form "[self increment:
 > > element]" with increment defined as "counts at: element put: ((counts
 > > at: element) + 1)" might yield a more responsive system.

I did curse the fact, but mostly because of subtle bugs. The
first really hard bug with Exupery was when a process was
switched due to an interrupt. Exupery didn't realise then and
tried to execute the native code for the old process using the
CompiledMethod of the new process, this lead to a crash.

Bryce

Firstly, thanks to everybody for their input in this. I'm just picking a
random post to reply to so don't feel left out :-).

Peter Crowther wrote:  > I think a check is made during at least one of the method call and
 > return sequences.

Yup. It gets checked on message sends and on longUnconditionalJumps.
I've poked around in the Interpreter and found the methods that check
for it.

>  Bryce would know more if so, as he'll probably have
> cursed the fact as he was building Exupery!  I accept that the numbers
> would increment more slowly, but a loop of the form "[self increment:
> element]" with increment defined as "counts at: element put: ((counts
> at: element) + 1)" might yield a more responsive system.

I tried that, and it is more responsive! Infact, I wouldn't have been
able to tell that CPU was at 100% if it weren't for my CPU ticker :-).

Now, the following tweak will also do the trick:

EventSensor eventPollPeriod: 50
Sensor installEventTickler

This causes the event tickler to run 20 times a second rather than 2,
meaning that at least 20 processes will have a chance to run each
second. The event tickler calls Delay>>wait, which eventually makes the
Interpreter do >>wakeHighestPriority, which find the next ready process.

>>- Process has a badly named instance variable - "myList".
>
>
> Given that quiescent Processes are held on LinkedLists, it would seem to
> be a reasonable name - what's up with it?

It is a non-descriptive variable name. It stood out because it was the
only instance variable in Process that I couldn't work out the purpose
of from its name.

The reason I'm working on this is because I want to modify the VM to be
able to safely execute foreign (and possibly malicious) code with no
risk to locally running processes. This is a hard thing to achieve, but
I need a VM that can handle multitasking, control forkbombs and limit
the number of objects a piece of remote code would make. Currently I'm
just trying to have a development environment that doesn't freeze up on
every bug I introduce :-).

Mikevdg.

> - Process has a badly named instance variable - "myList".

I suppose you mean because of the "my" prefix?

I read an article once about private variables/methods in Smalltalk.
The author suggested, for variables/methods which you want to emphasize
their privateness, you name them mySomething.

He argued besides emphasizing the privateness it even has a punitive
property; any outside callers must endure strange-looking code, as in,
someProcess myList.

I can't say I've practiced it too much, I find the 'private' method
category sufficient documentation..