操作系统时间片轮转法调度
时间片轮转法模拟进程调度
一、基本原理
在时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。当执行的时间片用完时,中断请求,将该程序送往就绪队列的队尾,并把处理机分配给新的队首进程,同时让它也执行一个时间片。这样就保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。
二、设计思路
首先,创建进程3-5,置低优先级,并依次插入低优先级队列,每次调度时,把处理器分配给队首进程,并给其一个随机数作为时间片的大小,当随机数小于300时令其等待,插入等待队列。当随机数大于300时,进程执行,并令其执行五个时间片。时间片耗尽时由一个计时器发出时钟中断请求,该进程转为低优先级就绪状态,插入到低优先级就绪队列的队尾,并将处理器分配给下一个进程。当高优先级队列和低优先级队列都为空时,则循环执行进程唤醒,执行等待队列里的进程。
三、运行结果(不唯一)
在运行结果中,按进程插入就绪队列的先后顺序进行调度,进程3先运行,其时间片耗尽后让其插入低优先级就绪队列的队尾,然后进程4开始运行,时间片耗尽后进程5开始运行,在进程5运行完第四个时间片后,分配给它的第五个时间片大小小于300,所以进程5
等待,插入等待队列。继续调度进程3,直到就绪队列里的进程都由于时间片大小小于300被插入等待队列后,开始唤醒进程5,并将其插入高优先级就绪队列,分配两个时间片,如此循环。
三、源代码:
#include
#include
#include
/*********************以下是全局数据结构和变量***********************/
/*PCB 结构*/
struct PCB{
int pname;
int pri;
int runtime;
int waittime;
struct PCB *next;
}pcb[7];
/* 运行指针*/
struct PCB *running;
/*高优先级就绪队列头指针*/
struct PCB *Hready;
/*低优先级队列头指针*/
struct PCB *Lready;
/*等待队列头指针*/
struct PCB*wait;
int A=0;
/**************************以下是函
****************************/
/*利用循环实现延迟*/
void delay();
/*模拟进程3-9*/
void proc(struct PCB *running);
/*将node插入到head所指示的队列的尾部*/
void InsertIntoQueueTail(struct PCB **head,struct PCB *node);
/*进程调度函数*/ 数说 明
int proc_switch();
/*进程等待函数*/
void proc_wait();
/*进程唤醒函数*/
int proc_wakeup();
/************************以下是函数定
************************/
/*主函数*/
main()
{
int i;
/*初始化,创建进程3-9,置低优先级,等待时间为0,
依次插入低优先级队列*/
for(i=0;i
pcb[i].pname=i+3;
pcb[i].pri=0;
pcb[i].waittime=0;
InsertIntoQueueTail(&Lready,&pcb[i]);
}
/*等待队列和高优先级队列为空*/
wait=NULL;
Hready=NULL;
printf("\n模拟进程调度开始:\n");
/*模拟进程调度开始*/
for(;;)
{
switch(A){
case 0:/*无进程等待调度,打印信息并返回*/
if(!proc_switch())
{
printf("/n没有进程在运行 返回:\n");
getchar();
}
break;
case 1:proc_wait();
break;
case 3:
case 4:
case 5: 义及 注释
case 6:proc(running);
break;
default:printf("\nerror!");
exit(-1);
}
}
}
/*功能:延迟一个时间片*/
/*入口参数:无*/
/*出口参数:无*/
void delay()
{
int i,j;
for(i=0;i
for(j=0;j
{
}
}
/*功能:进程3-9*/
/*入口参数:运行指针*/
/*出口参数:无*/
void proc(struct PCB * running)
{
int i;
srand( (unsigned)time( NULL ) );
/*显示当前运行的进程的id*/
printf("\n现在进程 %d 正在运行\n",running->pname);
/*当前进程执行running->runtime个时间片*/
for(i=running->runtime;i>0;i--){
/*显示剩余的时间片*/
printf("剩余的时间片为%d\n",i);
/*延迟*/
delay();
proc_wakeup();
/*产生一个1到1000的随机数,若该随机数小余300,当前进程等待,*/ if((rand()%1000+1)
printf("进程%d开始等待.\n",running->pname);
A=1;
return;
}
}
/*显示时间片耗尽,进程转为低优先级就绪状态*/
printf("进程%d时间片耗尽\n",running->pname);
InsertIntoQueueTail(&Lready,running);
A=0;
return;
}
/*功能:将一个节点插入队列尾部*/
/*入口参数:队列头指针地址head,待插入结点node*/
/*出口参数:无*/
void InsertIntoQueueTail(struct PCB **head,struct PCB *node)
{
struct PCB *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*/
int proc_switch()
{
/*若高优先级就绪队列和低优先级就绪队列均为空,则循环执行进程唤醒*/ while(Hready == NULL && Lready == NULL)
if(!proc_wakeup()) return 0;
/*若高优先级就绪队列非空,则执行其第一个进程,分配2个时间片*/ if(Hready!=NULL){
running=Hready;
Hready=Hready->next;
running->runtime=2;
}
/*若高优先级就绪队列为空,则执行低优先级就绪队列的第一个进程,
分配5个时间片*/
else{
running=Lready;
Lready=Lready->next;
running->runtime=5;
}
/*把调度进程的id赋给A*/
A=running->pname;
return 1;
}
/*功能:进程等待。将当前运行进程置高优先级,等待时间为20, 插入等待队列尾部*/
/*入口参数:无*/
/*出口参数:无*/
void proc_wait()
{
struct PCB *p;
running->pri=1;
running->waittime=10;
InsertIntoQueueTail(&wait,running);
A=0;
return;
}
/*功能:进程唤醒*/
/*入口参数:无*/
/*出口参数:若等待队列为空,则返回0,否则返回1*/
int proc_wakeup()
{
struct PCB *p,*last,*MoveToReady;
p=wait;
/*等待队列为空,返回0*/
if(p==NULL) return 0;
/*延迟*/
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(&Hready,MoveToReady); }
else
{
p=p->next;
}
}
A=0;
return 1;
}