Comments on snippet: 'pthread sleeper fairness'

deepsoul said on 14/Sep/2009

Mon, 14 Sep 2009 17:11:57 UTC

Surprise, surprise: I just tested my Linux box and obtained SIGALRM. thread0: 4891, thread1: 412, switch:3 as the most unfair of several runs with the unchanged program. Setting EXIT_AFTER to 10 gives SIGALRM. thread0: 9090, thread1: 43200, switch:15 as the worst result. With EXIT_AFTER=100 the worst case is: SIGALRM. thread0: 184344, thread1: 338777, switch:63 As one can see, the results become fairer as the test time and the number of task switches increases. Probable reason: My kernel was compiled with the option `CONFIG_HZ_250=y`. This means the interrupt timer frequency on which the scheduler depends is set to 250 Hz. The kernel config help calls this the compromise between 100Hz (for servers, few interrupts that would reduce overall performance) and 1000Hz (for desktops, fastest response to user events). A low timer frequency gives infrequent task switches and therefore little "fairness". Stock distribution kernels tend to be built with 1000Hz timer frequency, hence the fair results you saw. Look at `/boot/config-` to check. Thanks for the program! I will test some other Linux boxes I have access to which run distribution kernels and post the results.

deepsoul said on 14/Sep/2009

Mon, 14 Sep 2009 17:16:24 UTC

That should have been: Look at `/boot/config-` to ckeck.

deepsoul said on 14/Sep/2009

Mon, 14 Sep 2009 17:19:11 UTC

Another try: Look at `/boot/config-` to check. Sorry this took so long.

keigoi said on 15/Sep/2009

Tue, 15 Sep 2009 00:51:36 UTC

Thanks for comments, deepsoul! Actually, this code simulates context switching in O'Caml programming language (native code, compiled with ocamlopt). I suppose other scripting languages like Ruby and Python might take similar scheduling mechanism. Sorry for incomplete explanation. I will revise it. After googlin' some words like `fairness pthread scheduling` etc, I found this wikipedia page: Completely Fair Scheduler according to this, the kernel which version is greater or equal to 2.6.23, which is supposed to be equipped with CFS, will provide CPU time to each threads fairly, even if a thread waits for long time because of locked mutex. I suppose that the reason of unfairness in other OSs is that the `fairness' of their scheduling algorithm does not take into account sleeping threads. I found CONFIG_HZ in my linux (kernel 2.6.26, which is "fair"):


# CONFIG_HZ_100 is not set
CONFIG_HZ_250=y
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=250

hence I suppose that CONFIG_HZ parameter is irrelevant for fairness in this case.

deepsoul said on 17/Sep/2009

Thu, 17 Sep 2009 14:26:17 UTC

Oh well, there goes that theory. It would have been crass if a factor of 4 in the timer frequency had caused a factor of 100 in the timescale at which scheduling becomes fair, so this puts the world right in a way. **But** I have in the mean time tested three other linux systems. All (including the one above) run kernels with versions 2.6.23 or later, so use the CFS scheduler. Except for one, they gave the same results as the first machine above - fairness only at minute timescales. This one is distinguished by being a single-core CPU. The others are dual-core or (one of them) an Intel Atom which is treated as dual-core due to hyperthreading. This is the cause of the discrepancy: When I restrict the program to run on one core only (with the command `taskset 0x1`), the scheduling is perfectly fair on all machines at the default test time of one second! Your program seemed to run almost exclusively on one CPU anyway, but I saw this only visually from xosview, so it may simply give inaccurate results on multi-cores. Finally, I tested a windoze box (compiled and run via Cygwin). It behaved not quite as fairly as the single-core linux results, but decently. A typical result: SIGALRM. thread0: 1970, thread1: 2543, switch:6