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]

Message-ID: <20070502174829.GX19966@holomorphy.com>
Date:	Wed, 2 May 2007 10:48:29 -0700
From:	William Lee Irwin III <wli@...omorphy.com>
To:	Srivatsa Vaddagiri <vatsa@...ibm.com>
Cc:	Ting Yang <tingy@...umass.edu>, Ingo Molnar <mingo@...e.hu>,
	linux-kernel@...r.kernel.org
Subject: Re: [patch] CFS scheduler, -v8

On Tue, May 01, 2007 at 10:57:14PM -0400, Ting Yang wrote:
>>  "A Proportional Share REsource Allocation Algorithm for Real-Time, 
>> Time-Shared Systems", by Ion Stoica. You can find the paper here: 
>> http://citeseer.ist.psu.edu/37752.html

On Wed, May 02, 2007 at 11:06:34PM +0530, Srivatsa Vaddagiri wrote:
> Good paper ..thanks for the pointer.
> I briefly went thr' the paper and my impression is it expect each task
> to specify the length of each new request it initiates. Is that correct?
> If we have to apply EEVDF to SCHED_NORMAL task scheduling under CFS, how
> would we calculate that "length of each new request" (which is reqd
> before we calculate its virtual deadline)?

l_i and w_i are both functions of the priority. You essentially arrange
l_i to express QoS wrt. latency, and w_i to express QoS wrt. bandwidth.


On Tue, May 01, 2007 at 10:57:14PM -0400, Ting Yang wrote:
>>  EXAMPLE: assume the system runs at 1000 tick/second, i.e. 1ms a tick, 
>> and the granularity of pre-exemption for CFS is 5 virtual ticks (the 
>> current setting). If, at time t=0, we start 2 tasks: p1 and p2, both 
>> have nice value 0 (weight 1024), and rq->fair_clock is initialized to 0. 
>> Now we have: 
>>        p1->fair_key = p2->fair_key = rq->fair_clock = 0.
>> CFS breaks the tie arbitrarily, say it executes p1. After 1 system tick 
>> (1ms later) t=1, we have:
>>        rq->fair_clock = 1/2, p1->fair_key = 1,  p2->fair_key = 0.
>> Suppose, a new task p3 starts with nice value -10 at this moment, that 
>> is p3->fair_key=1/2. In this case, CFS will not schedule p3 for 
>> execution until the fair_keys of p1 and p2 go beyond 5+1/2 (which 
>> translates to about 10ms later in this setting), _regardless_ the 
>> priority (weight) of p3.

On Wed, May 02, 2007 at 11:06:34PM +0530, Srivatsa Vaddagiri wrote:
> There is also p->wait_runtime which is taken into account when
> calculating p->fair_key. So if p3 had waiting in runqueue for long
> before, it can get to run quicker than 10ms later.

Virtual time is time from the task's point of view, which it has spent
executing. ->wait_runtime is a device to subtract out time spent on the
runqueue but not running from what would otherwise be virtual time to
express lag, whether deliberately or coincidentally. ->wait_runtime
would not be useful for EEVDF AFAICT, though it may be interesting to
report.


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