西安文理学院 计算机科学系
课程设计报告
设计名称： 进程调度算法设计 设计题目： 进程调度算法设计 学生学号： [1**********] 专业班级： 软件工程一班 学生姓名： 张兴华 学生成绩： 课题工作时间：
计算机科学系课程设计任务书
指导教师： 孙少波 系主任：
日 期：2012年05月29日
——1——
一、设计题目
进程调度算法的设计
二、主要内容
1、设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。
2、建立进程就绪队列。对两种不同算法编制入链子程序。 3、编制两种进程调度算法：1）优先数调度；2）循环轮转调度
开发环境：VC++语言的编程环境
三、具体要求
1、本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
2、为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
3、在优先数算法中，优先数的值为50与运行时间的差值，即
P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
4、对于遇到优先数一致的情况，采用FIFO策略解决。
开发环境：不限
四、进度安排
1、资料查找、系统分析，数据流程分析，概要设计。
2、系统详细设计、功能设计。 3、算法实现、编程调试。
4、资料整理、课程设计说明书编写。
五、完成后应上交的材料
——2——
1、课程设计说明书 2、相关源程序文件
六、总评成绩
指导教师 签名日期 年 月 日
系 主 任 审核日期 年 月 日
——3——
目 录
一.设计目的................................................................................................................... 5 二.设计内容................................................................................................................... 5 三.设计原理................................................................................................................... 6
.............................................................................................. 6 .......................................................................................... 6 四．设计步骤................................................................................................................ 6
.......................................................................................................... 6 .......................................................................................................... 7 .......................................................................................................... 7 ………………………………………………………………………..8 4.5源程序………………………………………………………………………...8 ………………………………………...………….....16
.................................................................................... 16 ................................ 16 4.6.3 运用循环轮转调度算法的执行结果（如下图）............................ 19
五.设计总结................................................................................................................. 21 六.参考文献................................................................................................................. 21
——4——
一.设计目的
通过这次课程设计，加深理解有关进程控制块、进程队列的概念，并体会和了解优先数和循环轮转调度算法的具体实施办法。培养程序设计的方法和技巧，提高编制清晰、合理、可读性好的系统程序的能力，同时加深对操作系统课程的理解。
二.设计内容
1．用语言来实现对n个进程采用不同调度算法的进程调度。
2．每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段： （1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3…。 （2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的
优先级大于0，且随机产生，优先数越大，优先级越高。
（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。 （4）进程总共需要运行时间Alltime，利用随机函数产生。 （5）进程状态，0：就绪态；1：运行态；2：阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。 3．优先数改变的原则
（1）进程在就绪队列中每呆一个时间片，优先数增加1。 （2）进程每运行一个时间片，优先数减3。
4．在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，
所有的进程控制块PCB链接成就绪队列。
三.设计原理
3.1 优先数调度算法
对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程，再来采用先来先服务的次序分配处理器。系统常与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理该进程时有两种算法，一是“非抢占式”，另一种是“可抢占式”。前者是次进程占用处理器后一直运行到结束，除非本身主动让出处理器；后者则是严格保证在任何时刻总是让优先数最高的进程在处理器上运行。
3.2 循环轮转调度算法
——5——
循环轮转调度算法的具体原理是：每个进程被分配一个时间片，即该进程允许运行的时间。就绪的进程都存放在一个就绪链表中，队首的进程将获得时间片。如果在时间片结束时进程还在运行，则CPU将剥夺并分配给下一个进程。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
四．设计步骤
4.1 任务分析
(1)PCB结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可根据实验的不同，PCB结构的内容可以作适当的增删
(2)本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、执行、完成。并假设初始状态为就绪状态。
(3)为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
(4)在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
(5)对于遇到优先数一致的情况，采用FIFO策略解决。
4.2 概要设计
1.本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
2.为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
3.在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
4.对于遇到优先数一致的情况，采用FIFO策略解决。
4.3 详细设计
1.struct pcb（） 定义pcb块
2.Void display（） 显示结果信息函数
——6——
3.int process_finish(pcb *q) 进程完成标示
4.void display_round（） 显示循环轮转调度算法运行结果 5.priority_cal() 优先数调度算法
6.void cpu_round（）处理器的工作状态
4.4 流程图
——7——
4.5 源程序
源程序如下： #include #include #include #include #include #define P_NUM 5 #define P_TIME 50 enum state{ ready, execute, block, finish };
struct pcb{ char name[4]; int priority; int cputime; int needtime; int count; int round; state process; pcb * next; };
pcb * get_process(); pcb * get_process(){ pcb *q;
——8——
pcb *t; pcb *p; int i=0;
cout
while (i
q=(struct pcb *)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0;
q->priority=P_TIME-q->needtime; q->process=ready; q->next=NULL; if (i==0){ p=q; t=q; } else{
t->next=q; t=q; } i++; } //while return p; }
void display(pcb *p){
cout
——9——
"
coutname;
cout
coutcputime;
cout
coutneedtime;
cout
coutpriority;
cout
switch(p->process){
case ready:cout
case execute:cout
case block:cout
case finish:cout
}
p=p->next;
}
}
int process_finish(pcb *q){
int bl=1;
while(bl&&q){
bl=bl&&q->needtime==0;
q=q->next;
}
return bl;
}
void cpuexe(pcb *q){
pcb *t=q;
int tp=0;
——10——
while(q){
if (q->process!=finish){
q->process=ready;
if(q->needtime==0){
q->process=finish;
}
}
if(tppriority&&q->process!=finish){
tp=q->priority;
t=q;
}
q=q->next;
}
if(t->needtime!=0){
t->priority-=3;
t->needtime--;
t->process=execute;
t->cputime++;
}
}
void priority_cal(){
pcb * p;
p=get_process();
int cpu=0;
while(!process_finish(p)){
cpu++;
cout
cpuexe(p);
display(p);
——11——
}
printf("All processes have finished,press any key to exit"); getch();
}
void display_menu(){
cout
cout
cout
cout
}
pcb * get_process_round(){
pcb *q;
pcb *t;
pcb *p;
int i=0;
cout
while (i
q=(struct pcb *)malloc(sizeof(pcb));
cin>>q->name;
cin>>q->needtime;
q->cputime=0;
q->round=0;
q->count=0;
q->process=ready;
q->next=NULL;
if (i==0){
p=q;
t=q;
——12——
}
else{
t->next=q;
t=q;
}
i++;
} //while
return p;
}
void cpu_round(pcb *q){
q->cputime+=2;
q->needtime-=2;
if(q->needtime
q->needtime=0;
}
q->count++;
q->round++;
q->process=execute;
}
pcb * get_next(pcb * k,pcb * head){
pcb * t;
t=k;
do{
t=t->next;
}
while (t && t->process==finish);
——13——
if(t==NULL){
t=head;
while (t->next!=k && t->process==finish){ t=t->next;
}
}
return t;
}
void set_state(pcb *p){
while(p){
if (p->needtime==0){
p->process=finish;
}
if (p->process==execute){
p->process=ready;
}
p=p->next;
}
}
void display_round(pcb *p){
cout
coutname;
cout
coutcputime;
cout
coutneedtime;
——14——
"
cout
coutcount;
cout
coutround;
cout
switch(p->process){
case ready:cout
p=p->next;
}
}
void round_cal(){
pcb * p;
pcb * r;
p=get_process_round();
int cpu=0;
r=p;
while(!process_finish(p)){
cpu+=2;
cpu_round(r);
r=get_next(r,p);
cout
display_round(p);
set_state(p);
}
}
——15——
void main(){
display_menu();
int k;
scanf("%d",&k);
switch(k){
case 1:priority_cal();break; case 2:round_cal();break; case 3:break;
display_menu();
scanf("%d",&k);
}
}
4.6 程序测试数据及结果
4.6.1 程序测试数据
4.6.2 运用优先数调度算法的执行结果（如下图）
——16——
——17——
——18——
4.6.3 运用循环轮转调度算法的执行结果（如下图）
——19——
——20——
五.设计总结
经过这次课程设计，把课本中的理论知识转化为实践，在一定程度上加深了对优先级数调度和循环调度算法的理解，同时提高了我的动手编程能力。虽然在编程的过程中，遇到了很多的困难，但是经过我的努力，通过查参考书或者到网上搜索等途径，我所遇到的困难都被我一一的解决了。过程虽然很难，但是通过这次课程设计，结果还是让我受益匪浅。我始终相信：在前进的途中，所遇到的绊脚石，通过我的努力，它最终都会变成我脚下的垫脚石！
六.参考文献 《计算机操作系统》，汤小丹主编，西安电子科技大学出版社；
《C++语言基础教程》， 吕凤翥主编，清华大学出版社。
——21——
西安文理学院 计算机科学系
课程设计报告
设计名称： 进程调度算法设计 设计题目： 进程调度算法设计 学生学号： [1**********] 专业班级： 软件工程一班 学生姓名： 张兴华 学生成绩： 课题工作时间：
计算机科学系课程设计任务书
指导教师： 孙少波 系主任：
日 期：2012年05月29日
——1——
一、设计题目
进程调度算法的设计
二、主要内容
1、设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。
2、建立进程就绪队列。对两种不同算法编制入链子程序。 3、编制两种进程调度算法：1）优先数调度；2）循环轮转调度
开发环境：VC++语言的编程环境
三、具体要求
1、本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
2、为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
3、在优先数算法中，优先数的值为50与运行时间的差值，即
P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
4、对于遇到优先数一致的情况，采用FIFO策略解决。
开发环境：不限
四、进度安排
1、资料查找、系统分析，数据流程分析，概要设计。
2、系统详细设计、功能设计。 3、算法实现、编程调试。
4、资料整理、课程设计说明书编写。
五、完成后应上交的材料
——2——
1、课程设计说明书 2、相关源程序文件
六、总评成绩
指导教师 签名日期 年 月 日
系 主 任 审核日期 年 月 日
——3——
目 录
一.设计目的................................................................................................................... 5 二.设计内容................................................................................................................... 5 三.设计原理................................................................................................................... 6
.............................................................................................. 6 .......................................................................................... 6 四．设计步骤................................................................................................................ 6
.......................................................................................................... 6 .......................................................................................................... 7 .......................................................................................................... 7 ………………………………………………………………………..8 4.5源程序………………………………………………………………………...8 ………………………………………...………….....16
.................................................................................... 16 ................................ 16 4.6.3 运用循环轮转调度算法的执行结果（如下图）............................ 19
五.设计总结................................................................................................................. 21 六.参考文献................................................................................................................. 21
——4——
一.设计目的
通过这次课程设计，加深理解有关进程控制块、进程队列的概念，并体会和了解优先数和循环轮转调度算法的具体实施办法。培养程序设计的方法和技巧，提高编制清晰、合理、可读性好的系统程序的能力，同时加深对操作系统课程的理解。
二.设计内容
1．用语言来实现对n个进程采用不同调度算法的进程调度。
2．每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段： （1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3…。 （2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的
优先级大于0，且随机产生，优先数越大，优先级越高。
（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。 （4）进程总共需要运行时间Alltime，利用随机函数产生。 （5）进程状态，0：就绪态；1：运行态；2：阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。 3．优先数改变的原则
（1）进程在就绪队列中每呆一个时间片，优先数增加1。 （2）进程每运行一个时间片，优先数减3。
4．在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，
所有的进程控制块PCB链接成就绪队列。
三.设计原理
3.1 优先数调度算法
对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。对具有相同优先数的进程，再来采用先来先服务的次序分配处理器。系统常与任务的紧迫性和系统效率等因素确定进程的优先数。进程的优先数可以固定的，也可随进程执行过程动态变化。一个高优先数进程占用处理器后，系统处理该进程时有两种算法，一是“非抢占式”，另一种是“可抢占式”。前者是次进程占用处理器后一直运行到结束，除非本身主动让出处理器；后者则是严格保证在任何时刻总是让优先数最高的进程在处理器上运行。
3.2 循环轮转调度算法
——5——
循环轮转调度算法的具体原理是：每个进程被分配一个时间片，即该进程允许运行的时间。就绪的进程都存放在一个就绪链表中，队首的进程将获得时间片。如果在时间片结束时进程还在运行，则CPU将剥夺并分配给下一个进程。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
四．设计步骤
4.1 任务分析
(1)PCB结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可根据实验的不同，PCB结构的内容可以作适当的增删
(2)本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、执行、完成。并假设初始状态为就绪状态。
(3)为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
(4)在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
(5)对于遇到优先数一致的情况，采用FIFO策略解决。
4.2 概要设计
1.本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
2.为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
3.在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
4.对于遇到优先数一致的情况，采用FIFO策略解决。
4.3 详细设计
1.struct pcb（） 定义pcb块
2.Void display（） 显示结果信息函数
——6——
3.int process_finish(pcb *q) 进程完成标示
4.void display_round（） 显示循环轮转调度算法运行结果 5.priority_cal() 优先数调度算法
6.void cpu_round（）处理器的工作状态
4.4 流程图
——7——
4.5 源程序
源程序如下： #include #include #include #include #include #define P_NUM 5 #define P_TIME 50 enum state{ ready, execute, block, finish };
struct pcb{ char name[4]; int priority; int cputime; int needtime; int count; int round; state process; pcb * next; };
pcb * get_process(); pcb * get_process(){ pcb *q;
——8——
pcb *t; pcb *p; int i=0;
cout
while (i
q=(struct pcb *)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0;
q->priority=P_TIME-q->needtime; q->process=ready; q->next=NULL; if (i==0){ p=q; t=q; } else{
t->next=q; t=q; } i++; } //while return p; }
void display(pcb *p){
cout
——9——
"
coutname;
cout
coutcputime;
cout
coutneedtime;
cout
coutpriority;
cout
switch(p->process){
case ready:cout
case execute:cout
case block:cout
case finish:cout
}
p=p->next;
}
}
int process_finish(pcb *q){
int bl=1;
while(bl&&q){
bl=bl&&q->needtime==0;
q=q->next;
}
return bl;
}
void cpuexe(pcb *q){
pcb *t=q;
int tp=0;
——10——
while(q){
if (q->process!=finish){
q->process=ready;
if(q->needtime==0){
q->process=finish;
}
}
if(tppriority&&q->process!=finish){
tp=q->priority;
t=q;
}
q=q->next;
}
if(t->needtime!=0){
t->priority-=3;
t->needtime--;
t->process=execute;
t->cputime++;
}
}
void priority_cal(){
pcb * p;
p=get_process();
int cpu=0;
while(!process_finish(p)){
cpu++;
cout
cpuexe(p);
display(p);
——11——
}
printf("All processes have finished,press any key to exit"); getch();
}
void display_menu(){
cout
cout
cout
cout
}
pcb * get_process_round(){
pcb *q;
pcb *t;
pcb *p;
int i=0;
cout
while (i
q=(struct pcb *)malloc(sizeof(pcb));
cin>>q->name;
cin>>q->needtime;
q->cputime=0;
q->round=0;
q->count=0;
q->process=ready;
q->next=NULL;
if (i==0){
p=q;
t=q;
——12——
}
else{
t->next=q;
t=q;
}
i++;
} //while
return p;
}
void cpu_round(pcb *q){
q->cputime+=2;
q->needtime-=2;
if(q->needtime
q->needtime=0;
}
q->count++;
q->round++;
q->process=execute;
}
pcb * get_next(pcb * k,pcb * head){
pcb * t;
t=k;
do{
t=t->next;
}
while (t && t->process==finish);
——13——
if(t==NULL){
t=head;
while (t->next!=k && t->process==finish){ t=t->next;
}
}
return t;
}
void set_state(pcb *p){
while(p){
if (p->needtime==0){
p->process=finish;
}
if (p->process==execute){
p->process=ready;
}
p=p->next;
}
}
void display_round(pcb *p){
cout
coutname;
cout
coutcputime;
cout
coutneedtime;
——14——
"
cout
coutcount;
cout
coutround;
cout
switch(p->process){
case ready:cout
p=p->next;
}
}
void round_cal(){
pcb * p;
pcb * r;
p=get_process_round();
int cpu=0;
r=p;
while(!process_finish(p)){
cpu+=2;
cpu_round(r);
r=get_next(r,p);
cout
display_round(p);
set_state(p);
}
}
——15——
void main(){
display_menu();
int k;
scanf("%d",&k);
switch(k){
case 1:priority_cal();break; case 2:round_cal();break; case 3:break;
display_menu();
scanf("%d",&k);
}
}
4.6 程序测试数据及结果
4.6.1 程序测试数据
4.6.2 运用优先数调度算法的执行结果（如下图）
——16——
——17——
——18——
4.6.3 运用循环轮转调度算法的执行结果（如下图）
——19——
——20——
五.设计总结
经过这次课程设计，把课本中的理论知识转化为实践，在一定程度上加深了对优先级数调度和循环调度算法的理解，同时提高了我的动手编程能力。虽然在编程的过程中，遇到了很多的困难，但是经过我的努力，通过查参考书或者到网上搜索等途径，我所遇到的困难都被我一一的解决了。过程虽然很难，但是通过这次课程设计，结果还是让我受益匪浅。我始终相信：在前进的途中，所遇到的绊脚石，通过我的努力，它最终都会变成我脚下的垫脚石！
六.参考文献 《计算机操作系统》，汤小丹主编，西安电子科技大学出版社；
《C++语言基础教程》， 吕凤翥主编，清华大学出版社。
——21——