1. Experimental Purpose
~~~ Write and debug a simulated deadlock-prevention banker scheduling algorithm program to improve understanding of deadlock-prevention banker scheduling algorithms.
II. EXPERIMENTAL CONTENTS
- Debug and run the banker dispatch algorithm and give the results.
- Find the security sequence.
- Apply for Resource Allocation
3. Ideas for implementation
- Variable initialization, receiving user input m (number of processes), n (number of resources), Max (maximum number of resources required by the process), Allocation (number of resources occupied by the process), Need (number of resources required by the process), Available (resources available to the system);
- Determine whether the current state is safe or not according to the banker's algorithm. When a process first requests a resource, test the process's maximum demand for the resource. If the system's existing resources can meet its maximum demand, allocate the resource according to the current demand. Otherwise, postpone the allocation until all processes satisfy the resource allocation, which is considered safe, gives a safe sequence, and is not secure.Give all tips;
- If it is safe, prompt the user to enter the resource request Request(R1,..., Rm;
- Receive the user to enter the process number and the number of resources that need to be allocated to apply for resource allocation, determine if the number of resources is less than Need and Available, or fail to apply for resource allocation if it is not satisfied
- According to the banker's algorithm to determine whether the current state is safe or not, security gives a security sequence and prompts whether to apply for resource allocation again. If not, the request for resource allocation fails or no new request exits.
4. Major data structures
- The resource vector Available can be used.This is an array of m elements, each of which represents the number of a class of available resources. Its initial value is the number of all available resources of that class configured in the system, and its value changes dynamically with the allocation and recycling of such resources.If Available[j]=K, it represents K existing Rj class resources in the system.
- Maximum Requirement Matrix Max.This is an n*m matrix that defines the maximum demand for M-class resources for each process in n processes in the system.If Max[i,j]=K, the maximum number of Rj class resources required by process I is K.
- Allocation matrix A llocation.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, then the number of Rj-class resources currently shared by process I is K.
- Requirement matrix Need.This is also an n*m matrix representing the number of resources needed for each process.If Need[i,j]=K, this means that process I also needs K R j class resources to complete its tasks.
5. Algorithmic flowchart
6. Operations and Testing (System Operations Screenshot)
7. Summary
Through this experiment, we have written and debugged a deadlock prevention banker dispatching algorithm program, mastered how to find a safe sequence and apply for the allocation of resources to meet the requirements, and have a better understanding of the system's resource dispatching, at the same time, we have improved our programming and logic capabilities, and obtained very large gains.
8. Code Appendix
#include <stdio.h>
//Banker algorithm implementation
int Max[100][100]; //Process Maximum Requirement Resources
int Available[100]; //System Available Resources
int Allocation[100][100]; //Process already accounts for resource allocation
int Need[100][100]; //Processes also require resources (Maximum Required Resources minus Required Resources)
int Request[100][100]; //Process Request Resources
int Finish[100];//Storage Satisfaction Status (1 storage for a process if it meets all types of resource requirements less than system available resources)
int p[100];//Store Secure Sequence Process Number
int m, n; //m processes, n resources
//Check Resource Allocation Security Algorithms
int isSafe()
{
int i, j;
int a = 0;
int Work[100]; //Available resources array
for (i = 0; i < n; i++)
Work[i] = Available[i];
for (i = 0; i < m; i++)
Finish[i] = 0;//Initialization process satisfies condition state
for (i = 0; i < m; i++) {
if (Finish[i] == 1)
continue;
else
{
for (j = 0; j < n; j++)
{
if (Need[i][j] > Work[j])//Determine if each species requires more resources than is available
break;
}
if (j == n)//Determine that each species requires less resources than available resources
{
Finish[i] = 1;
for (int k = 0; k < n; k++)
Work[k] += Allocation[i][k];//Release resources from the Available Resource Recycling Process
p[a++] = i;//Store corresponding process number as subsequent output security sequence number
i = -1;//At the end of the loop, i++ then iterates through again to find the allocated resources for Finish=0 until all processes Finish=1
}
else continue;
}
}
if (a == m) {
printf("The system is secure\n");
printf("The system security sequence is:\n");
for (i = 0; i < a; i++) {
printf("%d", p[i]);
if (i != a - 1)
printf("-->");
}
printf("\n");
return 1;
}
else {
printf("The system is not secure, there is no security sequence!");
return 0;
}
}
// Request Resource Input Function
void apply() {
int i, j, k, fl = 0;
while (1) {
printf("Enter the process number of the resource you want to request: (the first process number is 0, the second process number is 1, and so on)\n");
scanf("%d", &k);
printf("Enter the number of individual resources requested by the process\n");//Apply for resources on the basis of occupied resources
for (i = 0; i < n; i++)
scanf("%d", &Request[k][i]);
while (1) {
for (i = 0; i < n; i++) {
if (Request[k][i] > Need[k][i])
{
printf("The number of resources requested exceeds the requirements of the process!\n");
printf("Re-enter the number of resources the process needs to request:\n");
for (i = 0; i < n; i++)
scanf("%d", &Request[k][i]);
break;
}
}
for (i = 0; i < n; i++) {
if (Request[k][i] > Available[i])
{
printf("The number of requested resources exceeds all the resources in the system!\n");
printf("Re-enter the number of resources the process needs to request:\n");
for (i = 0; i < n; i++)
scanf("%d", &Request[k][i]);
break;
}
}
break;
}
for (i = 0; i < n; i++)
{
Available[i] -= Request[k][i];
Allocation[k][i] += Request[k][i];
Need[k][i] -= Request[k][i];
}
printf("The process is now occupying the resource matrix:\n");
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", Allocation[i][j]);
}
printf("\n");
}
printf("The process also needs the resource matrix at this time:\n");
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", Need[i][j]);
}
printf("\n");
}
printf("At this point, the system can use resources:\n");
for (i = 0; i < n; i++)
printf("%d ", Available[i]);
printf("\n");
if (isSafe())
printf("Agree to Assignment Request\n");
else
{
printf("Disagree Assignment Request\n");
for (i = 0; i < n; i++)
{
Available[i] += Request[k][i];
Allocation[k][i] -= Request[k][i];
Need[k][i] += Request[k][i];
}
}
for (i = 0; i < m; i++)
Finish[i] = 0;
char Flag;
printf("Do you want to request allocation again?Yes, please press Y，No, press N\n");
while (1)
{
getchar();
scanf("%c", &Flag);
if (Flag == 'Y' || Flag == 'N') {
break;
}
else
{
printf("Please re-enter as required:\n");
continue;
}
}
if (Flag == 'Y')
continue;
else break;
}
}
int main()
{
int i, j, k;
char flag;
printf("****************************Banker Scheduling Algorithm**************************************\n");
printf("Number of input processes:\n");
scanf("%d", &m);
printf("Types of input resources:\n");
scanf("%d", &n);
printf("Enter the maximum number of resources required for each process,according to%d*%d Matrix Input\n", m, n);
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
scanf("%d", &Max[i][j]);
printf("Enter the number of resources each process has consumed,according to%d*%d Matrix Input\n", m, n);
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &Allocation[i][j]);
Need[i][j] = Max[i][j] - Allocation[i][j];//Calculate the number of additional resources the process needs to allocate
if (Need[i][j] < 0)
{
printf("The number you entered%d Process owned by%d Errors in resources, please re-enter the correct resources in this location:\n", i + 1, j + 1);
j--;
continue;
}
}
}
printf("The process also needs the resource matrix at this time:\n");
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", Need[i][j]);
}
printf("\n");
}
printf("Please enter the number of resources available for each type of system:\n");
for (i = 0; i < n; i++)
scanf("%d", &Available[i]);
if (isSafe()) {
printf("Do you need to specify a process to apply for resource allocation?Yes, please press Y，No, press N\n");
while (1)
{
getchar();
scanf("%c", &flag);
if (flag == 'Y' || flag == 'N') {
break;
}
else {
printf("Please re-enter as required:\n");
continue;
}
}
if (flag == 'Y') {
apply();
}
}
else {
return 0;
}
return 0;
}