Banker Algorithm
Resource download (documents, codes, etc.): https://download.csdn.net/download/fufuyfu/85511576?spm=1001.2014.3001.5503
1, Experiment content
Banker algorithm is used to avoid deadlock, realize the rational allocation of resources, and deepen the understanding of process synchronization and deadlock.
2, Experimental requirements
1. Suppose that the system has three kinds of resources A (10), B (15) and C (12), and five processes execute concurrently. The process scheduling adopts the time slice rotation scheduling algorithm.
2. Each process is represented by a process control block (PCB), which can contain the following information: process name, total required resources, allocated resources, and process status.
3. The process is automatically generated by the program (including the required data, and pay attention to the reasonable range of data).
4. During the process of running, a process will randomly request resources (randomly generate the number of requested resources). If the maximum demand is reached, it means that the process can be completed; If the maximum demand is not reached, schedule other processes to run after running a time slice. Banker algorithm is used to avoid deadlock in resource allocation.
5. The status of each process can be one of ready W (Wait), running R (Run), blocking B (Block), or completed F (Finish).
6. For each scheduling, the program will output the running results: the running process, the process in the ready queue, the process in the blocking queue, the completed process and the PCB of each process for inspection.
3, Algorithm flow
3.1 header file and data structure
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIME_SLICE 2
// Process status: ready to wait for blocking to complete
enum process_type{
process_type_wait = 'W',
process_type_run = 'R',
process_type_block = 'B',
process_type_finish = 'F'
};
typedef struct PCB{
// Process name
char name;
// Maximum required resources
int Max[100];
// Number of additional resources required
int Need[100];
// Number of resources allocated
int Allocate[100];
// Process elapsed time
int run_time;
// Process status
char state;
// Point to next process
PCB *next;
}PCB;
// Name of system resource
char Name[100]={0};
// System available resource vector
int Available[100];
// Process request resource vector
int Request[100];
// Available resources of storage system
int Work[100];
// Whether the marking system has enough resources allocated to each process
bool Finish[100];
// Store safety sequence
char Security[100];
// Maximum number of processes
int M = 100;
// Maximum number of resources
int N = 100;
// Flag output
bool flag = true;
// Function declaration // Initialization data void init(PCB *list); // Create process void create_process(PCB *list); // Display resource allocation and process operation void print(PCB *list); // Tentative allocation of resources void test(PCB *list); // Tentative resource allocation void void Retest(PCB *list); // Try to score application resources by banker algorithm bool bank(PCB *list); // Security algorithm bool safe(PCB *list); // Time slice rotation scheduling algorithm void round_robin(PCB *list);
3.2 main function
// Main function
int main(){
printf("-----------------------------------------------------------------------\n");
printf("|| Implementation of banker algorithm ||\n");
printf("-----------------------------------------------------------------------\n\n");
PCB *list = (PCB *)malloc(sizeof(PCB));
if(list == NULL){
printf("Dynamic memory allocation failed!");
}
list->next = NULL;
srand((int)time(NULL));
// Initialization data
init(list);
// Display resource allocation and process operation
printf("***********************************************************************\n");
print(list);
// Banker algorithm is used to determine whether the system is safe at the current time. If it is not safe, resources will no longer be allocated
if(!safe(list)) {
exit(0);
}
printf("\n***********************************************************************\n");
// Process scheduling using time slice rotation method
round_robin(list);
}
3.3 initialization data
// Initialization data
void init(PCB *list){
// m is the number of processes, n is the type of system resources
int m,n;
// Initialize the number of system resource types and resources
printf("The types of resources available to the system are:");
scanf("%d",&n);
// The number of system resource types, which is assigned to the global variable N to facilitate subsequent methods
N = n;
// Resource name
char name;
// Number of resources
int number;
for(int i = 1;i <= n;i++){
printf("\t resources%d Name of:",i);
getchar();
scanf("%c",&name);
Name[i] = name;
printf("\t resources%c The initial number of is:",name);
scanf("%d",&number);
Available[i] = number;
}
// The number of initialization processes and the maximum number of resources required by each process
printf("\n Please enter the number of processes:");
scanf("%d",&m);
// The number of processes, assigned to the global variable M, is convenient for subsequent methods
M = m;
create_process(list);
}
3.4 create process
// Create process
void create_process(PCB *list){
// Count allocated system resources
int temp[100] = {0};
int number = 1;
while(number <= M){
// Process node
PCB *p = (PCB *)malloc(sizeof(PCB));
if(p == NULL){
printf("Dynamic memory allocation failed!");
}
// Process name
printf("\t Please enter page%d Process name of the process:",number);
getchar();
scanf("%c",&p->name);
// Flag variable
bool flag;
// Initialize the maximum number of resources required, the number of resources still required, and the number of allocated resources for each process
do{
flag = false;
for(int i = 1;i <= N;i++){
p->Max[i] = rand()%10;
if(p->Max[i] > Available[i]){
flag = true;
// printf("the maximum resource demand is greater than the maximum number of resources in the system, please re-enter! \n");
break;
}
p->Need[i] = p->Max[i];
p->Allocate[i] = 0;
}
}while(flag);
// Process elapsed time
p->run_time = 0;
// Process status
p->state = process_type_wait;
// Point to next process
p->next = NULL;
if(list->next == NULL){
list->next = p;
}else{
PCB *move = list->next;
while(move->next != NULL){
move = move->next;
}
move->next = p;
}
number++;
}
printf("\n");
}
3.5 display resource allocation and process operation
// Display resource allocation and process operation
void print(PCB *list){
printf("\n Resources currently available in the system(Available):\n");
for(int i = 1;i <= N;i++){
printf("%c ",Name[i]);
}
printf("\n");
for(int i = 1;i <= N;i++){
printf("%d ",Available[i]);
}
printf("\n\n");
printf("The current resource allocation and process operation of the system are as follows:\n");
printf(" Max Allocate Need\n");
printf("Process name ");
//Output the resource name that goes with the process name, corresponding to Max, Allocate and Need respectively
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= N;j++){
printf("%c ",Name[j]);
}
printf(" ");
}
printf("Run time process status\n");
// Traverse linked list
PCB *p = list->next;
while(p != NULL){
//Output Max, Allocation and Need of each process
printf(" %c\t",p->name);
for(int j = 1;j <= N;j++)
printf("%d ",p->Max[j]);
printf(" ");
for(int j = 1;j <= N;j++)
printf("%d ",p->Allocate[j]);
printf(" ");
for(int j = 1;j <= N;j++)
printf("%d ",p->Need[j]);
printf(" ");
printf(" %d\t ",p->run_time);
printf("%c\n",p->state);
p = p->next;
}
}
3.6 tentative allocation of resources
// Tentative allocation of resources
void test(PCB *list){
// Process requesting resources
PCB *p = list->next;
// Change process information
for(int i = 1;i <= N;i++){
Available[i] -= Request[i];
p->Allocate[i] += Request[i];
p->Need[i] -= Request[i];
}
}
3.7 cancellation of tentatively allocated resources
// Tentative resource allocation void
void Retest(PCB *list){
// Process requesting resources
PCB *p = list->next;
// Contrary to test operation
for(int i = 1;i <= N;i++){
Available[i] += Request[i];
p->Allocate[i] -= Request[i];
p->Need[i] += Request[i];
}
}
3.8 trial scoring of application resources by banker algorithm
// Try to score application resources by banker algorithm
bool bank(PCB *list){
PCB *p = list->next;
// Randomly generate request vector
for(int i = 1;i <= N;++i){
Request[i] = rand()%(p->Need[i]+1);
}
// The number of randomly generated request resources is 0, indicating that they are ignored
int n = 0;
for(int i = 1;i <= N;++i){
if(Request[i] == 0){
n++;
}
}
if(n == N){
flag = false;
return false;
}
printf("\n%c Process request—— ",p->name);
for(int i = 1;i <= N;i++){
printf("resources%c: ",Name[i]);
printf("%d ",Request[i]);
}
printf("\n\n");
// Locate the required resource array subscript
int num = 1;
// Judge whether the first two conditions of banker algorithm are true
for(int i = 1;i <= N;++i){
// Judge whether the application is greater than the demand. If it is greater than the demand, an error will occur
if(Request[i] > p->Need[i]){
printf("%c The process requested more resources than it needed\n",p->name);
printf("Unreasonable distribution, no distribution!\n");
return false;
}else{
// Judge whether the application is greater than the current allocable resources. If it is greater than, an error will occur
if(Request[i] > Available[i]){
printf("%c The resources requested by the process are greater than the resources currently available to the system\n",p->name);
printf("The system does not have enough resources and will not be allocated!\n");
return false;
}
}
}
// If the first two conditions are true, try to allocate resources and find a safe sequence
// Try to allocate resources according to the process demand
test(list);
// Judge whether the system is safe
if(!safe(list)){
Retest(list);
return false;
}
return true;
}
3.9 security algorithm
// Security algorithm
bool safe(PCB *list){
// Count the number of incomplete processes
int m = 0;
PCB *move = list->next;
while(move != NULL && move->state != process_type_finish){
move = move->next;
++m;
}
// Initialize Work array
for(int i = 1;i <= N;i++){
Work[i] = Available[i];
}
// Initialize Finish array
for(int i = 1;i <= M;i++){
if(i <= m){
Finish[i] = false;
}else{
Finish[i] = true;
}
}
// Node location to judge the process running
int pnum = 1,apply;
int num = 1;
// Secure sequence
PCB *p = list->next;
while(p != NULL && pnum <= m){
apply = 0;
for(int i = 1;i <= N;i++){
// The current process is incomplete and various resources are less than or equal to the number of system resources
if(Finish[pnum] == false && p->Need[i] <= Work[i]){
apply++;
// Allocation is not allowed until the required number of resources of each type is less than the available resources of the system
if(apply == N){
for(int x = 1;x <= N;x++){
// Update current system allocable resources
Work[x] += p->Allocate[x];
}
// Update tag array
Finish[pnum] = true;
// Update safe sequence array
Security[num++] = p->name;
// Ensure that each query starts from the first process
pnum = 0;
p = list;
}
}
}
// Query next process
pnum++;
p = p->next;
}
for(int i = 1;i <= M;i++){
if(Finish[i] == false){
// The system is in an unsafe state
printf("The system is unsafe!\n");
return false;
}
}
// If safe, output safe sequence
printf("The system is safe!\n");
printf("There is a security sequence:");
for(int i = 1;i <= m;i++){
// Output process run order array
printf(" %c ",Security[i]);
if(i < m){
printf("->");
}
}
printf("\n");
return true;
}
3.10 time slice rotation scheduling algorithm
// Time slice rotation scheduling algorithm
void round_robin(PCB *list){
// Record the position of the first node
PCB *index = list->next;
while (index != NULL && index->state != process_type_finish) {
// Judge whether to output after scheduling
flag = true;
// System security, processes allocated to resources and running
if(bank(list)){
// Update elapsed time
index->run_time += TIME_SLICE;
// Determine whether the process is completed
int num = 0;
for(int i = 1;i <= N;++i){
if(index->Max[i] == index->Allocate[i]){
num++;
}
}
// The process is complete
if (num == N) {
// Modify process status
index->state = process_type_finish;
// Reclaim allocated resources
for(int i = 1;i <= N;i++){
Available[i] += index->Allocate[i];
}
printf("%c Process complete\n",index->name);
}else{
// The process is not completed, enter and wait
index->state = process_type_wait;
}
// Current process completed
if (index->state == process_type_finish){
// Adjust the completed process to the end of the completed queue
// 1. the header pointer points to the next node of the initial node
list->next = index->next;
// 2. traverse the entire linked list and insert it to the end of the completed queue
PCB *p = list;
while (p->next != NULL) {
p = p->next;
}
p->next = index;
index->next = NULL;
} else {
// Current process not completed
// 1. the header pointer points to the next node of the initial node
list->next = index->next;
// 2. traverse the entire linked list and insert it into the end of the waiting queue (followed by the completed queue)
PCB *p = list;
// 2.1 finding the insertion position
while (p->next != NULL && p->next->state != process_type_finish) {
p = p->next;
}
// 2.2 determining the insertion position
if (p->next == NULL) {
// the last one
p->next = index;
p->next->next = NULL;
}else{
// Not the last one, there are still nodes after it
index->next = p->next;
p->next = index;
}
}
}else{
// The resource allocation requested by this process will lead to unsafe system or unreasonable resource request
// Block and adjust the process to the middle of the waiting queue and the completed queue, and it is the last one in the blocking queue
index->state = process_type_block;
// The current process is incomplete and blocked
// 1. the header pointer points to the next node of the initial node
list->next = index->next;
// 2. traverse the entire linked list and insert it into the last block queue after the unfinished queue
PCB *p = list;
// 2.1 finding the insertion position
while (p->next != NULL && p->next->state != process_type_finish) {
p = p->next;
}
// 2.2 determining the insertion position
if (p->next == NULL) {
// the last one
p->next = index;
p->next->next = NULL;
}else{
// Not the last one, there are still nodes after it
index->next = p->next;
p->next = index;
}
}
// Show current queue status
if(list->next->state != process_type_finish){
list->next->state = process_type_run;
}
if(flag){
print(list);
printf("\n***********************************************************************\n");
}
index = list->next;
}
}
4, Experimental results (screenshot):
The code comments are very detailed and can be run by yourself. The screenshot of the experiment can be run by yourself
5, Analysis:
In this experiment, the time slice round robin scheduling algorithm is used to schedule multiple randomly generated processes. The banker algorithm first checks the legitimacy of the resource requests proposed by the processes, that is, to check whether the requests are not greater than what the processes need or the system can use. If the request is legal, trial allocation will be conducted. Finally, the security of the state call security algorithm after the trial allocation is checked. If the system is safe, that is, there is a safe execution sequence. As long as the system allocates all the resources required by the process according to this process sequence, each process can be successfully executed. If not, it will not be allocated, restore the original state, and reject the application. In this way, when the system is allocating resources, the system can not enter an unsafe state and can well avoid deadlock.
The code written in this experiment is redundant, and it can be optimized by modifying the data structure used. For example, the maximum required resource array Max, the required resource array Need and the allocated resource array Allocate in the PCB structure are replaced with three structure pointers, that is, a resource structure is established, which contains various resource variables of the system, and the three structure pointers point to this structure, This is a good way to optimize the code, but it also has a small drawback, that is, the number of resource types cannot be entered manually. It needs to be set in the code in advance. When the number of resource types needs to be changed, the source code needs to be changed, which is not very consistent with the OOP principle (open to extension and closed to modification). Therefore, it is not used in this experiment, but if there is a way to optimize the data structure again to solve this problem, the data structure is a better choice.