时间片轮转调度算法的基本原理

什么是时间片轮转调度算法~

　　时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node
{
char name[10]; /*进程标识符*/
int prio; /*进程优先数*/
int round; /*进程时间轮转时间片*/
int cputime; /*进程占用CPU时间*/
int needtime; /*进程到完成还要的时间*/
int count; /*计数器*/
char state; /*进程的状态*/
struct node *next; /*链指针*/
}PCB;
PCB *finish,*ready,*tail,*run; /*队列指针*/
int N; /*进程数*/
/*将就绪队列中的第一个进程投入运行*/
firstin()
{
run=ready; /*就绪队列头指针赋值给运行头指针*/
run->state='R'; /*进程状态变为运行态*/
ready=ready->next; /*就绪对列头指针后移到下一进程*/
}
/*标题输出函数*/
void prt1(char a)
{
if(toupper(a)=='P') /*优先数法*/
printf(" name cputime needtime priority state
");
else
printf(" name cputime needtime count round state
");
}
/*进程PCB输出*/
void prt2(char a,PCB *q)
{
if(toupper(a)=='P') /*优先数法的输出*/
printf(" %-10s%-10d%-10d%-10d %c
",q->name,
q->cputime,q->needtime,q->prio,q->state);
else/*轮转法的输出*/
printf(" %-10s%-10d%-10d%-10d%-10d %-c
",q->name,
q->cputime,q->needtime,q->count,q->round,q->state);
}
/*输出函数*/
void prt(char algo)
{
PCB *p;
prt1(algo); /*输出标题*/
if(run!=NULL) /*如果运行指针不空*/
prt2(algo,run); /*输出当前正在运行的PCB*/
p=ready; /*输出就绪队列PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
p=finish; /*输出完成队列的PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
getch(); /*压任意键继续*/
}
/*优先数的插入算法*/
insert1(PCB *q)
{
PCB *p1,*s,*r;
int b;
s=q; /*待插入的PCB指针*/
p1=ready; /*就绪队列头指针*/
r=p1; /*r做p1的前驱指针*/
b=1;
while((p1!=NULL)&&b) /*根据优先数确定插入位置*/
if(p1->prio>=s->prio)
{
r=p1;
p1=p1->next;
}
else
b=0;
if(r!=p1) /*如果条件成立说明插入在r与p1之间*/
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1; /*否则插入在就绪队列的头*/
ready=s;
}
}
/*轮转法插入函数*/
insert2(PCB *p2)
{
tail->next=p2; /*将新的PCB插入在当前就绪队列的尾*/
tail=p2;
p2->next=NULL;
}
/*优先数创建初始PCB信息*/
void create1(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL; /*就绪队列头指针*/
finish=NULL; /*完成队列头指针*/
run=NULL; /*运行队列指针*/
printf("Enter name and time of process
"); /*输入进程标识和所需时间创建PCB*/
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='w';
p->prio=50-time;
if(ready!=NULL) /*就绪队列不空调用插入函数插入*/
insert1(p);
else
{
p->next=ready; /*创建就绪队列的第一个PCB*/
ready=p;
}
}
clrscr();
printf(" output of priority:
");
printf("************************************************
");
prt(alg); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
/*轮转法创建进程PCB*/
void create2(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of round process
");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; /*计数器*/
p->state='w';
p->round=2; /*时间片*/
if(ready!=NULL)
insert2(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
clrscr();
printf(" output of round
");
printf("************************************************
");
prt(alg); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
/*优先数调度算法*/
priority(char alg)
{
while(run!=NULL) /*当运行队列不空时，有进程正在运行*/
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/
if(run->needtime==0) /*如所需时间为0将其插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F'; /*置状态为完成态*/
run=NULL; /*运行队列头指针为空*/
if(ready!=NULL) /*如就绪队列不空*/
firstin(); /*将就绪对列的第一个进程投入运行*/
}
else /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/
if((ready!=NULL)&&(run->prioprio))
{
run->state='W';
insert1(run);
firstin(); /*将就绪队列的第一个进程投入运行*/
}
prt(alg); /*输出进程PCB信息*/
}
}
/*时间片轮转法*/
roundrun(char alg)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->count=run->count+1;
if(run->needtime==0)/*运行完将其变为完成态，插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就绪对列不空，将第一个进程投入运行*/
}
else
if(run->count==run->round) /*如果时间片到*/
{
run->count=0; /*计数器置0*/
if(ready!=NULL) /*如就绪队列不空*/
{
run->state='W'; /*将进程插入到就绪队列中等待轮转*/
insert2(run);
firstin(); /*将就绪对列的第一个进程投入运行*/
}
}
prt(alg); /*输出进程信息*/
}
}
/*主函数*/
main()
{
char algo; /*算法标记*/
clrscr();
printf("type the algorithm:P/R(priority/roundrobin)
");
scanf("%c",&algo); /*输入字符确定算法*/
printf("Enter process number
");
scanf("%d",&N); /*输入进程数*/
if(algo=='P'||algo=='p')
{
create1(algo); /*优先数法*/
priority(algo);
}
else
if(algo=='R'||algo=='r')
{
create2(algo); /*轮转法*/
roundrun(algo);
}
}

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

---

夹江县15728836186： 什么是时间片轮转调度算法?希望能够详细的解释一下,最好是举个例子. - ？
度崔阿贝：[答案] 时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法.每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间.如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程.如果进程在时间片...

夹江县15728836186： 什么是时间片轮转调度算法 - ？
度崔阿贝： 时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法. 每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间.如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程.如果进程在时间片结束前阻塞或结束,则CPU当即进行切换.调度程序所要做的就是维护一张就绪进程列表,当进程用完它的时间片后,它被移到队列的末尾. 就这样说吧,CPU假如比做一个游戏机,现在A,B,C都想玩,如何去分配呢,时间片轮转调度就是来分配这游戏机的,先让A玩三分钟,再让B玩三分钟,再让C玩三分钟,再来让A玩三分钟,如此循环.

夹江县15728836186： 操作系统中的 名词解释:时间片轮转法?？
度崔阿贝： 好不容易才找到答案: 时间片轮转法主要是分时系统中使用的一种调度算法.时间片轮转法的基本思想是,将CPU 的处理 时间划分成一个个时间片,就绪队列中的诸进程轮流运行一个时间片.当时间片结束时,就强迫运行进程让出CPU,该进...

夹江县15728836186： 什么是“时间片轮转法” - ？
度崔阿贝： 处理器同一个时间只能处理一个任务.处理器在处理多任务的时候,就要看请求的时间顺序,如果时间一致,就要进行预测.挑到一个任务后,需要若干步骤才能做完,这些步骤中有些需要处理器参与,有些不需要(如磁盘控制器的存储过程).不需要处理器处理的时候,这部分时间就要分配给其他的进程.原来的进程就要处于等待的时间段上.经过周密分配时间,宏观上就象是多个任务一起运行一样,但微观上是有先后的,就是时间片轮换.

夹江县15728836186： 进程就是任务吗？
度崔阿贝： 1.进程是任务的一部分 2.线程(thread),有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元.一个标准的线程由线程ID,当前指令指针(PC),寄存器集合和堆栈组成.另外,线程是进程中的一个实体,是被系...

夹江县15728836186： 什么是多线程、多进程? - ？
度崔阿贝： ■什么是多线程:多线程是为了使得多个线程并行的工作以完成多项任务,以提高系统的效率.线程是在同一时间需要完成多项任务的时候被实现的.使用线程的好处有以下几点:·使用线程可以把占据长时间的程序中的任务放到后台去处理 ·...

夹江县15728836186： 进程调度算法是什么? - ？
度崔阿贝： 调度算法是指:根据系统的资源分配策略所规定的资源分配算法. 一、先来先服务和短作业(进程)优先调度算法 1. 先来先服务调度算法.先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度, 也可用于进程调...

夹江县15728836186： 时间片轮转调度 - ？
度崔阿贝： #include ＂stdio.h＂ #include ＂stdlib.h＂ #include ＂string.h＂ typedef struct node {char name[10]; /*进程标识符*/int prio; /*进程优先数*/int round; /*进程时间轮转时间片*/int cputime; /*进程占用cpu时间*/int needtime; /*进程到完成还...

夹江县15728836186： 处理机调度可以分为? - ？
度崔阿贝： 在多道程序设计系统中,内存中有多道程序运行,他们相互争夺处理机这一重要的资源.处理机调度就是从就绪队列中,按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程并发地执行.1.处理机调度的功能一般情况下,当占...