VRQ 0.89c released

VRQ 0.89c was released with

1. Introduce sched_rq_queued_masks, which made the run queue looking for higher policy queued task from other run queue firstly.
2. Fix unexpected design intention when creating new tasks and fix a hang issue enabling this new code.

I have decided to make a last-minute callback of planned task policy fairness feature commit, as it introduced a dead-lock scenario, by fixing this dead-lock, it leads to other side effects. It may need different solution for task policy fairness.

The cause of the cpu c-state issue has been found, it's the cpufreq_trigger callback.  It seems it also related to schedutil and intel cpufreq governor issues. It's time to solve it once for all.

Above two are in the to-do list in 0.89d. Although there are less commits in these release, but the sanity test also shows visible improvement in all kinds of workload.

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

all-in-one patch also available.

Enjoy it! :)

VRQ 0.89b released

VRQ 0.89b is released with

1. Fix low workload regression comparing to previous vrq release by not trying to pick tasks from other run queue when cpu is scaling.
2. Follow cpu affinity order when pick tasks from other run queue.
3. Fix long existed wrong run queue scaling value when run on performance governor or exit from dynamic governor.

With all above changes, this release show better sanity performance than any other previous vrq releases. Next release will be focus on task policy fairness.

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

all-in-one patch also available.

Enjoy it, :)

VRQ 0.89a released

VRQ 0.89a is released which mainly fix the imbalance cpu usage issue. Now all cpu can run at 100%, and no issue found in daily usage.

Also, there are other code changes/refines in scheduler core, but I afraid it is not so visible.

For this release, sanity kernel compilation tests also show there is noticeable improvement comparing the previous vrq release at 100%~300% workload. At 50% workload, a small regression is found in the 4 cores system, a debug patch already gets it back to the same level of the previous vrq, but I'd like it to be well test on other systems before officially commit it.

I am happy with the sanity test results, it show this new release of vrq already better than previous release, and there are several performance improvement idea not yet implemented.

Have fun with this release and expect the next. :)

BR Alfred

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

VRQ 0.89 test branch released

VRQ at its beginning is to reduce grq(global run queue) lock access as much as possible. In previous release of VRQ, it was trying to get rid of grq lock access hot spots and create grq lock free code path. With the recently introduced skip list queue data structure, grq could be wiped out completely, and it will be happened in this and the incoming release of VRQ.

The immediately question will be whether it is base on MuQSS by CK? Answer is NO. It actually divided from an early commit of 4.8 -vrq branch. The reasons why not based on MuQSS are
1. Different skip list implementation.
2. There are still many sync-up and feature commits need to be picked up from previous -vrq branch.
3. Different rules to be followed and different routine implementation.
4. Codes are more controlable when work on a familiar code base.

So here comes this new release of VRQ with the below changes

* Totally remove the global rq structure, per cpu run queue has its own skip list to hold the running tasks on this run queue and be accessed by rq->lock(which is existed in previous version of VRQ).

* Update task_access_lock/unlock(...) strategy for grq/rq data structure changes.

* Update set_task_cpu() logic and usage as it has to follow the principle rules, 1. don't use set_task_cpu() for blocked tasks, let ttwu to solve out. 2. Setting task's cpu means to change the cpu/rq which task resided on.

* Update set_cups_allowed_ptr() logic and usage when task is queued or running on wrong cpu.

* Update cpu hot-plug api implementation as tasks now reside on per cpu run queue instead of a global run queue. And makes cpu on/off-line and suspend/resume work more reliable.

* Remove unused code such as sticky task, because by putting prev task to per rq skip list is natural stick/cache.

* more to be listed.

It's not done yet, so this is called release 0.89, the major known issue is the imbalanced cpu loading, on two cpus system, most system workload will be on cpu0. On a quad cores system, it becomes better but some cores are still not running at 100% cpu usage. This is because a very simple version of __schedule() and TTWU() is using in this release, not fantastic feature is deployed yet.

With the above known issue/limitation, it's not suitable to use this release in a production environment. This release is aim to demonstration the foundation routine changes adapting to per cpu run queue and verify no major system broken occurs. Then in next release(0.9), fix for imbalance cpu loading and scheduler performance improvement could be added.

You are encouraged to test this VRQ release, don't looking at performance, it sucks due to the known limitation. But please looking for miss behaviors of system or suspected kernel log comparing to previous VRQ release.

Code is available at
https://bitbucket.org/alfredchen/linux-gc/commits/branch/linux-4.8.y-test
and also
https://github.com/cchalpha/linux-gc/commits/linux-4.8.y-test

Enjoy it.

BR Alfred

VRQ patch v4.8.1-vrq0 released

VRQ patch v4.8.1-vrq0 is released, all-in-one patch is available. linux-4.8.y-vrq branch has been pushed to bitbucket and github.

What's new
1. Sync up with 4.8 mainline scheduler code changes.
2. Introduced skip list as queue data structure. For detail information about the implementation of skip list, please reference to my previous posts(#1, #2,  #3) and also the original skip list design idea from CK.
3. Based on the feedback of users, sticky and caching features are turned off for NORMAL policy tasks, which give max interactivity experience for desktop&gaming usage(commit is here). Further tuning may still be needed, but it looks that it's the best choice out of the 4 debug patches, based on the feedback information so far.
4. Workaround fix for a boot-up issue caused by preempt task solution.
5. A v2 fix for smp_processor_id() preempt code usage in smpboot_thread_fn().


PS:
The policy based sticky/caching feature is almost done, unlike the interactivity switcher in original BFS, this feature provide throughput and interactivity at the same time. "At the same time" not means a task can both throughput and interactivity all together, it means that throughput tasks and interactivity tasks can run all together. Just assign the right policy to the tasks.


Enjoy VRQ for 4.8 kernel, :)

BR Alfred

About Skip List

I read one post about skip list today which link to this web(http://ticki.github.io/blog/skip-lists-done-right/), in which some very useful information can be found.

The "O(1) level generation" is just what I used in my new skiplist implement in BFS, though I never read similar before.

BR Alfred

Skip list + VRQ for 4.7

Based on the new implementation of skip list, I am adding -VRQ commits upon it. All commits will be pushed in linux-4.7.y-sl branch. Unlike previous -vrq release, I am releasing additional checkpoint tags, so users can use these tags to check their issue and narrow code changes which introducing the issue.

Checkpoint tags:
1. 4.7_0472_sl_baseline and all in one patch.

    This is the start point of all the work, all commits are in About skip list in BFS.

2. 4.7_0472_sl_new and all in one patch.

    New implementation of skip list, please check the post at New implementation of skip list for BFS.

3. 4.7_0472_sl_new_sync and all in one patch.
    Include all Sync-up commits from release to release which not yet be picked up by original BFS.

4. 4.7_0472_sl_new_gc and all in one patch.
    This patch include all former -gc commits, most important one is the "
 Full cpumask based and LLC sensitive cpu selection" commit, which help with performance under low workload.

5. 4.7_0472_sl_new_vrq and all in one patch.
    This is not the same as VRQ3 patch, but only include two major feature "VRQ solution" and "preempt task solution". I want tag a checkpoint here before the latest stick/cache code changes as it is not yet finalized.

6. 4.7_0472_sl_new_vrq_full and all in one patch.
    Include all -vrq features upto VRQ3 in 4.7.

...to be continued

BR Alfred