Thread: Help with simple deadlock detection program

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    2

    Help with simple deadlock detection program

    Hello all,

    I'm trying to write a program that detects deadlock. Some of the code I already tested in an earlier stage but at this point when I run the code it somehow gets stuck. I believe that it has something to do with a negative integer value. Anyhow, the program should still work if a negative integer comes up. Here's my code so far. I think it's fairly clear on what the idea is, but if you have any questions please let me know.

    Code:
    #include <stdio.h>
    
    
    #define FALSE 0
    #define TRUE 1
    
    
    int ALLOC[5][5], REQ[5][5], TOT_RES[5], process, resource, NUMB_RES=5, NUMB_PRO=5;
    int TMP[5]={0}, AVAIL[5], CNTR=0, FIN[5]={FALSE}, FLAG;
    
    
    int main(int argc, char **argv, char **envp) 
    {
        srand(time(NULL));
        
        //Create a randomly generated allocation matrix
        //with a value between 0 and 5 for each resource and process
        
        printf("Allocation matrix:\n");
    
    
        for(process=0;process<5;process++)
        {
            for(resource=0;resource<5;resource++)
            {
                ALLOC[process][resource]=rand()%4;
                printf("\t%d",ALLOC[process][resource]);
            }
            printf("\n");
        }
    
    
        //Create a randomly generated request matrix
        //with a value between 0 and 5 for each resource and process
        
        printf("\nRequest matrix:\n");
    
    
        for(process=0;process<5;process++)
        {
            for(resource=0;resource<5;resource++)
            {
                REQ[process][resource]=rand()%4;
                printf("\t%d",REQ[process][resource]);
            }
            printf("\n");
        }
    
    
        //Create a randomly generated total resource vector
        //with a value between 10 and 15 for each resource and process
        
        printf("\nResources:\n");
    
    
        for(process=0;process<5;process++)
        {
            TOT_RES[process]=rand()%3+NUMB_RES+NUMB_PRO;
            printf("\t%d",TOT_RES[process]);
        }
        
        //display the total number of resources in use
    
    
        //printf("\n\nTotal claimed per resource:\n");
    
    
        for(process=0;process<5;process++)
        {
            for(resource=0;resource<5;resource++)
            {
                TMP[process]+=ALLOC[resource][process];
            }
            //printf("\t%d", TMP[process]);
        }
    
    
        //Display the total number of available resources
        printf("\n\nAvailable:\n");
    
    
        for(process=0;process<5;process++)
        {
            AVAIL[process]=TOT_RES[process]-TMP[process];
            printf("\t%d",AVAIL[process]);
        }
    
    
        while(TRUE)
        {
            for(process=0;process<5;process++)
            {
                CNTR=0;
                if(FIN[process] == FALSE)
                {
                    for(resource=0;resource<5;resource++)
                    {
                        //zijn resources beschikbaar?
                        if(REQ[process][resource]<=AVAIL[resource])
                        {
                            //zo ja, verhoog de counter
                            CNTR++;
                        }
                    }
                    FLAG = FALSE;
                    
                    //vergelijk counter met aantal resources
                    //als counter tot 5 is opgelopen zijn alle resources beschikbaar
                    //en kunnen worden teruggegeven aan de available pool
                    if(CNTR == NUMB_RES)
                    {
                        for(resource=0;resource<5;resource++)
                        {
                            //geef resources terug
                            AVAIL[resource]+=ALLOC[process][resource];
                        }
                        FIN[process]=TRUE;
                        printf("\nProcess number %d is finished\n",process+1);
                    }
                    else
                    FLAG = TRUE;
                }
            }
            CNTR=0;
            for(process=0;process<5;process++)
            {
                if(FIN[process] == TRUE)
                {
                    CNTR++;
                }
            }
            if(CNTR==5)
            {
            break;
            }
        }
    
    
        for(process=0;process<5;process++)
        {
            if(FIN[process] == FALSE)
            {
                printf("\n Deadlock detected. Responsible process number is: %d\n",process+1);
                return;
            }
        }
    }
    The program usually gets stuck after producing output displaying the "Available: " text. After that a list of tabbed numbers should appear, but it doesn't. Any help would be much appreciated.

    Greetings,

    Deheerwassenaar

  2. #2
    Registered User
    Join Date
    Jan 2013
    Posts
    24
    printf("\t");
    printf("%d",AVAIL[process]);

    try it like that to see if it works.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    if its on linux, you might need a line feed or an fflush to get the 5 printfs after Available to show up. linux doesn't flush the printf output until it sees a \n. if your while loop is not terminating then you never do a linefeed.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,658
    Code:
            for(process=0;process<5;process++)
            {
                if(FIN[process] == TRUE)
                {
                    CNTR++;
                }
            }
            if(CNTR==5)
            {
            break;
            }
        }  //!! of while(true)
     
     
        for(process=0;process<5;process++)
        {
            if(FIN[process] == FALSE)
            {
                printf("\n Deadlock detected. Responsible process number is: %d\n",process+1);
                return;
            }
        }
    Examine this carefully.
    All of "FIN[process] == TRUE" have to be true before CNTR reaches the magic number that allows it to break out of the while TRUE loop.
    If the loop does actually exit, then none of "if(FIN[process] == FALSE)" can be true in order to print the expected message.

    The deadlock you seek has already happened, by causing your loop to never exit.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    May 2013
    Posts
    2
    Hi all,

    @jamesedmonds: I tried your solution, but to no avail unfortunately.

    @dmh2000: I tried to use fflush after the for-loop that displays my Available resources, but I didn't solve all my problems.

    @ Salem: I think you are right. After rethinking about my while-loop I figured you were on the right track, so I tried to make changes that could help. The first thing I tried was moving the last for-loop within the while-loop, but that still doesn't fix my problem. The reason for letting this for-loop out of the while-loop was so that the while-loop would try to continue, and not just stop after each process had been checked.

    I now know what the problem is, and I'm also aware of the solution I think, but I don't know how to implement it.

    I think the while loop should end after he checks all processes that aren't finished and nothing changes. Then it should know for sure that new resources will not be available ever. Is someone capable of helping me with this? I tried, but haven't found a solution so far.

    Thanks for all the help so far!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple Collision Detection Using SWIFT Library Problem
    By SterlingM in forum Game Programming
    Replies: 0
    Last Post: 04-12-2013, 02:37 PM
  2. Simple collision detection
    By aprop in forum Game Programming
    Replies: 3
    Last Post: 06-27-2010, 09:31 PM
  3. Simple 2-D Collision Detection
    By Tonto in forum Game Programming
    Replies: 4
    Last Post: 10-14-2006, 06:54 PM
  4. simple collision detection question
    By godhand in forum Game Programming
    Replies: 2
    Last Post: 05-25-2004, 11:27 PM
  5. simple collision detection problems
    By Mr_Jack in forum Game Programming
    Replies: 0
    Last Post: 03-31-2004, 04:59 PM