Chapter 18 Resource Allocation and Deadlock
Objectives
To establish the requirement for the dynamic allocation of objects and to study the possibility that deadlock can result from this. To study how deadlock can be detected, prevented and avoided.
Points to emphasise
- If you have complete, static information of the objects required by processes and the order in which they are requested you can plan a schedule in advance and can avoid the possibility of deadlock.
- There are allocation policies that lead to the possibility of deadlock: exclusive access (in the sense that a request can be refused); hold while waiting; and no pre-emption. If these policies must be used for the dynamic allocation of certain objects then it is possible that the order of requests for these objects by processes will be such that deadlock occurs.
- One approach to the management of resource allocation is to grant every request that you can, delay any request that you can’t grant and detect deadlock. If you have no information about the resource requirements of processes in advance of their requests this is all you can do.
- If you have more information, such as the total resource requirements of each process, you can devise algorithms to prevent deadlock.
Possible difficulties
The deadlock detection algorithm often seems counter-intuitive. Emphasise that we are looking for a cycle that exists NOW. Any resources that are not involved in such a cycle can be put back in the pool (at the moment). If we run the algorithm again later, after more requests have been made, these resources may have become part of a cycle.
Teaching hints
- Give examples of deadlock, livelock and starvation from many areas: concurrent programming, communications protocols, OS resource allocation, DB etc.
- Give practical examples to reinforce understanding of the algorithms.
These can again be taken from different application areas.
- Exercise 16.5 can be used as a small project on the dining philosophers problem. Pages 80 - 84 of this guide contrast solutions which are specific to that problem (of symmetric concurrent processes) with the general approaches to deadlock detection and prevention given in this chapter.
- In discussing how a system might recover from deadlock, point out that we shall be looking at this for transaction processing systems throughout Part III.
- The appendix covers two centralised mutual exclusion algorithms in detail and three approaches to distributed mutual exclusion algorithms. A discussion of deadlock is included in the text and the exercises. This aspect of the appendix could be used here.