Abstract

In this paper, we propose and evaluate the experimental implementation of cache coloring for task structures on the Linux kernel 2.4.x. We analyzed the behavior of the scheduler from the viewpoint of memory architecture and found that severe cache conflicts occur in a specific cache line. To solve this issue, we applied cache coloring scheme to task structures. Until now, task structures in Linux kernel could not be moved freely in main memory. We noticed, however, that a small modification can enable the coloring. Under heavy workloads, this technique can dramatically reduce cache misses while traversing the run queue that contains a lot of runnable processes. For the evaluation, we used 4-way and 8-way IA server machines. Web server execution and Chat micro benchmark of scheduler intensive benchmarks were used for the measurement. The experimental results showed that the Web server performance achieves a maximum of 23.3% improvement compared to the standard kernel. In the Chat micro benchmark, the message throughput improves a maximum of 89.6% compared to the standard kernel. Furthermore, our coloring technique gives better scalability as the number of processors increases on a SMP system since the lock contention which protects the run queue is reduced.