Friday, September 11, 2015

Consider cache in task scheduling Part 1

Recently, in the past two release, I am working on the idea taking task caching states into account in scheduler code and implement the first part in later commits on 4.0 and  4.1 release. Now it's in 4.2 and I am working on the second part of code, so it's time to give it a brief introduction.

Till now, the cpu cache is still like a "back-hole" of hardware piece from the view of software it impacts computer  performance greatly, so it's still worthy to emulate task caching usage even it's not 100% accurate. Here is the factors that should be considered
1. Cache size of the cpu

  • Larger cache size gives larger hardware capability to cache a task. Talking about the cache size, we specially means the LLC(Last Level Cache) size, which is usual has the largest amount of cache size among all levels of cache and shared with multi cpu cores/smts.

2. How many tasks have been switched and their caching status and memory footprint after the given task has been switched off the cpu. 

  • More tasks have been switched, more likely the given task's caching data will be flushed away.
  • Switch to a task already been cached, will likely less impact to other task's cache data.
  • Switch to a task with more memory footprint will likely impact other task's cache data than the task with less memory footprint.
3. How long the given task has been switched off the cpu

And these factors are restrict each others. The commit
ed20056 bfs: vrq: [2/2] scost for task caching v0.7
focuses on the 2nd factor above and introduce switch cost value in each run queue to emulate the impact of task switching to the cache data on the cpu. The implement is in function  update_rq_switch().

And when a task switches off a run queue, it records run queue's current switch cost value into it's cache_scost of the task structure. This information combines the cpu which the task run on and the time being switched off(not consider yet) are the caching property of the task, and can be used to emulate the task is cache hot or cool late after.

The algorithm is very simple as just one factor is taken into account in this commit. Whether the task is cache hot or cool is compare the delta of scost value current the rq has and the one when task switched off to a given threshold. The given threshold is now a hard-coded value which optimized for my test-bed system. And the threshold will be adjusted when other factors are taken into account.

Currently, the task caching proprieties are just used to replace the sticky task implementation in original BFS. And for sure it will be used in further development. Talking about the sticky task replacement implementation using task caching, the codes are simpler now
1. run queue doesn't need to reference to it's sticky task, and multiple tasks from a run queue can be "sticky"(caching) at the same time.
2. run queue doesn't need to trace sticky task's sticky state, now the cached state of the task is "auto" updated during task selection(in the earliest_deadline_task() function).


With this commit and optimize the cache scost threshold for my test-bed system, the sanity test shows better performance in all kind of workload.

Depends on what the threshold is chosen, the task may be waiting for the cache hot cpu to pick it up in grq longer than original BFS "sticky task" design. This will impact task's response time and an improvement is planned in further development.

... to be continue (Part 2)


  1. Nice !

    I wonder how much of an performance improvement or latency cut-down this will provide ...

    1. The commit already in 4.1 vrq, you can check the sanity test result at for performance improvement.