时间片轮转算法教材

1、课程设计说明书NO.1时间片轮转算法1. 课程设计的目的通过操作系统课程设计， 通过对作业调度算法的设计， 深入理解作业调度的 原理，从原理分析、物理设计，到功能分析和应用程序的最终实现，让我亲自动 手参与一个操作系统的模拟设计， 真正理解和掌握操作系统的有关内容， 加深对 操作系统， 软件工程，程序设计语言的理论知识的理解和应用水平； 在理论和实 验教学基础上进一步巩固已学基本理论及应用知识并加以综合提高； 学会将知识 应用于实际的方法， 提高分析和解决问题的能力， 增强对手能力； 并更好的理解 和消化课本所学的知识，为毕业设计和以后工作打下必要基础。2. 课程设计的开发语言在本次课程设计中

2、，我们选择了 C+语言作为我们所使用的开发语言，开发 工具则选用了 Microsoft Visual C+ 6.0 。MFC借助 C+的优势为 Windows开发 开辟了一片新天地，同时也借助 ApplicationWizzard 使开发者摆脱离了那些每 次都必写基本代码， 借助 ClassWizard 和消息映射使开发者摆脱了定义消息处理 时那种混乱和冗长的代码段。更重要的是利用C+的封装功能使开发者摆脱Windows中各种句柄的困扰，只需要面对 C+中的对象，这样一来使开发更接近 开发语言而远离系统。正因为 MFC是建立在 C+的基础上，所以我强调 C/C+语 言基础对开发的重要性。 利用

3、 C+的封装性开发者可以更容易理解和操作各种窗 口对象； 利用 C+的派生性开发者可以减少开发自定义窗口的时间和创造出可重 用的代码；利用虚拟性可以在必要时更好的控制窗口的活动。而且C+本身所具备的超越 C 语言的特性都可以使开发者编写出更易用，更灵活的代码。3. 功能描述 时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的 时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出 来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制块， 定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时间、 已运行时间和进程的状态以及指针的信息。 实

4、现的过程即运用指针指向某一个进 程，判断当前的进程是否是就绪状态“ r ”，如果是，则为该进程分配一个时间沈阳大学课程设计说明书NO.2片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个进 程的所需要运行的时间减少至 0 时，则将该进程的状态设置为“ e”。然后，将 指针指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。4. 方案论证4.1 概要设计4.1.1 各模块功能1) int InitQueue(LinkQueue &Q)： 输 入 进 程 时 ， 初 始 化 输 入 的 链 表 。2) int DestroyQueue(LinkQueue &Q) ：

5、运 行 完 后 ， 销 毁 链 表 。3) int EnQueue(LinkQueue &Q,QElemType e) ：将 进程插入循环队列中。4) int DeQueue(LinkQueue &Q,QElemType e) ：当进程完成后， 输出链表中元 素。5) int QueueEmpty(LinkQueue &Q)：判断链表是否为空。6) void chioce(struct PCB pcb,intn) ：对于输入链表中数的按关键字到达时间用选择法从小到大进行进行排序。7) void caidan() ：主菜单，包含：进程的创建和结果和结束。8) void create() ：进程的

6、创建。9) void main() ：实现函数调用的总控制。4.1.2 相关数据类型1) typedef int QElemType：自定义类型，定义 QElemTyp为e int 型。2) typedef struct QNode QElemType data;struct QNode *next;QNode,*QueuePtr;采 用 结 构 体 变 量 ， 存 队 列 的 相 关 信 息 ： QElemTyped ata 、 struct QNode *next 。同时定义结构体指针 *QueuePtr ，便于之后书写开辟空 间级表示。系统调用时，每次分配一个 QNode那么大的空间进行

7、存储。3) typedef struct PCB char name10; / 进程名 struct PCB *next; /循环链指针沈阳大学int need_time; /int worked_time; /char condition; /int flag; /课程设计说明书NO.3要求运行时间已运行时间，初始为 0进程状态，只有“就绪”和“结束”两种状态进程结束标志，用于输出PCB; PCB *front,*rear; /循环链队列的头指针和尾指针 int N; /N为进程数定义循环链表的头指针和尾指针。 QueuePtr front ， QueuePtr rear 。4) struc

8、t PCB int ArrivalTime;int ServiceTime;har number;mMaxNum;采用结构体数组，创建一个进程，包含进程相关信息：进程名称、进程到达 时间、进程服务时间。4.2.3 总体设计程序总体设计 :首先选择 1 创建进程，输入进程总数，进程的名称，各进程 到达的时间，各进程服 务的时间 ，以及时间片q 的值，运行出结果。选择 2 将结 束运行，如图 1 所示。图 1 系统总体设计沈阳大学课程设计说明书NO.44.2.4 主程序的流程图 主程序流程如图 2 所示YYNNY是否完成是否所有进程 都完成时间片是否用完NY输入时间片进程是否输入完NY是否有新进程

9、 到达分配给执行队列队首时间片时间片 -1 时间片 +1服务时间 -1将为完成的插入队尾将新到进程插入队尾输入进程数输入进程退出图2 主程序的流程图沈阳大学课程设计说明书NO.54.1.5 程序说明处理器调度总是选择指针指示的进程运行。 由于本实验是模拟处理器调度的 功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间 +1 来模拟进程的一次运行，表示进程已经运行过一个单位的时间。4.2 详细设计首先每一个进程用一个进程控制块 PCB 来代表。进程控制块的格式如表 3 所示。表 3 PCB 控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。 已运行时间假设进程已

10、经运行的单位时间数，初始值为“ 0”。 状态有两种状态， “就绪”和“结束”，初始状态都为 “就绪”，用“R” 表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。每次运行所设计的处理器调度程序前， 为每个进程任意确定它的 “要求运行 时间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示轮到运行的进程，如表 4 描述述所示表 4 进程队列沈阳大学课程设计说明书NO.6PCB1 PCB2 PCB3 PCB4 PCB54.3 程序详细设计步骤首先建立 PCB的数据结构，为了便于正确输出，加上了进程结束标志 flag 。 输入进程信息(包括进程名和要求运行的时间)，并

11、为每个进程创建一个 PCB 并初始化形成一个循环链队列，用函数 creatPCB() 来实现。建立函数 judge() 用来判断进程全部运行结束标志， 即当所有进程的状态变 为 e(即完成状态)后，循环结束，表示所有进程都已运行成功。建立时间片轮转算法 creatProcess ()对进程进行轮转运行，首先指针 s 指向第一个进程 PCB，即 s=front ，判断该进程的状态是否为 r (就绪状态) ， 即 if(s-condition = r) ，若是则表示此进程尚未执行结束，则执行 s-worked_time+ 且 s-need_time- ，if(s-need_time=0) ，则表示

12、此进程已 运行结束，将其状态置为结束，即 s-condition=e ，并根据状态位输出完成 信息，且以后不会再运行此进程。将指针指向下个进程， s=s-next ，并判断所 有进程是否已全部运行结束， 没有则重复上面算法。 当所有进程的状态位都变成 e表示所有进程运行完成，则循环结束。建立主函数 main(), 输入进程数 N，调用初始化循环链队列函数 creatPCB() 和时间片轮转算法 creatProcess(N) ，每次选中进程的进程名以及运行一次后进 程队列的变化，实现处理器的调度。5. 程序的运行及结果1 )主菜单：输入选项 1：进程创建及结果 2 ：结束，如图 5 所示。沈阳

13、大学课程设计说明书NO.7图 5 主菜单2）运行过程 :选择 1，创建进程。输入进程总数，进程的名称 a 、b，各进 程到达的时间，各进程服务的时间 ，以及时间片q的值。当输入 进程为2时，各 进 程 到达 时 间为 3,2 ，各进程服务时间为 2,3 ，以及时间片 q=2 时的情况，输入 情况如图 6 所示。图 6 创建进程3 ）输入成功后，按回车键，进程在程序中的具体实现情况即：时间轮转情 况。进程在调度算法中，计算出 的具体 的完 成时间，周转时间，带权时间，平均周 转时间，平均带权周转时间，如图 7 所示。沈阳大学NO.8图 7 进程运行结果3）选择 2：退出界面，如图 8课程设计说明

14、书图 8 退出界面6. 心得体会首先，我认为这次课程设计是对学习操作系统的一次综合考察， 锻炼我综合 分析问题、 解决问题的能力。 初次找到课程设计的题目时， 为程序本身的简单而 窃喜过；实验过程中也出现了一些难题需要解决， 为此去苦苦探索过。 课程设计 期间，曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，一次次实践。当沈阳大学课程设计说明书NO.9我的想法得到实现， 又学会了新的知识的时候， 心中满是欣喜， 或许这是实践出 真知的真实验证，有付出就有回报的真实写照吧。其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有 那么一部分是以前学过的问题， 但是已经忘却或是以前没有

15、真正的理解过。 但是 你会发现就在你的身边， 会有那么一批人在背后热心的帮助你， 这好像是人生的 一种历程， 团队的协作和彼此心的交流让我们彼此丰厚起来， 这也是我们成长中 必不可失的重要部分。最后，我认识到了自己的不足。平心而论，以前真的没有认真的学习过，即 使是在听课， 可是后来却没有对学习中出现的问题而仔细分析过。 得过且过，迷 失了我前进的方向， 而现在却又重新敞开了。 不论是以后的学习还是工作， 我想 这都是很重要的，我需要不断进步的动力。7. 参考文献1 陈莉君等. Linux 操作系统原理与应用 M . 北京:清华大学出版社 . 2012.12 李龙来,吴杰,吕智慧,杨明. 基于

16、 Web服务的分布式文件系统管理与优化方案 J. 计算机工程与设计 ,2012.3 庞丽萍，阳富民 . 计算机操作系统 （第 2 版）M . 北京：人民邮电出版社 .2014.14 孙洪庆. 浅谈对计算机操作系统的认识 J. 改革与开放 ,2011,04:140.5 汤小丹. 计算机操作系统（第 4版）M. 西安：电子科技大学出版社 . 2014.5沈阳大学课程设计说明书NO.10附录：#include #include #include typedef int QElemType;static const int MaxNum=100; typedef struct QNode QElemT

17、ype data;struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front;QueuePtr rear; LinkQueue;struct PCB int ArrivalTime;int ServiceTime; char number;mMaxNum;int InitQueue(LinkQueue &Q);int DestroyQueue(LinkQueue &Q);int EnQueue(LinkQueue &Q,QElemType e);int DeQueue(LinkQueue &Q,QElemType e);

18、int QueueEmpty(LinkQueue &Q); void chioce(struct PCB pcb,int n); void caidan();void create();int n,q,FinishedTimeMaxNum,WholeTimeMaxNum;double WeightWholeTimeMaxNum,Average_WT=0,Average_WWT=0; LinkQueue Q;void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q); void main()沈阳大学 while(1) / s

19、ystem(cls);课程设计说明书NO.11coutendl;caidan();int n;cout 请选择( 1-2 ) ： n;if(n2)cout 输入有误，请重新输入 endl;switch(n) case 1:create();break;case 2:return ;/RR 算法的具体实现void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q)int countTime=0,e;chioce(m,n); if(ArrivalTime0=0) countTime=0;elsecountTime=m0.Arri

20、valTime;int STimeMaxNum,pushedMaxNum;for(int i=0;iq)STimee=STimee-q; countTime+=q;elsecountTime+=STimee;STimee=0;FinishedTimee=countTime;while(time0)沈阳大学cout 时刻 setw(2)time: 进程 e 正在运行 endl; 课程设计说明书NO.12time+;for(i=1;in;i+)if(STime!=0&i!=e&mi.ArrivalTime0)/ 判断进程 e 是否已执行完EnQueue(Q,e); for(i=0;in;i+) /

21、 求周转时间和带权周转时间WholeTimei=FinishedTimei-mi.ArrivalTime;WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime);Average_WT+=WholeTimei; Average_WWT+=WeightWholeTimei;Average_WT/=n;/ 求平均周转时间Average_WWT/=n;/ 求平均带权周转时间/ 输出 coutendl;coutendl; coutendl;cout 进程运行的结果是： endl;cout-endl;cout 进程名称 : ; for(i

22、=0;in;i+) coutsetw(8)mi.number ; coutendl;cout 到达时间 : ; for(i=0;in;i+) coutsetw(8)mi.ArrivalTime ; coutendl;cout 服务时间 : ; for(i=0;in;i+) coutsetw(8)mi.ServiceTime ; coutendl;cout 完成时间 : ; for(i=0;in;i+) coutsetw(8)FinishedTimei ; coutendl;cout 周转时间 : ; for(i=0;in;i+) coutsetw(8)WholeTimei ;沈阳大学课程设计说

23、明书NO.13coutendl; cout 带权周转： ;for(i=0;in;i+) coutsetw(8)setiosflags(ios:fixed)setprecision(2)WeightWholeTimeicoutendl;cout-endl;cout 平均周转时间为： Average_WTendl;cout 平均带权周转时间为 :Average_WWTnext=NULL;return 1; / 销毁链队列 Qint DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next;free(Q.front); Q.front

24、=Q.rear;return 1; / 入队 int EnQueue(LinkQueue &Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode); p-data=e;p-next=NULL; Q.rear-next=p;Q.rear=p;return 1; / 出队，并用 e 返回出队节点的元素值 int DeQueue(LinkQueue &Q,QElemType e) QueuePtr p; if(Q.front=Q.rear) return 0; p=Q.front-next; e=p-data; Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;沈阳大学课程设计说明书NO.14free(p);return e;/ 判断链队列 Q 是否为