声明：未经允许，请勿转载
一.实验目的
(1) 掌握 RR(时间片调度) 算法，了解 RR 进程调度
(2) 了解死锁概念，理解安全状态，并且理解银行家算法
(3) 利用 RR 进程调度与银行家算法结合，写出一个简单的项目
二.实验原理
2.1 时间片调度算法
在分时系统中都采用时间片轮转算法进行进程调度。时间片是指一个较小的时间间隔，通常为 10- 100 毫秒。在简单的轮转算法中，系统将所有的就绪进程按先来先服务（即 FIFO）规则排成一个队列， 将 CPU 分配给队首进程，且规定每个进程最多允许运行一个时间片；若时间片使用完进程还没有结束， 则被加入就绪 FIFO 队列队尾，并把 CPU 交给下一个进程。时间片轮转算法只用于进程调度，它属于 抢占调度方式。
算法实现：
(1) 假设系统中有 5 个进程，每个进程有一个进程控制块（PCB）来标识。进程控制块内容包括：进 程名，链接指针，到达时间，估计运行时间，进程状态。进程名即进程标识。链接指针：按照进 程到达系统的时间将处于就绪状态的进程连接成一个就绪队列。指针指出下一个到达进程的进程 控制块地址。最后一个进程的链接指针为 NULL。
(2) 为每个进程任意确定一个到达时间和要求运行时间。
(3) 设置一个队首指针，用来指出最先进入系统的进程。各就绪进程通过链接指针连在一起构成一个 循环队列。
(4) 处理机调度时开始选择队首指针指向的进程投入运行。由于本实验是模拟试验，所以对被选中进 程并不实际启动运行，而只是执行：估计运行时间减 1。用这个操作来模拟进程的一次运行，而 且省去进程的现场保护和现场恢复工作。 2 电气与计算机工程学院实验报告
(5) 进程运行一次后，以后的调度则将当前指针依次下移一个位置，指向下一个进程。同时还应判断 该进程的剩余的运行时间是否为 0，若不为 0，则等待下一轮的运行；若该进程的剩余时间为 0， 则把它的状态改为完成态（C)，并撤出就绪队列。
(6) 若就绪队列非空，则重复上述的（4）和（5），直到所有进程为完成态。
(7) 在所设计的程序中应有显示或打印语句，能显示或打印正运行进程的进程名、已运行时间、还剩 时间、就绪队列中的进程等。
2.2 银行家算法
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源， 但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态， 则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构: 可利用资源向量 Available, 最大需 求矩阵 Max, 分配矩阵 Allocation, 需求矩阵 Need.
银行家算法详述：
设 Request；是进程 Pi 的请求向量，如果 Requesti[j] = K，表示进程 Pi 需要 K 个 Rj 类型的资 源。当 Pi 发出资源请求后，系统按下述步骤进行检査:
(1) 如果 Requesti[j] Need[i,j] 便转向步骤
(2)；否则认为出错，因为它所需要的资源数已超过它所 宣布的最大值 (2) 如果 Requesti[j] Available[j]，便转向步骤
(3)；否则，表示尚无足够资源，Pi 须等待。 (3) 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值
Available[j] = Available[j] − Requesti[j]
Allocation[i, j] = Allocation[i, j] + Requesti[j]
Need[i, j] = Need[i, j] − Requesti[j]
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分 配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。
安全性算法:
(1) 设置两个向量:工作向量 Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含 有 m 个元素，在执行安全算法开始时，Work = Available； Finish: 它表示系统是否有足够的资源分配 给进程，使之运行完成。开始时先做 Finish[i] = false；当有足够资源分配给进程时，再令 Finish[i] = true。
(2) 从进程集合中找到一个能满足下述条件的进程 Finish[i] = false; Need[i,j] Work[j]; 若找到，执 行步骤 (3)，否则，执行步骤 (4)。
(3) 当进程 Pi 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
W ork[j] = W ork[j] + Allocation[i, j]
F inish[i] = true
go to step 2
(4) 如果所有进程的 Finish[i] =true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
三.实验过程
3.1 RR 算法与银行家算法结合的实现
1、假定系统有 3 类资源 A（10 个）、B（15 个）、C（12 个），系有 5 个进程并发执行，进程调度 采用时间片轮转调度算法。
2、每个进程由一个进程控制块（PCB）表示，进程控制块可以包含如下信息：进程名、需要的资 源总数、已分配的资源数、进程状态。
3、由程序自动生成进程（包括需要的数据，要注意数据的合理范围）。
4、进程在运行过程中会随机申请资源（随机生成请求的资源数），如果达到最大需求，表示该进程 可以完成；如果没有达到最大需求，则运行一个时间片后，调度其它进程运行。资源分配采用银行家算 法来避免死锁。
5、每个进程的状态可以是就绪 W（Wait）、运行 R（Run）、阻塞 B（Block）或完成 F（Finish） 状态之一。 5 电气与计算机工程学院实验报告
6、每进行一次调度，程序都要输出一次运行结果：正在运行的进程、就绪队列中的进程、阻塞队 列中的进程、完成的进程以及各个进程的 PCB，以便进行检查。
完整项目：C++ 银行家算法与时间片轮转调度算法结合
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIME_SLICE 2
// 进程状态：就绪 等待 阻塞 完成
enum process_type{
process_type_wait = 'W',
process_type_run = 'R',
process_type_block = 'B',
process_type_finish = 'F'
};
typedef struct PCB{
// 进程名
char name;
// 最大需求资源数
int Max[100];
// 还需要的资源数
int Need[100];
// 已分配的资源数
int Allocate[100];
// 进程已运行时间
int run_time;
// 进程状态
char state;
// 指向下一个进程
PCB *next;
}PCB;
// 系统资源的名称
char Name[100]={0};
// 系统可用资源向量
int Available[100];
// 进程请求资源向量
int Request[100];
// 存放系统可提供资源量
int Work[100];
// 标记系统是否有足够的资源分配给各个进程
bool Finish[100];
// 存放安全序列
char Security[100];
// 进程的最大数
int M = 100;
// 资源的最大数
int N = 100;
// 标志是否输出
bool flag = true;
// 函数声明
// 初始化数据
void init(PCB *list);
// 创建进程
void create_process(PCB *list);
// 显示资源分配和进程运行情况
void print(PCB *list);
// 试探性分配资源
void test(PCB *list);
// 试探性分配资源作废
void Retest(PCB *list);
// 利用银行家算法对申请资源进行试分
bool bank(PCB *list);
// 安全性算法
bool safe(PCB *list);
// 时间片轮转调度算法
void round_robin(PCB *list);
// 主函数
int main(){
printf("-----------------------------------------------------------------------\n");
printf(" 银行家算法的实现 \n");
printf("-----------------------------------------------------------------------\n\n");
PCB *list = (PCB *)malloc(sizeof(PCB));
if(list == NULL){
printf("动态分配内存失败！");
}
list->next = NULL;
srand((int)time(NULL));
// 初始化数据
init(list);
// 显示资源分配和进程运行情况
printf("***********************************************************************\n");
print(list);
// 用银行家算法判定系统当前时刻是否安全，不安全就不再继续分配资源
if(!safe(list)) {
exit(0);
}
printf("\n***********************************************************************\n");
// 使用时间片轮转法进行进程调度
round_robin(list);
system("pause");
}
// 初始化数据
void init(PCB *list){
// m为进程数，n为系统资源种类
int m,n;
// 初始化系统资源种类数及各资源数
printf("系统可用资源种类数为：");
scanf("%d",&n);
getchar();
// 系统资源种类数，赋给全局变量N，方便后续方法使用
N = n;
// 资源名称
char name;
// 资源数
int number;
for(int i = 1;i <= n;i++){
printf("\t资源%d的名称：",i);
getchar();
scanf("%c",&name);
getchar();
Name[i] = name;
printf("\t资源%c的初始个数为：",name);
scanf("%d",&number);
getchar();
Available[i] = number;
}
// 初始化进程数及各进程的最大需求资源数
printf("\n请输入进程的数量：");
scanf("%d",&m);
// 进程数，赋给全局变量M，方便后续方法使用
M = m;
create_process(list);
}
// 创建进程
void create_process(PCB *list){
// 统计已分配的系统资源
int temp[100] = {0};
int number = 1;
while(number <= M){
// 进程节点
PCB *p = (PCB *)malloc(sizeof(PCB));
if(p == NULL){
printf("动态分配内存失败！");
}
// 进程名
printf("\t请输入第%d进程的进程名：",number);
getchar();
scanf("%c",&p->name);
// 标志变量
bool flag;
// 初始化各进程最大需求资源数、仍需资源数和已分配资源数
do{
flag = false;
for(int i = 1;i <= N;i++){
p->Max[i] = rand()%10;
if(p->Max[i] > Available[i]){
flag = true;
// printf("资源最大需求量大于系统中资源最大数，请重新输入!\n");
break;
}
p->Need[i] = p->Max[i];
p->Allocate[i] = 0;
}
}while(flag);
// 进程已运行时间
p->run_time = 0;
// 进程状态
p->state = process_type_wait;
// 指向下一个进程
p->next = NULL;
if(list->next == NULL){
list->next = p;
}else{
PCB *move = list->next;
while(move->next != NULL){
move = move->next;
}
move->next = p;
}
number++;
}
printf("\n");
}
// 显示资源分配和进程运行情况
void print(PCB *list){
printf("\n系统目前可用的资源(Available):\n");
for(int i = 1;i <= N;i++){
printf("%c ",Name[i]);
}
printf("\n");
for(int i = 1;i <= N;i++){
printf("%d ",Available[i]);
}
printf("\n\n");
printf("系统当前的资源分配情况及进程运行情况如下：\n");
printf(" Max Allocate Need\n");
printf("进程名 ");
//输出与进程名同行的资源名，Max、Allocate、Need下分别对应
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= N;j++){
printf("%c ",Name[j]);
}
printf(" ");
}
printf("已运行时间 进程状态\n");
// 遍历链表
PCB *p = list->next;
while(p != NULL){
//输出每个进程的Max、Allocation、Need
printf(" %c\t",p->name);
for(int j = 1;j <= N;j++)
printf("%d ",p->Max[j]);
printf(" ");
for(int j = 1;j <= N;j++)
printf("%d ",p->Allocate[j]);
printf(" ");
for(int j = 1;j <= N;j++)
printf("%d ",p->Need[j]);
printf(" ");
printf(" %d\t ",p->run_time);
printf("%c\n",p->state);
p = p->next;
}
}
// 试探性分配资源
void test(PCB *list){
// 请求资源的进程
PCB *p = list->next;
// 更改进程信息
for(int i = 1;i <= N;i++){
Available[i] -= Request[i];
p->Allocate[i] += Request[i];
p->Need[i] -= Request[i];
}
}
// 试探性分配资源作废
void Retest(PCB *list){
// 请求资源的进程
PCB *p = list->next;
// 与test操作相反
for(int i = 1;i <= N;i++){
Available[i] += Request[i];
p->Allocate[i] -= Request[i];
p->Need[i] += Request[i];
}
}
// 利用银行家算法对申请资源进行试分
bool bank(PCB *list){
PCB *p = list->next;
// 随机生成请求向量
for(int i = 1;i <= N;++i){
Request[i] = rand()%(p->Need[i]+1);
}
// 随机产生的请求资源数均为0，表示不理会
int n = 0;
for(int i = 1;i <= N;++i){
if(Request[i] == 0){
n++;
}
}
if(n == N){
flag = false;
return false;
}
printf("\n%c进程请求 —— ",p->name);
for(int i = 1;i <= N;i++){
printf("资源%c：",Name[i]);
printf("%d ",Request[i]);
}
printf("\n\n");
// 定位要求的资源数组下标
int num = 1;
// 判断银行家算法的前两条件是否成立
for(int i = 1;i <= N;++i){
// 判断申请是否大于需求，若大于则出错
if(Request[i] > p->Need[i]){
printf("%c进程申请的资源大于它需要的资源\n",p->name);
printf("分配不合理，不予分配！\n");
return false;
}else{
// 判断申请是否大于当前可分配资源，若大于则出错
if(Request[i] > Available[i]){
printf("%c进程申请的资源大于系统现可利用的资源\n",p->name);
printf("系统尚无足够资源，不予分配!\n");
return false;
}
}
}
// 前两个条件成立，试分配资源，寻找安全序列
// 根据进程需求量,试分配资源
test(list);
// 判断系统是否安全
if(!safe(list)){
Retest(list);
return false;
}
return true;
}
// 安全性算法
bool safe(PCB *list){
// 统计未完成进程数
int m = 0;
PCB *move = list->next;
while(move != NULL && move->state != process_type_finish){
move = move->next;
++m;
}
// 初始化Work数组
for(int i = 1;i <= N;i++){
Work[i] = Available[i];
}
// 初始化Finish数组
for(int i = 1;i <= M;i++){
if(i <= m){
Finish[i] = false;
}else{
Finish[i] = true;
}
}
// 节点位置，判断进程运行
int pnum = 1,apply;
int num = 1;
// 求安全序列
PCB *p = list->next;
while(p != NULL && pnum <= m){
apply = 0;
for(int i = 1;i <= N;i++){
// 当前进程未完成并且各类资源小于或等于系统资源数
if(Finish[pnum] == false && p->Need[i] <= Work[i]){
apply++;
// 直到每类资源尚需数都小于系统可利用资源数才可分配
if(apply == N){
for(int x = 1;x <= N;x++){
// 更新当前系统可分配资源
Work[x] += p->Allocate[x];
}
// 更新标记数组
Finish[pnum] = true;
// 更新安全序列数组
Security[num++] = p->name;
// 保证每次查询均从第一个进程开始
pnum = 0;
p = list;
}
}
}
// 查询下一进程
pnum++;
p = p->next;
}
for(int i = 1;i <= M;i++){
if(Finish[i] == false){
// 系统处于不安全状态
printf("系统不安全！\n");
return false;
}
}
// 如果安全，输出安全序列
printf("系统是安全的！\n");
printf("存在一个安全序列:");
for(int i = 1;i <= m;i++){
// 输出进程运行顺序数组
printf(" %c ",Security[i]);
if(i < m){
printf("->");
}
}
printf("\n");
return true;
}
// 时间片轮转调度算法
void round_robin(PCB *list){
// 记录第一个结点的位置
PCB *index = list->next;
while (index != NULL && index->state != process_type_finish) {
// 判断调度后是否输出
flag = true;
// 系统安全，进程分配到资源并运行
if(bank(list)){
// 更新已运行时间
index->run_time += TIME_SLICE;
// 判断该进程是否完成
int num = 0;
for(int i = 1;i <= N;++i){
if(index->Max[i] == index->Allocate[i]){
num++;
}
}
// 该进程已完成
if (num == N) {
// 修改进程状态
index->state = process_type_finish;
// 回收分配的资源
for(int i = 1;i <= N;i++){
Available[i] += index->Allocate[i];
}
printf("%c进程完成\n",index->name);
}else{
// 进程未完成，进入等待
index->state = process_type_wait;
}
// 当前进程已完成
if (index->state == process_type_finish){
// 将已完成进程调整到已完成队列末尾
// 1.头指针指向首元结点的下一个结点
list->next = index->next;
// 2.遍历整个链表，将其插入到已完成队列的最尾端
PCB *p = list;
while (p->next != NULL) {
p = p->next;
}
p->next = index;
index->next = NULL;
} else {
// 当前进程未完成
// 1.头指针指向首元结点的下一个结点
list->next = index->next;
// 2.遍历整个链表，将其插入到等待队列的最尾端(其后是已完成队列)
PCB *p = list;
// 2.1寻找插入位置
while (p->next != NULL && p->next->state != process_type_finish) {
p = p->next;
}
// 2.2判断插入位置
if (p->next == NULL) {
// 最后一个
p->next = index;
p->next->next = NULL;
}else{
// 不是最后一个，其后仍有结点
index->next = p->next;
p->next = index;
}
}
}else{
// 该进程请求资源分配会导致系统不安全或请求资源不合理
// 将该进程阻塞并调整到等待队列和已完成队列中间，且是阻塞队列的最后一个
index->state = process_type_block;
// 当前进程未完成并处于阻塞状态
// 1.头指针指向首元结点的下一个结点
list->next = index->next;
// 2.遍历整个链表，将其插入到未完成队列后阻塞队列的最后一个
PCB *p = list;
// 2.1寻找插入位置
while (p->next != NULL && p->next->state != process_type_finish) {
p = p->next;
}
// 2.2判断插入位置
if (p->next == NULL) {
// 最后一个
p->next = index;
p->next->next = NULL;
}else{
// 不是最后一个，其后仍有结点
index->next = p->next;
p->next = index;
}
}
// 展示当前队列状况
if(list->next->state != process_type_finish){
list->next->state = process_type_run;
}
if(flag){
print(list);
printf("\n***********************************************************************\n");
}
index = list->next;
}
}
3.3 实验结果
报告页面截图
文章来源：https://www.toymoban.com/news/detail-479476.html
注：代码借鉴于文章来源地址https://www.toymoban.com/news/detail-479476.html
到了这里，关于C++ 银行家算法与时间片轮转调度算法结合的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[操作系统] 银行家算法](https://imgs.yssmx.com/Uploads/2024/01/404257-1.png)
