进程调度程序设计.docx
《进程调度程序设计.docx》由会员分享,可在线阅读,更多相关《进程调度程序设计.docx(17页珍藏版)》请在冰点文库上搜索。
进程调度程序设计
一.设计目的:
通过课程设计,加深对操作系统对程序执行的理解,掌握操作系统的多程序运行原理,能模拟操作系统设计相应的进程调度算法,掌握操作系统的基本原理及功能,具有初步分析实际操作系统、设计、构造和开发现代操作系统的基本能力。
二.设计内容:
1、设计进程控制块PCB表结构,分别适用于可强占的优先数调度算法和循环轮转调度算法。
2、建立进程就绪队列。
对两种不同算法编制入链子程序。
3、编制两种进程调度算法:
1)可强占的优先进程调度;2)循环时间片轮转调度
4、设计操作系统运行的指令。
三.设计过程
1、实现功能
1、设计进程控制块PCB表结构,分别适用于可强占的优先数调度算法和循环轮转调度算法。
2、建立进程就绪队列。
对两种不同算法编制入链子程序。
3、编制两种进程调度算法:
1)可强占的优先进程调度;2)循环时间片轮转调度
4、设计操作系统运行的指令。
2、设计思路
1、本程序用两种算法对多个进程进行调度,每个进程可有三个状态,并假设初始状态为就绪状态。
2、为了便于处理,程序中的某进程运行时间以时间片为单位计算。
各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
3、在优先数算法中,优先数的值为31与运行时间的差值。
进程每执行一次,优先数减1,CPU时间片数加1,进程还需要的时间片数减1。
在轮转算法中,采用固定时间片(即:
每执行一次进程,该进程的执行时间片数为已执行了1个单位),这时,CPU时间片数加1,进程还需要的时间片数减1,并排列到就绪队列的尾上。
4、设计程序指令,
MOVn//把整数n赋给累加器A
SAVm//把累加器A的值存入地址M
ADDn//从累加器A的值减去整数n,结果送到累加器A。
SUBn//从累加器A的值减去整数n,结果送到累加器A。
MULn//从累加器A的值乘以整数n,结果送到累加器A。
DIVn//从累加器A的值除以整数n,结果送到累加器A。
JEQm//F为0跳转到m
JLGm//F大于0跳转到m
JLEm//F大于等于0跳转到m
JMPm//无条件跳转到m
OUTport//累加器的内容输出到端口port。
port为0,指显示器
3、算法和流程图
可强占优先调度算法实现过程流程图:
强占优先调度算法实现过程流程图
循环轮转算法实现过程流程图:
循环轮转算法实现过程流程图
四.设计总结:
通过该课程设计,加深了对系统进程调度机制的理解。
在抢占方式中实践了“抢占”必须遵循的原则:
优先权原则,短进程优先原则,时间片原则。
认识了几种进程调度算法的优缺点以及应用范围。
加强C的编程能力。
参考文献
[1]AbrahamSilberschatz.操作系统概念(第8版影印版).北京:
高等教育出版社,2010.
[2]GaryNutt(著),潘登(译).Linux操作系统内核实习.北京:
机械工业出版社,2004.
[3]于渊.自己动手写操作系统(影印版).电子工业出版社,2005
附录
程序源代码:
1、程序头文件
#ifndef__VIRTUAL_KERNEL__
#define__VIRTUAL_KERNEL__
#include"iostream.h"
#include"string.h"
#include"stdio.h"
#include"time.h"
#include
#defineNOP00//空指令:
消耗一个机器周期
#defineMOV01//传送指令:
立即数赋值给寄存器A
#defineADD02//加法指令:
寄存器A加立即数
#defineOUT80//输出指令:
寄存器A的值输出到端口(端口号01--表示显示器)
#defineMAX_PID10//系统并发运行的进程数的最大值
//定义PCB结构类型
structPCB{
intA;//累加器A
intPC;//程序计数器PC
char*addr;//程序加载起始地址
intlength;//程序大小
intruntime;
intwaittime;
intstate;
intpname;
intpri;//优先级数
structPCB*next;
}pcbs[MAX_PID];/*运行指针*/
structPCB*running;/*高优先级就绪队列头指针*/
structPCB*Hready;/*低优先级队列头指针*/
structPCB*Lready;/*等待队列头指针*/
structPCB*wait;
intsig=0;
intcur_pid;//当前_进程号
intreadyNum=MAX_PID;
/**************************以下是函数说明****************************/
/*利用循环实现延迟*/
voiddelay();
voidproc(structPCB*running);/*将node插入到head所指示的队列的尾部*/
voidInsertIntoQueueTail(structPCB**head,structPCB*node);/*进程调度函数*/
intproc_switch();/*进程等待函数*/
voidproc_wait();/*进程唤醒函数*/
intproc_wakeup();
voidinitSystem(void);//初始化系统
intloadProgram(char*name);//加载应用程序
intexeInstruction(intpid);//执行指令
voidremoveFromQueue(structPCB**head,structPCB*node);
#endif
2、程序文件
#include"vknl.h"
intmain(intargc,char*argv[])
{
inti;
if(argc!
=2)argv[1]="app1.bin";//默认应用程序
initSystem();
for(i=0;iloadProgram(argv[i]);//加载应用程序
}
/*模拟进程调度开始*/
for(;readyNum>0;)
{
switch(sig){
case0:
/*无进程等待调度,打印信息并返回*/
if(!
proc_switch())
{
printf("NoProcesstorun,pressanykeytoreturn:
\n");
getchar();
exit(-1);
}
break;
case1:
proc_wait();break;
case2:
case3:
case4:
case5:
case6:
case7:
case8:
case9:
case10:
case11:
proc(running);break;
default:
printf("\nerror!
");
exit(-1);
}
}
return0;//退出虚拟内核
}
//初始化系统
voidinitSystem(void)
{
cur_pid=0;
/*等待队列和高优先级队列为空*/
wait=NULL;
Hready=NULL;
}
//加载应用程序
intloadProgram(char*name)
{
FILE*fin=fopen(name,"rb");//打开源程序文件
if(fin==NULL)return-1;//若打开失败,返回-1
fseek(fin,0L,SEEK_END);//文件读写指针移到文件末尾
longfsize=ftell(fin);//求文件长度
fseek(fin,0L,SEEK_SET);//读写指针移到文件开头
PCB*pcb=pcbs+cur_pid;//获取当前进程PCB
pcb->addr=newchar[fsize];//为新进程分配内存
fread(pcb->addr,fsize,1,fin);//程序读入内存
fclose(fin);//关闭文件
pcb->length=fsize;//进程大小
pcb->A=0;//初始化寄存器
pcb->PC=0;
pcb->pname=(cur_pid+2);
pcb->waittime=0;
pcb->state=1;
InsertIntoQueueTail(&Hready,pcb);//&pcb[i]
cur_pid++;
return0;//正常返回
}
//执行指令
intexeInstruction(intpid)
{
PCB*pcb=pcbs+(pid-2);//获取当前进程PCB
charop_cmd=*(pcb->addr+pcb->PC);//取操作码
shortop_dat=*((short*)(pcb->addr+pcb->PC+1));//取操作数
//注意,我们约定操作数是16位整数,所以要定义为short。
if(op_cmd==MOV)//传送指令
{
pcb->A=op_dat;//操作数赋给累加器A
}
elseif(op_cmd==ADD)//加法指令
{
pcb->A+=op_dat;//加计算
}
elseif(op_cmd==SUB)
{
pcb->A-=op_dat;
}
elseif(op_cmd==MUL)
{
pcb->A*=op_dat;
}
elseif(op_cmd==DIV)
{
pcb->A/=op_dat;
}
elseif(op_cmd==MOD)
{
pcb->A%=op_dat;
}
elseif(op_cmd==JMP)
{
printf("JMPoperation.jumpto%d\n",op_dat);
pcb->pc+=(op_dat*3);
}
elseif(op_cmd==OUT)//输出指令
{
printf("OUToperation.resultis%d\n",pcb->A);//输出累加器A的内容
}
pcb->PC+=3;//修改程序计数器
if(pcb->PC>=pcb->length)
{
readyNum--;
pcb->state=0;
sig=0;
}
return0;//正常返回
}
/*功能:
进程*/
/*入口参数:
运行指针*/
/*出口参数:
无*/
voidproc(structPCB*running)
{
inti;
if(running->state==0)return;
/*显示当前运行的进程的id*/
printf("\nNowProcess%disrunning\n",running->pname);
/*当前进程执行running->runtime个时间片*/
for(i=running->runtime;i>0;i--){
exeInstruction(running->pname);
/*显示剩余的时间片*/
printf("%dtimeslice(s)left\n",i);
/*延迟*/
delay();
proc_wakeup();
}
/*产生一个1到1000的随机数,若该随机数小余100,当前进程等待,*/
if((rand()%10000+1)<1000){
printf("Process%dbeginstowait.\n",running->pname);
sig=1;
return;
}
/*显示时间片耗尽,进程转为低优先级就绪状态*/
printf("Timeslicesforprocess%dexhausted.\n",running->pname);
InsertIntoQueueTail(&Lready,running);
sig=0;
return;
}
/*功能:
将一个节点插入队列尾部*/
/*入口参数:
队列头指针地址head,待插入结点node*/
/*出口参数:
无*/
voidInsertIntoQueueTail(structPCB**head,structPCB*node)
{
structPCB*p;
node->next=NULL;
if(*head==NULL){
/*被插入队列为空*/
*head=node;
return;
}
/*被插入队列不为空*/
else{
p=*head;
/*找到队列的最后一个结点*/
while(p->next!
=NULL)p=p->next;
p->next=node;
}
}
/*功能:
进程调度*/
/*入口参数:
无*/
/*出口参数:
若调度成功,返回1,否则返回0*/
intproc_switch()
{
/*若高优先级就绪队列和低优先级就绪队列均为空,则循环执行进程唤醒*/
while(Hready==NULL&&Lready==NULL)
if(!
proc_wakeup())return0;
/*若高优先级就绪队列非空,则执行其第一个进程,分配2个时间片*/
if(Hready!
=NULL){
running=Hready;
Hready=Hready->next;
running->runtime=2;
}
/*若高优先级就绪队列为空,则执行低优先级就绪队列的第一个进程,
分配5个时间片*/
else{
running=Lready;
Lready=Lready->next;
running->runtime=5;
}
/*别调度进程的id赋给sig*/
sig=running->pname;
return1;
}
/*功能:
进程等待。
将当前运行进程置高优先级,等待时间为20,
插入等待队列尾部*/
/*入口参数:
无*/
/*出口参数:
无*/
voidproc_wait()
{
PCB*p;
running->pri=1;
running->waittime=20;
InsertIntoQueueTail(&wait,running);
sig=0;
return;
}
/*功能:
进程唤醒*/
/*入口参数:
无*/
/*出口参数:
若等待队列为空,则返回0,否则返回1*/
intproc_wakeup()
{
structPCB*p,*last,*MoveToReady;
p=wait;
/*等待队列为空,返回0*/
if(p==NULL)return0;
/*延迟*/
delay();
/*等待队列中每个进程的等待时间减1*/
while(p!
=NULL){
p->waittime-=1;
p=p->next;
}
p=wait;
/*从等待队列中摘除等待时间为0的进程,插入到高优先级就绪队列的尾部*/
while(p!
=NULL){
if(p->waittime==0){
MoveToReady=p;
if(p==wait)
wait=p->next;
else
last->next=p->next;
p=p->next;
InsertIntoQueueTail(&Lready,MoveToReady);
}
else{
p=p->next;
}
}
sig=0;
return1;
}
/*功能:
延迟一个时间片*/
/*入口参数:
无*/
/*出口参数:
无*/
voiddelay()
{
inti,j;
for(i=0;i<10000;i++)
for(j=0;j<5000;j++)
{
}
}