A deadlock is a state that a set of processes can encounter when dealing with resources. A deadlocked system will usually hang and no processes will continue computation. A deadlocked state is one in which the processes are powerless to resolve and require intervention from the operating system.
Resources are elements in a computing system that a CPU will call upon for information or a service. There are pre-emptiable resources which can be taken away from processes with out ill-effects, ie temp sensor. and non-pre-emptiable resources which can not be commendeared with out the process failing, ie printers.
To acquire a resource several steps are involved.
- request the resource.
- use the resource.
- release the resource.
If the resource is currently being used the process must wait for the resource to become available.
Formal Definition Edit
A set of processes are deadlocked if each process in the set is waiting for an event that only another process in the set can cause.
A deadlock ensures that no processes can run, release resources be awakened.
Conditions for Deadlock Edit
- Mutual exclusion condition - resource can only be given to a single process
- Hold and wait condition - process holding resources can request additional
- No preemption condition - previously granted resources cannot forcibly taken away
- Circular wait condition - must be a circular chain of 2 or more processes each is waiting for resource held by next member of the chain
Deadlock Strategies Edit
Not so good ey
It is reasonable if deadlocks are rare and the cost to prevent/recover is quite high. Unix and windows do use this method with more complex deadlock situations.
Detect and Recover EditDetection
A method to detect a potential dead lock is to form two tables. Table on the left contains all the possible resources and where they are allocated. The table on the right contains all the resources currently not in use and the upcoming requests. To find a deadlock search through the request matrix for a request row whose values are lower than the resources available. If it is found the process can complete and the resources are then released. Add the released resources to the resources available and repeat. If no such row can be found the remaining processes are then deadlocked. If the algorithm finds that all the resources are released then there is no deadlock.
Once a deadlock has been detected we need to recover from it.
- Preemption - take resources back
- Rollback - save process state periodically and roll back if we encounter deadlock
- Kill - kill processes until deadlock is resolved.
Dynamic Avoidance Edit
Is a state when the system is not deadlocked. There exists a scheduling order that results in every process running to completion, even if they all request their maximum resources immediately
An unsafe state does not necessarily that the system will result in deadlock, it could be lucky and complete with out an issue. We can however not guarantee that the system will complete (not deadlock).
A deadlock avoidance algorithm in essence only adds processes that will ensure safe status.
Processes are only allowed to proceed if there are enough resources to accommodate their maximum possible request. Otherwise they have to wait for other processes to return resources before continuing. Although the bankers algorithm will prevent a deadlock it is impractical to know the maximum number of resources required in advance.
Resource policies are used to ensure that one of the 4 conditions for deadlock is not met.
It is infeasible in general to attack this condition as some resources can not be shared.
Hold and Wait
Simply require processes to request all resources necessary for completion before starting. This can cause issues with processes unaware of which resources are required. It also does not allow for resources to be used effectively as some resources may be held by processes not currently using them. Several variations exist such as process giving up all of its resources if it blocks whilst holding a resource, then immediately request all the resources needed. This although can lead to starvation.
Simply take resources from processes. Not viable as many resources cannot be preempted. IE printer.
A common approach to attacking circular waiting is to enforce a policy that forces processes to acquire resources in a specified order. This ensures that resources are acquired and released circularly, ensuring that processes cannot block one another.
Starvation is a situation where the overall system continues to make progress but a particular process is not given the necessary resources or processor time to progress.
Starvation maybe caused by:
- Never being allocated resources - always in blocked state
- Never being scheduled to run
The easiest strategy to prevent starvation is to enforce a first come first served scheduling and resource allocation algorithm.