Re: Tree based scheduling

Rauli Ruohonen (
Fri, 23 Jan 1998 22:42:14 +0200

In linux-kernel, Janos Farkas wrote:
>On 1998-01-23 at 09:05:57, Rauli Ruohonen wrote:
>> This scheduling scheme would need new user-space priority setting
>> utilities so users could renice them either globally or just relative
>> to his/her own processes. The normal nice/renice scheme should of
>> course work, and it would probably just do the user-specific
>> renicing.
>Not necessarily new setting tools, but new levels of levels. So, the
>priority could contain a priority group, "above" the priority:

Now that I've thought a bit more on this, I came up with following
enhancements to the original idea: (and haven't yet looked at VSTa, perhaps I
should soon..)

There should be one default scheduler in the kernel, and in addition other
schedulers (like QNX-scheduler, evolutionary scheduler, ...) as modules.
Well, perhaps two schedulers in kernel, "normal" and "round robin"
(for realtime tasks).

The whole tree would be visible in /proc/sched_tree (and with sysctl) and
you could do modifications with standard tools. This way users could just
"mkdir" their own nodes and have, for example, 3 processes running with the
qnx scheduler, 6 with the normal scheduler and these nodes themselves
scheduled with a round-robin scheduler. This particular example doesn't make
any sense, but there are other things that do (real-time processes, idle
processes, ..). The number of nodes a user could create would be limited,
of course (otherwise any user could cause a DoS)..

For example, you could do:

# cd /proc/sched_tree/cpu_all/other/uids/0/
# cat scheduler
# cat /proc/sched_tree/schedulers
# echo "qnx" >scheduler
# insmod my_scheduler.o
# cat /proc/sched_tree/schedulers
# cd ..
# mv 0/* /proc/sched_tree/cpu_all/real-time/uids/0
# mv 500/13342 /proc/sched_tree/cpu_all/real-time/procs
# tree_setprio /proc/sched_tree/cpu_all/real-time/procs 30

(note: this would allow root to do "mv 123/* 312/", which wouldn't make any
sense :} but still demonstrates that the scheduler tree is completely
separate from the process tree)
Yet another idea struck me while I was writing this: If you could tell
kernel "don't migrate processes from one CPU to another", you could do it in
user-space (perhaps there's no point in it, but..) :)

I haven't yet thought how to implement the user-scheduling, but perhaps it
would be a module that creates the "/uid" dirs when it's insmoded..
Note that fork() places the new process under the same node where the parent
was, so it would suffice to move all processes under their proper /uid/xxx/
node.. Except for real-time processes, perhaps.
An exception is setuid(), because when a user logs in, the process should be
placed to an appropriate uid directory. There probably should be
"tree_root->place_process(task_struct *foo)" which would search the tree in
a well defined order to find where to put the process. Each parent node
would have this function, so the user-scheduler module would just override
the default for the /uid directories.

Does it sound like it would cause too much overhead?

Real Users are afraid they'll break the machine -- but they're never
afraid to break your face.