M.Sc. Computer Science
Computer Systems
Additional Questions on Week 8 Materials – Part I
Question #1: (a) Cinderella and the Prince are getting divorced. To divide their property, they have
agreed on the following algorithm. Every morning, each of one may send a letter to the other’s lawyer
requesting one item of property. Since it takes a day for letters to be delivered, they have agreed that if
both discover that they have requested the same item on the same day, the next day they will send a
letter canceling the request. Among their property is the glass shoe, their dog Woofer, Woofer’s
doghouse, their canary Tweeter, Tweeter’s cage and a sword. The animals love their houses, so it has
been agreed that any division of property separating an animal from its house is invalid, requiring the
lawyers to negotiate on which items they already have and should be returned back. Unfortunately the
lawyers are stubborn and never agree. Is deadlock or starvation possible in such a scheme?
In this case deadlock is possible because if one party requests an animal such as the Woofer and the
other party requests its house i.e. Woofer’s doghouse, the first transaction will be honored (as the
items are different) but it will lead to negotiations between the lawyers. As we know that the
lawyers are stubborn, they will never agree to each other and the deadlock will persist. Some
possible scenarios are given below:
Cinderella requests Prince requests End Result
Woofer Woofer Cancels after a day because both want the same thing.
Woofer Woofer’s House Have to start over (after a day) because the dog and his house cannot be separated.
(This will lead to negotiations i.e. deadlock)
Woofer’s House Woofer Have to start over (after a day) because the dog and his house cannot be separated.
(This will lead to negotiations i.e. deadlock)
Woofer’s House Woofer’s House Cancels after a day because both want the same thing.
If both Cinderella and Prince request an animal and its house in the first round, then both will enter
into a deadlock state and this will also cause starvation, as none of them have got anything so far.
However, if they start by requesting different items, then we will not say that they are starving.
(b) What happens if it has been agreed that in the case of any division of property separating an animal
from its house the whole division to start over from scratch, instead of letting the lawyers discuss.
Explain if starvation or deadlock possible now.
If both parties always request the same item (e.g. Woofer), livelock is possible, as the transactions
are always canceled.
Cinderella requests Prince requests End Result
Woofer Woofer Cancels after a day because both want the same thing.
Woofer Woofer’s House Have to start over (after a day) because the dog and his house cannot
be separated.
Woofer’s House Woofer Have to start over (after a day) because the dog and his house cannot
be separated.
Woofer’s House Woofer’s House Cancels after a day because both want the same thing.
Deadlock is not possible because illegal settlements restart the negotiations (same for starvation).
Question #2: Consider a system with a total of 150MB of memory, allocated to three processes as
shown below:
Process Max Request (C) Allocation (A)
P1 70 MB 45 MB
P2 60 MB 40 MB
P3 60 MB 15 MB
Determine whether it would be safe to grant each of the following requests. If yes, indicate a sequence
of terminations that could be guaranteed possible. If no, show the reduction of the resulting allocation
table.
a) A 4th process arrives, with a maximum memory need of 60 MB and an initial need of 25 MB.
Process Max Request (C) Allocation (A) Free
P1 70 MB 45 MB 105 MB
P2 60 MB 40 MB 65 MB
P3 60 MB 15 MB 50 MB
P4 60 MB 25 MB 25 MB
Anyone of P1 or P2 can still run to completion, as they require 25 and 20 MBs of memory respectively.
P3 & P4 can then complete their processing after using the memory resources freed-up by P1 & P2.
b) A 4th process arrives, with a maximum memory need of 60 MB & an initial need of 35 MB.
Process Max Request (C) Allocation (A) Free
P1 70 MB 45 MB 105 MB
P2 60 MB 40 MB 65 MB
P3 60 MB 15 MB 50 MB
P4 60 MB 35 MB 15 MB
Now the system is deadlocked, as none of the process can run to completion i.e. memory
requirements of all processes are more than the available memory.
Question #3: (a) Is there any deadlock in the following graph?
S1 has three resource instances, and two of these are allocated to P1 and one is allocated to P2. In the
current situation, none of the S1 resources are available. S2 has two resource instances, one of these is
allocated to P2; Both P1 and P2 are requesting for one more instance of S2.
In the current situation, the system is not deadlocked i.e. we can still allocate one more instance of S2
to P1 and it will then be able to complete its execution. However, deadlock is possible, if we allocate
one instance of S2 to P2, which will lead to a situation where both P1 and P2 will be holding some
resources and requesting more for their completion.
Another Explanation:
In the current state, there is no deadlock. However, a deadlock can happen, if resource allocations are
done in a certain way.
In this question, deadlock will happen, if we allocate an instance of S2 to P2; because then P1 will not
be able to complete, as it will still need one instance of S2 and P2 will also be unable to complete as it
requires one more instance of S1, which is not available.
Deadlock will not happen, if we allocate an instance of S2 to P1; because now P1 has all the resources
that it needs to complete its execution and once it is complete, it will release all of its allocated
resources, including 2 instances of S1 and 1 instance of S2 (the one we just allocated to P1) and then
P2 will be able to complete its execution.
(b) Is there any deadlock in the following graph?
In this graph, P3 and P4 are each holding one resource and requesting one more resource which is held
by the other process. So there is a deadlock between P3 and P4 (we assume that the blocks without any
circles in them are single instance resources).
P1 and P2 are holding onto one resource and requesting for one more instance, which is also requested
by P3; Two of these resources can be allocated, therefore either P1 or P2 will get at-least one instance
and complete its execution. Once P1 or P2 completes, the other process can complete its execution.
Please note that P3 and P4 are still deadlocked.
Question #4: Given the following state for the Banker’s Algorithm.
4 Resource Types: A (15 instances); B (6 instances); C(9 instances); D(10 instances)
Snapshot at time T0:
A B C D
P0 9 5 5 5
P1 2 2 3 3
P2 7 5 4 4
P3 3 3 3 2
P4 5 2 2 1
P5 4 4 4 4
Max. Claim Matrix
A B C D
P0 4 0 2 3
P1 0 1 3 1
P2 4 1 0 2
P3 1 0 0 1
P4 1 1 0 0
P5 1 0 1 1
Allocation Matrix
A B C D
P0 5 5 3 2
P1 2 1 0 2
P2 3 4 4 2
P3 2 3 3 1
P4 4 1 2 1
P5 3 4 3 3
Request (Need) Matrix
A B C D
4 3 3 2
Available Resource Vector
a) Verify that the Available Resource Vector has been calculated correctly ?
Yes, it is correct.
b) Calculate the Need Matrix (in the provided space above)?
See the Request (Need) Matrix above.
c) Show that the current state is safe i.e. show a safe sequence of processes. In addition, show how the
Available (working array) changes as each process terminates.
Yes, it is in safe state. One possible safe sequence will be P1, P2, P0, P3, P4 and P5
P1 Completes:
A B C D
4 4 6 3
P2 Completes:
A B C D
8 5 6 5
P0 Completes:
A B C D
12 5 8 8
P3 Completes:
A B C D
13 5 8 9
P4 Completes:
A B C D
14 6 8 9
P5 Completes:
A B C D
15 6 9 10
d) Given the request (3,2,2,1) from process P5, should this request be granted? Why or why not?
Assuming that we honor the request of Process P5. We will have the following state of the system:
A B C D
P0 4 0 2 3
P1 0 1 3 1
P2 4 1 0 2
P3 1 0 0 1
P4 1 1 0 0
P5 4 2 3 2
Allocation Matrix
A B C D
P0 5 5 3 2
P1 2 1 0 2
P2 3 4 4 2
P3 2 3 3 1
P4 4 1 2 1
P5 0 2 1 2
Request (Need) Matrix
A B C D
1 1 1 1
None of the processes will be able to complete, hence it is not a safe state and the request cannot be
granted.
Question #5: Consider that 5 philosophers are seated around a circular table:
There is one chopstick between each philosopher
A philosopher must pick up its two nearest chopsticks
in order to eat
A philosopher must pick up first one chopstick, then
the second one, not both at once
We need an algorithm for allocating these limited resources (chopsticks) among several processes
(philosophers) such that solution is free from deadlock and free from starvation.
Now suppose that there are two types of philosophers. One type always picks up his left fork first
(“lefty”), and the other type always picks up his right fork first (“righty”). The behaviors of a lefties
and righties are defined as below:
Behavior of a “Lefty” Behavior of a “Righty”
void philosopher (int i)
{
while (true) {
think();
wait (fork[i]);
wait (fork[(i+1) mod 5]);
eat();
signal (fork[(i+1) mod 5]);
signal (fork[i]);
}
}
void philosopher (int i)
{
while (true) {
think();
wait (fork[(i+1) mod 5]);
wait (fork[i]);
eat();
signal (fork[i]);
signal (fork[(i+1) mod 5]);
}
}
a) Prove that any seating arrangement of lefties and righties with at least one of each avoids deadlock.
Assume that the table is in deadlock, i.e., there is a nonempty set D of philosophers such that each P i in
D holds one fork and waits for a fork held by neighbor. Without loss of generality, assume that P j ϵ D is
a lefty. Since Pj clutches his left fork and cannot have his right fork, his right neighbor Pk never
completes his dinner and is also a lefty. Therefore, Pk ϵ D. Continuing the argument rightward around
the table shows that all philosophers in D are lefties. This contradicts the existence of at least one
righty. Therefore deadlock is not possible.
b) Prove that any seating arrangement of lefties and righties with at least one of each avoids starvation.
Assume that lefty Pj starves, i.e., there is a stable pattern of dining in which P j never eats. Suppose Pj
holds no fork. Then Pj’s left neighbor Pi must continually hold his right fork and never finishes eating.
Thus Pi is a righty holding his right fork, but never getting his left fork to complete a meal, i.e., P i also
starves. Now Pi’s left neighbor must be a righty who continually holds his right fork. Proceeding
leftward around the table with this argument shows that all philosophers are (starving) righties. But Pj is
a lefty: a contradiction. Thus Pj must hold one fork.
As Pj continually holds one fork and waits for his right fork, Pj’s right neighbor Pk never sets his left
fork down and never completes a meal, i.e., Pk is also a lefty who starves. If Pk did not continually hold
his left fork, Pj could eat; therefore Pk holds his left fork. Carrying the argument rightward around the
table shows that all philosophers are (starving) lefties: a contradiction. Starvation is thus precluded.
Question #6: Consider the following solution to the dining philosophers problem with 6 philosophers.
Each hungry philosopher first picks up his left fork; if his right fork is also available, he picks up his
right fork and starts eating; otherwise he puts down his left fork again and repeats the cycle after
waiting a random period of time. Discuss whether this solution is correct or build your argument
against it.
This solution is correct because it does not lead to a deadlock and/or starvation. As stated in the
question, all philosophers pick their left forks first, lets assume the worst case where all philosophers
pickup their left forks at the exact same time. In this scenario, each philosopher will try to get his/her
right fork, which will not be available and thus he/she will put his/her left fork back on the table.
Before, continuing with the next cycle, each philosopher will wait for a random amount of time, which
is very likely to be different for each philosopher. Therefore, in the next cycle, some of the
philosophers will be able to pick-up both left and right forks and eat. Once, they are done, they will
release their forks, which will allow other philosophers to continue and get both of their forks. Thus,
this solution is free from deadlock and starvation.