Achieving predictable timing and fairness through cooperative polling

Time-sensitive applications that are also CPU intensive like video games, video playback, eye-candy desktops etc. are increasingly common. These applications run on commodity operating systems that are targeted at diverse hardware, and hence they cannot assume that sufficient CPU is always available. Increasingly, these applications are designed to be adaptive. When executing multiple such applications, the operating system must not only provide good timeliness but also (optionally) allow co-ordinating their adaptations so that applications can deliver uniform fidelity. In this work, we present a starvation-free, fair, process scheduling algorithm that provides predictable and low latency execution without the use of reservations and assists adaptive time sensitive tasks with achieving consistent quality through cooperation. We combine an event-driven application model called cooperative polling with a fair-share scheduler. Cooperative polling allows sharing of timing or priority information across applications via the kernel thus providing good timeliness, and the fair-share scheduler provides fairness and full utilization. Our experiments show that cooperative polling leverages the inherent efficiency advantages of voluntary context switching versus involuntary pre-emption. In CPU saturated conditions, we show that the scheduling responsiveness of cooperative polling is five times better than a well-tuned fair-share scheduler, and orders of magnitude better than the best-effort scheduler used in the mainstream Linux kernel.

Name thesis:degree_name

Master of Science - MSc

Level thesis:degree_level

master's

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of British Columbia

Year dc:date

2007

Author dc:creator

• Sinha, Anirban

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International

Licence

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language

eng

Handle dc:identifier

http://hdl.handle.net/2429/436

OAI identifier oai:identifier

oai:circle.library.ubc.ca:2429/436