进程调度算法的模拟实现大学本科毕业论文

本科毕业论文（设计）

题 目 进程调度算法的模拟实现 院 系 计算机科学与技术

专 业 计算机科学与技术

姓 名

学 号 指导教师 职称 讲师 申请学位 理学学士学位

2015年 5 月 5 日

进程调度算法的模拟实现

学生姓名： 指导教师：

摘 要：为了提高自己的综合编程能力，也为了能进一步熟练掌操作系统中进程调

度算法的详细实现过程，该论文采用C语言中的链队列表示各进程，研究了进程调度算：先来先服务、非抢占式短进程优先、非抢占式高优先权优先以及时间片轮转算法的模拟实现,同时还研究了用C编写的系统，如何使界面更友好、更健壮。该模拟系统实现了预定的所有功能，结果正确、清晰，但对时间片轮转调度算法的模拟实现中，其时间片固定为一，不能对比不同时间片的执行效果，有待改进。通过本模拟系统的实现，使作者对C语言的系统函数使用有了新的认识，对软件的测试过程及方法知识的应用有了更好的掌握，使作者的综合编程能力大大提高。

关键字：进程调度；先来先服务；短进程优先；进程控制块；模拟实现

The Simulation Implementation of Process Scheduling

Algorithm

Author’s Name: He Wen-long Tutor: Deng Xi-hui

ABSTRACT：In order to improve their own comprehensive

programming ability, but also in order to further skilled palm operating system process scheduling algorithm in the

implementation process in detail, the paper adopts the C chain in the queue of each process, process scheduling is studied in this paper is: first come, first service and non preemptive short process, high non preemptive priority priority priority and time slice rotation algorithm simulation, and also studies the system written in C, how to make the interface more friendly and more robust. Achieved due to all the features of the simulation system, the results correct and clear, but the time slice rotation scheduling algorithm simulation

implementation, its time slice is fixed for a, can't compare different time slices of implementation effect, needs to be improved. Through the implementation of the simulation system, the author of the C language system function using a new understanding, the application of software testing process and method of knowledge have a better grasp and make the author's comprehensive programming ability is greatly increased.

KEYWORDS：Process scheduling；First come first serve；Short

process first；Process control block；Analog implementation

目 录

1 引言 ................................................................. 1 2 进程调度及算法相关知识简介 ............................. 1

2.1 先来先服务算法.......................................... 1 2.2 短进程优先算法.......................................... 2 2.3 高优先权优先算法 ........................................ 2 2.4 时间片轮转算法.......................................... 2

3 数据结构设计 .......................................... 2

3.1 进程控制块PCB .......................................... 3 3.2 进程队列LinkQueue ...................................... 3 3.3 全局变量的使用.......................................... 4

4 系统总体模块设计 ....................................... 4 5主要界面的设计与实现 ................................... 5

5.1菜单设计 ................................................ 5 5.2菜单的实现 .............................................. 6 5.3 系统模拟动态效果的实现 .................................. 7

6 主要功能函数的实现 ..................................... 8

6.1 创建进程createProc()函数的实现 ......................... 8

6.2显示已创建进程信息showProc()函数的实现 .................. 8 6.3先来先服务算法FCFS()的实现 .............................. 9 6.4短进程优先算法与高优先权优先算法的实现 .................. 9 6.5时间片轮转算法RR()的实现 ............................... 12

7 系统运行结果 ......................................... 12 8 结束语 ............................................... 13 致谢 ................................................... 14 参考文献 ............................................... 15

1 引言

操作系统是计算机的核心总控软件，是计算机系统的指挥和管理中心，是计算机系统的灵魂。在现代的计算机通信系统中，软件开发工作占了相当大的比重，而与通信系统有关的软件一般十分庞大，也相当复杂。这些软件还要大量地与操作系统内核作深层次的交互，以进行信息的传输、控制和实现各种通信协议。而进程管理是操作系统中的非常重要的部分，掌握进程管理部分的原理是为了更加深入的学好操作系统这门课程。

本文讨论了进程最重要数据结构进程控制块的表示，进程不同状态队列的存储，在链队列的数据结构上实现先来先服务、短进程优先、高优先权优先和时间片轮转等四种进程调度算法的实现。同时研究了用C编写系统，如何使系统界面友好健壮。

2 进程调度及算法相关知识简介

在操作系统中，进程调度也称为低级调度，其调度对象是进程。用户进程数一般都多于处理机数，系统进程也同样需要使用处理机，这将导致它们互相争夺处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行，这些策略就是进程调度算法[1]。常用的进程调度算法有先来先服务、短进程优先、高优先权优先和时间片轮转等。

2.1 先来先服务算法

先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。[2]

1

2.2 短进程优先算法

短进程优先（SPF）调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SPF调度算法能有效地降低进程的平均等待时间，提高系统吞吐量。该算法对长进程不利，完全没考虑进程的紧迫程度。[3]

2.3 高优先权优先算法

在批处理系统中，短进程优先算法是一种比较好的算法，其主要不足之处是长进程的运行得不到保证。如果我们能为每个进程引入动态优先权，并使进程的优先级随着等待时间的增加而以速率提高，则长进程在等待一定的时间后，必然有机会分配到处理机。该动态优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间 ，即：优先权=响应时间/要求服务时间。

2.4 时间片轮转算法

时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

本模似实现系统为了评价算法的优劣，主要以周转时间和带权周转时间为准则的。进程的周转时间是进程到达就绪队列，到进程完成为止的这段时间。进程的周转时间与系统为它服务的时间之比，则称为进程的带权周转时间。

3 数据结构设计

当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要

2

从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答，这个数学模型就是数据结构。

3.1 进程控制块PCB

为了描述和控制进程的运行，与进程相关的一个很重要的数据结构是进程控制块PCB（Process Control Block），它是进程存在的唯一标志，是操作系统中最重要的数据结构。本系统为了模拟实现对并发执行进程的调度，为PCB设计的数据结构是一个结构体PcbNode，其类型定义是：

typedef struct PcbNode {

char int float float float short

name[NAME_MAX_LEN]; id;

//进程名 //进程号 //进程到达的时间 //进程需要执行的时间 //该进程结束时间

//进程状态

//指向下一进程的指针

arriveTime; runTime;

finalTime; status;

struct PcbNode* next; }PcbNode,*PcbPoint;

3.2 进程队列LinkQueue

在操作系统中进程有多种状态，因为本系统主要模拟进程调度，是从就绪队列中选择一个进程，使其得到CPU运行，所以没涉及到阻塞状态。为记录不同状态的进程，该系统将不同状态的进程组织为链队列。

进程队列的链队列结构为：

typedef struct {

PcbPoint front; //队首指针 PcbPoint rear; //队尾指针 }LinkQueue;

3

3.3 全局变量的使用

为了实现各个进程调度算法，本系统使用了五个全局变量。

因各种调度算法都是从就绪队列中选择进程进行调度，故将就绪队列设计为LinkQueue类型的全局变量，其变量名为readyQueue。

为实现时间片轮转算法，本系统使用了三个指向结构体的指针：reaLQ、runLQ、finLQ，reaLQ表示当前时间尚未开始运行的就绪队列，runLQ表示已开始运行但未结束的各个进程组成的队列，finLQ则记录当前已经执行完的进程。

各个进程调度算法，都涉及到时间，故将时间设为全局变量current，以秒为单位输入，其类型为float。在本系统中，current在先来先服务、短进程优先和高优先权优先算法中表示当前时间，而在时间片轮转算法中，current表示时间片。

4 系统总体模块设计

系统总体可分为四个大的模块，即创建进程、输出进程、进程调度算法以及显示系统信息，而进程调度算法又可分为先来先服务、短进程优先、高优先权优先和时间片轮转四个模块。其总体模块如图4-1所示。

图4-1 系统总体模块图

为实现系统以上各个模块，本模拟系统将功能相对完整的代码定义为一个函数。本系统中主要的函数及其功能如表4-1所示。

表4-1 系统主要函数及其功能

函数名 showMainMenu() showSubMenu() createProc() 功能说明 显示系统主菜单 显示进程调度子菜单 创建一个不带有头结点的按到达时间有序的链队列 4

showProc(lq) FCFS(lq) SPF_FPF(lq,flag) RR(lq) copyQueue(lq1,lq2) 输出进程信息 先来先服务算法 短进程优先或高优先权算法，具体由flag确定 时间片轮转调度算法 复制进程队列 refrashCon(phead,current,con) 统计进程队列中到达时间大于current的进程数 readyproc() slicerun() getLev(const PcbPoint &pcb) 将current之前到来的就绪进程全部插入执行队列 对满足执行条件的各个进程分配时间片并执行 求进程的动态优先权

5主要界面的设计与实现

5.1菜单设计

本模拟系统主要有两个菜单，一个主菜单，列出了系统具有的五项功能，可以输入相应字符进行选择操作，其界面如图5-1所示。

图 5-1 主菜单

在主菜单是输入字符C就进入了选择调度算法子菜单，其界面如图5-2所示。

5

图 5-2 选择调度算法子菜单

在主菜单输入字符D就进入了系统信息子菜单，显示本系统的功能信息，其界面设计如图5-3所示。

图 5-3 选系统信息子菜单

5.2菜单的实现

主菜单界面的实现方法主要是调用C语言中的系统函数system()，其参数不同实现不同功能。system(\实现清屏，system(\设置默认控制台前景和背景颜色，system(\〖进程管理模拟器〗 Version[1.0]\设置界面的标题和版本信息。其它就是对菜单项的格式输出。showMainMenu()函数的实现代码如下所示。

void showMainMenu() //显示主菜单 {

system(\ cout<

6

cout<<\ cout<<\ cout<<\

╔════════════╗\\n\ ║ ☆ 进 程 管 理 器 ☆ ║\\n\ ╚════════════╝\\n\

cout<<\n\

cout<<\欢迎使用该系统,请选择菜单！---------\\n\ cout<

[A] 创建进程\\n\\n\[B] 浏览进程信息\\n\\n\[C] 选择调度算法\\n\\n\[D] 系统信息\\n\\n\[E] 退出程序\\n\

cout<<\\\n\

cout<<\请您键入菜单字母代码：\}

子菜单的实现是利用showSubMenu()函数，其实现方法类似主菜单的实现。在此不再赘述。

5.3 系统模拟动态效果的实现

在创建进程，输入要创建的进程信息后，系统会有一个延时，以显示动态效果。其实现方法主要调用C语言系统函数sleep()函数,其实现关键代码如下：

Sleep(200); //使程序暂停200秒

printf(\系统正在创建进程中，请稍候...\\n\ Sleep(500);

printf(\使光标回到本行行首 printf(\ for(i=0;i<65;i++) {

Sleep(18); printf(\

7

}

6 主要功能函数的实现

本系统中主要的功能函数有创建进程，显示已创建进程的信息，先来先服务调度算法，短作业优先调度算法，高优先权优先算法，时间片轮转算法。

6.1 创建进程createProc()函数的实现

因为各个调度算法都与进程到达的时间有关，所以本系统创建的进程是不带头结点的且按到达时间有序的链队列。在创建进程时，首先设定创建的进程数目，然后分别输入进程的名称、到达时间、服务时间。创建进程的主要代码是：

for(int i=1;i<=no;i++) //no是输入的进程数

{

PcbNode *temp=new PcbNode;

cout<<\第 \个进程的名称 (16字符以内):\cin>>temp->name;

cout<<\进程的到达时间 (以“秒”为单位的浮点数):\cin>>temp->arriveTime;

cout<<\进程的服务时间 (以“秒”为单位的浮点数):\cin>>temp->runTime; cout<status=R; temp->next=NULL;

//将新创建的temp结点插入就绪队列qp1使其依据arriveTime有序 insert(qp1,temp);

}

6.2显示已创建进程信息showProc()函数的实现

该函数是把已创建好的进程信息显示出来，其实现方法主要是使用C语言中的setw()函数来控制输出格式，然后通过一个指针，指针初始指向进程队列队首，不断移动指针直到队列尾，在移动过程中以指定位置格式输出各个指针的name、

8

arriveTime以及runTime值即可。

6.3先来先服务算法FCFS()的实现

因就绪队列按到达时间有序排列，所以，先来先服务算法只需创建好的进程顺序输出即可模拟进程的执行，为使用户能直观看到算法执行效果，需求每个进程的周转时间和带权周转时间，运行结果同样由setw()函数控制格式输出，其主要代码如下：

while(p1!=NULL) {

float t1,t2,t3; float t4;

t1=p1->arriveTime;

t2=p1->runTime; //t2 运行时间 current+=t2;

t3=current-t1; //t3 周转时间 t4=float(t3)/t2; //t4 带权周转时间 cout<name<

t2<next; }

//遍历队列全部调度,并计算打印各个参数

6.4短进程优先算法与高优先权优先算法SPF_FPF(slq,flag)的实现

进程调度的调度方式有抢占式和非抢占式，本模拟系统采用的是非抢占方式。在采用这种调度方式时，一旦把处理机分配给某个进程后，就让它一直运行下去，直到进程完成，自愿释放处理机或发生某事件而被阻塞时，才把处理机分配给其它进程。

短进程优先调度算法的每次调度是从就绪队列中选择服务时间最短的执行，而高优先权优先调度算法则是从就绪队列中选择优先权最高的执行，只是选择标准不同而其它过程类似，所以本模拟系统将二者定义为一个函数SPF_FPF(LinkQueue slq,int flag)，具体算法由第二个参数flag确定。

高优先权优先调度，其优先权有两种：静态优先权和动态优先权。本系统采用调

9

度性能较好的动态优先权。其动态变化规律是等待时间与要求服务时间的和除以服务时间。

SPF_FPF(LinkQueue slq,int flag)函数中，根据flag的值决定具体算法，flag值为1是短进程优先调度，flag值为2是高优先权优先算法。其关键代码如下：

current=0.0; //系统时间清零 float t1,t2,t3,t4; while(phead->next!=NULL)

{ //统计进程队列中到达时间大于current的进程数con int con=0;

refrashCon(phead,current,con); // cout<<\ switch(con)

{

case 0:

current++;

break;

case 1://只有一个进程到达，直接运行，计算并输出各个参数

pfront=phead->next;

t1=pfront->arriveTime; t2=pfront->runTime;

current+=t2;

t3=current-t1;

t4=t3/t2;

cout<name<

setw(10)<

removePCB(phead); //该进程运行完毕，从就绪队列中删除

break;

default://有多个进程

//查找最短进程或优先权最高进程,返回它的前驱

ptem=runSche(phead,con,flag);

//执行ptem的下一个进程，计算并输出相应信息 pfront=ptem->next ;

t1=pfront-

10

本文来源：https://www.bwwdw.com/article/wa88.html