Chapter 3
QOS in Operating Systems
The previous chapter has compared QOS with real­time scheduling paradigms and
discussed the advantages of QOS when used to schedule CM applications. The
purpose of this chapter is to investigate in some more detail, the means by which
QOS might be supported within an operating system together with some of the
implications of doing so. To begin with, a simple CM application is described. This
will be used as an example in later sections.
3.1 Example Decoder Application
The example application decodes a compressed video stream and displays it directly
on a memory mapped frame buffer. Each frame of the video stream is compressed
using the JPEG [Wallace91] still picture compression algorithm and the decoder
performs decompression and display of the frames at the rate at which the video
was originally sampled. The application decodes compressed frames in a number of
steps. The input bit stream is expanded into a sequence of 8 \Theta 8 tiles of Discrete
Cosine Transform (DCT) coefficients using a Huffman decoder and a run­length
decoder. Each of the coefficients in a tile is multiplied by a corresponding entry
in an 8 \Theta 8 quantiser matrix. An 8 \Theta 8 Inverse DCT (IDCT) is performed on the
coefficients to retrieve a tile of level­shifted pixel values which are then adjusted to
absolute pixel values. The process is repeated until all of the tiles for one frame of
video have been decoded whereupon the frame is displayed.
The encoding process is essentially the reverse of decoding; a tile of absolute pixel
values is level­shifted, transformed using the DCT and each of the coefficients di­
vided, using integer division, by a corresponding entry in the quantiser matrix. The
quantising step truncates small coefficients of the higher spatial frequencies, produc­
24

ing large numbers of zero­valued coefficients in the quantised tile. These coefficients
are run­length encoded then Huffman encoded to produce the output bit stream.
The degree of compression obtained can be controlled by scaling the quantiser matrix
during the encoding phase. The implementation used in the encoder controls this
scaling by means of the Q factor. Prior to encoding or decoding, each entry q ij (1 Ÿ
i; j Ÿ 8) in the quantiser matrix is scaled by the Q factor so that q Q
ij = (q ij \Theta Q)=100
with the resulting values truncated to the range (1; 32767), and the q Q
ij are used
during the encoding and decoding process. The same Q factor is used to decode
an image as is used to encode the image. High Q factors produce high compression
ratios and more distorted images; low Q factors produce low compression ratios and
less distorted images. Typical Q factors used for compressing video range from 30
to 200.
Section 2.3.3 demonstrates that one of the results of compressing a video stream is
that the bandwidth required to transport the compressed representation is bursty.
The JPEG decoder application exhibits this property and reveals another interesting
fact. A video segment was sampled at 15 frames per second and a resolution of 160
pels wide and 112 pels high, each pel being represented by 8 bits of grey­scale
information. In its raw form, this stream requires a bandwidth of 160 \Theta 112 \Theta 8 =
143:36 kilobits per 67 milliseconds to deliver the stream to an application. The
application then requires 653 microseconds of processor time if it is to display each
frame by copying it into a frame buffer. 1 In this case, a CBR stream is being delivered
to an application which requires a fixed rate of processor resource to display the
stream. The usages of the bandwidth and processor resources are both periodic and
constant.
The stream was then compressed using the JPEG encoder and presented to the
JPEG decoder for displaying. The graph in figure 3.1 plots frame number versus
the number of bits in the compressed frame and the time required to decode the
frame. The graph shows that not only has compression made the bandwidth of
the video stream bursty, but that the execution time required by the decoder to
reconstruct the frames has also become bursty.
The decoder is a simple application, but has the properties which are typical of the
applications which this work is aimed at scheduling. Each frame must be displayed
at the appropriate time and the resource requirements of the application vary con­
siderably with time. The temporal requirement would make it a good candidate for
scheduling using conventional real­time techniques but the burstiness would cause
them to obtain poor resource utilisation. The remaining sections discuss how QOS
can be incorporated into an operating system and how its use interacts with applica­
1 The measurements presented in this section were made on a DECstation 5000/25.
25

0
10
20
30
40
50
60
70
0 500 1000 1500 2000
Decode
Time
(milliseconds)
and
Frame
Size
(kilobits)
Frame Number
Decode Time
Max: 67.4 milliseconds
Min: 19.5 milliseconds
Frame Size
Max: 21.0 kilobits
Min: 1.8 kilobits
Figure 3.1: Decode time and bits per frame of compressed video.
tions such as the decoder. The discussion commences by presenting some definitions.
3.2 A Definition of QOS
In its common, accepted usage, quality connotes a particular characteristic, as well as
the degree to which a characteristic is present. Within the context of the operating
system being a provider of services such as processor cycles, memory, I/O operations
and so on, quality of service is used to refer both to the kind of a service being
provided, and to the extent to which that service is made available to an application.
This extent is quantified by the amount of the service which is provided and the
times at which it is provided.
The provision of services in a timely manner requires appropriate allocation of
system resources so, in their most basic forms, the QOS q d desired by an ap­
plication will describe the application's resource requirements, and the QOS q p
provided by the system will be the result of the resource allocation scheme used
within the system. q d and q p can be represented by vectors of resource requirements
~
q d =
h
r d
1 (t)r d
2 (t) \Delta \Delta \Delta r d
n (t)
i
and ~
q p =
h
r p
1 (t)r p
2 (t) \Delta \Delta \Delta r p
n (t)
i
where r d
i (t) is the amount
of resource r i desired by the application and r p
i (t) is the availability of resource r i
which was provided by the system. The r i (t) are called QOS parameters.
26

3.3 Elements of a QOS Implementation
Figure 3.2 shows how an operating system might be constructed to provide QOS for
its applications. In this diagram, the application is either a client or a server process.
Time Memory I/O
CPU
Run Time Resource Allocation
Accounting
Policing
QOS Manager Application
QOS Description
Contract
Parameters Resource
Allocation
Figure 3.2: QOS management entities and their interactions.
The purpose of the QOS manager is to come to some agreement with processes
about the QOS which will be delivered to them. An application presents to the QOS
manager a description of its requirements and the QOS manager converts this to a set
of parameters. The QOS manager then decides whether or not it can accommodate
this request; it may be able to do this using only the QOS description or it may need
the information provided by the QOS parameters. If the QOS can not be provided,
the application is informed and the user may be informed by the application or the
QOS manager. If the QOS can be provided the resources required to provide that
QOS are noted and the application is informed of their availability. A contract then
exists between the application and the system. The QOS manager communicates the
application's QOS parameters to the Run­Time Resource Allocator (RTRA), which
uses them in conjunction with some knowledge of the current time to allocate the
resources to the application. Effective resource allocation will require some means
of accounting for the resources used by an application. This will enable the resource
allocator to police an application's use of system resources so that, when resources
are scarce, it cannot use more than it has been allocated.
27

3.4 Contracts
Among the most important factors in a QOS implementation is the nature of the
contractual agreement which exists between the system and an application. The
existence of such a contract enables certain assertions to be made about the run­
time behaviour of an application. These assertions are useful to the writers of
applications, because they supplement the semantics of the standard definition of
the operating system interface.
3.4.1 Virtual Processors
One view of an operating system is that of a layer of software which abstracts the
physical hardware to a Virtual Processor (VP) more amenable to the applications
which run on it. Applications are written so that they are aware only of the Virtual
Processor Interface (VPI) provided by the operating system and do not necessarily
know about the existence of any other activities within the system. For example,
[Leffler89] describes the unix VPI as consisting of a set of system calls, a vector of
interrupt or signal handlers and a mask for enabling and disabling the delivery of
interrupts. The base semantics of this VPI are defined by the programmer's reference
manual. These include neither the time which any of the requested operations will
take nor any notion of the rate of progress which the application will make during
its execution. Without this information it is difficult for the application writer to
make any assertions about the temporal behaviour of an application.
The purpose of a QOS contract is to augment the semantics provided by the sys­
tem VPI so that stronger assertions may be made about an application's run­time
behaviour whenever the contract is in force. The terms of the contract are specific
to a particular instance of an application and determine the assertions which can be
made. To gain a better understanding of the QOS contract, it is worth noting that
the ability of a scheduling algorithm to decide whether or not an application will
run on time is determined by the amount of knowledge which it has about current
availabilities of system resources and the resource requirements of the application.
3.4.2 Hard Real­Time Systems
In a HRT system, application resource requirements are known exactly for all time
so a scheduler can, given sufficient time, determine whether or not a feasible schedule
exists and if so, produce a schedule. In such an environment, the contract between
the system and the application is quite rigid; the application, when it runs, will
28

always receive the resources it needs and if it does not, a fatal system error has
occurred. The QOS afforded by such a contract is always good enough for the
application to behave correctly both logically and temporally. Applications are
written so that, once they are scheduled, there is never any reason to expect that
their resources will not be available at the times they are needed, and timeliness is
always guaranteed.
3.4.3 Best Effort Systems
A Best Effort (BE) system, such as is typically run on current workstations, as­
sumes almost no knowledge of application resource requirements and provides no
mechanism for applications to specify their temporal requirements. The schedulers
in such systems make use of multilevel feedback queues to try to improve interac­
tive response times by giving a higher priority to programs which do a lot of I/O,
while also trying to give compute bound programs access to the system resources
for comparitively longer times. The contract which exists between such a system
and an application asserts that the VPI will be logically correct, but does not make
any assertions regarding the timeliness with which resources will be made available
to the application. The QOS afforded by such a contract is variable and fluctuates
with system load. Applications are written without any requirement for resources
to be made available to them in a timely manner and the operating system provides
little or no direct support for an application to determine its progress.
3.4.4 Dynamic Real­Time Systems
In between these two extremes lay a range of systems in which less than complete
knowledge of application resource requirements is available. This may be due to
the inability to measure them accurately, or simply the inability to predict the
future. Overall, the exact behaviour of such systems may be unpredictable, but the
applications which they support still have temporal requirements. The nature of the
contract which exists between the system and an application is less than absolute,
in that the application may not always be guaranteed to obtain all of its resources
every time it needs them. The assertions which may be made about the execution
of such an application are of the form ``99% of the time, this program will meet
its deadlines,'' and are less than absolute but do serve to quantify the application's
run­time behaviour.
Application writers will need to keep in mind that the quantity of resources avail­
able to them will change with time. This can be made easier if the system makes
29

available to applications some information about the amount of resources which are
being made available to them whenever they are running. The information could
be presented to the application as a sequence of upcalls or signals incorporated into
the VPI for this purpose.
This represents a significant departure from the traditional view of the VPI provided
by real­time systems. Rather than having the system guarantee a required level of
performance to applications and writing applications which assume their resources
will always be available, these systems try to provide resources in a timely manner
informing applications of their availability, and applications attempt to produce the
best results they can using the notification and resources which they are given.
3.4.5 Implications
The definition of QOS given in section 3.2 is quite broad and accommodates all three
types of system just described, so it ought to be possible in a QOS based system
to request any QOS ranging from BE to HRT. The former is relatively straightfor­
ward to provide and the ability of a system to provide the latter will depend on
the current knowledge of resource requirements and the scheduling algorithms in
use within the system. Both BE and HRT have been studied extensively and con­
siderable experience has been gained with them [Coffman73] [Stankovic88], so they
will not be considered in any detail in the remainder of this discussion except where
necessary. Rather, attention will be focussed on the more interesting case of the
type of QOS which might be used to support applications with dynamic real­time
resource requirements.
3.5 Negotiation and Renegotiation
An important system parameter is the length of time for which any single QOS
contract remains valid. A system in which contracts remained valid for the lifetime
of all processes would not be suitable for a workstation because of the variability of
the job load in such an environment.
Consider a situation in which 90% of a workstation's processor had been reserved
and the user wished to run an application which requires 15% of the processor;
there are two possible courses of action. The system can recognise that allowing
the new process to run could adversely affect the contracts currently in force and
inform the application that, while it can not have its desired 15%, it could be given
the remaining 10%. The application then would have to decide, either by executing
30

some default decision or by consulting the user, whether it would want to proceed
with only two thirds of the processor time which it ideally would like and then
accept or reject the contract which it has been offered. These actions constitute a
negotiation between the application and the system about the amount of processor
time which will be made available to the application as part of its contract.
If this application could not run with any less than 15% of the processor and con­
tracts were not allowed to be broken, the system would have to refuse to run it. If
contracts are allowed to be broken, then the user can direct the QOS manager to re­
lease resources previously reserved and make them available to the new application.
To help the other applications respond to this, they need to be informed of the fact
that the contract which they held at the time was just broken. They can use this
information to engage in renegotiation with the QOS manager for a new contract.
QOS renegotiation can also be instigated by an application. Consider the decoder
application described in section 3.1. Suppose the input data were being produced
by a camera viewing a live scene and encoding it for delivery to the decoder via a
network. The processor time of the decoder is dependent upon the data which it is
receiving, which is directly related to the scene which the camera is viewing. This
dependency is compounded by the use of encoders which use motion compensation
techniques to achieve high compression ratios. In such circumstances, an initial esti­
mate of processor time which was based upon the data rate produced by a uniform,
motionless scene would be wholly inadequate for decoding the data produced by
a popular music video clip. It would then be appropriate for the decoder to note
the number of frames which are successfully decoded on time, and renegotiate for
more processor time when this number falls below a specified level. To ensure sen­
sible use of system resources, applications ought to aim at maintaining the amount
of processor resource requested as close as is reasonable to their actual processor
requirements.
In the examples just described, scheduling decisions are made at two levels. At
the negotiation phase, long term scheduling decisions are being made and, because
they are made comparatively infrequently, they may be relatively complex and take
longer to make. The RTRA makes only very simple decisions (which process to run
next, for example), based on simple rules such as highest priority, earliest deadline
or as recorded in a state table. Negotiation and RTRA within the operating system
are parallelled in ATM networks by call acceptance control and cell­level scheduling
respectively. Negotiation and call acceptance control both have the effect of factoring
out the harder scheduling decisions and amortising their cost over the time between
negotiations. In the limiting case, where an application is required to negotiate
for resources at every arrival, the scheduling problem becomes that of scheduling a
totally dynamic real­time system.
31

3.6 Parameters
In the system shown in figure 3.2 in section 3.3, the QOS manager converts QOS
descriptions into a set of parameters which describe at a low level an application's
resource requirements.
3.6.1 Resources Requiring Parameterization
To describe all of the resource requirements of an application would require a QOS
parameter for each resource. In the case of the video decoder example, two obvious
QOS parameters would describe processor and input bandwidth requirements. Be­
cause paging in virtual memory systems can introduce large amounts of jitter, the
decoder might also like to specify that a certain minimum number of frames of phys­
ical memory be made available to it for its execution; this would constitute another
QOS parameter. Some criteria are required for determining the set of resources for
which QOS parameters are needed. An argument similar to that of section 2.1.1
would indicate that if, within a particular system, a resource is so plentiful that its
utilisation remains sufficiently low, then there is no need to reserve it and no cor­
responding requirement to parameterise its usage. This set is specific to a system;
resources which are scarce on one system may be plentiful on another and vice versa.
The remainder of this discussion will be concerned with only the processor resource.
3.6.2 Parametric Complexity
Another matter which arises is the amount of detail which ought to be included
in the QOS parameters. In the context of scheduling bandwidth in a network, the
B­ISDN signalling protocol [CCITT92] currently acknowledges peak bandwidth and
end­to­end transmission delay as being significant parameters. Other parameters
such as jitter and burstiness are yet to be decided upon and it is not likely that this
decision will result in an orthogonal set of individual parameters. More realistically,
the service user will be allowed to select from a number of QOS classes. The evidence
suggests that the more accurately the description of resource requirements is known,
the more accurately resources can be reserved, but that doing so will require more
detailed calculations. This motivates the use of simple, parametric descriptions of
service requirements.
32

3.6.3 Processor Time Parameters
An application's Processor Bandwidth (PB) can be used to quantify its processor
requirements. Such a bandwidth may be expressed as a percentage of the total avail­
able processor resource to obtain a measure of the utilisation of the processor by an
application. A percentage however, does not provide any indication of when the pro­
cessor resource is required, so the pair (c; t) is used as an equivalent representation,
where c is the processor time allocated to the process every t seconds.
The decoder application is a periodic process and it is straightforward to see how a
bandwidth can be specified for it. The upper timing diagram in figure 3.3 shows three
arrivals of a sporadic process ø 1 whose minimum inter­arrival time is 4 milliseconds
and whose deadline is 5 milliseconds after arrival. The process requires 2 milliseconds
of processor time, so its peak processor bandwidth is (2=4) \Theta 100 = 50%. The lower
t 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Time in milliseconds
e 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
e 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figure 3.3: Sporadic process ø 1 and execution profiles ffl 1 and ffl 2 .
two timing diagrams show possible execution profiles ffl 1 and ffl 2 of ø 1 when it has
been allocated a processor bandwidth of (1; 2). From the figure, it can be seen that
the processor needs to be allocated to ø 1 both within a certain minimal time and at
a certain minimum rate for ffl 1 to meet its deadline. This places some restrictions on
the granularity of the bandwidth parameters which can be used for ffl 1 if it is not to
be tardy. If bandwidth is periodically allocated as (c; t), and ø 1 requires C cycles
after its arrival at time A to meet a deadline at time D, then a bound for (c; t) when
t Ÿ (D \Gamma A) would be b(D \Gamma A)=tc \Theta c – C. When t ? (D \Gamma A), this is no longer
sufficient, and additional constraints that c – C and C of the c cycles be allocated
before D are needed.
While it is possible to meet temporal requirements by simply allocating a sufficient
processor bandwidth, this will not always result in an efficient use of the processor.
Figure 3.4 shows a feasible schedule for two sporadic tasks ø 1 and ø 2 . A simple as­
33

t 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
t 2
Figure 3.4: Two sporadic processes ø 1 and ø 1 .
signment of processor bandwidths to these processes would allocate (10; 16) = 62:5%
to ø 1 and (4; 8) = 50% to ø 2 which would overcommit the processor by 12:5%. In
other words, to meet these deadlines by assigning a processor bandwidth to each
task would require a processor which is 1:125 times faster than the one used to ob­
tain the timing diagram of figure 3.4. Using a faster processor, the execution times
could be reduced by a factor of 1=1:25, so that the bandwidths required would be­
come (10=1:125; 16) = 55:56% and (4=1:125; 8) = 44:44% for ø 1 and ø 2 respectively.
In this situation, processor bandwidth is too simple a description of the behaviour
of the processes; use of a constant processor bandwidth assumes that the processes
are periodic, while those in the figure are sporadic. In the special case of a periodic
process whose deadline is the same as its period, processor bandwidth can be an ac­
curate description of processor time requirements, and the process can be scheduled
using RM. While processor bandwidth provides a convenient means of describing
processor requirements, it must be remembered that, for some applications it is a
simplified description of the actual requirements.
3.7 QOS Description
[Nicolaou91] and [Campbell93] suggest that, when requesting a particular QOS from
a network, an application ought to provide a description of what it requires rather
than how the QOS is to be provided. An example given is that of an applica­
tion requiring a network connection over which a standard format video stream is
to be carried; the application simply requests a video source with a QOS descrip­
tion of StandardVideo and it is left to the network QOS management functions
to map this description to a set of network QOS parameters. This is reasonable
because the network QOS management entities are likely to have some knowledge
of what resources are required to support a frequently requested QOS such as a
StandardVideo stream. Both sources recognise that this will not always be the case
and that applications ought to be able to supply low level QOS parameters whenever
necessary.
34

Were the QOS manager able to convert a description as provided by an application
into a suitable set of QOS parameters, a number of advantages would be obtained.
Firstly, an application could be moved among machines of varying speeds with­
out having to concern itself with how much of the processor it needs on each of the
machines; the QOS managers on various machines could contain machine specific in­
formation and scale the run time allocated to the application accordingly. Secondly,
it provides a convenient mechanism for isolating the application's data dependent
resource requirements.
3.7.1 Describing the Accuracy of Results
One difficulty when presenting the QOS manager with a description of some desired
QOS lies in actually constructing the description. In the case of a segment of video
or audio, subjective judgements of the quality of presentation need to be quantified.
With respect to the decoder application, the Q factor provides a means of directly
specifying the amount of compression desired, but does not provide any means of
quantifying the image quality.
A simple method of measuring the quality of an image which has been processed
using lossy techniques is to measure the absolute difference between the processed
image and the original. This could be averaged over all pixels in the image, or a
maximum value might be used. This would provide a simple, efficient indication of
how accurately the measured image represents the original.
The temporal requirements of CM, together with the notion of an acceptable ac­
curacy represent a two dimensional space within which the quality of CM may be
quantified. Figure 3.5 shows the region of acceptable temporal and logical error for
a hypothetical CM application. The application is deemed to have computed an
Temporal Error
Logical Error
e l
+
e t
+
e l
­
e t ­
Figure 3.5: Region of acceptable error for a computation.
output of sufficient subjective quality if the output is within [ffl \Gamma
l ; ffl +
l ] of the logically
correct or ideal output, and it does this within [ffl \Gamma
t ; ffl +
t ] of its deadline.
35

3.7.2 Mapping QOS Descriptions
A QOS description is useful if it can be used to infer some indication of the resources
required by an application to process a particular set of data. For live data, a guess
based on some previous experience will have to suffice. If the data is stored, it is
possible to produce a profile of the data offline and use this in conjunction with a
model of the application to produce an estimate of resource requirements.
Inspection of the example decoder application reveals that the time required to
decode a frame of video is approximately proportional to the size of the frame.
Figure 3.6 shows a plot of frame sizes in kilobits versus the time required to decode
the frames for 2000 frames of video. Using the method of least squares, the line of
0
10
20
30
40
50
60
70
0 5 10 15 20 25
Decode
Time
(milliseconds)
Frame Size (kilobits)
t = 19.3 + 2.4 x b
Figure 3.6: Frame size versus time to decode.
best fit is given by t = 19:3 + 2:4b where t is the time required to decode the frame
and b is the number of kilobits of compressed data in the frame. This line is a model
of the data dependent execution time of the decoder application which, given the
right information about the data which is to be processed, can provide an estimate
of the time required to do so.
Figure 3.7 plots the predicted decode time per frame for a different segment of video
along with the decode time measured. The model tends to predict less decode time
than is required for some of the frames. This is a result of the line derived by the
36

0
10
20
30
40
50
60
70
80
0 500 1000 1500
Measured
and
Predicted
Decode
Times
(milliseconds)
Frame Number
Predicted Time
Measured Time
Figure 3.7: Predicted and measured decode times.
method of least squares not allowing for the large number of points which lie above
it. While the model is too simple to predict an accurate decode time for a single
frame, it does make reasonable predictions over a large number of frames. Raising
the height of the line by increasing the value of the intercept on the decode time
axis will cause the model to predict times which allow a greater percentage of the
frames to be decoded completely. 2 A more conservative model such as t = 25 + 2:4b
can be used to determine an upper bound on the decode times. This particular
model is quite primitive and more accurate models could be constructed based on
a more detailed analysis of the decoding algorithm and data, but it does provide an
estimate of the required processor time which is more realistic than the maximum
value of 67.4 milliseconds.
Such execution time models can be used to map QOS descriptions onto a set of QOS
parameters. For a particular decoder, an execution time model can be constructed.
This model can then be used in conjunction with a stored video segment to predict
the execution times required to decode the frames and these times used individually,
or summarised in the form of a distribution of execution times. The key point
here is that such a distribution would provide more information about the run­time
behaviour of the decoder than just a simple maximum decode time. The prediction
can be stored as a set of metadata associated with the compressed video segment.
2 Section 3.8.3 will discuss the usefulness of this.
37

When requested to display a video segment, the decoder can identify itself and the
video segment to the QOS manager, which can locate the relevant metadata and
use this in its calculations to map QOS descriptions onto parameters.
For many applications, this amount of offline processing may not be warranted, but
it is possible to envisage situations which might make use of it. A video distribution
centre might store online a number of movies in a compressed format, and offer to
a large number of mass­produced (and therefore identical) client systems a video­
on­demand service. An execution time model can be created for the clients and the
decoder which they run, and the model used to predict the execution time charac­
teristics of the decoder when decoding a specific segment of video. The prediction
might be done more quickly than in real­time by machines more powerful than the
clients. In such an application, given the bandwidth required to transport the com­
pressed video, it is not unreasonable to ensure that all of the clients run the same
version of the decoder by storing a master version at the centre and transmitting a
copy to the clients before the video data. A QOS manager within one of the clients
can then be provided with the metadata for a video segment and this can be used
to calculate parameters of the QOS required by the local instance of the decoder.
3.8 Run Time Resource Allocation
The method used by a system implementation to allocate resources at runtime will
determine the type of VP perceived by applications. At the lowest level, the Run
Time Resource Allocator (RTRA) multiplexes the available resources among those
applications which need to use them. It does this using information in the form
of QOS parameters supplied by the QOS manager. In the case of the processor
resource, run time allocation is performed by the system dispatcher, a model of
which is depicted by the diagram of figure 3.8. The dispatcher sees application
resource requests as a series of task arrivals ø i , which are placed in individual queues
to wait until the processor can be allocated to them. Whenever one request has
been serviced, the dispatcher, based on some service discipline which may be inbuilt
or dictated by the QOS manager, selects a task from the head of one of the queues,
then allocates the processor to it for some amount of time. The service discipline
and allotted service times need to be chosen so that application QOS contracts are
honoured.
38

Dispatcher
Task Arrivals
Completed
Tasks
t n­1
t n
t 2
t 1
Figure 3.8: Run time resource allocation model.
3.8.1 Notation
This is a queueing system whose operation can be described using the notation
W=X=Y=Z, where W is the distribution of interarrival times, X the distribution
of service times, Y the number of servers and Z the service discipline. Among the
values for W and X are D, indicating deterministic times and G indicating stochastic
times. The use of G here is deliberate as there is at present little or no real data
concerning the distributions of execution times and these are likely to be specific to
each application. For the purposes of this discussion, the only resource which will be
considered for allocation is processor cycles and the discussion will focus on single
processor systems, so Y will represent the number of processors in the system which
will usually be one. Service disciplines include First Come First Served (FCFS)
and priority based (PR). The latter is extended to include nonpreemptive, priority
based (NPR) and preemptive, priority based (PPR) disciplines.
This type of model has been used extensively in studies of the performance of time­
sharing systems. [Coffman73] provides an introductory treatment of the subject,
proposing that important performance measures for a given system include: the
distribution of the number of tasks in a system; the distribution of the time a task
will be in the system and; the distribution of the lengths of busy periods 3 in the
system. In essence, the type of questions answered by performance analyses are
the inverse of those required to maintain QOS contracts. Given a particular system
configuration, performance analyses can determine the QOS which an application
will receive. In providing QOS contracts, the desired application QOS is known,
and a system configuration which maintains that QOS needs to be determined.
3 A busy period begins when a job arrives to find an empty system and ends when the system
again becomes empty.
39

3.8.2 Deterministic Models
A system in which arrival and service times are known could be modelled as a
D=D=1=PR queue. This type of model reflects the behaviour of a hard real time
system such as might be scheduled using the RM algorithm and in which task
arrivals are assumed to be periodic, of known period and task service times are fixed
at the maximum of any of a task's service times. Priorities are assigned to each
of the queues according to RM and the PR service discipline always services the
task of highest priority. In such a system, the contract provided to an application
is absolute.
3.8.3 Stochastic Models
It is often the case that exact or even maximal execution times for an application
are not known; if the video being viewed by the decoder application were produced
by a camera viewing a live scene, it would be difficult to estimate the maximum
time required to decode a frame.
The frame decode times plotted in figure 3.1 show a large amount of variation from
a minimum of 19 milliseconds to a maximum of 67 milliseconds; since the video
was sampled at a rate of 15 frames per second giving an interframe period of 67
milliseconds, allocating the peak processor bandwidth of (67; 67) to the application
would consume 100% of the processor resource. The graph of figure 3.9 plots the run
time allocated to the decoder versus the percentage of frames which it can decode
in that time. It can be seen from this graph that allocating (54; 67) = 79% of the
processor to the application enables 91% of the frames to be decoded on time.
Allocating less than peak resources means that the application now misses some
of its deadlines (9% in this case). Even though the method of resource allocation
is similar to that used by periodic HRT systems with priorities assigned according
to RM, the system has become SRT. In this type of system, resource requirements
(and hence QOS parameters) are not known exactly, but their distributions may
be known. QOS requirements could be described in terms of the probability that
a deadline will be met. Given the distribution of run times either derived from a
model, or as a histogram resulting from a previous run, it is possible to calculate
how much resource to allocate to meet the desired percentage of deadlines.
Allocation of a fixed amount of processor time to an application as done in the
previous section is an example of a reservation strategy. A disadvantage of such
strategies is that, when used in conjunction with bursty resource requests, their use
can result in poor resource utilisation. Figure 3.10 plots frame number versus the
40

0
10
20
30
40
50
60
70
80
90
100
0 10 20 30 40 50 60 70
Percentage
of
Frames
Decode Time (milliseconds)
(54
milliseconds,
91%)
(67
milliseconds,
100%)
Figure 3.9: Run time allocated to decoder versus percentage of frames which can be
decoded within that time.
time to decode the frame for two different video streams, along with the total time
to decode both streams (this is just the sum of the two times). From this graph,
it is seen that reserving peak processing times for the two streams would require
67 + 69 = 136 milliseconds per frame, but the peak total processing time required is
only 120 milliseconds per frame. Statistical multiplexing aims to exploit this prop­
erty by allocating resources based on the combined requirements of a number of
sources rather than their individual requirements. If statistical multiplexing is to
be used for processor allocation, run time resource allocation can be modelled as a
D=G=1 queue, assuming deterministic (periodic) process arrivals and generally dis­
tributed processing times. Within this model, an important QOS parameter would
be the probability that the service time of a given arrival will exceed its deadline.
A typical implementation would select a priority based service discipline on the
grounds that these are known to provide higher resource utilisations. Additionally,
the models presented so far have assumed that the arrival processes are deterministic
and periodic. If CM data are presented to applications as motion compensated video
or silence suppressed voice for example, then arrivals will be sporadic, requiring the
incorporation of stochastic arrivals into the model.
41

0
10
20
30
40
50
60
70
80
90
100
110
120
0 500 1000 1500
Decode
Time
(milliseconds)
Frame Number
Stream Trace Max Min Dev
1
2
1+2
67 20 9
69 28 8
120 56 14
Figure 3.10: Frame number versus time to decode two compressed video streams.
3.9 Accounting
Ensuring that an application receives the QOS it requested requires a means of
accounting for the resources used by the application. Current monolithic kernels
already do this when they maintain a running total of the time spent by an appli­
cation in both user and supervisor mode. Accounting is performed by charging the
cost of the resources used to the accounting structure which is associated with the
currently executing user­mode protection domain. In the case of a system struc­
tured as a number of clients and servers running on top of a microkernel, accounting
becomes complicated by the fact that a single client may need to interact with a
number of servers during its execution.
3.9.1 Credits
One approach to solving this problem is via a system of credits. An application is
allocated credits at a rate determined by its PB and, whenever it interacts with a
server, it nominates a number of its credits which are to be used for the interaction.
These credits are debited from the application's account and deposited into the
server's account so that the server may do work for each of its clients on the basis
of the credits it has received from them. This approach separates the accounting
42

function from a process's address space. Its disadvantages include:
- it is possible for a server to use resources given to it by one client for other
purposes;
- it requires some knowledge of whether a particular server is on the same system
as the client or on a remote one and;
- it increases the overhead required for a client­server interaction.
3.9.2 QOS
Another approach is to have the client request a connection to a server with a
particular QOS. The client and server then perform the negotiation and reservation
actions described in previous sections. Thereafter, if the QOS can be supplied, the
server knows the resources which will be required to service any requests which arrive
on that connection. This has the advantages of not adding to the overhead of client­
server interactions and fitting in well with the notion of end­to­end QOS even when
the client and server are located on different machines. Among its disadvantages
are that a server has to perform some of the QOS management functions itself, and
that these include the policing functions, so poorly constructed servers may promise
qualities of service which they do not deliver. This last problem is common to both
approaches and currently may be addressed by observing that people will tend not
to use badly­behaved servers.
3.10 Policing
Policing occurs at two levels in the system. At the low level, a mechanism is required
to ensure that an application does not exceed its allocation and start consuming
resources which are reserved by another application. An appropriately designed
dispatcher can ensure that processor time is accurately meted out. At a higher level,
a means is required to ensure that the writers of applications do not request excessive
resources to ensure that their applications perform acceptably. Such behaviour will
result in poor resource utilisation and the informed user of a workstation will tend to
prefer programs which are more frugal with workstation resources. In a commercial
environment, being charged for the resources used to run a program may achieve
similar results.
43

3.11 Application Design
Since the QOS environment often does not guarantee absolutely to give an applica­
tion all of the resources it requires, applications must be able to produce as good
a result as possible with the resources which they are given. This is in contrast to
real­time approaches of resource allocation, but in many respects is more realistic; to
be able to offer absolute guarantees requires knowledge of the future. Applications
are written either so that they assume they have a minimal resource availability as
described by their QOS contract and try to make use of resources which fortuitously
become available, or they always assume the best possible QOS and have the means
of producing an acceptable result of poorer quality when peak resource requirements
cannot be met. In either case, applications may be written so that they can produce
results of varying quality.
3.11.1 Temporal Degradation
In timesharing systems, when resources are scarce, process execution degenerates
by taking longer to complete. This form of degeneration is not appropriate for some
CM applications, so an alternative is to decouple the rate at which processing is
performed from the data arrival rate, select the most recent data and process them
to completion. The decoder application could reduce its processor bandwidth from
(67; 67) = 100% to (33; 67) = 50% by halving its frame rate.
3.11.2 Spatial Degradation
The processor bandwidth required by the decoder application could also be reduced
by shrinking the size of the video format being presented. This could be done at
either the video sink or the video source by subsampling.
3.11.3 Logical Degradation
The performance of some algorithms may degrade logically if they are capable of
producing results of reduced but acceptable accuracy on time. These algorithms may
be implemented as imprecise computations. [Liu91] identifies a number of different
types of imprecise computation and presents approaches for scheduling them. A
task is monotone if the quality of its intermediate results does not decrease as it
executes. The milestone method records intermediate results and associated errors
44

at defined points in a computation, so that the intermediate result of a task is its
value at the last completed milestone. A task can be constructed as a sequence of
seive functions, one or more of which may be skipped during execution to reduce the
amount of time it requires. The multiple version method employs a primary and an
alternate version of a task. The primary version takes longer to produce a precise
result while the alternate version produces an imprecise result more quickly. During
transient overload, the system can execute alternate versions of tasks.
Tasks ø i of these types are modelled as a mandatory subtask and an optional subtask
o i . Algorithms are presented for scheduling subtasks such that the m i are guaranteed
to run to completion. For each of the o i , a processor time oe i is allocated so that
some function of their errors ffl i = o i \Gamma oe i is minimised. It is assumed that release
times r i , deadlines d i and the computation times required by the subtasks m i and o i
are known a priori. Typically the m i are scheduled using a fixed priority assignment
generated by RM which will guarantee their execution. In a dynamic environment,
the o i may be scheduled using, for example, EDF.
This type of scheduling can be provided by a QOS contract which offers applications
a guaranteed minimum processor bandwidth with the condition that, should addi­
tional bandwidth become available, it will be offered to the contracted applications.
The success of these scheduling strategies will depend on an application's ability
to make use of them, and the informational property of CM can be exploited to
do this. [Ghanbari89] presents a layered video codec for use on a slotted ring net­
work which is capable of offering fixed, guaranteed bandwidths as well as variable,
additional bandwidth. The codec uses a transform based algorithm to produce a
motion compensated stream of guaranteed packets and a DPCM based algorithm
to produce a stream of enhancement packets. The guaranteed packets contain the
basic picture and motion information and are allocated a fixed amount of guar­
anteed bandwidth. The enhancement packets contain the error difference between
the original image and the image reconstructed from the guaranteed packets. The
enhancement packet stream is bursty and is transmitted through a VBR channel
when bandwidth is available. When the VBR channel allows transmission of the
entire enhancement stream, a high quality picture can be reconstructed by the de­
coder using both the guaranteed stream and the enhancement stream. At the very
worst, when the VBR channel does not carry any enhancement packets, the received
picture quality degrades to what can be reconstructed from the guaranteed stream.
In the same way that layered coding makes use of the guaranteed and additional
bandwidths in a network, layered processing can be used to take advantage of the
processor time allocations associated with QOS contracts. At the application level,
an example of the use of layered processing would be the presentation of video frames
45

to a display application such that each frame is decomposed into a number of layers,
with each layer representing a milestone and successively refining the accumulated
image. Another example would be the presentation of stereo audio to an application
as two streams, one containing the sum of the left and right channels (L + R), the
other containing their difference (L \Gamma R). The audio application can simply use
(L + R) to produce a monophonic signal or, given some extra processing time can
compute a stereophonic signal by adding the two inputs to obtain 2L and subtracting
them to obtain 2R. The advantage of using these types of computations is that they
provide a direct control over the quality of their results by varying the amount of
processing resource they are allowed to use.
Applications which use layered processing can benefit from a knowledge of the type of
processing time which they are currently receiving. Consider an application holding
a contract which provides it with a guaranteed minimum processor time and affords
it additional time should any become available. If the application were informed of
the type of processor time it is about to receive whenever it is given the processor,
it could use this information to decide whether it ought to execute mandatory or
optional code. This information can be provided by the operating system as part of
the VPI seen by the application. Section 4.7 discusses the effects which this has on
the design of the VPI.
The fact that CM are amenable to layered processing provides a different perspective
on scheduling problems. Instead of determining the processor time required by
an application and constructing schedulers to accommodate this processing time
completely, layered processing and imprecise computations enable the system to
dictate the processing time which the application will receive, trading off quality for
computational resources.
3.11.4 Data Representation
The preceding section brings to light an important point about the representation
of data used by applications which can vary the quality of their results. The manner
in which an application degrades is specific to the application and this will directly
affect the representational requirements of the data with which the application is
presented. A layered coding scheme for video data which is to be viewed by a
human could split the video into high and low frequency components and transmit
these to a decoder. The low frequency components could be reconstructed to form
the minimal quality picture and the high frequency components used to refine the
picture. If the observer of the video were a program which did edge detection, then
it might be better to transmit some high and some low frequency components for
the basic picture and use the intermediate frequencies to refine it.
46

3.12 Summary
QOS has been presented as a paradigm for resource management within an operat­
ing system. It has been shown that QOS can meet a variety of resource allocation
requirements ranging from those of hard real­time to soft real­time applications; in
the case of soft real­time applications, a number of metrics have been presented
which enable their QOS to be quantified. A means of mapping high level QOS de­
scriptions onto low level QOS parameters has also been presented. It is recognised
that the range of QOS which a system can provide is determined by the combination
of the QOS manager and RTRA; the basic mechanisms required within an operat­
ing system to support these types of resource management include accounting and
policing. QOS contracts may give applications fewer resources than they require,
so the quality of any results produced may degrade. Providing applications with a
knowledge of the current availability of their resources can help them control the
manner in which their performance degrades. The remaining chapters describe the
design and implementation of a system which provides this information, along with
an example application which makes use of this information.
47