PDS 0.99j release

PDS 0.99j is released with the following changes

1. Fix missing mainline scheduler API for psi.
2. Fix fail to build on ppc64 arch. This issue was reported to PDS-mq repository 3 months ago, and I have missed the notification, very sorry about that.
3. Several code implement level optimization.
 
This is the happy new year release of PDS, include bug fixes and optimization. Thanks for your supporting PDS in 2018. PDS achieved stability, feature and performance this year.

Looking forward in the incoming 2019, there is not much pending features in my list, and after those features, PDS may very close to 1.0 release(thus it just a release number). So, sometime next year, PDS development will slow down(it will still sync with mainline release and bug fixes), I will switch to another scheduler project, hopefully ideas can be inspired from each other projects and benefit from it.

Enjoy PDS 0.99j for v4.20 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99i release

PDS 0.99i is released with the following changes

1. Sync-up with mainline 4.20 scheduler code changes.

Xmas gift comes as promised and here is the first PDS release for 4.20, just the sync-up code changes added. The code has been run since -rc7 for about a week. So there should be no surprise in it, :D
But if you are seeking for surprise, well, there will be optimization code changes for the next release before the new year!

Enjoy PDS 0.99i for v4.20 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99h release

PDS 0.99h is released with the following changes

1. Fix cpu hot-plug Oops. Thanks @pf's report(again).
2. Rework time_slice_expired().  Simplified and unified task deadline reflash

This should be the last PDS release for 4.19 kernel. Other code implement level optimization are pending for 4.20. Hopefully kernel 4.20 and PDS for 4.20 could be on time as Xmas gift.

Enjoy PDS 0.99h for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

EDIT: Pls also checkout the emergency fix at  https://gitlab.com/alfredchen/linux-pds/commit/fae1a3c0fbe60b7edf6d8aac6b838520da68f9e4

4.20 is coming out soon, so there is no plan to dump up version for 4.19 again.

PDS 0.99g release

PDS 0.99g is released with the following changes

1. [Sync] c5511d03ec09 sched/smt: Make sched_smt_present track topology. A lot of changes from mainline in v4.19.7 and the incoming 4.20 kernel release.
2. Fix smt boot up crash. This fix a bug in 0.99f PDS release(not related to mainline code changes), thanks @pf's report and help for debugging.

This is a sync-up and bug-fix release.

Enjoy PDS 0.99g for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99f release

PDS 0.99f is released with the following changes

1. Remove load balance code from scheduler_tick(). Based on recent code change and testing, looks like there is no need to check load balance in scheduler_tick() any more.
2. Default 4ms rr_interal. Trade off performance for interactivity improvement.
3. Rework sibling group balance. Reduce the overhead in sibling group balance by rework the code path.

This release includes balance code rework, and will be the biggest change in this kernel cycle. Please give it a try and feedback will be welcome.

Enjoy PDS 0.99f for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99e release

PDS 0.99e is released with the following changes

1. Fix sched_fork() time slice fairness. Simplify the code and fairness first.
2. Refine take_other_rq_task() code path.
3. Remove cpumask_weight() in best_mask_cpu().

This release includes minor changes. It's good to have such small change release before the big one.

Enjoy PDS 0.99e for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99d release

PDS 0.99d is released with the following changes

1. Rework SCHED_ISO support. Based on the limitation of the user land tools, for example, schedtool only support ISO tasks with priority specified, there is not big change for ISO. But this rework remove the "iso_cpu" kernel parameter. The logic behind this is, if your ISO task breaks the system, this parameter doesn't help(much), and if your ISO task runs well, you don't need to adjust this parameter. So, to keep the code simple, it has been removed.
2. UP compilation fix. Thanks jwh7's reporting. For the incoming release, I will do at least one UP compilation per kernel release cycle to prevent UP compilation breaks again.

This release includes the rest part of task policy support review in PDS. Now I am working on overhead cutting by cleaning up/reworking some balance code path. The next PDS release will be about two weeks later.

Enjoy PDS 0.99d for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99c release

PDS 0.99c is released with the following changes

1. Fix and sync-up reset on fork handling. In some cases, reset on fork will not work proper. This fixed the issue.
2. Unified time slice for FIFO tasks. Now every task(except for the idle) has the rr interval as time slice.
3. Handle SCHED_BATCH as SCHED_IDLE. Consider the fact that BATCH tasks is more like the IDLE policy task but compete cpu with NORMAL tasks. This commit handle BATCH tasks as IDLE policy and leave NORMAL policy tasks at NORMAL priority alone.
4. Enable SCHED_DEADLINE support. Mainline has SCHED_DEADLINE policy and PDS has to support it, no matter in kernel space or user space. PDS support it by squash it as priority 1 FIFO task.
5.  Optimize ISO branch in normal_prio(). An minor optimization in normal_prio().

This release includes the first part of task policy support review in PDS, and plus some minor optimization. The rest parts of the review, including the rework of ISO policy will be out in next release.

Enjoy PDS 0.99c for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.99b release

PDS 0.99b is released with the following changes

1. Sync with mainline 4.19 scheduler changes.

This is the first PDS release for 4.19, just sync-up changes.

Enjoy PDS 0.99b for v4.19 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PS, from now on, the linux-pds git will contains PDS only commits beside the mainline codes, while will help you to get the pure PDS commits a little easier.

PDS 0.99a release

PDS 0.99a is released with the following changes

1. Fix sugov_kthread_create fail to set policy.(Thanks jwh7's reporting and testing)
2. Fix task burst fairness issue. Thanks Holger reporting video playback issue, which remind me my mpv lost frame when running "git checkout", that burst creating a lot "git" tasks, I used to believe it is high io usage issue and ignored it. I'm not sure if this commit fix Holger's issue or not, but hopefully it will help.

This is another bug fix release. For #1, current fix is not perfect. I'll leave it to next kernel release cycle to decide how PDS handling mainline existed scheduler policies.

Enjoy PDS 0.99a for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.98z release

PDS 0.98z is released with the following changes

1. Fix and improvement in the previous release.
2. Re-mapping SCHED_DEADLINE to SCHED_FIFO, which fix cpufreq_schedutil create kernel thread as SCHED_DEADLINE(thanks jwh7 for reporting)

This is a bug fix release. I'd like to let PDS stable for awhile in the incoming releases.

Enjoy PDS 0.98z for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
All-in-one patch is available too.

PDS 0.98y release

PDS 0.98y is released with the following changes

1. Enable SMT_NICE scheduling.  Below is the commit msg of this commit
"""
    Firstly, look at the kernel compilation test result without(-j4) and with SMT(-j8).
   
    Without SMT(-j4)        With SMT(-j8)
    4m30s                   3m40s
   
    In the scenario IDLE and NORMAL(BATCH,ISO,RT) policy tasks run together,
    IDLE tasks can be supressed to run on SMT sibling cpus and let the other
    policy tasks run without SMT. In this way, tasks with other policy will
    take high priority and completed sooner than run with IDLE tasks on SMT
    sibling cpus. This is called the SMT_NICE scheduling.
   
    Below is the test results of SMT_NICE disabled and SMT_NICE enabled.
   
                    SMT_NICE disabled       SMT_NICE enabled
    NORMAL(-j4)     6m56s                   5m3s
    IDLE(-j4)       7m10s                   8m30s
"""

Hopefully this commit can help with who has IDLE task running in the backgroup to improve the fontgroup task interactivity.

Enjoy PDS 0.98y for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds.
All-in-one patch is available too.

PDS 0.98x release

PDS 0.98x is released with the following changes

1. Add cgroup stub. Thanks Oleksandr Natalenko for this porting, I don't have to test cgroup related stuff myselft, hopefully the stub make cgroup related application happy.
2. Revert "Rework rq->sl_header data structure". It turns out that the rq-sl_header data structure change makes some system unstable. So it is reverted, I'll try to bring it back after SMT_NICE feature code are published.

Hopefully this is the last release before SMT_NICE feature code submit.

Enjoy PDS 0.98x for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds.
All-in-one patch is available too.

PDS 0.98w release

PDS 0.98w is released with the following changes

1. Rework rq->sl_header data structure. Now, it is a pointer to the idle->sl_node. This unify sl_node -> task conversion.
2. Policy based task_preemptible_rq(). IDLE/BATCH/NORMAL tasks now has their own strategy in the ttwu code path.
3. Rewrok take_other_rq_task() code path. This code change is prepare for the incoming SM_NICE feature.
4. Try to take tasks from other rq when prio downgrade. Now when rq is going to switch to a low priority task than previous, it will look up if there is higher priority tasks from other run queues.
5. Introduce sched_rq_pending_masks. This replace the sched_rq_nr_running_masks, and provide better filter mask for take_other_rq_task code path.
5. Change per cpu cpu_has_smt_sibling to sched_sibling_cpu. Another preparation for SMT_NICE.
6. Fix UP/non-SMT compilation warning.

#1 and #2 are the new code changes. I personally like the #1, which actually implement the idle task as the tail of the task link in the rq, just like the old school book said. Other changes are preparation for SMT_NICE in the next release.

Enjoy PDS 0.98w for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds.
All-in-one patch is available too.

PDS 0.98v release

PDS 0.98v is released with the following changes

1. Some code refine.
2. Make Batch/Idle tasks less preemptible vs Normal tasks.

With #2, Normal policy tasks should be more responsible when run with Batch/Idle policy tasks. Slight regression has been found for Batch/Idle policy task sanity tests, but they are the design intention of #2.

SMT_NICE will get some love in this kernel release. There will be some SMT_NICE pre-required code changes in next PDS release next week.

Enjoy PDS 0.98v for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds.
All-in-one patch is available too.

PDS 0.98u release

PDS 0.98u is released with the following changes

1. Sync up mainline scheduler changes in 4.18

This is the first PDS-mq release for kernel 4.18. As usual, it just a sync-up release, it all goes well. The next PDS-mq release will be arrived at the weekend, 10+ commits are pending.

Enjoy PDS 0.98u for v4.18 kernel, :)

Code are available at https://gitlab.com/alfredchen/linux-pds
(Say good-bye to github)

All-in-one patch is available too.

Edit: Fix all-in-one patch link.

PDS 0.98t release

PDS 0.98t is released with the following changes

1. Rework pds_load_balance() based on current implementation. It's the main feature of this release.
2. Minor optimization in task_preemptible_rq().

This is the last release for 4.17, with the rework of balance code path as promise. The sanity test shows there are minor improvement over all workload due to balance overhead cutting. So far, I'd like to call it for the balance overhead cutting work and move on for next main line sync up and investigation of other potential improvement.

Enjoy PDS 0.98t for v4.17 kernel, :)

Code are available at
https://github.com/cchalpha/linux-gc/commits/linux-4.17.y-pds
and also
https://gitlab.com/alfredchen/linux-pds

All-in-one patch is available too.

PS: Here is the updated patch for v4.17.12+ kernel

https://gitlab.com/alfredchen/PDS-mq/raw/master/4.17/v4.17.12+_pds098t.patch
 

PDS 0.98s release

PDS 0.98s is released with the following changes

1. Fix compilation issue on raspberry pi.
2. Minor rework and optimization on balance code path.
3. Fix wrong nr_max_tries in migrate_pending_tasks.

This is mainly a bug fix and minor optimization release for 4.17. The rework of balance code doesn't go well, it actually make more overhead than current implement. Another rework which based on current implement is still on going, hopefully be included in next release.

Enjoy PDS 0.98s for v4.17 kernel, :)

Code are available at
https://github.com/cchalpha/linux-gc/commits/linux-4.17.y-pds
and also
https://gitlab.com/alfredchen/linux-pds

All-in-one patch is available too.

PDS 0.98r release

PDS 0.98r is released with the following changes

1. Fix compilation error when build CFS.
2. Optimization here and there.
3. Pick one more remaining sync-up from mainline.

This is the second PDS release for 4.17. It's mainly for bug fix, continue sync-up pick-up and minor optimization. After this, I'm reworking the balance, hopefully helping reducing the overhead.

Enjoy PDS 0.98r for v4.17 kernel, :)

Code are available at
https://github.com/cchalpha/linux-gc/commits/linux-4.17.y-pds
and also
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.17.y-pds (Will be deprecated soon)

All-in-one patch is available too.(Now the link is from github PDS-mq repository, although MS has bought github which make uncertain future of github, but moving from bitbucket is certain, all-in-one patch will not be uploaded to download page of bitbucket repository from this release)

PDS 0.98q release

PDS 0.98q is released with the following changes

1.Sync up with 4.17 mainline scheduler changes.

This is the first PDS release in 4.17. Because there are head files related code changes from mainline, so there may be chances compilation doesn't work under given combination of kernel config(scheduler related), please report back when it happens. Two "last minute" scheduler changes haven't been pick up from mainline, need more time to see how it apply upon PDS, because it happens on critical code path.

Known issue, but not PDS related, chromebook pixel failed to suspend(same on mainline CFS).

Enjoy PDS 0.98q for v4.17 kernel, :)

Code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.17.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.17.y-pds

All-in-one patch is available too.

PDS 0.98p release

PDS 0.98p is released with the following changes

1. Minor code optimization here and there.
2. Balance optimization. This fix regression in 098n when workload % < core number.
3. 32ms balance interval.

This is the last PDS release in 4.16 kernel, thanks for the benchmark testing by Predo and Manuel, a regression in 098n release is identified and fix. In this release, the balance interval also increase to 32ms, this will help with throughput, let's test this setting before there is new way to do balance later(maybe next kernel release).

Enjoy PDS 0.98p for v4.16 kernel, :)

Code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.16.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.16.y-pds

All-in-one patch is available too.


PS, please apply the below patch if you don't have SMT enabled in kernel config, or if you don't know what's in your kernel config, you'd better have it. Thanks manuel for reporting.

 https://bitbucket.org/alfredchen/linux-gc/downloads/v4.16_pda098p_non_smt_fix.patch

PDS 0.98o release

PDS 0.98o is released with the following changes

1. Minor code cleanup and optimization here and there.
2. Fix a bug in get_nohz_timer_target().

Although there is no improvement can be observed in sanity tests, but there should be no regression too. Code cleanup and optimization will be continued in next release(in two or three weeks) then some features will add in next kernel release.

Enjoy PDS 0.98o for v4.16 kernel, :)

Code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.16.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.16.y-pds

All-in-one patch is available too.

PDS 0.98n release

PDS 0.98n is released with the following changes

1. Migrate max SCHED_RQ_NR_MIGRATION tasks to empty rq at a time. This will help with burst situation.
2. Code cleanup.
3. Optimize scheduler_tick(), pds_sg_balance() and pds_load_balance(). This helps with overhead reduction.

With the help of optimization in this release, improvement can be observed in sanity tests(for all kinds of workload). PS, there will be no cachehot patch coming, as there is  overhead cutting in ttwu code path in 0.98m, and leave no improvement space for the cachehot patch.
Enjoy PDS 0.98n for v4.16 kernel, :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.16.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.16.y-pds

 All-in-one patch is available too.

PDS 0.98m release

PDS 0.98m is released with the following changes

1. Unify 32/64bits handing in task_preemptible_rq(). This makes 32/64bits system has the same code base(again). Personally, I'd love to see my raspberry pi running same scheduler code with my laptop.
2. Remove cpu scaling interfaces. Based on recent testing, there is no regression to drop these interfaces. Removing these also cut of overhead.
3. Accurate preempt for RT tasks. Before this release, RT tasks wake up on 32bits system is not fully based on their priority(kind of a bug).
4. Refines and code clean-up in several functions.
5. Fix some wrong likely/unlikely usage in PDS code.

These changes are inspired by the experimental cachehot patch. Aim to reduce the overhead in the existed code path and make the design simple. Another obvious change is in the patch size, -5KB!(No one cares, right?) For the sanity tests, there is slight improvement, no regression was found so far.

Enjoy PDS 0.98m for v4.16 kernel, :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.16.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.16.y-pds

 All-in-one patch is available too.

PS, PDS-mq patch repository is created, which will be used to category all pds-mq patch since 4. 13. I am thinking about migrate the source code/patch repository from bitbucket to github, because bitbucket used to have limit repository size(2G), but it looks like that they remove such limitation recently, what about your thought?

PDS 0.98l release

PDS 0.98l is released with the following changes

1. Sync up with mainline 4.16 scheduler code changes.

This is just a sync up release for 4.16 kernel. If all goes well, there will be another release this weekend with some "solid" PDS feature code changes.

Enjoy PDS 0.98l for v4.16 kernel, :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.16.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.16.y-pds

 All-in-one patch is available too.

CacheHot experimental patch for PDS

Overview


In modern computer system design, cpu cache plays an important rule in performance but it "becomes a resource which is transparently used and administered by the processors.", which make it like a "black whole" and hard to be measured, especially from per task aspect in the kernel point of view. Despite of the difficulty and limitation, it is worthy to give it a shot based on recent test result of a prototype cache hot patch for PDS scheduler.

The Cache-Hot prototype patch here is trying to determine a task is cache hot or not when it is waking up, then choose different method to select a cpu to run on based on this cache hot information. If the task is cache hot, then it can use the accurate but complicated method to choose a cpu be affinity with the cache which the task resides in. If the task is cache cool, then it can simply choose any cpu it can run on. In this way, the overhead of selecting a cpu to run on is reduced.

The test result of kernel compilation result can be download from here. It shows that overhead is reduced in heavy workload, and the overhead cutting should be able to been seem in light workload if advance the measure model in the feature.

Limitation

1. The prefer setting/formula in this patch may just work for x86 arch.
2. The prefer setting/formula in this patch may just work for certain workload(linux kernel compilation)

Consider these limitations and this version is still a prototype patch, it will be better not official put into PDS and provide it as an experimental patch to try it out.

Try out the patch

The patch can be download from here, apply it upon pds098k.

Then adjust the SCHED_CACHE_HOT_SWITCHES_TH in pds.c to the reference value in the below formula according to your cpu topology

SCHED_CACHE_HOT_SWITCHES_TH = 8  * (LLC_SIZE / 3) * (1.8 / CPU_SPEED) * (4 / NUM_CPUS)

LLC_SIZE is last level cache size in MB
CPU_SPEED is the cpu speed in GHz
NUM_CPUS is the numbers of logical cpu(HT counts in)

Feel free to try other value than the reference one, and on different kind of workload. Your feedback will be welcome.

What's next

Don't worry about too much of the SCHED_CACHE_HOT_SWITCHES_TH, it's just a simple measurement in the prototype. Another model is working in progress and will be available in next version.

PDS 0.98k release

PDS 0.98k is released with the following changes

1. Several code cleanup changes.

This is just a code cleanup release for 4.15 kernel, before the incoming feature release(hopefully in 2 or 3 weeks).

Enjoy PDS 0.98k for v4.15 kernel, and "Happy CNY", :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.15.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.15.y-pds

 All-in-one patch is available too.

PDS 0.98j release （respinned）

PDS 0.98j is released with the following changes

1. Sync up with mainline 4.15 scheduler code changes. (Updated to sync with official 4.15 mainline)

This is just a sync up release for 4.15 kernel. I will be on a trip and may not able to release new PDS code for kernel 4.15 when it comes out next week. So it is released earlier this week, the sync up changes should be completed if there is no last minute scheduler changes from mainline. Git repositories will be updated later.

Enjoy PDS 0.98j for v4.15 kernel, :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.15.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.15.y-pds

 All-in-one patch is available too.

PDS 0.98i release

PDS 0.98i is released with the following changes


1. Revert "pds: Remove yield support."
2. Set default yeild_type to 1 and remove yield_to() support.
3. 16ms dispersed balance interval.

This is the last release on 4.14 kernel and the first release in 2018, which brings back the yield_type support, users needs to adjust the value to their own requirement, now default is 1. And there is balance overhead cut-off feature which will help in all kinds of workload.

Enjoy PDS 0.98i for v4.14 kernel, :)

code are available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.14.y-pds
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.14.y-pds

 All-in-one patch is available too.