C语言实现 操作系统 银行家算法
2024-10-18 21:37:59
/****************************************************
银行家算法
算法思想：
1. 在多个进程中，挑选资源需求最小的进程Pmin。
可能存在多类资源，这时暂取第一类资源作为基准 2. 验证剩余的资源是否能满足进程Pmin各类资源的最大资源需求，
若满足。意味着进程可以执行完毕。最后释放占有着的资源。此时回收Pmin占有的资源，
将此进程标志为FINISH,并唤醒那些等待的进程（实际就是改变等待进程的状态标志）
若不满足，表明资源不够，将此进程标志为WAIT 3. 循环整个过程，当检測到进程所有为FINISH时，表明是安全状态
检測到所有的进程为WAIT时。表明可能死锁了，是一个非安全状态 林育彬 2014/10/17
*****************************************************/ #include <stdio.h>
#include <malloc.h>
#include <string.h> // 安全状态标志
#define TRUE 0
#define FALSE -1 // 进程状态标志
#define FINISH 1
#define READY 0
#define WAIT -1 // 为了在函数调用的时候，降低參数的个数，这里将声明一些变量为全局变量
int *Available = NULL; // 剩余资源可用数量
int *Max = NULL; // 每一个进程最大的需求量
int *Allocation = NULL; // 每一个进程已经分配的资源数
int *Need = NULL; // 每一个进程还须要的资源数
int *SafeList = NULL; // 存储一个安全序列 int initData(const int pCount, const int rCount)
{
int i = 0; Available = (int*)malloc(rCount * sizeof(int));
Max = (int*)malloc(rCount*pCount * sizeof(int));
Allocation = (int*)malloc(rCount*pCount * sizeof(int));
Need = (int*)malloc(rCount*pCount * sizeof(int));
SafeList = (int*)malloc((pCount+1) * sizeof(int)); // SafeList[0] 作为一个安全标志位 if (Available == NULL || Max == NULL || Allocation == NULL
|| Need == NULL || SafeList == NULL)
{
printf("out of space\n");
return FALSE;
} SafeList[0] = 0; // 初始化，表明不存在安全序列 // 最大需求量
for(i=0; i<rCount*pCount; ++i)
{
scanf("%d", &Max[i]);
} // 已分配资源数量
for(i=0; i<rCount*pCount; ++i)
{
scanf("%d", &Allocation[i]);
} // 剩余资源量
for(i=0; i<rCount; ++i)
{
scanf("%d", &Available[i]);
} // 计算需求数
for(i=0; i<rCount*pCount; ++i)
{
Need[i] = Max[i] - Allocation[i];
} return TRUE;
} // 測试此时的进程状态
int testStatus(const int pCount, const int rCount)
{
int pMin = 0; // 最小需求进程ID
int pWait = 0; // 等待进程数
int pFinish = 0; // 完毕进程数
int p = 0;
int r = 0;
int posList = 1; // 安全序列下标 int *pStatus = (int*)malloc(pCount * sizeof(int)); // 进程的标志状态
int *pAvai_cpy = (int*)malloc(rCount * sizeof(int)); // Available 的一份拷贝。避免破坏数据
int *safeList_tmp = (int*)malloc((pCount+1) * sizeof(int)); if (pStatus == NULL || pAvai_cpy == NULL || safeList_tmp == NULL)
{
printf("out of space\n");
return FALSE;
} // 初始化所有的进程为就绪状态
memset(pStatus, READY, pCount * sizeof(int));
// 拷贝 Available
memcpy(pAvai_cpy, Available, rCount * sizeof(int)); while(pFinish != pCount && pWait != pCount)
{ // 以第一类资源为基准，挑选资源需求最小的进程
int needMin = -1;
pMin = 0;
for (p=0; p<pCount; ++p)
{
if (pStatus[p] != READY)
continue; if (needMin == -1 || Need[p*rCount + 0] < needMin) // 第一类需求资源, needMin == -1 初次取值
{
needMin = Need[p*rCount + 0];
pMin = p; }
} // 验证剩余资源是否能满足最小资源进程的需求
for (r=0; r<rCount; ++r)
{
if (Need[pMin*rCount + r]> pAvai_cpy[r])
{
// 满足不了
break;
}
} if (r == rCount)
{
// 添加到安全序列中
safeList_tmp[posList++] = pMin+1; // 满足各类资源需求
pStatus[pMin] = FINISH;
pFinish++; // 回收资源
for (r=0; r<rCount; ++r)
{
pAvai_cpy[r] += Allocation[pMin*rCount + r];
} // 唤醒等待的进程
for (p=0; p<pCount; ++p)
{
if (pStatus[p] == WAIT)
{
pStatus[p] = READY;
pWait--;
}
}
}
else
{
// 表明无法满足，进程等待
pStatus[pMin] = WAIT;
pWait++;
}
} free(pStatus);
free(pAvai_cpy); // 验证状态
if (pFinish == pCount)
{
// 更新安全序列
safeList_tmp[0] = 1; // 安全标志位置1。表明存在安全序列
memcpy(SafeList, safeList_tmp, (pCount+1) * sizeof(int) );
free(safeList_tmp); return TRUE;
}
else
{
free(safeList_tmp);
return FALSE;
}
} void showSafeList(const int pCount)
{
if (SafeList != NULL)
{
int i = 0;
if (SafeList[i] != 1)
{
printf("不存在安全序列\n");
}
else
{
++i;
printf("安全序列：");
while(i <= pCount)
{
printf("p%d ", SafeList[i++]);
}
printf("\n");
}
}
else
{
printf("不存在安全序列\n");
} } // 測试资源请求，假设满足，则分配，不满足，则不分配资源 modify 2014/11/2
int request(const int pId, const int pCount, const int rCount, const int *reqList)
{
int *Avai_cpy = (int*)malloc(rCount * sizeof(int));
int *pId_Allo = (int*)malloc(rCount * sizeof(int)); // 保存当前进程的一条分配情况,
int *pId_Need = (int*)malloc(rCount * sizeof(int)); // 保存当前进程的一条需求情况 int r = 0;
const int locate = pId*rCount; // 定位到进程的位置 if (Avai_cpy == NULL || pId_Allo == NULL || pId_Need == NULL)
{
printf("out of space\n");
return FALSE;
} // 做数据备份
for(r=0; r<rCount; ++r)
{
pId_Allo[r] = Allocation[locate + r];
pId_Need[r] = Need[locate + r];
Avai_cpy[r] = Available[r];
} // 资源分配
for (r=0; r<rCount; ++r)
{
if (reqList[r] > Available[r])
{
return FALSE;
} Allocation[locate + r] += reqList[r];
Available[r] -= reqList[r];
Need[locate + r] -= reqList[r];
} // test
if (testStatus(pCount, rCount) != TRUE)
{
// 分配之后处于非安全状态，数据还原
for(r=0; r<rCount; ++r)
{
Allocation[locate + r] = pId_Allo[r];
Need[locate + r] = pId_Need[r];
Available[r] = Avai_cpy[r];
} free(Avai_cpy);
free(pId_Allo);
free(pId_Need);
Avai_cpy = pId_Allo = pId_Need = NULL; return FALSE;
}
else
{
// 成功分配 free(Avai_cpy);
free(pId_Allo);
free(pId_Need);
Avai_cpy = pId_Allo = pId_Need = NULL; return TRUE;
} return TRUE;
} // 清理空间
void destory()
{
if (Available != NULL)
{
free(Available);
} if (Max != NULL)
{
free(Max);
} if (Allocation != NULL)
{
free(Allocation);
} if (Need != NULL)
{
free(Need);
} if (SafeList != NULL)
{
free(SafeList);
} Available = NULL;
Max = NULL;
Allocation = NULL;
Need = NULL;
SafeList = NULL; //printf("destory\n"); } int main()
{
int rCount = 0;
int pCount = 0; // request
int pId = 2;
int reqList[] = {0, 3, 4}; freopen("data.txt", "r", stdin); // 为了測试的方便。这里使用重定位 // read data
scanf("%d %d", &pCount, &rCount);
initData(pCount, rCount); // test status
if (testStatus(pCount, rCount) == TRUE)
{
printf("是安全状态\n");
}
else
{
printf("非安全状态\n");
} showSafeList(pCount); //请求资源 p2 请求资源 0 3 4
if (request(pId, pCount, rCount, reqList) == TRUE)
{
printf("资源成功分配\n");
}
else
{
printf("该请求无法满足安全状态\n");
} destory(); return 0;
} /********************************************
data.txt
5 3 5 5 9
5 3 6
4 0 11
4 2 5
4 2 4 2 1 2
4 0 2
4 0 5
2 0 4
3 1 4 2 3 3
********************************************/
最新文章
- php杂记（二）
- Linux下用ftp更新web内容！
- Echarts3 关系图-力导向布局图
- Web前端发展前景及就业方向
- Python 素数判断；以及默尼森数
- 二分查找C++
- POJ 1523 SPF tarjan求割点
- System.Data.OracleClient 需要 Oracle 客户端软件 8.1.7 或更高版本
- ios--socket
- 一些实用的mysql语句(不断积累更新)
- Hecher学生互助平台(团队项目第一次)
- [Hadoop]Hadoop章3 NameNode的ZKFC机制
- Quartz的JobDetail没有触发器指向时会被删除的问题
- individual project1 12061183
- windows下boost编译（vs2010）
- Android Studio安装配置
- MySQL Error Code文档手册---摘自MySQL官方网站
- RSA密钥生成、加密解密、签名验签
- 使用 Zipkin 和 Brave 实现分布式系统追踪（基础篇）
- python的初始化运行了哪些？