1. Problem description
1.1 banker algorithm
The applicant shall state in advance the maximum demand for various resources. When dynamically applying for a certain type of resources during process activities, the system reviews whether the number of existing resources in the system can meet the maximum demand of the current process. If it can, it will be allocated, otherwise it will be rejected.
1.2 pseudo code
#Define N 5 / / number of processes
#Define m 3 / / resource type
int Available[m],Alloc[n][m],Need[n][m];
main() {
int request[m];
input( );
while (1) {
read_req( );
if (End of request) break;
(1) if (!(requesti <= Needi)) Indicates an illegal request;
(2) if (!(requesti <= Available)) be Pi Obstruction;
(3)Tentative distribution
Available=Available - Requesti;
Alloci=Alloci + Requesti;
Needi=Needi - Requesti;
(4)If the new state is safe, resources are actually allocated to Pi,Otherwise, cancel the exploratory allocation.
}
}
1.3 safety state discrimination algorithm
(1) Set Finish=(false,..., false), work = available
(2) Cycle to find the process pi that meets the following conditions, and cycle up to n times: Finish[i]=false and needI < = work
(3) If found, Finish[i]=true;work=work+Alloci; Turn (2)
(4) If Finish=(true,..., true), it is safe, otherwise it is not safe.
1.4 test data
Three types of resources m=3
Number of processes n=5
Available=(2,3,3);
The request sequence is as follows:
a) Process P2 requests resources (0, 3, 4)
b) Process P4 requests resources (1, 0, 1)
c) Process P1 requests resources (2, 0, 1)
d) Process P3 requests resources (0, 0, 2)
2. Implementation ideas
2.1 file reading
First, write the currently requested resources, maximum resource requirements and allocated resources into files. The program will read these files and process resource requests. The first number of each line of each file represents the thread, and the remaining value of each line represents the size of each resource.
2.2 tentative allocation
For each request sequence, it is first tentatively allocated to determine whether the resource request sequence can be satisfied. If yes, resources can be allocated, otherwise they cannot be allocated.
The user can input the number of sequences to be obtained, and the program will output all the request sequences that can be allocated. The process is as follows: first, an permutation is generated to represent the current resource request order. Two functions are designed to judge whether the current request is legal isLegal(int numOfReq) and whether it can meet notBlocked(int numOfReq). The parameter numOfReq represents the thread. For one of the sequences whose return value is false, resources cannot be allocated. Therefore, terminate the program, try the next request sequence and re allocate tentatively.
3. Core code
int detectiveAlloc(int permutation[]) {
order.clear();
AllocOrder.clear();
for (int i = 0; i < RESOURCE; ++i) {
Work[i] = Available[i];
}
for (int i = 0; i < PROCESS; ++i) {
for (int j = 0; j < RESOURCE; ++j) {
Alloc_[i][j] = Alloc[i][j];
Need_[i][j] = Need[i][j];
}
}
for (int i = 0; i < PROCESS; ++i) {
// Is the request legal
if (!isLegal(permutation[i])) {
printf("\n %d is illegal \n", permutation[i]);
exit(0);
}
// Is it assignable to this process
if (!notBlocked(permutation[i])) {
//if (i == 0);
break;
}
order.push_back(permutation[i]);
for (int j = 0; j < RESOURCE; ++j) {
// Work reduction
Work[j] -= Request[permutation[i]][j];
// Need reduction
Need_[permutation[i]][j] -= Request[permutation[i]][j];
// Alloc increase
Alloc_[permutation[i]][j] += Request[permutation[i]][j];
}
for (int k = 0; k < PROCESS; ++k) {
bool flag = true;
for (int j = 0; j < RESOURCE; ++j) {
// Whether resources are released
if (Need_[k][j] > Work[j]) {
flag = false;
break;
}
}
if (flag == true && std::count(AllocOrder.begin(), AllocOrder.end(), k) == 0) {
AllocOrder.push_back(k);
for (int j = 0; j < RESOURCE; ++j) {
Work[j] += Alloc_[k][j];
}
break;
}
}
}
return AllocOrder.size() == PROCESS ? 1 : 0;
}
4. Operation results
Read the file and enter the number of request sequences:
Output the qualified request sequence and the sequence of allocating resources to the sequence:
