课程设计说明书(操作系统)题目:进程调度院系:计算机科学与工程学院专业班级:信息安全13-2学号:20133029xx学生姓名:xx指导教师:xx2015年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的方法。
在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。
本程序用时间片轮转调度算法对多个进程进行调度,每个进程有三个状态就绪、运行和完成,初始状态为就绪状态。
时间片轮转调度算法中,系统将所有的就绪进程按先来先服务算法的原则,排成一个队列,每次调度时,系统把处理机分配给队列首进程,并让其执行一个时间片。
当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序根据这个请求停止该进程的运行,将它送到就绪队列的末尾,再把处理机分给就绪队列中新的队列首进程,同时让它也执行一个时间片。
(1)建立一个进程控制块。
PCB来代表。
PCB包括:进程名、链接指针、到达时间、估计运行时间、剩余时间和进程状态。
进程状态分为就绪(W)、运行(R)和完成(F)。
(2)为每个进程任意确定一个要求运行时间和到达时间。
(3)按照进程到达的先后顺序排成一个循环队列。
再设一个对首指针指向第一个到达进程的首址。
(4)执行处理机调度时,开始选择对首的第一个进程运行。
另外再设一个当前运行进程的指针,指向当前正运行的进程。
(5)执行:a)预计运行时间减1;b)输出当前运行进程的名字。
(6)进程执行一次后,若该进程的剩余运行时间为零,则将该进程的状态置为完成态F,并退出循环队列;若不为空,则将其移至队尾。
继续在运行队首的进程。
(7)若就绪队列不空,则重复上述的(5)和(6)步骤直到所有进程都运行完为止。
在所设计的调度程序中,要求包含显示或打印语句。
以便显示或打印每次选操作系统课程设计中进程的名称及运行一次后队列的变化情况。
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;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 );}}}}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 个作业没有完成\n",total );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源代码//进程调度模拟程序,以时间片轮转调度算法为核心#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; //指令执行时间}index;struct pcb {char filename[10]; //进程名int id; //作业编号int exetoIndex; //当前正在执行指令char status; //当前状态int wtime; //等待时间};struct pcb jobpcb[100]; //pcb表typedef struct job{index idx[100]; //指令集int pcbnum; //pcb编号对应}job;job jobtab[100]; //作业表char jobp[3][50]; //作业//队列结构体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;}//申请jobint 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 %c % d \n",j+1, 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++){ln=0;jnum=AllocJob();if(jnum == -1) return 0;pnum=AllocPCB();if(pnum == -1) return 0;jobtab[jnum].pcbnum=pnum;strcpy(jobpcb[pnum].filename," ");jobpcb[pnum].status='r';jobpcb[pnum].exetoIndex=0;jobpcb[pnum].id=jnum;jobpcb[pnum].wtime=0;int len=strlen(jobp[i]);pos=0;while(pos<len){while(jobp[i][pos]==' ') pos++;jobtab[jnum].idx[ln].name=jobp[i][pos++];///while(jobp[i][pos]==' ') pos++;bpos=0;while(jobp[i][pos]!=' ')buff[bpos++]=jobp[i][pos++];buff[bpos]='\0';jobtab[jnum].idx[ln].time=change(buff);/////if(pos<len) {pos++;ln++;}}}displayIndex();}//初始化队列void initqueue(struct Qnode *l){l->head=0;l->tail=0;}//插进入队列/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;else*pcbnum=l->pcbnum[l->head++];}//显示作业void display(){int i,j;for(i=0;i<5;i++){printf(" 队列%d ",i);for(j=Queue[i].head;j<Queue[i].tail;j++)printf("pcb 编号%d \n\n ",Queue[i].pcbnum[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;case 'i': insertqueue(& Queue[2],i);jobpcb[i].status='i'; break;case 'o': insertqueue(& Queue[3],i);jobpcb[i].status='o'; break;case 'w': insertqueue(& Queue[4],i);jobpcb[i].status='w'; break;case 'h':jobpcb[i].status='h'; num=jobpcb[i].id;jobtab[num].pcbnum=-1;jobpcb[i].id=-1;}if(cmd== 'h') {jobpcb[i].wtime=0; total--;}jobpcb[i].wtime=jobtab [ jobpcb[i].id ].idx[Index].time;(*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,jobpcb[i].status,jobpcb[i].wtime );fclose(fp);}//作业入队列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[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'; break;case 'w': insertqueue(& Queue[4],pcbnum);jobpcb[pcbnum].status='w'; break;case 'h': jobpcb[pcbnum].status='h'; num=jobpcb[pcbnum].id;jobtab[num].pcbnum=-1;jobpcb[pcbnum].id=-1;}if(cmd== 'h') {jobpcb[pcbnum].wtime=0;printf(" \n\t\t作业%d 完成\n", pcbnum+1, jobpcb[ pcbnum].status);(*total)--;}else jobpcb[pcbnum].wtime=jobtab [ jobpcb[pcbnum].id ].idx[Index].time;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);}}//得到队列的首元素int GetHead(struct Qnode l){return l.pcbnum[l.head];}//执行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);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 );}}}}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 个作业没有完成\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++){jobpcb[i].exetoIndex=0;strcpy(jobpcb[i].filename," nothing");jobpcb[i].id=-1;jobpcb[i].status='r';jobpcb[i].wtime=0;}for(i=0;i<100;i++)jobtab[i].pcbnum=-1;for(i=0;i<5;i++)initqueue(&Queue[i]);}int main(){char start;printf("欢迎界面");start=getch();if(start!=NULL){InitFile();CreatePcbLine();Run ();}return 0;}4.实验结果及分析4.1 使用说明先用文本编辑器写三个虚拟程序保存在改程序目录下,可以分别命名为p1.prc p2.prc p3.prc。