达州做网站
大橙子网站建设，新征程启航
为企业提供网站建设、域名注册、服务器等服务
操作系统——四种进程调度算法模拟实现（C语言）-创新互联
一、六种进程调度算法的基本思想
本文标题：操作系统——四种进程调度算法模拟实现（C语言）-创新互联
URL网址：http://dzwzjz.com/article/doiscj.html
1、先来先服务First-Come-First-Served（FCFS）（作业／进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。成都创新互联是一家专业提供珠晖企业网站建设,专注与成都网站建设、网站设计、H5页面制作、小程序制作等业务。10年已为珠晖众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。
2、短作业优先调度算法(Shortest Job First, SJF)
这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。
采用SJF有利于系统减少平均周转时间和平均带权周转时间。
3、高响应比优先调度算法 (Highest Response Ratio Next, HRRN)
按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比R，然后选择其值大的作业投入运行。R值定义为：
R ＝（已等待时间＋要求运行时间）／要求运行时间
＝1＋已等待时间／要求运行时间
HRRN算法实际上是FCFS算法和SJF算法的折衷。响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的响应比。这就克服了短作业优先的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。
4、时间片轮转Round-Robin（RR）调度算法
进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。
5、高优先级调度算法(Priority Scheduling Algorithm, PSA)
按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法。进程的优先权的设置可以是静态的，也可以是动态的。
二、四种进程调度算法模拟实现6、多级反馈队列调度算法
多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。
例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按FCFS等策略排序，后台采用高优先权的调度算法或者短作业优先的调度算法。
1、进程调度算法模拟程序设计要求
（1） 编写并调试一个模拟的进程调度程序，以深入探讨进程的概念及进程调度算法．
（2）分别采用3种调度算法对五个进程进行调度。每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。
（3）每个进程的状态可以是就绪W（Wait）、运行R（Run）、或阻塞B（Block）三种状态之一。 每进行一次调度程序都打印一次运行进程、就绪队列、阻塞队列以及各个进程的PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。进程的相关参数即运行时间、I/O需求等自行设定。
2、C语言源代码：
#includeusing namespace std;
#define MAXSIZE 30
typedef struct PCB {
char name[20]; // 进程名称(输入)
int arrivetime; //到达时间 (输入)
int running_time; //服务时间
int priority; //优先级
int start_time; //开始时间
int done_time; //结束时间
int copyRunning_time; //用于时间片轮转
float zztime; //记录该进程的周转时间（后期复制用）
float dqzztime; //记录该进程的带权周转时间（后期复制用）
PCB* next;
} Program;
typedef struct PCBQueue {
PCB* firstProg;
PCB* LastProg;
int size;
} PCBQueue;
// 函数声明
void print(PCB pro[], int num);//输出每个进程的到达时间
void inputProgram(PCB pro[], int num); //输入所有进程的具体信息
void PrintRunningprogram(PCB *pro);//输出正在运行的进程的信息
void PrintReadyqueue(PCBQueue *ready_queue);//输出就绪队列中的所有进程的信息
void PrintSortOfRunningprogram(PCB pro1[],int num);//输出进程的运行顺序
void CopyProgram(PCB *pro1,PCB *pro2);//将进程pro2的信息复制到进程pro1中
void Queueinit(PCBQueue* queue);//初始化就绪队列
void EnterQueue(PCBQueue* queue, PCB* pro);//将一个进程插入到就绪队列中
PCB* poll(PCBQueue* queue);//将一个进程从就绪队列中删除
void sortWithEnterTime(PCB pro[], int num);//将所有进程按到达时间升序排序
void EnterQueueOfRuntime(PCBQueue *ready_queue,PCB *program);//将一个进程按运行时间长短插入就绪队列
void EnterQueueOfPriority(PCBQueue *ready_queue,PCB *program);//将一个进程按优先级插入就绪队列
void FCFS(PCB pro[], int num);//先来先服务调度算法
void SJF(PCB pro[],int num);//短作业优先调度算法
void HPF(PCB pro[],int num);//高优先级调度算法
void RR(PCB pro[], int num);//时间片轮转调度算法
//具体函数实现
void print(PCB pro[], int num) {
int i;
for (i = 0; i< num; i++) {
printf("%d ", pro[i].arrivetime);
}
}
void inputProgram(PCB pro[], int num) {
int i;
for (i = 0; i< num; i++) {
PCB prog;
printf("\t\t\t\t\t请输入第%d个进程的名字，到达时间，服务时间，优先级\n\t\t\t\t\t", i + 1);
scanf("%s", prog.name);
scanf("%d", &prog.arrivetime);
scanf("%d", &prog.running_time);
prog.copyRunning_time = prog.running_time;
scanf("%d", &prog.priority);
pro[i] = prog;
}
}
void PrintRunningprogram(PCB *pro) {
printf("\t正在执行》》》进程%s\n",pro->name);
printf("\t————————————————————————————————————————————————\n");
printf("\t进程名字 到达时间 服务时间 优先级 开始时间 结束时间 周转时间 带权周转时间\n");
printf("\t%s\t\t%d\t%d\t%d",pro->name,pro->arrivetime,pro->running_time,pro->priority);
printf("\t%d\t%d\t %5.2f\t%5.2f\n",pro->start_time,pro->done_time,pro->zztime,pro->dqzztime);
printf("\t————————————————————————————————————————————————\n\n");
}
void PrintReadyqueue(PCBQueue *ready_queue) {
PCB *p;
p=ready_queue->firstProg->next;
if(!p) {
printf("\t无进程处于就绪状态！\n");
printf("\t————————————————————————————————————————————————\n\n\n");
return ;
}
printf("\t就绪队列：\n");
printf("\t————————————————————————————————————————————————\n");
printf("\t进程名字 到达时间 服务时间 优先级\n");
while(p) {
printf("\t%s\t\t%d\t%d\t%d\n",p->name,p->arrivetime,p->running_time,p->priority);
p=p->next;
}
printf("\t————————————————————————————————————————————————\n");
printf("\n\n\n");
}
void PrintSortOfRunningprogram(PCB pro1[],int num) {
int i;
printf("\t进程运行顺序如下：\n");
printf("\t————————————————————————————————————————————————\n");
printf("\t进程名字 到达时间 服务时间 优先级 开始时间 结束时间 周转时间 带权周转时间\n");
for(i=0; iname,pro2->name,sizeof(pro2->name));
pro1->arrivetime=pro2->arrivetime;
pro1->running_time=pro2->running_time;
pro1->priority=pro2->priority;
pro1->start_time=pro2->start_time;
pro1->done_time=pro2->done_time;
pro1->zztime=pro2->zztime;
pro1->dqzztime=pro2->dqzztime;
}
void Queueinit(PCBQueue* queue) {
if (queue == NULL) {
return;
}
queue->size = 0;
queue->LastProg = (PCB*)malloc(sizeof(PCB));
queue->LastProg->next=NULL;//注意加了此句
queue->firstProg = queue->LastProg;
}
void EnterQueue(PCBQueue* queue, PCB* pro) {
//加入进程队列
queue->LastProg->next = (PCB*)malloc(sizeof(PCB));
queue->LastProg = queue->LastProg->next;
queue->LastProg->arrivetime = pro->arrivetime;
memcpy(queue->LastProg->name, pro->name, sizeof(pro->name));
queue->LastProg->priority = pro->priority;
queue->LastProg->running_time = pro->running_time;
queue->LastProg->copyRunning_time = pro->copyRunning_time;
queue->LastProg->start_time = pro->start_time;
queue->LastProg->next=NULL;//注意加了此句
queue->size++;
}
PCB* poll(PCBQueue* queue) {
PCB *temp;
temp = queue->firstProg->next;
if (temp == queue->LastProg) {
queue->LastProg = queue->firstProg;
queue->LastProg->next=NULL;//注意加了此句
queue->size--;
return temp;
}
queue->firstProg->next = queue->firstProg->next->next;
queue->size--;
return temp;
}
void sortWithEnterTime(PCB pro[], int num) { //将进程按到达时间（arrivetime）全部排序
int i,j;
PCB temp;
for (i = 1; i< num; i++) {
for (j = 0; j< num - i; j++) {
if (pro[j].arrivetime >pro[j + 1].arrivetime) {
temp = pro[j];
pro[j] = pro[j + 1];
pro[j + 1] = temp;
}
}
}
}
void EnterQueueOfRuntime(PCBQueue *ready_queue,PCB *program) { //按进程的运行时间，找到就绪队列中的相应位置并插入进去
PCB *p,*q;
p=ready_queue->firstProg->next;
q=ready_queue->firstProg;
while(p) {
if(p->running_time>program->running_time) {
program->next=p;
q->next=program;
break;
}
q=p;
p=p->next;
}
if(!p) { //如果就绪队列为空或该进程的运行时间最长，则将其插入到队尾
ready_queue->LastProg->next=program;
ready_queue->LastProg=program;
program->next=NULL;
}
ready_queue->size++;
}
void EnterQueueOfPriority(PCBQueue *ready_queue,PCB *program) {
PCB *p,*q;
p=ready_queue->firstProg->next;
q=ready_queue->firstProg;
while(p) {
if(p->prioritypriority) { //优先级大的先执行
program->next=p;
q->next=program;
break;
}
q=p;
p=p->next;
}
if(!p) {
ready_queue->LastProg->next=program;
ready_queue->LastProg=program;
program->next=NULL;
}
ready_queue->size++;
}
void FCFS(PCB pro[], int num) {
int time,done_time;
int i,count,tt,pronum;
float sum_T_time,sum_QT_time;
PCB *curpro,*temp_PCB;
printf("\n\t\t\t\t\t先来先服务算法进程调度模拟\n\n");
printf("\t————————————————————————————————————————————————\n");
count=0;
PCB pro2[100];
sortWithEnterTime(pro, num); //按照进入到达时间顺序排序
PCBQueue* queue = (PCBQueue*)malloc(sizeof(PCBQueue)); //定义就绪队列
Queueinit(queue); //就绪队列初始化
EnterQueue(queue, &pro[0]); //将第一个进程送入就绪队列中
time = pro[0].arrivetime; //记录第一个进程的到达时间
pronum = 1; //记录当前的进程数量
sum_T_time = 0, sum_QT_time = 0; // sum_T_time 记录总的周转时间 ，sum_QT_time 记录总的加权周转时间
while (queue->size >0) {
curpro = poll(queue); //从进程队列中取出一个进程
if (time< curpro->arrivetime){
time = curpro->arrivetime;
}
done_time = time + curpro->running_time; // done_time 为该进程的结束时间（开始时间+CPU运行时间）
curpro->start_time=time;
curpro->done_time=done_time;
curpro->zztime = done_time - curpro->arrivetime;//周转时间
curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间
sum_T_time += curpro->zztime; // sum_T_time 总的周转时间更新
sum_QT_time += curpro->dqzztime; // sum_T_time 总的带权周转时间更新
for (tt = time; tt<= done_time && pronum< num; tt++) { //模拟进程的执行过程
if (tt >= pro[pronum].arrivetime) {
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
CopyProgram(&pro2[count],curpro);
PrintRunningprogram(&pro2[count]);
count++;
if(queue->size!=0) {
printf("\t就绪队列：\n");
printf("\t————————————————————————————————————————————————\n");
printf("\t进程 到达时间 服务时间 优先级\n");
temp_PCB=queue->firstProg->next;
for(i=queue->size; i>0; i--) {
printf("\t%s\t%d\t%d\t%d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
temp_PCB=temp_PCB->next;
}
printf("\t————————————————————————————————————————————————\n");
printf("\n\n\n");
} else {
printf("\t无进程处于就绪状态!\n");
printf("\t————————————————————————————————————————————————\n\n\n");
}
time += curpro->running_time;
if (queue->size == 0 && pronum< num) {
//防止出现前一个进程执行完到下一个进程到达之间无进程进入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
PrintSortOfRunningprogram(pro2,count);
//Print(pro2,count);
printf("\t平均周转时间为:%.2f\n", sum_T_time /num);
printf("\t平均带权周转时间为:%.2f\n",sum_QT_time/num);
}
void SJF(PCB pro[],int num) {
int time,done_time;
float sum_T_time,sum_QT_time;
int i,pronum;
PCBQueue *ready_queue;
PCB *curpro,pro1[MAXSIZE];
printf("\n\t\t\t\t\t短作业优先算法进程调度模拟\n\n");
printf("\t————————————————————————————————————————————————\n");
sortWithEnterTime(pro, num);
ready_queue = (PCBQueue*)malloc(sizeof(PCBQueue));
if(!ready_queue) {
printf("分配就绪队列头结点空间失败！");
exit(1);
}
Queueinit(ready_queue);
EnterQueueOfRuntime(ready_queue,&pro[0]);
time = pro[0].arrivetime;
pronum = 1; //记录当前的进程
sum_T_time = 0, sum_QT_time = 0;
i=0;
while(ready_queue->size>0) {
curpro=poll(ready_queue);//就绪队列中的队头进程进入CPU中运行
if(timearrivetime) { //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间
time=curpro->arrivetime;
}
done_time=time+curpro->running_time;
curpro->start_time=time;
curpro->done_time=done_time;
curpro->zztime = done_time - curpro->arrivetime;//周转时间
curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间
//打印正在运行的进程
PrintRunningprogram(curpro);
//将curpro的信息复制到pro1[i]中
CopyProgram(&pro1[i],curpro);
i++;
sum_T_time += curpro->zztime;
sum_QT_time += curpro->dqzztime;
while(pronumsize==0&&pronumsize>0) {
curpro=poll(ready_queue);//就绪队列中的队头进程进入CPU中运行
if(timearrivetime) { //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间
time=curpro->arrivetime;
}
done_time=time+curpro->running_time;
curpro->start_time=time;
curpro->done_time=done_time;
curpro->zztime = done_time - curpro->arrivetime;//周转时间
curpro->dqzztime = curpro->zztime / (curpro->running_time + 0.0);//带权周转时间
//打印正在运行的进程
PrintRunningprogram(curpro);
//将curpro的信息复制到pro1[i]中
CopyProgram(&pro1[i],curpro);
i++;
sum_T_time += curpro->zztime;
sum_QT_time += curpro->dqzztime;
while(pronumsize==0&&pronumsize >0) {
curpro = poll(queue); // 从就绪队列中取出一个进程
if (time< curpro->arrivetime) {
time = curpro->arrivetime; // 计算开始运行时间
}
if (timeslice >= curpro->running_time) { // 如果剩余时间小于时间片 则此任务完成
for (tt = time; tt<= time + curpro->running_time && pronum< num; tt++) { // 模拟进程的执行过程
if (tt >= pro[pronum].arrivetime) { // 统计从此任务开始到结束之间有几个进程到达
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
time += curpro->running_time;
curpro->running_time = 0;
curpro->done_time = time;
T_time = curpro->done_time - curpro->start_time;
QT_time = T_time / (curpro->copyRunning_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
strcpy(pro2[count].name, curpro->name) ;
pro2[count].arrivetime=curpro->arrivetime;
pro2[count].running_time= curpro->copyRunning_time;
pro2[count].priority=curpro->priority;
pro2[count].start_time=curpro->start_time;
pro2[count].done_time=curpro->done_time;
pro2[count].zztime=T_time;
pro2[count].dqzztime=QT_time;
count++;
printf("\n\t执行完成》》》进程%s！\n",curpro->name);
printf("\t————————————————————————————————————————————————\n");
if(queue->size!=0) {
printf("\t就绪队列：\n");
printf("\t————————————————————————————————————————————————\n");
printf("\t进程 到达时间 服务时间 优先级\n");
PCB* temp_PCB=queue->firstProg->next;
for(i=queue->size; i>0; i--) {
printf("\t%s\t%d\t%d\t %d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
temp_PCB=temp_PCB->next;
}
printf("\t————————————————————————————————————————————————\n\n\n");
} else {
printf("\t 无进程处于就绪状态！\n");
printf("\t————————————————————————————————————————————————\n\n\n");
}
if (queue->size == 0 && pronum< num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入
pro[pronum].start_time = pro[pronum].arrivetime;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
continue;
}
for (tt = time; tt<= time + timeslice && pronum< num; tt++) { //模拟进程的执行过程
if (tt >= pro[pronum].arrivetime) { // 统计从此任务开始到结束之间有几个进程到达
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("\n\t正在执行》》》进程%s\n",curpro->name);
printf("\t————————————————————————————————————————————————\n");
if(queue->size!=0) {
printf("\t就绪队列：\n");
printf("\t————————————————————————————————————————————————\n");
printf("\t进程 到达时间 服务时间 优先级\n");
temp_PCB=queue->firstProg->next;
for(i=queue->size; i>0; i--) {
printf("\t%s\t%d\t%d\t%d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
temp_PCB=temp_PCB->next;
}
printf("\t————————————————————————————————————————————————\n\n\n");
} else {
printf("\t 无进程处于就绪状态！\n");
printf("\t————————————————————————————————————————————————\n\n\n");
}
time += timeslice;
curpro->running_time -= timeslice;
EnterQueue(queue, curpro); //当前程序未完成 继续添加到队列中
if (queue->size == 0 && pronum< num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入
pro[pronum].start_time = pro[pronum].arrivetime;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
PrintSortOfRunningprogram(pro2,count);
printf("\t平均周转时间为:%.2f\n", sum_T_time / num);
printf("\t平均带权周转时间为:%.2f\n",sum_QT_time/num);
}
void menu() {
printf("\t\t\t\t\t<<-------------操作系统进程调度算法模拟程序----------——>>\n");
printf("\t\t\t\t\t1.先来先服务算法\n");
printf("\t\t\t\t\t2.短进程优先算法\n");
printf("\t\t\t\t\t3.高优先级算法\n");
printf("\t\t\t\t\t4.时间片轮转算法\n");
printf("\t\t\t\t\t5.退出\n");
printf("\t\t\t\t\t请选择进程调度算法:");
}
int main() {
int n, t = 1;
int proNum, choice;
PCB pro[MAXSIZE],temp_pro[MAXSIZE];
printf("\n\n\t\t\t\t\t<<-------------进程初始化----------——>>\n");
printf("\t\t\t\t\t请输入进程的个数：");
scanf("%d", &proNum);
inputProgram(pro, proNum);
while (t) {
menu();
memcpy(temp_pro, pro, (sizeof(pro) / sizeof(pro[0])) * sizeof(PCB));
scanf("%d", &n);
while (n<= 0 || n >5) {
printf("\t\t\t指令不正确，请重新输入指令： ");
scanf("%d", &n);
}
system("cls");
switch (n) {
case 1: {
FCFS(temp_pro, proNum);
break;
}
case 2: {
SJF(temp_pro, proNum);
break;
}
case 3: {
HPF(temp_pro, proNum);
break;
}
case 4: {
RR(temp_pro, proNum);
break;
}
case 5: {
t = 0;
break;
}
}
getchar();
printf("\n\t按任意键继续.......");
getchar();
system("cls");
}
system("cls");
printf("\n\n\t\t\t\t\t您已成功退出系统！！！\n");
return 0;
} （1）输入进程
（2）先来先服务调度算法（FSFS）
（3）短作业优先调度算法（SJF）
（4）高优先级调度算法
（5）时间片轮转调度算法
中间还有进程调度的详细过程图片......... （太多，放一两张）
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：操作系统——四种进程调度算法模拟实现（C语言）-创新互联
URL网址：http://dzwzjz.com/article/doiscj.html