Introduction to Deadlocks
In a computer system, we have a finite number of resources to be distributed among a number of competing processes. These system resources are classified in several types which may be either physical or logical. Examples of physical resources are Printers, Tape drivers, Memory space, and CPU cycles. Examples of logical resources are Files, Semaphores and Monitors. Each resource type can have some identical instances.
A process must request a resource before using it and release the resource after using it. It is clear that the number of resources requested cannot exceed the total number of resources available in the system.
In a normal operation, a process may utilise a resource only in the following sequence:
• Request: if the request cannot be immediately granted, then the requesting process must wait until it can get the resource.
• Use: the requesting process can operate on the resource.
• Release: the process releases the resource after using it.
Examples for request and release of system resources are:
• Request and release the device,
• Opening and closing file,
• Allocating and freeing the memory.
The operating system is responsible for making sure that the requesting process has been allocated the resource. A system table indicates if each resource is free or allocated, and if allocated, to which process. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.
In some cases, several processes may compete for a fixed number of resources. A process requests resources and if the resources are not available at that time, it enters a wait state. It may happen that it will never gain access to the resources, since those resources are being held by other waiting processes.
For example, assume a system with one tape drive and one plotter. Process P1 requests the tape drive and process P2 requests the plotter. Both requests are granted. Now PI requests the plotter (without giving up the tape drive) and P2 requests the tape drive (without giving up the plotter). Neither request can be granted so both processes enter a situation called the deadlock situation.
A deadlock is a situation where a group of processes is permanently blocked as a result of each process having acquired a set of resources needed for its completion and having to wait for the release of the remaining resources held by others thus making it impossible for any of the deadlocked processes to proceed.
In these tutorials we will study about the deadlocks, its characterisation, deadlock avoidance and its recovery.