linux-kernel - Re: [PATCH 08/16] sched: add period support for -deadline tasks.

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:	Thu, 12 Apr 2012 08:39:01 +0200
From:	Luca Abeni <luca.abeni@...tn.it>
To:	Steven Rostedt <rostedt@...dmis.org>
CC:	Juri Lelli <juri.lelli@...il.com>, peterz@...radead.org,
	tglx@...utronix.de, mingo@...hat.com, cfriesen@...tel.com,
	oleg@...hat.com, fweisbec@...il.com, darren@...art.com,
	johan.eker@...csson.com, p.faure@...tech.ch,
	linux-kernel@...r.kernel.org, claudio@...dence.eu.com,
	michael@...rulasolutions.com, fchecconi@...il.com,
	tommaso.cucinotta@...up.it, nicola.manica@...i.unitn.it,
	dhaval.giani@...il.com, hgu1972@...il.com,
	paulmck@...ux.vnet.ibm.com, raistlin@...ux.it,
	insop.song@...csson.com, liming.wang@...driver.com
Subject: Re: [PATCH 08/16] sched: add period support for -deadline tasks.

Hi Steven,

On 04/11/2012 10:32 PM, Steven Rostedt wrote:
> On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
>
>> @@ -293,7 +293,11 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
>>    * assigned (function returns true if it can).
>>    *
>>    * For this to hold, we must check if:
>> - *   runtime / (deadline - t)<  dl_runtime / dl_deadline .
>> + *   runtime / (deadline - t)<  dl_runtime / dl_period .
>> + *
>> + * Notice that the bandwidth check is done against the period. For
>> + * task with deadline equal to period this is the same of using
>> + * dl_deadline instead of dl_period in the equation above.
>
> First, it seems that the function returns true if:
>
> 	dl_runtime / dl_period<  runtime / (deadline - t)
>
>
> I'm a little confused by this. We are comparing the ratio of runtime
> left and deadline left, to the ratio of total runtime to period.
>
> I'm actually confused by this premise anyway. What's the purpose of
> comparing the ratio? If runtime<  (deadline - t) wouldn't it not be able
> to complete anyway? Or are we thinking that the runtime will be
> interrupted proportionally by other tasks?
I see that other people have been faster than me to reply (and Tommaso's
reply is pretty good).

I just add that the original CBS algorithm (which introduced this kind
of check) assumed "relative deadline = reservation period". So, if you
are wondering why
	dl_runtime / dl_deadline
is changed into
	dl_runtime / dl_period
I agree that this is not too clear... In my opinion, a more correct (but
probably too pessimistic) check should use
	dl_runtime / min(dl_deadline, dl_period)


Also, note that this check is presented as
	c_s >= (d_{s,k} - r_{i,j})U_s
(where U_s = Q_s/T_s = dl_runtime / dl_period - with dl_period = dl_deadline)
in the original paper (see the "When a job J_{i,j} arrives and the server is
idle..." item at the end of the first column of the third page of the paper).

Also, regarding the "Server mechanisms for multimedia applications" technical
report mentioned by Tommaso, you can download it from here:
http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps



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