THINK FIRST·CODE LATER

← All labs

The Banker's algorithm: safety and requests

Problem

Implement the Banker's algorithm.

Input: n m; the Available vector; then n rows of Max; then n rows of Allocation; then zero or more lines request i r1 … rm.

  1. Print Need: and one line per process: P0: (7 4 3).
  2. Run the safety algorithm with Work = Available, scanning P0…Pn−1 in passes (in each pass take, in index order, every unfinished process whose Need ≤ Work). For each process taken print P1 can finish, work = (5 3 2) (two leading spaces, Work after adding its allocation). Then State: SAFE, sequence P1 P3 P4 P0 P2 or State: UNSAFE.
  3. For each request (processed in order; a granted request changes the state), print Request P1 (1 0 2): followed by:
    • ERROR, exceeds maximum claim if Req > Need (any component);
    • WAIT, resources not available if Req > Available;
    • GRANTED, safe sequence …, available now (2 3 0) if the pretend-state is safe (no trace lines);
    • DENIED, would be unsafe (P0 waits) otherwise (the state is rolled back).

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os8-1-data-1.txt — first 14 lines of 16

5 3
3 3 2
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
request 1 1 0 2
request 4 3 3 0
What your program must print for os8-1-data-1.txt
Need:
P0: (7 4 3)
P1: (1 2 2)
P2: (6 0 0)
P3: (0 1 1)
P4: (4 3 1)
  P1 can finish, work = (5 3 2)
  P3 can finish, work = (7 4 3)
  P4 can finish, work = (7 4 5)
  P0 can finish, work = (7 5 5)
  P2 can finish, work = (10 5 7)
State: SAFE, sequence P1 P3 P4 P0 P2
Request P1 (1 0 2): GRANTED, safe sequence P1 P3 P4 P0 P2, available now (2 3 0)
Request P4 (3 3 0): WAIT, resources not available
Request P0 (0 2 0): DENIED, would be unsafe (P0 waits)
Request P3 (1 0 0): ERROR, exceeds maximum claim

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os8-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content os8-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.