Thread: Guys, need help RE: deadlock avoidance

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    2

    Guys, need help RE: deadlock avoidance

    hi guys, im trying to write a program that would simulate a process scheduling algorithm and would seek to avoid deadlocks. this is how it should look like:



    shell> program file.dat 5

    where program is my program that i will explain shortly, file.dat is a data file which i will access, and 5 is a number of processes 0-4(example)

    i got the first part of inputting the command line variables, now the problem is i have to detect a deadlock in a system so the file.dat would be something like this:

    332
    010753
    200322
    302902
    211222
    002433

    where 332 is the AVAILABLE resources in the system

    each of the other rows is process 0 - 4, where (010 | 753) 010 is the ALLOCATED resouces and 753 is the MAX resource vector. so only 3 resouces exist A B C, so this is what it looks like:

    ALLOCATED
    A B C
    P0 0 1 0
    P1 2 0 0
    P2 3 0 2
    P3 2 1 1
    P4 0 0 2




    MAX
    A B C
    7 5 3
    3 2 2
    9 0 2
    2 2 2
    4 3 3

    NEED (max-allocated)
    A B C
    7 4 3
    1 2 2
    6 0 0
    0 1 1
    4 3 1

    AVAILABLE

    A B C
    3 3 2

    the output has to determine whether the system is in a safe state i.e. whether it can determine a sequence to run processes without causing a deadlock, so the above snapshot of a system, a safe state would exist when we have a sequence like this:
    P1 -> P3 -> P4 -> P2 -> P0

    P1 goes because its NEED vector is closest and less than the AVAILABLE vector i.e. 3 2 2 < 3 3 2, runs and gives back its allocated resources to the AVAILABLE pool, so the AVAILABLE vector is now 6 5 4
    P3 would be the next process because its needs are the next lowest... and so on.


    so when the program can determine that there is such a sequence, then its in a safe state.



    if anyone has ideas, id really appreciate it, thanx, -mike

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    155
    An algorhythm to start solving the problem could be outlined as such:

    declare variables to be an int for resources available
    a char array to hold file input as a string
    a char array for substring
    an int array for resouses allocated for each process
    an int array for need
    an int array for difference
    an int indicating min difference between need and max
    an index to keep track of where you are in the evalution sequence
    an int array to hold process sequence
    a stream to open and read the file

    open file for reading

    read in initial resource available value

    use a loop to read in rest of file
    within loop read file one line at a time into the string
    use a sub loop to read the first three char of the string into the substring
    null terminate the substring
    use atoi() to convert substring to int and store in allocated
    read last three char of original string into substring
    null terminate substring
    convert substring into int using atoi() and store in need

    once file has been read and the int arrays filled then use a loop to file the third int array representing the difference between the first two array value at any given index and store in the int array called difference

    once the difference array has filled subtract the first difference from the initial resource and store result in min difference value the index is 1.

    use a loop to calculate the difference between the difference and the resource available for each of the remaining values, storing the result in the min value and the index if it is smaller than the previous minimum. Once the loop is done the value of the index containing the minimum difference between resources needed and resources available is stored in the initial index of the process sequence array.

    Remove the initial choice from competition by assigning it the value of zero to its difference so it alwaysis the largest difference.

    Repeat three times to find the entire sequence.

    If at any point in the four evaluation the need exceeds the availble, then there is no sequence which will allow all four processes to continue.

    Otherwise the number sequence stored in the processes array is the order which is most efficient so print out the sequence.

    The above is just a quick, general description of how I would go about solving the problem. I'm sure there are mistakes, inconsistencies, and general stupidity tucked therein. It's your task to refine the process and continue using english or your native language to describe what you are going to do in as much detail as you can, converting to psuedocode when you feel convertable with the verbal description, and code once you have some pseudocode available.

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    2
    thanks for the help

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Deadlock
    By Claudigirl in forum C Programming
    Replies: 2
    Last Post: 11-06-2003, 03:11 PM
  2. Hey guys, I'm new!
    By MrDoomMaster in forum C++ Programming
    Replies: 15
    Last Post: 10-31-2003, 05:47 PM
  3. How long have you guys been working with C/C++??
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 24
    Last Post: 08-01-2003, 03:41 PM
  4. Tic Tac Toe -- Can you guys rate this please?
    By Estauns in forum Game Programming
    Replies: 2
    Last Post: 09-15-2001, 10:22 AM
  5. hello guys
    By lupi in forum C++ Programming
    Replies: 4
    Last Post: 09-13-2001, 06:42 AM