One of the new features of the textbook for the course is a detailed discussion of multimedia operating systems, in particular, issues involved in the design of an operating system whose primary job is serving videos.
Video on demand over the Internet by sites such as Hulu, YouTube or Netflix is becoming extremely important, and, for Netflix, will largely replace mailing DVDs within a few years. Video on demand requires huge servers. The system has to be able to access, say, 1000 disks, and distribute signals to the distribution network at high speed in real time.
The NTSC (National Television Standards Commission) standard specifies 30 frames per second, or one frame every 33.3 msec. If each frame is 640 by 480 bytes, a raw image is 307,200 bytes per frame. At 30 frames per second, the server has to send out 9,216,000 bytes per second or 55,296,000 bytes per minute for each movie. This means that multimedia files are enormous. A two hour uncompressed 640x480 movie requires almost 200GB of disk space. But 640x480 format is being replaced by High Definition Television (HDTV). An uncompressed two hour HDTV movie requires 570GB. This means that a video server with 1000 movies needs 570 TB of disk.
The only way for an operating system to be able to do this is to reserve bandwidth, CPU, memory, etc. ahead of time. So the server has an admission control algorithm; it cannot accept a new request unless it can be reasonably confident that it will be able to satisfy it.
Uncompressed movies are far too big to transmit. Thus the system needs a compression (encoding) algorithm and a decompression (decoding) algorithm. The former can be slow and/or expensive, because it is only done once, but the latter has to be fast. Unlike a regular file compression algorithm, an image compression algorithm can be lossy. This means that some data can be lost.
The standard compression algorithm for still images is JPEG. It uses spatial redundancy to compress an image. A complex picture with lots of detail (not much spatial\ redundancy) cannot be compressed much, but a picture where, for example the whole top half of the image is more or less uniform blue sky, and can compressed quite a lot. This is explained in detail in your text, and is not a topic for operating systems, so I will not cover it here.
The standard video compression algorithm is MPEG, which is also covered in detail in your text. Briefly, each frame is initially treated as a JPEG. Note that there are 30 frames per second (in the US) in a movie. Sending every frame as a JPEG would be hugely expensive in terms of bandwidth and other resources, but there is enormous temporal redundancy in movies. In general frame x+1 is pretty similar to frame x. The MPEG compression algorithm makes good use of this by only sending the changes from the last frame.
There are three types of MPEG frames
But this is just the video. A movie also needs an audio sound track, and usually several other streams as well, such as sound tracks in several different languages, subtitles, and a separate fast forward stream.
Multimedia Process Scheduling
An operating system whose primary job is serving videos would differ from a traditional operating system in three ways.
But you need a timing mechanism to make sure that each process runs at the correct frequency. Run a clock with 30 ticks per second. At each tick, all threads are run sequentially in the same order, when a thread is done, it issues a suspend system call that releases the CPU. This algorithm works perfectly as long as the number of threads is small enough.
But there is a problem. The frame sizes for MPEG differ in size, and processes come and go. So this leads us into a discussion of general real timeprocess scheduling.
Real Time Process Scheduling
From a scheduling point of view, the definition of real time means that at least some of the processes have strict deadlines that must be met. Late equals wrong. A distinction is often made between soft real time scheduling, in which achieving deadlines is usual met, but is not guaranteed, and hard real time scheduling, in which meeting deadlines is guaranteed.
Real time scheduling can be either periodic in which deadlines happen at regular intervals, or aperiodic, in which deadlines happen unpredictably. Video is the classic example of periodic real time scheduling. There are three parameters.
It is possible that there is no scheduling algorithm which can satisfy this requirement. This formula tests this.
In this formula m is the number of processes, 3 in this case, Pi is the period of Process i, and Ci is the amount of CPU time needed per cycle.
Substituting our data into this formula
10/30 + 15/40 + 5/50 = .333 + .375 + .100 = .808
Since this is less than 1, the problem is potentially solvable.
Your text discusses two algorithms to address this problem. Both of these assume that we know this information in advance (a reasonable assumption, at least in the case of video) and that there is no overhead associated with context switching (not reasonable, but it makes things much easier).
Rate Monotonic Scheduling (RMS) With RMS, each process has a priority based on its frequency; the higher the frequency, the higher the priority. Then the system just has to run the process with the highest priority, with a higher priority process preempting a lower priority process if necessary. However, we need the caveat that a cycle for each process only begins at the time of the prior deadline; otherwise we would just always run the process with the highest frequency.
Earliest Deadline First Scheduling (EDF) As the name implies, just run the process with the earliest deadline. No preemption is necessary.
Here is a diagram from your text showing how these two algorithms work with the above data.
Simulations show that overall, EDF is a better algorithm; your text shows an example where RMS fails while EDF does not. However EDF is tricky to implement, and so, at least for soft real time systems RMS is often used.
Placing multimedia files on disk
The file systems that we have discussed earlier do not work well with multimedia.
Ordinary file systems are PULL, which means that the user requests data from the file system. Whenever a process wants to read data from a file, it calls read. Multimedia file systems can be, and usually are, PUSH, which means that the file system pushes data to the user process without the user having to issue a request. Specifically, the process issues an inital start command with some parameters, and the I/O system then just sends frames periodically, without further requests from the process. It is up to the process to handle the data as it is sent.
Another problem is how to implement VCR control functions (Pause, fast forward, fast backward, rewind) Pause and rewind are trivial, but the other two are not. With MPEG you can't just implement FF by sending every tenth frame, because most of the frames do not have all the information, they are P frames, just containing the differences from the previous frame. You could also just play the movie ten times faster, but this is usually impossible. The best solution is to have another stream, the fast forward stream (and the fast backward stream).
How a file is placed on the disk is very important, but note that the constraints are completely different than for more general purpose systems. Files can be written once, and we know that they will never grow or shrink, so we can have a lot more control over placement. First it is crucial to have all of the data for a frame together so that the disk will never have to do a seek in the middle of a frame. This usually means not only the MPEG portion, but also all of the other streams as well, such as the various audio streams (English, German, etc).
There are two basic approaches.
The most popular movies should be stored near the center of the disk. The organ pipe algorithm says to put the most popular movie at the center of the disk, with the second and third most popular movies on either side, the fourth and fifth most popular next, and so on.
Note that strategies like this are possible with multimedia file systems because these files do not grow and shrink over time like ordinary files do.
In fact, most multimedia servers use disk farms, i e. a cluster of many disks, to store the data. Note that you do not need to use RAID structures with these. One of the main benefits of RAID is to prevent data loss in the event of a crash, but this is less important for video servers since there is a backup dvd. However, you still might want to do some sort of striping, i.e. putting each movie on stripes on many disks, because if many people decide to watch a particular movie, (a very common occurence), striping would spread the load over many disks.
Disk scheduling can be done very efficiently. We can define a round as all of the reads in a particular time slice. With NTSC there would be 30 rounds per second. For each round, all of the reads are known, so they can be scheduled with maximum efficiency. This is called the scan-EDF algorithm. For example, collect the five requests with the earliest deadlines as a batch, sort them in cylinder number, and use the elevator algorithm.
Note that there is no reason to do traditional caching for video servers.
Return to the course home page