Chapter 1
Introduction
This dissertation is concerned with the treatment of continuous media by the sys­
tem and application software within a workstation environment. It commences by
describing the factors which motivate the investigation of this topic.
1.1 Motivation
Both the deployment of multi­service networks within the local area and the avail­
ability of suitable network interfaces have made it possible to deliver to a user's
workstation, new classes of traffic such as digital audio and video, in addition to
the types of network traffic previously found in LANs. This has prompted much
research into how video and audio are to be treated within a workstation environ­
ment. Video and audio are commonly referred to as continuous media (CM) because,
while they are in fact discrete, their regular, periodic presentation at sufficiently high
frequencies makes them appear smooth and continuous to the human perception.
Until recently, the bandwidth and temporal requirements of even moderate video
formats have meant that special­purpose, dedicated hardware has been used to
handle the video and audio data; the Pandora [Hopper90] project is an example
of such a system. In systems like this, the workstation CPU controls the continuous
media streams indirectly and typically does not directly manipulate the media data.
The increasing power of microprocessors [Geppert93] has made it possible for gen­
eral purpose processors to be used to perform tasks which have previously required
either dedicated hardware or special purpose, digital signal processors. Equipping
a workstation with such a microprocessor and a suitable network interface enables
it directly to manipulate continuous media streams in real­time without the need
1

for any special purpose hardware. Work recently done within the Computer Labo­
ratory has produced a system which has much of the functionality of a Pandora's
box, but which runs on an unmodified DECstation 5000/25, containing a 25MHz
MIPS R3000 processor and an interface between an ATM network and the DEC
TURBOchannel [Greaves92]. 1
While it is anticipated that future workstation hardware will be quite powerful,
even moderate video formats are able to consume a considerable amount of system
resources. For this reason, even though it is possible to handle video streams with
the workstation CPU, it may not necessarily be the case that all of the streams in a
system ought to be handled by the CPU. [Hayter91] presents a flexible, extensible,
workstation architecture which is based on a switch [Leslie91] rather than a bus and
in which CM streams can be routed either through a processor if they require pro­
cessing or around it if they do not. Both bus­based and switch­based architectures
have in common the ability to present CM data to applications. Consequently, CM
become another data type and the writers of applications can write programs which
store, process and present them similarly to other data types. Current workstation
operating systems do not provide adequate support for applications which handle
such data. This provides the motivation for investigating the treatment of CM data
within such an environment.
1.2 Environment
Many CM applications are distributed [Nicolaou91], and these are in many respects
more interesting than applications which run on a single machine. So the type of
system considered in the following chapters will be based on generic kernel function­
ality which provides the infrastructure for execution of and communication between
active entities (clients and servers). Within the distributed environment, specialised
servers run on machines configured for the services they offer. For example, one ma­
chine might provide a CM file service [Jardetzky92] and another a synchronisation
service [Sreenan92]. To discuss completely and design such a system would require
the investigation of many areas such as naming, security and reliability which are
beyond the scope of this work. So the work which is described in the following chap­
ters focusses on the development of low­level software which can be used to support
the servers and clients with which such a system can be built.
1 The Pandora framework was ported by Timothy Roscoe, the X server and CM stream software
by Paul Barham, and the Base Board Audio driver and AudioFile software by Shaw Chuang.
2

1.3 Properties of Continuous Media
CM have two important properties. The first property is that their fidelity is often
dependent upon the timeliness with which they are presented. This will be referred
to as the temporal property of CM and creates the requirement that code which
manipulates the segments of CM data may need to be executed within suitable
windows of time.
The second property is that they are often tolerant of the loss of some of their infor­
mation content. It is precisely this property which enables compression algorithms
such as those described in chapter 3 to obtain such high compression ratios. This
property will be referred to as the informational property and provides something
which might be exploited by systems which handle CM.
1.4 Issues
While there is a considerable body of experience with building real­time systems
which are able to provide temporal guarantees for the execution of applications
[Stankovic88], the exact relationship between CM and real­time systems is yet to
be determined. Correctness in real­time systems requires that the result of a com­
putation is both logically correct and available by a particular time. In many such
systems, failure to produce a correct result on time is treated as a fatal system er­
ror. Such stringency does not readily accommodate CM applications which might
require timely execution most of the time or only some of the time, and it does not
allow the informational property of CM to be exploited easily.
Much of the current experience with real­time programming derives from the con­
struction of embedded systems. These may be viewed as ``black boxes'' whose inputs
and corresponding outputs are well defined. In such an environment, the scheduler
has a detailed knowledge of system resource availability and application resource
requirements. Applications are written with the assumption that they will always
receive all of the resources which they require and system overload is an exceptional
condition. The design and construction of these systems emphasises the ability to
predict system responses to known inputs.
A workstation, particularly one connected to a network, is a dynamic environment
in which system inputs, resource availability and requirements are not likely to be
known in any detail. The size, complexity and dynamic nature of such systems
makes it difficult to predict their behaviour exactly, but in order to support CM
applications, they must still be able to maintain the temporal properties of CM
3

data. The types of applications which are envisioned are distributed and an exact
description of their resource requirements is likely to be complex. Some means
is needed, whereby an application's resource requirements can be expressed more
simply, and the system scheduler needs to be able to interpret such descriptions.
CM applications can consume large amounts of resources and this can impact the
performance of the rest of a system. It may be, that even in a lightly loaded system,
a user will not want to give an application all of the resources it wants. In an
overloaded system, there are not enough resources available to satisfy all requests,
and the ability to limit the usage of resources by an application can be used to
control the manner in which the system degrades. The operating system mechanisms
needed to do this are in many respects similar to those used in traditional mainframe
timesharing systems, but they are given a new perspective by requiring that they
maintain the temporal properties of CM and enable exploitation of the informational
properties.
Giving an application fewer resources than it needs affects its performance so some
applications may benefit from being written in a manner which allows them to
adjust the quality of their results according to the resources which are available to
them. Informing an application of the resources which are available to it would help
guide its decisions in such circumstances. Mechanisms suitable for conveying this
information to applications need to be investigated.
In situations of extreme overload, the system may have to refuse to run an appli­
cation on the grounds that running the new application would adversely affect the
performance of the system in general. Consideration needs to be given to the de­
velopment of policies for determining when newly arrived applications are allowed
to run, causing the system's performance to deteriorate, and when they ought to be
refused.
1.5 Quality of Service
Maintaining the temporal properties of CM data and applications within an op­
erating system is primarily a resource allocation problem. The model of resource
allocation which is used throughout this dissertation is based on the notion of Qual­
ity of Service (QOS). Within this model, QOS appears in different forms as part of
the interfaces between the layers of a system. At the interface between an applica­
tion and the operating system, the system is viewed as a service provider and the
application is viewed as a service user. The application can then request a certain
QOS from the operating system. As a further example, at the interface between
4

an application and a user, the application might be the service provider, with the
user requesting a certain QOS from the application. A QOS specification in this
model is a means by which the usual syntactic and semantic definition of an interface
such as a system call may be augmented to incorporate extra requirements such as
timeliness and accuracy.
1.6 Aims
This dissertation aims to investigate mechanisms and policies which can be imple­
mented in an operating system to provide support for CM applications. In partic­
ular, the suitability of QOS as a scheduling paradigm for CM applications is to be
examined and the mechanisms required to support it are to be determined. Also to
be explored are the effects which this type of resource allocation strategy has on the
design of applications, their behaviour, and the interface between applications and
the system.
1.7 Synopsis
Chapter 2 presents a summary of some background material covering real­time
scheduling and resource allocation within ATM networks, then compares these with
QOS­based resource management techniques for scheduling CM applications in a
workstation.
Chapter 3 discusses the incorporation of QOS into operating systems as a resource
allocation paradigm.
Chapter 4 presents considerations to be taken into account when designing an op­
erating system which is to provide QOS contracts to CM applications.
Chapter 5 describes a small system called Nemo which was implemented to experi­
ment with some of the mechanisms proposed in chapter 4.
Chapter 6 contains an evaluation of Nemo and shows how applications can be im­
plemented to make use of the features provided by it.
Chapter 7 summarises the work contained in the previous chapters and draws a
number of conclusions.
5