linux-kernel - Re: [patch] CFS scheduler, -v8

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]

Date:	Wed, 2 May 2007 12:42:47 -0700
From:	William Lee Irwin III <wli@...omorphy.com>
To:	Ingo Molnar <mingo@...e.hu>
Cc:	Srivatsa Vaddagiri <vatsa@...ibm.com>,
	Ting Yang <tingy@...umass.edu>, linux-kernel@...r.kernel.org,
	"Tong N. Li" <tong.n.li@...el.com>
Subject: Re: [patch] CFS scheduler, -v8

* William Lee Irwin III <wli@...omorphy.com> wrote:
>> Things are moving in good directions on all this as far as I'm 
>> concerned. Moving according to Ting Yang's analysis should wrap up the 
>> soundness concerns about intra-queue policy I've had. OTOH load 
>> balancing I know much less about (not that I was ever any sort of an 
>> expert on single queue affairs). [...]

On Wed, May 02, 2007 at 09:12:35PM +0200, Ingo Molnar wrote:
> the whole move to ->load_weight based calculations was to make CFS 
> integrate better with load-balancing and to bring the smpnice 
> infrastructure even more into the scheduler mainstream. [ There's a 
> small smpnice related buglet i fixed in -v9-to-be (based on Balbir 
> Singh's feedback), but otherwise it behaves quite well on SMP and that's 
> not a big surprise: i left the load-balancer largely intact. ]

Despite the original motive, the ->load_weight -based calculations
largely resolved my concerns about intra-queue prioritization. They
were the change to the ->fair_key computation I wanted to see, which
were still not enough because of the O(rq->nr_running) lag issue due to
the differences from EEVDF, but I wasn't entirely aware of that, only
suspicious that some issue remained.

Load balancing has non-negligible impacts on fairness but I'm almost
entirely ignorant of the aspects of the theory relating to it. More
knowledgeable people, e.g. Tong Li and Ting Yang, need to take over
reviewing here much as they did on the intra-queue front, where I only
knew enough to drop hints and not to make more useful suggestions.

O(1) vs. O(lg(n)) priority queues are not what matter here (well,
obviously O(n) priority queues would break), but rather O(1) vs. O(n)
lag.

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