[9fans] [GSOC] plan9 kernel scheduler

[9fans] [GSOC] plan9 kernel scheduler

[yan cui]

[-- Attachment #1: Type: text/plain, Size: 359 bytes --]

Hi all,

    On SMP or multicore systems, what algorithm(s) does Plan 9 use to
schedule(context switching and load balancing) different tasks (process or
thread) and where is it implemented? I searched some plan9 documents, but
cannot find some about this topic. Any recommendations?


Thanks, Yan

--
Think big; Dream impossible; Make it happen.

[-- Attachment #2: Type: text/html, Size: 489 bytes --]

Re: [9fans] [GSOC] plan9 kernel scheduler

[Yoann Padioleau]

if you look in sys/src/9/port
and grep for functions like

sched()
schedinit()
runproc()
updatecpu()
repriotirize()

you'll get the logic of the scheduling algorithm. It's mostly
priority queue fair robin I think, with a few hooks to prefer reschedule
on the same CPU.

Context switching is done with the
gotolabel()
setlabel()
mmuswtich()
taskswitch()


On Jun 21, 2014, at 12:30 PM, yan cui <ccuiyyan@gmail.com> wrote:

> Hi all,
> 
>     On SMP or multicore systems, what algorithm(s) does Plan 9 use to schedule(context switching and load balancing) different tasks (process or thread) and where is it implemented? I searched some plan9 documents, but cannot find some about this topic. Any recommendations?    
> 
> 
> Thanks, Yan
> 
> -- 
> Think big; Dream impossible; Make it happen.  

Re: [9fans] [GSOC] plan9 kernel scheduler

[Jessica Yu]

+1 what Yoann said. :-) On SMP systems, all maches share a global run
queue, and maches tend to try grabbing procs that have run on it
before (affinity). Take a look at port/proc.c in particular, where a
lot of the scheduling logic is implemented.

On Sat, Jun 21, 2014 at 6:10 PM, Yoann Padioleau <pad@fb.com> wrote:
> if you look in sys/src/9/port
> and grep for functions like
>
> sched()
> schedinit()
> runproc()
> updatecpu()
> repriotirize()
>
> you'll get the logic of the scheduling algorithm. It's mostly
> priority queue fair robin I think, with a few hooks to prefer reschedule
> on the same CPU.
>
> Context switching is done with the
> gotolabel()
> setlabel()
> mmuswtich()
> taskswitch()
>
>
> On Jun 21, 2014, at 12:30 PM, yan cui <ccuiyyan@gmail.com> wrote:
>
>> Hi all,
>>
>>     On SMP or multicore systems, what algorithm(s) does Plan 9 use to schedule(context switching and load balancing) different tasks (process or thread) and where is it implemented? I searched some plan9 documents, but cannot find some about this topic. Any recommendations?
>>
>>
>> Thanks, Yan
>>
>> --
>> Think big; Dream impossible; Make it happen.
>
>

Re: [9fans] [GSOC] plan9 kernel scheduler

[erik quanstrom]

On Sat Jun 21 21:47:37 EDT 2014, jyu@cowsay.org wrote:
> +1 what Yoann said. :-) On SMP systems, all maches share a global run
> queue, and maches tend to try grabbing procs that have run on it
> before (affinity). Take a look at port/proc.c in particular, where a
> lot of the scheduling logic is implemented.

the (base) plan 9 scheduler uses a global priority based round robin
scheduler.  priority is absolute; a process of priority n+1
will always run before a process of priority n.  processes within
a priority are run in round-robin fashion.  recent cpu usage lowers
a processes' priority.  there is soft affinity that tends to rerun a
process on the same cpu when practical, though this mechanism is
too hard inthe standard distribution. there is hard affinity; one can
wire a proc to a mach.

a key detail of the scheduler is the set of priorities with runnable
processes is kept in a bitvector named "runvec".  significantly less
than 32 priorities are used.

there is also an edf scheduler.  i can't find the iwp9 paper atm.
(other than /n/atom/plan9/sys/doc/real-time.ms) but i think that's
beyond the scope of the question.

the scheduler is inefficient for many cpus, and there are some bugs
that cause expectations to diverge strongly from reality.  so to make
life easier for a gsoc student who is working on proper changes to
the scheduler, i spent two days on some cheep improvements that
make the scheduler predectible and reasonable, if not terribly efficient.
they depend on having a scalable lock.

1.  given a scalable lock, then putting a monitor around the run queues
scan will result in 1 cacheline contention event, rather than many.
this also has the effect of building a queue of processors waiting in line
for their chance at the run queues

2.  replacing idlehands with monmwait of the runvec.

3.  reducing the soft affinity to n microseconds, rather than letting
all local-affinity processes come before non local processes, regardless
of time spent on run queues.  (i'm currently working with n=500µs)

these improvements have the net effect on my 8 thread machine
of lowering the nix kernel compile time about 40%.  i'm not sure what
to expect on larger machines.

i did not expect such large improvements.  so unfortunately this has
raised the bar quite a bit for the gsoc project.  nonetheless, i'm happy
to report that the new scheduler is already within 7% of the old!

- erik

Re: [9fans] [GSOC] plan9 kernel scheduler

[Ramakrishnan Muthukrishnan]

On Sun, Jun 22, 2014 at 5:40 PM, erik quanstrom <quanstro@quanstro.net> wrote:
> On Sat Jun 21 21:47:37 EDT 2014, jyu@cowsay.org wrote:
>> +1 what Yoann said. :-) On SMP systems, all maches share a global run
>> queue, and maches tend to try grabbing procs that have run on it
>> before (affinity). Take a look at port/proc.c in particular, where a
>> lot of the scheduling logic is implemented.
>
> the (base) plan 9 scheduler uses a global priority based round robin
> scheduler.  priority is absolute; a process of priority n+1
> will always run before a process of priority n.  processes within
> a priority are run in round-robin fashion.  recent cpu usage lowers
> a processes' priority.  there is soft affinity that tends to rerun a
> process on the same cpu when practical, though this mechanism is
> too hard inthe standard distribution. there is hard affinity; one can
> wire a proc to a mach.
>
> a key detail of the scheduler is the set of priorities with runnable
> processes is kept in a bitvector named "runvec".  significantly less
> than 32 priorities are used.
>
> there is also an edf scheduler.  i can't find the iwp9 paper atm.

Is it this one?

"Lightweight EDF Scheduling with Deadline
Inheritance" by Jansen, S.J.Mullender et al.
<http://doc.utwente.nl/41399/1/000000c6.pdf>

Re: [9fans] [GSOC] plan9 kernel scheduler

[erik quanstrom]

> "Lightweight EDF Scheduling with Deadline
> Inheritance" by Jansen, S.J.Mullender et al.
> <http://doc.utwente.nl/41399/1/000000c6.pdf>

no.  that's not it.

.TL
Real Time in Plan 9
.AU
Sape Mullender
Jim McKie
.AI

- erik

Re: [9fans] [GSOC] plan9 kernel scheduler

[andrey mirtchovski]

plan9.bell-labs.com/iwp9/Real-time.pdf


On Mon, Jun 23, 2014 at 10:30 AM, erik quanstrom <quanstro@quanstro.net> wrote:
>> "Lightweight EDF Scheduling with Deadline
>> Inheritance" by Jansen, S.J.Mullender et al.
>> <http://doc.utwente.nl/41399/1/000000c6.pdf>
>
> no.  that's not it.
>
> .TL
> Real Time in Plan 9
> .AU
> Sape Mullender
> Jim McKie
> .AI
>
> - erik
>

Re: [9fans] [GSOC] plan9 kernel scheduler

[Ramakrishnan Muthukrishnan]

On Tue, Jun 24, 2014 at 12:07 AM, andrey mirtchovski
<mirtchovski@gmail.com> wrote:
> plan9.bell-labs.com/iwp9/Real-time.pdf
>
>
> On Mon, Jun 23, 2014 at 10:30 AM, erik quanstrom <quanstro@quanstro.net> wrote:
>>> "Lightweight EDF Scheduling with Deadline
>>> Inheritance" by Jansen, S.J.Mullender et al.
>>> <http://doc.utwente.nl/41399/1/000000c6.pdf>
>>
>> no.  that's not it.
>>
>> .TL
>> Real Time in Plan 9
>> .AU
>> Sape Mullender
>> Jim McKie
>> .AI
>>
>> - erik

Thank you Erik and Andrey.

--
  Ramakrishnan