linux-kernel - Re: fair clock use in CFS

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 for Android: free password hash cracker in your pocket

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

Date:	Mon, 14 May 2007 04:05:00 -0700
From:	William Lee Irwin III <wli@...omorphy.com>
To:	Ingo Molnar <mingo@...e.hu>
Cc:	Srivatsa Vaddagiri <vatsa@...ibm.com>, efault@....de,
	tingy@...umass.edu, linux-kernel@...r.kernel.org
Subject: Re: fair clock use in CFS

On Mon, May 14, 2007 at 02:03:58PM +0530, Srivatsa Vaddagiri wrote:
>>> 	I have been brooding over how fair clock is computed/used in
>>> CFS and thought I would ask the experts to avoid wrong guesses!
>>> As I understand, fair_clock is a monotonously increasing clock which
>>> advances at a pace inversely proportional to the load on the runqueue.
>>> If load = 1 (task), it will advance at same pace as wall clock, as 
>>> load increases it advances slower than wall clock.
>>> In addition, following calculations depend on fair clock: task's wait
>>> time on runqueue and sleep time outside the runqueue (both reflected in
>>> p->wait_run_time).

* William Lee Irwin III <wli@...omorphy.com> wrote:
>> It's not hard to see that that's a mistake. [...]

On Mon, May 14, 2007 at 12:31:20PM +0200, Ingo Molnar wrote:
> please clarify - exactly what is a mistake? Thanks,

The variability in ->fair_clock advancement rate was the mistake, at
least according to my way of thinking. The queue's virtual time clock
effectively stops under sufficiently high load, possibly literally in
the event of fixpoint underflow. The waiting time is impossible to
scale properly in the presence of a variable time rate (at least under
the memory allocation constraints of a scheduler), and the deadlines
computed as offsets from ->fair_clock come out clustered.

Basically it needs to move closer to EEVDF in these respects.

This detail sailed right past me when it went in; sorry about that.

-- wli
-
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/