Deadlock - System Design | Assignment

Running head: DEADLOCK
SYSTEM DESIGN
Name of the Student
Name of the University
Author Note

1DEADLOCK
Solution 1
In priority based process scheduling processes got executed by their processes. In any
case if any low priority process does not get executed by the central processing unit (CPU) then
the condition of the process is called as starvation. Sometime due to deadlock processes does not
get access to the resources then starvation is also occurred. Process with the bigger priority
number is always has the low priority. Suppose there are two processes with priority 3 and
priority 10. Therefore the process will be executed first with priority 3 and then the process with
priority 10. If the process is the lowest among all the processes then there is a chance of
starvation for the process (Carbone, Montesi, 2013).
There are some differences between deadlock and starvation. Deadlock happens when a
process does not get access to its required resource and which is already taken by some other
process. In starvation a process is not get executed because of low priority. In deadlock processes
are unable to proceed while in starvation the process does not get executed due to low priority
while the other process with high priority get executed. Deadlock is also known as circular
waiting while starvation is known as lived lock (Chen et al. 2017)
To prevent starvation aging is the best process. In aging the priority of a process get
increased gradually. It depends on the time it stayed in the ready queue. The more it stayed in
ready queue, its priority is get higher gradually. If any process with low priority is waiting in
ready queue for more than time it should take then it became important to increase the priority of
that process. Because if the CPU keep the process waiting in the ready queue then it might
possible that the process will never execute. As an example in 1967 in a priority based

2DEADLOCK
scheduling, a process was scheduled but for the low priority the process was executed after 6
years, in 1973. (Eslamimehr and Palsberg, 2014)
Now the aim of the assignment is to develop and implement a model that would help to
detect starvation of any process.
Process Arrival time Burst Time Priority
P1 0 5 1
P2 2 10 3
P3 7 20 2
P4 11 5 4
P5 15 4 2
If a process is in ready state but its execution is in almost always got preempted by other high
priority process then the process will starve for execution (Giachino, Laneve and Lienhardt,
2016). In the above process chart there is a chance that P4 process will starve for execution. Now
it is needed to use aging to prevent such starvation. Aging suggests that the priority of P4 process
will increase in a fixed interval of time. For example after each 10 unit of time the priority of
process P4 will increase by one. After 10 unit of time the priority of process P4 will be 3. After
more 10 seconds the priority of P4 will be 2 and at last after more 10 unit of time the priority will
be 1. Now this process will have the highest priority and got executed accordingly (Hou et al.
2014).

3DEADLOCK
Solution 2
For the banking transaction problem there are 15 accounts. Among them only two accounts can
make transaction at a time. The following steps for the transaction are-
Lock A(i); lock A(i); update A(i); update A(j);
a. In the above mentioned steps A is the process and i, j are the resources such bank
accounts. In this scenario no deadlock situation will occur. Deadlock occurs when more
than one process try to get access to one resource. But here is only one process A. One
process can access one resource at a time. So here, there is no chance of deadlock (Kastis
et al. 2015).
b. Deadlock is defined as a task is blocked for a permanent time. If multiple processes are
looking for a same resource, then none of them are getting that resource. This cause
deadlock in a computer system. Deadlock prevention is the technique that allows the
system to prevent the possible ways that are responsible to make the deadlocked.
Deadlock prevention has some special techniques. They are no preemption, Hold and
wait, circular wait and mutual exclusion,
No preemption is if one resource is taken by a process and at the same time another
process is trying to get that resource. In such cases CPU should not preempt the process
and provide the resource to a new process. This is known as no preemption (Ling et al.
2016).
Hold and wait is also a way to detect deadlock. In hold and wait a process already
has a resource but they are intended some other resource. In that case while having the
resource, it do not proceed the resource but keeping the resource. It can be prevented by

4DEADLOCK
Circular wait can be found from the logical diagram of that processes. If there
exist any circular loop in the diagram, there must be a deadlock. To prevent deadlock we
must close the circular loop by allocating processes to their resources.
Next is mutual exclusion. Mutual exclusion is the process where a process
intending to have a resource which is already taken by another process (Mishra and
Rashid. 2014). At the same time, the process want to have the resource which is taken by
previous process. This can be prevented by giving the resource to one process and lets it
complete first and then another.
Spooling is also a deadlock prevention technique that can be used for printing
problems. In printer there is a memory which stores jobs from each of the processes.
Therefore printer follows FCFS method so no printing process has to wait for the ultimate
execution. Each of the tasks are executed sequentially. Spooling is mainly used to violate
mutual exclusion. Though there are some problem with spooling. The problems are that
each resource became part of spooling, which is unnecessary. After a few time, processes
take part of a race to become a part of the spool to get executed. Though it is not possible
to permit a resource to more than one resource. It is not good for the performance of
CPU. So we cannot discrete mutual exclusion for completing a process (Stallings, 2017).
Numbering policy request is the technique to prevent deadlock. In this method the first
requested process is numbered. Then the process is first executed. After that in that sequence
other processes are executed. When the first process processed, the other ones keep waiting.
When the first process successfully executed, the others got the resources and got executed.

5DEADLOCK
For the above scenario, it can be said that preventing deadlock is possible with
numbering request policy. If the number of accounts is dynamic, there will be no effect on the
problem (Mohn et al. 2016).
Solution 3
Waiting time and turnaround time
In ready state or ready queue the time, a process waits to get executed by CPU is known
as waiting time. The value of waiting time can be calculated by subtracting arrival time from
turnaround time. Arrival time means in which time the process arrived in the ready state. After
arriving into ready state a process can be supposed to wait for the CPU to get executed.
Sometime the CPU can be busy with some other higher priority tasks (Hamacher, Vranesic and
Zaky.,2018). Therefore the new process that came to the ready state have to wait. Sometime this
can cause starvation. Turnaround time is the total time that a process spent in CPU. Turnaround
time is the calculated by subtracting arrival time from burst time of that process. Execution time
means the time it takes while executing the process. Arrival time is the time in which the process
came to CPU. Turnaround Time also known as TAT. For example if a process came to CPU at 1
unit of time and got executed after 15 unit of time, then turnaround time will be 15-1= 14 unit of
time (Panda and Bhoi, 2014).
For the above mentioned table waiting time and turnaround time are calculated. First the
scheduling that is used is First Come First Serve (FCFS).

6DEADLOCK
Process
Arrival
time
Burst Time
Completion
time
Turnaround
time
Waiting
time
Priority
P1 0 5 5 5 0 1
P2 2 10 15 13 3 3
P3 7 20 35 28 8 2
P4 11 5 40 29 24 4
P5 15 4 44 29 25 2
Turnaround time = completion time – arrival time.
Waiting time = Turnaround time – burst time.
Now we will use Round robin scheduling. Suppose the time quantum is 5 (Parson and
Keith,2013).

7DEADLOCK
Process
Arrival
time
Burst Time
Completion
time
Turnaround
time
Waiting
time
Priority
P1 0 5 5 5 0 1
P2 2 10 29 27 7 3
P3 7 20 44 37 17 2
P4 11 5 20 9 4 4
P5 15 4 20 5 1 2
Solution 4
First Come First Serve (FCFS)
Process Arrival time Burst time Completion time TAT Waiting time
A 0 4 4 4 0
B 3 7 11 8 1
C 5 3 14 9 6
D 9 15 29 20 5
E 12 1 30 18 17

8DEADLOCK
Round Robin Scheduling (RR)
Process Arrival
time
Burst time Completion
time
TAT Waiting
time
Response
Time
A 0 4 4 4 0 0
B 3 7 14 11 4 1
C 5 3 11 6 3 3
D 9 15 26 17 2 5
E 12 1 15 3 2 2
Shortest Remaining Time First (SRTF)
Process Arrival
time
Burst time Completion
time
TAT Waiting
time
A 0 4 4 4 0
B 3 7 12 9 2
C 5 3 8 3 5
D 9 15 28 19 13
E 12 1 13 1 12

9DEADLOCK
Highest Response Ratio First (HRRF)
Process Arrival
time
Burst time Completion
time
TAT Waiting
time
A 0 4 4 4 0
B 3 7 11 7 0
C 5 3 14 9 6
D 9 15 30 21 6
E 12 1 15 3 2
Response Ratio= (Waiting time+ burst time) / burst time.
In this scheduling,method of response ratio is not occurred until all the remaining jobs occurred
in ready queue (Samak and Ramanathan, 2014)
Solution 5
The given system is in deadlock. For resource R1 there is only one instance which is
occupied by P2 and P1 is requesting for R1 instance to get executed. R2 resource has two
instances. Among them one is occupied by P1 and another instance is occupied by P2. P3 is
trying to access R2 to get executed. R3 resource has one instance and is occupied by P3 process
and P2 also requesting for R3. Therefore all the processes are in deadlock (Schäberle and Hack,
2014).
All the processes in the given system are in deadlock situation. Each process is requesting
some resources to get executed but the required instances of that resource is already occupied by
some other process. If one process release the resource then the second process will access that

10DEADLOCK
resource. But this is not going to be happen due to deadlock (Silberschatz, Gagne and Galvin,
2018).
The resulting graph is given below.
In a system if for some reason deadlock happens there three kind of ways to handle deadlock.
They are deadlock prevention, deadlock avoidance and remove deadlock. In the given diagram
deadlock is already present. Now we had to remove deadlock (Tanenbaum and Bos, 2015).
In this case the main reason for deadlock id process P2. P2 is already has the resource R1
and R2 but also wants R3 to get executed. There are some possible ways to remove deadlock.
For this reason it is important to handle the P2 process to make the system getting out of
deadlock. If we remove the process P2, deadlock will be removed. As well as P1 will get the
resource R1, and P1 also has the resource R2. Process P3 will also get the resource R2 and it
already has the resource R3. Now there will be no deadlock situated in the given system (Wang,
Wu and Yang, 2015).

11DEADLOCK
Reference
Stallings, W., 2017. Operating System Internals and Design Principles. 9th ed. Pearson.
Hamacher, C., Vranesic, Z., and Zaky, S., 2018. Computer Organization and Embedded
Systems. 6th ed. McGraw Hill. Sysdney: McGraw Hill.
Carbone, M. and Montesi, F., 2013, January. Deadlock-freedom-by-design: multiparty
asynchronous global programming. In ACM SIGPLAN Notices (Vol. 48, No. 1, pp. 263-274).
ACM.
Chen, Y., Li, Z., Al-Ahmari, A., Wu, N. and Qu, T., 2017. Deadlock recovery for flexible
manufacturing systems modeled with Petri nets. Information Sciences, 381, pp.290-303.
Eslamimehr, M. and Palsberg, J., 2014, November. Sherlock: scalable deadlock detection for
concurrent programs. In Proceedings of the 22nd ACM SIGSOFT International Symposium on
Foundations of Software Engineering (pp. 353-365). ACM.
Giachino, E., Laneve, C. and Lienhardt, M., 2016. A framework for deadlock detection in core
ABS. Software & Systems Modeling, 15(4), pp.1013-1048.
Hou, Y., Li, Z., Zhao, M. and Liu, D., 2014. Extended elementary siphon-based deadlock
prevention policy for a class of generalised Petri nets. International Journal of Computer
Integrated Manufacturing, 27(1), pp.85-102.
Kastis, G.A., Gaitanis, A., Samartzis, A.P. and Fokas, A.S., 2015. The SRT reconstruction
algorithm for semiquantification in PET imaging. Medical physics, 42(10), pp.5970-5982.

12DEADLOCK
Ling, X., Zhang, Y., Xiong, J., Huang, X. and Chen, Z., 2016. An image matching algorithm
integrating global SRTM and image segmentation for multi-source satellite imagery. Remote
Sensing, 8(8), p.672.
Mishra, M.K. and Rashid, F., 2014. An improved round robin CPU scheduling algorithm with
varying time quantum. International Journal of Computer Science, Engineering and
Applications, 4(4), p.1.
Mohn, F., Sienski, G., Handler, D. and Brennecke, J., 2014. The rhino-deadlock-cutoff complex
licenses noncanonical transcription of dual-strand piRNA clusters in Drosophila. Cell, 157(6),
pp.1364-1379.
Panda, S.K. and Bhoi, S.K., 2014. An effective round robin algorithm using min-max dispersion
measure. arXiv preprint arXiv:1404.5869.
Parson, E.A. and Keith, D.W., 2013. End the deadlock on governance of geoengineering
research. Science, 339(6125), pp.1278-1279.
Samak, M. and Ramanathan, M.K., 2014, October. Multithreaded test synthesis for deadlock
detection. In ACM SIGPLAN Notices (Vol. 49, No. 10, pp. 473-489). ACM.
Schäberle, T.F. and Hack, I.M., 2014. Overcoming the current deadlock in antibiotic
research. Trends in microbiology, 22(4), pp.165-167.
Silberschatz, A., Gagne, G. and Galvin, P.B., 2018. Operating system concepts. Wiley.
Tanenbaum, A.S. and Bos, H., 2015. Modern operating systems. Pearson.

13DEADLOCK
Wang, S., Wu, W. and Yang, J., 2015. Deadlock prevention policy for a class of petri nets based
on complementary places and elementary siphons. Journal of Intelligent Manufacturing, 26(2),
pp.321-330.