银行家算法-求所有安全序列
使用DFS（深度优先搜索）遍历求出所有的安全序列。
数据结构
先上头文件说明，实现此算法用到的数据结构和命名。
#ifndef _DATA_STRUCTURE
#define _DATA_STRUCTURE
// 表示资源个数
#define M (4)
// 表示进程个数
#define N (4)
// 当前状态还剩多少可用的资源
struct AvailableD;
// 每个进程对每个资源的最大需求量
struct MaxD;
// 当前分配个每个进程的资源数目
struct AllocationD;
// 每个进程还需要多少资源数目（最大需求 - 当前分配）
struct NeedD;
// 当前状态每个进程请求的资源数量
struct RequestD;
// 存放安全序列的数据结构（名字叫 Queue 实际上是栈的实现【FILO先进后出】）
struct QueueD;
// 表明每个进程是否在安全序列中
struct StatusD;
typedef struct AvailableD *Available;
typedef struct MaxD *Max;
typedef struct AllocationD *Allocation;
typedef struct NeedD *Need;
typedef struct RequestD *Request;
typedef struct QueueD *Queue;
typedef struct StatusD *Status;
Available create_available();
Allocation create_allocation();
Max create_max();
Need create_need();
Queue create_queue();
int queue_full(Queue queue);
int queue_empty(Queue queue);
void queue_add(Queue queue, int data);
int queue_get(Queue queue);
void queue_display(Queue queue);
Status create_status();
void display_need(Need need);
/* 更新 need 数组 */
void update_need(Need need, Allocation allocation, Max max);
/* 将 allocation 矩阵的 第 row 行的值加(减)到 available 里 */
void update_available(Allocation allocation, int row, Available available, int is_add);
/* 检查 available 是否满足 need 的第 row 行的需求 */
void check_available(Allocation allocation, Need need, Available available, int row, Queue queue, Status status);
#endif
算法步骤
首先检查当前剩余的资源数目是否满足某个进程的需求量，也就是说判断 Available 向量中每一个资源数目是否大于等于 Need 矩阵中某一个进程的需求量；
如果对于进程 row ，对每个资源数目的需求量小于当前可用的系统资源；首先检查当前进程是否已经在安全序列中，若存在就判断下一个进程；
若当前进程 row 还没有处在安全序列，就开始深度优先搜索：将当前进程 row 已经分配到的系统资源数目加到当前可用的资源数目中，即 Allocation 矩阵中第 row 行的所有数目加到 Available 向量中；然后将当前进程 row 添加到安全序列中（此安全序列是一个栈）；递归调用搜索的函数，向下一个进程开始搜索；
在搜索的过程中需要判断所有的进程是否已经添加到安全序列中，即查看安全序列（栈）的大小是否等于当前系统的进程数目；若达到了就将安全序列输出并且开始回溯；此判断应该放在深度优先搜索函数的前面，用来作为递归出口；
然后将最近加入到安全序列中的进程从安全队列中删除，即从栈中弹出一个元素，记为 row；然后修改此进程row未加在安全序列中的状态；将此进程row收回的资源数目归还，即从 Available 向量中减去 Allocation 矩阵中第 row 行的数目；然后向下一个进程搜索。
核心代码
/**
* allocation: Allocation 每个进程已经分配的资源数目的矩阵
* need: Need 每个进程还需的资源数目的矩阵
* available: Available 剩余资源数的矩阵
* row: 表示从哪个进程开始向下扫描
* queue: 已加入安全序列的进程（栈性质）
* status: 表示每个进程是否已经存在于安全序列
* */
void check_available(Allocation allocation, Need need, Available available, int row, Queue queue, Status status)
{
int temp = row;
int i;
int flag = 1;
// 递归出口
if (queue->length == 4)
{
printf("Safe sequence: ");
queue_display(queue);
return;
}
do
{
for (i = 0; i < M; i++)
{
if (available->vector[i] < need->matrix[row][i])
{
flag = 0;
break;
}
}
if (flag)
{
if (status->vector[row] == 1)
{
row = (row + 1) % N;
continue;
}
// 深搜准备
update_available(allocation, row, available, 1);
queue_add(queue, row);
status->vector[row] = 1;
check_available(allocation, need, available, (row + 1) % N, queue, status);
// 回溯 恢复刚才的状态
status->vector[row] = 0;
queue_get(queue);
update_available(allocation, row, available, 0);
//temp = row;
row = (row + 1) % N;
}
else
{
row = (row + 1) % N;
flag = 1;
}
} while (temp != row);
}
所有代码
#include <stdio.h>
#include <stdlib.h>
#include "datastructure.h"
// 长度为 m 的一维数组
// 表示还有多少可用资源
struct AvailableD
{
int m;
int *vector;
};
// 长度为 m*n 的矩阵
// 表示各进程对资源的最大需求数
struct MaxD
{
int m;
int n;
int **matrix;
};
// 长度为 m*n 的矩阵
// 表示已经给各进程分配了多少资源
struct AllocationD
{
int m;
int n;
int **matrix;
};
// 长度为 m*n 的矩阵
// 表示各进程最多还需要多少资源
struct NeedD
{
int m;
int n;
int **matrix;
};
// 长度为 m 的一维数组
// 表示进程此次申请的各种资源
struct RequestD
{
int m;
int *vector;
};
// 长度为 n 的一维数组
// 具有栈的性质的安全序列
struct QueueD
{
int n;
int *vector;
int length;
int front;
};
// 长度为 n 的一维数组
// 表示某个进程是否已经在安全序列的标志
struct StatusD
{
int *vector;
};
// 创建 Allocation 矩阵，数据手动输入
Allocation create_allocation()
{
int i, j;
Allocation allocation = (Allocation)malloc(sizeof(struct AllocationD));
allocation->m = M;
allocation->n = N;
allocation->matrix = (int **)malloc(sizeof(int *) * N);
for (i = 0; i < M; i++)
{
allocation->matrix[i] = (int *)malloc(sizeof(int) * M);
}
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
scanf("%d", &(allocation->matrix[i][j]));
}
}
return allocation;
}
// 创建 Max 矩阵，数据手动输入
Max create_max()
{
int i, j;
Max max = (Max)malloc(sizeof(struct MaxD));
max->m = M;
max->n = N;
max->matrix = (int **)malloc(sizeof(int *) * N);
for (i = 0; i < M; i++)
{
max->matrix[i] = (int *)malloc(sizeof(int) * M);
}
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
scanf("%d", &(max->matrix[i][j]));
}
}
return max;
}
// 创建 Need 矩阵，数据手动输入
Need create_need()
{
int i, j;
Need need = (Need)malloc(sizeof(struct NeedD));
need->m = M;
need->n = N;
need->matrix = (int **)malloc(sizeof(int *) * N);
for (i = 0; i < M; i++)
{
need->matrix[i] = (int *)malloc(sizeof(int) * M);
}
return need;
}
// 根据 Allocation 和 Max 矩阵计算 Need 矩阵
void update_need(Need need, Allocation allocation, Max max)
{
int i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
need->matrix[i][j] = max->matrix[i][j] - allocation->matrix[i][j];
}
}
}
// 创建 Available 一维数组，数据手动输入
Available create_available()
{
int i;
Available available = (Available)malloc(sizeof(struct AvailableD));
available->m = M;
available->vector = (int *)malloc(sizeof(int) * M);
for (i = 0; i < M; i++)
{
scanf("%d", &(available->vector[i]));
}
return available;
}
// 将 Allocation 矩阵的第 row 行的资源数目加（减）到 Available 数组中
// is_add: 为 1 时加；反之为减
void update_available(Allocation allocation, int row, Available available, int is_add)
{
int i = 0;
for (i = 0; i < N; i++)
{
if (is_add)
{
available->vector[i] += allocation->matrix[row][i];
}
else
{
available->vector[i] -= allocation->matrix[row][i];
}
}
}
// 创建一个安全“队列”（栈实现）
Queue create_queue()
{
int i;
Queue queue = (Queue)malloc(sizeof(struct QueueD));
queue->n = N;
queue->vector = (int *)malloc(sizeof(int) * N);
queue->length = 0;
queue->front = -1;
return queue;
}
// 判断是否为满
int queue_full(Queue queue)
{
return queue->length == queue->n;
}
// 判断是否为空
int queue_empty(Queue queue)
{
return queue->length == 0;
}
// 向安全“队列”（栈）中添加一个数据项
void queue_add(Queue queue, int data)
{
if (queue_full(queue))
{
printf("Queue has been fulled!\n");
return;
}
queue->front++;
queue->vector[queue->front] = data;
queue->length++;
}
// 从安全“队列”（栈）获得（弹出）一个数据项（栈顶）
int queue_get(Queue queue)
{
int result;
if (queue_empty(queue))
{
printf("Queue is empty!\n");
return -1;
}
result = queue->vector[queue->front];
queue->front--;
queue->length--;
return result;
}
// 创建状态数组
Status create_status()
{
int i;
Status status = (Status)malloc(sizeof(struct StatusD));
status->vector = (int *)malloc(sizeof(int) * N);
for (i = 0; i < N; i++)
{
status->vector[i] = 0;
}
return status;
}
// 打印输出安全“队列”（栈）中的所有数据项
void queue_display(Queue queue)
{
int i;
for (i = 0; i < queue->length; i++)
{
printf("P%d\t", queue->vector[i]);
}
printf("\n");
}
// 输出 Need 矩阵
void display_need(Need need)
{
int i, j;
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
printf("%d ", need->matrix[i][j]);
}
printf("\n");
}
}
/**
* allocation: Allocation 每个进程已经分配的资源数目的矩阵
* need: Need 每个进程还需的资源数目的矩阵
* available: Available 剩余资源数的矩阵
* row: 表示从哪个进程开始向下扫描
* queue: 已加入安全序列的进程（栈性质）
* status: 表示每个进程是否已经存在于安全序列
* */
void check_available(Allocation allocation, Need need, Available available, int row, Queue queue, Status status)
{
int temp = row;
int i;
int flag = 1;
if (queue->length == 4)
{
printf("Safe sequence: ");
queue_display(queue);
return;
}
do
{
for (i = 0; i < M; i++)
{
if (available->vector[i] < need->matrix[row][i])
{
flag = 0;
break;
}
}
if (flag)
{
if (status->vector[row] == 1)
{
row = (row + 1) % N;
continue;
}
// 深搜准备
update_available(allocation, row, available, 1);
queue_add(queue, row);
status->vector[row] = 1;
check_available(allocation, need, available, (row + 1) % N, queue, status);
// 回溯 恢复刚才的状态
status->vector[row] = 0;
queue_get(queue);
update_available(allocation, row, available, 0);
//temp = row;
row = (row + 1) % N;
}
else
{
row = (row + 1) % N;
flag = 1;
}
} while (temp != row);
}
int main()
{
// 数据的声明、创建
Available available;
Allocation allocation;
Max max;
Need need = create_need();
Queue queue = create_queue();
Status status = create_status();
// 手动输入数据
printf("Input available: \n");
available = create_available();
printf("Input allocation: \n");
allocation = create_allocation();
printf("Input Max: \n");
max = create_max();
// 计算 Need 矩阵
update_need(need, allocation, max);
printf("Need: \n");
display_need(need);
// 深度优先搜索 开始遍历所有安全序列
printf("\nAll the safa sequence:\n\n");
check_available(allocation, need, available, 0, queue, status);
printf("\n");
system("pause");
return 0;
}