Dining Philosopher Problem Solutions

This assignment delves into the Dining Philosophers problem, a classic computer science example illustrating synchronization challenges. It analyzes various algorithms for solving this problem, including runtime checks, resource reservation techniques, and the impact of restarting threads. The document also discusses deadlock prevention strategies and provides code examples for implementing solutions.

Running head: DEADLOCK HANDLING ALGORITHMS
Deadlock Handling Algorithms
Name of the Student
Name of the University
Author note

1DEADLOCK HANDLING ALGORITHMS
Table of Contents
4.1. ANSWER TO QUESTION 4.1:...........................................................................................2
a) Ranking according to concurrency:..........................................................................................2
 Detection of deadlocks, killing of threads, releasing of resources and roll back thread’s
action:..............................................................................................................................................2
 Banker’s algorithm and ordering of resources:....................................................................2
 Reserving of all resources in advance:.................................................................................3
 Restarting of all the resources and releasing of threads if needed:.......................................3
b) Ranking according to efficiency:.............................................................................................4
 Advance reserving of all the resource and ordering sequence of the resource:....................4
 Banker’s algorithm, detection and killing of threads and releasing the resources:..............4
 Roll back thread’s actions and detect deadlock:...................................................................5
 Restart of threads and releasing of all the resources if threads need to wait:.......................5
4.2. ANSWER TO QUESTION 4.2:...........................................................................................5
References:......................................................................................................................................7

2DEADLOCK HANDLING ALGORITHMS
4.1. ANSWER TO QUESTION 4.1:
a) Ranking according to concurrency:
The different approach towards evaluation of different deadlock conditions that permits the
greatest concurrency are as follows:
 Detection of deadlocks, killing of threads, releasing of resources and roll back
thread’s action:
There are no algorithms which limits the concurrency before the occurrence of deadlock.This
is the process in which deadlock is not prevented rather it is a process in which process requests
for a resource and make it wait in an uncontrolled manner. The detection technique is similar for
both disturbed and centralized systems. Detection algorithm becomes more simple if a wait-for-
graph is maintained and search for cycle is done (Kimura Graefe and Kuno 2012). Since the
algorithms depend on the runtime checks and not on the static restrictions. The effects of the
algorithms after the occurrence of the deadlocks are harder to characterize that is if they allow lot
of concurrency (enhance in some cases). Initially the computation may not be longer sensual or
efficient (KimuraGraefe and Kuno 2012). Collective request is a method which involves denial
of hold and wait condition by ensuring that if a resource is requested by a process then the
process does not hold any other resource.
 Banker’s algorithm and ordering of resources:
There is a restriction of the computation as the algorithms causes unnecessary waiting
than the previous one. Unsafe allocation (a proper superset of deadlock-producing
allocations) is prevented by the banker’s algorithm and the allocation is restricted by the

3DEADLOCK HANDLING ALGORITHMS
resource ordering making the threads to have fewer option if to wait or not (Agrawal,
Botlagunta and Srinivasulu 2013). This process involves denial of circular wait thereby
assigning each resource a unique global number which in turn is used for imposing total
ordering of all resource types.
 Reserving of all resources in advance:
This algorithm is less pathological than the worst one’s as this provides less concurrency than
the previous two. By the process of reserving all resources in advance makes the threads to wait
longer blocking the other threads while working. Initially, making the system-wide execution
more linear (Agrawal, Botlagunta and Srinivasulu 2013). Methods of avoidance includes the use
of some advanced knowledge for the usage of process to predict the future state of the system to
avoid the allocations that can lead to a state of deadlock.it is important to read the safety notices
of the resource allocation as the algorithms for deadlock avoidance are based on the concept of
weather the state is safe or unsafe. A safe state is something which means that the system is not
facing any deadlock. Avoidance is a technique in which the resource allocation is done in such a
way that the system always remains in a safe state (Nazeem and Reveliotis 2012).
 Restarting of all the resources and releasing of threads if needed:
Since the concurrency will be useless repetition making the algorithm strangest. This happens
because there remains a competition for execution time between the threads. The advancing of
useful thread is also prevented (Giachino, Kobayashi and Laneve 2014). If a system faces
deadlock, then it is not only important to apply the detection and recovery strategy for handling
deadlock but also it should be made sure that the system is able to recover from the state of
recovery (Huang Pan and Su 2013). The following can be used:

4DEADLOCK HANDLING ALGORITHMS
 The simplest way is to inform the operator about the deadlock and let the operator handle
the situation manually.
 Another way is the termination of the processes to reclaim the resources held by the
processes.
 The final method is the checking of the processes periodically so that whenever there
exists a state of deadlock the process is rolled back to a point where the resource was not
allocated to the process.
 Depending on the definition of concurrency this algorithm provides a doubtful distinction
which means it allows both the most and the least amount of concurrency (Geetha and
Sreenath 2013).
b) Ranking according to efficiency:
The deadlock handling algorithms in terms of efficiency are listed below ranking from the
most-efficient to least efficient:
 Advance reserving of all the resource and ordering sequence of the resource:
This algorithm does not involve any runtime overhead which initially makes this the most
efficient type of algorithm (Liu et al. 2015). This result is based on the same static restriction
which makes this algorithm rank last in terms of concurrency.
 Banker’s algorithm, detection and killing of threads and releasing the resources:
These type of algorithms performs a roughly equivalent runtime check upon the allocations.
A search is made on the number of threads and allocations by the banker’s algorithm to verify
the safety. A cycle-detection search is made by the deadlock detection on the length of the

5DEADLOCK HANDLING ALGORITHMS
resource dependent chains. Number of threads, number of resources and number of allocations
bound the resource dependent chains (Kimura Graefe and Kuno 2012).
 Roll back thread’s actions and detect deadlock:
This algorithm perform the same runtime check as that of previous one but entails a logging
cost which is in the number of memory writes performed (Agrawal, Botlagunta and Srinivasulu
2013).
 Restart of threads and releasing of all the resources if threads need to wait:
Mainly two reasons make this algorithm inefficient. Firstly, this algorithm has a low
probability of completing as the threads run the risk of restarting. Second of all there is a
competition between other restarting threads for finite execution time making the entire system
advance towards slow completion (Geetha and Sreenath 2013).
4.2. ANSWER TO QUESTION 4.2:
Dinning philosopher problem is the problem associated with computer science used for
solving the concurrent algorithm designswhich illustrates the synchronizing issues and
techniques. According to the problem, it can be selected that the number of philosophers sitting
in the chair are four (it is an even number). Now if the number of spoons available is five then,
after selecting the left spoon, one of the philosophers will have an option of selecting the right
spoon. This implies that one of the philosophers will be able to start eating at stage of the dinner.
This makes the deadlock prevention more efficient. In case of number of spoons are also four,
then the solution will be as following:
while (true) {

6DEADLOCK HANDLING ALGORITHMS
wait (spoon[z]);
wait (spoon [z+1) % 5]); // mod is used because if z=4, next
//chopstick is 1 (dining table is circular)
//eat
signal (spoon [z]);
signal (spoon [(z+1) % 5]);
//think
}

7DEADLOCK HANDLING ALGORITHMS
References:
Agrawal, S., Botlagunta, M.D. and Srinivasulu, C., 2013. A total need based resource reservation
technique for effective resource management. International Journal of Computer
Applications, 68(18).
Geetha, V. and Sreenath, N., 2013. Preventing deadlocks and starvation in distributed object
oriented systems. Computers & Electrical Engineering, 39(2), pp.582-595.
Giachino, E., Kobayashi, N. and Laneve, C., 2014, September. Deadlock analysis of unbounded
process networks. In International Conference on Concurrency Theory (pp. 63-77). Springer,
Berlin, Heidelberg.
Huang, Y.S., Pan, Y.L. and Su, P.J., 2013. Transition-based deadlock detection and recovery
policy for FMSs using graph technique. ACM Transactions on Embedded Computing Systems
(TECS), 12(1), p.11.
Kimura, H., Graefe, G. and Kuno, H.A., 2012. Efficient locking techniques for databases on
modern hardware. In ADMS@ VLDB (pp. 1-12).
Liu, H., Xing, K., Wu, W., Zhou, M. and Zou, H., 2015. Deadlock prevention for flexible
manufacturing systems via controllable siphon basis of Petri nets. IEEE Transactions on
Systems, Man, and Cybernetics: Systems, 45(3), pp.519-529.
Nazeem, A. and Reveliotis, S., 2012. Designing compact and maximally permissive deadlock
avoidance policies for complex resource allocation systems through classification theory: The
nonlinear case. IEEE Transactions on Automatic Control, 57(7), pp.1670-1684.