课程设计说明书

（操作系统）

题目： 进程调度

院 系：计算机科学与工程学院

专业班级： 信息安全13-2

学 号： 20133029xx

学生姓名： xx

指导教师： xx

20xx年 12月 15日

安徽理工大学课程设计（论文）任务书 计算机科学与工程学院

安徽理工大学课程设计（论文）成绩评定表

摘要

现代计算机系统中，进程是资源分配和独立运行的基本单位，是操作系统的核心概念。因而，进程就成为理解操作系统如何实现系统管理的最基本，也是最重要的概念。进程调度是进程管理过程的主要组成部分，是必然要发生的事件。

在现代操作系统中，进程的并发机制在绝大多数时候，会产生不断变化的进程就绪队列和阻塞队列。处于执行态的进程无论是正常或非正常终止、或转换为阻塞状态，都会引发从就绪队列中，由进程调度选择一个进程进占CPU。

进程调度的核心是进程调度的算法．在本课程设计中，用良好清晰的界面向用户展示了进程调度中的时间片轮转调度算法。在最终实现的成果中，用户可指定需要模拟的进程数，CPU时间片和进程的最大执行时间，并且选择需要演示的算法，界面将会动态的显示进程调度过程及各个队列的变化。 通过此进程调度模拟系统，用户可以对时间片轮转调度算法有进一步以及直观的了解。

关键词:进程，调度，PCB，时间片轮转

目录

1.设计目的 ................................................................................................................................................... 6

2.设计思路 ................................................................................................................................................... 6

3.设计过程 ................................................................................................................................................... 8

3.1流程图 ................................................................................................................................................ 8

3.2算法 .................................................................................................................................................... 8

3.3数据结构 .......................................................................................................................................... 10

3.4源代码 .............................................................................................................................................. 10

4.实验结果及分析 ..................................................................................................................................... 20

4.1 使用说明 ......................................................................................................................................... 20

4.2程序演示 .......................................................................................................................................... 20

5.实验总结 ................................................................................................................................................. 24

6.参考文献 ................................................................................................................................................. 24

安徽理工大学--操作系统课程设计报告

1.设计目的

根据设计任务，用自己熟悉的计算机语言编制程序，在机器上调试运行，并通过上机考核。编写一程序，可以创建若干个虚拟进程，并对若干个虚拟进程进行调度，调度策略为时间片轮转。

虚拟程序的描述：

虚拟指令的格式： 操作命令 操作时间

其中，操作命令有以下几种：

? C : 表示在CPU上计算

? I ：表示输入

? O：表示输出

? W：表示等待

? H：表示进程结束

操作时间代表该操作命令要执行多长时间

假设I/O设备的数量没有限制

I、O、W三条指令实际上是不占用CPU的，执行这三条指令就应将进程放入对应的等待队列（Input等待队列、Output等待队列、Wait等待队列） 例有一虚拟程序p1.prc描述如下：

c 30 o 12 c 9 i 14 h 0

该虚拟程序表示的含义是：先在CPU上计算30秒，再在输出设备上输出12秒，计算9 秒，在输入设备上输入14秒，程序结束。

2.设计思路

进程调度是操作系统中的重要功能，用来创建进程、撤消进程、实现进程状态转换，它提供了在可运行的进程之间复用CPU的方法。在进程管理中，进程调度是核心，因为在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态，当就绪进程个数大于处理器数目时，就必须依照某种策略决定哪些进程优先占用处理器。本程序用时间片轮转调度算法对多个进程进行调度，每个进程有三个状态就绪、运行和完成，初始状态为就绪状态。 时间片轮转调度算法中，系统将所有的就绪进程按先来先服务算法的原则，排成一个队列，每次调度时，系统把处理机分配给队列首进程，并让其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序根据这个请求停止该进程的运行，将它送到就绪队列的末尾，再把

6

安徽理工大学--操作系统课程设计报告

处理机分给就绪队列中新的队列首进程，同时让它也执行一个时间片。

（1）建立一个进程控制块。PCB来代表。PCB包括：进程名、链接指针、到达时间、估计运行时间、剩余时间和进程状态。进程状态分为就绪（W）、运行（R）和完成（F）。

（2）为每个进程任意确定一个要求运行时间和到达时间。

（3）按照进程到达的先后顺序排成一个循环队列。再设一个对首指针指向第一个到达进程的首址。

（4）执行处理机调度时，开始选择对首的第一个进程运行。另外再设一个当前运行进程的指针，指向当前正运行的进程。

（5）执行：a)预计运行时间减1；b)输出当前运行进程的名字。

（6）进程执行一次后，若该进程的剩余运行时间为零，则将该进程的状态置为完成态F，并退出循环队列；若不为空，则将其移至队尾。继续在运行队首的进程。

（7）若就绪队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。在所设计的调度程序中，要求包含显示或打印语句。以便显示或打印每次选操作系统课程设计中进程的名称及运行一次后队列的变化情况。

7

安徽理工大学--操作系统课程设计报告

3.设计过程

3.1流程图

3.2算法

如果就绪队列中有n个进程，且时间片为q，则每个进程会得到的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q个时间单元，直到它的下一个时间片为止

void Run (){

int i, flag=0, time=10, pcbnum, Index=0, exenum, num, quenum;

char cmd;

int j,m,n;

int total=0;

8

安徽理工大学--操作系统课程设计报告

JobEnQueueInit( &total );

save();

while( total!=0 ){

if( !EmptyQueue( Queue[1]) ){

outqueue(&Queue[1],&pcbnum);

insertqueue(&Queue[0], pcbnum);

}

else pcbnum=GetHead(Queue[0]);

delay();

jobpcb[ pcbnum].status='e';

printf(" \n\t\t作业 %d \n",pcbnum+1);

printf(" \t\t\t所处状态: %c \t执行了 %d 秒\n", jobpcb[ pcbnum].status, time);

for(i=0;i<3;i++){

if(jobpcb[i].id>=0){

//所有的作业除在就绪队列获执行结束的外等待时间 都减去时间片

if( jobpcb[i].status!='r'&&jobpcb[i].status!='h') jobpcb[i].wtime=jobpcb[i].wtime-time;

if(jobpcb[i].wtime<=0){ //查找所有的队列 所在位置

for(j=0;j<5;j++){

for(m=Queue[j].head;m<Queue[j].tail;m++){

if(Queue[j].pcbnum[m]==i) {flag=1;break; }

}

if(flag==1) break;

}

if(flag==1){ //删除该指令

for(n=m;n<Queue[j].tail;n++)

Queue[j].pcbnum[n]=Queue[j].pcbnum[n+1];

Queue[j].tail--;

jobpcb[i].exetoIndex++;

Index=jobpcb[i].exetoIndex;

JobEnQueue( i,Index,&total );

9

安徽理工大学--操作系统课程设计报告

}

}

}

}

if(!EmptyQueue( Queue[1]) ){

outqueue(&Queue[0],&pcbnum);

if(jobpcb[pcbnum].wtime>0){

insertqueue(&Queue[1], pcbnum); jobpcb[pcbnum].status='r';

}

}

printf(" \n\n\t\t 还有\t %d 个作业没有完成

save();

}

}

3.3数据结构

void delay()

int change(char *m)

int AllocPCB()

int AllocJob()

void displayIndex()

int CreatePcbLine()

void initqueue(struct Qnode *l)

void insertqueue(struct Qnode *l,int pcbnum)

int EmptyQueue( struct Qnode l)

void outqueue(struct Qnode *l,int *pcbnum)

void display()

void JobEnQueueInit( int * total)

void save ()

void JobEnQueue( int pcbnum,int Index ,int *total)

int GetHead(struct Qnode l)

void Run ()

void InitFile()

3.4源代码

10 \n",total );

安徽理工大学--操作系统课程设计报告

//进程调度模拟程序，以时间片轮转调度算法为核心 #define NULL 0

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <malloc.h>

#include <time.h>

FILE *GroupFile[10];

//定义一个pcb的结构体

typedef struct index{

char name; //指令

int time; //指令执行时间

struct pcb {

char filename[10]; //进程名

};

struct pcb jobpcb[100]; //pcb表

typedef struct job{

index idx[100]; //指令集

job jobtab[100]; //作业表

char jobp[3][50]; //作业

//队列结构体

11 int pcbnum; //pcb编号 对应 }job; int id; //作业编号 int exetoIndex; //当前正在执行指令 char status; //当前状态 int wtime; //等待时间 }index;

安徽理工大学--操作系统课程设计报告

struct Qnode

{

int pcbnum[100]; //pcb编号

int head,tail;

};

struct Qnode Queue[5]; //5个队列 0E 1R 2I 3O 4W

void initqueue(struct Qnode *l);

//延迟

void delay( ){

time_t begin,end;

time(&begin);

do {

time(&end);

} while((end-begin)<=1);

}

//字符转化为数值

int change(char *m){

int i,j=0;

int len=strlen(m);

for(i=0;i<len;i++)

j=j*10+m[i]-'0';

return j;

}

//申请 pcb进程块

int AllocPCB(){

int i;

for(i=0;i<3;i++)

if(jobpcb[i].id ==-1) break;

if(i<3)

return i;

return -1;

12

安徽理工大学--操作系统课程设计报告

}

//申请job

int AllocJob(){

int i;

for(i=0;i<3;i++)

if(jobtab[i].pcbnum == -1) break; if(i<3)

return i;

return -1;

}

//显示指令

void displayIndex(){

int i,j;

for(i=0;i<3;i++){

printf(" Job % d \n",i+1); for(j=0;j<10;j++)

printf(" %d jobtab[i].idx[j].name,jobtab[i].idx[j].time); }

}

//创建进程程序

int CreatePcbLine(){

char line[10];

int i,ll,jnum, pnum, ln=0, bpos, pos=0; char buff[50];

char name [20];

char ch;

for(i=0;i<3;i++){

13 %c % d \n",j+1,

安徽理工大学--操作系统课程设计报告

ln=0; }

//初始化队列

void initqueue(struct Qnode *l){ l->head=0; }

14

l->tail=0;

}

displayIndex();

}

}

if(pos<len) {pos++;ln++;

buff[bpos]='\0';

jobtab[jnum].idx[ln].time=change(buff);/////

bpos=0;

while(jobp[i][pos]!=' ')

jnum=AllocJob(); if(jnum == -1) return 0; pnum=AllocPCB(); if(pnum == -1) return 0; jobtab[jnum].pcbnum=pnum; jobpcb[pnum].status='r'; jobpcb[pnum].exetoIndex=0; jobpcb[pnum].id=jnum; jobpcb[pnum].wtime=0; pos=0; while(pos<len){

while(jobp[i][pos]==' ') pos++;

jobtab[jnum].idx[ln].name=jobp[i][pos++];/// while(jobp[i][pos]==' ') pos++;

strcpy(jobpcb[pnum].filename," ");

int len=strlen(jobp[i]);

buff[bpos++]=jobp[i][pos++];

安徽理工大学--操作系统课程设计报告

//插进入队列/

void insertqueue(struct Qnode *l,int pcbnum){

l->pcbnum[l->tail++]=pcbnum;

}

//队列是否为空

int EmptyQueue( struct Qnode l){

if(l.head==l.tail) return 1;

return 0;

}

//删除队列

void outqueue(struct Qnode *l,int *pcbnum)

{

if (l->head>=l->tail ) *pcbnum=-1;

}

//显示作业

void display(){

int i,j;

}

//作业入队列

void JobEnQueueInit( int * total){

int i,num ,Index=0;

char cmd; for( i=0;i<3;i++) if(jobpcb[i].id>=0){ cmd=jobtab[ jobpcb[i].id ].idx[ Index ].name; switch(cmd){ case 'c': insertqueue(& Queue[1],i); jobpcb[i].status='r'; break; for(i=0;i<5;i++){ for(j=Queue[i].head;j<Queue[i].tail;j++) printf("pcb 编号 %d \n\n ",Queue[i].pcbnum[j]); printf(" 队列 %d ",i); else *pcbnum=l->pcbnum[l->head++]; } case 'i': insertqueue(& Queue[2],i);jobpcb[i].status='i'; break;

15

安徽理工大学--操作系统课程设计报告

case 'o': insertqueue(& Queue[3],i);jobpcb[i].status='o'; break;

case 'w': insertqueue(& Queue[4],i);jobpcb[i].status='w'; break;

case } if(cmd== 'h') {jobpcb[i].wtime=0; total--;} jobpcb[i].wtime=jobtab [ jobpcb[i].id ].idx[Index].time; 'h':jobpcb[i].status='h'; num=jobpcb[i].id;jobtab[num].pcbnum=-1;jobpcb[i].id=-1; (*total)++; } }

//保存结果

void save (){

FILE *fp;

int i;

fp=fopen("pcbtable.txt","a");

fprintf(fp," 文件名 作业编号 执行到指令数 所处状态 等待时间 \n" );

for(i=0;i<3;i++)

fprintf(fp," \t %s \t %d \t %d \t %c \t %d \n" ,

jobpcb[i].filename,jobpcb[i].id,jobpcb[i].exetoIndex,

}

//作业入队列

void JobEnQueue( int pcbnum,int Index ,int *total){

int num;

char cmd; if(jobpcb[pcbnum].id>=0){ cmd=jobtab[ jobpcb[pcbnum].id ].idx[ Index ].name; switch(cmd){ case 'c': insertqueue(&Queue[1],pcbnum); jobpcb[i].status,jobpcb[i].wtime ); fclose(fp); jobpcb[pcbnum].status='r'; break;

case 'i': insertqueue(& Queue[2],pcbnum);jobpcb[pcbnum].status='i'; break;

case 'o': insertqueue(& Queue[3],pcbnum);jobpcb[pcbnum].status='o';

16

安徽理工大学--操作系统课程设计报告

break;

case 'w': insertqueue(& Queue[4],pcbnum);jobpcb[pcbnum].status='w'; break;

case } if(cmd== 'h') { } else jobpcb[pcbnum].wtime=jobtab jobpcb[pcbnum].wtime=0; printf(" \n\t\t作业 %d 完成\n", pcbnum+1, (*total)--; 'h': jobpcb[pcbnum].status='h'; num=jobpcb[pcbnum].id;jobtab[num].pcbnum=-1;jobpcb[pcbnum].id=-1; jobpcb[ pcbnum].status);

[ jobpcb[pcbnum].id ].idx[Index].time;

}

//得到队列的首元素

int GetHead(struct Qnode l){

}

//执行

void Run (){

int i, flag=0, time=10, pcbnum, Index=0, exenum, num, quenum;

char cmd;

int j,m,n;

int total=0; JobEnQueueInit( &total ); save(); while( total!=0 ){ if( !EmptyQueue( Queue[1]) ){ outqueue(&Queue[1],&pcbnum);

17 return l.pcbnum[l.head]; } printf(" \n\t\t作业 %d \n ", pcbnum+1); printf("\t\t\t\t所处状态 ： %c \n",jobpcb[ pcbnum].status); printf("\t\t还需要时间 %d 秒\n",jobpcb[ pcbnum].wtime);

安徽理工大学--操作系统课程设计报告

} insertqueue(&Queue[0], pcbnum);

else pcbnum=GetHead(Queue[0]);

delay();

jobpcb[ pcbnum].status='e';

printf(" \n\t\t作业 %d \n",pcbnum+1);

printf(" \t\t\t所处状态: %c \t执行了 %d 秒\n", jobpcb[ pcbnum].status, time); for(i=0;i<3;i++){

if(jobpcb[i].id>=0){

//所有的作业除在就绪队列获执行结束的外等待时间 都减去时间片

}

}

if(!EmptyQueue( Queue[1]) ){

outqueue(&Queue[0],&pcbnum); if(jobpcb[pcbnum].wtime>0){

18 } for(n=m;n<Queue[j].tail;n++) Queue[j].tail--; Queue[j].pcbnum[n]=Queue[j].pcbnum[n+1]; jobpcb[i].exetoIndex++; Index=jobpcb[i].exetoIndex; JobEnQueue( i,Index,&total ); } if( jobpcb[i].status!='r'&&jobpcb[i].status!='h') jobpcb[i].wtime=jobpcb[i].wtime-time; if(jobpcb[i].wtime<=0){ //查找所有的队列 所在位置 for(j=0;j<5;j++){ } //删除该指令 for(m=Queue[j].head;m<Queue[j].tail;m++){ if(Queue[j].pcbnum[m]==i) } {flag=1;break; } if(flag==1) break; if(flag==1){

安徽理工大学--操作系统课程设计报告

} } insertqueue(&Queue[1], pcbnum); jobpcb[pcbnum].status='r';

printf(" \n\n\t\t 还有\t %d 个作业没有完成 \n",total ); save();

}

//初始化

void InitFile(){

int i;

GroupFile[0]=fopen("p1.prc","r");

GroupFile[1]=fopen("p2.prc","r");

GroupFile[2]=fopen("p3.prc","r");

fgets(jobp[0],255,GroupFile[0]);

fgets(jobp[1],255,GroupFile[1]);

fgets(jobp[2],255,GroupFile[2]);

for(i=0;i<100;i++){ } for(i=0;i<100;i++) jobtab[i].pcbnum=-1; jobpcb[i].exetoIndex=0; strcpy(jobpcb[i].filename," nothing"); jobpcb[i].status='r'; jobpcb[i].wtime=0; } jobpcb[i].id=-1;

for(i=0;i<5;i++)

initqueue(&Queue[i]);

}

int main(){

char start;

printf("欢迎界面");

start=getch();

if(start!=NULL){

19

安徽理工大学--操作系统课程设计报告

InitFile();

CreatePcbLine();

Run ();

} } return 0;

4.实验结果及分析

4.1 使用说明

先用文本编辑器写三个虚拟程序保存在改程序目录下，可以分别命名为p1.prc p2.prc p3.prc。然后编一进程调度程序，将这三个虚拟程序创建成进程，并按各虚拟进程的指令要求执行和调度。用一个文本文件， 里面只能放一个整数，表示一个时间因子，用于调节设计程序进程调度.EXE的执行速度。

请在该程序目录下建立三个进程文件：

p1.prc p2.prc p3.prc

文件内容格式为：

操作命令 操作时间

c指令：CPU上计算

i指令：输入

o指令：输出

w指令：等待

h指令：结束。

4.2程序演示

20

安徽理工大学--操作系统课程设计报告

图1 程序与进程文件

图2 程序初始界面

21

安徽理工大学--操作系统课程设计报告

图3 程序运行状态

图4 程序运行状态

22

安徽理工大学--操作系统课程设计报告

图5 运行结束

图6 程序运行结果

23

安徽理工大学--操作系统课程设计报告

5.实验总结

本次课程设计虽然遇见许多困难，刚开始接触到课题感觉到无从下手，后来通过逐步的思考，认真的研究逐步的建立了整个宏观的流程，然后就是一段时间的埋头苦干，狂敲代码，最终都解决了。在设计过程中遇见问题而提出问题并且寻找解决方法的过程中颇是受益。通过咨询有更多经验的人和在网上、书籍上查找相应的资料，最后在规定的收件内完成本次课程设计。

但是，细观察设计内容可以发现许多的问题，一下是我个人认为的不足之处：设计过程中，存在许多不完整性的控制，整个设计流程简单，但是却没有阵中的使用进程机制。通过这次课程设计，我们对程序设计有了基本的认识，对计算机操作系统的进程机制也有了更进一步的理解，而且在设计过程中学习的团队合作精神和提高个人解决问题的能力都有了相应的见识。相信在这次设计能为今后的开发设计做一个很好的铺垫。

当然，我的成功也离不开大家的帮助。所以，在此我要感谢给于过我帮助的指导老师以及热心的同学们。

6.参考文献

[1] 龚沛曾等编.C/C++程序设计教程.北京：高等教育出版社,2004.

[2] [美]Prata S.著. C Primer Plus（第5版 中文版）.北京：人民邮电出版社,2005.

[3] 汤子瀛等编著. 计算机操作系统.西安：西安电子科技大学出版社,2011

[4] 胡志刚，谭长庚等，《计算机操作系统》，中南大学出版社20xx年

[5] 罗宇，邹鹏等，《操作系统》（第二版），电子工业出版社20xx年4月

[6] 庞丽萍，《操作系统原理》，华中理工大学出版社，20xx年

24