C语言实现随机分配算法和银行家算法

1. 随机分配算法

随机分配算法是一种简单的资源分配算法，适用于资源数量较少，进程数量较多的情况。其基本思路是随机地将进程请求的资源分配给它们。

以下是一个C语言实现随机分配算法的简单示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_PROCESS 10  // 最大进程数量
#define MAX_RESOURCE 5  // 最大资源数量

int main() {
    int available[MAX_RESOURCE];  // 可用资源
    int allocation[MAX_PROCESS][MAX_RESOURCE];  // 分配矩阵
    int request[MAX_PROCESS][MAX_RESOURCE];  // 请求矩阵
    int need[MAX_PROCESS][MAX_RESOURCE];  // 需求矩阵
    int work[MAX_RESOURCE];  // 工作向量
    int finish[MAX_PROCESS] = {0};  // 完成进程标记
    int safe[MAX_PROCESS];  // 安全序列
    int num_process, num_resource, i, j, k, count = 0;

    srand(time(0));  // 设置随机种子

    // 输入进程和资源数量
    printf("Enter the number of processes: ");
    scanf("%d", &num_process);
    printf("Enter the number of resources: ");
    scanf("%d", &num_resource);

    // 输入可用资源
    printf("Enter the available resources:\n");
    for (i = 0; i < num_resource; i++) {
        printf("Resource %d: ", i + 1);
        scanf("%d", &available[i]);
    }

    // 随机生成分配矩阵和请求矩阵
    for (i = 0; i < num_process; i++) {
        for (j = 0; j < num_resource; j++) {
            allocation[i][j] = rand() % (available[j] + 1);  // 分配矩阵随机生成
            need[i][j] = rand() % (available[j] - allocation[i][j] + 1);  // 需求矩阵随机生成
            request[i][j] = rand() % (need[i][j] + 1);  // 请求矩阵随机生成
        }
    }

    // 输出分配矩阵、需求矩阵和请求矩阵
    printf("\nAllocation Matrix:\n");
    for (i = 0; i < num_process; i++) {
        for (j = 0; j < num_resource; j++) {
            printf("%d ", allocation[i][j]);
        }
        printf("\n");
    }
    printf("\nNeed Matrix:\n");
    for (i = 0; i < num_process; i++) {
        for (j = 0; j < num_resource; j++) {
            printf("%d ", need[i][j]);
        }
        printf("\n");
    }
    printf("\nRequest Matrix:\n");
    for (i = 0; i < num_process; i++) {
        for (j = 0; j < num_resource; j++) {
            printf("%d ", request[i][j]);
        }
        printf("\n");
    }

    // 初始化工作向量
    for (i = 0; i < num_resource; i++) {
        work[i] = available[i];
    }

    // 执行随机分配算法
    while (count < num_process) {
        int found = 0;
        for (i = 0; i < num_process; i++) {
            if (!finish[i]) {
                int flag = 1;
                for (j = 0; j < num_resource; j++) {
                    if (need[i][j] > work[j]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    for (j = 0; j < num_resource; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = 1;
                    safe[count++] = i;
                    found = 1;
                }
            }
        }
        if (!found) {
            printf("System is not in safe state.\n");
            exit(0);
        }
    }

    // 输出安全序列
    printf("\nSafe sequence: ");
    for (i = 0; i < num_process; i++) {
        printf("%d ", safe[i]);
    }
    printf("\n");

    return 0;
}

2. 银行家算法

银行家算法是一种避免死锁的资源分配算法，它根据系统当前的资源情况，预测将来可能需要的资源量，以此决定是否分配资源。

以下是一个C语言实现银行家算法的简单示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS 10  // 最大进程数量
#define MAX_RESOURCE 5  // 最大资源数量

void print_matrix(int matrix[][MAX_RESOURCE], int n, int m) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int available[MAX_RESOURCE];  // 可用资源
    int allocation[MAX_PROCESS][MAX_RESOURCE];  // 分配矩阵
    int request[MAX_PROCESS][MAX_RESOURCE];  // 请求矩阵
    int need[MAX_PROCESS][MAX_RESOURCE];  // 需求矩阵
    int work[MAX_RESOURCE];  // 工作向量
    int finish[MAX_PROCESS] = {0};  // 完成进程标记
    int safe[MAX_PROCESS];  // 安全序列
    int num_process, num_resource, i, j, k = 0;

    // 输入进程和资源数量
    printf("Enter the number of processes: ");
    scanf("%d", &num_process);
    printf("Enter the number of resources: ");
    scanf("%d", &num_resource);

    // 输入可用资源
    printf("Enter the available resources:\n");
    for (i = 0; i < num_resource; i++) {
        printf("Resource %d: ", i + 1);
        scanf("%d", &available[i]);
    }

    // 输入分配矩阵
    printf("Enter the allocation matrix:\n");
    for (i = 0; i < num_process; i++) {
        printf("Process %d: ", i + 1);
        for (j = 0; j < num_resource; j++) {
            scanf("%d", &allocation[i][j]);
        }
    }

    // 输入需求矩阵
    printf("Enter the need matrix:\n");
    for (i = 0; i < num_process; i++) {
        printf("Process %d: ", i + 1);
        for (j = 0; j < num_resource; j++) {
            scanf("%d", &need[i][j]);
        }
    }

    // 初始化工作向量
    for (i = 0; i < num_resource; i++) {
        work[i] = available[i];
    }

    // 执行银行家算法
    while (k < num_process) {
        int found = 0;
        for (i = 0; i < num_process; i++) {
            if (!finish[i]) {
                int flag = 1;
                for (j = 0; j < num_resource; j++) {
                    if (need[i][j] > work[j]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    for (j = 0; j < num_resource; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = 1;
                    safe[k++] = i;
                    found = 1;
                }
            }
        }
        if (!found) {
            printf("System is in deadlock state.\n");
            exit(0);
        }
    }

    // 输出安全序列
    printf("Safe sequence: ");
    for (i = 0; i < num_process; i++) {
        printf("%d ", safe[i]);
    }
    printf("\n");

    // 输入请求矩阵
    printf("Enter the request matrix:\n");
    int process_id;
    printf("Process ID: ");
    scanf("%d", &process_id);
    printf("Request: ");
    for (i = 0; i < num_resource; i++) {
        scanf("%d", &request[process_id][i]);
    }

    // 判断请求是否合法
    for (i = 0; i < num_resource; i++) {
        if (request[process_id][i] > need[process_id][i]) {
            printf("Request is invalid.\n");
            exit(0);
        }
        if (request[process_id][i] > available[i]) {
            printf("Request is invalid.\n");
            exit(0);
        }
    }

    // 尝试分配资源
    for (i = 0; i < num_resource; i++) {
        work[i] = available[i] - request[process_id][i];
        allocation[process_id][i] += request[process_id][i];
        need[process_id][i] -= request[process_id][i];
        available[i] = work[i];
    }

    // 执行银行家算法
    for (i = 0; i < num_process; i++) {
        finish[i] = 0;
    }
    k = 0;
    while (k < num_process) {
        int found = 0;
        for (i = 0; i < num_process; i++) {
            if (!finish[i]) {
                int flag = 1;
                for (j = 0; j < num_resource; j++) {
                    if (need[i][j] > work[j]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    for (j = 0; j < num_resource; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = 1;
                    safe[k++] = i;
                    found = 1;
                }
            }
        }
        if (!found) {
            printf("System is in deadlock state.\n");
            exit(0);
        }
    }

    // 输出安全序列
    printf("Safe sequence: ");
    for (i = 0; i < num_process; i++) {
        printf("%d ", safe[i]);
    }
    printf("\n");

    return 0;
}