社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。因为源码中我对一些关键步骤的注释已经比较清晰了，所以在本文中不会再对每一个细节都进行分析，只分析整体的代码结构和所使用到的设计模式。
博客内所有文章均为 原创，所有示意图均为 原创，若转载请附原文链接。
1．可利用资源向量 Available ，它是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available(j) = k，表是系统中现有Rj类资源k个。
2．最大需求矩阵 Max，这是一个n×m的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果Max(i，j) = k，表示进程 i 需要 Rj 类资源的最大数目为 k 。
3．分配矩阵 Allocation，这是一个 n×m 的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果 Allocation(i，j) = k，表示进程 i 当前已经分到 Rj 类资源的数目为 k 。Allocationi 表示进程i的分配向量，有矩阵 Allocation 的第 i 行构成。
4．需求矩阵 Need，这是一个 n×m 的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need(i，j) = k，表示进程i还需要 Rj 类资源 k 个，才能完成其任务。Needi 表示进程i的需求向量，由矩阵 Need 的第 i 行构成。
上述三个矩阵间存在关系：Need(i，j) = Max(i，j) - Allocation(i，j)；
设 Requesti 是进程 Pi 的请求向量，如果 Requesti[j] = K，表示进程 Pi 需要 K 个 Pj 类型的资源。当 Pi 发出自愿请求后，系统按下述步骤进行检查：
1．设置两个向量。
Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work = Available。
Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish(i)=false；当有足够资源分配给进程Pi时，令Finish(i)=true；
2．从进程集合中找到一个能满足下述条件的进程。
Finish(i) == false；
Need i ≤ work；
如找到则执行步骤3；否则，执行步骤4；
3．当进程 Pi 获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行
Work = work + Allocation i
Finish(i) = true；转向步骤2；
4．若所有进程的 Finish(i) 都为true，则表示系统处于安全状态；否则，系统处于不安全状态。
#include <iostream>
#include <vector>
typedef std::vector<int> Resource;
typedef std::vector<int> * ResourcePtr;
typedef std::vector<std::vector<int>> Resources;
typedef std::vector<std::vector<int>> * ResourcesPtr;
class BankerAlgorithm
{
public:
BankerAlgorithm()
{
/*
process_num_ = process_num;
resource_num_ = resource_num;
*/
// should input by user
//available_ = new std::vector<int>(resource_num, 0);
/*
(*available_)[0] = 3;
(*available_)[1] = 3;
(*available_)[2] = 2;
*/
//allocation_ = createResourceArray(process_num, resource_num);
//need_ = createResourceArray(process_num, resource_num);
/*
(*need_)[0][0] = 7; (*need_)[0][1] = 4; (*need_)[0][2] = 3;
(*need_)[1][0] = 1; (*need_)[1][1] = 2; (*need_)[1][2] = 2;
(*need_)[2][0] = 6; (*need_)[2][1] = 0; (*need_)[2][2] = 0;
(*need_)[3][0] = 0; (*need_)[3][1] = 1; (*need_)[3][2] = 1;
(*need_)[4][0] = 4; (*need_)[4][1] = 3; (*need_)[4][2] = 1;
(*allocation_)[0][0] = 0; (*allocation_)[0][1] = 1; (*allocation_)[0][2] = 0;
(*allocation_)[1][0] = 2; (*allocation_)[1][1] = 0; (*allocation_)[1][2] = 0;
(*allocation_)[2][0] = 3; (*allocation_)[2][1] = 0; (*allocation_)[2][2] = 2;
(*allocation_)[3][0] = 2; (*allocation_)[3][1] = 1; (*allocation_)[3][2] = 1;
(*allocation_)[4][0] = 0; (*allocation_)[4][1] = 0; (*allocation_)[4][2] = 2;
*/
}
inline ResourcesPtr createResourceArray(int row_num, int col_num)
{
return new std::vector<std::vector<int>>(row_num, std::vector<int>(col_num, 0));
}
inline ResourcesPtr copyResourceArray(ResourcesPtr ori)
{
int col_num = (*ori)[0].size();
int row_num = (*ori).size();
ResourcesPtr res = createResourceArray(row_num, col_num);
for (int i = 0; i < row_num; ++i)
for (int j = 0; j < col_num; ++j)
(*res)[i][j] = (*ori)[i][j];
return res;
}
bool inputInitData()
{
std::cout << "please input process num and resource num: " << std::endl;
std::cin >> process_num_ >> resource_num_;
// allocate memory for struct
available_ = new std::vector<int>(resource_num_, 0);
allocation_ = createResourceArray(process_num_, resource_num_);
need_ = createResourceArray(process_num_, resource_num_);
std::cout << "please input init resource: " << std::endl;
for (int i = 0; i < resource_num_; ++i)
std::cin >> (*available_)[i];
std::cout << "please input max matrix: " << std::endl;
ResourcesPtr max = createResourceArray(process_num_, resource_num_);
bool inputSuccess = true;
do {
inputSuccess = true;
for (int i = 0; i < process_num_; ++i)
{
for (int j = 0; j < resource_num_; ++j)
{
std::cin >> (*max)[i][j];
if ((*max)[i][j] > (*available_)[j])
{
inputSuccess = false;
max->clear();
std::cout << "max matrix is illegal, please reinput max matrix: " << std::endl;
break;
}
}
}
} while (!inputSuccess);
std::cout << "please input allocation matrix: " << std::endl;
for (int i = 0; i < process_num_; ++i)
{
for (int j = 0; j < resource_num_; ++j)
{
std::cin >> (*allocation_)[i][j];
(*need_)[i][j] = (*max)[i][j] - (*allocation_)[i][j];
(*available_)[j] -= (*allocation_)[i][j];
}
}
std::cout << "current available resource: [";
for (int num : *available_)
std::cout << num << " ";
std::cout << "]" << std::endl;
std::vector<int> * req = new std::vector<int>(resource_num_, 0);
if (!bankerAlgorithm(-1, req))
{
std::cout << "init fail, data is illegal!" << std::endl;
}
bool quit = false;
while (!quit)
{
std::cout << "please input request process: " << std::endl;
int pid = -1;
std::cin >> pid;
std::cout << "please input request resource: " << std::endl;
for (int i = 0; i < resource_num_; ++i)
std::cin >> (*req)[i];
// do allocate.
bankerAlgorithm(pid, req);
}
}
inline bool allocateResourcesForProcess(int pid, ResourcePtr request)
{
return bankerAlgorithm(pid, request);
}
bool bankerAlgorithm(int pid, ResourcePtr request)
{
for (int i = 0; pid != -1 && i < (*request).size(); ++i)
{
if ((*request)[i] > (*need_)[pid][i])
{
std::cout << "[ERROR] request Resource more than need ResourcePtr." << std::endl;
return false;
}
else if ((*request)[i] > (*available_)[i])
{
std::cout << "[ERROR] request Resource more than available ResourcePtr." << std::endl;
return false;
}
}
// Here the copied value is passed
if (securityAlgorithm(pid, *available_, *request, *need_, *allocation_))
{
std::cout << "[INFO] securityAlgorithm true" << std::endl;
// Really allocate resources to process
for (int i = 0; pid != -1 && i < (*request).size(); ++i)
{
(*available_)[i] -= (*request)[i];
(*allocation_)[pid][i] += (*request)[i];
(*need_)[pid][i] -= (*request)[i];
}
// Debug
printResources();
return true;
}
else
{
std::cout << "[INFO] securityAlgorithm false" << std::endl;
// Don't allocate resources to process
// Debug
printResources();
return false;
}
}
bool securityAlgorithm(int pid, Resource available, Resource request, Resources need, Resources allocation)
{
if (pid != -1)
{
for (int i = 0; i < request.size(); ++i)
{
available[i] -= request[i];
allocation[pid][i] += request[i];
need[pid][i] -= request[i];
}
}
Resource work(available);
std::vector<bool> finish(allocation.size(), false);
while ((pid = getUsableProcessForSecurityAlgorithm(finish, work, need)) != -1)
{
for (int i = 0; i < work.size(); ++i)
work[i] += allocation[pid][i];
finish[pid] = true;
std::cout << "[INFO] process " << pid << " finish true, work: [";
for (int num : work)
std::cout << num << " ";
std::cout << "]" << std::endl;
}
for (bool b : finish)
if (!b) return false;
return true;
}
// return pid
int getUsableProcessForSecurityAlgorithm(std::vector<bool> finish, Resource work, Resources need)
{
for (int pid = 0; pid < finish.size(); ++pid)
{
if (!finish[pid])
{
bool canUse = true;
for (int i = 0; i < work.size(); ++i)
{
if (need[pid][i] > work[i])
{
canUse = false;
break;
}
}
if (canUse) return pid;
}
}
return -1;
}
bool printResources()
{
std::cout << "available: " << std::endl;
for (int num : *available_)
std::cout << num << " ";
std::cout << std::endl << std::endl;
std::cout << "allocation: " << std::endl;
printResource(allocation_);
std::cout << std::endl;
std::cout << "need: " << std::endl;
printResource(need_);
std::cout << std::endl;
}
bool printResource(ResourcesPtr ResourcesPtr)
{
for (std::vector<int> vec : *ResourcesPtr)
{
for (int num : vec)
std::cout << num << " ";
std::cout << std::endl;
}
return true;
}
private:
int process_num_;
int resource_num_;
ResourcePtr available_;
ResourcesPtr allocation_;
ResourcesPtr need_;
};
如果本文描述的内容或使用的代码存在任何问题，请及时联系我或在本篇文章的下面进行评论，我会本着对每一位学技术同学的负责态度立即修改。在后续还会有三篇计算机操作系统的算法 C++ 复现博文，如果感兴趣可以关注我。
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
