Trustworthy Platforms & Systems

Multi-core Schedulers

Multi-core Schedulers

Designing a scheduler that can be work-conserving and applicable in the real world.

Operating systems often leave idle cores even though work is ready to be scheduled. This leads to avoidable wastage of machine resources and consequent loss of performance and power. Although significant work has been done to optimize operating systems by developing verification methods, there are still many bottlenecks that hinder performance. Taking cognizance of these problems, Professor Willy Zwaenepoel and the research team at EPFL’s Operating Systems Laboratory are developing a methodology for designing, implementing, and verifying properties of multi-core schedulers, such as liveness (freedom from starvation) or work-conversation (no core is left idle when work is ready to be scheduled).

The focus of the study is on designing a scheduler that can be work-conserving and applicable in the real world, for instance as part of the Linux kernel. This is a critical need because the default Linux scheduler (CFS) has been proven to leave cores idle while threads are waiting in runqueues. This has hampered performance in the context of scientific applications, with up to 25% decrease in throughput for realistic database workloads.

The work also considers another challenge in proving performance properties of multi-core schedulers: uncoordinated concurrent operations. If we consider CFS, two cores might simultaneously attempt to steal work from a third core. Consequently, one of the two cores might not succeed because the third core doesn’t have enough threads. In a paper prepared in collaboration with researchers from other universities, Baptiste Lepers and Willy Zwaenepoel advocate a process that allows cores to make “optimistic” decisions by observing the state of other cores. This is a much better option than resorting to locks, which have a direct impact on performance.

The objective of the study is to develop an efficient scheduler design that can simplify proving effort and yield a level of performance comparable to that of current schedulers.

Suggested readings

https://labos.epfl.ch/page-152347-en.html
https://infoscience.epfl.ch/record/227943/files/main.pdf
https://www.archives-ouvertes.fr/hal-01556597/