alltime

课程设计报告

课程名称：操作系统

信息工程学院

1

题目：进程调度算法的模拟实现

一、设计目的

本课程设计是学习完“计算机操作系统”课程后进行的一次全面的综合训练，

通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理

论和重要算法的理解，加强学生的动手能力。本课程设计是在多道程序和多任务

系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程

数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度

策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固

和加深处理机调度的概念。

二、设计内容

（1）概述

选择一个调度算法，实现处理机调度。

设计要求：

1）进程调度算法包括：先来先服务算法，时间片轮转算法，短进程优先算法，

动态优先级算法。

2）可选择进程数量

3）本程序包括四种算法，用C或C++语言实现，执行时在主界面选择算法（可

用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），

执行，显示结果。

（2）设计原理

（1）先来先服务算法FCFS

每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作

业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。

（2）时间片轮转法RR

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，

把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百

ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此

信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配

给就绪队列中新的队首进程，同时也让它执行一个时间片。

(3)短进程优先算法SPF

2

短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将

处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃

处理机时再重新调度。

（4A）动态优先级算法

优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处

理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先

权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度

性能。

设计思想

首先开辟一个链表空间存放输入的原始作业的数据；然后设计的四种算法分

别开辟四个链表空间，以实现不改变输入作业的原始数据就可以同时进行四种算

法的调用，以对比四种算法的优劣性。

设计中所包括的函数有：

voidinput();//输入生成HEAD链表函数，用于存放输入作业的所有信息

voidconnect();//连接结点函数

voidmyprintf();//打印我的界面

voidprintftable();//打印作业状态

voidsortFCFS();//先来先服务复制HEAD并形成先来先服务的headFCFS链表

voidsortSJF();//短作业优先复制HEAD并形成短作业优先链表headSJF

voidsortHRN();//高响应比函数，包括了执行

voidsortSUPER();//高优先权函数复制HEAD形成headSUPER链表

voidchoo();//功能及算法选择函数

voidexecute(JCB*p);//执行函数

voidcopynode(JCB*p1,JCB*p2);//复制结点函数

voidprintffinish(JCB*p);//打印一个作业完成时的周转时间等统计

JCB*delenode(JCB*ph,JCB*P);//删除并返回结点，用于高响应比算法

Voidprintfall();//打印用过四种算法的周转时间和带权周转时间

Voiddestroy(JCB*P);//销毁函数，释放空间实现重新输入作业

3

（3）详细设计及编码

算法使用流程图

1.先来先服务算法

对于先到达的进程优先分配CPU，按照先来先服务的原则依次执行各进

程。

算法：

voidFCFS()

{

Node*p=head->next;

while(p!=NULL)

{

初始化PCB，输入进程信

息

SPS算法，按照ALLTIME

从小到大依次输出

RR算法，按照时间片依次

执行进程，ALLTIME—=4.

优先级算法，按照优先从大

到小输出，进程执行依次

P-3，就绪队列中的进程P+1

结束

开始

4

cout<<"执行进程"<;

p=p->next;

}

cout<

cout<<"所有进程都执行完成"<

}

2.短进程优先算法

先找到运行时间最短的程序，然后执行，再从剩余的程序中找到运行时间最

短的在执行，依次每次都执行运行时间最短的，直到程序执行完毕。

算法：

voidSJF()

{

Node*p;

Node*pmin;

while(head2->next!=NULL)

{

pmin=head2->next;

for(p=head2->next;p!=NULL;p=p->next)

{

if(pmin->e>p->e)

pmin=p;

}

cout<<"执行剩余区间长度最短的进程"<;

for(p=head2;p!=NULL;p=p->next)

{

if(p->next==pmin)

{

p->next=p->next->next;

free(pmin);

}

5

}

}

printf("n");

printf("所有进程都执行完成。nn");

}

3，时间片轮转算法

按照轮转的次序分配给每个程序一定的时间执行，执行完成后执行后面的

进程，依次循环执行直到所有进程执行完成。

算法：

voidRR(intm)

{

Node*p;

while(head1->next!=NULL)

{

p=head1->next;

Node*prep=head1;

Node*q;

while(p!=NULL)

{

cout<<"执行进程一个时间片"<;

for(q=head1;q->next!=NULL;q=q->next)

{

if(q->next==p)

{

p->e-=4;

p->e+=4;

}

}

if(p->e<=0)

6

{

cout<<"进程已执行完成"<;

prep->next=prep->next->next;

free(p);

p=prep->next;

}

el

{

prep=prep->next;

p=p->next;

}

}

cout<

cout<<"进入下一次轮转"<

}

cout<<"所有进程都执行完成"<

}

4.动态优先权算法

按照优先级从高到低依次执行程序。

算法：

voidSearchMaxPRI(intm)

{

Node*p=head->next;

Node*q=head->next;

Node*q0=head;

while(q!=NULL)

{

if(q->e==0)

{

7

cout<<"进程已执行完成"<;

n--;

q0->next=q0->next->next;

free(q);

q=q0->next;

}

el

{

if(q->ty>p->ty)

p=q;

q0=q0->next;

q=q->next;

}

}

if(n>0)

action(p);

}

（4）运行结果分析

（运行界面截图、输入输出数据说明和分析等）

先输入系统进程数，系统自动分配进程

先来先服务调度：

最短进程调度：

时间片轮转调度：

动态优先级调度：

8

（5）设计小结

课程设计是我们专业课程知识综合应用的实践训练，也是为我们以后的工作夯实基础。

通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法

——先来先服务算法，短进程优先调度算法，时间片轮转调度算法，动态优先级

调度有了更深刻的理解和掌握，使我能够为进程调度选择适当的算法，提高CPU

工作效率。进行进程调度程序设计的过程中，得到老师的大力指导和同学的支持，在此向

他们表示感谢。经过自己的动手操作和同学老师的指导我成功的做出了课程设计

自己感到很高兴。在整个过程中自己也感受到了集体团结的力量，今后无论是在

工作还是学习中我都会发样这种精神。

（6）参考文献

（参考的书籍等，列出书名、作者、出版社及出版时间等，例如：

[1]计算机操作系统(第3版)，汤小丹，西安电子科技大学出版社，2007年7月

[2]C语言程序设计，孟庆昌，人民邮电出版社，2006年4月）

9

源代码：

#include

#include

#include

#include

#include

#defineTRUE1

#defineFALSE0

#defineOK1

typedefstructPCB

{

intID;

intPriority;

intCPUTime;

intALLTime;

intStatus;

}PCB;

typedefPCBDt;

typedefstructNode

{

Dtdata;

structNode*next;

10

}Node;

Node*head=(Node*)malloc(sizeof(Node));

Node*head1=(Node*)malloc(sizeof(Node));

Node*head2=(Node*)malloc(sizeof(Node));

intn;

voidcreate(intn)

{

inti=1;

srand((int)time(0));

head->next=NULL;

Node*q=head;

cout<<"优先数优先级CPUTimeAllTimeStatus"<

while(i<=n)

{

Node*p=(Node*)malloc(sizeof(Node));

p->=i;

p->e=0;

p->=0;

p->ty=rand()%10+1;

p->e=rand()%8+1;

cout<<""<<<""<ty<<"

"<<

p->e<<""<e<<"

"<<

p->next=NULL;

q->next=p;

q=q->next;

i++;

}

Node*p0=head1;

11

head1->next=NULL;

for(q=head->next;q!=NULL;q=q->next)

{

Node*r=(Node*)malloc(sizeof(Node));

r->=q->;

r->e=q->e;

r->=q->;

r->ty=q->ty;

r->e=q->e;

p0->next=r;

r->next=NULL;

p0=p0->next;

}

Node*p1=head2;

head2->next=NULL;

for(q=head->next;q!=NULL;q=q->next)

{

Node*k=(Node*)malloc(sizeof(Node));

k->=q->;

k->e=q->e;

k->=q->;

k->ty=q->ty;

k->e=q->e;

p1->next=k;

k->next=NULL;

p1=p1->next;

}

}

voidFCFS()

12

{

Node*p=head->next;

while(p!=NULL)

{

cout<<"执行进程"<;

p=p->next;

}

cout<

cout<<"所有进程都执行完成"<

}

voidSJF()

{

Node*p;

Node*pmin;

while(head2->next!=NULL)

{

pmin=head2->next;

for(p=head2->next;p!=NULL;p=p->next)

{

if(pmin->e>p->e)

pmin=p;

}

cout<<"执行剩余区间长度最短的进程"<;

for(p=head2;p!=NULL;p=p->next)

{

if(p->next==pmin)

{

p->next=p->next->next;

free(pmin);

13

}

}

}

cout<

cout<<"所有进程都执行完成"<

}

voidaction(Node*p)

{

Node*q=head->next;

while(q!=NULL)

{

cout<<<"执行一个时间片的进程"<

if(q!=p)

q->ty=q->ty+1;

el

{

q->ty=q->ty-3;

if(q->e>4)

q->e-=4;

el

q->e=0;

q->=1;

}

q=q->next;

}

}

voidSearchMaxPRI(intm)

{

14

Node*p=head->next;

Node*q=head->next;

Node*q0=head;

while(q!=NULL)

{

if(q->e==0)

{

cout<<<"进程已执行完成"<

n--;

q0->next=q0->next->next;

free(q);

q=q0->next;

}

el

{

if(q->ty>p->ty)

p=q;

q0=q0->next;

q=q->next;

}

}

if(n>0)

action(p);

}

voidRR(intm)

{

Node*p;

while(head1->next!=NULL)

15

{

p=head1->next;

Node*prep=head1;

Node*q;

while(p!=NULL)

{

cout<<<"执行进程一个时间片"<

for(q=head1;q->next!=NULL;q=q->next)

{

if(q->next==p)

{

p->e-=4;

p->e+=4;

}

}

if(p->e<=0)

{

cout<<<"进程已执行完成"<

prep->next=prep->next->next;

free(p);

p=prep->next;

}

el

{

prep=prep->next;

p=p->next;

}

}

cout<

16

cout<<"进入下一次轮转"<

}

cout<<"所有进程都执行完成"<

}

intmain()

{

cout<<"请输入系统进程数："<

cin>>n;

intm=n;

if(n==0)

cout<<"此时没有就绪进程"<

el

{

create(n);

cout<

cout<<"先来先服务调度"<

FCFS();

cout<

cout<<"短进程优先调度"<

SJF();

cout<

cout<<"动态优先级调度"<

while(head->next!=NULL)

{

SearchMaxPRI(m);

}

cout<<"所有进程都执行完成"<

cout<

cout<<"时间片轮转调度"<

RR(m);

17

}

}