Banker's algorithm
The Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes a "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
Banker's algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
| This page uses content from Wikipedia. The original article was at Banker's algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
- Example input
Assuming that the system distinguishes between four types of resources, (A, B, C and D), the following is an example of how those resources could be distributed.
Note that this example shows the system at an instant before a new request for resources arrives. Also, the types and number of resources are abstracted. Real systems, for example, would deal with much larger quantities of each resource.
Total resources in system: A B C D 6 5 7 6
Available system resources are: A B C D 3 1 1 2
Processes (currently allocated resources): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 2 1 0
Processes (maximum resources): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
Need= maximum resources - currently allocated resources Processes (need resources): A B C D P1 2 1 0 1 P2 0 2 0 1 P3 0 1 4 0
V resources = Int(input(‘Cantidad de recursos: ’)) V processes = Int(input(‘Cantidad de procesos: ’)) V max_resources = input(‘Recursos máximos: ’).split_py().map(i -> Int(i)) print("\n-- recursos asignados para cada proceso --") V currently_allocated = (0 .< processes).map(j -> input(‘proceso #.: ’.format(j + 1)).split_py().map(i -> Int(i))) print("\n--- recursos máximos para cada proceso ---") V max_need = (0 .< processes).map(j -> input(‘proceso #.: ’.format(j + 1)).split_py().map(i -> Int(i))) V allocated = [0] * resources L(i) 0 .< processes L(j) 0 .< resources allocated[j] += currently_allocated[i][j] print("\nRecursos totales asignados : #.".format(allocated)) V available = (0 .< resources).map(i -> :max_resources[i] - :allocated[i]) print("Recursos totales disponibles: #.\n".format(available)) V running = [1B] * processes V count = processes L count != 0 V safe = 0B L(i) 0 .< processes I running[i] V executing = 1B L(j) 0 .< resources I max_need[i][j] - currently_allocated[i][j] > available[j] executing = 0B L.break I executing print(‘proceso #. ejecutándose’.format(i + 1)) running[i] = 0B count-- safe = 1B L(j) 0 .< resources available[j] += currently_allocated[i][j] L.break I !safe print(‘El proceso está en un estado inseguro.’) L.break print("El proceso está en un estado seguro.\nRecursos disponibles: #.\n".format(available))- Output:
Cantidad de recursos: 4 Cantidad de procesos: 3 Recursos máximos: 6 5 7 6 -- recursos asignados para cada proceso -- proceso 1: 1 2 2 1 proceso 2: 1 0 3 3 proceso 3: 1 2 1 0 --- recursos máximos para cada proceso --- proceso 1: 3 3 2 2 proceso 2: 1 2 3 4 proceso 3: 1 3 5 0 Recursos totales asignados : [3, 4, 6, 4] Recursos totales disponibles: [3, 1, 1, 2] proceso 1 ejecutándose El proceso está en un estado seguro. Recursos disponibles: [4, 3, 3, 3] proceso 2 ejecutándose El proceso está en un estado seguro. Recursos disponibles: [5, 3, 6, 6] proceso 3 ejecutándose El proceso está en un estado seguro. Recursos disponibles: [6, 5, 7, 6]
en Ingles
V resources = Int(input('Number of resources: ')) V processes = Int(input('Number of processes: ')) V max_resources = input('Maximum resources: ').split_py().map(i -> Int(i)) print("\n-- resources allocated for each process --") V currently_allocated = (0 .< processes).map(j -> input('process #.: '.format(j + 1)).split_py().map(i -> Int(i))) print("\n--- maximum resources for each process ---") V max_need = (0 .< processes).map(j -> input('process #.: '.format(j + 1)).split_py().map(i -> Int(i))) V allocated = [0] * resources L(i) 0 .< processes L(j) 0 .< resources allocated[j] += currently_allocated[i][j] print("\nTotal allocated resources: #.".format(allocated)) V available = (0 .< resources).map(i -> :max_resources[i] - :allocated[i]) print("Total available resources: #.\n".format(available)) V running = [1B] * processes V count = processes L count != 0 V safe = 0B L(i) 0 .< processes I running[i] V executing = 1B L(j) 0 .< resources I max_need[i][j] - currently_allocated[i][j] > available[j] executing = 0B L.break I executing print('process #. executing'.format(i + 1)) running[i] = 0B count-- safe = 1B L(j) 0 .< resources available[j] += currently_allocated[i][j] L.break I !safe print('The process is in an unsafe state.') L.break print("The process is in a safe state.\nAvailable resources: #.\n".format(available))Standard binary heap-as-priority queue affair. Only that each node links back to its heap position for easier update.
There are two main() functions to choose from (look for #define BIG_EXAMPLE), one is for task example, the other is a much heavier duty test case.
#include <stdio.h> #include <stdbool.h> int main() { int curr[5][5]; int max_claim[5][5]; int avl[5]; int alloc[5] = {0, 0, 0, 0, 0}; int max_res[5]; int running[5]; int i, j, exec, r, p; int count = 0; bool safe = false; printf("\nEnter the number of resources: "); scanf("%d", &r); printf("\nEnter the number of processes: "); scanf("%d", &p); for (i = 0; i < p; i++) { running[i] = 1; count++; } printf("\nEnter Claim Vector: "); for (i = 0; i < r; i++) scanf("%d", &max_res[i]); printf("\nEnter Allocated Resource Table: "); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) scanf("%d", &curr[i][j]); } printf("\nEnter Maximum Claim table: "); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) scanf("%d", &max_claim[i][j]); } printf("\nThe Claim Vector is: "); for (i = 0; i < r; i++) printf("%d ", max_res[i]); printf("\nThe Allocated Resource Table:\n"); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) printf("\t%d", curr[i][j]); printf("\n"); } printf("\nThe Maximum Claim Table:\n"); for (i = 0; i < p; i++) { for (j = 0; j < r; j++) printf("\t%d", max_claim[i][j]); printf("\n"); } for (i = 0; i < p; i++) for (j = 0; j < r; j++) alloc[j] += curr[i][j]; printf("\nAllocated resources: "); for (i = 0; i < r; i++) printf("%d ", alloc[i]); for (i = 0; i < r; i++) avl[i] = max_res[i] - alloc[i]; printf("\nAvailable resources: "); for (i = 0; i < r; i++) printf("%d ", avl[i]); printf("\n"); while (count != 0) { safe = false; for (i = 0; i < p; i++) { if (running[i]) { exec = 1; for (j = 0; j < r; j++) { if (max_claim[i][j] - curr[i][j] > avl[j]) { exec = 0; break; } } if (exec) { printf("\nProcess%d is executing.\n", i + 1); running[i] = 0; count--; safe = true; for (j = 0; j < r; j++) avl[j] += curr[i][j]; break; } } } if (!safe) { printf("\nThe processes are in unsafe state."); break; } if (safe) printf("\nThe process is in safe state."); printf("\nAvailable vector: "); for (i = 0; i < r; i++) printf("%d ", avl[i]); } return 0; } - Input and Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 Enter Maximum Claim table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 The Claim Vector is: 8 5 9 7 The Allocated Resource Table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 The Maximum Claim Table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 Allocated resources: 7 3 7 5 Available resources: 1 2 2 2 Process3 is executing. The process is in safe state. Available vector: 5 2 2 5 Process1 is executing. The process is in safe state. Available vector: 7 2 3 6 Process2 is executing. The process is in safe state. Available vector: 7 3 5 7 Process4 is executing. The process is in safe state. Available vector: 7 5 6 7 Process5 is executing. The process is in safe state. Available vector: 8 5 9 7
using System; using System.Linq; class BankerAlgorithm { static void Main() { try { // 1. Read Input Sizes Console.Write("Number of resources: "); int resources = int.Parse(Console.ReadLine()); Console.Write("Number of processes: "); int processes = int.Parse(Console.ReadLine()); // 2. Read Maximum Resources Console.Write("Maximum resources (space-separated): "); int[] maxResources = Console.ReadLine() .Trim() .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries) .Select(int.Parse) .ToArray(); // 3. Read Currently Allocated Resources for each process int[][] currentlyAllocated = new int[processes][]; Console.WriteLine("\n-- resources allocated for each process --"); for (int i = 0; i < processes; i++) { Console.Write($"process {i + 1}: "); currentlyAllocated[i] = Console.ReadLine() .Trim() .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries) .Select(int.Parse) .ToArray(); } // 4. Read Maximum Need for each process int[][] maxNeed = new int[processes][]; Console.WriteLine("\n--- maximum resources for each process ---"); for (int i = 0; i < processes; i++) { Console.Write($"process {i + 1}: "); maxNeed[i] = Console.ReadLine() .Trim() .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries) .Select(int.Parse) .ToArray(); } // 5. Calculate Total Allocated Resources int[] allocated = new int[resources]; for (int i = 0; i < processes; i++) { for (int j = 0; j < resources; j++) { allocated[j] += currentlyAllocated[i][j]; } } Console.WriteLine($"\nTotal resources allocated: [{string.Join(", ", allocated)}]"); // 6. Calculate Available Resources int[] available = new int[resources]; for (int i = 0; i < resources; i++) { available[i] = maxResources[i] - allocated[i]; if (available[i] < 0) { Console.Error.WriteLine($"Error: Calculated available resources are negative for resource {i}. Check input consistency."); return; } } Console.WriteLine($"Total resources available: [{string.Join(", ", available)}]\n"); // 7. Banker's Algorithm (Safety Check) bool[] running = new bool[processes]; // Replace Array.Fill with manual initialization for (int i = 0; i < processes; i++) { running[i] = true; } int count = processes; while (count > 0) { bool safe = false; for (int i = 0; i < processes; i++) { if (running[i]) { bool canExecute = true; for (int j = 0; j < resources; j++) { int needed = maxNeed[i][j] - currentlyAllocated[i][j]; if (needed > available[j]) { canExecute = false; break; } } if (canExecute) { Console.WriteLine($"process {i + 1} running"); running[i] = false; count--; safe = true; for (int j = 0; j < resources; j++) { available[j] += currentlyAllocated[i][j]; } break; } } } if (!safe) { Console.WriteLine("The process is in an unsafe state."); break; } else { Console.WriteLine("The process is in a safe state."); Console.WriteLine($"Available resources: [{string.Join(", ", available)}]\n"); } } if (count == 0) { Console.WriteLine("\nAll processes finished successfully. The initial state was safe."); } } catch (FormatException) { Console.Error.WriteLine("Error: Invalid number format entered. Please enter integers only."); } catch (IndexOutOfRangeException) { Console.Error.WriteLine("Error: Incorrect number of values entered on a line."); } catch (Exception e) { Console.Error.WriteLine($"An unexpected error occurred: {e.Message}"); } } } - Output:
Number of resources: 4 Number of processes: 3 Maximum resources (space-separated): 6 5 7 6 -- resources allocated for each process -- process 1: 1 2 2 1 process 2: 1 0 3 3 process 3: 1 2 1 0 --- maximum resources for each process --- process 1: 3 3 2 2 process 2: 1 2 3 4 process 3: 1 3 5 0 Total resources allocated: [3, 4, 6, 4] Total resources available: [3, 1, 1, 2] process 1 running The process is in a safe state. Available resources: [4, 3, 3, 3] process 2 running The process is in a safe state. Available resources: [5, 3, 6, 6] process 3 running The process is in a safe state. Available resources: [6, 5, 7, 6] All processes finished successfully. The initial state was safe.
#include <cstdint> #include <iostream> #include <sstream> #include <string> #include <vector> template <typename T> void print_vector(const std::vector<T>& list) { std::cout << "["; for ( uint32_t i = 0; i < list.size() - 1; ++i ) { std::cout << list[i] << ", "; } std::cout << list.back() << "]" << std::endl; } std::vector<uint32_t> split_string(const std::string& text, const char& delimiter) { std::vector<uint32_t> numbers; std::istringstream stream(text); std::string word; while ( std::getline(stream, word, delimiter) ) { numbers.emplace_back(std::stoi(word)); } return numbers; } int main () { // Step 1: Obtain user input std::string user_entry; uint32_t resource_count; std::cout << "Enter the number of resources: "; std::getline(std::cin, user_entry); std::stringstream(user_entry) >> resource_count; uint32_t process_count; std:: cout << "\n" << "Enter the number of processes: "; std::getline(std::cin, user_entry); std::stringstream(user_entry) >> process_count; std::cout << "\n" << "Enter the Claim Vector as a string of space separated integer: "; std::getline(std::cin, user_entry); std::vector<uint32_t> claims = split_string(user_entry, ' '); std::vector<std::vector<uint32_t>> allocated_resource_table; std::cout << "\n" << "Enter the rows of the Allocated Resource Table" << " as a string of space separated integers:" << std::endl; for ( uint32_t row = 1; row <= process_count; ++row ) { std::cout << "Row " << row << ": "; std::getline(std::cin, user_entry); allocated_resource_table.emplace_back(split_string(user_entry, ' ')); } std::vector<std::vector<uint32_t>> maximum_claim_table; std::cout << "\n" << "Enter the rows of the Maximum Claim Table" << " as a string of space separated integers:" << std::endl; for ( uint32_t row = 1; row <= process_count; ++row ) { std::cout << "Row " << row << ": "; std::getline(std::cin, user_entry); maximum_claim_table.emplace_back(split_string(user_entry, ' ')); } // Step 2: Initial calculations std::vector<uint32_t> allocated_resources(resource_count, 0); for ( uint32_t i = 0; i < process_count; ++i ) { for ( uint32_t j = 0; j < resource_count; ++j ) { allocated_resources[j] += allocated_resource_table[i][j]; } } std::cout << "\n" << "Allocated resources: "; print_vector(allocated_resources); std::vector<uint32_t> available_resources; for ( uint32_t i = 0; i < resource_count; ++i ) { available_resources.emplace_back(claims[i] - allocated_resources[i]); } std::cout << "\n" << "Available resources: "; print_vector(available_resources); // Step 3: Banker's Algorithm std::vector<bool> running(process_count, true); uint32_t running_count = process_count; while ( running_count > 0 ) { bool safe_state = false; for ( uint32_t i = 0; i < process_count; ++i ) { if ( running[i] ) { bool process_execution = true; for ( uint32_t j = 0; j < resource_count; ++j ) { if ( maximum_claim_table[i][j] - allocated_resource_table[i][j] > available_resources[j] ) { process_execution = false; break; } } if ( process_execution ) { std::cout << "\n" << "Process " << i + 1 << " is executing." << std::endl; running[i] = false; running_count--; safe_state = true; for ( uint32_t j = 0; j < resource_count; ++j ) { available_resources[j] += allocated_resource_table[i][j]; } break; } } } if ( ! safe_state ) { std::cout << "\n" << "The processes are in an unsafe state." << std::endl; break; } std::cout << "\n" << "The process is in a safe state." << std::endl; std::cout << "\n" << "Available resources: "; print_vector(available_resources); } } - Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter the Claim Vector as a string of space separated integer: 8 5 7 9 Enter the rows of the Allocated Resource Table as a string of space separated integers: Row 1: 2 0 1 1 Row 2: 0 1 2 1 Row 3: 4 0 0 3 Row 4: 0 2 1 0 Row 5: 1 0 3 0 Enter the rows of the Maximum Claim Table as a string of space separated integers: Row 1: 3 2 1 4 Row 2: 0 2 5 2 Row 3: 5 1 0 5 Row 4: 1 5 3 0 Row 5: 3 0 3 3 Allocated resources: [7, 3, 7, 5] Available resources: [1, 2, 0, 4] Process 1 is executing. The process is in a safe state. Available resources: [3, 2, 1, 5] Process 3 is executing. The process is in a safe state. Available resources: [7, 2, 1, 8] Process 5 is executing. The process is in a safe state. Available resources: [8, 2, 4, 8] Process 2 is executing. The process is in a safe state. Available resources: [8, 3, 6, 9] Process 4 is executing. The process is in a safe state. Available resources: [8, 5, 7, 9]
Dim As Integer i, j, r, p Input "Enter the amount of resources: ", r Input "Enter the number of processes: ", p Print !"\nEnter the maximum resources: "; Dim As Integer maxRes(r) For i = 1 To r Input ; " ", maxRes(i) Next i Print !"\n\n-- resources allocated for each process --" Dim As Integer curr(p, r) For i = 1 To p Print "process"; i; ":"; For j = 1 To r Input ; " ", curr(i, j) Next j Print Next i Print !"\n\n--- maximum resources for each process ---" Dim As Integer maxReclam(p, r) For i = 1 To p Print "process"; i; ":"; For j = 1 To r Input ; " ", maxReclam(i, j) Next j Print Next i Dim As Integer recAsigad(r) For i = 1 To p For j = 1 To r recAsigad(j) += curr(i, j) Next j Next i For i = 1 To r Print recAsigad(i); " "; Next i Dim As Integer recDispon(r) Print !"\n\nTotal available resources: "; 'Available Resources For i = 1 To r recDispon(i) = maxRes(i) - recAsigad(i) Print recDispon(i); " "; Next i Dim As Boolean executing(p) For i = 1 To p executing(i) = True Next i Dim As Integer count = p Do While count <> 0 Dim As Boolean safe = False For i = 1 To p If executing(i) Then Dim As Boolean executes = True For j = 1 To r If (maxReclam(i,j) - curr(i,j) > recDispon(j)) Then executes = False Exit For End If Next j If executes Then Color 11 : Print !"\n\nprocess"; i; !" running." executing(i) = False count -= 1 safe = True For j = 0 To r recDispon(j) += curr(i,j) Next j Exit For End If End If Next i If Not safe Then Color 12 : Print !"\nThe processes are in an unsafe state." Color 7 Exit Do End If Color 10: Print "The process is in a safe state." Color 7: Print "Available resources: "; For i = 1 To r Print recDispon(i); " "; Next i Loop Sleep WP cites EWD-108 and has EWD-623 as further reading. In using the analogy of a money, EWD-108 considers only a single type of resource. EWD-623 seems mostly in terms of a single resource but a couple of times says "all resources." This subtly hints that the algorithm can be adapted for multiple resource types. WP then gives an array-based presentation that works for multiple resources.
This solution is more inspired by EWD-623 than WP. EWD-623, while it talks of finding a permutation of processes, notes that the "ordering effort" can be stopped as soon as the process requesting resources happens to be found satisfiable. The solution here attempts to make this finding as soon as possible by moving the process to the front of a list of unsatisfied processes. Also since the solved permutation of satisfied processes has no use, it is not kept which simplifies the algorithm a bit.
package bank import ( "bytes" "errors" "fmt" "log" "sort" "sync" ) type PID string type RID string type RMap map[RID]int // format RIDs in order func (m RMap) String() string { rs := make([]string, len(m)) i := 0 for r := range m { rs[i] = string(r) i++ } sort.Strings(rs) var b bytes.Buffer b.WriteString("{") for _, r := range rs { fmt.Fprintf(&b, "%q: %d, ", r, m[RID(r)]) } bb := b.Bytes() if len(bb) > 1 { bb[len(bb)-2] = '}' } return string(bb) } type Bank struct { available RMap max map[PID]RMap allocation map[PID]RMap sync.Mutex } func (b *Bank) need(p PID, r RID) int { return b.max[p][r] - b.allocation[p][r] } func New(available RMap) (b *Bank, err error) { for r, a := range available { if a < 0 { return nil, fmt.Errorf("negative resource %s: %d", r, a) } } return &Bank{ available: available, max: map[PID]RMap{}, allocation: map[PID]RMap{}, }, nil } func (b *Bank) NewProcess(p PID, max RMap) (err error) { b.Lock() defer b.Unlock() if _, ok := b.max[p]; ok { return fmt.Errorf("process %s already registered", p) } for r, m := range max { switch a, ok := b.available[r]; { case !ok: return fmt.Errorf("resource %s unknown", r) case m > a: return fmt.Errorf("resource %s: process %s max %d > available %d", r, p, m, a) } } b.max[p] = max b.allocation[p] = RMap{} return } func (b *Bank) Request(pid PID, change RMap) (err error) { b.Lock() defer b.Unlock() if _, ok := b.max[pid]; !ok { return fmt.Errorf("process %s unknown", pid) } for r, c := range change { if c < 0 { return errors.New("decrease not allowed") } if _, ok := b.available[r]; !ok { return fmt.Errorf("resource %s unknown", r) } if c > b.need(pid, r) { return errors.New("increase exceeds declared max") } } // allocation is non-exported data so we can change it in place // then change it back if the request cannot be granted. for r, c := range change { b.allocation[pid][r] += c // change in place } defer func() { if err != nil { // if request not granted, for r, c := range change { b.allocation[pid][r] -= c // change it back } } }() // Collect list of process IDs, also compute cash // First in the list is always the requesting PID. cash := RMap{} for r, a := range b.available { cash[r] = a } perm := make([]PID, len(b.allocation)) i := 1 for pr, a := range b.allocation { if pr == pid { perm[0] = pr } else { perm[i] = pr i++ } for r, a := range a { cash[r] -= a } } ret := RMap{} // sum of loans m := len(perm) // number of processes still candidates for termination for { // find a process h that can terminate h := 0 h: for ; ; h++ { if h == m { // no process could terminate return errors.New("request would make deadlock possible") } for r := range b.available { if b.need(perm[h], r) > cash[r]+ret[r] { // h cannot terminate if any resource need cannot be met. continue h } } // log possible terimation, consistent with WP example program. log.Println(" ", perm[h], "could terminate") // all resource needs can be met. h can terminate. break } if h == 0 { // Zwanenburg condition: // if requesting process can terminate, pattern is safe and // remaining terminations do not need to be demonstrated. return nil } for r, a := range b.allocation[perm[h]] { ret[r] += a } m-- perm[h] = perm[m] } } package main import ( "fmt" "bank" ) func main() { // Task example data: // create "bank" with available resources b, _ := bank.New(bank.RMap{"A": 6, "B": 5, "C": 7, "D": 6}) // add processes with their maximum allocation limits b.NewProcess("P1", bank.RMap{"A": 3, "B": 3, "C": 2, "D": 2}) b.NewProcess("P2", bank.RMap{"A": 1, "B": 2, "C": 3, "D": 4}) b.NewProcess("P3", bank.RMap{"A": 1, "B": 3, "C": 5}) // processes request resources. Each request is checked for safety. // <nil> returned error value means request was safe and was granted. fmt.Println("P1 request:") fmt.Println(b.Request("P1", bank.RMap{"A": 1, "B": 2, "C": 2, "D": 1})) fmt.Println("\nP2 request:") fmt.Println(b.Request("P2", bank.RMap{"A": 1, "C": 3, "D": 3})) fmt.Println("\nP3 request:") fmt.Println(b.Request("P3", bank.RMap{"A": 1, "B": 2, "C": 1})) } - Output:
P1 request: 2017/08/29 16:44:15 P1 could terminate <nil> P2 request: 2017/08/29 16:44:15 P2 could terminate <nil> P3 request: 2017/08/29 16:44:15 P1 could terminate 2017/08/29 16:44:15 P2 could terminate 2017/08/29 16:44:15 P3 could terminate <nil>
The task description currently does not define the process being run. So we follow the example set by other implementations and have each process free all resources after successfully being run. Also, since this is a demo, we give a blow-by-blow description of what's happening as it runs.
bankrun=:1 :0 'MAX ALLOC TOTAL'=. y todo=.(#ALLOC)#1 whilst. (+./todo)*-. prior-:todo do. prior=. todo for_p.I.todo do. avail=. TOTAL-+/ALLOC echo 'currently available: ',":avail pALLOC=. p{ALLOC pMAX=. p{MAX request=. pMAX-pALLOC if.(0>request)+.&(+./)request>avail do. echo 'unsafe request ',(":request),', skipping ',":p continue. else. echo 'running process ',(":p),', allocating ',":request end. free=.request u pALLOC echo 'process ',(":p),' freeing ',":free assert (0<:free) *&(*/) free <: pMAX ALLOC=. (pALLOC-free) p} ALLOC todo=. 0 p} todo end. end. if.+./todo do. echo 'deadlocked processes: ',":I.todo end. echo 'DONE' ) Definitions for task example:
max=: 3 3 2 2,1 2 3 4,:1 3 5 0 alloc=: 1 2 2 1,1 0 3 3,:1 2 1 0 total=:6 5 7 6 NB. simulate running process NB. left arg: newly available resources, right: previously available NB. result: resources freed run=: + Example run:
run bankrun max;alloc;total currently available: 3 1 1 2 running process 0, allocating 2 1 0 1 process 0 freeing 3 3 2 2 currently available: 6 4 3 4 running process 1, allocating 0 2 0 1 process 1 freeing 1 2 3 4 currently available: 7 6 6 8 running process 2, allocating 0 1 4 0 process 2 freeing 1 3 5 0 DONE import java.util.Scanner; import java.util.Arrays; // For printing arrays easily class BankerAlgorithm { public static void main(String[] args) { // Use try-with-resources to ensure the scanner is closed automatically try (Scanner scanner = new Scanner(System.in)) { // 1. Read Input Sizes System.out.print("Number of resources: "); int resources = scanner.nextInt(); System.out.print("Number of processes: "); int processes = scanner.nextInt(); scanner.nextLine(); // Consume the newline left-over from nextInt() // 2. Read Maximum Resources System.out.print("Maximum resources (space-separated): "); int[] maxResources = new int[resources]; String[] maxResParts = scanner.nextLine().trim().split("\\s+"); for (int i = 0; i < resources; i++) { maxResources[i] = Integer.parseInt(maxResParts[i]); } // 3. Read Currently Allocated Resources for each process int[][] currentlyAllocated = new int[processes][resources]; System.out.println("\n-- resources allocated for each process --"); for (int i = 0; i < processes; i++) { System.out.print("process " + (i + 1) + ": "); String[] allocatedParts = scanner.nextLine().trim().split("\\s+"); for (int j = 0; j < resources; j++) { currentlyAllocated[i][j] = Integer.parseInt(allocatedParts[j]); } } // 4. Read Maximum Need for each process int[][] maxNeed = new int[processes][resources]; System.out.println("\n--- maximum resources for each process ---"); for (int i = 0; i < processes; i++) { System.out.print("process " + (i + 1) + ": "); String[] maxNeedParts = scanner.nextLine().trim().split("\\s+"); for (int j = 0; j < resources; j++) { maxNeed[i][j] = Integer.parseInt(maxNeedParts[j]); } } // 5. Calculate Total Allocated Resources int[] allocated = new int[resources]; // Initialized to 0 by default for (int i = 0; i < processes; i++) { for (int j = 0; j < resources; j++) { allocated[j] += currentlyAllocated[i][j]; } } System.out.println("\nTotal resources allocated: " + Arrays.toString(allocated)); // 6. Calculate Available Resources int[] available = new int[resources]; for (int i = 0; i < resources; i++) { available[i] = maxResources[i] - allocated[i]; // Optional check for negative available resources (indicates input error) if (available[i] < 0) { System.err.println("Error: Calculated available resources are negative for resource " + i + ". Check input consistency."); return; // Exit if input is inconsistent } } System.out.println("Total resources available: " + Arrays.toString(available) + "\n"); // 7. Banker's Algorithm (Safety Check) boolean[] running = new boolean[processes]; Arrays.fill(running, true); // Initially, all processes are running (haven't finished) int count = processes; // Number of processes still needing to run while (count > 0) { // While there are still processes that haven't finished boolean safe = false; // Flag to check if we found at least one process to run in this pass for (int i = 0; i < processes; i++) { if (running[i]) { // Check only processes that are still marked as running boolean canExecute = true; // Check if the process's *remaining need* can be satisfied by *available* resources for (int j = 0; j < resources; j++) { int needed = maxNeed[i][j] - currentlyAllocated[i][j]; if (needed > available[j]) { canExecute = false; // Cannot execute, not enough resources break; // No need to check further resources for this process } } if (canExecute) { // Process can execute! System.out.println("process " + (i + 1) + " running"); running[i] = false; // Mark process as finished count--; // Decrement count of running processes safe = true; // Found a safe process in this pass // Release the resources allocated to this process for (int j = 0; j < resources; j++) { available[j] += currentlyAllocated[i][j]; } // Optional: Print intermediate state (as in Python code) // Note: The Python code prints this *after* the process loop if safe was true. // Moved the print statement outside this inner 'if' but inside the 'while'. break; // Found a process, restart the check from the beginning // (or from the next process, depending on Banker's variant, // but breaking and restarting the outer loop is common and matches Python logic) } } } // End of loop through processes if (!safe) { // If we went through all running processes and couldn't find one to execute System.out.println("The process is in an unsafe state."); break; // Exit the while loop, deadlock detected or unsafe state } else { // If we *did* find a safe process (safe == true), print the state and continue the while loop System.out.println("The process is in a safe state."); // As per Python code structure System.out.println("Available resources: " + Arrays.toString(available) + "\n"); } } // End of while loop // Final check after the loop finishes if (count == 0) { // If count is 0, all processes finished successfully System.out.println("\nAll processes finished successfully. The initial state was safe."); } } catch (NumberFormatException e) { System.err.println("Error: Invalid number format entered. Please enter integers only."); e.printStackTrace(); } catch (ArrayIndexOutOfBoundsException e) { System.err.println("Error: Incorrect number of values entered on a line."); e.printStackTrace(); } catch (Exception e) { // Catch any other potential exceptions during input or processing System.err.println("An unexpected error occurred: " + e.getMessage()); e.printStackTrace(); } } } - Output:
Number of resources: 4 Number of processes: 3 Maximum resources (space-separated): 6 5 7 6 -- resources allocated for each process -- process 1: 1 2 2 1 process 2: 1 0 3 3 process 3: 1 2 1 0 --- maximum resources for each process --- process 1: 3 3 2 2 process 2: 1 2 3 4 process 3: 1 3 5 0 Total resources allocated: [3, 4, 6, 4] Total resources available: [3, 1, 1, 2] process 1 running The process is in a safe state. Available resources: [4, 3, 3, 3] process 2 running The process is in a safe state. Available resources: [5, 3, 6, 6] process 3 running The process is in a safe state. Available resources: [6, 5, 7, 6] All processes finished successfully. The initial state was safe.
const readline = require('readline').createInterface({ input: process.stdin, output: process.stdout, }); function askQuestion(query) { return new Promise(resolve => { readline.question(query, answer => { resolve(answer); }); }); } async function main() { const resources = parseInt(await askQuestion("Number of resources: ")); const processes = parseInt(await askQuestion("Number of processes: ")); const maxResources = (await askQuestion("Maximum resources: ")).split(" ").map(Number); console.log("\n-- resources allocated for each process --"); const currentlyAllocated = []; for (let j = 0; j < processes; j++) { const processResources = (await askQuestion(`process ${j + 1}: `)).split(" ").map(Number); currentlyAllocated.push(processResources); } console.log("\n--- maximum resources for each process ---"); const maxNeed = []; for (let j = 0; j < processes; j++) { const processMaxNeed = (await askQuestion(`process ${j + 1}: `)).split(" ").map(Number); maxNeed.push(processMaxNeed); } let allocated = new Array(resources).fill(0); for (let i = 0; i < processes; i++) { for (let j = 0; j < resources; j++) { allocated[j] += currentlyAllocated[i][j]; } } console.log(`\nTotal resources allocated: ${allocated}`); const available = maxResources.map((resource, i) => resource - allocated[i]); console.log(`Total resources available: ${available}\n`); let running = new Array(processes).fill(true); let count = processes; while (count !== 0) { let safe = false; for (let i = 0; i < processes; i++) { if (running[i]) { let executing = true; for (let j = 0; j < resources; j++) { if (maxNeed[i][j] - currentlyAllocated[i][j] > available[j]) { executing = false; break; } } if (executing) { console.log(`process ${i + 1} running`); running[i] = false; count -= 1; safe = true; for (let j = 0; j < resources; j++) { available[j] += currentlyAllocated[i][j]; } break; } } } if (!safe) { console.log("The process is in an unsafe state."); break; } console.log(`The process is in a safe state.\nAvailable resources: ${available}\n\n`); } readline.close(); } main(); - Output:
interacitve input and output
Number of resources: 4 Number of processes: 3 Maximum resources: 6 5 7 6 -- resources allocated for each process -- process 1: 1 2 2 1 process 2: 1 0 3 3 process 3: 1 2 1 0 --- maximum resources for each process --- process 1: 3 3 2 2 process 2: 1 2 3 4 process 3: 1 3 5 0 Total resources allocated: 3,4,6,4 Total resources available: 3,1,1,2 process 1 running The process is in a safe state. Available resources: 4,3,3,3 process 2 running The process is in a safe state. Available resources: 5,3,6,6 process 3 running The process is in a safe state. Available resources: 6,5,7,6
function queryprompt(query, typ) print(query, ": ") entry = uppercase(strip(readline(stdin))) return (typ <: Integer) ? parse(Int, entry) : (typ <: Vector) ? map(x -> parse(Int, x), split(entry, r"\s+")) : entry end function testbankers() r = queryprompt("Enter the number of resources", Int) p = queryprompt("\nEnter the number of processes", Int) maxres = queryprompt("\nEnter Claim Vector", Vector{Int}) curr, maxclaim = zeros(Int, p, r), zeros(Int, p, r) for i in 1:p curr[i, :] .= queryprompt("\nEnter Allocated Resource Table, Row $i", Vector{Int}) end for i in 1:p maxclaim[i, :] .= queryprompt("\nEnter Maximum Claim Table, Row $i", Vector{Int}) end alloc = [sum(curr[:, j]) for j in 1:r] println("\nAllocated Resources: $alloc") avl = map(i -> maxres[i] - alloc[i], 1:r) println("\nAvailable Resources: $avl") running = trues(p) count = p while count != 0 safe = false for i in 1:p if running[i] exec = true for j in 1:r if maxclaim[i, j] - curr[i, j] > avl[j] exec = false break end end if exec println("\nProcess $i is executing.") running[i] = false count -= 1 safe = true for j in 1:r avl[j] += curr[i, j] end break end end end if !safe println("The processes are in an unsafe state.") break end println("\nThe process is in a safe state.") println("\nAvailable Vector: $avl") end end testbankers() - Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table, Row 1: 2 0 1 1 Enter Allocated Resource Table, Row 2: 0 1 2 1 Enter Allocated Resource Table, Row 3: 4 0 0 3 Enter Allocated Resource Table, Row 4: 0 2 1 0 Enter Allocated Resource Table, Row 5: 1 0 3 0 Enter Maximum Claim Table, Row 1: 3 2 1 4 Enter Maximum Claim Table, Row 2: 0 2 5 2 Enter Maximum Claim Table, Row 3: 5 1 0 5 Enter Maximum Claim Table, Row 4: 1 5 3 0 Enter Maximum Claim Table, Row 5: 3 0 3 3 Allocated Resources: [7, 3, 7, 5] Available Resources: [1, 2, 2, 2] Process 3 is executing. The process is in a safe state. Available Vector: [5, 2, 2, 5] Process 1 is executing. The process is in a safe state. Available Vector: [7, 2, 3, 6] Process 2 is executing. The process is in a safe state. Available Vector: [7, 3, 5, 7] Process 4 is executing. The process is in a safe state. Available Vector: [7, 5, 6, 7] Process 5 is executing. The process is in a safe state. Available Vector: [8, 5, 9, 7]
For simplicity, input checking is ignored:
// version 1.1.4-3 fun main(args: Array<String>) { print("Enter the number of resources: ") val r = readLine()!!.toInt() print("\nEnter the number of processes: ") val p = readLine()!!.toInt() print("\nEnter Claim Vector: ") val maxRes = readLine()!!.split(' ').map { it.toInt() } .toIntArray() println("\nEnter Allocated Resource Table:") val curr = Array(p) { IntArray(r) } for (i in 0 until p) { print("Row ${i + 1}: ") curr[i] = readLine()!!.split(' ').map { it.toInt() }.toIntArray() } println("\nEnter Maximum Claim Table: ") val maxClaim = Array(p) { IntArray(r) } for (i in 0 until p) { print("Row ${i + 1}: ") maxClaim[i] = readLine()!!.split(' ').map { it.toInt() }.toIntArray() } val alloc = IntArray(r) for (i in 0 until p) { for (j in 0 until r) alloc[j] += curr[i][j] } println("\nAllocated Resources: ${alloc.joinToString(" ")}") val avl = IntArray(r) { maxRes[it] - alloc[it] } println("\nAvailable Resources: ${avl.joinToString(" ")}") val running = BooleanArray(p) { true } var count = p while (count != 0) { var safe = false for (i in 0 until p) { if (running[i]) { var exec = true for (j in 0 until r) { if (maxClaim[i][j] - curr[i][j] > avl[j]) { exec = false break } } if (exec) { print("\nProcess ${i + 1} is executing.\n") running[i] = false count-- safe = true for (j in 0 until r) avl[j] += curr[i][j] break } } } if (!safe) { print("The processes are in an unsafe state.") break } print("\nThe process is in a safe state.") println("\nAvailable Vector: ${avl.joinToString(" ")}") } } Sample input/output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table: Row 1: 2 0 1 1 Row 2: 0 1 2 1 Row 3: 4 0 0 3 Row 4: 0 2 1 0 Row 5: 1 0 3 0 Enter Maximum Claim Table: Row 1: 3 2 1 4 Row 2: 0 2 5 2 Row 3: 5 1 0 5 Row 4: 1 5 3 0 Row 5: 3 0 3 3 Allocated Resources: 7 3 7 5 Available Resources: 1 2 2 2 Process 3 is executing. The process is in a safe state. Available Vector: 5 2 2 5 Process 1 is executing. The process is in a safe state. Available Vector: 7 2 3 6 Process 2 is executing. The process is in a safe state. Available Vector: 7 3 5 7 Process 4 is executing. The process is in a safe state. Available Vector: 7 5 6 7 Process 5 is executing. The process is in a safe state. Available Vector: 8 5 9 7
Module BankerAlgo { Form 80, 44 Cls 5 Pen 14 Function Request(FromWhere as Inventory, What$, Many as long) { =FromWhere(What$)-FromWhere(What$+"_Request")-Many>=0 } Function RequestPreset(FromWhere as Inventory, What$, Many as long) { =FromWhere(What$+"_Request")-Many>=0 } Function Need(FromWhere as Inventory, What$, Many) { =FromWhere(What$ + "_max")-FromWhere(What$)-Many>=0 } \\ code for sub can be found from parent module/function (here parent as in code, not as in call) Function NewProcess { Inventory Process ApplyResources(Process) ' sub need more arguments and read from current stack =Process } Inventory System, Processes \\ Recource, Max, Available ApplyResources(System, "A", 6, 3,"B", 5,1,"C", 7, 1, "D", 6, 2) \\ Recource, Max, Available Append Processes, "P1":=NewProcess("A", 3, 1, "B", 3, 2, "C", 2, 2, "D", 2,1) Append Processes, "P2":=NewProcess("A", 1, 1, "B", 2, 0, "C", 3, 3, "D", 4,3) Append Processes, "P3":=NewProcess("A", 1, 1, "B", 3, 2, "C", 5, 1, "D", 0,0) Status(True) ' show all process, available resource and max SafeState=True Print "Current Status" RequestResource() ' display Safe State RequestResource("P2", "D", 1) ' display Safe State RequestResource("P1", "A", 1, "D", 1) ' display Safe State RequestResource("P1", "C", 1, "D", 1) ' display Too many resources ... RequestResource("P2", "B", 1) ' display Unsafe State RequestResource("P3", "C", 1) ' display Safe State Status() \\ Second Example Clear System, Processes ApplyResources(System, "A", 10, 3) Append Processes, "P1":=NewProcess("A", 9, 3) Append Processes, "P2":=NewProcess("A", 4, 2) Append Processes, "P3":=NewProcess("A", 7, 2) Status(True) ' show all process, available resource and max Print "Current Status" RequestResource() ' display Safe State \ Third Example Clear System ApplyResources(System, "A", 10, 2) Return Processes, "P1":=NewProcess("A", 9,4) Status(True) ' show all process, available resource and max Print "Current Status" RequestResource() ' display UnSafe State Sub Respond() If SafeState Then { Pen 15 {Print "Safe State"} } Else Pen 13 {Print "Unsafe State"} End Sub Sub WaitForKey() Pen 11 {Print "Press a key"} local a$=key$ End Sub Sub RequestResource(ProcessName$="" ) SafeState=True If ProcessName$="" Then CheckNewState(&SafeState) : Respond() : Print : WaitForKey():Exit Sub Local pro=Processes(ProcessName$), ResourceName$, many as long ClearAllRequest(pro) Local skip=False While Match("SN") { Read ResourceName$, many Print Format$("Claim {1} for type {0} resource ",ResourceName$, many) If skip Then Continue If Request(System, ResourceName$, many) Then { If Need(pro, ResourceName$, many) Then { Return pro, ResourceName$+"_Request":=many Return System, ResourceName$+"_Request":=-many } Else { Print "Too many Recources "+ResourceName$+" for Process "+ProcessName$ : Skip=True } } Else Print "Too many Recources for System" : Skip=True If Skip Then exit } If skip Else CheckNewState(&SafeState) : Respond() Print ' just a new line WaitForKey() End Sub Sub ApplyResources(Where as Inventory, What$, MaxValue, InitialValue) Repeat { If Not Exist(Where, What$) Then { Append Where, What$:=InitialValue, What$+"_max":=MaxValue, What$+"_Request":=0 } If not Match("SNN") Then Exit Read What$, MaxValue, InitialValue } Always End Sub Sub ClearAllRequest(Where as Inventory) Local M=Each(Where) While M { If Instr(Eval$(M, M^),"_")=0 Then { Return Where, Eval$(M,M^)+"_Request":=0 } } End Sub Sub PrintResources(Where as Inventory) Local M=Each(Where) While M { If Instr(Eval$(M, M^),"_")=0 Then Print Eval$(M, M^)+"="+Eval$(M), } Print Exit Sub Sub PrintMax(Where as Inventory) Local M=Each(Where) While M { If Instr(Eval$(M, M^),"_max")>0 Then Print LeftPart$(Eval$(M, M^), "_")+"="+Eval$(M), } Print Exit Sub Sub Status(Ok as boolean=False) Print "Total System Resources" PrintMax(System) Print "Available Resources in System" PrintResources(System) If Not Ok Then WaitForKey(): Exit Sub Local M=Each(Processes) While M { Print "Process "+Eval$(M, M^) PrintResources(Processes(M^!)) ' give index M^ as Key index number (using !) Print "Maximum Resources for "+Eval$(M, M^) PrintMax(Processes(M^!)) } End Sub Sub CheckNewState(&Ok) local M=Each(Processes), M1, count=len(Processes), alive(0 to count-1)=1 Local Z, Recource$, safe as boolean=false While count { safe=false While M { If alive(M^) Then { Z=Processes(M^!) M1=Each(Z) safe=True While M1 { Recource$=Eval$(M1, M1^) If Instr(Recource$,"_")=0 Then { safe=System(Recource$)+System(Recource$+"_Request") >= Z(Recource$ + "_max") - Z(Recource$)-Z(Recource$ + "_Request") } If not safe Then exit } If safe Then { print format$("Process {0} is executing", M^+1) alive(M^)=0 count-- M1=Each(Z) While M1 { Recource$=Eval$(M1, M1^) If Instr(Recource$,"_")=0 Then { Return System, Recource$+"_Request":= System(Recource$+"_Request") + Z(Recource$) + Z(Recource$+"_Request") Return Z, Recource$+"_Request":=0 } } } } } If safe Else exit } Ok=safe ClearAllRequest(System) End Sub } BankerAlgoimport sequtils, strformat, strutils, sugar stdout.write "Enter the number of resources: " let r = stdin.readLine().parseInt() stdout.write "Enter the number of processes: " stdout.flushFile() let p = stdin.readLine().parseInt() stdout.write "Enter Claim Vector: " let maxRes = stdin.readLine().splitWhitespace().map(parseInt) echo "Enter Allocated Resource Table:" var curr = newSeqWith(p, newSeq[int](r)) for i in 0..<p: stdout.write &"Row {i + 1}: " curr[i] = stdin.readLine().splitWhitespace().map(parseInt) echo "Enter Maximum Claim Table:" var maxClaim = newSeqWith(p, newSeq[int](r)) for i in 0..<p: stdout.write &"Row {i + 1}: " maxClaim[i] = stdin.readLine().splitWhitespace().map(parseInt) var alloc = newSeq[int](r) for i in 0..<p: for j in 0..<r: alloc[j] += curr[i][j] echo &"\nAllocated Resources: {alloc.join(\" \")}" var avl = collect(newSeq, for i in 0..<r: maxRes[i] - alloc[i]) echo &"Available Resources: {avl.join(\" \")}" var running = repeat(true, p) var count = p while count > 0: var safe = false for i in 0..<p: if running[i]: var exec = true for j in 0..<r: if maxClaim[i][j] - curr[i][j] > avl[j]: exec = false break if exec: echo &"\nProcess {i + 1} is executing." running[i] = false dec count safe = true for j in 0..<r: avl[j] += curr[i][j] break if not safe: echo "The processes are in an unsafe state." break echo "\nThe process is in a safe state." echo &"Available Vector: {avl.join(\" \")}" - Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table: Row 1: 2 0 1 1 Row 2: 0 1 2 1 Row 3: 4 0 0 3 Row 4: 0 2 1 0 Row 5: 1 0 3 0 Enter Maximum Claim Table: Row 1: 3 2 1 4 Row 2: 0 2 5 2 Row 3: 5 1 0 5 Row 4: 1 5 3 0 Row 5: 3 0 3 3 Allocated Resources: 7 3 7 5 Available Resources: 1 2 2 2 Process 3 is executing. The process is in a safe state. Available Vector: 5 2 2 5 Process 1 is executing. The process is in a safe state. Available Vector: 7 2 3 6 Process 2 is executing. The process is in a safe state. Available Vector: 7 3 5 7 Process 4 is executing. The process is in a safe state. Available Vector: 7 5 6 7 Process 5 is executing. The process is in a safe state. Available Vector: 8 5 9 7
use strict; use warnings; use feature 'say'; my @avail = (3, 1, 1, 2); # Available instances of resource my @maxm = ([3, 3, 2, 2], [1, 2, 3, 4], [1, 3, 5, 0]); # Maximum R that can be allocated to processes my @allot = ([1, 2, 2, 1], [1, 0, 3, 3], [1, 2, 1, 0]); # Resources allocated to processes # Function to find the system is in safe state or not sub isSafe { my($work, $maxm, $allot) = @_; my $P = @$allot; # Number of processes my $R = @$work; # Number of resources my @unfinished = (1) x $P; # Mark all processes as unfinished my(@safeSeq,@need); for my $i (0..$P-1) { # Calculating need of each process: for my $j (0..$R-1) { # maxm instance - allocated instance $need[$i][$j] = $$maxm[$i][$j] - $$allot[$i][$j] } } # While all processes are not finished or system is not in safe state my $count = 0; while ($count < $P) { my $found = 0; for my $p (0..$P-1) { # While a process is not finished if ($unfinished[$p]) { # Check if for all resources of current P need is less than work my $satisfied; LOOP: for my $j (0..$R-1) { $satisfied = $j; last LOOP if $need[$p][$j] > $$work[$j] } # If all needs of p were satisfied if ($satisfied == $R-1) { $$work[$_] += $$allot[$p][$_] for 0..$R-1; # free the resources say 'available resources: ' . join ' ', @$work; push @safeSeq, $p; # Add this process to safe sequence $unfinished[$p] = 1; # Mark this process as finished $count += 1; $found = 1 } } } # If we could not find a next process in safe sequence. return 0, "System is not in safe state." unless $found; } # If system is in safe state then safe sequence will be as below return 1, "Safe sequence is: " . join ' ', @safeSeq } # Check system is in safe state or not my($safe_state,$status_message) = isSafe(\@avail, \@maxm, \@allot); say "Safe state? " . ($safe_state ? 'True' : 'False'); say "Message: $status_message"; - Output:
available resources: 4 3 3 3 available resources: 5 3 6 6 available resources: 6 5 7 6 Safe state? True Message: Safe sequence is: 0 1 2
with javascript_semantics sequence max_res = {6, 5, 7, 6}, curr = {{1, 2, 2, 1}, {1, 0, 3, 3}, {1, 2, 1, 0}}, running = repeat(true,length(curr)), max_claim = {{3, 3, 2, 2}, {1, 2, 3, 4}, {1, 3, 5, 0}}, alloc = repeat(0,length(max_res)) integer count = length(curr) for i=1 to count do alloc = sq_add(alloc,curr[i]) end for sequence avl = sq_sub(max_res,alloc) printf(1,"Available system resources: %V\n",{max_res}) printf(1,"Process allocated: %V\n",{curr}) printf(1,"Maximum resources: %V\n",{max_claim}) printf(1,"Allocated resources: %V\n",{alloc}) printf(1,"Available resources: %V\n",{avl}) while count!=0 do bool safe = false for i=1 to length(curr) do if running[i] then bool execute = true for j=1 to length(max_res) do if max_claim[i][j]-curr[i][j] > avl[j] then execute = false exit end if end for if execute then printf(1,"Process%d is executing. ", i) running[i] = false count -= 1 safe = true for j=1 to length(max_res) do avl[j] += curr[i][j] end for exit end if end if end for if not safe then printf(1,"The processes are in an unsafe state.\n") exit end if printf(1, "Safe state. Available resources: %V\n",{avl}) end while
- Output:
Available system resources: {6,5,7,6} Process allocated: {{1,2,2,1},{1,0,3,3},{1,2,1,0}} Maximum resources: {{3,3,2,2},{1,2,3,4},{1,3,5,0}} Allocated resources: {3,4,6,4} Available resources: {3,1,1,2} Process1 is executing. Safe state. Available resources: {4,3,3,3} Process2 is executing. Safe state. Available resources: {5,3,6,6} Process3 is executing. Safe state. Available resources: {6,5,7,6} Changing the initial curr[2] to {1, 1, 3, 3}:
Available system resources: {6,5,7,6} Process allocated: {{1,2,2,1},{1,1,3,3},{1,2,1,0}} Maximum resources: {{3,3,2,2},{1,2,3,4},{1,3,5,0}} Allocated resources: {3,5,6,4} Available resources: {3,0,1,2} The processes are in an unsafe state. def main(): resources = int(input("Number of resources: ")) processes = int(input("Number of processes: ")) max_resources = [int(i) for i in input("Maximum resources: ").split()] print("\n-- resources allocated for each process --") currently_allocated = [[int(i) for i in input(f"process {j + 1}: ").split()] for j in range(processes)] print("\n--- maximum resources for each process ---") max_need = [[int(i) for i in input(f"process {j + 1}: ").split()] for j in range(processes)] allocated = [0] * resources for i in range(processes): for j in range(resources): allocated[j] += currently_allocated[i][j] print(f"\nTotal resources allocated: {allocated}") available = [max_resources[i] - allocated[i] for i in range(resources)] print(f"Total resources available: {available}\n") running = [True] * processes count = processes while count != 0: safe = False for i in range(processes): if running[i]: executing = True for j in range(resources): if max_need[i][j] - currently_allocated[i][j] > available[j]: executing = False break if executing: print(f"process {i + 1} running") running[i] = False count -= 1 safe = True for j in range(resources): available[j] += currently_allocated[i][j] break if not safe: print("The process is in an unsafe state.") break print(f"The process is in a safe state.\nAvailable resources: {available}\n\n") if __name__ == '__main__': main() - Output:
Number of resources: 4 Number of processes: 3 Maximum resources: 6 5 7 6 -- resources allocated for each process -- process 1: 1 2 2 1 process 2: 1 0 3 3 process 3: 1 2 1 0 --- maximum resources for each process --- process 1: 3 3 2 2 process 2: 1 2 3 4 process 3: 1 3 5 0 Total resources allocated: [3, 4, 6, 4] Total resources available: [3, 1, 1, 2] process 1 running The process is in a safe state. Available resources: [4, 3, 3, 3] process 2 running The process is in a safe state. Available resources: [5, 3, 6, 6] process 3 running The process is in a safe state. Available resources: [6, 5, 7, 6]
#lang racket/base (require racket/block racket/pretty racket/port racket/vector) (pretty-print-columns 20) ; make the matrices look a bit more matrixey (define (bankers-algorithm p r maxres curr maxclaim) (define running? (make-vector p #t)) (define alloc (for/vector #:length r ((j (in-range r))) (for/sum ((cu_i (in-vector curr))) (vector-ref cu_i j)))) (printf "Allocated resources:~%~a~%" (pretty-format alloc)) (define avl (for/vector #:length r ((m (in-vector maxres)) (a (in-vector alloc))) (- m a))) (printf "Available resources:~%~a~%~%" (pretty-format avl)) (define (safe-exec i mc_i cu_i) (define exec? (for/and ((a (in-vector avl)) (m (in-vector mc_i)) (c (in-vector cu_i))) (<= (- m c) a))) (cond [exec? (printf "Process ~a is executing~%" (add1 i)) (vector-set! running? i #f) (for ((j (in-range r)) (a (in-vector avl)) (c (in-vector cu_i))) (vector-set! avl j (+ a c))) #t] [else #f])) (let loop () (unless (zero? (vector-count values running?)) (define safe? (for/first ((i (in-range p)) (r? (in-vector running?)) (mc_i (in-vector maxclaim)) (cu_i (in-vector curr)) ;; the break condition for this is identical to safe?, so we have no ;; separate break? flag #:when r? #:when (safe-exec i mc_i cu_i)) #t)) (cond [safe? (printf "The process is in a safe state~%~%Available vector: ~a~%" (pretty-format avl)) (loop)] [else (displayln "The processes are in an unsafe state")])))) (define (bankers-input) (define ((n-vector? type? dims) x) ;; not the world's most efficient implementation! (cond [(null? dims) (type? x)] [(not (vector? x)) #f] [(not (= (car dims) (vector-length x))) #f] [else (for/and ((e (in-vector x))) (n-vector? type? (cdr dims)) e)])) (define-syntax-rule (prompted-input prompt valid?) (block (printf "Enter ~a:~%" prompt) (define rv (read)) (pretty-print rv) (unless (valid? rv) (raise-argument-error 'prompted-input (format "~a" 'valid?) rv)) rv)) (define p (prompted-input "the number of processes" exact-positive-integer?)) (define r (prompted-input "the number of resources" exact-positive-integer?)) (define maxres (prompted-input "Claim Vector" (n-vector? exact-positive-integer? (list r)))) (define curr (prompted-input "Allocated Resource Table" (n-vector? exact-positive-integer? (list p r)))) (define maxclaim (prompted-input "Maximum Claim Table" (n-vector? exact-positive-integer? (list p r)))) (values p r maxres curr maxclaim)) (module+ main (with-input-from-string #<<EOS 5 4 #(8 5 9 7) #(#(2 0 1 1) #(0 1 2 1) #(4 0 0 3) #(0 2 1 0) #(1 0 3 0)) #(#(3 2 1 4) #(0 2 5 2) #(5 1 0 5) #(1 5 3 0) #(3 0 3 3)) EOS (λ () (call-with-values bankers-input bankers-algorithm)))) - Output:
Enter the number of processes: 5 Enter the number of resources: 4 Enter Claim Vector: '#(8 5 9 7) Enter Allocated Resource Table: '#(#(2 0 1 1) #(0 1 2 1) #(4 0 0 3) #(0 2 1 0) #(1 0 3 0)) Enter Maximum Claim Table: '#(#(3 2 1 4) #(0 2 5 2) #(5 1 0 5) #(1 5 3 0) #(3 0 3 3)) Allocated resources: '#(7 3 7 5) Available resources: '#(1 2 2 2) Process 3 is executing The process is in a safe state Available vector: '#(5 2 2 5) Process 1 is executing The process is in a safe state Available vector: '#(7 2 3 6) Process 2 is executing The process is in a safe state Available vector: '#(7 3 5 7) Process 4 is executing The process is in a safe state Available vector: '#(7 5 6 7) Process 5 is executing The process is in a safe state Available vector: '#(8 5 9 7)
(formerly Perl 6) Based on the Python3 solution by Shubham Singh found here
my @avail = <3 1 1 2>; # Available instances of resource my @maxm = <3 3 2 2>, <1 2 3 4>, <1 3 5 0>; # Maximum resources that can be allocated to processes my @allot = <1 2 2 1>, <1 0 3 3>, <1 2 1 0>; # Resources allocated to processes # Function to find the system is in safe state or not sub isSafe(\work is copy, \maxm, \allot) { my \P = allot.elems; # Number of processes my \Pool = (^P).SetHash; # Process pool my \R = work.elems; # Number of resources my \need = maxm »-« allot; # the need matrix my @safe-sequence; # While all processes are not finished or system is not in safe state my $count = 0; while $count < P { my $found = False; for Pool.keys -> \p { if all need[p] »≤« work { # now process can be finished work »+=« allot[p;^R]; # Free the resources say 'available resources: ' ~ work; @safe-sequence.push: p; # Add this process to safe sequence Pool{p}--; # Remove this process from Pool $count += 1; $found = True } } # If we could not find a next process in safe sequence return False, "System is not in safe state." unless $found; } # If system is in safe state then safe sequence will be as below return True, "Safe sequence is: " ~ @safe-sequence } # Check if system is in a safe state my ($safe-state,$status-message) = isSafe @avail, @maxm, @allot; say "Safe state? $safe-state"; say "Message: $status-message"; - Output:
available resources: 4 3 3 3 available resources: 5 3 6 6 available resources: 6 5 7 6 Safe state? True Message: Safe sequence is: 0 1 2
Adapted from the C language version. It crashes for invalid input.
fn read_numbers<T>() -> Vec<T> where T: std::str::FromStr { use std::io::Write; std::io::stdout().flush().unwrap(); let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split(" ").map(|word| word.trim().parse::<T>().ok().unwrap()).collect() } fn main() { print!("Enter the number of resources: "); let r = read_numbers()[0]; print!("Enter the number of processes: "); let p = read_numbers()[0]; let mut running = vec![true; p]; let mut count = p; print!("Enter the {}-item claim vector: ", r); let max_res = read_numbers::<u32>(); println!("Enter the {}-line {}-column allocated-resource table:", p, r); let mut curr = vec![vec![0; 0]; p]; for i in 0..p { curr[i] = read_numbers::<u32>(); } println!("Enter the {}-line {}-column maximum-claim table:", p, r); let mut max_claim = vec![vec![0; 0]; p]; for i in 0..p { max_claim[i] = read_numbers::<u32>(); } print!("The claim vector is: "); for i in 0..r { print!("{} ", max_res[i]); } println!(); println!("The allocated resources table is:"); for i in 0..p { for j in 0..r { print!("\t{}", curr[i][j]); } println!(); } println!("The maximum claims table is:"); for i in 0..p { for j in 0..r { print!("\t{}", max_claim[i][j]); } println!(); } let mut alloc = vec![0; r]; for i in 0..p { for j in 0..r { alloc[j] += curr[i][j]; } } print!("The allocated resources are: "); for i in 0..r { print!("{} ", alloc[i]); } println!(); let mut avl = vec![0; r]; for i in 0..r { avl[i] = max_res[i] - alloc[i]; } print!("The available resources are: "); for i in 0..r { print!("{} ", avl[i]); } println!(); while count != 0 { let mut safe = false; for i in 0..p { if running[i] { let mut exec = true; for j in 0..r { if max_claim[i][j] - curr[i][j] > avl[j] { exec = false; break; } } if exec { println!("Process {} is executing.", i + 1); running[i] = false; count -= 1; safe = true; for j in 0..r { avl[j] += curr[i][j]; } break; } } } if safe { println!("The process is in safe state."); } else { println!("The processes are in unsafe state."); break; } print!("The available vector is: "); for i in 0..r { print!("{} ", avl[i]); } println!(); } } - Input and Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter the 4-item claim vector: 8 5 9 7 Enter the 5-line 4-column allocated-resource table: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 Enter the 5-line 4-column maximum-claim table: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 The claim vector is: 8 5 9 7 The allocated resources table is: 2 0 1 1 0 1 2 1 4 0 0 3 0 2 1 0 1 0 3 0 The maximum claims table is: 3 2 1 4 0 2 5 2 5 1 0 5 1 5 3 0 3 0 3 3 The allocated resources are: 7 3 7 5 The available resources are: 1 2 2 2 Process 3 is executing. The process is in safe state. The available vector is: 5 2 2 5 Process 1 is executing. The process is in safe state. The available vector is: 7 2 3 6 Process 2 is executing. The process is in safe state. The available vector is: 7 3 5 7 Process 4 is executing. The process is in safe state. The available vector is: 7 5 6 7 Process 5 is executing. The process is in safe state. The available vector is: 8 5 9 7
import scala.io.StdIn.readLine object BankersAlgorithm { def main(args: Array[String]): Unit = { println("Number of resources: ") val resources = readLine().toInt println("Number of processes: ") val processes = readLine().toInt println("Maximum resources: ") val maxResources = readLine().split(" ").map(_.toInt) println("\n-- resources allocated for each process --") val currentlyAllocated = Array.ofDim[Int](processes, resources) for (i <- 0 until processes) { println(s"process ${i + 1}: ") currentlyAllocated(i) = readLine().split(" ").map(_.toInt) } println("\n--- maximum resources for each process ---") val maxNeed = Array.ofDim[Int](processes, resources) for (i <- 0 until processes) { println(s"process ${i + 1}: ") maxNeed(i) = readLine().split(" ").map(_.toInt) } val allocated = Array.fill(resources)(0) for (i <- 0 until processes) { for (j <- 0 until resources) { allocated(j) += currentlyAllocated(i)(j) } } println(s"\nTotal resources allocated: ${allocated.mkString(", ")}") val available = maxResources.zip(allocated).map { case (max, alloc) => max - alloc } println(s"Total resources available: ${available.mkString(", ")}\n") var running = Array.fill(processes)(true) var count = processes while (count != 0) { var safe = false for (i <- 0 until processes if running(i)) { var executing = true for (j <- 0 until resources) { if (maxNeed(i)(j) - currentlyAllocated(i)(j) > available(j)) { executing = false } } if (executing) { println(s"process ${i + 1} is running") running(i) = false count -= 1 safe = true for (j <- 0 until resources) { available(j) += currentlyAllocated(i)(j) } } } if (!safe) { println("The processes are in an unsafe state.") return } println(s"The processes are in a safe state.\nAvailable resources: ${available.mkString(", ")}\n") } } } input
4 3 6 5 7 6 1 2 2 1 1 0 3 3 1 2 1 0 3 3 2 2 1 2 3 4 1 3 5 0
- Output:
Number of resources: 4 Number of processes: 3 Maximum resources: 6 5 7 6 -- resources allocated for each process -- process 1: 1 2 2 1 process 2: 1 0 3 3 process 3: 1 2 1 0 --- maximum resources for each process --- process 1: 3 3 2 2 process 2: 1 2 3 4 process 3: 1 3 5 0 Total resources allocated: 3, 4, 6, 4 Total resources available: 3, 1, 1, 2 process 1 is running process 2 is running process 3 is running The processes are in a safe state. Available resources: 6, 5, 7, 6
import Foundation print("Enter the number of resources: ", terminator: "") guard let resources = Int(readLine(strippingNewline: true)!) else { fatalError() } print("Enter the number of processes: ", terminator: "") guard let processes = Int(readLine(strippingNewline: true)!) else { fatalError() } var running = Array(repeating: true, count: processes) var curr = Array(repeating: [Int](), count: processes) var alloc = Array(repeating: 0, count: resources) var available = Array(repeating: 0, count: resources) var maxClaims = Array(repeating: [Int](), count: processes) var count = processes print("Enter the \(resources)-item claim vector: ", terminator: "") guard let maxRes = readLine(strippingNewline: true)?.components(separatedBy: " ").compactMap(Int.init), maxRes.count == resources else { fatalError() } print("Enter the \(processes)-line \(resources)-column allocated-resource table:") for i in 0..<processes { print("Row \(i + 1): ", terminator: "") guard let allc = readLine(strippingNewline: true)?.components(separatedBy: " ").compactMap(Int.init), maxRes.count == resources else { fatalError() } curr[i] = allc } print("Enter the \(processes)-line \(resources)-column maximum-claim table:") for i in 0..<processes { print("Row \(i + 1): ", terminator: "") guard let clms = readLine(strippingNewline: true)?.components(separatedBy: " ").compactMap(Int.init), maxRes.count == resources else { fatalError() } maxClaims[i] = clms } for i in 0..<processes { for j in 0..<resources { alloc[j] += curr[i][j] } } for i in 0..<resources { available[i] = maxRes[i] - alloc[i] } print("The claim vector is: \(maxRes)") print("The allocated resources table is: \(curr)") print("The maximum claims table is: \(maxClaims)") print("The allocated resources are: \(alloc)") print("The available resources are: \(available)") while count != 0 { var safe = false for i in 0..<processes where running[i] { var exec = true for j in 0..<resources where maxClaims[i][j] - curr[i][j] > available[j] { exec = false break } if exec { print("Process \(i + 1) is executing.") running[i] = false count -= 1 safe = true for j in 0..<resources { available[j] += curr[i][j] } break } } if safe { print("The process is in safe state.") } else { print("The processes are in unsafe state.") break } print("The available vector is: \(available)") } - Input and Output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter the 4-item claim vector: 8 5 9 7 Enter the 5-line 4-column allocated-resource table: Row 1: 2 0 1 1 Row 2: 0 1 2 1 Row 3: 4 0 0 3 Row 4: 0 2 1 0 Row 5: 1 0 3 0 Enter the 5-line 4-column maximum-claim table: Row 1: 3 2 1 4 Row 2: 0 2 5 2 Row 3: 5 1 0 5 Row 4: 1 5 3 0 Row 5: 3 0 3 3 The claim vector is: [8, 5, 9, 7] The allocated resources table is: [[2, 0, 1, 1], [0, 1, 2, 1], [4, 0, 0, 3], [0, 2, 1, 0], [1, 0, 3, 0]] The maximum claims table is: [[3, 2, 1, 4], [0, 2, 5, 2], [5, 1, 0, 5], [1, 5, 3, 0], [3, 0, 3, 3]] The allocated resources are: [7, 3, 7, 5] The available resources are: [1, 2, 2, 2] Process 3 is executing. The process is in safe state. The available vector is: [5, 2, 2, 5] Process 1 is executing. The process is in safe state. The available vector is: [7, 2, 3, 6] Process 2 is executing. The process is in safe state. The available vector is: [7, 3, 5, 7] Process 4 is executing. The process is in safe state. The available vector is: [7, 5, 6, 7] Process 5 is executing. The process is in safe state. The available vector is: [8, 5, 9, 7]
import "io" for Stdin, Stdout System.write("Enter the number of resources: ") Stdout.flush() var r = Num.fromString(Stdin.readLine()) System.write("\nEnter the number of processes: ") Stdout.flush() var p = Num.fromString(Stdin.readLine()) System.write("\nEnter Claim Vector: ") Stdout.flush() var maxRes = Stdin.readLine().split(" ").map { |s| Num.fromString(s) }.toList System.print("\nEnter Allocated Resource Table:") var curr = List.filled(p, null) for (i in 0...p) { System.write("Row %(i + 1): ") Stdout.flush() curr[i] = Stdin.readLine().split(" ").map { |s| Num.fromString(s) }.toList } System.print("\nEnter Maximum Claim Table: ") var maxClaim = List.filled(p, null) for (i in 0...p) { System.write("Row %(i + 1): ") Stdout.flush() maxClaim[i] = Stdin.readLine().split(" ").map { |s| Num.fromString(s) }.toList } var alloc = List.filled(r, 0) for (i in 0...p) { for (j in 0...r) alloc[j] = alloc[j] + curr[i][j] } System.print("\nAllocated Resources: %(alloc.join(" "))") var avl = List.filled(r, 0) for (i in 0...r) avl[i] = maxRes[i] - alloc[i] System.print("\nAvailable Resources: %(avl.join(" "))") var running = List.filled(p, true) var count = p while (count != 0) { var safe = false for (i in 0...p) { if (running[i]) { var exec = true for (j in 0...r) { if (maxClaim[i][j] - curr[i][j] > avl[j]) { exec = false break } } if (exec) { System.print("\nProcess %(i + 1) is executing.") running[i] = false count = count - 1 safe = true for (j in 0...r) avl[j] = avl[j] + curr[i][j] break } } } if (!safe) { System.print("\nThe processes are in an unsafe state.") break } System.write("\nThe process is in a safe state.") System.print("\nAvailable Vector: %(avl.join(" "))") } - Output:
Sample input/output:
Enter the number of resources: 4 Enter the number of processes: 5 Enter Claim Vector: 8 5 9 7 Enter Allocated Resource Table: Row 1: 2 0 1 1 Row 2: 0 1 2 1 Row 3: 4 0 0 3 Row 4: 0 2 1 0 Row 5: 1 0 3 0 Enter Maximum Claim Table: Row 1: 3 2 1 4 Row 2: 0 2 5 2 Row 3: 5 1 0 5 Row 4: 1 5 3 0 Row 5: 3 0 3 3 Allocated Resources: 7 3 7 5 Available Resources: 1 2 2 2 Process 3 is executing. The process is in a safe state. Available Vector: 5 2 2 5 Process 1 is executing. The process is in a safe state. Available Vector: 7 2 3 6 Process 2 is executing. The process is in a safe state. Available Vector: 7 3 5 7 Process 4 is executing. The process is in a safe state. Available Vector: 7 5 6 7 Process 5 is executing. The process is in a safe state. Available Vector: 8 5 9 7
clear screen input "Ingrese la cantidad de recursos: " r input "Ingrese la cantidad de procesos: " p print "\nIngrese los recursos m ximos: " dim maxRes(r) for i = 1 to r input " " maxRes(i) next i print "\n-- recursos asignados para cada proceso --" dim curr(p, r) for i = 1 to p print "proceso ", i, ":" for j = 1 to r input " " curr(i, j) next j print next i print "\n--- recursos m ximos para cada proceso ---" dim maxReclam(p, r) for i = 1 to p print "proceso ", i, ":" for j = 1 to r input " " maxReclam(i, j) next j print next i print "\nRecursos totales asignados : "; dim recAsigad(r) for i = 1 to p for j = 1 to r recAsigad(j) = recAsigad(j) + curr(i, j) next j next i for i = 1 to r print recAsigad(i), " "; next i dim recDispon(r) print "\nRecursos totales disponibles: "; for i = 1 to r recDispon(i) = maxRes(i) - recAsigad(i) print recDispon(i), " "; next i dim ejecutando(p) for i = 1 to p ejecutando(i) = True next i contar = p while contar <> 0 seguro = False for i = 1 to p if ejecutando(i) then ejecuta = True for j = 1 to r if (maxReclam(i,j) - curr(i,j) > recDispon(j)) then ejecuta = False break end if next j if ejecuta then print color("cya") "\n\nproceso ", i, " ejecut ndose." ejecutando(i) = False contar = contar - 1 seguro = True for j = 0 to r recDispon(j) = recDispon(j) + curr(i,j) next j break end if end if next i if not seguro then print color("red") "\nLos procesos est n en un estado inseguro." break end if print color("gre") "El proceso est en un estado seguro." print color("whi")"Recursos disponibles: ", for i = 1 to r print recDispon(i), " "; next i wend print end