Preemptive scheduling

> Hi all,
>
> Does the Squeak VM do preemptive scheduling or regular yield style  
> scheduling.  This may sound like a silly question, but I know  
> Erlang is language that does mainly green threads and they are  
> preemptive in nature.  They accomplish this by allowing a given  
> thread to execute no more then 100 VM instructions before it is  
> preempted (obviously if a thread makes a primitive call that is a  
> voluntary yield).
>
> Does Squeak do this already?  I suspect not, and if I am correct,  
> would there be any benefit in doing something like this or would it  
> actually slow things down?
>
> Thanks,
> Jason
>
> _________________________________________________________________
> Don’t quit your job – Take Classes Online and Earn your Degree in 1  
> year. Start Today! http://www.classesusa.com/clickcount.cfm?
> id=866146&goto=http%3A%2F%2Fwww.classesusa.com%2Ffeaturedschools%
> 2Fonlinedegreesmp%2Fform-dyn1.html%3Fsplovr%3D866144
>
>

>From: John M McIntosh <[hidden email]>
>Reply-To: [hidden email],The general-purpose Squeak
>developers list<[hidden email]>
>To: The general-purpose Squeak developers
>list<[hidden email]>
>Subject: Re: Preemptive scheduling
>Date: Tue, 1 May 2007 11:21:38 -0700
>
>Interpreter>>transferTo: is the place in the VM were we transfer  control
>from one process to another. This is invoked via
>
>primitiveSuspend
>primitiveWait
>primitiveYield
>resume:
>
>for wait and yield it follows the pattern
>
> self addLastLink: activeProc toList: processList.
> self transferTo: self wakeHighestPriority
>
>which means we stick the process at the end of the linked list of  
>processes in the same priority, thus if there was a higher process or
>process at the same priority ready to run it will run instead of the  
>process that has the wait or yield.  It could of course wake the same
>process if the process is the only one in it's priority group and  it's
>ready to run of course.
>
>for suspend, we don't do the addLastLink because the process is being  
>suspended.
>
>In all of this the ProcessorScheduler does not do preemptive  scheduling,
>thus if you have a high priority smalltalk process that  runs away it will
>block all other
>processes from running.  You could of course and I've seen change  sets for
>Visualworks write your own scheduler that modifies what  
>wakeHighestPriority means by suspending processes that normally would  be
>runnable.  That would be overhead, and what is the problem you are  trying
>to solve?
>
>
>On May 1, 2007, at 10:48 AM, J J wrote:
>
>>Hi all,
>>
>>Does the Squeak VM do preemptive scheduling or regular yield style  
>>scheduling.  This may sound like a silly question, but I know  Erlang is
>>language that does mainly green threads and they are  preemptive in
>>nature.  They accomplish this by allowing a given  thread to execute no
>>more then 100 VM instructions before it is  preempted (obviously if a
>>thread makes a primitive call that is a  voluntary yield).
>>
>>Does Squeak do this already?  I suspect not, and if I am correct,  would
>>there be any benefit in doing something like this or would it  actually
>>slow things down?
>>
>>Thanks,
>>Jason
>>
>>_________________________________________________________________
>>Don’t quit your job – Take Classes Online and Earn your Degree in 1  year.
>>Start Today! http://www.classesusa.com/clickcount.cfm?
>>id=866146&goto=http%3A%2F%2Fwww.classesusa.com%2Ffeaturedschools%
>>2Fonlinedegreesmp%2Fform-dyn1.html%3Fsplovr%3D866144
>>
>>
>
>--
>========================================================================
>===
>John M. McIntosh <[hidden email]>
>Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
>========================================================================
>===
>
>
>

>From: "Philippe Marschall" <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: "The general-purpose Squeak developers
>list"<[hidden email]>
>Subject: Re: Preemptive scheduling
>Date: Tue, 1 May 2007 20:25:23 +0200
>
>http://groups.google.com/group/strongtalk-general/msg/5e36e34c2f91eb23
>
>2007/5/1, J J <[hidden email]>:
>>Hi all,
>>
>>Does the Squeak VM do preemptive scheduling or regular yield style
>>scheduling.  This may sound like a silly question, but I know Erlang is
>>language that does mainly green threads and they are preemptive in nature.
>>They accomplish this by allowing a given thread to execute no more then
>>100
>>VM instructions before it is preempted (obviously if a thread makes a
>>primitive call that is a voluntary yield).
>>
>>Does Squeak do this already?  I suspect not, and if I am correct, would
>>there be any benefit in doing something like this or would it actually
>>slow
>>things down?
>>
>>Thanks,
>>Jason
>>
>>_________________________________________________________________
>>Don't quit your job – Take Classes Online and Earn your Degree in 1
>>year.
>>Start Today!
>>http://www.classesusa.com/clickcount.cfm?id=866146&goto=http%3A%2F%2Fwww.classesusa.com%2Ffeaturedschools%2Fonlinedegreesmp%2Fform-dyn1.html%3Fsplovr%3D866144
>>
>>
>>

> Aha, Interpreter!  I was looking in process for the "swap" method. :)
>
> At the moment, I am not looking to solve a problem per se.  I was  
> just thinking that Smalltalk tries to be it's own OS, kind of.  I  
> wonder what would happen if it went a bit further.
>
> On a real OS, a processes are only allowed to run for a certain  
> amount of time before the CPU interupts them and puts the OS back  
> in control to decide what to do next.  In any kind of "green  
> threads" system this (normally) isn't doable because it is actually  
> just one running process and if a "green thread" doesn't want to  
> yield, then the threading system never gets back in control to stop  
> it.  The threading system could, of course, have the OS send it  
> some kind of signal ever so many milliseconds but how that is done  
> is very platform specific (not to mention a host of other problems  
> with it).
>
> But with an interpreter it would be possible to do the same things  
> an advanced OS does, let a process only run for a specific amount  
> of VM instructions, penilize processes that keep using their whole  
> "quantum", promote processes that don't, etc.
>
> The question is, would this have any benifit? If I ever have time,  
> maybe I will find out (unless of course Squeak already does most of  
> this). :)

>> But with an interpreter it would be possible to do the same things  
>> an advanced OS does, let a process only run for a specific amount  
>> of VM instructions, penilize processes that keep using their whole  
>> "quantum", promote processes that don't, etc.
>
>
> If you want to do some sort of count of bytecodes or prim calls  
> instead of a simple timer, that is not difficult to arrange. I  
> think John put some timer/counter stuff in a few years ago that  
> would support this.

>From: tim Rowledge <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: The general-purpose Squeak developers
>list<[hidden email]>
>Subject: Re: Preemptive scheduling
>Date: Tue, 1 May 2007 13:24:30 -0700
>
>>On a real OS
>
>...interesting definition of 'real' here. I can assure you there are  OSs
>I've used that didn't do any such thing...

>> Does the Squeak VM do preemptive scheduling or regular yield style
>> scheduling.  This may sound like a silly question, but I know  
>> Erlang is
>> language that does mainly green threads and they are preemptive in
>> nature.  They accomplish this by allowing a given thread to  
>> execute no
>> more then 100 VM instructions before it is preempted (obviously if a
>> thread makes a primitive call that is a voluntary yield).
>>
>> Does Squeak do this already?
>
> Yes, the Squeak scheduler implements preemptive scheduling. An active
> process is given a quantum of such-and-such many byte codes, and when
> the quantum expires, a scheduling decision is made. The scheduler
> attempts to make each quantum a (tunable) period of time (by default
> 1ms), and adjusts the number of byte code operations to account for
> differences in CPU speed.
>
> Regards,
> Martin
>

>
>> You can easily do this in Smalltalk in a portable way; just a  
>> high  priority process that cycles on a time interrupt to shuffle  
>> the  process scheduler. You can manually shuffle the processes at  
>> the  various priorities if you want to.
>
> I'm good with a time interrupt, but how is that done in a remotely  
> portable/safe way?  I'm not asking about process shuffling, I'm  
> asking how a process that consists of:
>
> [ [ true ] whileTrue: [ true ] ] fork
>
> can ever be taken off the processor.  Unless you do either (a)  
> instruction count based preemption or (b) time based (i.e. what  
> CPU's use), it can't be done afaik.

>From: "Martin v. Löwis" <[hidden email]>
>Reply-To: The general-purpose Squeak developers
>list<[hidden email]>
>To: The general-purpose Squeak developers
>list<[hidden email]>
>Subject: Re: Preemptive scheduling
>Date: Tue, 01 May 2007 22:56:38 +0200
>
> > Does the Squeak VM do preemptive scheduling or regular yield style
> > scheduling.  This may sound like a silly question, but I know Erlang is
> > language that does mainly green threads and they are preemptive in
> > nature.  They accomplish this by allowing a given thread to execute no
> > more then 100 VM instructions before it is preempted (obviously if a
> > thread makes a primitive call that is a voluntary yield).
> >
> > Does Squeak do this already?
>
>Yes, the Squeak scheduler implements preemptive scheduling. An active
>process is given a quantum of such-and-such many byte codes, and when
>the quantum expires, a scheduling decision is made. The scheduler
>attempts to make each quantum a (tunable) period of time (by default
>1ms), and adjusts the number of byte code operations to account for
>differences in CPU speed.
>
>Regards,
>Martin
>

>From: John M McIntosh <[hidden email]>
>Reply-To: [hidden email],The general-purpose Squeak
>developers list<[hidden email]>
>To: The general-purpose Squeak developers
>list<[hidden email]>
>Subject: Re: Preemptive scheduling
>Date: Tue, 1 May 2007 14:54:12 -0700
>
>Ah, well as one of the authors of that piece of code let me comment,  
>assuming Martin and I are talking about the same piece of code.
>
>There is a checkForInterrupts method that is called by the  interpreter
>every so often and under certain conditions.
>
>It
>
>- deals with the lowspace pending signal
>- ensures VM event polling occurs in a timely manner.
>- deals with the interrupt pending signal
>- deals with clock rollover
>- deals with the finalization logic
>- takes any external semaphore index number signal requests off a  dual
>queue set and signals the actual semaphore
>- executes the next pending process on a semaphore if the semaphore  should
>be woken and it's priority is > than the current process.
>
>So if any process that is waiting on a timer, or a semphore is  signaled,
>and if the process involved is a *higher* priority than the  current one we
>would transfer control.
>
>Now this routine was originally called when we executed a new method,  and
>when we  did a long unconditional jump bytecode backwards. Those  so called
>  "safe points"
>
>Many years ago when we moved from 25Mhz 68030 motorola macintoshs to  
>powerpc machines I discovered that this routine could be called upwards
>5,000 a second and contribute to much of the cpu usage of Squeak  since it
>was being called on the basis of a number (1000?) being  decremented.
>I altered this logic to ensure it would be called every N  milliseconds by
>fiddling with the interruptCheckCounter by  incrementing, decrementing the
>value
>to reach a steady state to limit the calling frequency to a target  value.
>
>Later we added the ability to force an interrupt check, say after an  
>incremental GC, or after a signal semphore, plus some other  interesting
>places to ensure the check for interrupt would very  quickly process a
>pending interrupt.
>
>This does not mean the routine is called exactly every N  milliseconds,
>rather it's *usually* called every N milliseconds.  How  many bytecodes
>that is, is well anyone's guess since reliant on  method sends, and
>backward long unconditional jumps.
>
>Exceptions are I believe the Windows VM forces an interrupt check  every
>millisecond due to an external timer to ensure it's called more  closely to
>the 1 millisecond goal.
>
>On May 1, 2007, at 1:56 PM, Martin v. Löwis wrote:
>
>>>Does the Squeak VM do preemptive scheduling or regular yield style
>>>scheduling.  This may sound like a silly question, but I know  Erlang is
>>>language that does mainly green threads and they are preemptive in
>>>nature.  They accomplish this by allowing a given thread to  execute no
>>>more then 100 VM instructions before it is preempted (obviously if a
>>>thread makes a primitive call that is a voluntary yield).
>>>
>>>Does Squeak do this already?
>>
>>Yes, the Squeak scheduler implements preemptive scheduling. An active
>>process is given a quantum of such-and-such many byte codes, and when
>>the quantum expires, a scheduling decision is made. The scheduler
>>attempts to make each quantum a (tunable) period of time (by default
>>1ms), and adjusts the number of byte code operations to account for
>>differences in CPU speed.
>>
>>Regards,
>>Martin
>>
>
>--
>========================================================================
>===
>John M. McIntosh <[hidden email]>
>Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
>========================================================================
>===
>
>
>