hamadmarri / tt-cpu-scheduler

Task Type (TT) is an alternative CPU Scheduler for linux.

TT CPU Scheduler

Task Type (TT) is an alternative CPU Scheduler for linux.

The goal of the Task Type (TT) scheduler is to detect tasks types based on their behaviours and control the schedulling based on their types. There are 5 types:

1. REALTIME
2. INTERACTIVE
3. NO_TYPE
4. CPU_BOUND
5. BATCH

Find the descriptions and the detection rules in tasks.ods

The benefit of task types is to allow the scheduler to have more control and choose the best task to run next in the CPU.

TT gives RT tasks a -20 prio in vruntime calculations. This boosts RT tasks over other tasks. The preemption rules are purely HRRN where RT tasks have a priority since their vruntimes are relatively less than other types. The reason of using HRRN instead of hard level picking is to smooth out the preemtions and to prevent any chance of starvation.

Monitoring detected tasks

You need to compile with CONFIG_SCHED_DEBUG=y. I have added a field in the output of tasks information task_type. See and use ttdebug.sh.

Usage examples:

ttdebug.sh | grep -i realtime

watch -t "(ttdebug.sh | grep -i interactive)"

watch -t "(ttdebug.sh | egrep -i 'webco|firefox')"

Note: Tasks types are detected based on their behaviour, not by what it should be. So if systemd at some point acted like a REALTIME tasks and went for long sleep then the type would be REALTIME until it wakes up and get its type updated. You might see many sleeping tasks with incorrect types because at some point on booting time they acted like REALTIME, CPU_BOUND, or whatever type. Those tasks are sleeping for long time, so when they wake up their type will be INTERACITVE sine they have very hight HRRN value. So, don't worry about the type of sleeping system processes.

sysctls

kernel.sched_tt_max_lifetime

Default is 22s. This is the tasks' maximum life time to normalize their life time and vruntime. Similar to CacULE's cacule_max_lifetime.

kernel.sched_tt_rt_prio Default is -20. Range [-20, 19]. In case that tasks with types other than realtime are starving because of realtime tasks' priorities are too high, you can soften the priority of realtime tasks. The -20 is the highest, 19 is the least priority.

kernel.sched_tt_interactive_prio Default is -10. Range [-20, 19].

kernel.sched_tt_cpu_bound_prio Default is -15. Range [-20, 19].

kernel.sched_tt_batch_prio Default is 19. Range [-20, 19].

kernel.sched_tt_balancer_opt

It can be set to 4 values:

• 0: Normal TT balancer
• 1: Candidate Balancer (which is an addition to normal TT balancer - good for reponsiveness (perfomance gets affected when #CPUs > 4))
• 2: CFS balancer (default - good for perfomance/throughput)
• 3: Power save balancer (tries its best to avoid running tasks on idle cpus - saves power)

You can change the balancer option at run time.

kernel.sched_tt_lat_sens_enabled Default is 1. latency sensitive keeps CPUs (with no tasks) at high frequency for sometime (~1ms) in case of incoming task during this time would run faster. It reduces latency but increases power consumption. If Power save balancer is chosen, then this option has no effect (i.e. disabled, = 0).

kernel.sched_tt_dedicated_cpu_bound_enabled Default is 1. This option stick a CPU bound task to its current CPU to enhance cache locality. A CPU can only have one dedicated cpu bound task.

Support

Telegram: https://t.me/tt_sched

Thank you

Hamad

tt-cpu-scheduler's Issues

TT scheduler data usage

Hi @hamadmarri

I have been testing TT scheduler in my daily work routine for 1 complete day (no gaming related), and in general the experience was great, no lags, no hangs, etc. and the system was responsive, only one thing that I will explain later. I tested on 5.14.16-cacule and I 5.14.16 with your TT patch, I also will test the 5.15.1-tt and 5.15.1-cacule(I applied your 5.14 full patch with no problems and is working so far)

My aspects in general are:

8 x Intel Core i7-8665U @ 1.90 Ghz
Ubuntu 20.04.3 LTS
32 Gb ram
KDE plasma 5.18.7
zram 8GB algorithm lzo-rle

I've worked using overclocking in my laptop and always the temperature was approx 80 C.

Something I noticed using TT was that my local builds some times were double of the normal time under high process demand.
I opened 2 android emulators(QEMU), ide, chrome, slack, etc. Using cacule gives me the best results when I'm doing multiple tasks (debuggin, building, jumping in meetings, etc) the compilation times are constants e.g. 4-5 min per project, and also playing some video/music on the background, using cacule and doing all of these task I only notice some times a lag in the emulators, or in latte-dock, but system is responsive,some kde desktop animations become a little slow, but I repeat only minimum lag switching between windows.

With TT I've noticed longer lags on the same apps, even in the android emulator the app I am using stops, the building in the background goes to 8-10 minutes build time, some windows freezes, and the lag in latte is more noticeable, when the background build stops the system works like a charm again, If a I have a low CPU demand everything works normally.

I have some log files using your TT script (every log is with a building in the background, 2 emulator opened and a video playing in the background) I opened kate and was frozen
kate.txt

when the java builds lasted twice as long
java.txt

and the emulator slowed down
emulator.txt

Also run some stress test on TT
stress-ng
stress-ng-tt.txt

sysbench( different runs (4) take the one with more events of all of them)
sysbench_tt.txt

Cacule
stress-ng
stress-ng-cacule.txt

sysbench
sysbench-cacule.txt

and finally your responsiveness python script

responsive_cacule.txt
responsive_tt.txt

To me cacule is the one with the best results in 5.14.16 for multitasking and high cpu demand, TT and cacule have the same result to me in single tasks and low cpu demand, now I'm testing 5.15.1 with your 5.14.full patch applied, I know it is for 5.14 but I wanted to tested in 5.15.

responsive_cacule_15.txt

at the moment I'm doing the same "tests" in 5.15 and I see a better performance than in 5.14.

If you need a very specific test or log do not hesitate to ask me, as soon as I can I will share it with you and as soon as I have results and commentary for 5.15 tt and cacule I will post it here.

Thanks!

The high-hz.patch should be in the 5.16 patch folder too

[bug] k3s does not work with TT Scheduler

This might be a duplicate of #14, though I am not sure.
When I attempted to start the k3s systemd service, it fails.
Full journalctl -eu k3s.service log is here: https://fars.ee/XESP

This line in the log seems to be the cause:

k3s[5373]: time="2023-09-27T22:03:57+08:00" level=fatal msg="failed to find cpu cgroup (v2)"

I am pretty sure I am using cgroup v2 unified hierarchy, and I gave proper Delegate to the cpu cgroup:

$ cat /sys/fs/cgroup/cgroup.controllers
cpuset io memory hugetlb pids rdma misc
$ cat /etc/systemd/system/[email protected]/delegate.conf 
[Service]
Delegate=cpu cpuset io memory pids
$ systemctl show [email protected] -p Delegate
Delegate=yes
$ cat /sys/fs/cgroup/user.slice/user-60255.slice/[email protected]/cgroup.controllers
cpuset io memory pids

The cpu cgroup controller seems to be mysteriously missing when TT Scheduler is used, which causes the failure of k3s. This is not observed on linux kernel with CFS and the same config (other than TT specific config).

Latency_nice proposal for use in TT

Good morning
First of all, I want to apologize for my English

Additionally, I want to thank you for your hard work on Linux Scheduler and more
especially for BABY-CPU-SCHEDULE, thanks to which I am constantly learning
various algorithms.
I was forced to do so by the COVID-19 pandemic to bring in my 10-year-old
son's laptop for remote work.
I am not a programmer and I also want to mention it at the outset.

Back to the point
I am currently checking my stock kernel 5.13 with your Cachy Scheduler
v5.9-Idle with additional patches some solution.Parth Shah latency_nice series of patches

https://lkml.org/lkml/2020/5/7/575

Unfortunately I don't have benchmarks but implemented it alongside
MLFQ for the classification of latency_nice tasks. After a few modifications, the kernel
classifies
only user processes with no children, leaving the system alone. As
for me the usability experience for normal system operation is very much
promising.
If you are able and have time to experiment, you can take a look at
series of patches
Patha Shah. Maybe the idea will be useful for the development of TT?

Currently I'm not going to switch to kernel> 5.13, I don't
I don't know why, but for me it works weird on the desktop (subjectively
feeling).

I did a general test of my kernels with a backport to 5.13 of your solutions, but
as you know, what's good for desktops doesn't always equal performance.
Mine is cachyb2. I know compiling Clang 13 with LTO is always faster than GCC
even with the GCC LTO, but the overall picture shows that 5.14 and 5.15 after the changes
weirdly poorly with the SCHED_CORE changes.

https://openbenchmarking.org/result/2111136-IB-SCHEDULER42&export=pdf

Same kernel settings as for BABY-CPU: CONFIG_HZ_803 and https://github.com/hamadmarri/cacule-cpu-scheduler/blob/master/scripts/apply_suggested_configs.sh

I can reveal a binary version of my kernel.
I'm ashamed of my code.
I don't want to publish this to you at the moment.

Thank you for your interest

how to enable TT?

i yay -S'ed linux-tt package, it compiled and installed
what should i do next? thanks in regards

Severe performance issues with Back 4 Blood.

Ill give details as needed but i dont know what to include here other than my experience.
Basicly B4B lags VERRRY badly with this scheduler. Its mostly unplayable. This is not an issue with the regular xanmod or any other scheduler except bmq in my experience.

Deferred some updates during migration (locking 2 runqueues)

hamadmarri/linux-baby@95e9c5c

This change removes some unneeded updates during task migration
(while locked 2 runqueues) and make some updates
deferred after releasing the lock.
it saves some locking time (nanoseconds though not much)

Please test and let me know if it worths to merge.

Some benchmarks I did for vblank_mode=1 glxgears
the first column (with -dev suffix) is the full deferred patch, the next has only removed update_curr without the deferred stuff, the last two are repeated tests for TT without any changes.

glxgears.ods

Thank you

ananicy

Hello,

how does this scheduler interacts with ananicy?
is it ok to use with your scheduler? Should it be disabled?

Thanks!

error: implicit declaration of function ‘printk_deferred_once’

Hi, Hamad. When I compiled with the latest patch tt-5.15-r2 I encountered the following error.

  CC      kernel/sched/bs.o
In file included from kernel/sched/bs.c:9:
kernel/sched/tt_stats.h: In function ‘check_schedstat_required’:
kernel/sched/tt_stats.h:794:17: error: implicit declaration of function ‘printk_deferred_once’ [-Werror=implicit-function-declaration]
  794 |                 printk_deferred_once("Scheduler tracepoints stat_sleep, stat_iowait, "
      |                 ^~~~~~~~~~~~~~~~~~~~
cc1: some warnings being treated as errors
make[2]: *** [scripts/Makefile.build:277: kernel/sched/bs.o] Error 1
make[1]: *** [scripts/Makefile.build:540: kernel/sched] Error 2
make: *** [Makefile:1868: kernel] Error 2
==> ERROR: A failure occurred in build().
    Aborting...

I see it on line 5313 of the latest commit.

[question] Is possible to use Docker Server with TT enabled in kernel?

Hi Hamad Al Marri,

Is it possible to have the TT in kernel and the docker server working properly?
Is there a problem with CGROUPs?

// level=warning msg="Unable to find cpu cgroup in mounts"

A good day.
Ionut.

Yield fix

When Task t1 calls yield, a yield mark is set to its vruntime on the most sig. bit to make it large, and it gets reset when another task gets picked.

However, in case there is no other tasks except t1 in the rq, no need to mark it with the yield bit.

5.16.x and patch rt

There is no rt.patch for version 5.16, why? Is there no need?
i.e. no need? just apply tt.patch?

Build error: implicit declaration of function ‘update_load_add’

Hello.

Trying out TT for the first time, and compiling against 5.16.4 with the tt-5.16.patch fails with the following error:

In file included from kernel/sched/bs.c:11:
kernel/sched/bs.h: In function ‘account_entity_enqueue’:
kernel/sched/bs.h:206:9: error: implicit declaration of function ‘update_load_add’; did you mean ‘update_load_avg’? [-Werror=implicit-function-declaration]
  206 |         update_load_add(&cfs_rq->load, se->load.weight);
      |         ^~~~~~~~~~~~~~~
      |         update_load_avg
kernel/sched/bs.h: In function ‘account_entity_dequeue’:
kernel/sched/bs.h:217:9: error: implicit declaration of function ‘update_load_sub’; did you mean ‘update_load_avg’? [-Werror=implicit-function-declaration]
  217 |         update_load_sub(&cfs_rq->load, se->load.weight);
      |         ^~~~~~~~~~~~~~~
      |         update_load_avg
In file included from kernel/sched/bs.c:1595:
kernel/sched/bs_nohz.h: In function ‘nohz_try_pull_from_candidate’:
kernel/sched/bs_nohz.h:719:24: warning: unused variable ‘cfs_rq’ [-Wunused-variable]
  719 |         struct cfs_rq *cfs_rq;
      |                        ^~~~~~

.config: config.txt

wake_affine_weight

Port wake_affine_weight from CFS

Global runqueue

Branch: https://github.com/hamadmarri/linux-baby/tree/tt-grq

Welcome back to GRQ again. I still have some hope to implement global runqueue
on current CFS. It is not an easy task apparently. I have reimplemented the
old GRQ with slight modification. Don't use this commit 385bff302e395a88306fba3823c21d231c8c31f2
since it freezes like the old GRQ implementation on Cachy/CacULE.

However, in 11962a4e7cc20dd5fa9539d88c7a884b93995301 is a try to fix freezing issue. I am testing it right now, but as usual whenever I believe it is fixed it will surprise me with a freeze at random time/day! But so far no freezes yet.

If you want to test, make sure that you don't have any important files on your computer since the GRQ freezes can cause damage to FS. Also, don't use GRQ while your are doing important tasks

Please let me know if you got any freezes with this commit and later 11962a4e7cc20dd5fa9539d88c7a884b93995301 and whether it has better performance/latency

Thank you

AMD GPU Issue

Hello,
Since kernels 6.1 and above (did not tested with 6.0)
I can't use TT CPU Sched.

All actions requiring an interaction with my GPU (AMD RX 6800 XT) are all drastically long.
Quick example:
Starting xterm: 0.03s
Starting alacritty: 29.11s

Same goes for Steam, or Chromium (even with HW Accel off). If we talk about games, for an unknow reason back 3~4 days ago I succesfully started AIM Lab, benchmarking it with MangoHud (linux-xanmod-tt [5.15] vs linux-xanmod-tt-uksm-cjktty [6.1.8]) gave about 30% perfomance gain.

While writing those lines, I re-tried some GPU software.
It appear that TT Sched some take it sweet time to start a full communication with the GPU.
After 15~20 mins of uptime, the PC finally seem fully ready to do his job.
EDIT: Nah, nevermind, sometime he seem ready, sometime he seem sleepy

Distro: ArchLinux
CPU: AMD R9 5950X (SMT off, no diff with it)
RAM: 64Go G.Skill 3600Mhz (F4-3600C16-16GTZNC)
GPU: AMD RX 6800 XT Midnight Edition
MOBO: Gigabyte X570 Gaming X (Rev 1.0) (I highlyyyyyy suspect that this little fu**er to be the culprit here)
WM: AwesomeWM (official repo)
Driver: Either it is Vulkan (AMDVLK, AMDGPU-Pro and RADV) or OpenGL (Mesa and AMDGPU-Pro) problem happen.

With Kernel 5.15-Xanmod-TT from Chaotic-AUR, no problems.
With Kernel 6.1.8-Xanmod-TT problem appear.
No problems with other CPU Sched such as Bore, CFS, PDS, BMQ (Kernel 6.2.7 TKG compiled at the same time as this one).

Except for my MOBO suspicion that I would like to replace to validate it is it that create this problem. All of my analysis point to CPU Sched for the hang problem.

Any idea on what I can do to solve/investigate further the problem ?

Any help, or comparisons with similar installation (AMD CPU & GPU combo) are very welcome. It would help me determinate if the problem is my MOBO / or any other part or if it is the CPU Sched or my config that is problematic.

Thanks for the reading.

`arch_asym_cpu_priority` undefined

Hi @hamadmarri,

Thank you for continuing development of alternative Linux kernel schedulers.

When I tried to compile the kernel with the tt-5.14.patch, I got the following errors during linking:

ld: kernel/sched/bs.o: in function `trigger_load_balance':
bs.c:(.text+0x601b): undefined reference to `arch_asym_cpu_priority'
ld: bs.c:(.text+0x6026): undefined reference to `arch_asym_cpu_priority'
ld: kernel/sched/topology.o: in function `build_sched_domains':
topology.c:(.text+0x1c27): undefined reference to `arch_asym_cpu_priority'
ld: topology.c:(.text+0x1c31): undefined reference to `arch_asym_cpu_priority'
make: *** [Makefile:1180: vmlinux] Error 1

I guess this is used in sched_asym_prefer when NO_HZ is enabled. Here I also attach my kernel config file.
config.zip

Frequency locked with `ondemand` governor

Hi @hamadmarri,

I notice that with the tt-scheduler on 5.15 kernel, the lowest frequency of some CPU cores might be locked at a random frequency with the ondemand scaling governor (both with and w/o intel_pstate). There is no such issue with the cfs scheduler on my machine.

This could be easily solved with cpupower frequency-set -g powersave and then cpupower frequency-set -g ondemand. However, since I have noticed that sometimes the lowest frequency of a CPU core might be locked at e.g. turbo frequency, it would be nice to make sure that the ondemand governor can work correctly for laptops during boot without intervention. I remember one earlier version of MuQSS/PDS had the same issue so I guess this might be related to the stats.

Another issue I have noticed is that, with nohz_full enabled for all cores except CPU0, some random CPU cores other than CPU0 might be locked at a low frequency i.e. no frequency scaling at all with the ondemand governor even under load. It seems that cfs scheduler does not have the frequency scaling issue with nohz_full. Also I can confirm via /proc/sched_debug that there is actually a task running on the frequency locked cores under load with the tt-scheduler.

By the way, thanks for your awesome scheduler! In my daily usage on my laptop, so far my system is quite smooth and I did not notice any freezes. I am using the tt-scheduler patch on top of the vanilla kernel with some other patches (most are picked from https://github.com/sirlucjan/kernel-patches/tree/master/5.15).

Heterogeneous CPU Topology Support (Intel Alder Lake)

Hi, Hamad

As a user of the Xanmod kernel with your CacULE CPU scheduler and now presently your TT CPU scheduler, I really appreciate your work. I am not 100% sure if this would be the correct place to inquire about the following, but I wanted ask you about the feasibility of integrating better and more consistent performance into your TT CPU scheduler for the newly released Intel Alder Lake chips that use heterogeneous CPU topology with their P-cores and E-cores designed for different types of tasks/workloads. Based on my understanding, much of this depends on the kernel being able to communicate with Intel's new hardware-based "Thread Director" technology, which is currently only supported in the Windows 11 scheduler (not even Windows 10 as of now). I extracted the following quote describing in a basic, high-level sense how the new Thread Director works from a Tom's Hardware overview/review article on Alder Lake that I will provide the link to at the bottom.

"This technology works by feeding the Windows 11 operating system with low-level telemetry data collected from within the processor itself, thus informing the scheduler about the state of the cores, be it power, thermal, or otherwise, and the type of workload being executed by any given thread. The Windows scheduler then uses this additional information to make real-time intelligent decisions about thread placement."

Long story short, Alder Lake performance in Linux (and Windows 10 for that matter too) is significantly poorer and far more inconsistent than Windows 11 at the moment. So I guess my questions are as follows: What are the prerequisites for implementing support for Intel's new heterogeneous CPU topology in the TT CPU scheduler to achieve better performance/parity with Windows 11 on Alder Lake chips? Correct me if I'm wrong, but my assumption would be that first, patches must be made to the mainline Linux kernel that allow the kernel to interface with Intel's new hardware-based "Thread Director". I would imagine that such patches would be at least in part Intel's responsibility to contribute. And then once these patches are implemented upstream, what are the implications for your TT CPU scheduler project? Will accommodating this new "hybrid" Intel architecture be trivial given the current state and functionality of your TT CPU scheduler? Or will exploiting the full performance of Intel's Alder Lake chips require extensive/complex work on your part?

Lastly, I am strongly considering an purchasing Intel Alder Lake chip (the i9-12900K) as an upgrade from my Intel i7-8700K for my machine in the coming weeks. Assuming I end up going thru with that, could I be of any assistance to you/your TT CPU scheduler project by providing some sort of debugging data/feedback while using the processor, perhaps by running tests/benchmarks and collecting data?

My apologies if this post seems misdirected or uninformed. I am very proficient in general Linux stuff like systems administration, configuration, Bash, Python programming, etc, but understanding the lower-level workings of the OS, such as CPU schedulers is a new horizon for me, so to speak, because I am not as familiar things of that nature. I'm just very appreciative of your work and interested in helping with your project's development once I get my hands on a new Alder Lake chip, if that would be worthwhile to you.

Many thanks for your time and consideration,

Andy

BTW, here is the link to the Tom's Hardware article, along with another link to a Phoronix article that discusses the Alder Lake performance disparity and provides some benchmarks as well:

https://www.tomshardware.com/news/intel-core-i9-12900k-and-core-i5-12600k-review-retaking-the-gaming-crown
https://www.phoronix.com/scan.php?page=article&item=alderlake-windows-linux

[request] about config

Hi, I don't know how to configure the config, using TT. I want two copies of the config, one for the game/performance and one for the responsive/latency. Thank you!

Xanmod-5.15-tt kernel freezes some time after booting.

Hi.
I use xanmod cacule tt 5.15 kernel.
I use it for the performance benifits.
Everything was fine with 5.14. but with 5.15 tt kernel, my system freezes after a minute of booting. What information do I need to share?
I can share journalctl log, my sysctl conf, or the list of packages installed.
I don't have nvidia card.
I am running elementary os.
I also use https://github.com/gautamramk/FQ-PIE-for-Linux-Kernel as shown on xanmod homepage.
Also I use schedutil cpu governor and auto-cpufreq

I will share any log you ask for, it will help you.

high-hz.patch info

Hi,

if I want to add more frequencies, do I just have to edit this?

config HZ
@@ -53,7 +90,13 @@ config HZ
 	default 100 if HZ_100
 	default 250 if HZ_250
 	default 300 if HZ_300
+	default 417 if HZ_417
+	default 833 if HZ_833
 	default 1000 if HZ_1000
+	default 1666 if HZ_1666
+	default 3333 if HZ_3333
+	default 5000 if HZ_5000
+	default 10000 if HZ_10000

in for example

config HZ
@@ -53,7 +90,13 @@ config HZ
 	default 100 if HZ_100
 	default 250 if HZ_250
 	default 300 if HZ_300
+	default 417 if HZ_417
+	default 833 if HZ_833
 	default 1000 if HZ_1000
+	default 1666 if HZ_1666
+	default 3333 if HZ_3333
+	default 5000 if HZ_5000
+	default 10000 if HZ_10000
+	default 44100 if HZ_44100
+	default 88200 if HZ_88200
+	default 176400 if HZ_176400