linux-kernel - Re: [ANNOUNCE/RFC] Really Simple Really Fair Scheduler

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: <Pine.LNX.4.64.0709040130360.1817@scrub.home>
Date:	Tue, 4 Sep 2007 04:50:57 +0200 (CEST)
From:	Roman Zippel <zippel@...ux-m68k.org>
To:	Ingo Molnar <mingo@...e.hu>
cc:	linux-kernel@...r.kernel.org, peterz@...radead.org,
	Mike Galbraith <efault@....de>
Subject: Re: [ANNOUNCE/RFC] Really Simple Really Fair Scheduler

Hi,

On Mon, 3 Sep 2007, Ingo Molnar wrote:

> > It's a variation of the sleeper bonus. [...]
> 
> hm, where are its effects described in your explanation? Seems like a 
> key item.

It has no direct effect on the correctness of the mathematical model, the 
time is initialized before the time is added to the model.
What you're after is the effect on the behaviour, which wasn't my focus, 
so sorry, I didn't mention it.

> > [...]  Let's assume two running tasks which have been running for 95ms 
> > and 105ms and a time slice of 10ms, the average is thus 100ms. If the 
> > new task has been sleeping for a while it starts at 90ms, if the task 
> > had been running lately it doesn't get this bonus again.
> 
> what happens if there are lots of such tasks? What limits the total 
> bonus?

Every task gets a little more bonus, but it grows quite slowly, every task 
gets time_slice/task_cnt more than the previous one (assuming all tasks 
are started at the same time), so the 10th gets 2.82*time_slice, the 100th 
gets 5.18*time_slice, the 1000th gets 7.48*time_slice...

I thought about it already and I didn't consider it a serious problem, 
however it's solvable if needed by keeping the bonus separate:

	avg = avg_exec_runtime(cfs_rq);
	se->time_norm = kclock_max(avg - time_slice, se->time_norm);
	se->bonus = avg - se->time_norm;
	cfs_rq->time_sum += avg;

But the bonus also had to be undone when unqueueing the task:

	cfs_rq->time_sum -= se->time_norm + bonus;

> > That would be equivalent to simply clearing wait_runtime in CFS.
> 
> so my prototype patch is not an exact map of the nice-0 special-case of 
> your code? Would this be the correct thing then perhaps:
> 
> +               se->exec_runtime =
> +                       max(avg_exec_runtime(cfs_rq), se->exec_runtime);

You should substract the desired bonus here from the average as above and 
evtl. also store the given bonus separately.

bye, Roman
-
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/