I. Demand analysis

1. Tasks and objectives of programming

Through this experiment, we can deepen the understanding of process deadlocks, and further master the allocation of process resources, deadlock detection and security sequence generation method.

2. Input form and input value range

Number of processes n, type of resources m, resource allocation of each process at time T0 (input can be run, can also be set in the program)

3. The form of output

If a secure process sequence is displayed, a message is displayed indicating that the process sequence is secure.

4. The functions that the program can achieve

The program simulates the working process of the banker algorithm to prevent process deadlocks. Suppose the system has n processes P1… ,Pn, there are m types of allocated resources R1… Rm, at time T0, the j resources allocated by process Pi are Allocationij, and it also needs J resources. Currently, there are Workj resources remaining in the system. Now the banker algorithm is used to allocate process resources to prevent deadlock.

5, test data, including correct input and output results and contains error input and output results

Correct use cases

The input

Enter the maximum allowed quantity of resource 1 of process 1 Max[1] : 7 Enter the maximum allowed quantity of resource 2 of process 1 Max[2] : 5 Enter the maximum allowed quantity of resource 3 of process 1 Max[3] : 3 Input the allocated amount of resource 1 for process 1 [1] : 0 Input the allocated amount of resource 2 for process 1 [2] : 1 Input the allocated amount of resource 3 for process 1 [3] : 0 Input the maximum allowed quantity of resource 1 in process 2 Max[1] : 3 Input the maximum allowed quantity of resource 2 in process 2 Max[2] : 2 Input the maximum allowed quantity of resource 3 in process 2 Max[3] : 2 Input the allocated quantity of resource 1 in process 2 [1] : 2 Input the allocated quantity of resource 2 in process 2. Allocation[2] : 0 Input the allocated quantity of resource 3 in process 2. Allocation[3] : 0 Input the maximum allowed quantity of resource 1 in process 3. Max[1] : 9 Input the maximum allowed quantity of resource 2 in process 3. 0 Input the maximum amount of resource 3 in process 3 Max[3] : 2 Input the allocated amount of resource 1 in process 3 [1] : 3 Input the allocated amount of resource 2 in process 3 [2] : 0 Input the allocated amount of resource 3 in process 3. Allocation[3] : 2 Input the maximum allowed amount of resource 1 in process 4. Max[1] : 2 Input the maximum allowed amount of resource 2 in process 4. 2 Please input the allocated quantity of resource 1 of process 4 to be allocated [1] : 2 Please input the allocated quantity of resource 2 of process 4 to be allocated [2] : 1 Please input the allocated quantity of resource 3 of process 4 to be allocated [3] : 1 Input the maximum allowed quantity of resource 1 of process 5 Max[1] : 4 Input the maximum allowed quantity of resource 2 of process 5 Max[2] : 3 Input the maximum allowed quantity of resource 3 of process 5 Max[3] : 3 Input the allocated quantity of resource 1 of process 5 [1] : 0 Input the allocated amount of resource 2 for process 5 Allocation[2] : 0 Input the allocated amount of resource 3 for process 5 Allocation[3] : 2 Input the available amount of resource 1:3 Input the available amount of resource 2:3 Input the available amount of resource 3:2Copy the code

The output

SafeOrder: Process 2 Process 4 Process 5 Process 1 Process 3 The remaining resources are as follows: Resource 1 Remaining quantity: 3 Resource 2 Remaining quantity: 3 Resource 3 Remaining quantity: 2 Check whether there are new requests. If yes, enter the process id. If no, enter 0. 2 Enter resource 1 required by process 2. 1 Enter resource 2 required by process 2. 0 Enter resource 3 required by process 2. 2 Remaining quantity of resource 2:3 Remaining quantity of resource 3:0Copy the code

Wrong use case (negative input affects correct results)

The input

N: 1 Type of resource M: 3 Maximum allowed quantity of resource 1 of process 1 Max[1] : 1 Maximum allowed quantity of resource 2 of process 1 Max[2] : 1 Maximum allowed quantity of resource 3 of process 1 Max[3] : 1 please enter the process of resource Allocation number of allocated 1 [1] : 1 please enter the number of allocated resources process 1 2 Allocation [2] : 1-1 please enter process of the number of allocated resources 3 Allocation [3] : 1, please input the number of available resources available 1: 2 Enter the number of available resources 2:2 Enter the number of available resources 3:2Copy the code

The output

SafeOrder: The remaining resources of process 1 are as follows: Resource 1 Remaining quantity: 2 Resource 2 Remaining quantity: 2 Resource 3 Remaining quantity: 2 Check whether there are new requests. If yes, enter the process id. If no, enter 0. 1 Enter the quantity of resource 1 required by process 1. 2 Enter the quantity of resource 2 required by process 1. 2 Enter the quantity of resource 3 required by process 1Copy the code

Second, outline design

Definition of abstract data types

int n;// Number of processes n
int m;// Resource type m
int Available[MaxNumber];// The number of available resources
int Request[MaxNumber];// Number of resources requested by the process
int SafeOrder[MaxNumber];// Security process sequence

// Define the data structure of the process
typedef struct {
    int Max[MaxNumber];
    int Allocation[MaxNumber];
    int Need[MaxNumber];
    bool Finished;// Complete state
} Progress;
Copy the code

2. The flow of the main program

int main(a) {
    BankerAlgorithm bankerAlgorithm{};
    bankerAlgorithm.Input();
    bankerAlgorithm.Order(bankerAlgorithm.progress, bankerAlgorithm.Available);

    return 0;
}
Copy the code

3. Hierarchical (call) relationship between each program module

int main(a) {
    BankerAlgorithm bankerAlgorithm{};
    bankerAlgorithm.Input();
    bankerAlgorithm.Order(bankerAlgorithm.progress, bankerAlgorithm.Available);

    return 0;
}

// The InputAlgorithm function is called to select the input function
void Input(a) {...}// Perform security process detection and output security sequence
void Order(Progress pg[MaxNumber], int a[MaxNumber]) {
    // Define the subscript
    int orderNum = 0;

    // Copy process operations
    Progress progressCopy[MaxNumber];
    for (int i = 1; i <= n; i++) {
        progressCopy[i] = pg[i];
    }

    // Copy the number of available requirements
    int available[MaxNumber];
    for (int i = 1; i <= m; i++) {
        available[i] = a[i];
    }

    // Call NewFinish to determine whether all processes are complete
    while(! NewFinish(progressCopy)) {// call the IsSafe function to determine if it IsSafe now
        if (IsSafe(progressCopy, available)) {
            for (int i = 1; i <= n; i++) {
                if(! progressCopy[i].Finished &&// Call the IsExecutable function to determine whether the process can satisfy the allotable resources
                    IsExecutable(progressCopy[i], available)) {
                    // Allocate only if both incomplete and assignable requirements of the process are satisfied...}}}else {
            cout << "Unsafe" << endl;
            exit(0); }}/ / output SafeOrder... NewRequest (pg, a); }// Determine whether there is a new request, if there is no exit, if there is a request to enter the number of resources
void NewRequest(Progress pg[MaxNumber], int a[MaxNumber]) {...// Output the number of remaining resources...// Determine the new request, if there are new requests available, call the Order function to re-perform the banker algorithm security calculation
    cout << endl << "Is there a new request? If yes, enter the process number. If no, enter 0:";
    cin >> newRequest;
    if(newRequest ! =0) {
        for (int i = 1; i <= m; i++) {
			// If the allocatable resource is insufficient or exceeds the requirement, the NewRequest function is called again
            NewRequest(pg, a);
        }
    	···
        Order(pg, a);
    } else {
        return; }}// Determine whether all processes are complete
bool NewFinish(Progress pg[MaxNumber]) {...}// Determine if allocatable resources can satisfy the process
bool IsExecutable(Progress pg, const int a[MaxNumber]) {...}// Determine if it is safe now
bool IsSafe(Progress pg[MaxNumber], int a[MaxNumber]) {...}Copy the code

Third, detailed design

Implement the specific algorithm of the program module

1, Order banker algorithm sort

// Perform security process detection and output security sequence
void Order(Progress pg[MaxNumber], int a[MaxNumber]) {
    // Define the subscript
    int orderNum = 0;

    // Copy process operations...// Copy the number of available requirements...// Call NewFinish to determine whether all processes are complete
    while(! NewFinish(progressCopy)) {// call the IsSafe function to determine if it IsSafe now
        if (IsSafe(progressCopy, available)) {
            for (int i = 1; i <= n; i++) {
                if(! progressCopy[i].Finished &&// Call the IsExecutable function to determine whether the process can satisfy the allotable resources
                    IsExecutable(progressCopy[i], available)) {
                    // Allocate only if both incomplete and assignable requirements of the process are satisfied...}}}else {
            cout << "Unsafe" << endl;
            exit(0); }}/ / output SafeOrder...// If the state is secure, call NewRequest again to request the next requirement input
    NewRequest(pg, a);
}
Copy the code

2. NewRequest initiates a NewRequest

// Determine whether there is a new request, if there is no exit, if there is a request to enter the number of resources
void NewRequest(Progress pg[MaxNumber], int a[MaxNumber]) {...// Output the number of remaining resources...// Determine the new request, if there are new requests available, call the Order function to re-perform the banker algorithm security calculation
    cout << endl << "Is there a new request? If yes, enter the process number. If no, enter 0:";
    cin >> newRequest;
    if(newRequest ! =0) {
        for (int i = 1; i <= m; i++) {
			// If the allocatable resource is insufficient or exceeds the requirement, the NewRequest function is called again
            NewRequest(pg, a);
        }
    	···
        Order(pg, a);
    } else {
        return; }}Copy the code

3. The NewFinish function determines that the process is complete

// Determine whether all processes are complete
bool NewFinish(Progress pg[MaxNumber]) {
    bool finished = true;
    for (int i = 1; i <= n; i++) {
        finished *= pg[i].Finished;
    }
    return finished;
}
Copy the code

The IsExecutable function determines whether resources are sufficient or not

// Determine if allocatable resources can satisfy the process
bool IsExecutable(Progress pg, const int a[MaxNumber]) {
    bool isExecutable = true;
    for (int i = 1; i <= m; i++) {
        isExecutable *= (pg.Need[i] <= a[i]);
    }
    return isExecutable;
}
Copy the code

5. The IsSafe function checks whether the current process IsSafe

// Determine if it is safe now
bool IsSafe(Progress pg[MaxNumber], int a[MaxNumber]) {
    bool isExecutable = false;
    for (int i = 1; i <= n; i++) {
        if (IsExecutable(pg[i], a)) {
            isExecutable = true;
            returnisExecutable; }}return isExecutable;
}
Copy the code

Four, debugging analysis

Problems encountered in the debugging process and solutions, design and implementation review and analysis

The performance analysis of the algorithm (including the time complexity and space complexity analysis of basic operations and other algorithms) and its improvement idea

Performance analysis

Improve vision

The output is more complicated, more inconvenient to test, can be read file input instead

5. User instructions

Directions for use

• The console will prompt the user to enter, as prompted to enter the content
• Do not enter negative values, which will affect the correct results
• When the selection algorithm input is complete, the secure process sequence is output
• You can choose whether to use additional resource requests or exit as required

6. Test results

Test results, both input and output

D:\Documents\MyCourse\OperatingSystem\cmake-build-debug\chapter03.exe Please enter the number of processes n: 5 Please enter the type of resource M: 3 Please enter the maximum allowed number of resource 1 of process 1 Max[1] : 7 Input the maximum amount of resource 2 for process 1 Max[2] : 5 Input the maximum amount of resource 3 for process 1 Max[3] : 3 Input the allocated amount of resource 1 for process 1 Allocation[1] : 0 Input the allocated amount of resource 2 for process 1 Allocation[2] : 1 Set the maximum amount of resource 1 in process 2. Max[1] : 3 Set the maximum amount of resource 2 in process 2. Max[2] : 2 Set the maximum amount of resource 3 in process 2. 2 Please input the allocated quantity of resource 1 of process 2 as Allocation[1] : 2 Please input the allocated quantity of resource 2 of process 2 as Allocation[2] : 0 Please input the allocated quantity of resource 3 of process 2 as Allocation[3] : 0 Input the maximum allowed quantity of resource 1 in process 3 Max[1] : 9 Input the maximum allowed quantity of resource 2 in process 3 Max[2] : 0 Input the maximum allowed quantity of resource 3 in process 3 Max[3] : 2 Input the allocated quantity of resource 1 in process 3 [1] : 3 Input the allocated quantity of resource 2 in process 3. Allocation[2] : 0 Input the allocated quantity of resource 3 in process 3. Allocation[3] : 2 Input the maximum allowed quantity of resource 1 in process 4. 2 Input the maximum allowed quantity of resource 3 for process 4 Max[3] : 2 Input the allocated quantity of resource 1 for process 4 [1] : 2 Input the allocated quantity of resource 2 for process 4 [2] : 1 Set the maximum allowed quantity of resource 1 for process 5. Max[1] : 4 Set the maximum allowed quantity of resource 2 for process 5. Max[2] : 3 Set the maximum allowed quantity of resource 3 for process 5. 3 Input the allocated quantity of resource 1 for process 5. [1] : 0 Input the allocated quantity of resource 2 for process 5. [2] : 0 Input the allocated quantity of resource 3 for process 5. [3] : 2 Input the available quantity of resource 1. 3 Enter the available quantity of resource 2:3 Enter the available quantity of resource 3:2 SafeOrder: Process 2 Process 4 Process 5 Process 1 Process 3 Remaining quantity of resource 1:3 Remaining quantity of resource 2:3 Remaining quantity of resource 3: If no, enter 0:2 Number of resource 1 required by process 2 :1 Number of resource 2 required by process 2 :0 Number of resource 3 required by process 2 :2 SafeOrder: Process 2 Process 4 Process 5 Process 1 Process 3 The remaining resources are as follows: Resource 1 Remaining quantity: 2 Resource 2 Remaining quantity: 3 Resource 3 Remaining quantity: 0 Check whether new requests exist. If yes, enter the process id. If no, enter 0. If the number of resources required by process 4 exceeds the number of resources required by process 4, re-enter the number of resources available. If the number of resources required by process 4 exceeds the number of resources required by process 4, re-enter the number of resources available. If the number of resources required by process 4 exceeds the number of resources required by process 4, re-enter the number of resources available. 5 Enter resource 1 required by Process 5 :1 Resource 2 required by Process 5 :3 Resource 3 required by Process 5 :0 Unsafe Process finished with exit code 0Copy the code

Seven, the appendix

Annotated source programs

#include <iostream>
#include <iomanip>

using namespace std;
#define MaxNumber 100

class BankerAlgorithm {
public:

    int n;// Number of processes n
    int m;// Resource type m
    int Available[MaxNumber];// The number of available resources
    int Request[MaxNumber];// Number of resources requested by the process
    int SafeOrder[MaxNumber];// Security process sequence

    // Define the data structure of the process
    typedef struct {
        int Max[MaxNumber];
        int Allocation[MaxNumber];
        int Need[MaxNumber];
        bool Finished;// Complete state
    } Progress;

    Progress progress[MaxNumber];

    // Enter the number of processes, type of resources, and the number of Max, Allocation, and needs of resources related to each process
    void Input(a) {
        cout << "Please enter the number of processes n:";
        cin >> n;
        cout << "Please enter resource type m:";
        cin >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << "Please enter the process" << i << "Resources" << j << "Maximum allowable quantity Max[" << j << "]：";
                cin >> progress[i].Max[j];
            }
            for (int j = 1; j <= m; j++) {
                cout << "Please enter the process" << i << "Resources" << j << "Allocation of allocated quantity [" << j << "]：";
                cin >> progress[i].Allocation[j];
            }
            for (int j = 1; j <= m; j++) { progress[i].Need[j] = progress[i].Max[j] - progress[i].Allocation[j]; }}for (int i = 1; i <= m; i++) {
            cout << "Please enter available resources" << i << "Available quantity:";
            cin >> Available[i];
        }

        cout << endl;
    }

    // Determine whether there is a new request, if there is no exit, if there is a request to enter the number of resources
    void NewRequest(Progress pg[MaxNumber], int a[MaxNumber]) {
        int newRequest;

        // The number of remaining resources is referenced
        cout << endl << endl << "The remaining resources are as follows:" << endl;
        for (int i = 1; i <= m; i++) {
            cout << setw(6) < <"Resources" << setw(2) << i << setw(6) < <"Remaining quantity:" << setw(2) << a[i] << endl;
        }

        // Determine the new request
        cout << endl << "Is there a new request? If yes, enter the process number. If no, enter 0:";
        cin >> newRequest;
        if(newRequest ! =0) {
            for (int i = 1; i <= m; i++) {
                cout << "Please enter the process" << newRequest << "Required resources" << i << "Quantity :";
                cin >> Request[i];
                if (Request[i] > a[i]) {
                    cout << "Insufficient allocatable resources, please re-enter" << endl;
                    NewRequest(pg, a);
                }
                if (Request[i] > pg[newRequest].Need[i]) {
                    cout << "Out of demand, please re-enter" << endl; NewRequest(pg, a); }}for (int i = 1; i <= m; i++) {
                a[i] -= Request[i];
                pg[newRequest].Allocation[i] += Request[i];
                pg[newRequest].Need[i] -= Request[i];
            }
            Order(pg, a);
        } else {
            return; }}void Order(Progress pg[MaxNumber], int a[MaxNumber]) {
        // Define the subscript
        int orderNum = 0;

        // Copy process operations
        Progress progressCopy[MaxNumber];
        for (int i = 1; i <= n; i++) {
            progressCopy[i] = pg[i];
        }

        // Copy the number of available requirements
        int available[MaxNumber];
        for (int i = 1; i <= m; i++) {
            available[i] = a[i];
        }

        while(! NewFinish(progressCopy)) {/ / if any
            if (IsSafe(progressCopy, available)) {
                for (int i = 1; i <= n; i++) {
                    if(! progressCopy[i].Finished && IsExecutable(progressCopy[i], available)) {// Allocate only if both incomplete and assignable requirements of the process are satisfied
                        progressCopy[i].Finished = true;
                        for (int j = 1; j <= m; j++) { available[j] += progressCopy[i].Allocation[j]; } SafeOrder[++orderNum] = i; }}}else {
                cout << "Unsafe" << endl;
                exit(0); }}/ / output SafeOrder
        cout << "SafeOrder for.";
        for (int i = 1; i <= n; i++) {
            cout << setw(12) < <"Process" << setw(4) << SafeOrder[i];
        }

        NewRequest(pg, a);
    }

    // Determine whether all processes are complete
    bool NewFinish(Progress pg[MaxNumber]) {
        bool finished = true;
        for (int i = 1; i <= n; i++) {
            finished *= pg[i].Finished;
        }
        return finished;
    }

    // Determine if allocatable resources can satisfy the process
    bool IsExecutable(Progress pg, const int a[MaxNumber]) {
        bool isExecutable = true;
        for (int i = 1; i <= m; i++) {
            isExecutable *= (pg.Need[i] <= a[i]);
        }
        return isExecutable;
    }

    // Determine if it is safe now
    bool IsSafe(Progress pg[MaxNumber], int a[MaxNumber]) {
        bool isExecutable = false;
        for (int i = 1; i <= n; i++) {
            if (IsExecutable(pg[i], a)) {
                isExecutable = true;
                returnisExecutable; }}returnisExecutable; }};int main(a) {
    BankerAlgorithm bankerAlgorithm{};
    bankerAlgorithm.Input();
    bankerAlgorithm.Order(bankerAlgorithm.progress, bankerAlgorithm.Available);

    return 0;
}
Copy the code