linux-kernel - RE: Definition of fairness (was Re: [patch] CFS scheduler, -v11)

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, 9 May 2007 21:22:45 -0700
From:	"David Schwartz" <davids@...master.com>
To:	"Linux-Kernel@...r. Kernel. Org" <linux-kernel@...r.kernel.org>
Subject: RE: Definition of fairness (was Re: [patch] CFS scheduler, -v11)


> Ex: consider two equally important tasks T1 and T2 running on
> same CPU and
> whose execution nature is:
>
> 	T1 = 100% cpu hog
> 	T2 = 60% cpu hog (run for 600ms, sleep for 400ms)
>
> Over a arbitrary observation period of 10 sec,
>
> 	T1 was ready to run for all 10sec
> 	T2 was ready to run for 6 sec
>
> Over this observation period, how much execution time should T2 get,
> under a "fair" scheduler?

	Anywhere between 30% and 50% of the CPU is fair. There is nothing
particularly fair or unfair about how much credit you give an interactive
task. Less than 30% is unfair as the task is being punished for voluntarily
yielding. More than 50% is unfair as the task should not be entitled to more
than half the CPU if another task with equal static priority wants as much
CPU as possible.

	Slightly less than 30% or slightly more than 50% can also be reasonable due
to rounding or the scheduling interval beating against T2's internal timing.

	From a practical standpoint, we'd like such a task to get a bit more than
30%. How much more may reasonably depend on exactly what the sleep/run
interval is for the task. It would be unreasonable to expect a task to be
credited for sleeping for an entire day, but unreasonable to expect a task
to not get any credit for voluntarily yielding the CPU when it is later
ready-to-run.

	Typical UNIX schedulers bump a task's dynamic priority when it voluntarily
yields. As a result, it can pre-empty a CPU-burner when it later becomes
ready-to-run. This is intended more to reduce latency than to increase CPU
share. However, it should also have the effect of giving a polite task more
CPU than pure CPU-burned when it needs it. (That's only fair.)

	DS


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