Hi,
Are Squeak processes pre-emptive? Are infinite loop processes safe to run? Thanks. Ang Beepeng |
>>>>> "Ang" == Ang BeePeng <[hidden email]> 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. So, it's safe to run an infinite loop, but be sure that anything that should interrupt it is at a higher priority. And if you're running *two* infinite loops at the same priority, you need something that will just interrupt regularly. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion |
On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz <[hidden email]> wrote: >>>>> "Ang" == Ang BeePeng <[hidden email]> writes: 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.
FWIW VisualWorks has not moved preempted processes to the back of the run-queue since ObjectWorks 2.3, the last BlueBook compatible release. best Eliot
|
On 13.04.2010, at 18:46, Eliot Miranda wrote:
My guess is this odd behavior was like an accidental round-robin scheduler ... But changing it now might provoke rather obscure problems, no? - Bert - |
Bert Freudenberg wrote:
> On 13.04.2010, at 18:46, Eliot Miranda wrote: >> >> >> On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz >> <[hidden email] <mailto:[hidden email]>> wrote: >> >> >>>>> "Ang" == Ang BeePeng <[hidden email] >> <mailto:[hidden email]>> 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? > > - Bert - > Should always be possible to offer alternative built-in schedulers, no? Lawson |
In reply to this post by Bert Freudenberg
On Tue, Apr 13, 2010 at 9:53 AM, Bert Freudenberg <[hidden email]> wrote:
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
|
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"? On Tue, Apr 13, 2010 at 12:24 PM, Eliot Miranda <[hidden email]> wrote: > > > On Tue, Apr 13, 2010 at 9:53 AM, Bert Freudenberg <[hidden email]> > wrote: >> >> On 13.04.2010, at 18:46, Eliot Miranda wrote: >> >> On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz >> <[hidden email]> wrote: >>> >>> >>>>> "Ang" == Ang BeePeng <[hidden email]> 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 - >> >> >> >> > > > > > |
On 13 April 2010 22:05, Chris Muller <[hidden email]> 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"? > I think it means that scheduler having no guarantee that any given preempted process within a same priority level will be able to gain control within _any_ specified time period, unless there are higher priority process, which interrupts a currently running one. > > > On Tue, Apr 13, 2010 at 12:24 PM, Eliot Miranda <[hidden email]> wrote: >> >> >> On Tue, Apr 13, 2010 at 9:53 AM, Bert Freudenberg <[hidden email]> >> wrote: >>> >>> On 13.04.2010, at 18:46, Eliot Miranda wrote: >>> >>> On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz >>> <[hidden email]> wrote: >>>> >>>> >>>>> "Ang" == Ang BeePeng <[hidden email]> 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 - >>> >>> >>> >>> >> >> >> >> >> > > -- Best regards, Igor Stasenko AKA sig. |
In reply to this post by Chris Muller-3
On Tue, Apr 13, 2010 at 12:05 PM, Chris Muller <[hidden email]> wrote: Hi, I'm not very well-versed in process-scheduling, but I'm having 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.
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.
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 having the VM not put processes to the back of the queue is generally more useful and flexible.
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 2:53 PM, Eliot Miranda <[hidden email]> wrote:
> > > On Tue, Apr 13, 2010 at 12:05 PM, Chris Muller <[hidden email]> 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 <[hidden email]> >> wrote: >> > >> > >> > On Tue, Apr 13, 2010 at 9:53 AM, Bert Freudenberg <[hidden email]> >> > wrote: >> >> >> >> On 13.04.2010, at 18:46, Eliot Miranda wrote: >> >> >> >> On Tue, Apr 13, 2010 at 9:24 AM, Randal L. Schwartz >> >> <[hidden email]> wrote: >> >>> >> >>> >>>>> "Ang" == Ang BeePeng <[hidden email]> 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 - >> >> >> >> >> >> >> >> >> > >> > >> > >> > >> > >> > > |
On Apr 13, 2010, at 2:18 PM, Chris Muller wrote: > On Tue, Apr 13, 2010 at 2:53 PM, Eliot Miranda <[hidden email]> wrote: >> >> >> On Tue, Apr 13, 2010 at 12:05 PM, Chris Muller <[hidden email]> 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 you have some task that is clearly higher-priority than some other task (eg: VoIP vs. polling an email server), then it's better to simply use a higher-priority Process rather than relying on particular scheduling behavior within a single priority-class. Cheers, Josh |
In reply to this post by Randal L. Schwartz
On Wed, Apr 14, 2010 at 4:24 AM, Randal L. Schwartz
<[hidden email]> wrote: >>>>>> "Ang" == Ang BeePeng <[hidden email]> 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. > > So, it's safe to run an infinite loop, but be sure that anything that > should interrupt it is at a higher priority. And if you're running > *two* infinite loops at the same priority, you need something that will > just interrupt regularly. What I do is start up a very high priority process that does something like: d := Delay forMilliseconds: 50. [ d wait ] repeat. or... EventSensor eventPollPeriod: 50. EventSensor install. This forces processes at lower levels to rotate, thus making the whole system a bit fairer and surprisingly more reactive. My opinion is that the scheduler needs improving. I'll work on it... one day. Gulik. -- http://gulik.pbwiki.com/ |
In reply to this post by Chris Muller-4
On Tue, Apr 13, 2010 at 04:18:41PM -0500, Chris Muller wrote:
> > On Tue, Apr 13, 2010 at 2:53 PM, Eliot Miranda <[hidden email]> wrote: > > > > So having the VM not put processes to the back of the queue is generally > > more useful and flexible. > > Great explanation, thanks. Yes, thank you for the clear explanation. Dave |
In reply to this post by Josh Gargus
> If you have some task that is clearly higher-priority than some other task (eg: VoIP vs. polling an email server), then it's better to simply use a higher-priority Process rather than relying on particular scheduling behavior within a single priority-class.
Hm, agreed.. So.. what is a use-case for when you might want the type of cooperative scheduling Eliot mentioned? |
Say for example a server that receives network requests at a certain priority, then spawns worker processes at a lower priority. When the server receives a new request, it should interrupt the current worker process to fork another, but then the previously running worker process should continue, not be put to the back of the queue. That way worker processes can complete in the order that they were forked, not shuffled randomly to the back based on some external factor. I agree with Eliot that VisualWorks does this correctly and in Squeak it's a bug. I guess you could work around it with Semaphores, but that adds a large burden on the developer.
Mike Hales Engineering Manager KnowledgeScape www.kscape.com On Tue, Apr 13, 2010 at 9:21 PM, Chris Muller <[hidden email]> wrote:
|
Guys, i'm going to remind you, that there is a VM/Image refactoring,
which moves a scheduling into the image side: http://bugs.squeak.org/view.php?id=7345 I even put a description of it on my blog http://computeradventures.wordpress.com/ but since nobody seems interested in it, i abandoned this for a better times :) -- Best regards, Igor Stasenko AKA sig. |
In reply to this post by Mike Hales
On Wed, Apr 14, 2010 at 12:09 AM, Mike Hales <[hidden email]> wrote:
> Say for example a server that receives network requests at a certain > priority, then spawns worker processes at a lower priority. When the server > receives a new request, it should interrupt the current worker process to > fork another, but then the previously running worker process should > continue, not be put to the back of the queue. That way worker processes can > complete in the order that they were forked, not shuffled randomly to the > back based on some external factor. Hm, well I suppose if you wanted to preserve order then there would be no need to fork would there? Just post the requests to a shared-queue, and have only one "worker" process which pops them off the top and processes them. That process is interruptible, of course, by the process that appends new incoming requests to the bottom of the queue. I would think that would be much more reliable in a case where order mattered, not to mention, more efficient.. > I agree with Eliot that VisualWorks does > this correctly and in Squeak it's a bug. I agree with Eliot about the merit of the approach where, when one approach permits the other so that, effectively, both are available at the image, but the other approach does not, that there is merit in the approach that provides choice up in the image-level. Given my limited experience, however, I still cannot see a use-case where such fine-grained control is useful, so "bug" is a stronger word than I would know to use at this point.. - Chris Muller |
>>>>> "Chris" == Chris Muller <[hidden email]> writes:
Chris> I agree with Eliot about the merit of the approach where, when one Chris> approach permits the other so that, effectively, both are available at Chris> the image, but the other approach does not, that there is merit in the Chris> approach that provides choice up in the image-level. Given my limited Chris> experience, however, I still cannot see a use-case where such Chris> fine-grained control is useful, so "bug" is a stronger word than I Chris> would know to use at this point.. It would be nice to presume that if I'm running, I'll stay running, interrupted only by either a higher priority process, or me saying "yield". So, even though the current Squeak behavior delivers a cycling of same-priority jobs when higher-priority jobs interrupt regularly, there are clearly other ways to do that, and probably more sensible to *not* do this rotation. After all, the higher priority job could always just force a cooperating job to yield if needed. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion |
On Apr 14, 2010, at 2:56 PM, Randal L. Schwartz wrote: >>>>>> "Chris" == Chris Muller <[hidden email]> writes: > > Chris> I agree with Eliot about the merit of the approach where, when one > Chris> approach permits the other so that, effectively, both are available at > Chris> the image, but the other approach does not, that there is merit in the > Chris> approach that provides choice up in the image-level. Given my limited > Chris> experience, however, I still cannot see a use-case where such > Chris> fine-grained control is useful, so "bug" is a stronger word than I > Chris> would know to use at this point.. > > It would be nice to presume that if I'm running, I'll stay running, > interrupted only by either a higher priority process, or me saying > "yield". Or blocking on a mutex, or waiting for bytes from a socket or a file, or etc. etc. Why would it "be nice" to be able to presume that? A couple of use-cases have been proposed, and upon examination, neither one is facilitated by making the presumption. What's a concrete use-case where this scheduling behavior pays its way? I can't think of any, but that doesn't mean they don't exist. In my opinion, there's too many possible gotchas in this approach to rely on it as a general mechanism for managing concurrency. Cheers, Josh |
On 4/14/2010 3:45 PM, Josh Gargus wrote:
> > On Apr 14, 2010, at 2:56 PM, Randal L. Schwartz wrote: > >>>>>>> "Chris" == Chris Muller<[hidden email]> writes: >> >> Chris> I agree with Eliot about the merit of the approach where, when one >> Chris> approach permits the other so that, effectively, both are available at >> Chris> the image, but the other approach does not, that there is merit in the >> Chris> approach that provides choice up in the image-level. Given my limited >> Chris> experience, however, I still cannot see a use-case where such >> Chris> fine-grained control is useful, so "bug" is a stronger word than I >> Chris> would know to use at this point.. >> >> It would be nice to presume that if I'm running, I'll stay running, >> interrupted only by either a higher priority process, or me saying >> "yield". > > Or blocking on a mutex, or waiting for bytes from a socket or a file, or etc. etc. > > Why would it "be nice" to be able to presume that? For the same reasons that Tweak goes to great length to effectively implement the same model :-) Cheers, - Andreas |
Free forum by Nabble | Edit this page |