进程调度

基本要求

　　在进程控制实验基础上实现按先来先服务FCFS、短作业优先SJF以及时间片轮转算法调度进程的模拟过程。根据当前所设定调度算法，连续调度所有进程，并计算每个进程的周转时间和带权周转时间、所有进程的平均周转时间和平均带权周转时间。实现调度算法时应适当输出调度过程中各进程状态队列的变化情况以及进程的已执行时间、还需服务时间（针对时间片轮转算法）。同时可以考虑优先级等其它的进程调度算法，独立的避免死锁的银行家算法。

实验提示

 

　　1、 调度算法：程序开始运行时选择调度算法，创建进程时输入进程所需服务时间以及到达时间。可参考如下数据结构：

 

struct PCB{ char name[10]; int size; int arrival_time; //到达时间 int burst_time; //服务时间 int finished_time; //结束运行时间 int runned_time; //已运行时间 struct PCB*next; }; struct PCB *ready,*blocked,*running,*finished;

 

其中，finished队列是已运行结束的进程队列，便于统计各项时间数据。

 

　　2、 银行家算法：首先检查安全性，然后进程资源请求后及其安全检测。

 

2.1数据结构

 

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。

 

4) 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成任务。  

 

上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j] 

 

2.2设计思路

 

　　第一部分：银行家算法模块

 

1)．如果Request<=Need,则转向2;否则,出错

 

2)．如果Request<=Available,则转向3,否则等待

 

3)．系统试探分配请求的资源给进程 

 

4)．系统执行安全性算法

 

　　第二部分:安全性算法模块

 

1).设置两个向量

 

①工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)

 

②Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False  

 

2).若Finish[i]=False&&Need<=Work,则执行3;否则执行4(i为资源类别)

 

3).进程P获得第i类资源,则顺利执行直至完成，并释放源:Work=Work+Allocation;Finish[i]=true;转2

 

4).若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!

实验代码

代码提示

　　银行家算法中，只考虑了优先队列成功的情况，也就是没有考虑优先级，实例在代码下面，可以运行后再看一眼，便于理解。

代码

#include<stdio.h>
#include<string.h>
struct PCB {
char name[10];
int arrival_time;        //到达时间
int burst_time;            //服务时间
int start_time;            //开始时间 
int finished_time;        //结束运行时间
int sign_RR;
int sign_RR2;
int T;
double W;
};
struct PCBb {
char name[10];
int MAX[10];
int Allocation[10];
int Need[10];
int Available[10];
int WORK[10];
int WA_sum[10];
char finish;
int sign;
}; 
int num;    // 进程个数
struct PCB p[10]; 
int number, n;
struct PCBb q[10];
struct PCBb t[10];
// 创建进程 
void creat_Process() {
printf("请输入创建进程的个数:/n");
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
printf("进程名称、到达时间、服务时间:/n");
scanf(" %s", &p[i].name);
scanf("%d", &p[i].arrival_time);
scanf("%d", &p[i].burst_time);    
}
}
void display() {
for (int i = 1; i <= num; i++) {
printf("/t%s", p[i].name);
}
printf("/n到");
for (int i = 1; i <= num; i++) {
printf("/t%d", p[i].arrival_time);
}
printf("/n服");
for (int i = 1; i <= num; i++) {
printf("/t%d", p[i].burst_time);
}
printf("/n开");
for (int i = 1; i <= num; i++) {
printf("/t%d", p[i].start_time);
}
printf("/n完");
for (int i = 1; i <= num; i++) {
printf("/t%d", p[i].finished_time);
}
printf("/nT");
for (int i = 1; i <= num; i++) {
printf("/t%d", p[i].T);
}
printf("/nW");
for (int i = 1; i <= num; i++) {
printf("/t%.1lf", p[i].W);
}
} 
// 先来先服务
void FCFS() {
// 按到到达顺序排序 
for (int i = 1; i <= num; i++) {
for (int j = i+1; j <= num; j++) {
if(p[i].arrival_time > p[j].arrival_time) {
p[0] = p[j];
p[j] = p[i];
p[i] = p[0];
}
}
}
p[1].start_time = p[1].arrival_time;
p[1].finished_time = p[1].arrival_time + p[1].burst_time;
p[1].T = p[1].finished_time - p[1].arrival_time;
p[1].W = p[1].T / p[1].burst_time;
for (int i = 2; i <= num; i++) {
p[i].start_time = p[i-1].start_time + p[i-1].burst_time;
p[i].finished_time = p[i-1].finished_time + p[i].burst_time;
p[i].T = p[i].finished_time - p[i].arrival_time;
p[i].W = (double)p[i].T / p[i].burst_time;
}
double sum_T = 0;
double sum_W = 0;
for (int i = 1; i <= num; i++) {
sum_T += p[i].T;
sum_W += p[i].W;
}
double o_T = sum_T / num;
double o_W = sum_W / num;
printf("/nFCFS");
display();
printf("/n平均周转时间:%.2lf", o_T);
printf("/n平均带权周转时间:%.2lf", o_W);
}
// 短作业优先 
void SJF() {
// 按到到达顺序排序
for (int i = 1; i < num; i++) {
for (int j = 1; j < num; j++) {
if (p[j].arrival_time > p[j+1].arrival_time) {
p[0] = p[j];
p[j] = p[j+1];
p[j+1] = p[0];
}
// 到达顺序相同  按服务时间排序 
else if (p[j].arrival_time == p[j+1].arrival_time) {
if (p[j].burst_time > p[j+1].burst_time) {
p[0] = p[j];
p[j] = p[j+1];
p[j+1] = p[0];
}
}
}
}
p[1].start_time = p[1].arrival_time;
p[1].finished_time = p[1].arrival_time + p[1].burst_time;
p[1].T = p[1].finished_time - p[1].arrival_time;
p[1].W = p[1].T / p[1].burst_time;
int time = p[1].finished_time;
// 过程 
for (int i = 2; i <= num; i++) {
for (int j = i+1; j <= num; j++) {
if (time > p[j].arrival_time) {
if (p[i].burst_time > p[j].burst_time) {
p[0] = p[j];
p[j] = p[i];
p[i] = p[0];
}
}
else {
continue;
}
}
p[i].start_time = p[i-1].start_time + p[i-1].burst_time;
p[i].finished_time = p[i-1].finished_time + p[i].burst_time;
p[i].T = p[i].finished_time - p[i].arrival_time;
p[i].W = (double)p[i].T / p[i].burst_time;
time = p[i].finished_time;
}
double sum_T = 0;
double sum_W = 0;
for (int i = 1; i <= num; i++) {
sum_T += p[i].T;
sum_W += p[i].W;
}
double o_T = sum_T / num;
double o_W = sum_W / num;
printf("/nSJF");
display();
printf("/n平均周转时间:%.2lf", o_T);
printf("/n平均带权周转时间:%.2lf", o_W);
}
// 时间片轮转 
void RR() {
// 按到到达顺序排序 
for (int i = 1; i <= num; i++) {
for (int j = i+1; j <= num; j++) {
if(p[i].arrival_time > p[j].arrival_time) {
p[0] = p[j];
p[j] = p[i];
p[i] = p[0];
}
}
}
int pp;
printf("请输入P:/n");
scanf("%d", &pp);
// 初始化标记位 
for (int i = 1; i <= num; i++) {
p[i].sign_RR = 0;   // 记录服务时间 
p[i].sign_RR2 = 0;  // 记录进程完成 
p[i].start_time = -1;
p[i].finished_time = -1;
}
int N = num;
int z = 0;  // 总时间 
int flag;
do {
for (int i = 1; i <= N; i++) {
if (p[i].sign_RR == p[i].burst_time) {
continue;
}
if (p[i].start_time == -1) {
p[i].start_time = z;
}
for(int j=0; j<pp; j++){
if (p[i].sign_RR != p[i].burst_time) {
printf("%s", p[i].name);
p[i].sign_RR++;
z++;
}
if (p[i].sign_RR == p[i].burst_time) {
if (p[i].finished_time == -1) {
p[i].finished_time = z;
}
p[i].sign_RR2 = 1;
}                
} 
}
// 结束条件 
flag = 0;
for (int i = 1; i <= num; i++) {
if (p[i].sign_RR2 == 1) {
flag++;
}    
}
} while(flag != num);
for (int i = 1; i <= num; i++) {
p[i].T = p[i].finished_time - p[i].arrival_time;
p[i].W = (double)p[i].T / p[i].burst_time;
}
double sum_T = 0;
double sum_W = 0;
for (int i = 1; i <= num; i++) {
sum_T += p[i].T;
sum_W += p[i].W;
}
double o_T = sum_T / num;
double o_W = sum_W / num;
printf("/nRR");
display();
printf("/n平均周转时间:%.2lf", o_T);
printf("/n平均带权周转时间:%.2lf", o_W);
}
//银行家算法 
void creat() {
printf("请输入资源类的个数：/n");
scanf("%d", &number);
printf("请输入每类资源对应的个数：/n");
scanf("%d", &n);
for (int i = 1; i <= number; i++) {
printf("请输入资源名称:/n"); 
scanf(" %s", &q[i].name);
printf("最大需求数:/n");
for (int j = 1; j <= n; j++) {
scanf("%d", &q[i].MAX[j]);
}
printf("已分配数:/n");
for (int j = 1; j <= n; j++) {
scanf("%d", &q[i].Allocation[j]);
}
}
printf("请输入可利用资源：/n");
for (int j = 1; j <= n; j++) {
scanf("%d", &q[1].Available[j]);
}
}
void display_r() {
printf("-----------------------------------------------------------------------------------------------/n"); 
printf("银行家");
printf("/t/tMAX/t/tAllocation/tNeed/t/tAvailable/n");
for (int i = 1; i <= number; i++) {
printf("%s/t/t", q[i].name);
for (int j = 1; j <= n; j++) {
printf("%d ", q[i].MAX[j]);
}
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", q[i].Allocation[j]);
}
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", q[i].Need[j]);
}
if (i == 1) {
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", q[1].Available[j]);
}
}
printf("/n");
}
printf("-----------------------------------------------------------------------------------------------/n"); 
}
void display_re() {
printf("银行家");
printf("/t/tWORK/t/tNeed/t/tAllocation/tW+A/t/tfinish/n");
for (int i = 1; i <= number; i++) {
printf("%s/t/t", t[i].name);
for (int j = 1; j <= n; j++) {
printf("%d ", t[i].WORK[j]);
}
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", t[i].Need[j]);
}
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", t[i].Allocation[j]);
}
printf("/t");
for (int j = 1; j <= n; j++) {
printf("%d ", t[i].WA_sum[j]);
}
printf("/t");
printf("%c/n", t[i].finish);
}
printf("-----------------------------------------------------------------------------------------------/n");
printf("安全序列：");
for (int i = 1; i <= number; i++) {
printf(" %s", t[i].name);
} 
}
void banker() {
for (int i = 1; i <= number; i++) {
for (int j = 1; j <= n; j++) {
q[i].Need[j] = q[i].MAX[j] - q[i].Allocation[j];
}
}
int flag = 0;
for (int i = 1; i <= number; i++) {
q[i].sign = 0;
}
for (int k = 1; k <= number; k++) {
for (int i = 1; i <= number; i++) {  
for (int j = 1; j <= n; j++) {
if (q[k].Available[j] >= q[i].Need[j] && q[i].sign == 0) {
flag++; 
}
}
if (flag == n) {
strcpy(t[k].name, q[i].name);
for (int h = 1; h <= number; h++) {
t[k].WORK[h] = q[k].Available[h];
t[k].Need[h] = q[i].Need[h];
t[k].Allocation[h] = q[i].Allocation[h];
t[k].WA_sum[h] = t[k].WORK[h] + t[k].Allocation[h];
t[k].finish = 'R';
q[k+1].Available[h] = t[k].WA_sum[h];
q[i].sign = 1;
}
}
flag = 0;
}
}
}
void menu() {
printf("/t*********************************/n");
printf("/t*/t1.创建新进程            */n");
printf("/t*/t2.先来先服务问题        */n");
printf("/t*/t3.短作业优先问题        */n");
printf("/t*/t4.时间片轮转问题        */n");
printf("/t*/t5.银行家算法            */n");
printf("/t*/t6.退出程序              */n");
printf("/t*********************************/n");
}
int main()
{
int n;
menu(); 
while(1)
{   printf("/n/n请输入您的选择：/n");
scanf("%d",&n);
switch(n)
{
case 1:
creat_Process();
break;
case 2:
FCFS();
break;
case 3:
SJF();
break;
case 4:
RR();
break;
case 5:
creat();
banker();
display_r();
display_re();
break;
case 6:
printf("感谢使用！！！");
return 0;
}
}
}
/*
A 0 4
B 1 3
C 2 5
D 3 2
E 4 4
*/
/*
5
4
P0
0 7 4 2
0 2 3 1
P1
1 3 8 1
0 3 2 0
P2
0 0 3 1
0 0 1 1
P3
5 5 4 3
1 0 1 1
P4
6 1 1 0
1 1 1 0
4 3 5 0
*/