We’ve seen that we can prevent deadlock absolutely by removing any one of the three conditions necessary for it to occur. We’ve also seen that the cost of removing these conditions is very high, in terms of damage to data sets (if we allow resources to be taken away from a deadlocked process), decreased efficiency in the use of resources (if we require preallocation or do not allow multitasking) or other bad effects. We’ve also seen very little that an individual application programmer can do about the three deadlock conditions – most of the solutions we’ve talked about have had to be implemented by the operating system. Are there some methods that we can employ to let programmers protect their own programs and data? Perhaps we can find some shared-responsibility solutions that can be employed to prevent deadlock in a fashion, like the use of locks prevented lost updates.
Actually, there are many solutions like this that are employed to reduce the damage caused by deadlock, and each solution has its own strengths and weaknesses. A full study of these solutions is beyond the scope of this course and will have to wait for systems programming, hardware, and database courses to come. Still, we can look at a few possible solutions to see how these problems are approached.
A good place to begin is by asking questions. Here are a couple of good ones.
1. Why can’t the operating system do a better job of
resolving deadlock by taking resources from programs only if it won’t mess up
the program’s data?
2. Why can’t the application programmers write their
own programs in such a way that they can detect and resolve deadlock?
Before reading on, it would be a really good idea for you to try to come up with answers for these questions. I’ll wait as long as you want.
OK, ready to go on? Here are my answers to these questions.
Probably the best answer for question 1 is that the operating system doesn’t know very much about any running application program. It can’t tell if data would be corrupted by taking resources away or by killing the application process.
As for question 2, remember that when a program is in deadlock it’s not running. If it’s not running, it can’t do ANYTHING, - detect deadlock, decide how to deal with it, make backups of data, scream for help, ANYTHING.
Now that we understand why operating systems and applications programs have difficulty with deadlock, can we change anything to fix the problems?
Could we fix problem 1 by training/requiring the applications programmers write their program in a standardized way that included making information on the status of the program’s data available to the operating system?
Again, it would be good for you to try to answer that question for yourself. Think about what that would mean to the application programmers, and also think about whether or not it would solve the problem.
OK, here’s what I think about it. I’m as big a fan of standardization as the next guy, but I see a problem with it here. Standardization of a rigid interface between application programs and the operating system will tend to put the brakes on the development of new applications for two reasons. It will make the applications harder (and thus more expensive) to write and it will mean that they only work for one operating system, which limits their market.
Even if you assume that we can get past those economic problems, we have a big workability issue remaining. While there may be some cases in which one of the deadlocked programs can be killed without damage, there will be many times when both programs are in ‘unkillable’ states – both have data that will be damaged if their resources are taken away. This strategy will not help at all in those circumstances.
OK, let’s move to question 2, which focuses more directly on the application program. Is there a way we can allow it to keep running so it can deal with deadlock intelligently (making backups, saving temporary files, creating logs, rolling back to a safe state, whatever)?
What if we allowed an applications program to check to see if a resource was available rather than simply trying to acquire it? Let’s suppose that there is a Boolean function called available(), which takes the name of a resource as an argument and returns true if the resource is available for use and false if it is already allocated to another process. Then we could write an application program to check for resources and wait until all were available before actually taking control of them. This is a little like preallocation, except that the application program can ‘preallocate’ resources just for the small sections of the program that need them, rather than for the entire run of the program.
Here’s an example. Let’s say that we have a program for copying a CD. It uses two CDR drives, CDR-1 and CDR 2.
A1. get name of CD to copy
A2. Get control of CDR-1
A3. Mount the original disk on CDR-1
A4. Read the first record
A5. Get control of CDR-2
A6. Mount a blank disk in CDR-2
A7. While there are more records to copy
A8. Write the record to CDR-2
A9. Read another record from CDR-1
A10. Close the copy on CDR-2
A11. Release CDR-2
A12. Release CDR-1
We can see that there is a potential for deadlock caused because we request one CD in step 2 and another in step 5. If the system has only two drives and if another process also needs them both and if it gets control of one of the drives while this process is between steps 2 and 5, we’re dead.
Now let’s rewrite the section using our new available() function.
A1. get name of CD to copy
A2. While not((available (CDR-1) and
available(CDR-2))
A3. Wait 5 seconds
A4. Get control of a CDR
A5. Get control of a CDR
A6. Mount the original disk on 1st CDR
A7. Read the first record
A8. Mount a blank disk in second CDR
A9. While there are more records to copy
A10. Write the record to 2nd CDR
A11. Read another record from
1st CDR
A12. Close the copy on 2nd CDR
A13. Release 2nd CDR
A14. Release 1st CDR
Now we have a loop (steps A2 and A3) which runs until both CDR drives are available. Only when both are available will we get out of the loop and try to get control of both drives, one after another. It appears that we won’t enter the critical section of our program until we have the resources to get through it.
So, does this solve our problem? Think about it and try to answer the question yourself before reading farther.
Unfortunately, no. We’ve reduced the chance of deadlock by reducing the time between the two allocations and we’ve reduced the chance of deadlock farther by checking that both drives are available before we try to allocate either one, but we can still get into deadlock. As an illustration, think about two identical processes, both copying CDs
|
A1. get name of CD to copy A2. While not((available (CDR-1) and available(CDR-2)) A3. Wait 5 seconds A4. Get control of a CDR A5. Get control of a CDR A6. Mount the original disk on 1st CDR A7. Read the first record A8. Mount a blank disk in second CDR A9. While there are more records to copy A10. Write the record to 2nd CDR A11. Read another record from 1st CDR A12. Close the copy on 2nd CDR A13. Release 2nd CDR A14. Release 1st CDR |
B1. get name of CD to copy B2. While not((available (CDR-1) and available(CDR-2)) B3. Wait 5 seconds B4. Get control of a CDR B5. Get control of a CDR B6. Mount the original disk on 1st CDR B7. Read the first record B8. Mount a blank disk in second CDR B9. While there are more records to copy B10. Write the record to 2nd CDR B11. Read another record from 1st CDR B12. Close the copy on 2nd CDR B13. Release 2nd CDR B14. Release 1st CDR |
You should be able to come up with a sequence of steps such that both processes think they can have both drives but they still get involved in deadlock. This is actually the assignment for the next class.
Let’s look at one more possibility. What if the application program had access to a single command called test_and_set()? It would take the name of a resource as an argument and check to see if the resource was available. If it was, it would allocate the resource to the process and return the value true. If the resource was not available, it would return false. Here’s the most important feature of test_and_set() – whether the process gets control of the resource or not it keeps running! It does not get blocked if the resource is unavailable, it just gets false back from the function call. This means that the application programmer can write the program to cope with unavailable resources. For example, we could rewrite the disk-copying processes like this:
|
A1. get name of CD to copy A2. While not((test_and_set (CDR-1) and test_and_set(CDR-2)) A3. release CDR-1 A4. release CDR-2 A5. Mount the original disk on CDR-1 A6. Read the first record A7. Mount a blank disk in CDR-2 A8. While there are more records to copy A9. Write the record to CDR-2 A10. Read another record from CDR-1 A11. Close the copy on CDR-2 A12. Release CDR-2 A13. Release CDR-1 |
B1. get name of CD to copy B2. While not((test_and_set (CDR-1) and test_and_set(CDR-2)) B3. release CDR-1 B4. release CDR-2 B5. Mount the original disk on CDR-1 B6. Read the first record B7. Mount a blank disk in CDR-2 B8. While there are more records to copy B9. Write the record to CDR-2 B10. Read another record from CDR-1 B11. Close the copy on CDR-2 B12. Release CDR-2 B13. Release CDR-1 |
We have to add the clarification that if a process issues a release command for a resource it does not control, nothing happens.
Now, does this prevent these two processes from getting involved in deadlock over the CR drives? We’ll talk about this in class.