Bank home algorithm analysis report
One. Algorithm introduction:
**data structure:
1. Value available resources available for Available
2. Maximum demand matrix MAX
3. Assign Matrix Allocation
4. Demand matrix NEED
**Features:
Simulate the banker algorithm for Dijkstra to avoid deadlocks. Divide two parts:
Part 1: Bank algorithm (scan)
1. If required, turn to 2; otherwise, error
2. If Request <= Available, turn to 3, otherwise waiting
3. System Try the resource for allocation requests to the process
4. System execution security algorithm
Part II: Safety Algorithm
Set two vectors
(1). Work vector: Work = available (indicating the number of resources required to process to process continued to run)
(2) .finish: Indicates if there is enough resource allocation to the process (True: Yes; false: no). Initialization is false
2. If Finish [i] = false && need <= work, execute 3; otherwise, 4 (i is the resource category)
3. Process P Gets Class I resources, execute smoothly until it is complete! And release resources:
Work = work allocation;
Finish [i] = true;
Transfer
4. If all processes are finish [i] = true, the system security is indicated; otherwise, not safe!
II. Original code and notes:
#include
#include
#include
#include "windows.h"
#define max_process 32 // maximum number of processes
#define max_cource 64 // Maximum resource category
INT max_fact_process; // actual total process number
INT max_fact_cource; // actual resource category number
Int available [max_cource]; // can take advantage of the resource vector
INT MAX [MAX_PROCESS] [MAX_COURCE]; // Maximum demand matrix
INT Allocation [MAX_PROCESS] [MAX_COURCE]; // Assign Matrix
INT NEED [MAX_PROCESS] [MAX_COURCE]; // demand matrix
INT Request_Process; / / Process issued
INT Request_cource; // Request resource category
INT request_cource_nember; // Request for resources
Struct comp {
Int value;
Int Num;
Int next;
}
INT FLAG = 0;
Void read_initiate (void) {// Read Initialization Document
IFStream Infile ("Initiate.txt");
IF (! infile) {
Cout << "cannot open the input file:" << "initiate.txt" << '/ n';
Exit (1);
}
COUT << "Start reading initialization document" << '/ n';
int CH;
Int Array [MAX_PROCESS * MAX_COURCE * 2];
INT NUM = 0;
While (Infile >> CH)
Array [NUM ] = CH; Num = 0;
Max_FACT_COURCE = Array [NUM ];
For (int J = 0; j Available [J] = Array [NUM ]; Max_FACT_PROCESS = array [Num ]; For (int i = 0; i For (int J = 0; j Max [i] [j] = array [num ]; } Infile.Close (); } Void write_initiate (void) {// Write Initialization Document (Assign Resources OFSTREAM OUTFILE ("INITIATE.TXT"); IF (! outfile) { Cout << "cannot open the initialization document:" << '/ n'; Exit (1); } Int Array [MAX_PROCESS * MAX_COURCE * 2]; INT NUM = 0; Array [NUM ] = max_fact_cource; For (int i = 0; i Array [Num ] = Available [i]; Array [NUM ] = max_fact_process; For (i = 0; i For (int J = 0; j Array [Num ] = Max [i] [j]; Num = 0; Outfile << array [NUM ] << " For (i = 0; i Outfile << array [NUM ] << " Outfile << '/ n' << array [num ] << ENDL; For (i = 0; i For (int J = 0; j Outfile << array [NUM ] << " Outfile << Endl; } DWORD M_DELAY = 3000; Sleep (m_delay); Outfile.Close (); Cout << "Modify the initialization document success!" << Endl; } Void allocated_list (void) {// read into the list of assigned resources IFStream Infile ("allocated_list.txt"); IF (! infile) { Cout << "cannot open the input file:" << "allocated_list.txt" << '/ n'; Exit (1); } Cout << "starts reading the list of allocated resources" << '/ n'; int CH, NUM = 0; Int arch [max_process * max_cource]; While (Infile >> CH) Array [NUM ] = CH; Num = 0; For (int i = 0; i For (int J = 0; j Allocation [i] [j] = array [NUM ]; Infile.Close (); } Void set_need (void) {// Setting the requirements matrix COUT << "Settings the demand matrix" << '/ n'; For (int i = 0; i For (int J = 0; j NEED [i] [j] = max [i] [j] -allocation [i] [j]; } Void read_request (void) {// read the request vector IFStream Infile ("Request_List.txt"); IF (! infile) { Cout << "You cannot open the input file:" << "Request_List.txt" << '/ n'; Exit (1); } Cout << "Start reading request vector" << '/ n'; Int arch [3]; INT NUM = 0, CH; While (Infile >> CH) Array [NUM ] = CH; Request_process = array [0]; Request_cource = array [1]; Request_cource_nember = array [2]; Infile.Close (); } Void write_allocation (void) {// Modify the resource allocation list (resource allocation) OFSTREAM OUTFILE ("allocated_list.txt"); IF (! outfile) { COUT << "You cannot open the resource allocation list:" << '/ n'; Exit (1); } For (int i = 0; i For (int J = 0; j Outfile << Allocation [i] [j] << " Outfile << Endl; } DWORD M_DELAY = 3000; Sleep (m_delay); Cout << "Modify the resource allocation list successfully!" << Endl; Outfile.Close (); } Void allocate_source (void) {// Start assignment (have been detected by scanning and security) Cout << '/ n' << "starts to the" << Request_Process << "Process Assignment Pinth" << Request_cource << "<< Request_cource_nember <<" "<< endl; Write_initiate (); WRITE_ALLOCATION (); DWORD M_DELAY = 3000; Sleep (m_delay); COUT << '/ n' << "Congratulations, resource allocation has been successful!" << Endl; } Void test_safty () {// security detection Cout << '/ n' << "Entering Security Detection!" << Endl; INT WORK [MAX_COURCE]; For (int I = 0; i Work [i] = available [i]; } Bool finish [MAX_PROCESS] [MAX_COURCE]; For (i = 0; i For (int J = 0; j FINISH [I] [J] = false; Comp Array [32]; For (i = 0; i { Array [i] .value = need [i] [request_cource-1]; Array [i] .num = i; } For (i = 0; i For (int J = i 1; j IF (array [i] .value> = array [j] .value) { Int T; T = array [j] .value; Array [J] .Value = array [i] .value; Array [i] .value = t; T = array [j] .num; Array [j] .num = array [i] .num; Array [i] .num = t; } Else Continue; } DWORD M_DELAY = 3000; Sleep (m_delay); / * for (i = 0; i For (int J = 0; j COUT << NEED [i] [j] << '/ t'; Cout << Endl; } * / IF (Finish [Request_Process-1] [Request_Cource-1] == false && need [request_process-1] [request_cource-1] <= Work [Request_cource-1]) { Work [Request_Cource-1] = Work [Request_cource-1] Allocation [Request_Process-1] [Request_Cource-1]; Finish [Request_Process-1] [Request_cource-1] = true; } Else { COUT << "does not pass security test, not with allocation" << endl; exit (0); } For (i = 0; i IF (array [i] .num == request_process-1) CONTINUE; IF (array [i] .num! = request_process-1 && finish [array [i] .num] [request_cource-1] == false && need [array [i] .num] [request_cource-1] <= work [request_cource-1] ) { Work [Request_cource-1] = Work [Request_cource-1] Allocation [Array [i] .num] [Request_cource-1]; Finish [Array [i] .num] [Request_cource-1] = true; } } For (i = 0; i { IF (Finish [I] [Request_cource-1] == True) CONTINUE; Else { COUT << "does not pass security test, not with allocation" << endl; exit (0); } } Cout << '/ n' << "found a security sequence:" << "p" << Request_Process << "---> For (i = 0; i IF (array [i] .num == required_process) CONTINUE; Else COUT << "p" << array [i] .num << "--->"; } Cout << '/ n' << "has passed security test!" << Endl; Allocate_source (); } Void Run (void) {// Executive banker algorithm COUT << "************************************************************ *** "<< '/ n' <<" Click 1 to execute! " << '/ n' << "Click 2 to exit!" << '/ n' << "**************************************** ******** "<< Endl; CIN >> FLAG; IF (Flag == 2) exit (0); IF (Flag == 1) { Cout << "Start Scanning Request Information!" << Endl; DWORD M_DELAY = 3000; Sleep (m_delay); IF (Request_cource_Nember> NEED [Request_Process-1] [Request_cource-1]) { COUT << '/ n' << "" << Request_Process << "Process Request Press" << Request_cource << "" << Request_cource_nember << "<< Endl; cout <<" The maximum number of resources that is still needed to exceed this process, so do not assign it !! "<< endl; exit (0); } IF (request_cource_nember> available [request_cource-1]) { Cout << '/ n' << "" << Request_Process << "Process Request Press" << Request_cource << "<< Request_cource_Nember <<" "<< endl; Cout << "However, there is no sufficient resource in the system, so enter the waiting queue !!" << endl; exit (0); } Else { Available [Request_cource-1] = available [request_cource-1] -request_cource_nember; Allocation [Request_Process-1] [Request_cource-1] = allocation [request_process-1] [Request_Cource-1] Request_Cource_Nember; NEED [Request_Process-1] [Request_cource-1] = NEED [Request_Process-1] [Request_cource-1] -Request_cource_nember; COUT << "Scan" << endl; Sleep (m_delay); Test_safty (); } } Else { Cout << "Enter an error, please re-enter!" << '/ n'; Run (); } } Void main (void) { Read_initiate (); Cout << max_fact_cource << '/ t'; For (int i = 0; i COUT << Available [i] << '/ t'; Cout << Endl << max_fact_process << Endl; For (i = 0; i For (int J = 0; j COUT << max [i] [j] << '/ t'; Cout << Endl; } DWORD M_DELAY = 3000; Sleep (m_delay); COUT << "Read success" << '/ n'; Allocated_list (); For (i = 0; i For (int J = 0; j COUT << Allocation [i] [j] << '/ t'; cout << endl; } Sleep (m_delay); COUT << "Read success" << '/ n'; Set_need (); For (i = 0; i For (int J = 0; j COUT << NEED [i] [j] << '/ t'; Cout << Endl; } Sleep (m_delay); COUT << "Setting success" << '/ n'; Read_Request (); Cout << '/ n' << "" << Request_Process << "Process Request Press" << Request_cource << "<< Request_cource_Nember <<" "<< endl; COUT << '/ n' << "Read success" << '/ n'; Run (); } three. Data test Note: Array Array [i] indicates the number of actual significance of i 1 Three TXT text needs to be created. 1.initiate.txt text 3 3 3 2 // Total 3 types of resources, available [0] = 3; available [1] = 3; available [2] = 2 5 // There is a process in the current system 7 5 3 //max [0] [0] = 7 3 2 2 //max [1] [1] = 3 9 0 2 2 2 2 4 3 3 2.allocated_list.txt text 0 1 0 // Allocation [0] [1] = 1 2 0 0 3 0 2 2 1 1 0 0 2 3.Request_list.txt text 2 1 1 / / The second process requests 1 Request [1] [0] = 1 four. Program description: This program assumes that only one process is requested to request a certain type of resource n. To meet a certain type of resource at the time of the current time, it is necessary to increase the dimension of the maximum demand matrix Max, allocate matrix allocation, and demand matrix NEED, of course, the amount of code will also increase, but the algorithm logic itself has no change.
