进程调度算法的模拟实现.pdf

课程设计报告

课程名称：操作系统

信息工程学院
题目：进程调度算法的模拟实现

一、设计目的

本课程设计是学习完“计算机操作系统”课程后进行的一次全面的综合训练，
通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理
论和重要算法的理解，加强学生的动手能力。本课程设计是在多道程序和多任务
系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程
数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度
策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固
和加深处理机调度的概念。
二、设计内容

（1）概述
选择一个调度算法，实现处理机调度。
设计要求：
1）进程调度算法包括：先来先服务算法，时间片轮转算法，短进程优先算法，
动态优先级算法。
2）可选择进程数量
3）本程序包括四种算法，用C或C++语言实现，执行时在主界面选择算法（可
用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），
执行，显示结果。

（2）设计原理

（1）先来先服务算法FCFS

每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作
业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。

（2）时间片轮转法RR

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，
把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百
ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此
信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配
给就绪队列中新的队首进程，同时也让它执行一个时间片。

(3)短进程优先算法SPF

1
短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将
处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃
处理机时再重新调度。

（4A）动态优先级算法

优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处
理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先
权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度
性能。

设计思想
首先开辟一个链表空间存放输入的原始作业的数据；然后设计的四种算法分
别开辟四个链表空间，以实现不改变输入作业的原始数据就可以同时进行四种算
法的调用，以对比四种算法的优劣性。

设计中所包括的函数有：
voidinput();//输入生成HEAD链表函数，用于存放输入作业的所有信息
voidconnect();//连接结点函数
voidmyprintf();//打印我的界面
voidprintftable();//打印作业状态
voidsortFCFS();//先来先服务复制HEAD并形成先来先服务的headFCFS链表
voidsortSJF();//短作业优先复制HEAD并形成短作业优先链表headSJF
voidsortHRN();//高响应比函数，包括了执行
voidsortSUPER();//高优先权函数复制HEAD形成headSUPER链表
voidchoose();//功能及算法选择函数
voidexecute(JCB*p);//执行函数
voidcopynode(JCB*p1,JCB*p2);//复制结点函数
voidprintffinish(JCB*p);//打印一个作业完成时的周转时间等统计
JCB*delenode(JCB*ph,JCB*P);//删除并返回结点，用于高响应比算法
Voidprintfall();//打印用过四种算法的周转时间和带权周转时间
Voiddestroy(JCB*P);//销毁函数，释放空间实现重新输入作业

2

（3）详细设计及编码
算法使用流程图

开始

初始化PCB，输入进程信
息

RR算法，按照时间片依次
执行进程，ALLTIME—=4.

SPS算法，按照ALLTIME

从小到大依次输出

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

到小输出，进程执行依次
P-3，就绪队列中的进程P+1

结束

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

算法：

voidFCFS()
{

Node*p=head->next;
while(p!=NULL)

{

3
执行进程

p=p->next;
}

cout<<endl;
所有进程都执行完成
}

2.短进程优先算法
先找到运行时间最短的程序，然后执行，再从剩余的程序中找到运行时间最
短的在执行，依次每次都执行运行时间最短的