[9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Uriel]

On Sat, 14 Apr 2007 06:17:24, 9changes@cat-v.org <9changes@cat-v.org> wrote:
>         + # turn on cooperative scheduling (assuming it starts off)
>         + echo coop > /dev/reboot
>  [geoff] --rwxrwxr-x M 121 geoff sys 448 Apr 13 18:06 rc/bin/cpurc.local

What does this do? It is undocumented, and as far as I can tell it
toggles the coopsched var, which is used once in the scheduler code.

Would be nice to know what it does exactly, and why on earth it uses
/dev/reboot. Note that there is no way to check the state of the
variable, so one has no clue if one is enabling or disabling
'coopsched', whatever it does this interface is clearly far from
ideal.

While investigating this I noticed a couple of other undocumented
commands for /dev/reboot that seem more relevant and self-evident but
would still be nice to have documented.

Best wishes

uriel

[9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Uriel]

On 4/15/07, Uriel <uriel99@gmail.com> wrote:
> Note that there is no way to check the state of the
> variable, so one has no clue if one is enabling or disabling
> 'coopsched', whatever it does this interface is clearly far from
> ideal.

Seems that I was overzealous (as usual) in this point, I read the code
but then forgot, dho correctly reminded me that there is a kprint
reporting the new state of coopsched when toggled, but this is still
an ugly, non standard and inconvenient interface.

uriel

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Devon H. O'Dell]

2007/4/15, Uriel <uriel99@gmail.com>:
> On Sat, 14 Apr 2007 06:17:24, 9changes@cat-v.org <9changes@cat-v.org> wrote:
> >         + # turn on cooperative scheduling (assuming it starts off)
> >         + echo coop > /dev/reboot
> >  [geoff] --rwxrwxr-x M 121 geoff sys 448 Apr 13 18:06 rc/bin/cpurc.local
>
> What does this do? It is undocumented, and as far as I can tell it
> toggles the coopsched var, which is used once in the scheduler code.

Additionally, we can't assume it starts off. The value is never
initialized in the C code, so it could be 0, 1, or 382355318. I'm
assuming that kencc zeroes uninitialized variables in the text, but
I'm not sure.

> Would be nice to know what it does exactly, and why on earth it uses
> /dev/reboot. Note that there is no way to check the state of the
> variable, so one has no clue if one is enabling or disabling
> 'coopsched', whatever it does this interface is clearly far from
> ideal.
>
> While investigating this I noticed a couple of other undocumented
> commands for /dev/reboot that seem more relevant and self-evident but
> would still be nice to have documented.

At least this one, as the comment states, turns on cooperative
scheduling. Cooperative scheduling differs from preemptive scheduling
in that it requires the process to schedule itself, instead of rely on
the kernel to preempt it when something of higher priority needs to
run. Only, it seems that the kernel controls this, too.

In runproc() (port/proc.c), we have the test

if(coopsched && (p=m->readied) && p->mach == 0 && p->state==Ready &&
runq[Nrq-1].head==nil && runq[Nrq-2].head == nil)

m->readied is a ready process in the Mach structure. This is set in
ready(), which is called in various places, including when notes and
whatnot are sent to a process so that they can act on them
immediately.

p->mach is a pointer back to a machine structure. I'm assuming this
only gets set when a process is being run. I suppose this test is here
in case another CPU took over running the process.

Additionally, the check requires that the highest two priority run
queues are empty. If all these conditions are satisfied, we'll
schedule the process cooperatively. It seems like this would allow
low-priority processes that have notes to be delivered, or are stuck,
or similar, to run when other workloads have finished and the
scheduler hasn't yet ticked. This would obviously give potentially
better CPU / workload utilization. Which is I guess, what this means.
Seems like Russ wrote it, so it'd be interesting to hear how far off I
am.

> Best wishes
>
> uriel

--dho

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[erik quanstrom]

> Additionally, we can't assume it starts off. The value is never
> initialized in the C code, so it could be 0, 1, or 382355318. I'm
> assuming that kencc zeroes uninitialized variables in the text, but
> I'm not sure.

non automatic variables are always initialized to zero unless
explicitly initialized to something else regardless of your version of
c.

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Devon H. O'Dell]

2007/4/15, erik quanstrom <quanstro@coraid.com>:
> > Additionally, we can't assume it starts off. The value is never
> > initialized in the C code, so it could be 0, 1, or 382355318. I'm
> > assuming that kencc zeroes uninitialized variables in the text, but
> > I'm not sure.
>
> non automatic variables are always initialized to zero unless
> explicitly initialized to something else regardless of your version of
> c.

Ok, thanks for the clarification.

--dho

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Russ Cox]

> Additionally, we can't assume it starts off. The value is never
> initialized in the C code, so it could be 0, 1, or 382355318. I'm
> assuming that kencc zeroes uninitialized variables in the text, but
> I'm not sure.

This is just not true.  Global variables in C are guaranteed
to be zeroed at program start time.

> Would be nice to know what it does exactly, and why on earth it uses
> /dev/reboot. Note that there is no way to check the state of the
> variable, so one has no clue if one is enabling or disabling
> 'coopsched', whatever it does this interface is clearly far from
> ideal.

True enough.  The toggle was only so it could be turned off
easily if it was a bad idea, and so that the difference could
be measured.  But it turned out to be a good idea and I never
got around to removing the cruft.  The cruft is now gone
from sources.

The code it controlled in the scheduler did the following.
If process A readies process B to run (say, by writing to a pipe
that process B is reading) and gives up the cpu before
its time slice is up, then process B inherits the rest of
process A's time slice.

This makes concurrent programs (like pipelines, but also 
threaded programs that do a lot of context switching)
get something closer to their fair share of the cpu when
there is scheduling contention.  Inspired by L4.

Russ

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Uriel]

Neat, thanks for the explanation!

uriel

On 4/15/07, Russ Cox <rsc@swtch.com> wrote:
> > Additionally, we can't assume it starts off. The value is never
> > initialized in the C code, so it could be 0, 1, or 382355318. I'm
> > assuming that kencc zeroes uninitialized variables in the text, but
> > I'm not sure.
>
> This is just not true.  Global variables in C are guaranteed
> to be zeroed at program start time.
>
> > Would be nice to know what it does exactly, and why on earth it uses
> > /dev/reboot. Note that there is no way to check the state of the
> > variable, so one has no clue if one is enabling or disabling
> > 'coopsched', whatever it does this interface is clearly far from
> > ideal.
>
> True enough.  The toggle was only so it could be turned off
> easily if it was a bad idea, and so that the difference could
> be measured.  But it turned out to be a good idea and I never
> got around to removing the cruft.  The cruft is now gone
> from sources.
>
> The code it controlled in the scheduler did the following.
> If process A readies process B to run (say, by writing to a pipe
> that process B is reading) and gives up the cpu before
> its time slice is up, then process B inherits the rest of
> process A's time slice.
>
> This makes concurrent programs (like pipelines, but also
> threaded programs that do a lot of context switching)
> get something closer to their fair share of the cpu when
> there is scheduling contention.  Inspired by L4.
>
> Russ
>
>

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Devon H. O'Dell]

2007/4/15, Russ Cox <rsc@swtch.com>:
> > Additionally, we can't assume it starts off. The value is never
> > initialized in the C code, so it could be 0, 1, or 382355318. I'm
> > assuming that kencc zeroes uninitialized variables in the text, but
> > I'm not sure.
>
> This is just not true.  Global variables in C are guaranteed
> to be zeroed at program start time.

I'm stupid.

> > Would be nice to know what it does exactly, and why on earth it uses
> > /dev/reboot. Note that there is no way to check the state of the
> > variable, so one has no clue if one is enabling or disabling
> > 'coopsched', whatever it does this interface is clearly far from
> > ideal.
>
> True enough.  The toggle was only so it could be turned off
> easily if it was a bad idea, and so that the difference could
> be measured.  But it turned out to be a good idea and I never
> got around to removing the cruft.  The cruft is now gone
> from sources.

This means it should probably be removed from cpurc.local, too, right?
I see it's still there on sources (see uriel's original post with
geoff's change).

--dho

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Devon H. O'Dell]

2007/4/15, Devon H. O'Dell <devon.odell@gmail.com>:
> p->mach is a pointer back to a machine structure. I'm assuming this
> only gets set when a process is being run. I suppose this test is here
> in case another CPU took over running the process.

Though, this can't be the case, because m->readied isn't locked when
we come in here, and if we're running MP, wouldn't it be possible
(though unlikely) that another CPU takes the process between the
assignment and the test? Especially if running heavily threaded
applications on MP systems?

> --dho

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Russ Cox]

>> p->mach is a pointer back to a machine structure. I'm assuming this
>> only gets set when a process is being run. I suppose this test is here
>> in case another CPU took over running the process.
> 
> Though, this can't be the case, because m->readied isn't locked when
> we come in here, and if we're running MP, wouldn't it be possible
> (though unlikely) that another CPU takes the process between the
> assignment and the test? Especially if running heavily threaded
> applications on MP systems?

	/* cooperative scheduling until the clock ticks */
	if((p=m->readied) && p->mach==0 && p->state==Ready
	&& runq[Nrq-1].head == nil && runq[Nrq-2].head == nil){

The tests are:

	p=m->readied
		some process p was last readied on this cpu (Mach)
	
	p->mach == 0
		p is not running on any cpu right now
	
	p->state == Ready
		p is still Ready (waiting to run)
	
	runq[Nrq-1].head == nil && runq[Nrq-2].head == nil
		there are no real-time processes waiting to run

If all those succeed, then the code tries to choose
p to run next.  But it might not -- the next thing that 
happens is

	p = dequeueproc(rq, p);

which can return nil if p has already been grabbed
or even if there is contention for the runq lock.
All the accesses in the if condition are just fine --
they happen without a lock but dequeueproc double-checks
that p is okay to schedule.

If dequeueproc returns nil, then runproc won't pick 
the readied p after all -- it will fall into the regular
scheduling loop to find a process.

Russ

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Devon H. O'Dell]

2007/4/15, Russ Cox <rsc@swtch.com>:
>         /* cooperative scheduling until the clock ticks */
>         if((p=m->readied) && p->mach==0 && p->state==Ready
>         && runq[Nrq-1].head == nil && runq[Nrq-2].head == nil){
>
> The tests are:
>
>         p=m->readied
>                 some process p was last readied on this cpu (Mach)
>
>         p->mach == 0
>                 p is not running on any cpu right now

Not to be overly annoying, but _is_ it possible that between the
assignment and that test, p->mach is set, indicating another CPU took
over? It just doesn't seem like m->readied is locked, at all; it seems
like another CPU could pick it up in the middle.

>         p->state == Ready
>                 p is still Ready (waiting to run)
>
>         runq[Nrq-1].head == nil && runq[Nrq-2].head == nil
>                 there are no real-time processes waiting to run
>
> If all those succeed, then the code tries to choose
> p to run next.  But it might not -- the next thing that
> happens is
>
>         p = dequeueproc(rq, p);
>
> which can return nil if p has already been grabbed
> or even if there is contention for the runq lock.
> All the accesses in the if condition are just fine --
> they happen without a lock but dequeueproc double-checks
> that p is okay to schedule.
>
> If dequeueproc returns nil, then runproc won't pick
> the readied p after all -- it will fall into the regular
> scheduling loop to find a process.
>
> Russ

Thanks for the low-level explanation. It does really help my understanding.

--dho

Re: [9fans] Re: [sources] 20070413: /rc/bin/cpurc.local

[Russ Cox]

> Not to be overly annoying, but _is_ it possible that between the
> assignment and that test, p->mach is set, indicating another CPU took
> over? It just doesn't seem like m->readied is locked, at all; it seems
> like another CPU could pick it up in the middle.

Many things are possible.  m->readied is just a hint.
p->mach is just a hint unless you hold the scheduling lock.

That's why dequeueproc double-checks:
    All the accesses in the if condition are just fine --
    they happen without a lock but dequeueproc double-checks
    that p is okay to schedule.

Russ