On Tue, Apr 13, 2010 at 2:53 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, Apr 13, 2010 at 12:05 PM, Chris Muller asqueaker@gmail.com wrote:
Hi, I'm not very well-versed in process-scheduling, but I'm having trouble understanding why you don't like sending the last pre-empted process to the back of its queue of processes waiting at that level. Doesn't that seem more "fair" and also, allow "smoother" multi-tasking since those other processes at that level would get a turn?
Your reason was: "It means one cannot rely on cooperative scheduling within a priority level." but I don't understand what you mean by "rely on"?
A cooperative scheduler is one in which it is guaranteed that another process does not run until the active process chooses to yield. This makes it easy to implement particular forms of synchronisation because processes are not preemptive. The Smalltalk scheduler is a form of real-time scheduler in which processes have fixed priorities and are only preempted by higher-priroity processes. This also makes it easy to implement various kinds of multi-process behaviour because one is guaranteed that a lower-priority process is never running while a higher priority process is able to run.
Ok, I am guessing this is useful for time-critical applications; like a voip chat program. So it can choose to not be interrupted while actively digitizing voice, perhaps..
If one arranges that the scheduler does not put processes to the back of the run queue on preemption then within a priority level scheduling is cooperative and those simple synchronisation algorithms can still function when used by processes within the same priority.
Ah, I see!
One can still implement moving to the back of the queue on preemption with Smalltalk code if the VM does not, but one cannot prevent being put to the back if the VM does.
So it provides another tool for finer-grained scheduling within a level; based on whether the particular object cares about immediate resumption or not. The voip chatter would.
So having the VM not put processes to the back of the queue is generally more useful and flexible.
Great explanation, thanks.
- Chris
Your point about fairness is an important one, but being put to the back of the run queue on preemption does not in any way guarantee fairness. Consider examples where some lower-priority process needs to kick a higher-priority process briefly, but the lower-priority process is contending with other lower-priroity processes. The lower-priroity kicker can't avoid giving up the processor to the other contending processes and so the result could be unfairness. Fairness is going to have to be defined in some context and a policy implemented to maintain that regime. merely having the VM scheduler force an implicit yield on preemption is not enough to implement fairness. cheers Eliot
On Tue, Apr 13, 2010 at 12:24 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, Apr 13, 2010 at 9:53 AM, Bert Freudenberg bert@freudenbergs.de wrote:
On 13.04.2010, at 18:46, Eliot Miranda wrote:
On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz merlyn@stonehenge.com wrote:
>>>> "Ang" == Ang BeePeng beepeng86@yahoo.com writes:
Ang> Are Squeak processes pre-emptive? Are infinite loop processes safe Ang> to run?
Squeak uses a simple priority scheme.
A Squeak process runs until it yields or it is interrupted by a higher priority process event. When it is interrupted, it goes to the back of the queue, so when the higher priority process pauses or completes, other processes at the same priority are likely to be run instead.
IMO the sending of the preempted process to the back of the queue is a bug. It means one cannot rely on cooperative scheduling within a priority level. On the other hand, if the VM does not send the preempted process to the back of the queue there is nothing to prevent a higher-priority process altering the run queues of lower priority processes, achieving the same thing. But it is flexible if the scheduler code does it rather than the VM. One can imagine per-process priorities being examined so that by default a process gets moved to the back of its run queue when preempted, but if a process has a "don't preempt me" property it is not.
My guess is this odd behavior was like an accidental round-robin scheduler ... But changing it now might provoke rather obscure problems, no?
That's certainly possible, but not the VisualWorks experience. One can simply add a yield to allow other processes at the same priority level to run. If there aren't any high-priroity processes running sporadically then one needs yields anyway. So it is highly likely that in cases where the programmer wants to yield they have explicitly used a yield. I think it much more likely that the current behaviour creates obscure problems because sometimes implicit yields occur and at other times they don't, depending on the state of finalization, whether delays are in progress or not, etc. But I agree it seems like a big change. I just think it's a change for the better :) best Eliot
- Bert -