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

吉首大学数学与计算机科学学院计算机操作系统课程设计报告课题名称:进程调度 开发人员：肖海波学号: 20054044029 班级：2005级计算机科学与技术2班 实现算法:最高优先数度算法完成日期:2007年12月21日 指导老师： 李必云计算机操作系统进程调度模拟算法第一章 绪论1第二章 算法简介 11 最高优先数算法第三章 程序开发平台及开发工具第四章 算法数据结构及流程图41 算法数据结构42 算法流程图第五章 程序源代码第六章 测试数据及测试结果61 最高优先数611 测试数据612 测试结果62 测试总结第七章 算法分析结束语参考文献第一章 绪 论进程调度是操作系统中最基本的一种调度,在各种类型的操作系统中都必须设有进程调度.进程调度的基本方式可分为非抢占方式和抢占式方式(也称为剥夺方式)(1) 非抢占方式在这种进程调度方式下,一旦一个进程被选中投入运行,它就一直运行下去,直至完成工作,自愿放弃CPU,或者因某个事件而被阻塞为止,才把CPU让出给其他进程,即得到CPU的进程不会因为时钟中断等原因而被迫让出CPU.(2) 抢占方式与非抢占方式相反,抢占方式允许进程调度程序根据某种策略终止当前正在运行的进程,将其移入就绪队列,并再根据某种调度算法选择另一个进程投入运行.第二章 算法简介21 最高侁先数算法 最简单的调度算法就是先来先服务,也可以称为先进先出(First In First Out)或严格排队方式.对于进程调度算法来说,先来先服务调度算法就是从就绪队列中选择一个最先进入队列的进程,将CPU分配于它,让其运行.该进程一直运行下去直到完成或由于某事件而被阻塞入放弃CPU.这样,当一个进程进入就绪队列时,它的PCB就链入了该就绪队列的末尾,排队等待分配CPU.一般来说,先来先服务调度算法对于长任务来说比较短任务要好一些. FCFS算法不考虑作业运行时间的长短，仅按作业进入输入井时间的先后进行调度，因此对所有的作业是公平合理的。第三章 程序开发平台及开发工具Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，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由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Visual C+它大概可以分成三个主要的部分：1 Developer Studio，这是一个集成开发环境，我们日常工作的99%都是在它上面完成的，再加上它的标题赫然写着“Microsoft Visual C+”，所以很多人理所当然的认为，那就是Visual C+了。其实不然，虽然Developer Studio提供了一个很好的编辑器和很多Wizard，但实际上它没有任何编译和链接程序的功能，真正完成这些工作的幕后英雄后面会介绍。我们也知道，Developer Studio并不是专门用于VC的，它也同样用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio当成Visual C+， 它充其量只是Visual C+的一个壳子而已。这一点请切记！2 MFC。从理论上来讲，MFC也不是专用于Visual C+，Borland C+，C+Builder和Symantec C+同样可以处理MFC。同时，用Visual C+编写代码也并不意味着一定要用MFC，只要愿意，用Visual C+来编写SDK程序，或者使用STL，ATL，一样没有限制。不过，Visual C+本来就是为MFC打造的，Visual C+中的许多特征和语言扩展也是为MFC而设计的，所以用Visual C+而不用MFC就等于抛弃了Visual C+中很大的一部分功能。但是，Visual C+也不等于MFC。3 Platform SDK。这才是Visual C+和整个Visual Studio的精华和灵魂，虽然我们很少能直接接触到它。大致说来，Platform SDK是以Microsoft C/C+编译器为核心（不是Visual C+，看清楚了），配合MASM，辅以其他一些工具和文档资料。上面说到Developer Studio没有编译程序的功能，那么这项工作是由谁来完成的呢？是CL，是NMAKE，和其他许许多多命令行程序，这些我们看不到的程序才是构成Visual Studio的基石。第四章 算法数据结构及流程图41 算法数据结构每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、进程时间轮转时间片、计数器、需要运行时间、已用CPU时间、进程状态。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。4.2算法流程图 最高优先数调度算法流程图开始初始化PCB，输入进程数度息各进程按优先数从高到低排列时间片到，运行进程已占用CPU时间+1就绪队列第一个进程投入运行使运行进程的优先数减1，把运行进程插入就绪队列就绪队列空？运行进程已占用CPU时间已达到所需的运行时间结束进程完成，撤消该进程已达到未达到N第五章 程序源代码代码如下:#include stdio.h #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0 struct 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)|(p-super)(ready-super) /*优先级最大者,插入队首*/ p-link=ready; ready=p; else /* 进程比较优先级,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-super)(second-super) /*若插入进程比当前进程优先数大,*/ /*插入到当前进程前面*/ 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; 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) /*建立进程显示函数,用于显示当前进程*/ printf(n qname t state t super t ndtime t runtime n); printf(|%st,pr-name); printf(|%ct,pr-state); printf(|%dt,pr-super); printf(|%dt,pr-ntime); printf(|%dt,pr-rtime); printf(n); check() /* 建立进程查看函数 */ PCB* pr; printf(n * now pcb running:%s,p-name); /*显示当前运行进程*/ disp(p); pr=ready; printf(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函数*/ 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(); 第六章 测试数据及测试结果最高优先数进程调度算法模拟测试最高优先数进程调度算法模拟测试的输入数据的及其结果如下:进程名优先级运行时间a12b21c11d33e44please input n pcb?5 pcb num No.1: pcb name:a pcb super:1 pcb run time:2 pcb num No.2: pcb name:b pcb super:2 pcb run time:1 pcb num No.3: pcb name:c pcb super:1 pcb run time:1 pcb num No.4: pcb name:d pcb super:3 pcb run time:3 pcb num No.5: pcb name:e pcb super:4 pcb run time:4 The execute number:1 * now pcb running:e qname state super ndtime runtime|e |R |4 |4 |0 *now pcb waiting: qname state super ndtime runtime|d |w |3 |3 |0 qname state super ndtime runtime|b |w |2 |1 |0 qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 any key continue. The execute number:2 * now pcb running:d qname state super ndtime runtime|d |R |3 |3 |0 *now pcb waiting: qname state super ndtime runtime|e |w |3 |4 |1 qname state super ndtime runtime|b |w |2 |1 |0 qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 any key continue. The execute number:3 * now pcb running:e qname state super ndtime runtime|e |R |3 |4 |1 *now pcb waiting: qname state super ndtime runtime|b |w |2 |1 |0 qname state super ndtime runtime|d |w |2 |3 |1 qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 any key continue. The execute number:4 * now pcb running:b qname state super ndtime runtime|b |R |2 |1 |0 *now pcb waiting: qname state super ndtime runtime|d |w |2 |3 |1 qname state super ndtime runtime|e |w |2 |4 |2 qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 pcb b successed. any key continue. The execute number:5 * now pcb running:d qname state super ndtime runtime|d |R |2 |3 |1 *now pcb waiting: qname state super ndtime runtime|e |w |2 |4 |2 qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 any key continue. The execute number:6 * now pcb running:e qname state super ndtime runtime|e |R |2 |4 |2 *now pcb waiting: qname state super ndtime runtime|a |w |1 |2 |0 qname state super ndtime runtime|c |w |1 |1 |0 qname state super ndtime runtime|d |w |1 |3 |2 any key continue. The execute number:7 * now pcb running:a qname state super ndtime runtime|a |R |1 |2 |0 *now pcb waiting: qname state super ndtime runtime|c |w |1 |1 |0 qname state super ndtime runtime|d |w |1 |3 |2 qname state super ndtime runtime|e |w |1 |4 |3 any key continue. The execute number:8 * now pcb running:c qname state super ndtime runtime|c |R |1 |1 |0 *now pcb waiting: qname state super ndtime runtime|d |w |1 |3 |2 qname state super ndtime runtime|e |w |1 |4 |3 qname state super ndtime runtime|a |w |0 |2 |1 pcb c successed. any key continue. The execute number:9 * now pcb running:d qname state super ndtime runtime|d |R |1 |3 |2 *now pcb waiting: qname state super ndtime runtime|e |w |1 |4 |3 qname state super ndtime runtime|a |w |0 |2 |1 pcb d successed. any key continue. The execute number:10 * now pcb running:e qname state super ndtime runtime|e |R |1 |4 |3 *now pcb waiting: qname state super ndtime runtime|a |w |0 |2 |1 pcb e successed. any key continue. The execute number:11 * now pcb running:a qname state super ndtime runtime|a