Deadlock Question - operating systems (existing resource/safe/requests..)

[BryantFury]

Hi I'm currently going through some questions, basically studying up one bits for my operating systems unit and my particular weakness is algorithms and 'working out' type questions such as this one below.

Consider the following snapshot of the system, with 4 types of resources and 3 processes, P1,
P2 and P3.
Available resources vector A: [4 1 0 1]

Current allocation matrix
C:
P1 [3 1 0 0]
P2 [0 0 1 2]

Maximum request matrix
R:
P1 [3 4 4 0]
P2 [0 0 1 3]
P3 [0 2 3 4] P3 [3 3 4 6]

a.
What is the existing resource vector for this system?
b.
Using bankers algorithm prove what is the current state of the system: safe, unsafe or
deadlocked.
c.
Process P1 requests the following resources [0 1 0 0], and this request is granted. What
is the new state of the system: safe, unsafe or deadlocked?

I am not looking for answers but I'm looking for help or methods to find
A) the existing resource vector
B) if the system is deadlocked or not (basically it's state)
C) for part c i have no idea where to begin but I am guessing it is similar in method to B.

Any help is greatly appreciated.
apologies if this is the incorrect place to post this question. I was unsure whether to place it in the C forum or not since it isn't really coding

[Taywin]

Edited. I think the table is as follows?

Current:
P1          3 1 0 0
P2          0 0 1 2
P3          0 2 3 4

Max:
P1          3 4 4 0
P2          0 0 1 3
P3          3 4 4 6

[Taywin]

I will go over this step by step, so that you can see how to compute it. Picture means more than a thousand words. Try to understand the steps to solve the problem, and you will get it. If you don't understand any part of the explanation, you need to ask.

Available
Resources  [4 1 0 1]

            Current     Max
P1          3 1 0 0     3 4 4 0
P2          0 0 1 2     0 0 1 3
P3          0 2 3 4     3 4 4 6

Compute resources needed for each process (max - current)...
P1          (3-3) (4-1) (4-0) (0-0) -> 0 3 4 0
P2          (0-0) (0-0) (1-1) (3-2) -> 0 0 0 1
P3          (3-0) (4-2) (4-3) (6-4) -> 3 2 1 2

The maximum resource is the current available + the total of current allocated.
Therefore, Maximum (existing) resource vector would be...
            4 1 0 1
            3 1 0 0
            0 0 1 2
            0 2 3 4
           ---------
           [7 4 4 7]

The idea of Banker's algorithm is to check whether or not each process can request, take the requested resources, complete the task, and then return all resources back.

Let say we iterate through each process vector to see if we could allocate (similar to a while-loop fashion). Let say we iterate through P1, P2, and P3 in order.

iteration 1:
Current Available: [4 1 0 1]
P1 needs [0 3 4 0]  <-- not enough, pass
iteration 2:
Current Available: [4 1 0 1]
P2 needs [0 0 0 1]  <-- OK
P2 is done and returns resources. Now, avaible resources is
[(4+0) (1+0) (0+1) (1+2)] --> [4 1 1 3]
iteration 3:
Current Available: [4 1 1 3]
P3 needs [3 2 1 2]  <-- not enough, pass
iteration 4:
Current Available: [4 1 1 3]
P1 needs [0 3 4 0]  <-- not enough, pass

All process vectors are visited but P1 and P3 still cannot complete the request!
The Banker's algorithm will deny this request. What does this tell you?

Now, the question said P1 requests [0 1 0 0] and is granted, you will need to recompute all available, current, and need vectors again.

Available
Resources  [4 0 0 1]

            Current     Max
P1          3 2 0 0     3 4 4 0
P2          0 0 1 2     0 0 1 3
P3          0 2 3 4     3 4 4 6

Compute resources needed for each process (max - current)...
P1          (3-3) (4-2) (4-0) (0-0) -> 0 2 4 0
P2          (0-0) (0-0) (1-1) (3-2) -> 0 0 0 1
P3          (3-0) (4-2) (4-3) (6-4) -> 3 2 1 2

If you attempt to go through the iteration again, what would the result be?

[BryantFury]

Firstly i must say, that was a brilliant explanation. I understood your response very well and I hope you don't mind but I will be using it for my study notes. Many thanks.

1. Ah so basically existing resources is just a simple addition.

2. Since it loops back, the system would be in an unsafe state. I.e deadlocked or leading to deadlock

3. iteration 1:
   Current Available: [4 0 0 1]
   P1 needs [0 2 4 0] <-- not enough, pass
   iteration 2:
   Current Available: [4 0 0 1]
   P2 needs [0 0 0 1] <-- OK
   P2 is done and returns resources. Now, avaible resources is
   [(4+0) (0+0) (0+1) (1+2)] --> [4 0 1 3]
   iteration 3:
   Current Available: [4 0 1 3]
   P3 needs [3 2 1 2] <-- not enough, pass
   iteration 4:
   Current Available: [4 0 1 3]
   P1 needs [0 2 4 0] <-- not enough, pass

so system will end up in unsafe state again, ie deadlocked or leading to deadlock?

thankyou again very much for your explanation. one point i did not realise was you need to
'(max - current)' in the computation. that was not explained in my notes and thus made a lot of sense.

lastly you please check if the answer i have given for part 3 i correct? Just to make sure.

[Taywin]

You are welcome. Yes, both are unsafe. The problem with #3, I would rather incline to deadlock. The reason is that the system has granted the request. Anyway, unsafe is the safest answer. :)