Multi Factors Scores

[hamadmarri]

Hi Everyone,

I have added two more scores to the Interactivity Score for testing. Starving and Cache scores. The final score is the sum of the 3 scores.

Starving Score

Default factor is: 19660, which is about interactivity_factor * 0.6
Divisor: 3000000 (3ms)

The divisor is used in the score equation. All scores are bounded by their factors.

Algorithm:

if starve_factor == 0
	return 0

if task = current task
	return 2 * starving_factor

starving = now - last_run

if starving_divisor >= starving
	return (2 * starving_factor) - (starving_factor / (starving_divisor / starving));
else
	return starving_factor / (starving / starving_divisor);

Cache Score

Default factor is: 13107, which is about interactivity_factor * 0.4
Divisor: 1000000 (1ms)

Algorithm:

if cache_factor == 0
	return 0

if task = current task
	return 0

cache_period = now - exec_start

if cache_divisor >= cache_period
	return cache_factor / (cache_divisor / cache_period);
else
	return (2 * cache_factor) - (cache_factor / (cache_period / cache_divisor));

Notice that those equations are just like the interactivity score equation. Starving equation is written in the opposite way just for readability so we always compare with the divisor.

Some notes

• All scores IS, SS, and CS are designed in a way that 0 means the highest and 2 * factor is the lowest. Task with the smallest scores will run on cpu.
• I advice that both starving and cache factors are <= Interactivity_factor.

Motivation

Depending solely on IS can have some issues. A task which its IS is very low value (ex. 0) will run on the cpu and won't leave it until its IS become greater than the next task's IS. It could be good to save context switches and cpu cache, but other tasks may wait too much for the current tasks to preempt. Therefore the starving factor is introduced to help. A currently running task will always be punished by a starving factor = max (which is 2*starving_factor) because obviously it is not starving since it is already running. For other tasks, the more they are not running, the less starving value they got (less value means good for tasks). So instead of running a task in one shot until reaching a preempt-able IS value, the starving score will help to preempt the current task for small amount of time (1 tick mostly) and run the starving task/s for 1 tick each. Even if the starving task has very high IS value (think of running HD video) it will have some time to run (at least one tick, then its starving value will reset and it will leave the cpu again in the next tick for that high interactivity score task).

Starving score can make the scheduler too smooth, where it will be somehow similar to CFS. The responsiveness could be affected by starving score. Thus, I added cache score which tries to keep a task sticky to the cpu. You can experiment with high cache factor values and notice that the system may freezes until the current running tasks finishes.

Cache score works together with starving score, if you disable starving score (with starving factor = 0) and having high cache factor, then the system won't run properly.

Tuning

I suggest that you think of Interactivity factor as the base value, and first tune starving factor while cache factor = 0. After you got a nice starving factor, increasing cache factor gradually.

Try use perf tools which shows the cache miss and other stuff. I have tested the responsiveness script with:

sudo perf stat -e context-switches,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses,branches,branch-misses -a -B python3 responsiveness.py -i1 -p4 --np 3

And got more responsiveness by tuning starving and cache factors. Also, the throughput of the prime is not effected much.

You can also sysctl the divisors too.

The mfs patch is on cacule where rdb is still balancing based on IS only. You can test the patch on both cacule and cacule+rdb

https://github.com/hamadmarri/linux/tree/cacule-5.13-mfs
https://github.com/hamadmarri/linux/tree/cacule-5.13-rdb-mfs

https://github.com/hamadmarri/cacule-cpu-scheduler/tree/master/patches/CacULE/experimental

Sysctls:
sched_starve_factor
sched_starve_divisor
sched_cache_factor
sched_cache_divisor

Please let me know if you got any interesting values.
Thank you

[raykzhao]

Hi @hamadmarri,

The default setting with rdb+autogroup is quite smooth on my laptop.

Thank you for your great work!

[ptr1337]

@raykzhao

Are you using this patch with autogroup enabled ?

https://github.com/hamadmarri/cacule-cpu-scheduler/blob/master/patches/CacULE/experimental/rdb-5.13-mfs.patch

need to test that :D

[raykzhao]

Hi @ptr1337

The synced rdb-autogroup patch here can be directly applied on top of the CacULE-mfs patch.

[ptr1337]

Much thanks, ill report!!

[ptr1337]

Running right now cacule-mfs + rdb autogroup from @raykzhao
compiled with lto thin and runs very good so far.

need to test more. ill report!

[raykzhao]

Hi @hamadmarri @ptr1337

I can see that the latest rdb-autogroup already merged some changes from the mfs patch. Here is the synced mfs patch that can be applied on top of the latest rdb-autogroup patch. Basically it only adds the mfs scoring part.
mfs.patch.zip