all OS assignments ----- chandy lamport,misra hass , raymond's tree , ho ramamurthy ------

os.txt

----------------------------------------------------------------------------------------------------------------------------
graph initiator
----------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n,**adj,incount0=0,i,j,*source,*non_sink,i1=0,i2=0;
	printf("\nEnter number of nodes:");
	scanf("%d",&n);
	printf("\n\nYou have entered %d!!",n);
	adj=(int**)malloc(sizeof(int*)*n+1); /* Allocating memory for adjacency matrix of size n+1 * n+1 */
	for(i=0;i<n+1;i++)
		adj[i]=(int*)malloc(sizeof(int)*n+1);
	source=(int*)malloc(sizeof(int)*n); /* Allocating an array to store the source nodes */
	non_sink=(int*)malloc(sizeof(int)*n); /* Allocating an array to store the non-sink nodes */
	printf("\n\nEnter the graph:\n");
	for(i=0;i<n+1;i++) /* Initializing the adjacency matrix with 0s */
		for(j=0;j<n+1;j++)
			adj[i][j]=0;
	for(i=0;i<n;i++)	
	{
		for(j=0;j<n;j++)
		{
			printf("\nIs their is an edge  %d ---> %d?(1=YES,0=NO): ",i+1,j+1);
			scanf("%d",&adj[i][j]);
		}
		printf("\n");
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			adj[i][n]+=adj[i][j]; /* Obtaining the sum of out-degrees */
		}
		if(adj[i][n]!=0)
			non_sink[i2++]=i+1;  /* Storing all non-sink nodes in array non_sink */
	}
	for(j=0;j<n;j++)
	{
		for(i=0;i<n;i++)
		{
			adj[n][j]+=adj[i][j]; /* Obtaining the sum of in-degrees */
		}
		if(adj[n][j]==0)
		{
			incount0++; /* Counting source nodes, i.e. nodes with in-degree 0 */
			source[i1++]=j+1; /* Storing all source nodes in array source */
		}	
	}
	printf("\n\nThe matrix representation of this graph:\n\n"); /* Displaying the adjacency matrix, with nth column having sum of out-degrees of each node and nth column having sum of in-degrees of each node */
	for(i=0;i<n+1;i++)
	{
		for(j=0;j<n+1;j++)
		{
			printf("%d\t",adj[i][j]);
		}
		printf("\n");
	}
	if(incount0>1) /* Condition 1: If there is more than one source node, then none of the nodes can be initiator */
		printf("\n\nResult:\n\n\tNone of the nodes can be initiator!");
	else if(incount0==1) /* Condition 2: If there is only one source node, then it is the only initiator */
		printf("\n\nResult:\n\n\tThe only initiator can be: node[%d] !",source[0]);
	else /* Condition 3: If there is no source node, then the non-sink nodes can be initiator  */
	{
		printf("\n\nResult:\n\n\tThe initiator nodes are: nodes[");
		for(i=0;i<i2;i++)
			printf("%d ,",non_sink[i]);
		printf("]");
	}
	return 0;
}
-----------------------------------------------------------------------------------------------------------------------
chandy mishra hass


Chandy-Misra-Haas’s distributed deadlock detection algorithm is an edge chasing algorithm to detect deadlock in distributed systems.

In edge chasing algorithm, a special message called probe is used in deadlock detection. A probe is a triplet (i, j, k) which denotes that process Pi has initiated the deadlock detection and the message is being sent by the home site of process Pj to the home site of process Pk.

The probe message circulates along the edges of WFG to detect a cycle. When a blocked process receives the probe message, it forwards the probe message along its outgoing edges in WFG. A process Pi declares the deadlock if probe messages initiated by process Pi returns to itself.



Other terminologies used in the algorithm:

Dependent process:
A process Pi is said to be dependent on some other process Pj, if there exists a sequence of processes Pi, Pi1, Pi2, Pi3…, Pim, Pj such that in the sequence, each process except Pj is blocked and each process except Pi holds a resource for which previous process in the sequence is waiting.
Locally dependent process:
A process Pi is said to be locally dependent on some other process Pj if the process Pi is dependent on process Pj and both are at same site.
Data structures:
A boolean array, dependenti. Initially, dependenti[j] is false for all value of i and j. dependenti[j] is true if process Pj is dependent on process Pi.

Algorithm:

Process of sending probe:

1. If process Pi is locally dependent on itself then declare a deadlock.

2. Else for all Pj and Pk check following condition:

(a). Process Pi is locally dependent on process Pj
(b). Process Pj is waiting on process Pk
(c). Process Pj and process Pk are on different sites.
If all of the above conditions are true, send probe (i, j, k) to the home site of process Pk.

On the receipt of probe (i, j, k) at home site of process Pk:

1. Process Pk checks the following conditions:


(a). Process Pk is blocked.
(b). dependentk[i] is false.
(c). Process Pk has not replied to all requests of process Pj
If all of the above conditions are found to be true then:

1. Set dependentk[i] to true.
2. Now, If k == i then, declare the Pi is deadlocked.
3. Else for all Pm and Pn check following conditions:

(a). Process Pk is locally dependent on process Pm and
(b). Process Pm is waiting upon process Pn and
(c). Process Pm and process Pn are on different sites.
4. Send probe (i, m, n) to the home site of process Pn if above conditions satisfy.


Thus, the probe message travels along the edges of transaction wait-for (TWF) graph and when the probe message returns to its initiating process then it is said that deadlock has been detected.

Performance:

Algorithm requires at most exchange of m(n-1)/2 messages to detect deadlock. Here, m is number of processes and n is the number of sites.
The delay in detecting the deadlock is O(n).
Advantages:

There is no need for special data structure. A probe message, which is very small and involves only 3 integers and a two dimensional boolean array dependent is used in the deadlock detection process.
At each site, only a little computation is required and overhead is also low
Unlike other deadlock detection algorithm, there is no need to construct any graph or pass nor to pass graph information to other sites in this algoirthm.
Algorithm does not report any false deadlock (also called phantom deadlock).
Disadvantages:
The main disadvantage of a distributed detection algorithms is that all sites may not aware of the processes involved in the deadlock this makes resolution difficult. Also, proof of correction of the algorithm is difficult.
----------------------------------------------------------------------------------------------------------------------
#include<stdio.h>

int main()
{
int p[10],n,i,p1,s1,sp1,sp2;
printf("Enter total no. of sites\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter total no. of process in S%d\n",i+1);
scanf("%d",&p[i]);
}
for(i=0;i<n;i++)
{
printf("Total no. of process in S%d are %d\n",i+1,p[i]);
}
printf("Enter the site no. and process id for which deadlock detection should be initiated\n");
scanf("%d %d",&s1,&p1);
printf("Enter  the processes of two different sites connected with requesting edge\n");
 scanf("%d %d",&sp1,&sp2);
printf("Probe message is (%d,%d,%d)",p1,sp1,sp2);    //probe message  generation 
if(p1==sp2)       //checking if the last process of the site is same as the 1st process of the other  site 
{
printf("Deadlock detected");
 }
else
{
printf("no Deadlock detected");
}
return 0;
}

-------------------------------------------------------------------------------------------------------------------------
chandy lamport
-------------------------------------------------------------------------------------------------------------------------
import queue
class node(object):
    def __init__(self, name, balance):
        self.name = name
        self.temp_state = []
        self.recorded_state = []
        self.is_recorded = False
        self.out_channel_list = []
        self.in_channel_list = []
        self.balance = balance
        self.msg_count = 0
        self.last_marker_from = None
 
    def add_channel(self, channel):
        self.channel_list.append(channel)
 
    def send_marker(self, except_):
 
        # except_ = self.last_marker_from
        for chnl in self.out_channel_list:
            if except_ != None:
                if chnl.rcvr.name == except_.name:  # send marker to everyone except to the channel through which the
                    # last marker was received
                    continue
            marker = message((str(self.name) + "_" + str(self.msg_count)), self, chnl.rcvr, 1)  # it's a marker
            marker.msg(-1)
            marker.send(self, chnl.rcvr, chnl)
            self.msg_count += 1
            self.temp_state.append(marker)  # temporarily make an entry for this message
 
    def record_state(self):
        self.recorded_state = True
        self.send_marker(None)
 
    def send_msg(self, rcvr_, val):
        temp_msg = message((str(self.name) + "_" + str(self.msg_count)), self, rcvr_, 0)
        temp_msg.set_type(0)  # setting type to send
        temp_msg.msg(val)
        self.msg_count += 1
 
        # selecting channel automatically
        i = 0
        for index in range(len(self.out_channel_list)):
            if self.out_channel_list[index].rcvr.name == rcvr_.name:
                i = index
 
        temp_msg.send(self, rcvr_, self.out_channel_list[i])
        self.balance -= val
        self.out_channel_list[i].message_queue.put(temp_msg)
        self.temp_state.append(temp_msg)  # temporarily make an entry for this message
 
    def receive_msg(self, sendr_):
        global target_channel, mssg
        global target_channel, mssg
        print("Recived a message")
        # check for the input queue for the first message
 
        global target_channel, mssg
        for chnl in self.in_channel_list:
 
            if chnl.sender.name == sendr_.name:
                target_channel = chnl
                if target_channel.message_queue.qsize() != 0:
                    mssg = target_channel.message_queue.get_nowait()
        if mssg == None: return
 
        # this message is not a marker then fine
        if mssg.marker == 0:
            val = mssg.msg
            self.balance += val
            self.temp_state.append(mssg)
            target_channel.local_state.append(mssg)
            print("Application message : appended")
        else:
            print("Got a marker")
            # if this is a marker then
            # if thi9s is the first marker
            if not self.recorded_state:
                self.recorded_state = True
                self.last_marker_from = target_channel.sender
                # record the state of channel as empty
                target_channel.local_state.clear()
                # sends the marker ro every one else
                self.send_marker(target_channel)
 
                # receive messages on every incoming channel except the current channel
                for channel_ in self.in_channel_list:
                    if channel_.sender.name == target_channel.sender:
                        continue
                    # get the message queue
                    for _ in range(channel_.message_queue.qsize()):
                        mssg = channel_.message_queue.get_nowait()
                        self.receive_msg(channel_.sender)
 
 
            else:
                # if this process itself hast not recorded it's state yet record it now
                # record this channel's state as set of messages sent after the this process has recorded it's state and
                # before this process received the marker
                chnl.temp_state.append(chnl.message_queue)
                print("Recording state:->", self.name)
 
    ###########################################
 
 
class channel(object):
    def __init__(self, sender, rcvr):
        self.sender = sender
        self.rcvr = rcvr
        self.message_queue = queue.Queue(maxsize=20)
        self.temp_state = []
        # adding the channel to sender list
        self.sender.out_channel_list.append(self)
        self.rcvr.in_channel_list.append(self)
        self.local_state = []
 
 
class message(object):
    def __init__(self):
        pass
 
    def __init__(self, id, sender_, rcvr_,
                 marker=0):  # marker represents that it is a snapshot request, by default False
        self.id = id
        self.type = -1
        self.marker = marker
        self.sender = sender_
        self.rcvr = rcvr_
 
    def set_type(self, type):
        if type == 0:  # send
            self.type = 0
        else:
            self.type = 1
 
    def msg(self, msg):
        self.msg = msg
 
    def send(self, sender, rcvr, channel):
        pass
 
 
process_list = []
 
process_1 = node(1, 50)
process_2 = node(2, 50)
process_3 = node(3, 50)
process_4 = node(4, 50)
 
process_list.append(process_1)
process_list.append(process_2)
process_list.append(process_3)
process_list.append(process_4)
 
channel_list = []
 
channel_12 = channel(process_1, process_2)
channel_13 = channel(process_1, process_3)
channel_14 = channel(process_1, process_4)
 
channel_21 = channel(process_2, process_1)
channel_24 = channel(process_2, process_4)
 
channel_32 = channel(process_3, process_2)
 
channel_43 = channel(process_4, process_3)
channel_42 = channel(process_4, process_2)
 
channel_list.append(channel_12)
channel_list.append(channel_13)
channel_list.append(channel_14)
channel_list.append(channel_21)
channel_list.append(channel_24)
channel_list.append(channel_32)
channel_list.append(channel_43)
channel_list.append(channel_42)
 
process_1.record_state()
 
process_1.send_msg(process_2, 5)
 
process_2.receive_msg(process_1)
 
process_1.send_msg(process_2, 10)
process_1.send_msg(process_3, 10)
 
process_3.receive_msg(process_1)
process_2.receive_msg(process_1)
process_2.send_msg(process_4, 10)
 
process_4.receive_msg(process_2)
process_2.record_state()
 
process_2.send_msg(process_3, 5)
 
# process_3.receive_msg(process_2)
 
process_3.send_msg(process_2, 3)
process_2.receive_msg(process_4)
 
#################### GLOBAL SNAPSHOT ###############
print("--------------- process state ---------------- \n")
for process in process_list:
    # print(process.temp_state)
    print("p_name:-> ", process.name, )
    print("balance: ", process.balance)
    print("message:")
    for mssg in process.temp_state:
        print("{ id:", mssg.id, ", marker:", mssg.marker, " to/from process:", mssg.rcvr.name, ", msg:", mssg.msg,
              " },")
 
    for channel in process.in_channel_list:
        print("channel state:")
        for mssg in channel.local_state:
            print("{ id:", mssg.id, ", marker:", mssg.marker, " to/from process:", mssg.rcvr.name, ", msg:", mssg.msg,
                  " },")
 
    print()
    print(".................")



---------------------------------------------------------------------------------------------------------------------------
ricart agrawala
-----------------------------------------------------------------------------------------------------------------------------

import java.util.*;
public class Ricartagrawala {
    public static int a=0;
	public static int count=0;
	public static int count1=0;
	public static int cs=0;
	public static void main(String[] args) throws InterruptedException{
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the number of process");
		final int n=sc.nextInt();
		final Process arr[]=new Process[n];
		final int ap[]=new int[100];
		for(int i=0;i<n;i++)
		{
			Process pop=new Process(i+1,0);
			
			arr[i]=pop;
			System.out.println(arr[i].no+" "+arr[i].clock);
		}
		System.out.println("Enter the order in which the processes will enter it's critical section");
		System.out.println("Choose processes from 1 to "+n+". If you want to quit enter 0.");
		while(true)
		{
			System.out.println("Give input : ");
			int ip=sc.nextInt();
			if(ip==0)
				break;
			ap[a++]=ip;
		}
		final ArrayList<Process> p=new ArrayList<Process>(a);
		Thread t1=new Thread(new Runnable()
		{
			public void run()
			{
				int i;
				while(count1<=(a-1))
				{
					synchronized (this)
					{
						for(i=0;i<n;i++)
						{
							if(arr[i].no==ap[count1])
								break;
						}
						p.add(arr[i]);
						Collections.sort(p, new Sortbyclock());
					}
					count1++;
				}
			}
		});
		Thread t=new Thread(new Runnable()
		{
			 int i=0;
			public void run()
			{
				Process newnode;
				try
				{
					/*while(count<=(a-1))
					{
						for(i=0;i<n;i++)
						{
							if(arr[i].no==ap[count])
								break;
						}
						p.add(arr[i]);
						Collections.sort(p, new Sortbyclock());
						
						synchronized (this)//critical section synchronisation
						{
							if(cs==1)
								wait();
							System.out.println("Process "+p.get(0).show()+" is entering its critical section");
							cs=1;
							p.get(0).inclk();
							newnode=p.get(0);
							p.remove(0);
							Thread.sleep(2000);
							System.out.println("Process "+newnode.show()+" is done executing in its critical section");
							cs=0;
						}
						count++;
					}
				catch(InterruptedException e) 
				{ 
					e.printStackTrace(); 
				} 
			}
		});
		
		t1.start();
		t.start();
		t1.join();
		t.join(); 
		sc.close();	
	}
}
class Process{
	int clock,no;
	Process(int n,int clk)
	{
		clock=clk;
		no=n;
	}
	public void inclk()
	{
		clock++;
	}
	public int show()
	{
		return no;
	}
}
class Sortbyclock implements Comparator<Process> 
{ 
    // Used for sorting in ascending order of 
    // clock value
    public int compare(Process a, Process b) 
    { 
        return a.clock - b.clock; 
    } 

}
----------------------------------------------------------------------------------------------------------------------------
ricart - python
----------------------------------------------------------------------------------------------------------------------------


4 of 1,716
Fwd:
Inbox
x

Nabanita Dey <[email protected]>
Attachments
Sat, Jan 4, 5:54 PM (8 hours ago)
to me


---------- Forwarded message ---------
From: DEBOLINA SAHA <[email protected]>
Date: Wed, 1 Jan 2020, 10:48 pm
Subject:
To: nabacsedey1997 <[email protected]>




2 Attachments

p_cnt=0#global variable
csid=0
glob_wt_q=[]
glob_pr_q=[]
class Process:
    
    def __init__(self,id1,time):
        self.id1=id1
        self.time=time
        self.wt_q=[]
        self.rv_q=set()
        global p_cnt
        p_cnt=p_cnt+1

   
    def add_to_cs(self):
        global csid
        csid=self.id1

    def release_cs(self):
        global glob_wt_q
        global csid
        glob_wt_q.pop(0)
        self.rv_q.clear()
        csid=0
        for x in glob_wt_q:
            x.rv_q.add(self.id1)


    #def send_goahead(self,p_list):
    def send_goahead(self):
        global glob_wt_q
        global glob_pr_q
        global csid
        for x in glob_pr_q:
            if x.id1!=self.id1:
                self.rv_q.add(x.id1)
        for x in glob_wt_q:
            if x.id1!=self.id1:
                self.rv_q.remove(x.id1)
       # if len(p_list)==p_cnt-1:
        if len(self.rv_q)==len(glob_pr_q)-1:#p_cnt-1
            #csid=self.id1
            self.add_to_cs()
        else:
            for p in glob_wt_q:
                p.wt_q.append(self.id1)       
        glob_wt_q.append(self)     



def display(msg):
    print(msg)
    print("Global waiting q")
    for p in glob_wt_q:
        print("ID : " + str(p.id1))
        print("Receive q : " )
        print(p.rv_q)
        print("Waiting q : " )
        print(p.wt_q)
        print("-"*20)
    

p_cnt=0
#p1=Process(1,1)
#p2=Process(2,1)
#p3=Process(3,1)
#p4=Process(4,1)
#p5=Process(5,1)
########################
for i in range(1,6):
    p1=Process(i,1)
    glob_pr_q.append(p1)
    #############################
print("Process count ")
print(p_cnt)        
glob_pr_q[0].send_goahead()
glob_pr_q[2].send_goahead()
display("After 1 and 3")
glob_pr_q[0].release_cs()
glob_pr_q[2].send_goahead()
display("After releasing 1 goahead 3")

-----------------------------------------------------------------------------------------------------------------------------
raymond's
-----------------------------------------------------------------------------------------------------------------------------

import java.io.*;
import java.util.*;
class pro {
	Queue<Integer> q=new LinkedList<>();
	int holder;
	pro(){
		holder=0;
	}
}
public class Raymond {
	static Scanner obj = new Scanner(System.in);
	static int no;
	static int privi;
	static int arr[][];
	static pro process[]=new pro[10];
	public static void input(){
		for(int i=0;i<10;i++){
			process[i]=new pro();
		}
		System.out.println("Enter the number of processes : ");
		no =obj.nextInt();
		System.out.println("Enter the node initially holding the priviledge : ");
		privi=obj.nextInt();
		privi=privi-1;
		process[privi].holder=privi; //holder variable having the token priviledge
		for(int i=0;i<no-1;i++){
			System.out.println("Enter a directed vertex pair : ");
			int v1=obj.nextInt();
			int v2=obj.nextInt();
			process[v1-1].holder=v2-1;
		}
	}
	public static void criticalsection(){
		int currnode;
		while(true)
		{
			System.out.print("Enter the process that wants to enter it's critical section : ");
			int pro=obj.nextInt();
			System.out.println("Request flow : ");
			currnode=pro-1;
			process[currnode].q.add(currnode);  //entering the critical section
			System.out.print(currnode+1);
			while(currnode != privi)
			{
				int val=process[currnode].holder;
				process[val].q.add(currnode);
				currnode=val;
				System.out.print(" -> "+(currnode+1));
			}
			while(currnode != pro-1) //comparison for getting the access of critical section access
                                                     {
				int val=process[currnode].q.peek();
				process[currnode].q.poll();
				process[currnode].holder=val;
				currnode=val;
			}
			process[currnode].q.remove();
			process[currnode].holder=currnode;
			privi=currnode;
			System.out.println("");
			System.out.println("Now the priviledge node is "+privi+" and the modified direction of edges are : ");
			for(int i=0;i<no;i++)
			{
				System.out.println((i+1)+" -> "+(process[i].holder +1));
			}
			System.out.println("Do you want to exit? Press 1 if yes else 0");
			int ch=obj.nextInt();
			if (ch==1)
				break;
		}
	}
	public static void main(String[] args){
		input();
		criticalsection();
	}
}

---------------------------------------------------------------------------------------------------------------------------
raymonds - python
---------------------------------------------------------------------------------------------------------------------------
mport time
class Process:
    def __init__(self,name='A',holder=None):
        self.name=name
        self.cs=False
        if holder is  None:
            self.holder=self
        else:
            self.holder=holder
        self.reqQ=[]
        self.asked=False

    def assignToken(self):
        if self.holder!=self and self.cs==False and len(self.reqQ)>0:
            self.holder=self.reqQ.pop(0)
            self.asked=False
        if self.holder==self:
            self.cs=True
        #else:
            #self.sendToken(self.holder)


    def sendRequest(self,neighbor):
        print("sendRequest ",self.name," : ",neighbor.name)
        if self.cs==False and self!=self.holder :
            self.reqQ.append(neighbor)
            self.holder.sendRequest(self)
        elif self==self.holder:
            self.reqQ.append(neighbor)
            self.releaseResource()
        print("sendrequest reqQ : ",self.name," : Len of reqQ ",len(self.reqQ))
        self.holder=self.reqQ.pop(0)

    def releaseResource(self):
        if self.cs==True:
            print(self.name, " in Critical section  Waiting ..")
            time.sleep(2)
            self.cs=False
            
            
        
        
    def makeRequest(self):
        if self!=self.holder and self.cs==False and len(self.reqQ)==0:
            self.reqQ.append(self)
            self.asked=True
            self.holder.sendRequest(self)
            self.assignToken()
        

    def setInfo(self,name,holder,cs):
        self.holder=holder
        self.name=name
        self.holder=holder
        self.cs=cs

    def show(self):
        print("Process : ",self.name,"  Holder : ",self.holder.name)
        print("Critical Section : ",self.cs,"  Asked : ",self.asked)
        print("Request Queue : ",self.reqQ)
    

a=Process('A')
b=Process('B',a)
c=Process('C',b)
d=Process('D',b)
e=Process('E',a)
f=Process('F',e)
g=Process('G',e)

processQ=dict()

processQ['A']=a
processQ['B']=b
processQ['C']=c
processQ['D']=d
processQ['E']=e
processQ['F']=f
processQ['G']=g


root=processQ['A']

for x in processQ:
    processQ[x].show()

processQ['A'].cs=True
processQ['C'].makeRequest()

for x in processQ:
    processQ[x].show()

-------------------------------------------------------------------------------------------------------------------
michell merit
-------------------------------------------------------------------------------------------------------------------

import java.util.ArrayList;

import java.util.Scanner;

public class Mitchell_Merit {
	static ArrayList<Process> plist=new ArrayList<Process>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n,i,j,cnt=0;
		String str;
		boolean flag=true;
		System.out.print("Enter number of Processes :-\n");
		n=sc.nextInt();
		System.out.println("Enter Process name - ");
		for(i=0;i<n;i++) {
			str=sc.next();
			Process p=new Process(str,cnt++);
			plist.add(p);
		}
		do {
			System.out.println("Enter wait-for edge between Processes :-");		// Entering the Wait for edge
			do{
				str=sc.next();
				for(i=0;i<plist.size();i++) {
					if(plist.get(i).name.equalsIgnoreCase(str)) {
						flag=false;
						break;
					}
					else
						flag=true;
				}
				if(flag==true) {
					System.out.println("Enter valid Process name ! ");
				}
			}while(flag);
			do{
				str=sc.next();
				for(j=0;j<plist.size();j++) {
					if(plist.get(j).name.equalsIgnoreCase(str)) {
						flag=false;
						break;
					}
					else
						flag=true;
				}
				if(flag==true) {
					System.out.println("Enter valid Process name ! ");
				}
			}while(flag);
			plist.get(j).waiting_list.add(plist.get(i));
			plist.get(i).block(plist.get(j));
			plist.get(i).detect(plist.get(j));		
		}while(true);
	}
}
//Class for deadlock detection
import java.util.ArrayList;

public class Process {
	String name;
	int id;
	int pub_label,pri_label;
	ArrayList<Process> waiting_list;		// to keep track of all the processes waiting for the process to release resource
	public Process(String name,int id) {
		this.name=name;
		this.id=id;
		this.pub_label=0;
		this.pri_label=0;
		this.waiting_list=new ArrayList<Process>();
	}
	public void block(Process q) {		// to be called when a wait for edge between two processes are created 
		int tmp;			//to record the greater public label between two processes
		if(this.pub_label>=q.pub_label) {
			tmp=this.pub_label;
		}
		else {
			tmp=q.pub_label;
		}
		tmp=tmp+1;
		this.pub_label=tmp;
		this.pri_label=tmp;
		for(Process t:this.waiting_list) {
			t.transit(this);
		}		
	}
	public void transit(Process q) {		// to be called when labels of any process are changed
		if(q.pub_label>this.pub_label) {
			this.pub_label=q.pub_label;
			for(Process t:this.waiting_list) {
				t.transit(this);
			}
		}
	}
	public void detect(Process q) {			//to be called to detect deadlock
		if(this.pub_label==this.pri_label) {
			if(this.pub_label==q.pub_label) {
				System.out.println("\n\t\t\tDeadlock is Detected\n\n");
			}
		}
	}
}

----------------------------------------------------------------------------------------------------------
rama murthy
---------------------------------------------------------------------------------------------------------
import java.util.*;
public class HoRama {
	static int pro=6;
	static int res=4;
	static int wfg[][]=new int[pro+1][pro+1];
	public static void ho()
	{
		 int p1[][]={{1,0,2},{3,1,4},{3,0,3},{1,1,1}};
		 int r1[][]={{2,1,5},{2,0,1},{1,1,1},{1,0,4}};
		// int r1[][]={{2,1,5},{2,0,1},{1,1,1}};   //alternative input
		 int p2[][]={{5,1,2},{4,1,3},{5,0,4},{4,0,1}};
		 //int p2[][]={{5,1,2},{4,1,3},{5,0,4}};    //alternative input
		 int r2[][]={{4,1,3},{3,1,4},{3,0,3},{4,0,5}};
		 int pr[][]=new int[7][5];
		 int rp1,rr1,rp2,rr2;
		 rp1=p1.length;
		 rr1=r1.length;
		 rp2=p2.length;
		 rr2=r2.length;
		 int i,j,pro1;
		 for(i=1;i<=pro;i++)    //process table
		 {
			 for(j=1;j<=res;j++)
			 {
				 pr[i][j]=99;
			 }
		 }
		 for(i=1;i<=pro;i++)
		 {
			 for(j=1;j<=pro;j++)
			 {
				 wfg[i][j]=0;     //entering the wait-for-graph
			 }
		 }
		 for(i=0;i<rr1;i++)
		 {
			 for(j=0;j<rp1;j++)
			 {
				 if(r1[i][0]==p1[j][2] && r1[i][1]==p1[j][1] && r1[i][2]==p1[j][0])
				 {
					 pr[r1[i][2]][r1[i][0]]=r1[i][1];
				 }
			 }
			 for(j=0;j<rp2;j++)
			 {
				 if(r1[i][0]==p2[j][2] && r1[i][1]==p2[j][1] && r1[i][2]==p2[j][0])
				 {
					 pr[r1[i][2]][r1[i][0]]=r1[i][1];
				 }
			 }
		 }
		 for(i=0;i<rr2;i++)
		 {
			 for(j=0;j<rp1;j++)
			 {
				 if(r2[i][0]==p1[j][2] && r2[i][1]==p1[j][1] && r2[i][2]==p1[j][0])
				 {
					 pr[r2[i][2]][r2[i][0]]=r2[i][1];
				 }
			 }
			 for(j=0;j<rp2;j++)
			 {
				 if(r2[i][0]==p2[j][2] && r2[i][1]==p2[j][1] && r2[i][2]==p2[j][0])
				 {
					 pr[r2[i][2]][r2[i][0]]=r2[i][1];
				 }
			 }
		 }
		 for(i=1;i<=res;i++)     //resource table
		 {
			 pro1=-1;
			 for(j=1;j<=pro;j++)
			 {
				 if(pr[j][i]==1)
				 {
					 pro1=j;
					 break;
				 }
			 }
			 if(pro1 != -1)
			 {
				 for(j=1;j<=pro;j++)
				 {
					 if(pr[j][i]==0)
					 {
						 wfg[j][pro1]=1;
						 break;
					 }
				 } 
			 }
		 }
		 System.out.println("The wait-for graph is : ");
		 System.out.print("   ");
		 for(i=1;i<=pro;i++)
		 {
			 System.out.print("P"+i+" ");
		 }
		 System.out.println("");
		 for(i=1;i<=pro;i++)
		 {
			 System.out.print("P"+i+" ");
			 for(j=1;j<=pro;j++)
			 {
				 System.out.print(wfg[i][j]+"  ");
			 }
			 System.out.println("");
		 }
	}
	 static class Graph {
	        int vertices;
	        LinkedList<Integer>[] adjList;

	        Graph(int vertices) {
	            this.vertices = vertices;
	            adjList = new LinkedList[vertices];
	            for (int i = 0; i < vertices; i++) {
	                adjList[i] = new LinkedList<>();
	            }
	        }
	        public void addEgde(int source, int destination) {
	            adjList[source].addFirst(destination);
	        }
	        public boolean isCycle() {
	            boolean visited[] = new boolean[vertices];
	            boolean recursiveArr[] = new boolean[vertices];

	            //do DFS from each node
	            for (int i = 0; i < vertices; i++) {
	                if (isCycleUtil(i, visited, recursiveArr))
	                    return true;
	            }
	            return false;
	        }

	        public boolean isCycleUtil(int vertex, boolean[] visited, boolean[] recursiveArr) {
	            visited[vertex] = true;
	            recursiveArr[vertex] = true;

	            //recursive call to all the adjacent vertices
	            for (int i = 0; i < adjList[vertex].size(); i++) {
	                //if not already visited
	                int adjVertex = adjList[vertex].get(i);
	                if (!visited[adjVertex] && isCycleUtil(adjVertex, visited, recursiveArr)) {
	                    return true;
	                } else if (recursiveArr[adjVertex])
	                    return true;
	            }
	            //if reached here means cycle has not found in DFS from this vertex
	            //reset
	            recursiveArr[vertex] = false;
	            return false;
	        }
	    }
	public static void main(String[] args) {
		int i,j;
		ho();
		int vertices = pro;
        Graph graph = new Graph(vertices);
        for(i=1;i<=pro;i++)
        {
        	for(j=1;j<=pro;j++)
        	{
        		if(wfg[i][j]==1)
        		{
        			graph.addEgde(i, j);
        		}
        	}
        }
        boolean result = graph.isCycle();
        System.out.println("Is Deadlock present? " + result);
	}

}

---------------------------------------------------------------------------------------------------------------------