1. Experimental purpose
Use a high-level language to write and debug a Banker’s Algorithm program, and use the Banker’s Algorithm to simulate resource allocation and perform safety checks. Deepen your understanding of the Banker’s Algorithm.
2. Experimental environment:
Hardware environment: one computer, LAN environment;
Software environment: Windows XP and above, Professional operating system platform, Visual C++ 6.0 Professional Edition or Enterprise Edition.
3. Experimental guidance
1. Data structure in banker’s algorithm
(1) Available resource vector Available. This is an array containing m elements. Each element represents the number of available resources of a type. Its initial value is the number of all available resources of this type configured in the system. Its value varies with the allocation and allocation of this type of resources. Recycle and change dynamically. If Available[j]=K, it means that there are K existing Rj type resources in the system.
(2) Maximum demand matrix Max. This is a matrix of n×m, which defines the pair m of each of the n processes in the system. em>The maximum demand for class resources. If Max[i,j]=K, it means that the maximum number of Rj type resources required by process i is K.
(3) Allocation matrix Allocation. This is also an n×m matrix, which defines the number of resources currently allocated to each process for each type of resource in the system. If Allocation[i,j]=K, it means that the number of Rj type resources currently allocated to process i is K.
(4) Demand matrix Need. This is also an n×m matrix, used to represent the number of various resources that each process still requires. If Need[i,j]=K, it means that process i still needs Rj type resources K to complete its task.
Need［i,j］=Max［i,j］-Allocation［i,j］
2. Banker’s Algorithm
Let Requesti be the request vector of process Pi. If Requesti[j]=K, it means that process Pi needs K resources of type Rj. When Pi sends a resource request, the system checks according to the following steps:
(1) If Requesti[j]≤Need[i,j], go to step 2; otherwise, it is considered an error because the number of resources it requires has exceeded the maximum value announced.
(2) If Requesti[j]≤Available[j], go to step (3); otherwise, it means there are not enough resources and Pi must wait.
(3) The system tentatively allocates resources to process Pi and modifies the values in the following data structure:
Available［j］= Available［j］-Requesti［j］;
Allocation［i,j］= Allocation［i,j］ + Requesti［j］;
Need［i,j］= Need［i,j］-Requesti［j］;
(4) The system executes the security algorithm to check whether the system is in a safe state after this resource allocation. If it is safe, the resources will be officially allocated to process Pi to complete this allocation; otherwise, this trial allocation will be invalidated, the original resource allocation status will be restored, and process Pi will wait.
3. Security algorithm
(1) Set two vectors: ① Work vector Work: It represents the number of various resources that the system can provide to the process to continue running. It contains m elements. When the security algorithm starts, Work:=Available; ② Finish: It indicates whether the system has enough resources allocated to the process to complete its operation. At the beginning, make Finish[i]=false; when enough resources are allocated to the process, make Finish[i]=true.
(2) Find a process from the process set that satisfies the following conditions: ① Finish［i］=false; ② Need［i,j］≤Work［j］; If found, execute step (3), otherwise, execute Step (4).
(3) After process Pi obtains resources, it can be executed smoothly until it is completed and the resources allocated to it are released, so it should be executed:
Work［j］=Work［i］ + Allocation［i,j］;
Finish［i］=true;
go to step 2;
(4) If Finish[i]=true of all processes is satisfied, it means that the system is in a safe state; otherwise, the system is in an unsafe state.
4. Tips
You can use the following data as test data
Assume that there are five processes {P0, P1, P2, P3, P4} and three types of resources {A, B, C} in the system. The numbers of various resources are 10, 5, and 7 respectively. In T The resource allocation situation at em>0 time is shown in Figure 2-1.
Figure 2-1 Resource allocation table at time T0
request sequence
(1) P1 sends the request vector Request1(1, 0, 2)
(2) P4 sends the request vector Request4(3, 3, 0)
(3) P0 sends the request vector Requst0(0, 2, 0)
4. Experimental steps (including flow chart, experimental process analysis, etc.)
Process analysis:
(1) The process applies for resources for the first time: Check whether the requested resources are less than need&&available. If the existing resources of the system can be satisfied, the resources will be allocated according to the current application amount, otherwise the allocation will be postponed.
(2) The process continues to apply for resource allocation during execution: If the sum of the resources occupied by the process and the resources applied for this time does not exceed the maximum demand for resources, and the existing resources can meet the maximum amount of resources still needed by the process , then the resources will be allocated according to the current application amount, otherwise the allocation will be postponed.
(3) Ensure that at least one process can obtain all the required resources and execute to the end. If it does not exist, it means that the process is unsafe.
(4) First set all the finish arrays to false, indicating that no process has been completed yet. Then traverse all processes and determine whether the need[i][j] of each process is less than the available resources. If it is satisfied, it means that the current process has been completed. Finish[i] = true is executed, and the corresponding subscript is recorded for output safety. sequence.
flow chart:
5. Experimental results and analysis
Chart 1 Initialization results
Diagram 2 Menu
- P1 issues a request vector Request1(1, 0, 2)
Process security, the process security sequence is: P1 P3 P4 P0 P2
(2) P4 sends the request vector Request4(3, 3, 0)
The request vector is larger than the available vector (2, 3, 0), so the requested resource is too large and the resource cannot be allocated.
(3) P0 sends the request vector Requst0(0, 2, 0)
After allocating resources, the available resources will not meet the needs of any process, so the process is unsafe.
6. Experimental source code
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 20 //Number of resources
#define M 50 //Number of processes
int available[N], maxneed[N][M], allocation[N][M], need[N][M], safe[M], temp[N]; // safe--》safety sequence, temp --》Storage available
int n, m, safel = 0;
bool finish[M]={false};
void Init(){ //Initialization
n=5;m=3;
int maxneedl[n][m]={<!-- -->{7,5,3},{3,2,2},{9,0,2},{2,2,2},{ 4,3,3}}; //Array definition and initialization cannot be separated
int allocationl[n][m]={<!-- -->{0,1,0},{2,0,0},{3,0,2},{2,1,1},{ 0,0,2}};
for (int i = 0;i < n;i + + ) {
for (int j = 0;j < m;j + + ) {
maxneed[i][j]=maxneedl[i][j];
}
for (int j = 0;j < m;j + + ) {
allocation[i][j]=allocationl[i][j];
}
for (int j = 0;j < m;j + + ) {
need[i][j] = maxneed[i][j] - allocation[i][j];
}
}
available[0]=3;
available[1]=3;
available[2]=2;
for (int i = 0;i < m;i + + ) { //Restore
temp[i] = available[i]; //used for subsequent restoration of available data
}
}
bool safety() { //Safety algorithm
int count = n, flag = 0, t = 0; //0 is true, 1 is false, t determines it is unsafe to jump out of the loop
while (count!=0) {
for (int i = 0;i < n;i + + ) {
for (int j = 0;j < m;j + + ) {
if (available[j] < need[i][j] & amp; & amp; finish[i] != true) {
flag = 1; //Available resources do not meet the needs of the current process
}
}
if (flag == 0 & amp; & amp; finish[i] != true) { //Available resources satisfy the resource request of the current process and the current process is not completed
for (int k = 0;k < m;k + + ) {
available[k] + = allocation[i][k]; //Recover allocated resources
finish[i] = true; //process completed
}
safe[safel] = i; //safe sequence
safel + + ;
count--; //Add one to the number of process completions, exit the loop and return true if all are completed
t = 1; //This cycle exists to satisfy the resource allocation process
}
flag = 0; //restore to 0
}
if (t == 0) { //This loop process does not meet the resource allocation, then jump out of the loop and return an error
return false;
}
t = 0; //Restore the judgment conditions for the next cycle
}
return true;
}
bool requst() { //m is the number of resources
int a, requst[M], flag=0, e=0; //e is used to determine whether the process still needs resources
printf("The process number of the input request:");
scanf("%d", & amp;a);
a--; //Convert to corner mark
printf("The request vector is:");
for (int i = 0;i < m;i + + ) {
scanf("%d", & amp;requst[i]);
}
for (int i = 0;i < m;i + + ) {
if (requst[i] > available[i] || requst[i] > need[a][i]) {
flag = 1;
}
}
if (flag == 1) {
printf("The requested resource is too large and cannot be allocated\\
");
return false;
}
else {
for (int i = 0;i < m;i + + ) { //Try to allocate
allocation[a][i] + = requst[i]; //Increase allocated resources
need[a][i] -= requst[i]; //need less resources
available[i] -= requst[i]; //Reduced callable resources
}
for(int i = 0;i < n;i + + ){
finish[i] = false; //Restore process completion status
}
for (int i = 0;i < m;i + + ) { //Determine whether the process has obtained all required resources
if(need[a][i] != 0){
e=1;
}
}
if (safety()) {
for (int i = 0;i < m;i + + ) { //Restore
allocation[a][i] -= requst[i];
need[a][i] + = requst[i];
available[i] = temp[i];
}
if(e==1){
for (int i = 0;i < m;i + + ) { //Change the corresponding resource
allocation[a][i] + = requst[i];
need[a][i] -= requst[i];
available[i] -= requst[i];
temp[i] = available[i];
}
}
else{
for (int i = 0;i < m;i + + ) { //Change the corresponding resource
available[i] + = allocation[a][i];
temp[i] = available[i];
allocation[a][i] = 0;
need[a][i] = 0;
}
}
printf("Process Security\\
");
printf("The process security sequence is:");
for (int i = 0;i < n;i + + ) {
printf("P%d ", safe[i]);
}
safel = 0;
return true;
}
else {
for (int i = 0;i < m;i + + ) { //Restore
allocation[a][i] -= requst[i];
need[a][i] + = requst[i];
available[i] = temp[i];
}
printf("The process is not safe\\
");
return false;
}
}
}
void _scanf() { //Input
printf("Please enter the number of processes:");
scanf("%d", & amp;n);
printf("Please enter the number of resource types:");
scanf("%d", & amp;m);
printf("\\
");
for (int i = 0;i < n;i + + ) {
printf("Please enter data according to the number of resource types:\\
");
printf("Maximum demand vector of process %d:",i + 1);
for (int j = 0;j < m;j + + ) {
scanf("%d", & amp;maxneed[i][j]);
}
printf("Allocation vector of process %d:",i + 1);
for (int j = 0;j < m;j + + ) {
scanf("%d", & amp;allocation[i][j]);
}
printf("\\
");
for (int j = 0;j < m;j + + ) {
need[i][j] = maxneed[i][j] - allocation[i][j];
}
}
printf("Please enter available resource vector:");
for (int i = 0;i < m;i + + ) {
scanf("%d", & amp;available[i]);
temp[i] = available[i]; //used for subsequent restoration of available data
}
}
/*
void Sscanf() { //Randomly generate process --》n, m is not 5, 3, the output style is destroyed
printf("Please enter the number of processes:");
scanf_s("%d", & amp;n);
printf("Please enter the number of resources:");
scanf_s("%d", & amp;m);
printf("Randomly generated process:\\
");
srand(time(NULL));
for (int i = 0;i < n;i + + ) {
for (int j = 0;j < m;j + + ) {
maxneed[i][j] = rand() % 10;
}
for (int j = 0;j < m;j + + ) {
allocation[i][j] = 10000;
while(maxneed[i][j]< allocation[i][j]) { //Ensure that the randomly generated allocated resources are less than the maximum resources. In special circumstances, the need demand vector will be all zero.
allocation[i][j] = rand() % 10;
}
}
for (int j = 0;j < m;j + + ) {
need[i][j] = maxneed[i][j] - allocation[i][j];
}
}
}
*/
void _printf() { //Output
printf("\\
The resource breakdown is as shown in the figure:\\
");
printf(" ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\
");
printf(" Process | Max | Allocation | Need |\\
");
for (int i = 0;i < n;i + + ) {
printf(" P%d ",i);
printf(" | ");
for (int j = 0;j < m;j + + ) {
printf("%d ", maxneed[i][j]);
}
printf(" | ");
for (int j = 0;j < m;j + + ) {
printf("%d ", allocation[i][j]);
}
printf(" | ");
for (int j = 0;j < m;j + + ) {
printf("%d ", need[i][j]);
}
printf(" | ");
printf("\\
");
}
printf(" ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\
");
printf("Available resources are:");
for (int i = 0;i < m;i + + ) {
printf(" %d", available[i]);
}
printf("\\
\\
");
}
void menu() {
int i,t=1;
while (t) {
printf("\\
");
printf(" Please select: \\
");
printf(" 0. Exit the system\\
");
printf(" 1. Restart the system-->Initialize\\
");
printf(" 2. Change the available resource vectorAvailable\\
");
printf(" 3. New request vector-->security algorithm\\
");
printf(" 4. Check the process data at this time\\
");
printf(" 5. Manually enter new process data\\
");
scanf("%d", & amp;i);
if (i == 0) {
t = 0;
}
if (i == 1) {
Init();
_printf();
}
if (i == 2) {
printf("Please enter available resource vector:");
for (int i = 0;i < m;i + + ) {
scanf("%d", & amp;available[i]);
temp[i] = available[i];
}
}
if (i == 3) {
if (requst()) {
printf("Request successful\\
");
}
else {
printf("Request failed\\
");
}
}
if (i == 4) {
_printf();
}
if(i==5){
_scanf();
_printf();
if (requst()) {
printf("Request successful\\
");
}
else {
printf("Request failed\\
");
}
}
if (i < 0 || i>5) {
printf("Input error, please re-enter\\
");
}
}
}
int main() {
Init();
_printf();
menu();
}
/* Test Data
5
3
7 5 3 0 1 0
3 2 2 2 0 0
9 0 2 3 0 2
2 2 2 2 1 1
4 3 3 0 0 2
3 3 2
*/
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57294 people are learning the system