Operating System Support
for
Quality of Service
Eoin Andrew Hyden
Wolfson College
University of Cambridge
A dissertation submitted for the degree of
Doctor of Philosophy
February, 1994

Abstract
The deployment of high speed, multiservice networks within the local area has meant
that it has become possible to deliver continuous media data to a general purpose
workstation. This, in conjunction with the increasing speed of modern microproces­
sors, means that it is now possible to write application programs which manipulate
continuous media in real­time. Unfortunately, current operating systems do not
provide the resource management facilities which are required to ensure the timely
execution of such applications.
This dissertation presents a flexible resource management paradigm, based on the
notion of Quality of Service, with which it is possible to provide the scheduling
support required by continuous media applications. The mechanisms which are
required within an operating system to support this paradigm are described, and
the design and implementation of a prototypical kernel which implements them is
presented.
It is shown that, by augmenting the interface between an application and the op­
erating system, the application can be informed of varying resource availabilities,
and can make use of this information to vary the quality of its results. In particular
an example decoder application is presented, which makes use of such information
and exploits some of the fundamental properties of continuous media data to trade
video image quality for the amount of processor time which it receives.

To my parents
John and Olive

Preface
Except where otherwise stated in the text, this dissertation is the result of my own
work and is not the outcome of work done in collaboration.
This dissertation is not substantially the same as any I have submitted for a degree
or diploma or any other qualification at any other university.
No part of this dissertation has already been, or is being currently submitted for
any such degree, diploma or other qualification.
Trademarks
DECstation, TURBOchannel and AudioFile are trademarks of Digital Equipment
Corporation.
MIPS is a trademark of MIPS Technologies, Inc.
unix is a registered trademark of AT&T.
i

Acknowledgements
I would like to thank my supervisor Ian Leslie for his guidance and encouragement
throughout my time at the Computer Laboratory. I would also like to thank Derek
McAuley for many interesting and thought­provoking discussions. Thanks are also
due to Roger Needham for his observations and comments which have often provided
insight into the problem at hand.
The Systems Research Group has provided a stimulating environment in which to
work and my thanks go to those who helped to make it that way. In particular, Paul
Barham, Richard Black, Simon Crosby, Mark Hayter, Paul Jardetzky, Guangxing
Li, Ian Pratt and Timothy Roscoe were always ready to discuss ideas. The interest
expressed by Jean Bacon and Ken Moody in my work is also appreciated.
For reading and commenting on drafts of this dissertation, I am indebted to Shaw
Chuang, Robin Fairbairns, Ian Leslie, Derek McAuley, Simon Moore, Cosmos Nico­
laou, Timothy Roscoe and Cormac Sreenan.
This work was supported by a studentship from Tadpole Technology plc. I am
grateful to George Grey, CEO of Tadpole for his support. Thanks are also due to
colleagues past and present at Tadpole, Timothy Bissell, Steve Chamberlain, Jeff
Graham, Mark Hancock, Crispin Thomson and Jes Wills for their continued interest
and support.
ii

Contents
List of Figures viii
List of Tables ix
Glossary of Terms x
1 Introduction 1
1.1 Motivation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1
1.2 Environment : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2
1.3 Properties of Continuous Media : : : : : : : : : : : : : : : : : : : : : 3
1.4 Issues : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
1.5 Quality of Service : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
1.6 Aims : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
1.7 Synopsis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
2 Background 6
2.1 Real­Time : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
2.1.1 Real­Time Versus Fast : : : : : : : : : : : : : : : : : : : : : : 7
2.1.2 Scheduling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9
2.1.3 Periodic Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : : 9
2.1.4 Sporadic Tasks : : : : : : : : : : : : : : : : : : : : : : : : : : 10
2.1.5 Overload Behaviour : : : : : : : : : : : : : : : : : : : : : : : : 11
2.2 Continuous Media and Real­Time : : : : : : : : : : : : : : : : : : : : 12
2.2.1 Hard Real­Time and Best Effort Job Mixes : : : : : : : : : : : 12
2.3 Networks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
2.3.1 Transfer Mode : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
2.3.2 Bandwidth Allocation : : : : : : : : : : : : : : : : : : : : : : 16
2.3.3 Bursty Traffic : : : : : : : : : : : : : : : : : : : : : : : : : : : 17
2.3.4 Traffic Descriptors : : : : : : : : : : : : : : : : : : : : : : : : 18
2.3.5 Statistical Multiplexing : : : : : : : : : : : : : : : : : : : : : : 18
2.3.6 Service Degradation : : : : : : : : : : : : : : : : : : : : : : : 19
2.4 Real­Time and QOS : : : : : : : : : : : : : : : : : : : : : : : : : : : 19
iii

2.5 Extending QOS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20
2.5.1 IMAC : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20
2.5.2 QOS­A : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21
2.5.3 End­to­End QOS : : : : : : : : : : : : : : : : : : : : : : : : : 22
2.6 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22
3 QOS in Operating Systems 24
3.1 Example Decoder Application : : : : : : : : : : : : : : : : : : : : : : 24
3.2 A Definition of QOS : : : : : : : : : : : : : : : : : : : : : : : : : : : 26
3.3 Elements of a QOS Implementation : : : : : : : : : : : : : : : : : : : 27
3.4 Contracts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28
3.4.1 Virtual Processors : : : : : : : : : : : : : : : : : : : : : : : : 28
3.4.2 Hard Real­Time Systems : : : : : : : : : : : : : : : : : : : : : 28
3.4.3 Best Effort Systems : : : : : : : : : : : : : : : : : : : : : : : : 29
3.4.4 Dynamic Real­Time Systems : : : : : : : : : : : : : : : : : : : 29
3.4.5 Implications : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30
3.5 Negotiation and Renegotiation : : : : : : : : : : : : : : : : : : : : : : 30
3.6 Parameters : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32
3.6.1 Resources Requiring Parameterization : : : : : : : : : : : : : 32
3.6.2 Parametric Complexity : : : : : : : : : : : : : : : : : : : : : : 32
3.6.3 Processor Time Parameters : : : : : : : : : : : : : : : : : : : 33
3.7 QOS Description : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34
3.7.1 Describing the Accuracy of Results : : : : : : : : : : : : : : : 35
3.7.2 Mapping QOS Descriptions : : : : : : : : : : : : : : : : : : : 36
3.8 Run Time Resource Allocation : : : : : : : : : : : : : : : : : : : : : : 38
3.8.1 Notation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39
3.8.2 Deterministic Models : : : : : : : : : : : : : : : : : : : : : : : 40
3.8.3 Stochastic Models : : : : : : : : : : : : : : : : : : : : : : : : : 40
3.9 Accounting : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42
3.9.1 Credits : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42
3.9.2 QOS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43
3.10 Policing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43
3.11 Application Design : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44
3.11.1 Temporal Degradation : : : : : : : : : : : : : : : : : : : : : : 44
3.11.2 Spatial Degradation : : : : : : : : : : : : : : : : : : : : : : : : 44
3.11.3 Logical Degradation : : : : : : : : : : : : : : : : : : : : : : : 44
3.11.4 Data Representation : : : : : : : : : : : : : : : : : : : : : : : 46
3.12 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 47
4 Design Considerations for QOS 48
4.1 Approach : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48
iv

4.2 Design Goals : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49
4.3 Addressing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50
4.3.1 Loading Executables : : : : : : : : : : : : : : : : : : : : : : : 50
4.3.2 Sharing Text : : : : : : : : : : : : : : : : : : : : : : : : : : : 51
4.4 Memory Access Protection : : : : : : : : : : : : : : : : : : : : : : : : 52
4.5 Communication : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54
4.5.1 Components of Communication : : : : : : : : : : : : : : : : : 55
4.5.2 Events : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57
4.5.3 Design of the Event Mechanism : : : : : : : : : : : : : : : : : 58
4.5.4 IPC from Primitives : : : : : : : : : : : : : : : : : : : : : : : 60
4.5.5 Hardware Interface : : : : : : : : : : : : : : : : : : : : : : : : 60
4.6 Scheduling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60
4.6.1 Time : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61
4.6.2 Process Classes and States : : : : : : : : : : : : : : : : : : : : 61
4.6.3 Accounting : : : : : : : : : : : : : : : : : : : : : : : : : : : : 63
4.6.4 Policing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64
4.7 Virtual Processor Interface : : : : : : : : : : : : : : : : : : : : : : : : 64
4.7.1 Activation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 65
4.8 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 67
5 Implementation 68
5.1 System Overview : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68
5.2 NTSC Code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 69
5.2.1 Device Interrupt Stubs : : : : : : : : : : : : : : : : : : : : : : 70
5.3 Processes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 71
5.3.1 The Virtual Processor Interface : : : : : : : : : : : : : : : : : 72
5.3.2 Activation and the VPI : : : : : : : : : : : : : : : : : : : : : 73
5.4 Building a Nemo System : : : : : : : : : : : : : : : : : : : : : : : : : 74
5.5 The Bootstrap Sequence : : : : : : : : : : : : : : : : : : : : : : : : : 75
5.6 Resource Management : : : : : : : : : : : : : : : : : : : : : : : : : : 75
5.6.1 Accounting and Policing : : : : : : : : : : : : : : : : : : : : : 76
5.6.2 Allocation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76
5.7 Events : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76
5.7.1 Creating an Event Channel : : : : : : : : : : : : : : : : : : : 76
5.7.2 Signalling Events : : : : : : : : : : : : : : : : : : : : : : : : : 77
5.8 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78
6 Evaluation 79
6.1 Experimental Assessment : : : : : : : : : : : : : : : : : : : : : : : : : 79
6.1.1 Application Use of the System VPI : : : : : : : : : : : : : : : 79
6.1.2 Interaction With QOS Mechanisms : : : : : : : : : : : : : : : 83
v

6.1.3 Varying Application QOS : : : : : : : : : : : : : : : : : : : : 85
6.1.4 User Level Threads : : : : : : : : : : : : : : : : : : : : : : : : 89
6.2 Comparison With Related Work : : : : : : : : : : : : : : : : : : : : : 89
6.2.1 Scheduling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89
6.2.2 Virtual Processor Interface : : : : : : : : : : : : : : : : : : : : 90
6.2.3 QOS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 93
6.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 94
7 Conclusions and Further Work 95
7.1 Contributions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 95
7.2 Further Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 97
Bibliography 98
vi

List of Figures
2.1 Timing diagram for a task. : : : : : : : : : : : : : : : : : : : : : : : : 7
2.2 A periodic task. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7
2.3 Two periodic tasks. : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
2.4 Transmission of two temporally constrained messages. : : : : : : : : 15
2.5 Bits per frame for video encoded with MPEG codec. : : : : : : : : : 17
3.1 Decode time and bits per frame of compressed video. : : : : : : : : : 26
3.2 QOS management entities and their interactions. : : : : : : : : : : : 27
3.3 Sporadic process ø 1
and execution profiles ffl 1
and ffl 2
. : : : : : : : : : : 33
3.4 Two sporadic processes ø 1 and ø 1 . : : : : : : : : : : : : : : : : : : : : 34
3.5 Region of acceptable error for a computation. : : : : : : : : : : : : : 35
3.6 Frame size versus time to decode. : : : : : : : : : : : : : : : : : : : : 36
3.7 Predicted and measured decode times. : : : : : : : : : : : : : : : : : 37
3.8 Run time resource allocation model. : : : : : : : : : : : : : : : : : : 39
3.9 Run time allocated to decoder versus percentage of frames which can
be decoded within that time. : : : : : : : : : : : : : : : : : : : : : : : 41
3.10 Frame number versus time to decode two compressed video streams. : 42
4.1 Sharing text in a single address space. : : : : : : : : : : : : : : : : : 51
4.2 The structure of a system which uses privileged library. : : : : : : : : 54
4.3 Arrival, processing and delivery of an event. : : : : : : : : : : : : : : 57
4.4 Activation section of the virtual processor interface. : : : : : : : : : : 65
4.5 Execution of a process showing activation points and reasons. : : : : 66
5.1 Structure of a typical Nemo system. : : : : : : : : : : : : : : : : : : : 68
5.2 Nemo clock device interface. : : : : : : : : : : : : : : : : : : : : : : : 70
5.3 Nemo virtual processor interface. : : : : : : : : : : : : : : : : : : : : 72
5.4 Example Nemo configuration file. : : : : : : : : : : : : : : : : : : : : 74
5.5 Layout of a Nemo system image as constructed by build. : : : : : : : 75
5.6 PCB event structure. : : : : : : : : : : : : : : : : : : : : : : : : : : : 77
5.7 Process A signalling the occurrence of n events to process B. : : : : : 78
6.1 Assembler part of default activation handler. : : : : : : : : : : : : : : 80
6.2 Body of default activation handler. : : : : : : : : : : : : : : : : : : : 80
vii

6.3 Body of the decode/display activation handler. : : : : : : : : : : : : : 82
6.4 Contracted and additional processor times versus frame number. : : : 83
6.5 Processor time obtained by ten decoder applications. : : : : : : : : : 85
6.6 Partially decoded frame: milestone version. : : : : : : : : : : : : : : : 87
6.7 Partially decoded frame: milestone/monotone version. : : : : : : : : : 88
viii

List of Tables
4.1 Definitions of bits in the virtual processor interface registers. : : : : : 65
5.1 NTSC code segments. : : : : : : : : : : : : : : : : : : : : : : : : : : : 70
ix

Glossary
ACME Abstractions for Continuous Media
ASCII American Standard Code for Information Interchange
ATM Asynchronous Transfer Mode
BE Best Effort
B­ISDN Broadband Integrated Services Digital Network
CBR Cambridge Backbone Ring
CBSRP Capacity Based Session Reservation Protocol
CIF Common Intermediate Format
CM Continuous Media
CPU Central Processing Unit
DAN Desk Area Network
DCT Discrete Cosine Transform
DPCM Differential Pulse Code Modulation
DS Deferrable Server
EDF Earliest Deadline First
FCFS First Come First Served
FIFO First In First Out
HRT Hard Real­Time
IDCT Inverse Discrete Cosine Transform
IMAC Integrated Multimedia Applications Communication
I/O Input/Output
IPC Inter­Process Communication
JPEG Joint Photographic Experts Group
KLS Kernel Level Scheduler
LAN Local Area Network
x

MAC Media Access
MAS Multiple Address Space
MPEG Motion Picture Experts Group
NPR Non­preemptive Priority
NRM Network Resource Manager
NTSC Nemo Trusted Supervisor Call
PB Processor Bandwidth
PCB Process Control Block
pel Picture Element
PPR Preemptive Priority
PR Priority
PTM Packet Transfer Mode
QCIF Quarter Common Intermediate Format
QOS Quality of Service
RISC Reduced Instruction Set Computer
RM Rate Monotonic
RPC Remote Procedure Call
RTRA Run Time Resource Allocator
SAS Single Address Space
SLS Split Level Scheduling
SM Session Manager
SRM System Resource Manager
SRT Soft Real­Time
STM Synchronous Transfer Mode
ULS User Level Scheduler
VBR Variable Bit Rate
VP Virtual Processor
VPI Virtual Processor Interface
xi