{"id":90982,"date":"2019-03-28T12:27:55","date_gmt":"2019-03-28T12:27:55","guid":{"rendered":"http:\/\/www.sickgaming.net\/blog\/2019\/03\/28\/can-better-task-stealing-make-linux-faster\/"},"modified":"2019-03-28T12:27:55","modified_gmt":"2019-03-28T12:27:55","slug":"can-better-task-stealing-make-linux-faster","status":"publish","type":"post","link":"https:\/\/sickgaming.net\/blog\/2019\/03\/28\/can-better-task-stealing-make-linux-faster\/","title":{"rendered":"Can Better Task Stealing Make Linux Faster?"},"content":{"rendered":"

Oracle Linux kernel developer Steve Sistare contributes this discussion on kernel scheduler improvements.<\/em><\/p>\n

Load balancing via scalable task stealing<\/h2>\n

The Linux task scheduler balances load across a system by pushing waking tasks to idle CPUs, and by pulling tasks from busy CPUs when a CPU becomes idle. Efficient scaling is a challenge on both the push and pull sides on large systems. For pulls, the scheduler searches all CPUs in successively larger domains until an overloaded CPU is found, and pulls a task from the busiest group. This is very expensive, costing 10’s to 100’s of microseconds on large systems, so search time is limited by the average idle time, and some domains are not searched. Balance is not always achieved, and idle CPUs go unused.<\/p>\n

I have implemented an alternate mechanism that is invoked after the existing search in idle_balance() limits itself and finds nothing. I maintain a bitmap of overloaded CPUs, where a CPU sets its bit when its runnable CFS task count exceeds 1. The bitmap is sparse, with a limited number of significant bits per cacheline. This reduces cache contention when many threads concurrently set, clear, and visit elements. There is a bitmap per last-level cache. When a CPU becomes idle, it searches the bitmap to find the first overloaded CPU with a migratable task, and steals it. This simple stealing yields a higher CPU utilization than idle_balance() alone, because the search is cheap, costing 1 to 2 microseconds, so it may be called every time the CPU is about to go idle. Stealing does not offload the globally busiest queue, but it is much better than running nothing at all.<\/p>\n

Results<\/h2>\n

Stealing improves utilization with only a modest CPU overhead in scheduler code. In the following experiment, hackbench is run with varying numbers of groups (40 tasks per group), and the delta in \/proc\/schedstat is shown for each run, averaged per CPU, augmented with these non-standard stats:<\/p>\n