课程设计报告题 目 进程调度程序设计课 程 名 称 操作系统课程设计院 部 名 称 计算机工程学院专 业 计算机科学与技术班 级 13计算机科学与技术(单)(1) 学 生 姓 名 周敏健学 号 1305201013课程设计地点 A104课程设计学时 20学时指 导 教 师 何 健金陵科技学院教务处制 成绩目录摘要 (3)一、课程设计的目的和要求 (4)二、系统需求分析 (4)三、总体设计 (5)四、详细设计 (6)五、测试、调试过程 (9)六、结论与体会 (11)七、参考文献 (12)附录：源程序 (12)课程设计课题进程调度程序设计摘要在多道系统中，对批处理作业需要进行作业调度。
作业调度是在资源满足的条件下，将处于就绪状态的作业调入内存，同时生成与作业相对应的进程，并未这些进程提供所需要的资源。
进程调度需要根据进程控制块（PCB）中的信息，检查系统是否满足进程的资源需求。
只有在满足进程的资源需求的情况下，系统才能进行进程调度。
下面是几种常见的作业调度算法：先来先服务（FCFS）、优先算法、轮换算法、短作业优先算法以及最高响应比优先法等，本文将对前两种算法进行详细的介绍。
关键词：进程调度，优先级，FCFS，PCB，作业，资源一、课程设计的目的和要求1、目的进程调度是处理机管理的核心内容。
本设计要求用C语言编写和调试一个简单的进程调度程序。
通过设计本可以加深理解有关进程控制块、进程队列的概念，并体会和了解最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法的具体实施办法。
2、要求1）进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。
2）每个进程有一个进程控制块（PCB）表示。
进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
3）进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。
进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
4）每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
5）就绪进程获得CPU后都只能运行一个时间片。
用已占用CPU时间加1来表示。
如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
6）每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。
7）重复以上过程，直到所要进程都完成为止。
二、系统需求分析编写一个模拟进程调度的程序，将每个进程抽象成一个进程控制块PCB，PCB 用一个结构体描述。
采用两种不同的调度算法来实现功能，主要有如下几大功能模块组成。
（1）创建优先数PCB模块用循环来实现对每个进程的进程名、进程优先数（随机分配）以及所需时间的录入。
将进程队列存放到就绪队列等待执行。
（2）优先数调度算法模块从优先级最高（就绪队列的第一个进程）的开始执行，每执行一次优先数减1，并重新放入就绪队列进行排序，对排序完的继续运行直到所有进程都结束。
（3）FCFS创建PCB模块对N个进程的信息进行输入：进程名、到达时间、需要时间等。
每输入一个进程，按进程的到达时间进行排序，记下前驱和后继的方法。
（4）FCFS调度算法模块当系统时间与第一个进程到达时间一致时，将进程状态置为Run，直到这个进程执行完，再判断下个进程的到达时间，若系统时间大于下个进程的到达时间，即上个进程的结束时间就是下个进程的开始时间，反之就等待系统时间。
进程结束后放入完成队列。
（5）主函数及菜单显示由主菜单进入显示界面，进行算法选择。
三、总体设计进程是程序在处理机上的执行过程。
进程存在的标识是进程控制块（PCB），所谓系统创建一个进程，就是由系统为某个程序设置一个PCB，用于对该进程进行控制和管理。
进程任务完成，由系统收回其PCB，该进程便消亡。
每个进程可有三个状态：运行状态、就绪状态和完成状态。
因此设计三个链队列，finish 为完成队列的头指针，wait为就绪队列的头指针。
因为每一时刻，CPU只能运行一个进程，所以运行队列只有一个run指针指向当前运行的进程。
考虑到处理的方便，将它们设为全局变量。
总体结构框架图：四、详细设计（1）优先数调度算法优先调度算法要为每一个进程设一个优先数，它总是把处理机给就绪队列中具有最高优先权的进程。
常用的算法有静态优先权法和动态优先权法。
本程序采用了动态优先权法，使进程的优先权随时间而改变。
初始的进程优先数取决于进程运行所需的时间，时间大，则优先数低，所以采取了将进程优先数定位最大的那个进程，随着进程的运行优先数进行调整，每次运行时都是从就绪队列中选取优先数最大的进程运行，所以将就绪队列按照优先数的大小从高到低排序，这样，每次取队头进程即可。
优先数算法 界面F C F S 算法开始（2）先来先服务调度算法先来先服务调度算法是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行，一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某种事件而不能继续运行时才释放处理机。
优先数调度算法输入进程信息将进程放入ready 队列进程按优先数大小排序 取ready 队列首进程送入run执行一个时间片,优先数-1,运行时间+1是否还需输入进程 YN 输入时进程是否完成N执行队列时 放入完成队列YFCFS 调度算法输入进程信息将进程放入ready 队列进程按到达先后顺序排序 取ready 队列首进程送入run执行一个时间片,运行时间+1是否还需输入进程 YN 输入时进程是否完成 N执行队列时 放入完成队列Y五、测试、调试过程界面优先数算法输入优先数算法输出FCFS算法输入FCFS算法输出遇到的问题：在设计程序时，在算法上面出现了一些错误，优先数不是由大到小排序，而是应该这样理解，当进程执行一个时间片时，优先数减一（使用CPU的时间变少，反而优先级高），因此，优先级高的优先数应该是比较小的，而不是优先数大的优先级大。
在程序调试时，链表发生了错误，该内存不可写或者就是程序直接结束，但最终结果不是我想要的，经过一番折腾，最后发现，头指针和头结点混淆，有些地方没有给指针分配内存，语句的先后顺序不正确，以及没有考虑到链表最后没有设置结束标志。
六、结论与体会做这个程序我断断续续的算下来应该总共用了2天，主要是花时间在观察别人的算法读别人的程序，然后才开始写自己的程序，期间参考了前人的程序并进行了改善和加工，这让我对进程调度的理解再次加深了，这是在平常学习的基础上，与程序相结合的过程，让我再次感受到编程给我们带来的无穷魅力，只要自己有兴趣，其实编程也是一件有趣的事，为了达到一定的要求，我们必须多次尝试用不同的方法去实现它，比如，进程调度有先来先服务算法，对于这个算法，可以用数组实现，也可以用链表实现，但是到底哪个更好哪个更灵活呢，相信学过C语言的人都知道肯定是用链表实现最好了。
这次设计还是有一些不足之处的，比如在算法和运行效率上还是有些欠缺的，需要进一步去改善程序代码，提高效率，减少冗余和错误，让使用者更清晰的观察和理解进程调度。
七、参考文献[1]任爱华、罗晓峰. 操作系统实用教程（第三版）[M].北京：清华大学出版社,2009[2]谌卫军、王浩娟. 操作系统[M]. 北京：清华大学出版社，2012.5[3]（日）前桥和弥（Maebasi Kazuya）. 征服C指针[M]. 吴雅明译. 北京：人民邮电出版社，2013.2附录：源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#include<windows.h>#include<time.h>typedef struct node{char name[10]; //进程名int prio; //进程优先数int cputime; //进程占用CPU时间int needtime; //进程到完成还要的时间int arrivetime; //进程到达时间int starttime; //进程开始时间int finishtime; //进程完成时间int servicetime; //进程服务时间char state; //进程的状态struct node *next;}PCB;PCB *finish,*ready,*run; //队列指针int N; //进程量void firstin(){run=ready; //就绪队列头指针赋值给运行头指针run->state='R'; //进程状态变为运行态ready=ready->next; //就绪对列头指针后移到下一进程}void prt1(char a){switch(a){case 1: /*优先数法*/printf("名字\t进程占用CPU时间\t需要的时间\t优先级数\t状态\n");break;case 2: /*先来先服务算法*/printf("名字\t到达时间\t开始时间\t服务时间\t完成时间\t状态\n");break;default:break;}}void prt2(char a,PCB *q){switch(a){case 1:printf("%s\t%d\t\t%d\t\t%d\t\t%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);break;case 2:printf("%s\t%d\t\t%d\t\t%d\t\t%d\t\t%c\n",q->name,q->arrivetime,q->starttime,q->servicetim e,q->finishtime,q->state);break;default:break;}}void prt(char algo){PCB *p;prt1(algo); //输出文字格式if(run!=NULL) //如果运行指针不空prt2(algo,run); //输出当前正在运行的PCBp=ready; //输出就绪队列PCBwhile(p!=NULL){prt2(algo,p);p=p->next;}p=finish; //输出完成队列的PCBwhile(p!=NULL){prt2(algo,p);p=p->next;}getchar(); //压任意键继续}void insert1(PCB *q){PCB *p1,*s,*r;int b;s=q; //待插入的PCB指针p1=ready; //就绪队列头指针r=p1; //做p1的前驱指针b=1;while((p1!=NULL)&&b) //根据优先数确定插入位置if(p1->prio>=s->prio){r=p1;p1=p1->next;}elseb=0;if(r!=p1) //如果条件成立说明插入在r与p1之间{r->next=s;s->next=p1;}else{s->next=p1; //否则插入在就绪队列的头ready=s;}}void insert2(PCB *q){PCB *p1,*s,*r;int b;s=q; //指针s指向新要插入的进程p1=ready; //指针p1指向原来的进程的对首r=p1; //使用指针r指向p1前面的进程b=1;while((p1!=NULL)&&b){if(p1->arrivetime<s->arrivetime){r=p1;p1=p1->next;}elseb=0;}if(r!=p1){r->next=s;s->next=p1;}else{s->next=p1;ready=s;}}void create1(char alg){PCB *p;int i,time;char na[10];ready=NULL; //就绪队列头指针finish=NULL; //完成队列头指针run=NULL; //运行队列头指针//输入N个进程名和所需时间创建PCBfor(i=1;i<=N;i++){printf("请输入第%d个进程的名字和运行时间\n进程名:",i);p=(PCB *)malloc(sizeof(PCB));scanf("%s",na);printf("所需时间:");scanf("%d",&time);strcpy(p->name,na);p->cputime=0;p->needtime=time;p->state='W';p->prio=rand()%15+1; //随机分配优先数[1,15]if(ready!=NULL) //就绪队列不空则调用插入函数插入insert1(p); //对新进程插入就绪队列else{p->next=ready; //创建就绪队列的第一个PCBready=p;}}system("cls");printf(" 优先数算法结果输出\n");printf("---------------------------------------------------------------------------\n");prt(alg); //输出进程PCB信息run=ready; //将就绪队列的第一个进程投入运行ready=ready->next;run->state='R';}void create2(char alg){PCB *p;int i;ready=NULL;run=NULL;finish=NULL;for(i=0;i<N;i++){p=(PCB *)malloc(sizeof(PCB));printf("进程名:");scanf("%s",p->name);printf("到达时间:");scanf("%d",&p->arrivetime);printf("需要时间:");scanf("%d",&p->servicetime);p->starttime=0;p->finishtime=0;p->state='W';if(ready!=NULL)insert2(p);//将新进程插入就绪队列else{p->next=ready;//创建就绪队列的第一个ready=p;}}system("cls");printf(" 先来先服务算法结果输出\n");printf("---------------------------------------------------------------------------\n");prt(alg);}void priority(char alg){while(run!=NULL) //当运行队列不空时，有进程正在运行{run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-1; //每运行一次优先数-1if(run->prio<0) //如果优先数减到小于0，则转换成0run->prio=0;if(run->needtime==0) //如果所需时间为0，即完成，将其插入完成队列{run->next=finish;finish=run;run->state='F'; //置状态为完成态run=NULL; //运行队列头指针为空if(ready!=NULL) //如果就绪队列不空firstin(); //将就绪对列的第一个进程投入运行}else //没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列if((ready!=NULL)&&(run->prio<ready->prio)){run->state='W'; //状态改为就绪insert1(run); //将进程按优先数大小插入firstin(); //将就绪队列的第一个进程投入运行}prt(alg); //输出进程PCB信息}}void FCFS(char alg){ int time=0;//系统时间从0开始do{run=ready;//就绪序列的第一个进程放入run队列进行执行run->state='R';//进程开始执行ready=ready->next;//指向下一个time=run->arrivetime>time? run->arrivetime:time;run->starttime=time;//进程开始prt(alg);//显示正在执行的进程time=time+run->servicetime;//计算下个进程最小可开始时间run->finishtime=time;//进程结束时间run->state='F';//结束状态标识prt(alg);//进程结束再显示run->next=finish;finish=run;//进程结束放入结束队列run=NULL;}while(ready!=NULL);}/*菜单显示函数*/void Menu(){system("cls");printf("\t\t+━━━━━━━━━━━━━━━━━━━━━━+\n");printf("\t\t| 进程调度算法| \n");printf("\t\t|━━━━━━━━━━━━━━━━━━━━━━| \n");printf("\t\t| | \n");printf("\t\t| [1]优先数算法| \n");printf("\t\t| | \n");printf("\t\t| [2]先来先服务算法| \n");printf("\t\t| | \n");printf("\t\t| [3]退出系统| \n");printf("\t\t| | \n");printf("\t\t|━━━━━━━━━━━━━━━━━━━━━━| \n");printf("\t\t| By:周敏健| \n");printf("\t\t+━━━━━━━━━━━━━━━━━━━━━━+\n");printf("\t\t请输入编号:");}int main(){char algo; //接收算法编号char mainmenu;//判断是否继续srand((unsigned)time(NULL));system("cls");//清屏do{Menu();//显示菜单scanf("%d",&algo); //输入算法编号switch(algo){case 1:system("cls");printf("您选择的是优先数算法\n");printf("请输入进程数目:");scanf("%d",&N); //输入进程数create1(algo); //创建队列priority(algo);//优先数break;case 2:system("cls");printf("您选择的是先来先服务算法\n");printf("请输入进程数目:");scanf("%d",&N); //输入进程个数create2(algo);//创建队列FCFS(algo);//先来先服务break;case 3:printf("\t\t再见! \n");exit(0);break;default:printf("输入有误\n");break;}printf("\n是否继续操作(Y/N) ");fflush(stdin);mainmenu=getchar();}while(mainmenu=='y'||mainmenu=='Y');return 0;}。
