一、实验目的
（1）在单处理器情况下按时间片轮转算法实现处理器调度，输出运行动态
变化过程。
（2）通过算法的实现加深了解处理器调度的工作。
二、实验内容
输入实现处理器调度的几个进程信息，任意确定一组“要求运行时间”，启动
所设计的处理器调度程序，显示逐次被选中进程的进程名以及进程控制块的动态
变化过程。
三、实验步骤
1、任务分析：
时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片
的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示
出来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制块，
定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时间、
已运行时间和进程的状态以及指针的信息。实现的过程即运用指针指向某一个进
程，判断当前的进程是否是就绪状态“r”，如果是，则为该进程分配一个时间片，
同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个进程的
所需要运行的时间减少至 0 时，则将该进程的状态设置为“e”。然后，将指针指
向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。
2、概要设计：
（1）所用数据结构及符号说明
typedef struct PCB{
char name[10]; //进程名
struct PCB *next; //循环链指针
int need_time; //要求运行时间
int worked_time; //已运行时间，初始为 0
char condition; //进程状态，只有“就绪”和“结束”两种状态
int flag; //进程结束标志，用于输出
}PCB;
PCB *front,*rear; //循环链队列的头指针和尾指针
int N; //N 为进程数
（2）主程序的流程图：
Y
Y
N
Y
（3）程序说明：处理器调度总是选择指针指示的进程运行。由于本实验是
模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：
已运行时间+1 来模拟进程的一次运行，表示进程已经运行过一个单位的时间。
进程是否’r’
开始
输入进程数 N
输入各进程信息
为每个进程创建 PCB 并初
始化形成一个循环链队列
指针指向循环链队
列第一个进程
运行时间+1 且剩余时间-1
剩余时间=0？
将进程状态置为’e’（完成）
所有进程是否完成
指针指向队列中下个进程
结束
3、详细设计
（1）首先每一个进程用一个进程控制块 PCB 来代表。进程控制块的格式为：
进程名
指针
要求运行时间
已运行时间
状态
其中，进程名——作为进程的标识，如 Q1、Q2 等。
指针——进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块
的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。
要求运行时间——假设进程需要运行的单位时间数。
已运行时间——假设进程已经运行的单位时间数，初始值为“0”。
状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。
当一个进程运行结束后，它的状态为“结束”，用“E”表示。
（2）每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求
运行时间”。
把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示
轮到运行的进程，如下图描述所示：
K1 Q1
K2
Q2
K3
Q3
K4
Q4
K5
Q5
K2 K3 K4 K5 K1
2 4 3 1 2
0 0 0 0 0
R R R R R
PCB1 PCB2 PCB3 PCB4 PCB5
（3）程序详细设计步骤：
a.首先建立 PCB 的数据结构，为了便于正确输出，加上了进程结束标志
flag。输入进程信息（包括进程名和要求运行的时间），并为每个进程创建一个
PCB 并初始化形成一个循环链队列，用函数 creatPCB()来实现。
b.建立函数 judge()用来判断进程全部运行结束标志，即当所有进程的状态变
为’e’（即完成状态）后，循环结束，表示所有进程都已运行成功。
c.建立时间片轮转算法 creatProcess（）对进程进行轮转运行，首先指针 s 指
向第一个进程 PCB，即 s=front，判断该进程的状态是否为’r’（就绪状态），即
if(s->condition == 'r')，若是则表示此进程尚未执行结束，则执行 s->worked_time++
且 s->need_time--，if(s->need_time==0)，则表示此进程已运行结束，将其状态置
为结束，即 s->condition='e'，并根据状态位输出完成信息，且以后不会再运行此
进程。将指针指向下个进程，s=s->next，并判断所有进程是否已全部运行结束，
没有则重复上面算法。当所有进程的状态位都变成’e’表示所有进程运行完成，
则循环结束。
d.建立主函数 main(),输入进程数 N，调用初始化循环链队列函数 creatPCB()
和时间片轮转算法 creatProcess(N)，每次选中进程的进程名以及运行一次后进程
队列的变化，实现处理器的调度。
4、调试分析：
a．调试过程中遇到的问题及解决方案
开始运行到 Q5 运行完成后显示错误，如下图所示：
原因：经检查程序发现语句 if(s->condition=='e' ){printf("进程%s 已经运行完
成！\n\n",s->name);}有错误，因为当某个进程运行完成后，其状态标志已修改
为’e’，所以再次循环运行未完成的进程时，当运行到此句时仍会将前面已完成
的进程重新输出一遍完成信息，导致输出错误。
解决方案：为每个进程加上一个结束标志 flag，并赋初值为 0，当进程运行
完 成 后 ， 将 flag 改 为 1 ， 再 将 后 面 输 出 改 为 if(s->condition=='e' ||
s->flag==0 ){printf("进程%s 已经运行完成！\n\n",s->name);s->flag==0;}，这样在
前面进程运行完成输出后，后面再循环时就不会重新输出一遍了。
b．改进设想：本实验较简单，但还不够完善，如未实现插入进程功能，即
进程在运行过程中可以插入其他的进程再运行。还有未进行进程优先级判别，本
实验默认进程的优先级按输入的先后顺序从大到小排列的，还有其他功能等，希
望在以后的实验中逐步完善。
5、测试结果：
a．首先输出五个进程的初始状态
b．开始从进程 Q1 开始按时间片轮转运行进程，Q4 先运行完成
c.接着 Q1 运行完成
d.接着 Q5 运行完成
e.再 Q3 运行完成
f.最后 Q2 运行完成
四、实验总结
因在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则
排成一个队列，每次调度是，把 CPU 分配给队首进程，并令其执行一个时间片。
当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末
尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时
间片。在时间片轮转算法中，时间片的大小对系统性能有很大的影响。如果选择
很小的时间片将有利于短作业，因为它能较快地完成，但会频繁的发生中断、进
程上下文的切换，从而增加系统的开销；反之，如果选择太长时间片，使得每个
进程都能在一个时间片内完成，所以，一般定为时间片略大于一次典型地交互所
需要的时间。
在完成时间片轮转算法的实现过程中，我们遇到了一些问题，比如怎样运用
循环队列，如何设计结构体等等，也积极配合并思考进行解决。整体来说，我们
的算法虽然实现了体现进程动态运行变化的过程，但是相对而言比较简单。实验
中，我们小组不断讨论对算法进行优化，使得运行结果看起来更容易理解，也达
到了处理机调度的功能。做实验让我们对于时间片轮转的思想理解的更加透彻，
巩固了理论知识的学习。
实验心得体会：首先，我们认为这次课程设计是对学习《操作系统》的一次
综合考察，锻炼我们综合分析问题、解决问题的能力。
初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也出
现了一些难题需要解决，为此去苦苦探索过。课程设计期间，几乎有几天我们完
全投入进去了，就像是在做一个相当重要的项目一样的感觉。曾经跑过图书馆几
次，只是为了一种新的想法得到实现，也曾多次登录网站浏览网页，为了弥补一
些知识上的纰漏，为此曾洒下了真实的汗水。当我们的想法得到实现，又学会了
新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有
回报的真实写照吧。
其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有
那么一部分是以前学过的 C 问题，但是已经忘却或是以前没有真正的理解过。
但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，让你身处困
境却感到无限希望。这好像是人生的一种历程，风风雨雨中我们一起走过，然后
为了一些坑坑洼洼彼此真诚的帮助过和无私的付出过。团队的协作和彼此心的交
流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。
最后，我认识到了自己的不足。平心而论，以前真的没有认真的学习过，即
使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。得过且过，迷
失了我前进的方向，而现在却又重新敞开了。不论是以后的学习还是工作，我想
这都是很重要的，我们需要不断进步的动力。
总的说来知识上的收获很是重要，精神上的丰收也是更加可喜的，让我知道
了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，
一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。
这次课程设计必将成为我人生旅途上一个非常美好的回忆。
五、附录
实验源程序如下：
#include""
#include""
#include""
#include""
#define NULL 0
typedef struct PCB{
char name[10]; //进程名
struct PCB *next; //链指针
int need_time; //要求运行时间
int worked_time; //已运行时间
char condition; //进程状态，只有“就绪”和“结束”两种状态
int flag; //进程结束标志
}PCB;
PCB *front,*rear;
int N; //N 为进程数
void creatPCB(){ //为每个进程创建一个 PCB 并初始化形成一个循环链
队列
PCB *p,*l;
l = (PCB *)malloc(sizeof(PCB));
printf("Please enter process name and time\n");
scanf("%s%d",l->name,&l->need_time);
l->condition = 'r'; //进程初始状态为就绪
l->worked_time = 0;
l->next=NULL;
l->flag=0;
front=l;
for(int i = 1;i < N ;i ++){
p = (PCB *)malloc(sizeof(PCB));
scanf("%s%d",p->name,&p->need_time);
p->condition = 'r';
p->worked_time = 0;
p->flag=0;
l->next = p;
l=l->next;
}
rear=l;rear->next=front;
}
void output(){ //进程输出函数
printf("name runtime needtime state\n");
for(int j=1;j<=N;j++){ printf("
%-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front-
>condition);
front=front->next;
}
printf("\n");
}
int judge(PCB *p){ //判断所有进程运行结束
int flag = 1;
for(int i=0;i<N;i++){
if(p->condition != 'e'){
flag = 0;
break;}
p=p->next;
}
return flag;
}
void creatProcess(int n){ //时间片轮转算法
PCB *s,*p;
int i,j,flag1=0;
s = (PCB *)malloc(sizeof(PCB));
s=front;
printf("\n--------------------------------------------\n");
output();
printf("Press any key to continue...\n\n");
getch(); //按任意键继续
s=front;
while(flag1 != 1){
if(s->condition == 'r'){
s->worked_time++;
s->need_time--;
if(s->need_time==0)
s->condition='e';
output();
printf("Press any key to continue...\n\n");
getch();
}
if(s->condition=='e' && s->flag==0){
printf("进程%s 已经运行完成！\n\n",s->name);
s->flag=1;
}
s=s->next;
flag1=judge(s);
}
printf("--------------------------------------------\n");
}
void main(){
printf("Please enter process number\n");
scanf("%d",&N);;
creatPCB();
creatProcess(N);
}
