[OSC] Day4: Deadlocks

Deadlock

Deadlocks and conditions for deadlocks

How do they occur?


Process A and B request the resources in opposite orders and end up in deadlock
  • Deadlock can occur on the same machine or between multiple machines(e.g. resources are requested over the network) and any number of resources
  • Deadlocks are not just related to operating systems but also occur in databases
A resource (e.g. a device, a data record, file, semaphore) can be acquired, used, and released
  • A resource can be preemptable, i.e. it can be forcefully taken away from the process without permanent adverse effect(e.g. memory -> disk)
  • A resource can be non-preemptable, i.e. it cannot b taken away from a process without permanent adverse effect(e.g. CD, printer)
    If a non-preemptable resource is requested but not available, the process is made to wait
    Deadlocks only occur for non-preemtable resources since preemtable resources can be temporarily taken away to recover from the deadlock

definition

“A set of processes is deadlocked if each process in the set is waiting for an event that only the other process in the set can cause”
  • each deadlocked process is waiting for a resource held by an other deadlocked process(which cannot run and hence cannot release the resources)
  • This can happen between any number of processes and for any number of resources

Minimum conditions

Four conditions must hold for deadlocks to occur:
  • Mutual exclusion: a resource can be assigned to at most one process at a time
  • Hold and wait condition: a resource can be held whilst requesting new resources
  • No preemption: resources cannot be forcefully taken away from a process
  • Circular wait: there is a circular chain of two or more processes, waiting for a resource held by the other processes
No deadlocks can occur if one of the conditions is not satisfied.

Algorithm to detect deadlocks

Approaches to dealing with deadlocks

  1. Just ignore them: Ostrich algorithm
  2. Detection and recovery
  3. Avoid deadlocks from happening by detecting them early
  4. Avoid deadlocks from happening by breaking Coffman’s conditions

Detecting deadlocks

A graph based approach

Deadlocks can be modelled using directed graphs:
  • resources are represented by squares and processes are represented by circles
  • A directed arc from a square(resource) to a circle(process) means that the resource was requested and granted, i.e. is allocated to the process
  • A directed arc from a circle(process) to a squared(resource) indicates that the process has requested the resouces and is waiting to obtain it
A cycle in the graph means that a deadlock occurs for the respective resources and processes

Example


If all of them run sequential, no deadlock will occur, but no multi-programming will take place
But if not

This is the directed graph it is a circle, so there will be deadlocks
If the OS were able to detect deadlocks, it could have changed the order in which the processes are executed, e.g.:
`A requests R, C requests T, A requests S
Basic graph algorithms can be used to search the graph and detect cycles
This is the second approach –Detection and recovery

A matrix based algorithm(Detection and recovery)

A matrix based algorithm is used when multiple “copies” of the same resource exist(The graph only applied to one copy of resource!!!!!)
  • Let P1 to Pn denote n processes
  • Let there by m resources classes:
    Let Ei denote the “existing” resources of type i
    Let Ai denote the number of available resources of type i
    The total number of allocated and available resources (Ai ) of type i is equal to Ei
The algorithm uses two vectors for the existing and available resources (E and A), and two matrices to describe the current and requested resources per process (C and R)

This might seems complicated! But we see one example

Assume C is the current allocation situation, R is the request situation.
E is the total resources situation
From C, we can know there only remains 2 Tape drives and 1 plotter, so we can came up with A=(2 1 0 0 )
So can we run process1 or process2 then? Obviously, there request can not be satisified.
Thus, we only can run process 3 first!
Then process 3 can be released and the available matrix A would be (2 1 0 0) + (0 1 2 0) = (2,2,2,0)
This time, process 2 can obtain resources and release it, there will be no deadlocks!

recovery from deadlocks(three methods)

Preemption: the resource is forcefully removed from one of the processes (this is likely to have an ill effect)
Rollback mechanisms: build in check points that allow the process to be restarted
  • The check points contain the memory image and resource states
  • Multiple checkpoints should be maintained
  • The process that owns the “deadlocked” resources is rolled back
Kill a strategically chosen processes to release its resources
  • The process should own the required type of resources
  • The process should be easy to restart

Deadlock avoidance

Example

Assume two processes, A and B, and two resources, a plotter and a printer:
Process A needs the printer between I1 and I3, and the plotter between I2 and I4
Process B needs the plotter between I5 and I7, and the printer between I6 and I8
we can draw a picture:

The shaded regions are inaccessible (the resources would be assigned by two processes simultaneously)
The box defined by I1, I2, I5, I6 is not deadlocked, but will deadlock eventually (i.e. unsafe)

Safe state and unsafe state

A safe state is one where there is a feasible order for the processes to finish without deadlock, even if all of them were to acquire all their resources immediately
Consider the following example for a single resource, assuming that 10 entities exist for the given resource (current allocation, and MAXIMUM allocation):

We can see every process can run, it is safe state for a!
Now let’s see a unsafe example:

(d) at least need 5 free resources but we only have 4, so it is unssafe.
But unsafe doesn’t means deadlock
A state might not be in deadlocked, but still be unsafe
The “bankers algorithm” (Dijkstra) can be used to avoid deadlocks

Bankers algorithm

For a single resource:
  - Find customer closest to max resource allocation
  - Check whether remaining resources can satisfy
      the maximum request
  - Return the resources from this process to
      the set of available resources
  - Find next process closest to its max
      resource allocation
  - ...
  The state is safe iff all processes can finish,
  even when they request all their resources
  at the same time
For multiple resources:
The bankers algorithm for multiple resources is a generalisation of the bankers algorithm for a single resource
Two matrices are maintained, one for the allocated resources C, one for the remaining resources that are required R
Three vectors are maintained; the existing resources, the possessed resources, the available resources

There are there vectors on the right
E is the total(exist) resources
P is the assigned(possessed) resources
A is the available resources
Thus, E = P+A
So the banker’s algorithm for multiple resources is :
Find a row in R which all corresponding resource requirements are less or equal to A
(selection order has no influence)
-If no row satisfied this, the state is unsafe
-Else "run the process" and add its resource to A
Repeat the above until all processes have finished
-The state is safe if all processes complete successfully
So as the image shows above, there are two questions:
Q: Can process B be granted a printer?
A: Yes. we can first run D, then A =(1 0 2 0) + (1 1 0 1) = (2 1 2 1)
then we can run A or E(assume we run A first) A = (2 1 2 1)+(3 0 1 1) = (5 1 3 2)
then we can run E, A = (5 1 3 2)+(0 0 0 0)=(5 1 3 2)
then we can run B…
we can run C finally.
So, a feasible order exists(D, A, E, B, C)
Q: Can process B and E both be granted a printer?
A:TBC?

Deadlock Prevention

The maximum number of requested resources for a certain process are not always known in advance, i.e., deadlock avoidance can be difficult in practices
An alternative approach to prevent deadlocks is to undermine at least one of the four Coffman conditions：
  • No preemption: forcibly remove a process’s resources
  • Prevent the circular waits:
    Allow at most one resource per process at any one time (this is not always practical)
    Allocate resources a number and force resource requests to be made in numerical order
Q: A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:enter image description here
What is the smallest value of x for which this is a safe state?
A:The needs matrix is as follows:
0 1 0 0 2
0 2 1 0 0
1 0 3 0 0
0 0 1 1 1
If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is 1 1 3 2 1 and C can run. After it finishes and returns its resources the avail- able vector is 2 2 3 3 1, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2.

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文