This is the first day of my participation in the August Challenge. For details, see:August is more challenging
Recently xiaobian in the process of learning to test the operating system, understand a process can avoid deadlock algorithm —– banker algorithm
If you already know what a banker’s algorithm is and just want to look at the code, go straight to the source section
What is a banker’s algorithm
Banker algorithm is an algorithm to avoid deadlock in the operating system
What is a deadlock
Similar to our thread deadlock, different threads hold each other’s lock, and multiple threads cannot release the lock, that is, a deadlock
Like the figure above, P1 claims an output device, but the output device is owned by P2, which in turn claims an input device, which in turn is owned by P1
How to avoid it?
And simply check whether the current system is in a secure state before resource allocation, whether it can be allocated, and whether the system is still safe after allocation
Algorithm is the core
For example: Suppose A system with A, B, C three kinds of resources, class A total of 10 resources as an example, class B five resources as an example, the C class A total of seven resources as an example, the existing five process (P1, P2, P3, P4, P5, they are the biggest demand for all kinds of resources and the first – ~ time distribution has possession of resources as shown.
At this time, we need to find a process that can directly meet the allocation requirements. It can be seen that process P2 can directly meet the requirements. When P2 meets the requirements, all resources held by P2 are released, as shown in the figure.
And then P4, and by the same logic, P4
And then we have P5, and then we have the same distribution
P1
All the way down to P3
So the safe sequences are: P2, P4, P5, P1, P3
The source code
#include <iostream>
#include <string>
#include<random>
using namespace std;
// The suffix Test is marked as the Test value
const int ResMaxSize = 20;// The maximum number of resources allowed
const int ProMaxSize = 10;// Maximum number of processes allowed
string ResName[ResMaxSize]; / / resource name
string ResNameTest[4] = { "R1"."R2"."R3"."R4" }; // Test data
int Max[ProMaxSize][ResMaxSize]; // Maximum demand for various resources per process
int MaxTest[ProMaxSize][ResMaxSize] = { {0.0.1.2}, {2.7.5.0}, {6.6.5.6}, {4.3.5.6}, {0.6.5.2}};// Test data
int Allocation[ProMaxSize][ResMaxSize]; // The number of resources each process has acquired for each resource in the system
int AllocationTest[ProMaxSize][ResMaxSize] = { {0.0.1.2}, {2.0.0.0}, {0.0.3.4}, {2.3.5.4}, {0.3.3.2}};// Test data
int Available[ResMaxSize]; // The number of different types of resources still available to the system
int AvailableTest[ResMaxSize] = { 2.1.0.0 }; // Test data
int Need[ProMaxSize][ResMaxSize]; // The number of resources required for each process
int Security[ProMaxSize]; // Process safety sequence, can also use STL queue
int SNum = 0;
// The process completes the queue
bool ProFinish[ProMaxSize];
int ProNum; // Actual number of processes
int ProNumTest = 5; // Test data
int ResNum; // Actual number of resources
int ResNumTest = 4; // Test data
// Work that needs to be done
void BankerInit(a);// Initial Settings: input functions
void PrintSecurity(a);// Output the safety sequence
void OutPut(a);// Output function
bool CheckRequest(int Pid, const int Request[]);// Banker algorithm core, judge request algorithm
bool CheckSafe(a);// Security check algorithm
bool TryCheckSafe(a);// Security check algorithm
void InitPost(a);
class Utils{
public:
static vector<string> split(const string &s, const string &seperator);
static int splitVar(const string &s, string delim,int param[] = {});
static bool allisNum(string str);
};
vector<string> Utils::split(const string &s, const string &seperator){
vector<string> result;
typedef string::size_type string_size;
string_size i = 0;
while(i ! = s.size()) {// Find the first letter in the string that is not equal to the delimiter;
int flag = 0;
while(i ! = s.size() && flag == 0){
flag = 1;
for(string_size x = 0; x < seperator.size(a); ++x)if(s[i] == seperator[x]){
++i;
flag = 0;
break; }}// Find another delimiter and fetch the string between the two delimiters;
flag = 0;
string_size j = i;
while(j ! = s.size() && flag == 0) {for(string_size x = 0; x < seperator.size(a); ++x)if(s[j] == seperator[x]){
flag = 1;
break;
}
if(flag == 0)
++j;
}
if(i ! = j){ result.push_back(s.substr(i, j-i)); i = j; }}return result;
}
int Utils::splitVar(const string &s, string delim, int param[]) {
vector<string> input;
input = Utils::split(s, delim);
for (int i = 0; i < input.size(a); i++) { param[i] =atoi(input[i].c_str());
}
return input.size(a); }bool Utils::allisNum(string str)
{
for (int i = 0; i < str.size(a); i++) {int tmp = (int)str[i];
if (tmp >= 48 && tmp <= 57)
{
continue;
}
else
{
return false; }}return true;
}
// Input function implementation
void BankerInit(a)
{// You can set the values directly here
ProNum = ProNumTest; // Set the actual number of processes
ResNum = ResNumTest; // Set the actual number of processing resources
for (int i = 0; i < ResNum; i++)// Set the resource name
ResName[i] = ResNameTest[i];
// Set the maximum resource requirements for each process
for (int i = 0; i < ProNum; i++)
for (int j = 0; j < ResNum; j++)
Max[i][j] = MaxTest[i][j];
// Set the number of resources each process has obtained
for (int i = 0; i < ProNum; i++)
for (int j = 0; j < ResNum; j++)
Allocation[i][j] = AllocationTest[i][j];
// Set the remaining number of available system resources
for (int i = 0; i < ResNum; i++)
Available[i] = AvailableTest[i];
// Calculate the number of resources each process still needs: the Need array
for (int i = 0; i < ProNum; i++)
for (int j = 0; j < ResNum; j++)
Need[i][j] = Max[i][j] - Allocation[i][j];
}
// Output the safety sequence
void PrintSecurity(a)
{
/ /...
cout << "------------- Security sequence -------------" << endl;
for (int i = 0; i < SNum; ++i) {
cout << Security[i] << "\t";
}
cout << endl;
}
// Output function
void OutPut(a)
{
cout << "= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =" << endl;
cout << "Number of current processes :" << ProNum << "; Number of current resource types :" << ResNum << endl;
for (int i = 0; i < ResNum; i++)
cout << "Resources" << ResName[i] << "Available quantity is:" << Available[i] << endl;
cout << "-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --" << endl;
for (int i = 0; i < ProNum; i++)
{
cout << "Process" << i << "\t" <<(ProFinish[i] ? "Complete" : "Unfinished") << endl;
for (int j = 0; j < ResNum; j++)
cout << "Resources" << ResName[j] << "The maximum quantity required is:" << Max[i][j] << "Currently allocated quantity is:" << Allocation[i][j] << "The remaining demand quantity is:" << Need[i][j] << endl;
}
cout << "= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =" << endl;
}
// Banker algorithm core, judge request algorithm
bool CheckRequest(int Pid,const int Request[])
{
// Check whether the resource request is valid
for (int i = 0; i < ResNum; i++)
{
if (Request[i] > Need[Pid][i])// The number of required resources has exceeded the maximum available value
{
/ /...
cout << "Resources." << ResName[i] << "The number of requests has exceeded the maximum available on the system." << endl;
return false;
}
if (Request[i] > Available[i])// There are not enough resources
{
cout << "Resources." << ResName[i] << "There are not enough resources." << endl;
return false; }}// Data rollback point after failed allocation
int AllocationTemp[ProNum][ResNum];
int NeedTemp[ProNum][ResNum];
int AvailableTemp[ResNum];
int SecurityTemp[ProNum];
bool ProFinishTemp[ProNum];
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
AllocationTemp[i][j] = Allocation[i][j];
NeedTemp[i][j] = Need[i][j];
}
SecurityTemp[i] = Security[i];
ProFinishTemp[i] = ProFinish[i];
AvailableTemp[i] = Available[i];
}
// Try to allocate resources to the process to see if the system is safe after this allocation
for (int i = 0; i < ResNum; i++)
{
/ /...
Allocation[Pid][i] += Request[i];
Available[i] -= Request[i];
Need[Pid][i] = Max[Pid][i] - Allocation[Pid][i];
}
// Data rollback point after successful allocation
int AllocationSuccessTemp[ProNum][ResNum];
int NeedSuccessTemp[ProNum][ResNum];
bool ProFinishSuccessTemp[ProNum];
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
AllocationSuccessTemp[i][j] = Allocation[i][j];
NeedSuccessTemp[i][j] = Need[i][j];
}
ProFinishSuccessTemp[i] = ProFinish[i];
}
InitPost(a);// OutPut();
if (TryCheckSafe())// Check whether the system is safe after allocation
{
// After the allocation system security, formal allocation
cout << "This resource is allocated to the process" << Pid << ", distribution success!" << endl;
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
if (Pid == i) {
Allocation[Pid][j] = 0;
} else{
Allocation[i][j] = AllocationSuccessTemp[i][j];
}
Need[i][j] = NeedSuccessTemp[i][j];
}
if (Pid == i) {
ProFinish[Pid] = true;
} else{ ProFinish[i] = ProFinishSuccessTemp[i]; }}OutPut(a);return true;
}
else {// After the allocation is unsafe, the allocation fails, and the resource recovers
cout << "The system is not secure after this resource allocation. The allocation is invalid." << std::endl;
// Restore resources
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
Allocation[i][j] = AllocationTemp[i][j];
Need[i][j] = NeedTemp[i][j];
}
Security[i] = SecurityTemp[i];
ProFinish[i] = ProFinishTemp[i];
Available[i] = AvailableTemp[i];
}
OutPut(a);return false; }}bool CheckSafe(a){
// Backup data
int AllocationTemp[ProNum][ResNum];
int NeedTemp[ProNum][ResNum];
bool ProFinishTemp[ProNum];
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
AllocationTemp[i][j] = Allocation[i][j];
NeedTemp[i][j] = Need[i][j];
}
ProFinishTemp[i] = ProFinish[i];
}
bool b= TryCheckSafe(a);// Restore resources
for (int i = 0; i < ProNum; ++i) {
for (int j = 0; j < ResNum; ++j) {
Allocation[i][j] = AllocationTemp[i][j];
Need[i][j] = NeedTemp[i][j];
}
ProFinish[i] = ProFinishTemp[i];
}
return b;
}
void InitPost(a){
for (int i = 0; i < ProNum; ++i) {
int j;
for (j = 0; j < ResNum; ++j) {
if(Need[i][j] ! =0) {
break; }}if (j == ResNum) {
// Resources have been allocated and need to be released
cout << "Process." << i << "\t" << "It has been allocated." << endl;
for (j = 0; j < ResNum; ++j) {
Available[j] += Allocation[i][j];
Allocation[i][j] = 0;
}
ProFinish[i] = true; }}}// The security algorithm
bool TryCheckSafe(a)
{
int Work[ResNum];// represents the number of various resources that the system can provide for the process to continue running
// Initialize the Work and Finish arrays
for (int i = 0; i < ResNum; i++) {
Work[i] = Available[i];
}
SNum = 0;// Reset the safe sequence queue
cout << "TryCheckSafe" << endl;
while (true)
{
int i;
// Check whether everything is safe
for (i = 0; i < ProNum; i++)
if(! ProFinish[i])break;
// If all are in safe state, then the system is also in safe state
if (i == ProNum)
{
// cout << "The system is safe now!" << endl;
return true;
}
// I
for (i = 0; i < ProNum; i++)
{
if(! ProFinish[i])// If the current process has not finished executing
{
// Try to allocate resources to the process and check if they are sufficient
int j;
for (j = 0; j < ResNum; ++j) {
if (Need[i][j] > Work[j]) {
break; }}bool flag = j == ResNum;
if (flag)// The I process has enough resources to allocate
{
cout << "Execution process" << i << ", the system can use resources to update" << endl;
// Add the process to the security sequence
Security[SNum] = i;
SNum++;
// Call the process to run, and release the resources occupied by the process, output the update of the available resources
for (int k = 0; k < ResNum; ++k) {
Need[i][k] = 0;
Work[k] += Allocation[i][k];
Allocation[i][k] = 0;
ProFinish[i] = true;
}
// cout << "after the call to the next round to find the security process" << endl;
// OutPut();
// cout << "==================" << endl;
break; // After the call, go to the next round to find the security process}}}// If the process has traversed all and no one is executed, then it is not safe to allocate
if (i == ProNum)
{
// cout << "The system is not secure at this time!" << endl;
return false; }}}/ / = = = = = = = = = = = = = = = = = = = = = = = = = = = = = the main function = = = = = = = = = = = = = = = = = = = = = = =
int main(a)
{
int choice = 0;
BankerInit(a);// Banker algorithm initialization
InitPost(a);while (true)
{
cout << "================ Banker algorithm ================" << endl;
cout << "------------1. Determine the current system status ------------" << endl;
cout << "------------2. Apply for resources --------------------" << endl;
cout << "------------3. Output resource --------------------" << endl;
cout << "-- -- -- -- -- -- -- -- -- -- -- -- 9. Quit -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --" << endl;
cout << "= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =" << endl;
string inputVar;
cin >> inputVar;
bool isNum = Utils::allisNum(inputVar);
if(! isNum) { cout <<"Input error" << endl;
continue;
}
choice = atoi(inputVar.c_str());
switch (choice) {
case 1:
{
if (CheckSafe())
{
cout << "The system is now secure!" << endl;
PrintSecurity(a); }else
{
cout << "The system is not secure at this time! << endl;
}
break;
}
case 2:
{
int Pid;
int Request[ResNum];
cout << "Please enter the process number that initiated the request :" << endl;
cin >> Pid; // Test data: 2
if (Pid > ProNum) {
cout << "Process number wrong :" << endl;
break;
}
string dataVar;
cout << "Please enter the number of requested resources :" << endl;
cin >> dataVar;
Utils::splitVar(dataVar, ",", Request);
bool flag = true;
for (int i = 0; i < ResNum && flag; i++) // Test data: 0 1 0 0 0
{
if (Need[Pid][i] < Request[i]) {
cout << ResName[i] << "=> Exceed maximum resource number :" << Request[i] << endl;
flag = false;
continue;
}
if (Available[i] < Request[i]) {
cout << ResName[i] << "=> The number of available resources exceeds :" << Request[i] << endl;
flag = false;
continue; }}if(! flag) {break;
}
cout << "Application resources are as follows :";
for (int i = 0; i < ResNum; i++) // Test data: 0 1 0 0 0
{
cout << Request[i] << "\t";
}
cout << endl;
if (CheckRequest(Pid, Request))
{
cout << "Resource allocation successful, the system is now secure!" << endl;
PrintSecurity(a); }else
{
cout << "Resource allocation failed, the system is not secure at this time!" << endl;
}
break;
}
case 3:
OutPut(a);break;
case 9:
return 0;// End the program
default:
cout << "Please enter the correct option" << endl;
continue; }}return 0;
}
Copy the code