Project Description

Linux has seen tremendous growth as a server operating system and has been deployed in the enterprise for Web, file and print serving. Increased demand in such environments can often be scaled through clustering solutions. We expect that Linux will also move towards more demanding enterprise applications such as databases and e-commerce business. To scale in these applications the Linux kernel must scale well on SMP based systems. We are examining the Linux kernel to see whether existing resource limitations, algorithms, and data structures are sufficient to support the increased number of cpus and load on these systems. Fixed resource limits, such as the max number of processes, files and devices can impose a hard limit on the application deployment. Datastructures and algorithms, while suitable for small load/cpus might be the source of excessive lock contention and increased lock wait times ultimately limiting system scalability.

Our current work focuses on improving the Linux scheduler scalability. We have shown that under heavy load, increased system activity and/or increased CPU numbers the current scheduler exhibits poor scalability due to high lock contention on the shared runqueue lock. We implemented more traditional priority level scheduler still centered around a single lock, reducing the lock hold times. This approach improves scalability with respect to an increase in the number of runnable tasks. However, due to the shared lock, lock contention is not substantially reduced and scalability is still limited. We prototyped a new Linux scheduler MQ that replaces the single queue, single lock design with a multi-queue design. MQ reduces lock hold times and allows parallel scheduler execution on different CPUs. As a result, lock contention is substantially reduced and scalability is significantly improved for medium to large scale SMPs. For TCP-H based benchmarks, we have seen a reduction of lock contention from 56 percent to 11 percent.

This project is run as an open source project on the SourceForge Linux Scalability website where we post code and results and interact with external peers.

Journal Publications

• "Enhancing Linux Scheduler Scalability," M. Kravetz, H. Franke, S. Nagar, R. Ravindran, in Proceedings of the Ottawa Linux Symposium, July 2001, Ottawa, Canada.