2022年2022年进程调度最高优先数度算法 .pdf

吉首大学数学与计算机科学学院计算机操作系统课程设计报告课题名称 : 进程调度开发人员：肖海波学号 : 20054044029 班级： 2005 级计算机科学与技术2 班实现算法 : 最高优先数度算法完成日期 :2007 年 12 月 21 日指导老师：李必云名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 计算机操作系统进程调度模拟算法第一章绪论1第二章算法简介 11 最高优先数算法第三章程序开发平台及开发工具第四章算法数据结构及流程图 41 算法数据结构42 算法流程图第五章程序源代码 第六章测试数据及测试结果 61 最高优先数611 测试数据612 测试结果62 测试总结第七章算法分析 结束语 参考文献 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - 第一章绪论进程调度是操作系统中最基本的一种调度,在各种类型的操作系统中都必须设有进程调度.进程调度的基本方式可分为非抢占方式和抢占式方式(也称为剥夺方式 ) (1) 非抢占方式在这种进程调度方式下,一旦一个进程被选中投入运行,它就一直运行下去 ,直至完成工作 ,自愿放弃 CPU, 或者因某个事件而被阻塞为止,才把 CPU 让出给其他进程 ,即得到CPU 的进程不会因为时钟中断等原因而被迫让出CPU. (2) 抢占方式与非抢占方式相反,抢占方式允许进程调度程序根据某种策略终止当前正在运行的进程 ,将其移入就绪队列,并再根据某种调度算法选择另一个进程投入运行 .第二章算法简介21 最高侁先数算法最简单的调度算法就是先来先服务,也可以称为先进先出(First In First Out) 或严格排队方式 .对于进程调度算法来说,先来先服务调度算法就是从就绪队列中选择一个最先进入队列的进程,将 CPU 分配于它 ,让其运行 .该进程一直运行下去直到完成或由于某事件而被阻塞入放弃CPU. 这样,当一个进程进入就绪队列时,它的 PCB 就链入了该就绪队列的末尾,排队等待名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 分配 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的基石。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 第四章算法数据结构及流程图41 算法数据结构每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、进程时间轮转时间片、计数器、需要运行时间、已用CPU 时间、进程状态。每个进程的状态可以是就绪W（Wait） 、运行 R（Run） 、或完成 F（Finish）三种状态之一。4.2 算法流程图最高优先数调度算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - 开始初始化PCB，输入进程数各进程按优先数从高到低排列时间片到，运行进程已占用CPU 时间+1 就绪队列第一个进程投入运行使运行进程的优先数减1，把运行进程插入就绪队列就绪队列空？运 行 进 程 已 占 用CPU 时间已达到所需的运行时间结束进程完成，撤消该进程已达到未达到N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - 第五章 程序源代码代码如下 : #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) /* 优先级最大者 ,插入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 队首*/ 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 21 页 - - - - - - - - - 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() /* 建立进程就绪函数 (进程运行时间到 ,置就绪状态 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - (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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - 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(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - 第六章测试数据及测试结果最高优先数进程调度算法模拟测试最高优先数进程调度算法模拟测试的输入数据的及其结果如下: 进程名优先级运行时间a 1 2 b 2 1 c 1 1 d 3 3 e 4 4 please 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - 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. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 21 页 - - - - - - - - - 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - 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. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - 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 |R |0 |2 |1 *now pcb waiting: pcb a successed. any key continue. pcb have succed. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - 第七章算法分析通过以上数据测最高优先数算法的可以看出这种方法的优点是可使资源利用率得以提高 , 公平性好 . 缺点是系统开销大 , 实现比较复杂 . 结束语首先感谢李必云老师对我这次课程设计的细心指导和耐心讲授. 这次的操作系统课程设计，让我收获很大。以前虽然也做过几次课程设计但是都没有这次来得印象深刻。以前的许多课程设计要么觉得无所适从，像C 语言的课程设计，因为是进大学来的第一次课程设计，而且学的东西也太少，所以根本不知道怎么动手。到最后，课程设计是完了，把自己也弄的疲惫不堪，几乎对自己失去信心；要么，像数据结构的课程设计，太简单，三两天就做完了，觉得什么感觉都没有，毫无收获。这次的课程设计就不一样，一来，在此之前已经学了一些专业课程，二来，自己也通过平时的阅读，对计算机专业到底是干什么的，学计算机专业该怎么学，有了大概的了解。所以，可以说是在这个学期开学之前，我已经知道自己该做些什么，该怎么去做。有了这样的一个基础，加上这次的操作系统课程设计对自己又是一次很好的锻炼机会，所谓学以致用。所以，一拿到设计题目，我就对自己很有信心。首先到图书馆查阅资料，在有了理论基础之后，再上机实践。实践过程中，当然遇到很多问题，但是大都通过自己查阅资料，和向老师与同学请教而解决了。每当这个时候，自己就有一种成就感。并且，在查阅资料的同时，也发现了很多有用的书籍，有用的知识。有的我当场就做了适当的记录，有的比较多，一时没有时间看，就做个备忘，以后有时间的时候再去看，去学习参考文献1Operating System ，William Stallings, 电子工业版，第 5 版2操作系统设计与实现 ，Tennenbaum ，机械版3操作系统原理、技术与编成 ，蒋静，机械版4计算机操作系统教程 核心设计与原理，范策 , 许宪成 清华大学出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -