International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2048

ISSN 2229-5518

An efficient method to avoid deadlock complexity for mutual exclusion.

Siddaraju K. 1, Dr. Sanjay Pande 2

1: Research Scholar, and Assistant Professor of Computer Science, .Maharani’s Science College for Women, Mysore-570005, Karnataka, India

2: Research Guide, Principal, SITAR, Belakere, Channapatna-562160, Karnataka, India

Absract_In a distributed system, the multiple processes want to share a common resource. All processes cannot access the resource at a time. The resource should be accessed by at most one process at a time. For example, in a system with multiple processes, some or all of the processes may wish to write to a common file. However, no two processes should be allowed to write to that file at the same time in order to ensure the integrity and consistency of the file. This problem is solved in this paper.

In this paper a distributed algorithm is proposed that realizes mutual exclusion among n nodes in a computer network. There is no common or

global memory shared by the nodes and there is no global controller. The nodes of the network communicate among themselves by exchanging messages only. Formally while one process executes the shared variable all other processes desiring to do so at the same time should be kept waiting. When that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed.

In this fashion, each process executing the shared files excludes all others from doing so simultaneously. This is called Mutual Exclusion. In this mechanism if a node wishes to invoke mutual exclusion then all other nodes are aware of this directly or indirectly that they may themselves not enter into their critical section. By this mutual exclusion we are ensuring that shared resource is accessed by at most one process at a time. So that integrity and consistency of the file is ensured.

In this paper we are implementing token based distributed mutual exclusion algorithm with a logical ring topology. Processes form a logical

ring where a token circulates in the ring. A process is allowed to execute in its critical section only if it possesses the token. W hen the process has finished its critical section, it passes the token to the successor node in the ring. The logical ring structure is attractive because it is simple, fair, and deadlock-free. The proposed algorithm is based on queue migration and achieves a message complexity of O(√n) per mutual exclusion

invocation. Under heavy load, the number of required messages approaches 2 per mutual exclusion.

1. INTRODUCTION:

—————————— ——————————
The main purpose of this paper is to provide mutual exclusion of shared object in a distributed system. In a system with multiple processes which must share a common resource, it may be necessary to avoid multiple simultaneous access to that resource. Mutual exclusion ensures that the shared resource is accessed by at most one process at a time. For example, in a system with multiple processes, some or all of the processes may wish to update a common file. However, no two processes should be allowed to write to that file at the same time in order to ensure the integrity and consistency of the file. The section of code that allows for such mutual exclusive access of the shared resource is often referred to as the critical section [1,
2].
In a centrally controlled system, we can implement the mutual exclusive use of the shared object by Semaphores and monitors. In a distributed environment, mutual exclusion is complex due to the absence of a global or centralized controller, which makes these abstract data types ineffective. Possibility of data loss during the simultaneous access of same resource is also high Integrity and consistencies of files are also not ensured. The solution to this problem is provided using queue migration algorithm which achieves a message complexity of O(√n) per mutual exclusion invocation. In this paper we are implementing token based distributed mutual exclusion algorithm with a logical ring topology. Processes form a
logical ring where a token circulates in the ring. A process

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2049

ISSN 2229-5518

is allowed to execute in its critical section only if it possesses the token. When the process has finished its critical section, it passes the token to the successor node in the ring. The logical ring structure is attractive because it is simple, fair, and deadlock-free [5].

2. PROBLEM STATEMENT:

In a distributed system, the multiple processes want to share a common resource. All processes cannot access the resource at a time. The resource should be accessed by at most one process at a time. For example, in a system with multiple processes, some or all of the processes may wish to write to a common file. However, no two processes should be allowed to write to that file at the same time in order to ensure the integrity and consistency of the file. This problem is solved in this paper.

3. LITERATURE SURVEY:

BANERJEE AND CHRYSANTHIS [11]: A non symmetric deadlock-free mutual exclusion algorithm for computer networks is presented. The algorithm requires O(m) messages to synchronise m nodes in a lightly load based system, and the performance approaches a constant k dependent on m as the workload increases. In a medium to heavily load system it outperforms other proposed algorithms and its performance is independent of network topology. A node k (request collector) is selected at initialization to which requests are sent from nodes wishing to enter the critical section. Node k also holds the token. When a request is received at node k the request queue at k is copied to the token and is sent to the node indicated at the front of the queue.

Node k broadcasts a message to all nodes announcing a new request collector, the node at the rear of the token queue. The token is passed from node to node in the order presented in the token queue until the last node is reached. The token is now appended to the request queue at the request collector node and the process is repeated. In the
event that a node had requested to node k before it received the broadcast but after the token was sent, node k transfers the token to the new request collector. The message complexity is O(n) under light load and tends to 3 messages per critical section invocation under heavy load [3,4]. In the existing distributed system a token based distributed algorithm is used for mutual exclusion. The request collector holds the token. When it receives request the request queue at the request collector is copied to the token and it is sent to the node which is at the front of the request queue.
Drawbacks of the existing system:
• The existing system achieved a message complexity of
O(n) using the above algorithm under light load.
• This algorithm requires 3 messages per critical section
invocation under heavy load.
• Nodes are not grouped into a local group because of
which the message complexity is O(n).

PRANAY CHAUDHURY AND THOMAS EDWARD [8]: In this paper a distributed algorithm is proposed that realises mutual exclusion among n nodes in a computer network. There is no common or global memory shared by the nodes and there is no global controller. The nodes of the network communicate among themselves by exchanging messages only. The proposed algorithm is based on queue migration and achieves a message complexity of O(√n) per mutual exclusion invocation. Under heavy load, the number of required messages approaches 2 per mutual exclusion. The network is assumed to be fully connected. We partition the n nodes of the network into √n sets of √n nodes each. Each set is called a local group (LG). Nodes in a local group can communicate directly with each other for the purposes of entering the critical section. That is, all nodes in a local group are fully connected. One node from each group is selected to form part of the global group (GG). This node is called a link-node [6]. Each node of the

global group can communicate with all other nodes of the

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2050

ISSN 2229-5518

global group and also with all nodes of its local group to which they belong. In every local group, there exists a node designated as the local request collector (LRC) known to all nodes in that group. When a node of a local group wants to enter the critical section it sends a request message to the LRC. The LRC enqueues all requests received into its local request queue. Every node maintains a local request queue. If the request collector is holding the idle token, the local request queue is copied to the token queue and the token together with the token queue are sent to the node which is at the front of the token queue. A request collector message is then sent to all nodes in the local group to indicate that the last node in the token queue is the new LRC. It must be noted that whenever a request queue or part thereof is copied to the token queue all nodes copied are deleted from the request queue [11,12].
A requesting node, upon receiving the token, deletes its node id from the token queue and enters the critical section. Upon completion of the critical section operation it forwards the token to the next node in the token queue. The process is repeated until the last node of the token queue, that is, the new LRC, is reached. Meanwhile, the new LRC may be receiving new request messages from other nodes, that is, the new LRC is in the request collecting phase. A node, which previously was an LRC, may receive a request message sent to it just before the new LRC information was received by the requesting node. This request is simply forwarded to the new LRC.
In the global group, there exists a node designated
as the global request collector (GRC) known to all nodes in the group. Each link-node maintains a variable that holds the node id of the GRC of the global group. In addition to the local request queue, a global node also maintains a global request queue. If a local group does not possess the token the link-node will be the LRC of its local group.
When a node from such a local group wants to enter the critical section it sends a request message to the
LRC which then forwards a request message to the GRC.
The GRC, enqueues the request message in a global request queue, maintained for that purpose, and a marker is inserted into the local request queue of the GRC. If the GRC has the token and is idle, the token is sent to the requesting link-node. Otherwise, it must wait for the token to arrive [7].

PETERSONS ALGORITHM:

A classic software based solution to the critical section problem known as Peterson’s solution which is restricted to two processes that alternate execution between their critical sections and remainder sections.

BOUNDED-BUFFER PROBLEM:

The bounded buffer problem is used to illustrate the power of synchronization primitives. The mutex semaphore provides mutual exclusion for accesses to the buffer pool and is initialised to the value 1.the empty and full semaphores count the no of empty and full buffers. The semaphore empty is initialised to value n. the semaphore full is initialised to value 0.
The solution to this problem is provided by using semaphores and monitors. Even though an inadequate solution could result in a deadlock where where both processes are waiting to be awakened.

RESOURCE-ALLOCATION GRAPH:

A set of vertices V and a set of edges E in a resource allocation graph.
• V is partitioned into two types:
• P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
• R = {R1, R2, …, Rm}, the multi-set consisting of all
resource types in the system.
• request edge – directed edge P1 → Rj
• assignment edge – directed edge Rj → Pi
If graph contains no cycles ⇒ no deadlock.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2051

ISSN 2229-5518

If graph contains a cycle ⇒
• if only one instance per resource type, then deadlock.
• if several instances per resource type, possibility of
deadlock

RESOURCE ALLOCATION GRAPH WITH RESPECT TO OUR PAPER:

In the present work, we are providing a solution to avoid deadlock where the shared files can be accessed by only one at a time. To avoid deadlock we are using a distributed algorithm which is token based where there is only one token present in the network. The system having the token can access the shared files otherwise it should wait in the queue to access the shared file until it is released by the one who is using it. Hence this algorithm provides a solution which is deadlock-free.

BANKERS ALGORITHM

The Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of pre-determined maximum possible amounts of all resources, and then makes a "safe-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue [9].
The Banker's algorithm is run by the operating system whenever a process requests resources. The algorithm avoids deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where deadlock could occur).
When a new process enters a system, it must declare the maximum number of instances of each resource type that may not exceed the total number of resources in
the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.
For the Banker's algorithm to work, it needs to know three things:
• How much of each resource each process could possibly request
• How much of each resource each process is
currently holding
• How much of each resource the system currently has available
Resources may be allocated to a process only if it satisfies the following conditions:
• request ≤ max, else set error condition as process
has crossed maximum claim made by it.
• request ≤ available, else process waits until
resources are available.
Basic data structures to be maintained to implement the
Banker's Algorithm:
Let n be the number of processes in the system and m be the number of resource types. Then we need the following data structures:

Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.

Max: An n×m matrix defines the maximum demand of each process. If Max[i,j] = k, then Pi may request at most k instances of resource type Rj.

Allocation: An n×m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j] = k, then process Piis currently allocated k instance of resource type Rj.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2052

ISSN 2229-5518

Need: An n×m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then Pimay need k more instances of resource type Rj to complete task.

SAFETY ALGORITHM:

1. Let Work and Finish be vectors of length m and n, respectively.
Initialize: Work = Available; Finish [i] = false for i = 0, 1, …, n- 1.
2. Find and i such that both:
(a) Finish [i] = false ; (b) Needi ≤ Work; If no such i exists,
go to step 4.
3.Work= Work + Allocationi ; Finish[i] = true
go to step 2.
4.If Finish [i] == true for all i, then the system is in a safe
state.
The Banker's algorithm avoids deadlock by denying the request if it determines that accepting the request could put the system in an unsafe state. In our paper deadlock is avoided by denying the request when some other is accessing the shared file. But when the request is denied the system can wait in the queue so that after the shared file is released it can be accessed.

PROPOSED SYSTEM:

The proposed system uses a token based queue migration algorithm and achieves a message complexity of O(√n) per mutual exclusion invocation and only one token
exists in the network. Permission to enter the critical section is granted by the only by acceptance of the token, thus security, Integrity and consistency of files is ensured.
In a distributed system, nodes in the computer network can communicate only by exchanging messages. Formally, while one process executes the shared variable, all other processes desiring to do so at the same time should be kept waiting. When that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed.
In this fashion, each process executing the shared
data (variables) excludes all others from doing so simultaneously. This is called Mutual Exclusion. In this mechanism if a node wishes to invoke mutual exclusion then all other nodes are aware of this directly or indirectly that they may themselves not enter into their critical section. By this mutual exclusion we are ensuring that shared resource is accessed by at most one process at a time. So that integrity and consistency of the file is ensured.
In the proposed system n nodes are grouped into
√n sets of √n nodes each. each set is called local group(LG). The network is assumed to be fully connected. We partition the n nodes of the network into √n sets of √n nodes each. Each set is called a local group (LG).
Nodes in a local group can communicate directly with each other for the purposes of entering the critical section. That is, all nodes in a local group are fully connected. One node from each group is selected to form part of the global group (GG).This node is called a link- node. Each node of the global group can communicate with all other nodes of the global group and also with all nodes
of its local group to which they belong [10].

IMPLEMENTATION:

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2053

ISSN 2229-5518

This flowchart shows how an IP address of a system connected to a Local Area Network is retrieved. First the hostname of the system will be retrieved and then the address list will be retrieved using host.addresslist then the addressfamily of it will
be compared with internetwork which is IPV4 format, if it matches then the IP address will be assigned to the localIP variable.

FLOWCHART 2:

FIGURE: FLOWCHART 1

This flowchart shows how the shared files are accessed. The shared files are displayed in the list box. The contents of the list box are cleared. If we select the IP address the shared files of that system will be displayed. Then if select one of the
shared files is selected and if we click the “open requested file” button the contents of the files will be displayed.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2054

ISSN 2229-5518

RESULTS :

FIGURE: FLOWCHART 2

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2055

ISSN 2229-5518

In the snapshot we can see the list of IP addresses of all the systems connected in the Local Area Network in the first column. The IP address of the local system is also present at the bottom left corner as shown in snapshot.

In the snapshot we can see that after selecting the IP address the list of the shared files present in that system is displayed.

In the snapshot we can see the shared object of the IP address 192.168.1.60 is present in second column. When the shared object is selected and the “open requested file” button is clicked the file contents is displayed as shown in the snapshot.

In this snapshot we can see that when the shared file which is being used by other system is tried to open a message is displayed asking whether you want to wait in queue as shown in snapshot.

The snapshot shows that when a shared file being accessed is released by clicking a “release requested file” button a message is displayed as shown.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2056

ISSN 2229-5518

The snapshot shows that when we want to view the queue and history we can click on the view log as shown and select view queue or view history.

In this snapshot we can see the current requested queue for files which shows who is waiting in queue with details such as qID, IP address of that system, file name for which it is waiting, access date of that file, access time of that file.

The snapshot shows that we can remove the request from the queue by selecting the file and right click on it and remove the request.

The snapshot we can see the history of the file accessing in network which shows the fileID, IP address of the system, filename, token, access date of the file, access time of that file and the checkbox which tells whether the file is open or close.

CONCLUSION:

Operating systems and principles is one of subjects where we study many things like process scheduling algorithms, synchronization problems and so on. Among all these deadlock is a very interesting topic where we
studied various methods to avoid deadlock. But all those methods were not efficient in solving the deadlock problem. Our paper also suggests one of the efficient methods to avoid deadlock and has achieved a message complexity of O(√n) and under heavy load, the number of
required messages approaches 2 per mutual exclusion. To

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 7, July-2013 2057

ISSN 2229-5518

achieve this objective we have used .NET technology. Currently in our paper the system can use the shared resource for a long period there is no time limit, which leads to starvation. If the checkbox is checked the file is open otherwise it is closed. We can also search the history by entering the IP address in the textbox present at the top left corner or by selecting the date in the calendar present at top right corner. Also in our paper we have used only text files for sharing.

REFERENCES:

[1] G. Ricart and A. K. Agrawala, Author’s response to ‘On mutual exclusion in computer networks by Carvalho and Roucairol’, Communications of the ACM
26. 1983, 147 - 148.
[2] J. M. Helary, N. Plouzeau and M. Raynal,
A distributed algorithm for mutual
exclusion in an arbitrary network,
Computer Journal 31, 1988, 289 - 295.
[3] L. Lamport, Time, clocks and the ordering
of events in a distributed system,
Communications of the ACM 21, 1978,
558-565.
[4] M. G. Velazquez, A survey of distributed
mutual exclusion algorithms, Technical
Report CS-93-116, September 1993.
[5] M. Maekawa, A √n algorithm for mutual
exclusion in decentralized systems. ACM
Transactions on Computer Systems 3,
1985, 344 - 349.
[6] O. Carvalho and G. Roucairol, On mutual exclusion in computer networks, Communications of the ACM 26, (1983)
147 - 148.
[7] Peerapon Siripongwutikorn, Sujata
Banerjee and David Tipper "Fuzzy-Based
Adaptive Bandwidth Control for Loss Guarantees,", IEEE Transactions on Neural Networks, vol. 16, No. 5, September 2005.
[8] Pranay Chaudhuri, Thomas Edward, An
O(√n) Distributed Mutual Exclusion
Algorithm Using Queue Migration, Journal of Universal Computer Science, vol. 12, no. 2 (2006), 140-159, submitted:
18/1/05, accepted: 20/10/05, appeared:
28/2/06 c J.UCS
[9] Priya Mahadevan, Sujata Banerjee, Puneet Sharma, Amip Shah and Partha Ranganathan,On Network Energy Efficiency for Data Centers and Enterprise Networks," IEEE Communications Magazine, August 2011
[10] Puneet Sharma, Zhichen Xu, Sujata Banerjee and Sung-Ju Lee "Estimating Network Proximity and Latency,", ACM Sigcomm Computer Communications Review, Volume 36, Number 3, pages 39-
50, July 2006.
[11] S. Banerjee and P. K. Chrysanthis, A new
token passing distributed mutual
Exclusion algorithm, Proceeding of Intl.
Conf. on Distributed Computing Systems
(ICDCS), Hong Kong, 1996, 717 - 724.
[12] Sujoy Basu, Lauro B. Costa, Franscisco
Brasileiro, Sujata Banerjee, Puneet Sharma
and Sung-Ju Lee,"NodeWiz: Fault-
Tolerant Grid Information Service,"
Springer Journal: Peer-to-Peer Networking and Applications, March 2009.

IJSER © 2013 http://www.ijser.org