进程调度 最高优先数度算法

1、吉首大学数学与计算机科学学院计算机操作系统课程设计报告课题名称:进程调度开发人员：肖海波学号：20054044029班级：2005级计算机科学与技术2班实现算法:最高优先数度算法完成日期：2007年12月21日 指导老师：李必云计算机操作系统进程调度模拟算法第一章绪论1第二章算法简介1最高优先数算法第三章程序开发平台及开发工具第四章 算法数据结构及流程图4. 1算法数据结构4. 2算法流程图第五章程序源代码第六章测试数据及测试结果6. 1最高优先数6. 1. 1测试数据6. 1. 2测试结果6. 2测试总结第七章算法分析结束语参考文献第一章绪论进程调度是操作系统中最基本的一种调度，在各种类型的

2、操作系统中 都必须设有进程调度.进程调度的基本方式可分为非抢占方式和抢占式方 式(也称为剥夺方式)非抢占方式在这种进程调度方式下，一旦一个进程被选中投入运行，它就一直运行下去, 直至完成工作,自愿放弃CPU,或者因某个事件而被阻塞为止才把CPU让 出给其他进程，即得到CPU的进程不会因为时钟中断等原因而被迫让出 CPU.抢占方式与非抢占方式相反，抢占方式允许进程调度程序根据某种策略终止当前正 在运行的进程，将其移入就绪队列，并再根据某种调度算法选择另一个进程 投入运行.第二章算法简介1最高侁先数算法最简单的调度算法就是先来先服务，也可以称为先进先出(First In First Out)或严格

3、排队方式.对于进程调度算法来说，先来先服务调度算法就 是从就绪队列中选择一个最先进入队列的进程，将CPU分配于它，让其运行. 该进程一直运行下去直到完成或由于某事件而被阻塞入放弃CPU.这样，当 一个进程进入就绪队列时，它的PCB就链入了该就绪队列的末尾，排队等待 分配CPU.一般来说，先来先服务调度算法对于长任务来说比较短任务要好 一些.FCFS算法不考虑作业运行时间的长短，仅按作业进入输入井时间的 先后进行调度，因此对所有的作业是公平合理的。第三章 程序开发平台及开发工具Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出 Visual C+1.0后

4、，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件 开发的首选工具。虽然微软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性， 只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以 Visual C+6.0 为平台。Visual C+6.0不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集 成开发环境(integrated development environment,IDE)。Visual C+6.0 由许多组件组 成，包括编辑器、调试器以及程序向导AppW

5、izard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Visual C+它大概可以分成三个主要的部分：Developer Studio,这是一个集成开发环境，我们日常工作的99%都是在它上面完 成的，再加上它的标题赫然写着“Microsoft Visual如+所以很多人理所当然的认为， 那就是Visual C+了。其实不然，虽然Developer Studio提供了一个很好的编辑器和很 多Wizard，但实际上它没有任何编译和链接程序的功能，真正完成这些工作的幕后英 雄后面会介绍。我们也知道，Developer

6、Studio并不是专门用于VC的，它也同样用于 VB, VJ, VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio当 成Visual C+,它充其量只是Visual C+的一个壳子而已。这一点请切记！ MFC。从理论上来讲，MFC 也不是专用于 Visual C+, Borland C+, C+Builder 和Symantec C+同样可以处理MFC。同时，用Visual C+编写代码也并不意味着一 定要用MFC,只要愿意，用Visual C+来编写SDK程序，或者使用STL, ATL, 一样 没有限制。不过，Visual C+本来就是为MFC打

7、造的，Visual C+中的许多特征和语 言扩展也是为MFC而设计的，所以用Visual C+W不用MFC就等于抛弃了 Visual C+ 中很大的一部分功能。但是，Visual C+也不等于MFC。Platform SDK。这才是Visual C+和整个Visual Studio的精华和灵魂，虽然我们 很少能直接接触到它。大致说来，Platform SDK是以Microsoft C/C+编译器为核心(不 是Visual C+，看清楚了)，配合MASM,辅以其他一些工具和文档资料。上面说到 Developer Studio没有编译程序的功能，那么这项工作是由谁来完成的呢？是CL,是 NMAKE

8、,和其他许许多多命令行程序，这些我们看不到的程序才是构成Visual Studio 的基石。第四章 算法数据结构及流程图4. 1算法数据结构每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如 下信息：进程名、优先数、进程时间轮转时间片、计数器、需要运行 时间、已用CPU时间、进程状态。每个进程的状态可以是就绪 W(Wait)、运行R (Run)、或完成F (Finish)三种状态之一。4.2算法流程图最高优先数调度算法流程图第五章程序源代码代码如下：#include stdio.h#include #include #define getpch(type) (type*)malloc

9、(sizeof(type)#define NULL 0struct pcb /*定义进程控制块PCB */char name10;char state;int super;int ntime;int rtime;struct pcb* link;*ready=NULL,*p;typedef struct pcb PCB;sort() /*建立对进程进行优先级排列函数*/PCB *first, *second;int insert=0;if(ready=NULL)ll(p-super)(ready-super) /*优先级最大者，插入队首*/(p-link=ready;ready=p;else

10、/*进程比较优先级，插入适当的位置中*/(first=ready;second=first-link;while(second!=NULL)(if(p-s uper)(second-s uper) /*若插入进程比当前进程优先数大,*/( /*插入到当前进程前面*/p-link=second;first-link=p;second=NULL;insert=1;else /*插入进程优先数最低，则插入到队尾*/(first=first-link;second=second-link;if(insert=0) first-link=p;input() /*建立进程控制块函数*/(int i,num

11、;printf(n please input n pcb?);scanf(%d,&num);for(i=0;iname);printf(n pcb super:);scanf(%d”,&p-super);printf(n pcb run time:);scanf(%d”,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort(); /* 调用 sort 函数 */int space()(int l=0; PCB* pr=ready;while(pr!=NULL)(l+;pr=pr-link;return(l);disp(PCB * pr

12、) /*建立进程显示函数，用于显示当前进程*/(printf(n qname t state t super t ndtime t runtime n);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-s uper);printf(|%dt,pr-ntime);printf(l%dt,pr-rtime);printf(n);check() /*建立进程查看函数*/(PCB* pr;printf(n * now pcb running:%s,p-name); /* 显示当前运行进程*/ disp(p);pr=ready;prin

13、tf(n *now pcb waiting:n); /* 显示就绪队列状态 */while(pr!=NULL)(disp(pr);pr=pr-link;destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/(printf(n pcb %s successed.n,p-name);free(p);running() /*建立进程就绪函数(进程运行时间到，置就绪状态*/(p-rtime)+;if(p-rtime=p-ntime)destroy(); /* 调用 destroy 函数 */else(p-super)-;p-state=w;sort(); /* 调用 sort 函数 *

14、/main() /* 主函数*/(int len,h=0;char ch;input();len=space();while(len!=0)&(ready!=NULL)(ch=getchar();h+;printf(n The execute number:%d n,h);p=ready;ready=p-link;p-link=NULL;p-state=R;check();running();printf(n any key continue);ch=getchar();printf(nn pcb have succed.n);ch=getchar();第六章测试数据及测试结果最高优先数进程调

15、度算法模拟测试最高优先数进程调度算法模拟测试的输入数据的及其结果如下：进程名优先级运行时间a12b21c11d33e44please input n pcb?5pcb num No.1:pcb name:apcb super:1pcb run time:2pcb num No.2:pcb name:bpcb super:2pcb run time:1pcb num No.3:pcb name:cpcb super:1pcb num No.4:pcb name:dpcb super:3pcb run time:3pcb num No.5:pcb name:epcb super:4pcb run

16、time:4The execute number:1* now pcb running:eqnamestatesuperndtimeruntime|e|R|4|4|0*now pcb waiting:qnamestatesuperndtimeruntime|d|w|3|3|0qnamestatesuperndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0* now pcb running:dqnamestatesuperndtimeruntime|

17、d|R|3|3|0*now pcb waiting:qnamestatesuperndtimeruntime|e|w|3|4|1qnamestatesuperndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0any key continueThe execute number:3* now pcb running:eqnamestatesuperndtimeruntime|e|R|3|4|1*now pcb waiting:qnamestatesu

18、perndtimeruntime|b|w|2|1|0qnamestatesuperndtimeruntime|d|w|2|3|1qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0The execute number:4* now pcb running:bqnamestatesuperndtimeruntime|b|R|2|1|0*now pcb waiting:qnamestatesuperndtimeruntime|d|w|2|3|1qnamestatesuperndtimeruntime

19、|e|w|2|4|2qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0pcb b successed.any key continue.The execute number:5* now pcb running:dqnamestatesuperndtimeruntime|d|R|2|3|1*now pcb waiting:qnamestatesuperndtimeruntime|e|w|2|4|2qnamestatesuperndtimeruntime|a|w|1|2|0qnamestates

20、uperndtimeruntime|c|w|1|1|0The execute number:6* now pcb running:eqnamestatesuperndtimeruntime|e|R|2|4|2*now pcb waiting:qnamestatesuperndtimeruntime|a|w|1|2|0qnamestatesuperndtimeruntime|c|w|1|1|0qnamestatesuperndtimeruntime|d|w|1|3|2any key continueThe execute number:7* now pcb running:aqnamestate

21、superndtimeruntime|a|R|1|2|0*now pcb waiting:qnamestatesuperndtimeruntime|c|w|1|1|0qnamestatesuperndtimeruntime|d|w|1|3|2qnamestatesuperndtimeruntime|e|w|1|4|3any key continue* now pcb running:cqname state super|c|R|1ndtime|1|0runtime*now pcb waiting:qname state super|d|w|1ndtime|3|2runtimeqname sta

22、te super|e|w|1ndtime|4|3runtimeqname state super|a|w|0ndtime|2|1runtimepcb c successed.any key continueThe execute number:9* now pcb running:d qname state super|d|R|1ndtime|3|2runtime*now pcb waiting:qname state super|e|w|1ndtime|4|3runtimeqname state super|a|w|0ndtime|2|1runtimepcb d successed.any

23、key continue.The execute number:10* now pcb running:eqname state super|e |R |1ndtime|4runtime13*now pcb waiting:qname state super|a |w |0ndtime|2runtime11pcb e successed.any key continueThe execute number:11qname state super|e |R |1ndtime|4runtime13*now pcb waiting:qname state super|a |w |0ndtime|2runtime11pcb e successed.any key continueThe execute number:11* now pcb running:a qname state super|a |R |0ndtime|2runtime|1*now pcb waiting:pcb a successed.any key contin