We showed in this paper that the current Linux kernel potentially has scalability problem due to severe cache line conflicts from the placement of task structures in physical memory. We observed memory bus transactions on real SMP server systems and confirmed that large number of cache misses occur in the scheduler under heavy workload.
To address this issue, we proposed and implemented the cache coloring for a task structure. The evaluation result of this implementation demonstrates that the cache miss ratio while traversing the run queue is significantly reduced and the scheduling speed is enhanced. In WebBench, the web transaction performance on the coloring kernel achieved maximum of 42.3% improvement on 4-way Pentium Pro 200MHz system and 23.3% improvement on 8-way Pentium III Xeon 550MHz system. In Chat benchmark, the message throughput on the coloring kernel showed a maximum of 89.6% improvement on 8-way Pentium III system.
Reduction of cache misses can lead to decreasing run queue traversal time. On a SMP system this results in decreasing the lock hold time and lock contention. This is the effect of coloring on a large scale SMP machine. We verified these effects on an 8-way system, and found that the coloring scheme achieves better scalability than the standard kernel.
On the other hand, there is potential disadvantage caused by coloring: useful data are replaced on colored lines. To avoid this problem, we provided a simple model to decide the appropriate number of colorings, and verified the model with the bus transactions data observed on a real system.
As the gap between processor and memory speed grows wider the cache conflict issue caused by the current scheduler becomes more serious. Our coloring scheme is an essential technique for ameliorating this issue. The coloring scheme patch is contributed to the open source community, and is freely available for use and modification. The current patch can be downloaded from https://www.labs.fujitsu.com/en/techinfo/linux/.