linux-kernel - Re: is RSDL an "unfair" scheduler too?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-id: <45FC525D.5000708@argo.co.il>
Date:	Sat, 17 Mar 2007 22:41:01 +0200
From:	Avi Kivity <avi@...o.co.il>
To:	Ingo Molnar <mingo@...e.hu>
Cc:	Con Kolivas <kernel@...ivas.org>, ck@....kolivas.org,
	Serge Belyshev <belyshev@...ni.sinp.msu.ru>,
	Al Boldi <a1426z@...ab.com>, Mike Galbraith <efault@....de>,
	linux-kernel@...r.kernel.org, Nicholas Miell <nmiell@...cast.net>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: is RSDL an "unfair" scheduler too?

Ingo Molnar wrote:
> * Con Kolivas <kernel@...ivas.org> wrote:
>
>   
>> Despite the claims to the contrary, RSDL does not have _less_ 
>> heuristics, it does not have _any_. It's purely entitlement based.
>>     
>
> RSDL still has heuristics very much, but this time it's hardcoded into 
> the design! Let me demonstrate this via a simple experiment.
>
>
>   
[...]

> But it's easy to demonstrate this under RSDL: consider the following two 
> scenarios, which implement precisely the same fundamental computing 
> workload (everything running on the same, default nice 0 level):
>
> 1) a single task runs almost all the time and sleeps about 1 msec every
>    100 msecs.
>
>    [ run "while N=1; do N=1; done &" under bash to create such a 
>      workload. ]
>
> 2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1
>    msec and passes the 'token' around to the next task in the ring. (in
>    essence every task will sleep 9900 msecs before getting another run)
>
>
> Workload #1 uses 100% of CPU time. Workload #2 uses 99% of CPU time. 
> They both do in essence the same thing.
>
> if RSDL had no heuristics at all then if i mixed #1 with #2, both 
> workloads would get roughly 50%/50% of the CPU, right? (as happens if i 
> mix #1 with #1 - both CPU-intense workloads get half of the CPU)
>   

Well, the heuristic here is that process == job.  I'm not sure heuristic 
is the right name for it, but it does point out a deficieny.

A cpu-bound process with many threads will overwhelm a cpu-bound single 
threaded threaded process.

A job with many processes will overwhelm a job with a single process.

A user with many jobs can starve a user with a single job.

I don't think the problem here is heuristics, rather that the 
scheduler's manages cpu quotas at the task level rather than at the user 
visible level.  If scheduling were managed at all three hierarchies I 
mentioned ('job' is a bit artificial, but process and user are not) then:

- if N users are contending for the cpu on a multiuser machine, each 
should get just 1/N of available cpu power.  As it is, a user can run a 
few of your #1 workloads (or a make -j 20) and slow every other user down
- your example would work perfectly (if we can communicate to the kernel 
what a job is)
- multi-threaded processes would not get an unfair advantage

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/