linux-kernel - Re: [PATCH try 3] CFS: Add hierarchical tree-based penalty.

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>] [day] [month] [year] [list]

Message-ID: <87939.1771286877776896.JavaMail.root@ifrit.dereferenced.org>
Date:	Tue, 12 Oct 2010 14:02:56 +0400 (MSD)
From:	William Pitcock <nenolod@...eferenced.org>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...e.hu>,
	Mike Galbraith <efault@....de>
Subject: Re: [PATCH try 3] CFS: Add hierarchical tree-based penalty.

Hi,

----- "Peter Zijlstra" <peterz@...radead.org> wrote:

> On Tue, 2010-10-12 at 13:34 +0400, William Pitcock wrote:
> > Yes, this should be a multiplication I believe, not a divide.  My
> original
> > code had this as a multiplication, not a division, as does the new
> patch.
> > 
> > However, I think:
> > 
> >     vruntime >>= tsk->fork_depth;
> > 
> > would do the job just as well and be faster. 
> 
> That's still somewhat iffy as explained, vruntime is the absolute
> service level, multiplying that by 2 (or even more) will utterly
> upset
> things.
> 

Yes, this is why I thought that doing a division would be better.

> Imagine two runnable tasks of weight 1, say both have a vruntime of 3
> million, seconds (there being two, vruntime will advance at 1/2
> wall-time).
> 
> Now, suppose you wake a third, it too had a vruntime of around 3
> million
> seconds (it only slept for a little while), if you then multiply that
> with 2 and place it at 6 mil, it will have to wait for 6 mil seconds
> before it gets serviced (twice the time of the 3 mil difference in
> service time between this new and the old tasks).
> 
> So, theory says the fair thing to do is place new tasks at the
> weighted
> average of the existing tasks, but computing that is expensive, so
> what
> we do is place it somewhere near the leftmost task in the tree.
> 
> Now, you don't want to push it out too far to the right, otherwise we
> get starvation issues and people get upset.
> 
> So you have to somehow determine a window in which you want to place
> this task and then vary in that depending on your fork_depth.
> 
> Simply manipulating the absolute service levels like you propose
> isn't
> going to work.

I think I have a solution to this.  Presently waiting on a kernel rebuild
on my laptop so I can test.

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