Note that there is a lot of reading associated with this class; you can skip all of the reading on deadlock avoidance (6.5), and the details of JPEG, MPEG, and audio compression (except that you need to know what I, P and B frames are in MPEG), and everything on Near Video on Demand
Solutions to deadlock
There are several ways to address the problem of deadlock in an operating system.
The text refers to this as the Ostrich Algorithm. Just hope that deadlock doesn't happen. In general, this is a reasonable strategy. Deadlock is unlikely to occur very often; a system can run for years without deadlock occurring. If the operating system has a deadlock prevention or detection system in place, this will have a negative impact on performance (slow the system down) because whenever a process or thread requests a resource, the system will have to check whether granting this request could cause a potential deadlock situation.
If deadlock does occur, it may be necessary to bring the system down, or at least manually kill a number of processes, but even that is not an extreme solution in most situations.
Deadlock detection and recovery
As we saw above, if there is only one instance of each resource, it is possible to detect deadlock by constructing a resource allocation/request graph and checking for cycles. Graph theorists have developed a number of algorithms to detect cycles in a graph. The book discusses one of these. It uses only one data structure L a list of nodes.
A cycle detection algorithm
For each node N in the graph
The algorithm needs to search each node; let's start at node P1. We add P1 to L and follow the only edge to R1, marking that edge. R1 is now the current node so we add that to L, checking to confirm that it is not already in L. We then follow the unmarked edge to P2, marking the edge, and making P2 the current node. We add P2 to L, checking to make sure that it is not already in L, and follow the edge to R2. This makes R2 the current node, so we add it to L, checking to make sure that it is not already there. We are now at a dead end so we back up, making P2 the current node again. There are no more unmarked edges from P2 so we back up yet again, making R1 the current node. There are no more unmarked edges from R1 so we back up yet again, making P1 the current node. Since there are no more unmarked edges from P1 and since this was our starting point, we are through with this node (and all of the nodes visited so far).
We move to the next unvisited node P3, and initialize L to empty. We first follow the unmarked edge to R1, putting R1 on L. Continuing, we make P2 the current node and then R2. Since we are at a dead end, we repeatedly back up until P3 becomes the current node again.
L now contains P3, R1, P2, and R2. P3 is the current node, and it has another unmarked edge to R3. We make R3 the current node, add it to L, follow its edge to P4. We repeat this process, visiting R4, then P5, then R5, then P3. When we visit P3 again we note that it is already on L, so we have detected a cycle, meaning that there is a deadlock situation.
Once deadlock has been detected, it is not clear what the system should do to correct the situation. There are three strategies.
Deadlock avoidance
The above solution allowed deadlock to happen, then detected that deadlock had occurred and tried to fix the problem after the fact. Another solution is to avoid deadlock by only granting resources if granting them cannot result in a deadlock situation later. However, this works only if the system knows what requests for resources a process will be making in the future, and this is an unrealistic assumption. The text describes the bankers algorithm but then points out that it is essentially impossible to implement because of this assumption.
Deadlock Prevention
The difference between deadlock avoidance and deadlock prevention is a little subtle. Deadlock avoidance refers to a strategy where whenever a resource is requested, it is only granted if it cannot result in deadlock. Deadlock prevention strategies involve changing the rules so that processes will not make requests that could result in deadlock.
Here is a simple example of such a strategy. Suppose every possible resource is numbered (easy enough in theory, but often hard in practice), and processes must make their requests in order; that is, they cannot request a resource with a number lower than any of the resources that they have been granted so far. Deadlock cannot occur in this situation.
As an example, consider the dining philosophers problem. Suppose each chopstick is numbered, and philosophers always have to pick up the lower numbered chopstick before the higher numbered chopstick. Philosopher five picks up chopstick 4, philosopher 4 picks up chopstick 3, philosopher 3 picks up chopstick 2, philosopher 2 picks up chopstick 1. Philosopher 1 is hungry, and without this assumption, would pick up chopstick 5, thus causing deadlock. However, if the lower number rule is in effect, he/she has to pick up chopstick 1 first, and it is already in use, so he/she is blocked. Philosopher 5 picks up chopstick 5, eats, and puts both down, allows philosopher 4 to eat. Eventually everyone gets to eat.
An alternative strategy is to require all processes to request all of their resources at once, and either all are granted or none are granted. Like the above strategy, this is conceptually easy but often hard to implement in practice because it assumes that a process knows what resources it will need in advance.
Livelock
There is a variant of deadlock called livelock. This is a situation in which two or more processes continuously change their state in response to changes in the other process(es) without doing any useful work. This is similar to deadlock in that no progress is made but differs in that neither process is blocked or waiting for anything.
A human example of livelock would be two people who meet face-to-face in a corridor and each moves aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.
Addressing deadlock in real systems
Deadlock is a terrific theoretical problem for graduate students, but none of the solutions discussed above can be implemented in a real world, general purpose operating system. It would be difficult to require a user program to make requests for resources in a certain way or in a certain order. As a result, most operating systems use the ostrich algorithm.
Some specialized systems have deadlock avoidance/prevention mechanisms. For example, many database operations involve locking several records, and this can result in deadlock, so database software often has a deadlock prevention algorithm.
The Unix file locking system lockf has a deadlock detection mechanism built into it. Whenever a process attempts to lock a file or a record of a file, the operating system checks to see if that process has locked other files or records, and if it has, it uses a graph algorithm similar to the one discussed above to see if granting that request will cause deadlock, and if it does, the request for the lock will fail, and the lockf system call will return and errno will be set to EDEADLK.
Communication Deadlock
Another variant of deadlock which is very common is Communication Deadlock. Many communication protocols involve one side sending a request to the other side, and the other side replies. If the request is somehow lost, then both sides are left waiting for an event which will never occur.
The simple and obvious solution to this is that when either side sends a message to the other, it sets a timer, and if after a while, no acknowledgement is received, the message is sent again.
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. As I was working on this lesson, it occurred to me that I was just paraphrasing the book for this material. As a result, this on-line lesson is abreviated. Do not assume that just because a video topic is not covered here, it is not important. Read this chapter closely.
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 images is JPEG. This is explained in detail in your text, and so I will not cover it here. The standard video compression algorithm is MPEG, which is also covered in detail in your text. Make sure that you understand how these work.
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 processe have strict deadlines that must be met. Late equals wrong. Real time sheduling 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.
Sustituting 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.
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. 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.
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. 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).
All of the frames for a movie should be stored together to minimize head movement. Of course this breaks down if there are multiple files stored on one disk, and several of them are being read at the same time.
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 because 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 usually 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 accurately. 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.
Note that there is no reason to do traditional caching for video servers.
Return to the course home page