进程调度程序设计报告.doc

一、课程设计的目的和要求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）重复以上过程，直到所有进程都完成为止。二、课程设计环境要求1、硬件环境联想系列电脑Intel（R） Pentium（R）DualCPU主频2GHz 内存1G2、软件环境Microsoft Windows Xp Professional版本2002装有Turbo C2.0软件三、设计任务介绍及系统需求分析1、设计任务的介绍根据设计任务书的要求，画出程序设计流程图，确定程序的功能，把整个程序根据功能要求分解为各个子程序，利用TC语言编写程序代码，然后进行上机调试、修改、进行连接、测试，写出设计总结报告。2、系统需求分析在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度（又称高级调度或长程调度）和进程调度（又称低级调度或短程调度）两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程调度即可获得处理机。在较完善的操作系统中，为提高内存的利用率，往往还设置了中级调度（又称中程调度）。对于上述的每一级调度，又都可采用不同的调度方式和调度算法。在本程序设计中要掌握的是进程调度的其中两种调度算法的应用。一个是最高优先数优先的调度算法（即把处理机分配给优先数最高的进程），另一个是先来先服务算法。最高优先数优先调度算法（即把处理机分配给优先数最高的进程）的基本思想是把CPU分配给就绪队列中优先数最高的进程。采用动态优先数，即优先数在创建进程时给定一个初始值，当进程获得一次CPU后其优先数就减少1，然后把它插入就绪队列等待CPU。先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。四、概要设计1、最高优先数优先调度算法（即把处理机分配给优先数最高的进程）实验步骤:（1）初始化进程信息。（2）将各个进程按优先数从高到低排列成就绪队列。（3）检查所有队列是否为空，若空则结束，否则将队首进程调入执行。（4）检查该运行进程是否运行完毕，若运行完毕，将此进程状态改为完成，插入另一个完成进程队列；否则，将该进程的优先数减1，然后重新对它进行排序，插入就绪队列适当位置后等待CPU。（5）重复步骤（3）、（4），直到就绪队列为空。2、先来先服务调度算法实验步骤:（1）初始化进程信息。（2）按先来先服务算法将进程排成就绪队列。（3）检查所有队列是否为空，若空则结束，否则将队首进程调入执行。（4）检查该运行进程是否运行完毕，若运行完毕，将此进程状态改为完成；否则，继续运行直到此进程运行完为止，才运行就绪队列的下一个进程。（5）重复步骤（3）、（4），直到就绪队列为空。3、程序功能模块图：（两种算法程序共用）main()函数input()函数running()函数geti()函数sort()函数check()函数disp()函数 五、详细设计1、功能模块设计（1）主要函数（最高优先数优先调度算法和先来先服务的核心函数相同）： a.主函数b.初始化进程函数c.使用户输入仅为正整数的函数d.排序函数e.就绪函数f.查看函数g.显示函数（2）程序流程图 a最高优先数优先调度算法： b先来先服务调度算法：未到达已到达运行进程已占用CPU时间达到所需的运行时间？进程完成，释放此进程开始初始化PCB，输入进程信息各进程按到达时间从先到后排序就绪队列为空？结束就绪队列首进程投入运行运行进程已占用CPU时间+1 2、数据结构设计（1）最高优先数优先调度算法：typedef struct pcb /*定义结构体数组，内部包含进程的信息*/ char name10; /*定义进程名*/ int super; /*定义到达时间*/ int needtime; /*定义进程需要运行的时间*/ int runtime; /*定义进程已用CPU时间*/ char state; /*定义进程的运行状态*/ struct pcb* link; /*进程块的后继指针，用于连接进程队列*/ PCB; （2）先来先服务调度算法： typedef struct pcb /*定义结构体数组，内部包含进程的信息*/ char name10; /*定义进程名*/ int arrivetime; /*定义到达时间*/ int needtime; /*定义进程需要运行的时间*/ int runtime; /*定义进程已用CPU时间*/ char state; /*定义进程的运行状态*/ struct pcb* link; /*进程块的后继指针，用于连接进程队列*/PCB; 3、函数功能描述（1）最高优先数优先调度算法： amain()主函数：掌控整个程序的运行过程，是程序的主体部分。 binput()初始化进程函数： 初始化各个进程的基本信息：如进程个数、进程名、进程需运行的时间、进程的优先数、进程的已运行时间、进程的状态。 cgeti()使用户输入仅为正整数的函数： 使用户输入的进程个数、进程需运行的时间、进程的优先数都为正整数。 dsort()排序函数：按优先数由高到低排列成就绪队列，进而等待运行。 erunning()就绪函数：进程运行时间到，则置就绪状态。若已运行时间已达到需运行时间，则此进程已完成，插入另一个完成队列中；若未达到，则优先数减1，重新插入就绪队列中排序等待运行。 fcheck()查看函数：查看哪个进程正在执行，哪些进程在就绪队列中，哪些进程已经完成。 gdisp()显示函数：显示各个进程的信息。（2）先来先服务调度算法： amain()主函数：掌控整个程序的运行过程，是程序的主体部分。 binput()初始化进程函数： 初始化各个进程的基本信息：如进程个数、进程名、进程需运行的时间、进程的到达时间、进程的已运行时间、进程的状态。 cgeti()使用户输入仅为正整数的函数： 使用户输入的进程个数、进程需运行的时间、进程的到达时间都为正整数。 dsort()排序函数：按到达时间从先到后排列成就绪队列，进而等待运行。 erunning()就绪函数：进程运行时间到，则置就绪状态。若已运行时间已达到需运行时间，则此进程已完成；若未达到，则继续运行直到时间达到为止。 fcheck()查看函数：查看哪个进程正在执行，哪些进程在就绪队列中，哪些进程已经完成。 gdisp()显示函数：显示各个进程的信息。六、调试过程1、最高优先数优先调度算法（1）先输入各个进程的信息 （2）进程运行的具体情况（部分调试结果） 2、先来先服务调度算法（1）先输入各个进程的信息 （2）进程运行的具体情况（部分调试结果） 3、当输入进程信息时，应输入正整数的信息输成字符或是其他不规范的数，则显示为：（两种算法程序都适用）七、结论与体会本次实验，成功实现了两种算法的主体功能。最高优先数优先调度算法（即把处理机分配给优先数最高的进程）的基本思想是把CPU分配给就绪队列中优先数最高的进程。采用动态优先数，即优先数在创建进程时给定一个初始值，当进程获得一次CPU后其优先数就减少1，然后把它插入就绪队列等待CPU。先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。其实，这两种算法有一些不同之处。最高优先数优先算法较先来先服务算法多了进程优先数这个进程信息，此算法就是围绕进程优先数进行排序从而运行进程。当进程获得一次CPU后其优先数就减少1，然后把它插入就绪队列重新排序等待CPU；而先来先服务算法较前者则是多了进程到达时间这个进程信息，此算法则是围绕先进先服务的原则来排序从而运行进程，直到此进程运行完成，才继续运行就绪队列的下一个进程。这两种算法也有很多共同之处，在初始化进程信息时，要注意有些进程信息必须输入正整数，所以为了实现这个功能，这两种调度算法中都调用了一个函数geti(),使得输入的数仅能为正整数，否则（当无输入或有输入但输入为字符、小数、负数等不符规则的数）必须重新输入才可继续运行程序。为了方便查看各个进程在每个时间片后的状态与信息，在这两种调度算法中，不仅将正在运行的进程信息和就绪队列的各个进程信息显示出来，还将已经完成的进程排成一个完成队列。最后将所有进程的信息进行查看与显示，方便用户及时了解各个进程的状态。八、参考文献1计算机操作系统第三版汤小丹、梁红兵、哲凤屏、汤子瀛编著，西安电子科技大学出版社2数据结构严蔚敏，吴伟明。北京：清华大学出版社，20063C语言程序设计田祥宏主编 西安电子科技大学出版社4/view/eee911eb81c758f5f61f6738.html?from=rec&pos=2&weight=9&lastweight=8&count=55/view/f5c83fd3240c844769eaeea8.html?from=rec&pos=3&weight=8&lastweight=8&count=5附件：源程序清单最高优先数优先调度算法源程序清单：#include#include /*malloc函数的头文件*/ #include /*getchar函数的头文件*/ typedef struct pcb /*定义结构体数组，内部包含进程的信息*/char name10; /*定义进程名*/ int super; /*定义到达时间*/int needtime; /*定义进程需要运行的时间*/ int runtime; /*定义进程已用CPU时间*/char state; /*定义进程的运行状态*/ struct pcb* link; /*进程块的后继指针，用于连接进程队列*/ PCB; PCB *ready = NULL, *p;/*ready总是指向进程队列中的第一个进程,p指向当前正在使用的进程*/ PCB * pfhead = NULL; /*定义两个指针指向完成队列的首部和尾部*/PCB * pfend = NULL;int geti() /*使用户仅能输入整数*/ char ch;int i = 0;fflush(stdin);ch = getchar();while(ch = n) /*当用户输入为空，则重新输入*/printf(tf输入不能为空.请重新输入n);fflush(stdin);ch = getchar();while(ch != n) /*注意：字符型是一位一位的输入的*/ if(ch 9 | ch super) (ready-super) /*如果就绪队列为空或新进程优先数较高*/ p-link = ready; /*优先数较小的放在ready后*/ready = p; /*ready指向就绪队列的第一个进程，即优先数最高的进程*/ else /*若优先数较小，则将其优先数与后面的进程一一比较，直到插入适当位置为止*/ first = ready;second = first-link;while (second != NULL)if (p-super second-super)p-link = second;first-link = p;insert = 1;break;elsefirst = first-link;second = second-link;if (insert = 0) /*标志着此进程的优先数最小，排在就绪队列的最后*/first-link = p;p-link = NULL;return ready;void input() /*初始化结构体数组*/ int i,j;printf(n请输入进程个数：);j=geti(); /*使输入个数为正整数*/ for(i=1;iname);printf(n输入进程需运行的时间:);p-needtime=geti();printf(n输入进程优先数:);p-super=geti();p-runtime=0;p-state=w; p-link=NULL; /*初始进程的已运行时间为0，状态为等待，后继指针为空*/ sort(p); /*输入所有的进程后，调用排序函数进行排序*/ void disp(PCB* p) /*建立进程显示函数*/ printf(name state super needtime runtimen); printf(%st,p-name); printf(%ct,p-state); printf(%dtt,p-super); printf(%dt,p-needtime); printf(%dtn,p-runtime); void check(PCB * p) /*建立进程查看函数*/PCB * pr;static int i = 1;char ch;printf(nthe execute number:%dn, i+); /*相当于对时间片的计时*/ch=getch(); /*键入一个键后再继续执行*/printf(n*当前正在运行的进程为：%sn, p-name);/*显示当前运行进程*/ disp(p);pr = p-link; /*pr指向就绪队列*/if (pr = NULL) /*若就绪队列为空，则输出*/printf(n*当前进程就绪队列为空！n);else /*若就绪队列不为空，则输出就绪队列*/ printf(n*当前进程就绪队列为：n); while (pr != NULL) /*显示就绪队列各个进程的信息*/ disp(pr);pr = pr-link;printf(n*当前所有进程的信息列表：n);/*显示全部进程的信息*/ pr = ready;while (pr != NULL) /*显示的是就绪队列的个进程信息*/disp(pr);pr = pr-link; while (pfhead != NULL) /*显示的是已完成进程的信息*/ disp(pfhead);pfhead = pfhead-link;printf(.);void running(PCB * p) /*建立进程就绪函数，进程运行时间到，就置就绪状态*/while (p != NULL) /*仍有未运行完的进程*/ p-state = R; /*状态仍然为运行状态*/check(p); /*查看并显示进程*/(p-runtime)+; /*进程的已运行时间加1*/ if (p-runtime = p-needtime) /*若运行时间已达需要的运行时间，则状态为完成，输出此进程已完成*/p-state = F;printf(n进程 %s 已完成！n, p-name);ready = p-link;p-link = NULL; /*使P指针指向的已完成的进程独立出来*/ if (pfhead = NULL) /*使已完成的进程排成一个完成队列*/pfhead = p;pfend = p; pfend-link = NULL;elsepfend-link = p;pfend = p;pfend-link = NULL; p =ready; /*P指针重新指向就绪队列的第一个进程*/ else /*当进程的已运行时间还未达到需要运行的时间*/(p-super)-; /*此进程优先数减1，重新排序等待执行*/p-state = W;ready= p-link; /*将此进程独立出来，重新排序*/p-link = NULL;p = sort(p);main() printf(*欢迎来到最高优先数优先调度算法界面*n); input(); p = ready; /*当前的运行进程指针P指向就绪队列的首进程指针ready*/ running(p); printf(nn所有进程都已完成.n); getchar(); /*利用getchar()函数让程序调试运行结束后等待编辑者按键才返回编辑界面*/先来先服务调度算法源程序清单：#include#include /*malloc函数的头文件*/#include /*getchar函数的头文件*/typedef struct pcb /*定义结构体数组，内部包含进程的信息*/char name10; /*定义进程名*/ int arrivetime; /*定义到达时间*/ int needtime; /*定义进程需要运行的时间*/ int runtime; /*定义进程已用CPU时间*/ char state; /*定义进程的运行状态*/ struct pcb* link; /*进程块的后继指针，用于连接进程队列*/PCB; PCB *ready = NULL, *p; /*ready总是指向进程队列中的第一个进程,p指向当前正在使用的进程*/int geti() /*使用户仅能输入整数*/char ch;int i = 0;fflush(stdin);ch = getchar();while(ch = n) /*当用户输入为空，则重新输入*/printf(tf输入不能为空.请重新输入n);fflush(stdin);ch = getchar();while(ch != n) /*注意：字符型是一位一位的输入的*/ if(ch 9 | ch arrivetime) arrivetime) /*如果就绪队列为空或新进程到达时间较早*/ p-link = ready; /*到达时间较晚的放在ready后*/ready = p; /*ready指向就绪队列的第一个进程，即到达时间最早的进程*/ else /*若到达时间较晚，则将其到达时间与后面的进程一一比较，直到插入适当位置为止*/ first = ready;second = first-link;while (second != NULL)if (p-arrivetime arrivetime)p-link = second;first-link = p;insert = 1;break;elsefirst = first-link;second = second-link;if (insert = 0) /*标志着此进程的到达时间最晚，排在就绪队列的最后*/first-link = p;p-link = NULL;void input() /*初始化结构体数组*/ int i,j;printf(n请输入进程个数：);j=geti(); /*使输入个数为正整数*/ for(i=1;iname);printf(n输入进程需运行时间:);p-needtime=geti(); printf(n输入进程到达时间:); p-arrivetime=geti(); p-runtime=0; p-state=w; p-link=NULL;/*初始进程的已运行时间为0，状态为等待，后继指针为空*/ sort(); /*输入所有的进程后，调用排序函数进行排序*/ void disp(PCB* p) /*建立进程显示函数*/ printf(name arrivetime needtime runtime staten); printf(%st,p-name); printf(%dtt,p-arrivetime); printf(%dt,p-needtime); printf(%dt,p-runtime); printf(%ctn,p-state