CSA402

Lecture 10 - Multimedia Operating Systems

References:
Steinmetz, R., and Nahrstedt, K. (1995). Multimedia: Computing, Communications & Applications. Prentice Hall. Chapter 9.

Introduction

Multimedia applications typically operate in a distributed environment in which there is a mixture of discrete and continuous data, some sourced locally and some remotely. Traditional Operating Systems and distributed environments have been developed with largely the processing of discrete media in mind. Real-time systems have been used in the domains of manufacturing, automobile control and avionics (e.g., fly-by-wire), and time-critical life-threatening environments, such as power plant control systems.
The advent of continuous multimedia data types to the domain of distributed end-user systems means that popular operating systems (e.g., UNIX, Microsoft Windows, OS/2 and MacOS) need to deliver real-time capabilities to desktop computers.

Issues

Why do multimedia applications require real-time processing? "Real-time" systems are really systems which are capable of guaranteeing that data can and will be processed within certain time restrictions. Traditionally, the only restrictions placed on the processing of data or execution of processes was that these happen "as quickly as possible". Unfortunately, this is too vague for continuous media types, because delays in processing data, even in the order of milliseconds, can result in human users noticing jitter in the playback of audio-visual material. In face-to-face dialogs, unacceptably long delays in the transmission and processing of data can result in a violation of the perception of real-time communications. Systems capable of giving these guarantees are said to offer Quality of Service (QoS) guarantees.
In order to guarantee that a data stream will be processed within QoS parameters, resource and process management functions need to be adjusted. In a distributed environment, the network is an important resource which can also be a major source of delay, as it is not under complete control of the computer or computers engaged in the multimedia session. Similarly, in a distributed environment, resources required by the owner computer, might in fact be loaned out to remote computers. Other operating system functions, such as the file system and peripherals, also need to address the issues and requirements of real-time processing, but are beyond the scope of this lecture series.

Characteristics of real-time requirements

Events can occur at either a priori known points in time, or else they can be random. An example of a random event is an incoming network event, and an expected event is a scheduled event. In either case, the real-time system must receive data from or deliver data to the environment within certain time constraints.
If the only events that occur are predetermined ones, then the real-time system has the relatively simple task of scheduling the events so that they can complete within the given time constraints. The real-time system must know in advance what the time constraints are, and also what resources the processes will require. As usual, there may not be enough resources to satisfy all the process requests, in which case the scheduler must schedule processes so that all processes can obtain all the resources they require and complete according to their deadlines without compromising the integrity of other processes. However, a real real-time operating system also has to contend with unscheduled, or random, events which are also time-critical, and which will compete for limited resources.
For these purposes, a real-time system distinguishes between soft and hard deadlines. A soft deadline is a deadline which, although time-critical, will not produce an unacceptable result if it is not met, or if it is met a bit late. If a single frame in a video-conferencing session is dropped, it is not a complete disaster. It may also be acceptable if the frame is slightly delayed. However, if too many successive frames are dropped, or if the delay is too great, then it should not be tolerated. Hard deadlines are deadlines which if missed result in system failure.
Real-time systems are characterized by having predictably fast responses to time-critical events and accurate (shared, in a distributed environment) timing information. They must also have a high degree of schedulability, which refers to the degree to which resources can be concurrently utilized without jeopardizing reliability. Even if too many real-time events require simultaneous processing, the system must remain stable. Usually, the system becomes overloaded in times of emergency - it could be disastrous if a real-time system failed to process critical tasks.

Resource Management

The transmission and processing requirements of local and distributed multimedia applications can be specified according to the following characteristics, which are known as the QoS parameters:

Throughput: determined by the data rate of the connection to satisfy the application requirements and the size of the data units
Local and end-to-end delay
1. Local delay: the maximum time span for the completion of a certain task being performed by the resource
2. End-to-end delay: the total delay for a data unit to be transmitted from the source to its destination
Delay jitter: the maximum allowed variance in the arrival of data at the destination
Reliability: error detection and correction mechanisms. Errors can be ignored, indicated, and/or corrected. Forward error correction mechanisms are more appropriate for time-critical data, because re-transmitting the correct data implies a delay which will probably violate the timing requirements

Although individual applications may have their own requirements specified as constants, usually there are boundaries within which the application will still receive an acceptable service. For this reason, the allocation of resources is negotiated between the client application and the resource manager.
The client will request a resource by specifying a QoS specification. The resource manager will check its own resource utilization and will decide whether the reservation request can be served. If a request cannot be granted immediately, it is queued. Although this might seem odd, in a real-time environment, one must bear in mind that it is more important that playback of a continuous data stream is smooth, than to immediately start playing back the stream. It may be more acceptable for the user to wait a while until uninterrupted playback can start, than it would be for playback to commence immediately but suffer jitter delays.
When a request for a resource is received, the resource manager will perform a Schedulability Test to determine if there is sufficient resource capacity to handler the request. The resource manager will then perform a QoS Calculation to determine the best possible guarantee for the request and allocates the required capacity (Resource Reservation). Finally, through Resource Scheduling, incoming messages from connections are scheduled according to the given QoS guarantees. Different scheduling algorithms for different resources can be defined. The schedulability test, QoS calculation and resource reservation depend on the algorithm used by the scheduler.

Continuous Media Resource Model

In order to manage resources whilst guaranteeing a quality of service in a distributed environment, the chain of resources traversed by data on its end-to-end path are often modeled using the Continuous Media Resource Model. This in turn is based on the model of Linear Bounded Arrival Processes (LBAP).
In this model, the data stream consists of Logical Data Units. An LDU is an individual data unit in a sequence of units which are time-dependent. In the context of LBAP, LDUs are known as messages. When retrieving continuous data, the original analog signal was sampled, and as such the data stream is highly periodic - the samples must be played at regular intervals. The compressed data forming each sample may be highly irregular, as the compressed data representing each sample may require different amounts of bandwidth (if they are variable length coded). However, there is a definite maximum message size.
In the LBAP model, a burst of messages consists of messages that arrive ahead of schedule. LBAP is a message arrival process at a resource defined by three parameters:

M = Maximum message size, in bytes
R = Maximum message rate, per second
B = Maximum burstiness, in messages

Example

Two workstations are connected by a LAN. A CD player is attached to one workstation. Single channel audio data are transferred from the CD player over the network to the other computer, which has speakers attached. The audio signal is sampled 44,100 times per second, and each sample is coded in 16 bits. Hence, the data rate is

R_byte = 44100Hz x (16bits/8bits/byte) = 88200bytes/second

The CD prepares data for transmission as messages by assembling samples into frames. The CD-format standard decrees that 75 frames are assembled per second of audio (R). Therefore, the maximum message size is

M = (88200bytes/second / 75messages/second) = 1176bytes/message

For transmission over the LAN, up to 12000bytes are assembled into a packet. The maximum number of messages per packet is

B = (12000bytes/1176bytes/messages) >= 10 messages

This represents a burst, where data is being carried over the network in bulk. We assume that there is only one route between the client and server, so it is not possible for packets to arrive out of sequence. The LAN may also be capable of carrying 10Mbits of data per second (roughly equivalent to 1.2Mbytes/s, or less than 1000 audio frames per second). However, a single second of audio can be carried by only 75 frames. We need to limit the number of frames that are transmitted so that we don't overload the client and the network. We can state that during a time interval t, the maximum number of messages received by the client must not exceed

M' = B + (R x t) messages

For example, assuming that t is 1 second:

M' = 10 messages + (75 messages x 1 second) = 85 messages

This allows for short time violations of the rate constraint. The maximum average data rate of the LBAP is

R' = M x R bytes per second

E.g.,

R' = 1176bytes/message x 75 messages/s = 88200 bytes per second

As a limited number of messages can arrive earlier than required, we need to define a buffer size to temporarily store them on the client. If the buffer size is too small, that data will be lost, but if the buffer size is too big, then memory will be under utilized. The buffer size is defined to be

S = M x (B + 1) bytes

For example:

S = 1176 bytes/message x (10 + 1) messages = 12936 bytes

These calculations let us estimate the logical backlog (the messages which have already arrived ahead of schedule), the logical arrival time of messages (the earliest time a message can arrive ahead of schedule, when all messages arrive at their rate), the guaranteed logical delay (the maximum delay between a message's earliest arrival time and its latest completion time), and the number of work ahead messages (the number of messages that arrive ahead of schedule, and which can be immediately processed if the resource is idle).

A message is deemed to be critical if its logical arrival time has passed.

Process Management: Process Scheduling

Continuous media data processing must occur in exactly predetermined, and usually periodic, intervals. Operations on these data are repetitive and must be completed by certain deadlines. The scheduler is responsible for loaning out the CPU to processes that require it while maintaining guarantees that other processes which are waiting for the CPU will complete by their deadline.
Two conflicting goals must be considered:

No starvation of non-critical tasks (e.g., text, graphics processing)
No priority inversion of time-critical tasks

Real-time Scheduling: System Model

A task is a schedulable entity which has timing constraints and resource requirements. In many multimedia environments, there is no independence between tasks.
A periodic task T has the following parameters:

s: a starting point
e: the processing time of T
d: the deadline of T
p: the period of T
r: the rate of T (r = 1/p)

Consider the following example. A 5 second long sound bite of CD-quality audio has a definite start time s. The sound bite has a period of 5 x 44,100 samples, where each sample must be processed at a rate r of 1/44,100th of a second, and e is the amount of time required to process each sample. Once the audio playback starts, the samples must be processes at these regular intervals. The deadline d indicates by when a sample must be delivered to the speakers. 0 <= e <= d <= p. It is assumed that the next sample is ready for processing (i.e., is runnable) within the deadline for the processing of the previous sample. This is known as congestion avoidance deadlines.
A scheduling algorithm is said to guarantee a newly arrived task if it can schedule the new task whilst ensuring that previously guaranteed tasks can be completed by their respective deadlines. This is only possible if the parameters described above are available to the scheduler.

Earliest Deadline First Scheduling Algorithm

EDF is one of the best known algorithms for real-time scheduling. Every time the scheduler runs, it selects the task with the earliest deadline, from amongst those that are runnable. Processes request the CPU using the LBAP model described above. If the CPU is reserved by a process, the EDF must run to determine the new order of processes in its ready queue. If a new process has an earlier deadline than the current process, the current process is preempted, and the suspended process is rescheduled according to EDF.
EDF is an optimal dynamic algorithm. If there is a sequence in which all tasks can complete within their deadlines, then the algorithm will find it, even in a dynamic environment.
EDF can be considered to be a priorty-based pre-emptive scheduler, where processes are assigned priorities according to their deadlines. One specific difference from traditional priorty-based pre-emptive schedulers is that in the latter case, there are usually a limited number of assignable priorities, and all processes with the same priority will be processed in a strict FIFO order. In a real-time environment, the granularity of priorities is likely to be finer, resulting in a large number of tasks being reordered. In the worst case, all processes will need to be reordered, as they become critical.

Back to the index for this course.
In case of any difficulties or for further information e-mail [email protected]

Date last amended: Wednesday, 10 March, 1999