Go to  Advanced Search

Achieving predictable timing and fairness through cooperative polling

Show full item record

Files in this item

Files Size Format Description   View
ubc_2008_spring_sinha_anirban.pdf 5.125Mb Adobe Portable Document Format   View/Open
Title: Achieving predictable timing and fairness through cooperative polling
Author: Sinha, Anirban
Degree: Master of Science - MSc
Program: Computer Science
Copyright Date: 2007
Subject Keywords process scheduling algorithm;cooperative polling
Issue Date: 2008-02-21
Publisher University of British Columbia
Abstract: 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.
Affiliation: Science, Faculty of
URI: http://hdl.handle.net/2429/436
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893