10
$\begingroup$

I was reading Operating Systems by Galvin and came across the below line,

Not all unsafe states are deadlock, however. An unsafe state may lead to deadlock

Can someone please explain how deadlock != unsafe state ? I also caught the same line here

If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )

$\endgroup$
  • 1
    $\begingroup$ deadlock can be a similar concept to a race condition that happens intermittently. the unsafe code only triggers the deadlock when a particular sequence lines up. that sequence could "happen at any time" aka "accident waiting to happen"... $\endgroup$ – vzn Aug 11 '15 at 14:58
  • $\begingroup$ unsafe state means, theoretically there is a possibility of deadlock. deadlock can occur when some specific things happen. for safe state, doesn't matter what happens, there can't be a deadlock. $\endgroup$ – nishantbhardwaj2002 Aug 23 '16 at 12:09
  • 1
    $\begingroup$ For exactly the same reasons that any dangerous situation (in real life) doesn't always cause bad things to actually happen. $\endgroup$ – David Richerby Sep 29 '16 at 11:23
14
$\begingroup$

Deadlock means something specific: there are two (or more) processes that are currently blocked waiting for each other.

In an unsafe state you can also be in a situation where there might be a deadlock sometime in the future, but it hasn't happened yet because one or both of the processes haven't actually started waiting.

Consider the following example:

Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

There's a more interesting example in Section 7.5.1 of the link you gave:

Consider a system with 12 tape drives with:

Process       Max Need       Current
P0:             10              5
P2:              9              3

This is an unsafe state. But we're not in a deadlock. There's only 4 free drives, so, for example, if P0 does request an additional 5, and P2 does request an additional 1, we will deadlock, but it hasn't happened yet. And P0 might not request any more drives, but might instead free up the drives it already has. The Max need is over all possible executions of the program, and this might not be one of the executions where we need all 10 drives in P0.

$\endgroup$
  • $\begingroup$ Thank you so much sir! and I hate my unclear textbook... $\endgroup$ – Ning Nov 14 '18 at 12:45
  • $\begingroup$ But I also have some questions: (1) You said ["]The Max need is over all possible executions of the program[."], but you also said ["]if P0 does request an additional 5, and P2 does request an additional 1, we will deadlock[."], where (1)means if Max Need is not achieved it's possible to have deadlock, while (2) means must to have deadlock when it's not achieved? $\endgroup$ – Ning Nov 14 '18 at 12:49
  • $\begingroup$ Is my reasoning correct?: If P2 does request an additional 1 and it finish, then the free tapes become (4+3=7), and since P1 request additional 5 then it can be achieved, so no deadlock. But if P2 does not finish, then deadlock occurs since even if P1 only need 5 to finish, still 4<5. $\endgroup$ – Ning Nov 14 '18 at 13:21
  • $\begingroup$ For the last example: P0 request additional 5, then 5+5+3=13>12, so P0 has to wait P2, to generate deadlock just let P2 request an additional one. $\endgroup$ – Bit_hcAlgorithm Dec 25 '18 at 13:44
7
$\begingroup$

Just to expound on what Wandering Logic was saying.

Say I have two threads that both need access to X and Y, and have no synchronization and no mechanism to fix deadlock. This is unsafe, as one could lock X and the other Y and then neither could proceed. But it isn't guaranteed.

Thread 1                    Thread 2
Lock X                      
Lock Y
OS Interrupts Thread 1 and passes control to Thread 2
                            Unable to lock needed resources.
OS Interrupts Thread 2 and passes control to Thread 1
Unlock X                    
Unlock Y                    
                            Lock Y
                            Lock X
 ....

This scenario didn't wind up in deadlock, but it could have. Due to the way threading works, there isn't a set flow. The OS controls the threading and so it could occur something like the following:

Thread 1                    Thread 2
Lock X        
OS Interrupts Thread 1 and passes control to Thread 2
                            Lock Y              
DEADLOCK Thread 1 needs Y, Thread 2 needs X. Neither knows to back down and simply waits.
$\endgroup$
1
$\begingroup$

Safe state is deadlock free for sure, but if you cannot fulfill all requirements to prevent deadlock it might occur. For example if two threads may fall in deadlock when they start thread A, then thread B, but when they start the opposite (B, A) they will work fine - let me assume B is nicer ;) The state of system is unsafe, but with fortunate starting sequence it will be working. No deadlock, but it is possible. If also you synchronize them by hand - start in good order - it is hazardous - for some reason they might not be fired as you like - system still is unsafe (because of possible deadlock) but there is low probability to that. In case of some external events like freezing threads or interupts after continuing it will fail.

You have to realise - safe state is sufficient condition to avoid deadlock, but unsafe is only nessesary condition. It is hard to write code out of head right now, but I can search for some. I did encountered code in Ada that more than 99/100 times it was perfectly working for several weeks (and then stopped due to server restart not deadlock) but once in a while it was crashing after several seconds into deadlock state.

Let me add some easy example by compare to division: If your function divides c / d and returns result, without checking whether d is equal 0, there might be division by zero error, so code is unsafe (same naming intended), but until you do such division, everything is fine, but after theoretical analysis code is unsafe and might fall into undefined behaviour not handled properly.

$\endgroup$
0
$\begingroup$

Here is my understanding on this (please correct me if I am wrong): (A) If deadlock, means there exist a cycle (one of the necessary condition) (B) A cycle is mandatory condition for deadlock (for both single and multi instance resources)

So we can prove now that there exist a cycle which may not lead to deadlock, unsafe state with cycle You can see here a cycle exist meaning an unsafe state is found, but this might not lead to a deadlock since resource R2 which is participating in cycle may break the cycle as soon as process P3 finishes and releases it (remember P3 is not having any dependency or waiting for any other resource).

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! A small point: it's best to avoid the phrase "may not" in written English, since it's unclear whether it means "must not" ("You may not park here") or "might not" ("You may not enjoy this movie.") $\endgroup$ – David Richerby Sep 27 '16 at 13:11
0
$\begingroup$

A trivial unsafe state: Thread 1 takes lock A, then lock B, then unlocks both. Thread 2 takes lock B, then lock A, then unlocks both.

This will only lead to a deadlock if Thread 2 takes lock B just between Thread 1 taking lock A and trying to take lock B, or Thread 1 takes lock A just between Thread 2 taking lock B and trying to take lock A.

If Thread 1 and Thread 2 do this randomly once an hour, and there is a microsecond gap of time that would actually lead to a deadlock. this can run a very long time in the hand of customers until eventually you get a deadlock by chance.

Walk across a street with your eyes closed. It's unsafe. But you don't always get killed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.