CMSC 412 H4 Data Files:

  • Using types and free counters
  • Since this problem basically is checking to see which permutations of a set of processes will not deadlock,
    the following page and algorithms should be helpful (Java):

Hints:





// File: data01.txt

// Sample data file for Exercise 7.9
// no paths

types 5 3 5 3
P1 2 2 1 1 1 1 0 0
P2 1 2 1 2 0 1 1 0
P3 1 1 2 1 1 0 1 1
P4 3 1 2 0 2 1 2 0
P5 2 1 1 0 1 0 1 0

Explanation:

  • Think of the data file as representing the current state of the system, and the problem is listing those paths (sequences of processes, Pi's) that are valid - in the sense that there are enough resources to allow the next process to proceed.
  • The first line tells how many total resources are available:
    • types n1 n2 etc. gives the total number of resources of each type
      • Here, 5 of r0, 3 of r1, 5 of r2, 3 of r3
      • Let us call this list of number the total resources list
      • Thinking of r0, r1, r2 and r3 as the different types of resources
    • free n1 n2 etc. would indicate that those are the resources currently free
  • Columns in the main table:
    • The first column is the name of the various process - they should be treated as just strings with no particular meaning in your program
    • The yellows columns (the 2nd, 3rd, 4th and 5th columns here) are the resources of each type that process requires to proceed.
    • The green columns (5, 6, 7 and 8 here) are resources currently held by the corresponding process.
  • Summing up the green columns and subtracting from the total resources list gives us the following current free resources list:
    (5 3 5 3) - (5 3 5 1) = (0 0 0 2)
    • In this case, none of the processes will have sufficient resources to proceed by adding (0 0 0 2)
    • SO - the status of this system is currently DEADLOCKED - there are NO paths possible


// File: data02.txt

Following the thinking in the explanation above, we can analyze the following system thus:

// From Table 7.1:
// path: P3 P1 P2 P4 P5

types 5 6 8 4
P1 3 2 2 2 2 1 1 0
P2 2 1 1 2 0 1 1 0
P3 1 1 3 1 1 1 1 0
P4 3 4 2 2 1 1 2 1
P5 2 4 1 4 1 2 1 1
types 5 6 8 4                       Free        Free resources   
    total      has     deficit    
AFTER Pn     BEFORE Pn
P1 3 2 2 2 - 2 1 1 0 ? 1 1 1 2 (2) (3 2 4 2)    (1 1 3 2) - after P3
P2 2 1 1 2 - 0 1 1 0 ? 2 0 0 2 (3) (3 3 5 2)    (3 2 4 2) - after P1
P3 1 1 3 1 - 1 1 1 0 ? 0 0 2 1 (1) (1 1 3 2)    (0 0 2 2) = (5 6 8 4) - (5 6 6 2)
P4 3 4 2 2 - 1 1 2 1 ? 2 3 0 1 (4) (4 4 7 3)    (3 3 5 2) - after P2
P5 2 4 1 4 - 1 2 1 1 ? 1 2 0 3 (5) (5 6 8 4)    (4 4 7 3) - after P4



// File: data01.txt
// See Exercise 7.9
// no paths

types 5 3 5 3
P1 2 2 1 1 1 1 0 0
P2 1 2 1 2 0 1 1 0
P3 1 1 2 1 1 0 1 1
P4 3 1 2 0 2 1 2 0
P5 2 1 1 0 1 0 1 0
// File: data02.txt
// See Table 7.1:
// 1 path: P3 P1 P2 P4 P5

types 5 6 8 4
P1 3 2 2 2 2 1 1 0
P2 2 1 1 2 0 1 1 0
P3 1 1 3 1 1 1 1 0
P4 3 4 2 2 1 1 2 1
P5 2 4 1 4 1 2 1 1
// File: data03.txt
// 6 Paths

// P5 P3 P2 P4 P1
// P5 P3 P4 P1 P2
// P5 P3 P4 P2 P1
// P5 P4 P2 P3 P1
// P5 P4 P3 P1 P2
// P5 P4 P3 P2 P1

types 9
P1 8 0
P2 7 1
P3 6 2
P4 5 2
P5 4 2
// File: data04.txt
// 48 paths

types 12 8 7 2 6
P1 8 4 6 1 5 0 1 0 0 0
P2 8 4 6 1 5 2 1 0 0 0
P3 8 4 6 1 5 1 0 0 0 0
P4 5 4 6 1 5 2 1 0 0 0
P5 8 4 6 1 5 1 1 0 0 0
// File: data05.txt
// 1 path: P1 P2 P3 P4 P5

// types 21
free 1
P4 15 5
P5 21 6
P1 3 2
P2 6 3
P3 10 4
// File: dataSpringer.txt
// 50 paths

types 8 12 20 15 9
P1 0 3 20 0  1  0 0 1 0 1
P2 1 3 1  5  5  1 3 1 5 4
P3 1 4 1  1  1  1 0 1 1 0
P4 8 4 5  3  1  0 1 0 0 1
P5 0 0 19 1  5  0 0 1 1 1
P6 6 3 2  0  2  1 2 0 0 0
P7 2 4 4  13 8  0 0 0 0 0
// File: dataAndrew.txt
// 48 paths

types 10 4 10 16 32
P1 1 4 1 5 32 0 0 0 0 0
P2 1 1 8 15 1 1 0 0 1 0
P3 2 4 8 16 1 0 0 0 0 0
P4 1 1 1 1 1 1 1 1 1 1
P5 2 2 2 2 2 1 0 0 0 0
P6 1 2 3 4 5 0 2 0 0 1
P7 2 3 7 15 10 0 0 0 2 0
// File: dataLee.txt
// 2400 paths

free 2 2 2 2 2
P1 5 4 3 4 5 1 2 3 4 5
P2 5 3 3 5 5 1 2 3 4 5
P3 5 4 3 4 5 5 4 3 2 1
P4 5 4 5 3 1 5 4 3 2 1
P5 2 2 3 3 3 1 1 1 1 1
P6 3 3 2 2 2 2 2 2 2 2
P7 4 4 4 4 4 3 3 3 3 3
// File: John Sellers
// 112 paths

// Process Max Claim Allocation Need
free 1 2 2 5 6
P1 1 1 1 1  1 1 0 0 0 0
P2 1 0 0 1  1 0 0 0 0 1
P3 3 0 3 0  0 0 0 1 0 0
P4 2 0 0 4  8 0 0 0 4 8
P5 2 3 3 8 10 0 3 0 0 0
P6 1 0 1 1  2 1 0 0 1 0
P7 3 3 0 6 12 0 3 0 0 0



ND.