OS进程调度算法.docx
- 文档编号:17154898
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:46
- 大小:205.44KB
OS进程调度算法.docx
《OS进程调度算法.docx》由会员分享,可在线阅读,更多相关《OS进程调度算法.docx(46页珍藏版)》请在冰点文库上搜索。
OS进程调度算法
实验2进程调度算法
2.1实验目的
进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。
在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。
本实验模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不同调度算法的优缺点。
下面回顾一下进程管理的相关内容。
2.1.1进程控制块
为了管理和控制进程,系统在创建每一个进程时,都为其开辟一个专用的存储区,用以随时记录它在系统中的动态特性。
而当一个进程被撤消时,系统就收回分配给它的存储区。
通常,把这一存储区称为该进程的“进程控制块”(ProcessControlBlock)。
由于PCB是随着进程的创建而建立,随着进程的撤消而取消的,因此系统是通过PCB来“感知”一个个进程的,PCB是进程存在的唯一标志。
随操作系统的不同,PCB的格式、大小以及内容也不尽相同。
一般地,在PCB中大致应包括如下4方面的信息。
·标识信息:
进程名等。
·说明信息:
进程状态、程序存放位置、数据存放位置等。
·现场信息:
通用寄存器内容、控制寄存器内容、断点地址等。
·管理信息:
进程优先数、队列指针等。
2.1.2进程控制块队列
在多道程序设计环境里,同时会创建多个进程。
当计算机系统只有一个CPU时,每次只能让一个进程运行,其他的进程或处于就绪状态,或处于阻塞状态。
为了对这些进程进行管理,操作系统要做三件事。
(1)把处于相同状态的进程的PCB,通过各自的队列指针链接在一起,形成一个个队列。
通常有运行队列、就绪队列、阻塞队列。
(2)为每一个队列设立一个队列头指针,它总是指向排在队列之首的进程的PCB。
(3)排在队尾的进程的PCB,它的“队列指针”项内容应该为“NULL”,或一个特殊的符号,以表示这是该队的队尾PCB。
在单CPU系统中,任何时刻都只有一个进程处于运行状态,因此运行队列中只能有一个PCB;系统中所有处于就绪状态的进程的PCB排成一队,称其为“就绪队列”。
一般地,就绪队列中会有多个进程的PCB排在里面,它们形成处理机分配的候选对象。
如果就绪队列里没有PCB存在,则称该队列为空;所有处于阻塞状态进程的PCB,应该根据阻塞的原因进行排队,每一个都称为一个“阻塞队列”。
比如等待磁盘输入/输出进程的PCB排成一个队列,等待打印机输出进程的PCB排成一个队列等。
所以,系统中可以有多个阻塞队列,每个阻塞队列中可以有多个进程的PCB,也可以为空。
2.1.3进程调度算法
进程调度算法用于确定就绪队列中的哪一个进程即将获得CPU。
常用的进程调度算法有先来先服务法、时间片轮转法、优先数法等。
1.先来先服务调度算法
先来先服务调度算法的基本思想是:
以到达就绪队列的先后次序为标准来选择占用处理机的进程。
一个进程一旦占有处理机,就一直使用下去,直至正常结束或因等待某事件的发生而让出处理机。
采用这种算法时,应该这样来管理就绪队列:
到达的进程的PCB总是排在就绪队列末尾;调度程序总是把CPU分配给就绪队列中的第一个进程使用。
2.时间片轮转法
时间片轮转调度算法的基本思想是:
为就绪队列中的每一个进程分配一个称为“时间片”的时间段,它是允许该进程运行的时间长度。
在使用完一个时间片后,即使进程还没有运行完毕,也要强迫其释放处理机,让给另一个进程使用。
它自己则返回到就绪队列末尾,排队等待下一次调度的到来。
采用这种调度算法时,对就绪队列的管理与先来先服务完全相同。
主要区别是进程每次占用处理机的时间由时间片决定,而不是只要占用处理机就一直运行下去,直到运行完毕或为等待某一事件的发生而自动放弃。
3.优先数调度算法
优先数调度算法的基本思想是:
为每一个进程确定一个优先数,进程就绪队列按照优先数排序。
如何确定进程的优先数(也就是进程的优先级)?
可以从如下几个方面考虑。
(1)根据进程的类型。
系统中既有系统进程,又有用户进程。
系统进程完成的任务是提供系统服务,分配系统资源,因此,给予系统进程较高的优先数能够提高系统的工作效率。
(2)根据进程执行任务的重要性。
重要性和紧迫性高的进程应当被赋予较高的优先级。
(3)根据进程程序的性质。
一个CPU繁忙的进程,由于需要占用较长的运行时间,影响系统整体效率的发挥,因此只能给予较低的优先数。
一个I/O繁忙的进程,给予它较高的优先数后,就能充分发挥CPU和外部设备之间的并行工作能力。
(4)根据对资源的要求。
系统资源有处理机、内存储器和外部设备等。
可以按照一个进程所需资源的类型和数量,确定它的优先数。
比如给予占用CPU时间短或内存容量少的进程以较高的优先数,这样可以提高系统的吞吐量。
(5)根据用户的请求。
系统可以根据用户的请求,给予它的进程很高的优先数,作“加急”处理。
4.多级队列调度算法
多级队列调度算法也称多级反馈队列调度算法,它是时间片调度算法与优先数调度算法的结合。
实行这种调度算法时,系统中将维持多个就绪队列,每个就绪队列具有不同的调度级别,可以获得不同长度的时间片。
例如,系统维持N个就绪队列,第1级就绪队列中进程的调度级别最高,可获得的时间片最短,第N级就绪队列中进程的调度级别最低,可获得的时间片最长。
具体的调度方法是:
创建一个新进程时,它的PCB将进入第1级就绪队列的末尾。
对于在第1级到第N-1级队列中的进程,如果在分配给它的时间片内完成了全部工作,那么就撤离系统;如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生,那么就进入相应的阻塞队列里等待。
在所等待的事件出现时,仍回到原队列末尾,参与下一轮调度(也就是每个队列实行先来先服务调度算法);如果用完了时间片还没有完成自己的工作,那么只能放弃对CPU的使用,降到低一级队列的末尾,参与那个队列的调度。
对位于最后一个队列里的进程,实行时间片轮转调度算法。
整个系统最先调度1级就绪队列;只有在上一级就绪队列为空时,才去下一级队列调度。
当比运行进程更高级别的队列中到达一个进程(可以肯定,在此之前比运行进程级别高的所有队列全为空)时,系统将立即停止当前运行进程的运行,让它回到自己队列的末尾,转去运行级别高的那个进程。
可以看出,多级队列调度算法优先照顾I/O繁忙的进程。
I/O繁忙的进程在获得一点CPU时间后就会提出输入/输出请求,因此它们总是被保持在1、2级等较前面的队列中,总能获得较多的调度机会。
对于CPU繁忙的进程,它们需要较长的CPU时间,因此会逐渐地由级别高的队列往下降,以获得更多的CPU时间,它们“沉”得越深,被调度到的机会就越少。
但是,一旦被调度到,就会获得更多的CPU时间。
2.2实验要求
2.2.1界面要求
实验要求采用简单的控制台界面,包括一级功能菜单,如图2-1所示。
图2-1界面要求
2.2.2功能要求
实验应该包括以下功能:
1.运行先来先服务进程调度算法;
2.运行时间片轮转进程调度算法;
3.运行优先数进程调度算法;
4.运行多级反馈队列进程调度算法;
5.显示就绪进程队列;
6.显示运行进程队列;
7.显示阻塞进程队列;
8.创建新进程;
9.阻塞进程;
10.唤醒进程;
11.删除进程;
12.退出程序。
2.3实验步骤
2.3.1总体设计
确定程序包含多少个模块,每个模块有哪些功能、包括哪些函数,模块之间的调用关系如何。
由于本实验并不复杂,所以只用一个模块实现。
要求宏、数据结构、全局变量和函数原型放在头文件中,而函数实现放在源文件中。
假设头文件名为process_schedule.h,源程序文件名为process_schedule.cpp。
实验中用到的主要数据结构是进程控制块,其结构如图2-2所示。
实验中用到1个宏和8个全局变量,如图2-3所示。
实验中用到的主要函数有10个,如图2-4所示。
数据项
作用
next
前向指针,指向下一个进程控制块,用来构成进程队列
process_name
进程名称
process_number
进程号,当进程有相同名称时,用来区分进程
process_start_moment
进程启动时刻
process_need_time
进程要求运行时间
process_time_slice
时间片
process_priority
优先数
图2-2进程控制块
全局变量名称
作用
MAX_PROCESS
程序最多能处理的进程数
process_number
存放下一个被创建进程的进程号
pcb_table
进程控制块表
pcb_run
进程运行队列头指针
pcb_free
进程空闲队列头指针
pcb_ready
进程就绪队列头指针
pcb_ready_rear
进程就绪队列尾指针
pcb_blocked
进程阻塞队列头指针
pcb_blocked_rear
进程阻塞队列尾指针
图2-3宏和全局变量
函数名称
作用
main
初始化进程队列,并管理主菜单命令
init_pcb_table
初始化进程空闲队列
display_process_queue
以表格的形式显示进程队列
create_process
创建进程
block_process_by_name
阻塞进程
wakeup_process
唤醒进程
FCFS
先进先出进程调度算法
RR
时间片轮转进程调度算法
HPF
优先数进程调度算法
MFBQ
多级反馈队列进程调度算法
图2-4函数名称及作用
2.3.2详细设计及实现
1.头文件
头文件中含有图2-2、图2-3和图2-4的内容。
#include
#include
#include
#include
#include
#defineMAX_PROCESS10
intprocess_number=0;//下一个可用的进程编号
typedefstructpcb{
structpcb*next;//下一个进程控制块指针
charprocess_name[20];//进程名
intprocess_number;//进程编号
intprocess_start_moment;//进程启动时刻
intprocess_need_time;//要求运行时间
intprocess_time_slice;//时间片
intprocess_priority;//优先数
}PCB;//自定义数据类型:
进程控制块
PCBpcb_table[MAX_PROCESS];//进程控制块表
PCB*pcb_run=NULL;//进程运行队列头指针
PCB*pcb_free=NULL;//进程空闲队列头指针
PCB*pcb_ready=NULL;//进程就绪队列头指针
PCB*pcb_ready_rear=NULL;//进程就绪队列尾指针
PCB*pcb_blocked=NULL;//阻塞队列头指针
PCB*pcb_blocked_rear=NULL;//阻塞队列尾指针
voidinit_pcb_table();//初始化进程控制块表
voidprint_space(intnum);//显示若干个空格
voiddisplay_process_queue(PCB*queue);//显示进程队列
PCB*create_process();//创建进程函数,成功时返回新创建进程的PCB,失败时返回NULL。
voidblock_process_by_name();//阻塞指定名称的进程。
voidwakeup_process();//唤醒进程
voidFCFS();//先来先服务进程调度算法
voidRR();//时间片轮转进程调度算法
voidHPF();//优先数进程调度算法
voidMFBQ();//多级反馈队列进程调度算法
2.主函数main
主函数用来初始化进程队列,显示菜单,接收用户输入的菜单选项,并根据用户的选项执行相应的功能。
其处理流程如下:
main(){
初始化进程控制块表;
while
(1){
显示菜单;
输出提示信息;
接收用户输入的选项,如果输入不是数字1~8或者字母a~d则重新输入;
switch(选项){
case‘1’:
调用先来先服务进程调度算法;
break;
case‘2’:
调用时间片轮转进程调度算法;
break;
case‘3’:
调用优先数进程调度算法;
break;
case‘4’:
调用多级反馈队列进程调度算法;
break;
case‘5’:
显示就绪进程队列;
break;
case‘6’:
显示阻塞进程队列;
break;
case‘7’:
显示运行进程队列;
break;
case‘a’:
调用创建进程函数;
break;
case‘b’:
调用删除进程函数;
break;
case‘c’:
调用阻塞进程函数;
break;
case‘d’:
调用唤醒进程函数;
break;
case‘8’:
返回;
}
}
返回;
}
说明:
通常用循环语句和多分支语句实现菜单。
while语句实现菜单的循环选择,switch语句实现功能分支,只有当用户输入数字8时,才会跳出循环,结束程序的执行,输入其它合法数字或者字符时,程序将执行对应的功能,并在执行完功能后,重新显示菜单,供用户做下一步选择。
main函数的源代码如下:
#include"process_schedule.h"//包含头文件
intmain(intargc,char*argv[]){
charselect;//存放用户选择的菜单项
init_pcb_table();//初始化进程控制块表
while
(1){
printf("|----------MAINMENU-------------|\n");//显示菜单项
printf("|1:
firstcomefirstserved|\n");
printf("|2:
roundrobin|\n");
printf("|3:
highestpriorityfirst|\n");
printf("|4:
multi_levelfeedbackqueue|\n");
printf("|5:
displayreadyprocessqueue|\n");
printf("|6:
displayblockedprocessqueue|\n");
printf("|7:
displayrunningqueue|\n");
printf("|a:
createaprocess|\n");
printf("|b:
deleteaprocess|\n");
printf("|c:
blockaprocess|\n");
printf("|d:
wakeupaprocess|\n");
printf("|8:
exit|\n");
printf("|-----------------------------------|\n");
printf("selectafunction(1~8,a~d):
");//输出提示信息
do{
select=(char)getch();//接收用户的选项
}while(!
((49<=select&&select<=56)||(97<=select&&select<=100)));
system("cls");//清屏
switch(select){//由选项控制程序功能
case'1':
FCFS();
break;
case'2':
RR();
break;
case'3':
HPF();
break;
case'4':
MFBQ();
break;
case'5':
printf("readyqueue\n");
display_process_queue(pcb_ready);
break;
case'6':
printf("blockedqueue\n");
display_process_queue(pcb_blocked);
break;
case'7':
printf("runningqueue\n");
display_process_queue(pcb_run);
break;
case'a':
create_process();
break;
case'b':
break;
case'c':
block_process_by_name();
break;
case'd':
wakeup_process();
break;
case'8':
return0;
}
printf("\nPressanykeytoreturntomainmenu.");
getch();
system("cls");
}
return0;
}
有了头文件和主函数就可以编译、链接并运行程序,测试程序的主菜单是否正常工作。
现在运行程序,可以看到程序仅仅显示一个主菜单,如果你选择1~7和a~e项对应的功能,该程序不会有所反应,因为你还没有编写相关的功能函数。
如果你选择8,则程序终止执行。
这说明主菜单能正常工作。
此后,你可以每实现一个函数就测试程序是否正确,如果不正确则修改这个函数,直到它正确为止;如果正确,则实现下一个函数。
如此每次实现一个函数,直到所有函数都正确实现,直到整个程序能正确执行。
3.进程控制块表的初始化函数init_pcb_table()
该函数用来给进程控制块表即数组pct_table赋初值,并且将数组元素从头到尾串成链表,形成进程空闲队列。
每个数组元素的初值为:
进程名为空字符串,进程启动时刻为0,要求运行时间为0,时间片为0,优先数为0。
初始化完成后的进程控制块表如图2-5所示。
voidinit_pcb_table()
{
inti=0;
pcb_free=&pcb_table[0];
pcb_table[MAX_PROCESS-1].next=NULL;
pcb_table[MAX_PROCESS-1].process_number=0;
pcb_table[MAX_PROCESS-1].process_start_moment=0;
pcb_table[MAX_PROCESS-1].process_need_time=0;
pcb_table[MAX_PROCESS-1].process_time_slice=0;
pcb_table[MAX_PROCESS-1].process_priority=0;
strcpy(pcb_table[MAX_PROCESS-1].process_name,"");
for(i=0;i pcb_table[i].next=&pcb_table[i+1]; pcb_table[i].process_number=0; pcb_table[i].process_start_moment=0; pcb_table[i].process_need_time=0; pcb_table[i].process_time_slice=0; pcb_table[i].process_priority=0; strcpy(pcb_table[i].process_name,""); } } 4.进程队列输出函数display_process_queue() 该函数有一个输入参数用来指明要显示的进程队列的对首。 在vc++6.0的控制台程序中不能直接控制光标,要想显示整齐的表格,需要自己设计相关函数,我们设计一个print_space()函数用来输出若干个空格,以便对齐文本。 voidprint_space(intnum){ inti; for(i=0;i printf(""); } } //以表格的形式显示由queue指出的进程队列 voiddisplay_process_queue(PCB*queue) { PCB*p=queue;//用来遍历进程队列的指针 charbuffer[10];//将整数转换成字符串时用到的缓冲区 printf("|--------------|---------|-------|------|-------|----------|\n");//显示表头 printf("|name|number|start|need|slice|priority|\n"); printf("|--------------|---------|-------|------|-------|----------|\n"); while(p! =NULL){//显示队列中的每个节点 printf("|"); printf("%s",p->process_name);//显示进程名称 print_space(23-strlen(p->process_name));//右边用空格补齐 printf("|"); printf("%d",p->process_number);//显示进程号 itoa(p->process_number,buffer,10);//整数转换成字符串 print_space(8-strlen(buffer)); printf("|"); printf("%d",p->process_start_moment);//显示进程启动时刻 itoa(p->process_start_moment,buffer,10); print_space(6-strlen(buffer)); printf("|"); printf("%d",p->process_need_time);//显示进程要求运行时间 itoa(p->process_need_time,buffer,10); print_space(5-strlen(buffer)); printf("|"); printf("%d",p->process_time_slic
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- OS 进程 调度 算法