key: cord-0764511-kp50oaz7
authors: Botlagunta, Madhavi Devi; Agrawal, Smriti; Rajeswara Rao, R.
title: A novel resource management technique for deadlock-free systems
date: 2021-05-10
journal: Int J Inf Technol
DOI: 10.1007/s41870-021-00670-6
sha: b60d096f087a76e1e617e4b731c9dea8555e791b
doc_id: 764511
cord_uid: kp50oaz7

Deadlock in a shared resource system is a well-known problem. It has been extensively studied and recently a new class of resource reservation technique is researched upon for deadlock free resource management. This class of technique reserves a portion of the resources. The unreserved resources are freely allocated to any process demanding it. When the unreserved resources are not sufficient for a process demand the reserve pool resources are used such that the process completes and releases all the resources it is holding. This paper presents a new resource reservation technique resource driven DFRR. This technique estimates the optimal number of resources needed for a deadlock free resource reservation policy. The correctness is proved in the form of theorem 1. The theorem 2, suggests the resource reservation with minimal resources. The overhead of the resource pool estimation is [Formula: see text] and that of resource management is [Formula: see text] which is optimal for any deadlock handling technique. The effectiveness of the proposed technique is shown in the form of examples and simulation results.

Computing systems such as real-time [1, 2] , IoT [3, 4] , distributed, parallel, cluster, cloud computing systems, share resources for their effective utilization. The computing systems using shared resources, sometimes enter into a Deadlock, after which they are unable to execute further. Deadlocks adversely affect the system performance sometimes making it irresponsive so they are highly undesirable. Deadlock has been a big concern in both computing and non-computing shared resource systems and has been extensively studied for decades. Deadlocks will not always occur but as suggested by Coffman [5] it occurs if certain necessary conditions hold. These conditions are Mutual exclusion, Hold and wait, No pre-emption, and Circular wait condition. Thus, the first set of the Deadlock prevention (DP) resource management solution for a deadlock problem lies around these conditions. They suggest ensuring that one of the necessary conditions does not hold. The second set of Deadlock avoidance (DA), is a look forward technique to avoid deadlock in the future. The next set of solutions is event based where the system does not do any resource management rather waits for a deadlock event. The system periodically monitors for a deadlock occurrence and performs recovery action in case a deadlock is detected. Recently, a new class of techniques called Resource Reservation Techniques (RR) is also used for deadlock handling. These techniques are neither proactive nor reactive in the absolute sense. They reserve a set of resources and blindly allocate the remaining to processes for successful execution and also reduce the overhead usually caused by all other deadlock avoidance algorithms [6] [7] [8] [9] .

The main objective of this paper is to find optimal number of resources needed by processes to complete the execution without deadlocks in a system and also estimates how many minimal number resources of each type are sufficient. The correctness of the proposed technique can be proved in form of theorems and with the help of example and simulation results.

The rest of the paper is organized as follows: Sect. 2, provides a further look at the existing literature. Section 3 presents the proposed Resource driven-Deadlock-free technique and its effectiveness is explained with the help of example along with comparisons of other existing techniques. Section 4 illustrates experimental results and analysis. Finally, the paper concludes with Sect. 5 and Sect. 6 gives the future scope.

Resource allocation is a critical issue in shared or concurrent systems where resources are shared to avoid deadlocks. Authors [10] introduced a new metric Mean Normalized Blocking Time to compare locking mechanisms and also provide two different semaphore models for existing real-time systems in the automotive power environment. But these locking mechanisms with significant processing overhead reduce the system performance especially for multi core processing systems where processes execute on different cores in queues waiting to acquire a lock. So this implementation of more than one lock leads the risk of deadlock. The best solution is to eliminate locks. Removing the locks is significant overhead and propose performance based lock-free algorithms [11] in multi core systems which reduces the possibility of concurrency defects and risk of deadlock. They present a multi core communication API which enhances lock-free messaging and data exchange latency between processes. Authors [8] implemented resource request algorithm to avoid deadlocks with the help of simulating software. This algorithm grants requesting resources to processes for execution and analyze the state whether in safe or unsafe after every possible situation. But they fail to provide significant improvement in system performance and also deadlock-free. Authors [12] proposed a technique which is a combination of deadlock prevention and dead-lock avoidance to detect a feasible resources and to reduce the false-positive situations by applying the Banker's algorithm. False-positive situations means it is a request, it may not actually lead to a deadlock, but still be rejected due to a failed deadlock-free test. Authors [13] proposed a new scheduling method to order products in supply chain system. Deadlocks may arise while managing multiple supply chain flows simultaneously. To prevent capital chain ruptures and increase the suppliers money flow by adopting a famous deadlock avoidance Banker's algorithm and for this method correctness SPIN tool [14] is used. Youming Li [7, 15, 16] proposed an improved method over traditional Dijkstra's algorithm [17] in an optimal way without losing the simplicity of the data structures and also a graph-free with the cost of linear dependence on the number of the processes, with fixed number of resources and when the units of requests for resources are bounded by constants. But this is not practically possible with resource requests are constant. Begum et al. [18] proposed a safety detection algorithm over bankers algorithm [17] using linked list data structure to store resource requests and applied radix sort for comparisons to find safety sequence with the cost of linear dependence on number of the processes and number of resources. Agrawal.et al. [3] proposed deadlock free resource reservation technique which is fairly allocating resources to all processes for their successful completion. But this has not give details of how to estimate resources sufficient for deadlock free system.

Another category of resource reservation policies which are improved over traditional deadlock avoidance algorithms by reserving some number of resources proposed by authors [19] [20] [21] . In this approach also considering maximum resource requirement known in advance is a major drawback. To overcome this drawback authors [22, 23] propose budget concept which is dynamically adjusts and reserve the resources for reducing the safety sequence calls overhead in traditional avoidance algorithms.

The Resource Reservation (RR) Techniques suggest to reserve some resources that can be used to avoid the deadlock. Botlagunta et al. [20] first introduced this idea and suggested to reserve resources based on a threshold. Agrawal et al. [19] suggested to use the total need of the processes to reserve the resources. The process with minimum worst case execution time reserved the resources as suggested in [21] . Kumar et al. [24] , extended the technique suggested in [21] to reserve the resources based on the remaining resource need. Botlagunta et al. [22, 23] extended the RR techniques to dynamically allocate a budget of resources to each incoming process and perform resource reservation as per the technique suggested in [19, 20] . These techniques are discussed in detail in the subsequent section. All the deadlock avoidance techniques have high computation time as they must perform some test before each allocation to avoid deadlock. The Resource Reservation (RR) techniques eliminated this test for deadlock avoidance and thus, reduce the turnaround time of the processes.

Both DA and RR techniques presume that the system resource requirement is known in advance. The DA techniques perform some kind of test for ensuring that the deadlock will not occur in the future. However, the Resource Reservation techniques do not perform any test rather use the knowledge of the resource requirement for estimating the portion of resources that must be reserved to avoid deadlock. The resource reserved by different RR Techniques existing so far is not sufficient for completely avoiding the deadlock. The present work extends the idea of the (RR) techniques to use the knowledge of the resource requirement by the processes for estimating the reserve pool strength. The proposed technique ensures that all the processes have the opportunity to complete with the reserved resources.

This work is an extension of the Deadlock-free resource reservation techniques (DFRR) [3] . The DFRR technique is free from deadlocks and its effectiveness is proved in the form of theorems. However, DFRR does not suggests how to estimate the resources that would be sufficient for a deadlock-free system. This work reexamines the DFRR technique from the systems point of view and proposes resource driven Deadlock free resource reservation (DFRR) technique. It considers a system that has a finite set of resources and manages its resources for a process set ensuring deadlock-free implementation. The system model used in this work is the same as used in [3] . The system consisting of R 1 ; R 2 ; R 3 . . .R m resources with a 1 ; a 2 ; a 3 . . .a m instances of each type. These resources are portioned into Reserve[j]and Available[j] pools. This system executes n independent processes P 1 ; P 2 ; P 3 . . .P n with their maximum resource requirement represented as The theorem 1, estimates the optimal resources used for a deadlock-free system. The DFRR further, investigates the systems with lower resources and suggests theorem 2 for a deadlock-free management. The proposed resource driven DFRR works on the same principle as DFRR but it examines the resources required by the processes and that available in the system. It suggested to reserve some resources in the reservation pool. The remaining resources are made available in the available pool. Whenever, a process requests for a set of resources, available pool resources are granted. In case the request cannot be granted only from the available pool then the reserved pool resources are also used such that the maximum resources this process can ever want are granted, giving it the chance to complete.

The theorem 1 is presented below to estimate the optimal number of resources needed for a deadlock-free system. Theorem 1 A system with a 1 ; a 2 ; a 3 . . .a m f ginstances of resource types R 1 ; R 2 ; R 3 . . .R m f gcan schedule a set of independent processes P 1 ;

j from available and reserve pool put together such that the available pool is consumed first. That is a process must acquire all the resource it might need. iv. A process P i on completion relinquishes all the resources, Max i ½ j ½ 8R j , that are returned to the reserve and available pools as per condition i.

Proof By definition:

In worst case as per the condition iii. a. the resources any process can acquire is as per Eq. (2) .

Thus, each process needs Reserve j ½ resources to complete it's execution.

Total number of resources allocated to all the processes is

Substituting Eq. (1) and (2) in (3) )

. .m is a generic deadlock-free system because it has more resources then it can ever consume with all the processes holding their complete set. However, a system with a j ¼

Á has optimal number of resources. This is actually under-utilization of resources. This value will always be lower than

. .m, indicating that the DFRR can achieve deadlock-free system with lower number of resources. This estimated a j ¼

The overhead is only O n ð Þ for estimating the reserve pool initially. This technique as with all other reservation technique does not perform any kind of testing before allocating the resources and hence, has minimal overhead.

The following example illustrates the effectiveness of the proposed technique and compares it with other existing reservation techniques.

Example: consider a set of processes P 1 ; P 2 ; P 3 ; P 4 ; P 5 f g with the resource requirement as suggested in Table 1 The chronological sequence of resource requests as shown in the Table 2 .

The resource management by all the existing techniques is examined in the following subsections 1. Banker's algorithm (BA) [9] : The Banker's algorithm estimates the safety sequence (SS) before each request is granted or not granted. Table 2 , displays the set of request made by the process set. All the requests Req 1 À Req 16 ð Þ , are granted and the safety sequence is estimated as P 1 ; P 2 ; P 3 ; P 4 ; P 5 h i . The system status can be viewed in the Table 3 . The unallocated resources are (2, 2, 3, 3). However, when the request Req 17 for (0, 0, 0, 1) by process P 5 is made the BA does not find a SS, implying that it is a unsafe state. The process P 5 is sent to the pending queue. Similarly, the requests of the process P 4 ; P 3 ; P 2 are also not granted and after the SS estimation they all are sent to the pending queue. Finally, all the requests Req 21 À Req 30 ð Þ (refer Table 2 ) of process P 1 are granted step wise. Once the process P 1 completes it releases all the resources it was holding and processes from the queue are retrieved. Þare granted by this technique also, this is same as the BA and the system is in safe state so far. Its state is as shown in Table 4 . The following request Req 16 for (0, 1, 0, 0) by process P 1 cannot be granted from the Available pool so it is given resources from the reserve pool. The process thus, gets all the resources it need and completes and releases the resources it was holding. These resources can then be used by the remaining process likewise. 3 ð Þare all granted, the available pool is then (0, 0, 0, 1). The reserve pool is untouched. The request Req 17 for (0, 0, 0, 1) by process P 5 can be satisfied from the available pool and is also granted. The state of the system is as in Table 5 . The reserve pool resources (2, 2, 3, 2) is insufficient to satisfy the need of any of the process thus, the system in an unsafe state and will eventually end in a deadlock. 4. Worst-case execution time based resource reservation (ETRR) Technique [7] : The shortest execution time process is selected for the resource reservation. In the example given in Table 1 , the shortest process is P 1 thus, (5, 6, 3, 4) resources are reserved. The requests Req 1 toReq 9 ð Þare granted, however request Req 10 for (1, 1, 0, 0) by processP 4 , cannot be satisfied from the available pool. The process is thus, assigned resources from the available and reserve pool put together. It then completes and hand over the resources it was holding. This technique works well when the resource requirement of the shortest process is high. However, if the shortest job was process P 2 then this system would have ended in a deadlock. Int. j. inf. tecnol.

The proposed resource driven DFRR technique considers the nascent system in the Table 1 with no initial allocation. The reserve pool is estimated using equation Þfor the resources are granted and the system state can be seen the Table 4 .It may be noted that the safety sequence is never calculated and reserve pool is also estimated only once. When the request Req 16 is made by P 1 the available pool is empty so the resources from the reserve pool are allocated to it to accelerate its completion lowering its turnaround time. Elimination of the SS estimation also lowers the wait time and hence, the turnaround time of all the processes. The process P 1 on its completion releases all the resources it is holding and system continues its operation.

Another interesting question to ask is what happens if number of resources in the system are lower than a opt j that is a j  opt j ? If the resources can be allocated as per the theorem 1, the system may end up in a deadlock. The resource driven DFRR technique suggests to modify the resource allocation policy whose correctness is proved in the theorem 2. Theorem 2 A system with a 1 ; a 2 ; a 3 . . .a m f ginstances of resource types R 1 ; R 2 ; R 3 . . .R m f gcan schedule a set of independent processes P 1 ; P 2 ; P 3 . . .P n f g with resource requirement as Max i ½ j ½ , in deadlock-free manner if a j ! d Max i ½ j ½ ð Þ ewhere i. g j is the number of processes requesting for the resource R j i.e., count Max i ½ j

resources from the available pool such that a j a opt j , OR b. Max i ½ j ½ 8R j from available and reserve pool put together such that the available pool is consumed first. That is a process must acquire all the resource it might need. iv. A process P i on completion relinquishes all the resources, Max i ½ j ½ 8R j , that are returned to the reserve and available pools as per condition i.

Proof Proving by contradiction that total resources allocated are greater than available in the system:

Substituting in (4):

Substituting in (5) :

as per the equation iii. a. from theorem 2.

In worst case g j ¼ n implying that the resource is being used by all the processes in the system. Safety sequence \ P 1 , P 2 , P 3 , P 4 , P 5 [ Safety sequence \ P 1 , P 2 , P 3 , P 4 , P 5 [ Max i ½ j ½ À ðn À 1Þ Ã Reserve j ½ À n à a opt j À a j n À 1

Substituting as suggested in the theorem 2 iii. a. ;

In worst case g j ¼ n implying that the resource is being used by all the processes in the system. Therefore,

However, a j  opt j , hence contradiction. Therefore, P n i¼1 Allocation i ½ j ½ Available j ½ ; 8R j , implying that the system remains feasible. Hence Proved. h

In the above example if the resources are reduced from a opt ¼ 12; 9; 7; 7 ð Þtoa ¼ ð10; 8; 6; 6Þ. The total allocation possible is P n i¼1 Allocation i ½ ½ ¼ ð6; 4; 2; 1Þ, as per condition iii. a. from theorem 2, therefore the remaining resources are 10; 8; 6; 6 ð ÞÀ 6; 4; 2; 1 ð Þ¼ð 4; ; 4; 4; 5Þ, sufficient for any process to complete hence, this system remains deadlock free with lower resources also. The following section present the simulation results.

This section presents the results of the simulations performed on the synthesized process sets generated. The performance of the proposed DFRR is compared with various existing techniques.

Resource instances Vs. Avg. turnaround time:

a) Fig. 1 shows the effect of change in the number of instances a j À Á of a resource type on the average turnaround time of the process set. 100 process sets were generated with 6 processes, and one resource type and its distribution the same in all the process sets. The instances of the resource are varied from its minimum acceptable value of d Max i ½ j ½ ð Þ e(as per theorem 2) to P n i¼1 Max i ½ j ½ À Á . The DFRR performs best at the a opt . The DFRR performs approximately 18% better than the BA. This is because as the number of resources is reduced the BA sends the processes into pending queue over and over again. The same is indicated by the example. All the reservation techniques promote the process with resource crunch to assist it to complete. However, the TRA, TNRR, and ETRR sometimes land into deadlock increasing their average turnaround time. Resource bound Vs. Avg. Turnaround Time: a process can be resource bound or CPU bound [2, 25, 26] . A CPU bound process is a process whose major execution depends on the CPU and it has little or no resource requirement. Similarly, if the process execution depends on the resources then such a process is resource bound. b) Fig. 2 

This paper presented a new resource reservation technique for resource management in shared resource systems. The proposed DFRR technique is a deadlock-free resource management technique. Unlike other resource reservation techniques, DFRR suggests resource management based on the resources in the system. It suggests a deadlock free resource management for minimal resource system. It also suggests the optimal number of resources needed for a process set to efficiently execute on a system. The correctness of the technique is proved in the form of two theorems. The theorem 1, answers, given a process set how many resources will be sufficient for its efficient execution. While theorem 2, suggest resource management based on the resources available in the system to the demanding process set. Its effectiveness is demonstrated by an example and simulation results.

The DFRR belongs to resource reservation class of deadlock handling techniques. This class of techniques eliminate the excessive overhead incurred by the Deadlock Prevention and Avoidance techniques as well as the uncertainty of deadlock occurrence in the deadlock detection and recovery techniques. In other words, the proposed technique achieved deadlock freeness as any deadlock avoidance technique with the overhead of a deadlock detection and recovery technique, which is optimal. The overhead in these technique is only for the reservation pool estimation. The proposed technique estimates the reservation pool by finding a minimum in an array of 'n' where 'n' is the number of processes in the system. Hence, the overhead for reservation pool estimation is OðnÞ.The simulation results indicate that the turnaround time of the proposed DFRR is approximately 18% better than the existing Banker's algorithm. Thus, the proposed technique is a deadlock-free technique with optimal overhead.

This work considers resource management based on the resources available in the system to the demanding process set. This work can be applied to study resource management during hospitalization due to the present pandemic of Covid-19.

Transient fault tolerance patterns for real time systems with arbitrary deadline

Checkpointing based fault tolerance patterns for systems with arbitrary deadlines

Deadlock free resource management technique for iot-based post disaster recovery systems

Resource scheduling for postdisaster management in IoT environment

System deadlocks

Gadara: Dynamic deadlock avoidance for multithreaded programs

A modified Banker's algorithm

Implementation resource request alghoritm in simulation of deadlock avoidance

Reliable resource provisioning using bankers' deadlock avoidance algorithm in MEC for industrial IoT

A modified synchronization model for dead-lock free concurrent execution of strongly interacting task sets in embedded systems

Performance Impact of Lock-Free Algorithms on Multicore Communication APIs

Searching feasible resources to reduce false-positive situations for resolving deadlocks with the Banker's algorithm in railway simulation

The Application of Banker's Algorithm in Order Scheduling Management for Deadlock Avoidance Software Product Line View project ICT Software Platform View project

SPIN model checking: an introduction

On Dijkstra's algorithm for deadlock detection

A new algorithm and asymptotical properties for the deadlock detection problem for computer systems with reusable resource types

The mathematics behind the banker's algorithm. In: Selected writings on computing: a personal perspective. Texts and monographs in computer science

An Improved Safety Detection Algorithm Towards Deadlock Avoidance. ISCAIE 2020 -IEEE 10th Symposium on

A total need based resource reservation technique for effective resource management

An efficient resource allocation technique for uniprocessor system

Effective resource management technique using reservation pool

Dynamic budgetthreshold based resource reservation technique

Dynamic budget-total need based resource reservation technique

Modified execution time based resource reservation (METRR) algorithm

A speed fine tuning technique for system energy minimization of weakly hard realtime system

System level energy aware fault tolerance approach for real time system