[优秀毕业设计精品] 进程模拟调度程序

1、数学与计算机学院 课程设计说明书 课 程 名 称: 操作系统原理-课程设计 课 程 代 码: 题 目: 进程调度模拟程序 年级/专业/班: 09 级 计科 5 班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 12 月 9 日 完 成 时 间: 2011 年 12 月 23 日 课程设计成绩： 学习态度及平 时成绩（30） 技术水平与实际 能力（20） 创新（5）说明书撰写质量（45） 总 分 （100） 指导教师签名： 年 月 日 i 摘摘 要要 随着计算机的普及，在计算机上配置合适的操作系统，已成为不可或缺的因 素，操作系统时配置在计算机硬件上的第一层软件，时对硬件系统的首次

2、扩充，其 他的诸如汇编程序，编译程序，数据库管理系统等系统软件，以及大量的应用软件， 都将依赖于操作系统的支持，取得它的服务。os 作为用户与计算机硬件之间的接 口，作为系统资源的管理者，实现了对计算机资源的抽象，因此，不断提高计算机 资源的利用率，方便用户，以及器件的不断更新换代，计算机体系结构的不断发展， 已经成为推动计算机操作系统发展的主要因素，为了达到这些目的，了解操作系统 的发展过程，熟悉操作系统的内部结构，掌握操作系统的运行，已经成为当代大学 生，特别是计算机专业的学生所必不可少的知识。 操作系统的主要任务是为多道程序的运行提供良好的运行环境，并能最大程 度的提高系统中各种资源的利

3、用率和方便用户，为了实现这些功能，操作系统还应 该具有处理机管理，存储器管理，设备管理和文件管理等功能。 关键词：关键词：操作系统；资源利用率；处理机；文件管理 进程模拟调度程序 目 录 1 引 言 .1 1.1 问题的提出 .1 1.2 任务与分析.1 2 程序的主要函数.2 2.1 建立将要模拟进程调度的所有进程 pcb 链表.2 2.2模拟 cpu 运行进程.3 2.3 显示.4 2.4 排序.5 2.5 建立先来先服务调度算法的就绪队列.7 2.6 建立最高优先数优先调度算法的就绪队列.8 2.7 进程模拟调度.9 2.8 主函数.12 3 程序运行平台 .14 4 总体设计 .14

4、5 程序结构体的说明 .14 6 程序运行结果 .15 7 结论.22 8 参考文献 .23 9 附录 .24 进程模拟调度程序 0 1 引引 言言 1.1 问题的提出问题的提出 随着现在操作系统的日趋成熟，用户对计算机的需求越来越多，处理机在同一时 刻处理资源的能力是有限的，从而导致各种任务随时随地的争夺使用处理机，因而此 对程序的并发能力提出了更高的要求。 引进并发技术后，为了更好地说明并发现象（尤其是动态进程） ，引入了进程的概 念。进程是一个具有一定独立功能的可并发执行的关于某个数据集合一次运行活动的 程序。一个程序的启动执行，便是一个进程的建立；一个程序执行结束（正常或者是 不正常）

5、 ，便是一个进程的撤销。由于同时处于就绪态（争夺使用 cpu 资源）的进程通 常比较多，因此需要 cpu 调度算法来决定由哪个进程获得 cpu 使用权进入运行状态， 即进程调度算法。 1.2 任务与分析任务与分析 本课题主要的目的是编写并调试一个有 n 个进程并发的进程模拟调度程序。 进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高 的进程）和先来先服务算法。 每个进程有一个进程控制块（ pcb）表示。进程控制块可以包含如下信息：进程 名、优先数、到达时间、需要运行时间、已用 cpu 时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生

6、） 。进 程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。 等待 i/o 的时间以时间片为单位进行计算，可随机产生，也可事先指定。 每个进程的状态可以是就绪 r（ready） 、运行 r（run） 、等待（wait）或完成 f（finish）四种状态之一。 就绪进程获得 cpu 后都只能运行一个时间片。用已占用 cpu 时间加 1 来表示。 如果运行一个时间片后，进程的已占用 cpu 时间已达到所需要的运行时间，则撤 消该进程，如果运行一个时间片后进程的已占用 cpu 时间还未达所需要的运行时间， 也就是进程还需要继续运行，此时应将进程的优先数减 1（即降低一级） ，然后

7、把它插 入就绪队列等待 cpu。 xxx 数计学院课程设计说明书 1 每进行一次调度程序都打印一次运行进程、就绪队列、等待进程以及各个进程的 pcb，以便进行检查。 重复以上过程，直到所要进程都完成为止。 2 2 程序的主要函数 2.1 建立将要模拟进程调度的所有进程建立将要模拟进程调度的所有进程 pcb 链表链表 算法思想算法思想：要建立的进程个数 n 作为函数参数，头指针作为返回，在函数内部由一重 循环建立每个进程 pcb 的各个数据项，其中进程需要运行时间、到达时间以及优先数 全部采用随机生成。 代码代码： plist *creatpro(int n) /建立所有将要进行 n 个模拟调度

8、的进程 int j; plist *p, *q, *head; p= (plist *) malloc(sizeof(plist); head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(rand_max+1.0); p-arrivetime = (int)(10.0*rand()/(rand_max+1.0); p-pri = 1+(int)(9.0*rand()/(rand_max+1.0); p-state = 0; p-cputime =0; p-next = (plist *) malloc(sizeof(p

9、list); p=p-next; q-next = null; return head; 进程模拟调度程序 2 流程图：流程图： p= (plist *) malloc(sizeof(plist); head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(rand_max+1.0); p-arrivetime = (int)(10.0*rand()/(rand_max+1.0); p-pri = 1+(int)(9.0*rand()/(rand_max+1.0); p-state = 0; p-cputime =0; p

10、-next = (plist *) malloc(sizeof(plist); p=p-next; q-next = null; return head; 2.2 模拟模拟 cpu 运行进程运行进程 算法思想算法思想：需要运行进程的 pcb 作为函数参数，先修改进程状态，然后修改再修改进 程已运行时间和还需运行时间。 代码：代码： void action(plist * nowpro) /模拟 cup 运行进程的过程 nowpro-state = 2; /设置进程状态为运行态 printf(now is process %d ,nowpro-name); nowpro-needtime-; /

11、修改进程还需运行时间 nowpro-cputime+; /修改进程已运行时间 nowpro-state = 1; if(nowpro-needtime=0)/进程运行结束 printf(tthe process %d is endn,nowpro-name); xxx 数计学院课程设计说明书 3 nowpro-state = 4; /进程运行结束，设置进程状态为结束态 else printf(tprocess %d needtime is %dn,nowpro-name,nowpro-needtime); printf(-n); 流程图流程图： nowpro-state = 2; nowpro

12、-needtime-; nowpro-cputime+; nowpro-state = 1; nowpro-needtime=0？ 真 假 printf(tthe process %d is endn, printf(tprocess %d needtime is %dn, nowpro-name); nowpro-name,nowpro-needtime); nowpro-state = 4; 2.3 显示显示 算法思想算法思想：先判断链表借点是否为空，然后利用循环输出各 pcb 信息 代码：代码： void show(plist * process) /显示 if(!process) pr

13、intf(there is no process nown); while(process 进程模拟调度程序 4 printf(tneedtime %d,process-needtime); printf( arrivetime %d,process-arrivetime); printf( pri %d,process-pri); printf( state %d,process-state); printf( cputime %dn,process-cputime); process = process-next; 流程图：流程图： if(!process) 真 假 printf(ther

14、e is no 当 process printf(name of process %d,process-name); printf(tneedtime %d,process-needtime); printf( arrivetime %d,process-arrivetime); printf( pri %d,process-pri); printf( state %d,process-state); printf( cputime %dn,process-cputime); process = process-next; 2.4 排序排序 算法思想：算法思想：利用两层循环，比较相邻两个元素的

15、大小，第一遍将最大的数排到最末， 第二遍将次大的数排到最末的数的前面，经 n-1 遍后将满足排序的要求。 代码：代码： plist *sort(plist *head) /将进程队列按到达先后顺序排序 plist *p,*p1,*p2,*p3,*temp; p=head; while(p-next!=null) p=p-next; xxx 数计学院课程设计说明书 5 while(p!=head) p3=p1=head; p2=p1-next; while(p1!=p else p3-next=p2; temp=p2-next; p2-next=p1; p1-next=temp; temp=p1

16、; p1=p2; p2=temp; p3=p1; p1=p1-next; p2=p1-next; p=p3; return head; 2.5 建立先来先服务调度算法的就绪队列建立先来先服务调度算法的就绪队列 算法思想算法思想：先来先服务调度算法中的就绪队列是按到达时间的先后排序的，当就绪队 进程模拟调度程序 6 列为空时，直接将作为将要添加的进程接将作为将要添加的进程 pcbpcb temptemp 作为队头，如果就绪队列不为空，则作为队头，如果就绪队列不为空，则 将将 temptemp 添加到队列末尾。添加到队列末尾。 添加到就绪队列后再修改进程状态为就绪态。添加到就绪队列后再修改进程状态

17、为就绪态。 代码：代码： plist *fcfs_creatready(plist *ready_queue,plist *temp) /将进程 temp 添加到就绪队列 ready_queue 的尾部 plist *q; q=ready_queue; if(ready_queue) /当就绪队列不为空时，新进入的进程添加到就绪队列末尾 while(q-next) q=q-next; /使指针 p 指向就绪队列中最后一个进程 q-next=temp; temp-state=1;/修改进程状态 temp-next=null; else /当就绪队列为空时，新进入的进程作为就绪队列头部 ready

18、_queue=temp; ready_queue-state = 1; /将进程状态设为就绪状态 temp-next=null; return ready_queue; 流程图流程图： xxx 数计学院课程设计说明书 7 q=ready_queue; ready_queue=null？ 真 假 q-next ready_queue=temp; q=q-next; ready_queue-state=1; q-next=temp; temp-next=null; temp-state=1; temp-next=null; return ready_queue; 2.6 建立最高优先数优先调度算法

19、的就绪队列建立最高优先数优先调度算法的就绪队列 算法思想算法思想：最高优先数优先调度算法中的就绪队列是按进程优先数递减排序的，当就 绪队列为空时，直接将作为将要添加的进程 pcb temp 作为队头，如果就绪队列不为空， 则将 temp 添加到队列合适位置。然后再修改进程状态为就绪态。 代码代码： plist *hrrn_creatready(plist *ready_queue, plist *temp) /按优先数递减的顺序将进程 temp 添加到就绪队列 ready_queue 的合适位置 plist *q, *p; p=q=ready_queue; if(ready_queue q=q

20、-next; /使指针 p-next 指向就绪队列中进程 temp 的插入位置 p-next=temp; temp-next=q; temp-state=1;/修改进程状态 进程模拟调度程序 8 else /当就绪队列为空时，新进入的进程作为就绪队列头部 temp-next=ready_queue; ready_queue=temp; ready_queue-state = 1; /将进程状态设为就绪状态 return ready_queue; 流程图流程图： p=q=ready_queue; ready_queue-pritemp-pri 真 ready_queue 假 q p=q; tem

21、p-next=null; ready_queue-state=1; temp-next=null; q=q-next; q-next=temp; temp-state=1; return ready_queue; 2.7 进程模拟调度进程模拟调度 算法思想：算法思想： 1.先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也 可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选 择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程， 然后放入就绪队列。在进程调度中采用 fcfs 算法时，则每次调度是从就绪队列中选

22、择 一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完 成或发生某事件而阻塞后才放弃处理机。fcfs 算法比较有利于长作业（进程） ，而不利 于短作业（进程） 。 2.最高优先数调度算法 优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理 xxx 数计学院课程设计说明书 9 机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占 式优先数算法。在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先 数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机， 这时系统才能重新将处理机分配给就绪队列中的另一个优先

23、数最高的进程。在抢占式 优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但 在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理 机分配给新的高优先数进程。 本次模拟采用抢占式最高优先数调度算法。 如果调用此函数时是 process_simulation(process,fcfs_creatready);则此时是 先来先服务算法模拟调度。 如果调用此函数时是 process_simulation(process,hrrn_creatready);则此时是 最高优先数优先算法模拟调度。 代码代码： void process_simulation(pl

24、ist * process,plist *creatready(plist *,plist *) int time; /模拟 cpu 时钟 plist *temp; plist *ready_queue=null; /定义就绪队列，并初始化 time = 0; /初始化 cpu 时序 while(process|ready_queue) /当进程队列不为空，或者就绪队列不为空 while(process process = process-next; ready_queue=creatready(ready_queue, temp); if(ready_queue = null) /如果没有进

25、程运行，打印 cpu 空转信息 printf(the time sequence is :%dn,time); printf(the ready queue is :n); printf(there is no process nown); 进程模拟调度程序 10 printf(-n); time+; sleep(500); else/如果有进程需要运行，则模拟进程运行过程 printf(the time sequence is :%dn,time); printf(the ready queue is :n); show(ready_queue-next);/打印就绪队列 action(re

26、ady_queue); /模拟进程运行 if(ready_queue -needtime = 0) /进程运行结束，此时将此进程从就绪 队列中删除 ready_queue=ready_queue-next; time+; sleep(1000); printf(the time sequence is :%dn,time); /先来先服务模拟调度结束 printf(there is no process nown); printf(-n); 流程图流程图： xxx 数计学院课程设计说明书 11 plist *ready_queue=null; time = 0; process|ready_q

27、ueue process process = process-next; ready_queue=creatready(ready_queue, temp); ready_queue = null 真 假 printf(the time sequence is :%dn,time); printf(the time sequence is :%dn,time); printf(the ready queue is :n); printf(the ready queue is :n); printf(there is no process nown); show(ready_queue-next

28、); printf(-n); action(ready_queue); time+; ready_queue -needtime = 0 sleep(500); 真 假 ready_queue=ready_queue-next; time+; sleep(1000); printf(the time sequence is :%dn,time); printf(there is no process nown); printf(-n); 2.8 主函数主函数 算法思想算法思想：先建立所有需要模拟调度的 pcb 链表，然后采用冒泡法将链表按进程到达 时间递增的顺序排序，然后采用 switch-c

29、ase 选择结构进行菜单选择需要模拟的调度 模拟。 代码：代码： void main() int n; /*the number of process*/ int k; plist *process; printf(please input the number of process: ); scanf(%d, process = creatpro(n); 进程模拟调度程序 12 process = sort(process);/* 利用冒泡法将进程按到达时间排序 */ show(process); printf(please choose the what you want to use:n

30、); printf(t1 先来先服务nt2 最高优先数优先n); scanf(%d, switch(k) case 1: process_simulation(process,fcfs_creatready); /* 先来先服务 */ break; case 2: process_simulation(process,hrrn_creatready); /* 最高优先数算 法 */ break; default : printf(请输入正确选项！n); break; xxx 数计学院课程设计说明书 13 3 3 程序运行平台程序运行平台 windows xp microsoft visual

31、c+ 6.0 4 4 总体设计总体设计 开始 先来 先服 务算 法模 拟调 度 最高 优先 数优 先算 法模 拟调 度 退 出 系统总体框架图 5 5 程序结构体的说明程序结构体的说明 typedef struct pcb int name; /进程名 int needtime; /进程所需运行时间 int arrivetime; /进程到达时间 int pri; /进程优先数 int state; /进程状态：0 表示未到达 1 表示就绪 2 表示运行 3 表示等 待 4 表示结束 int cputime; /已用 cpu 时间 struct pcb *next; plist; 进程模拟调度

32、程序 14 6 程序运行结果 先来先服务模拟调度运行结果：先来先服务模拟调度运行结果： xxx 数计学院课程设计说明书 15 进程模拟调度程序 16 xxx 数计学院课程设计说明书 17 最高优先数优先调度模拟运行结果：最高优先数优先调度模拟运行结果： 进程模拟调度程序 18 xxx 数计学院课程设计说明书 19 进程模拟调度程序 20 xxx 数计学院课程设计说明书 21 7 结论 这次课程设计的题目是模拟进程调度，课程设计的任务书要求实现模拟作业调度 的两个算法：先来先服务调度算法，最高优先数优先算法。这次的课程设计我采用的 是 c 语言来编写的，首先编写一个结构体用来存放进程的相关信息，

33、即 pcb。然后将要 模拟调度的进程 pcb 放在队列中。通过不断的调试与优化，程序很好的模拟了进程的 调度过程，先来先服务，最高优先数优先。在编写实现最高优先数优先算法的时候， 刚开始由于没有考虑到后到达的进程的优先数，和当前运行的进程的优先数有高低之 分，导致调度得不到预想的结果，经过改正之后就得到了正确的结果。他们的调度结 果都不一样，但是对于进程调度而言，这几个算法各有个的优点和缺点。先来先服务 算法有利于长进程而不利于短进程；最高优先数优先算法既照顾了长进程，又考虑了 进程的优先级，不会使长进程长期得不到服务，该算法实现了比较好的折中。 通过本次课程设计加深了我对进程调度算法的理解并

34、且还明白了调度的过程。在 上操作系统课的时候对这几个算法并不是很理解，通过实现了这几个调度算法的模拟 之后我，我就明白了这几个算法的本质，并且理解了这几个算法。在做课程设计的时 候自己还是存在不足之处，在考虑算法的时候考虑的不够周全，在编写最高优先数优 先的时候刚开始由于没有考虑到后到达的进程与之前的进程的优先数不一样造成调度 的结果与预想的不一样，通过仔细的检查与思考之后发现了这个问题并且改正了之后 就可以得到正确的结果了。这次课程设计还让我明白了只有多实践才能发现自己的问 题所在才能够很好的掌握知识。 进程模拟调度程序 22 8 参考文献 1张尧学等编著. 计算机操作系统教程.北京：清华大

35、学出版社，2006.02 2汤子瀛等编著.计算机操作系统.西安：西安电子科技出版社，1996.12 3陈向群 编著.操作系统教程.北京：北京大学出版社，2007.01 4罗宇 等编著.操作系统课程设计.北京：机械工业出版社，2005.9 xxx 数计学院课程设计说明书 23 附 录 程序源代码：程序源代码： #include #include #include #include typedef struct pcb int name; /进程名 int needtime; /进程所需运行时间 int arrivetime; /进程到达时间 int pri; /进程优先数 int state;

36、/进程状态：0 表示未到达 1 表示就绪 2 表示运行 3 表示等待 4 表示结束 int cputime; /已用 cpu 时间 struct pcb *next; plist; plist *creatpro(int n) /建立所有将要进行 n 个模拟调度的进程 int j; plist *p, *q, *head; p= (plist *) malloc(sizeof(plist); head = p; for(j=0;jname = j+1; p-needtime = 1+(int)(10.0*rand()/(rand_max+1.0); p-arrivetime = (int)(1

37、0.0*rand()/(rand_max+1.0); 进程模拟调度程序 24 p-pri = 1+(int)(9.0*rand()/(rand_max+1.0); p-state = 0; p-cputime =0; p-next = (plist *) malloc(sizeof(plist); p=p-next; q-next = null; return head; void action(plist * nowpro) /模拟 cup 运行进程的过程 nowpro-state = 2; /设置进程状态为运行态 printf(now is process %d ,nowpro-name)

38、; nowpro-needtime-; /修改进程还需运行时间 nowpro-cputime+; /修改进程已运行时间 nowpro-state = 1; if(nowpro-needtime=0)/进程运行结束 printf(tthe process %d is endn,nowpro-name); nowpro-state = 4; /进程运行结束，设置进程状态为结束态 else printf(tprocess %d needtime is %dn,nowpro-name,nowpro-needtime); printf(-n); void show(plist * process) xx

39、x 数计学院课程设计说明书 25 /显示 if(!process) printf(there is no process nown); while(process printf(tneedtime %d,process-needtime); printf( arrivetime %d,process-arrivetime); printf( pri %d,process-pri); printf( state %d,process-state); printf( cputime %dn,process-cputime); process = process-next; plist *sort(

40、plist *head) /将进程队列按到达先后顺序排序 plist *p,*p1,*p2,*p3,*temp; p=head; while(p-next!=null) p=p-next; while(p!=head) p3=p1=head; p2=p1-next; 进程模拟调度程序 26 while(p1!=p else p3-next=p2; temp=p2-next; p2-next=p1; p1-next=temp; temp=p1; p1=p2; p2=temp; p3=p1; p1=p1-next; p2=p1-next; p=p3; return head; plist *fcf

41、s_creatready(plist *ready_queue,plist *temp) /将进程 temp 添加到就绪队列 ready_queue 的尾部 xxx 数计学院课程设计说明书 27 plist *q; q=ready_queue; if(ready_queue) /当就绪队列不为空时，新进入的进程添加到就绪队列末尾 while(q-next) q=q-next; /使指针 p 指向就绪队列中最后一个进程 q-next=temp; temp-state=1;/修改进程状态 temp-next=null; else /当就绪队列为空时，新进入的进程作为就绪队列头部 ready_que

42、ue=temp; ready_queue-state = 1; /将进程状态设为就绪状态 temp-next=null; return ready_queue; plist *hrrn_creatready(plist *ready_queue, plist *temp) /按优先数递减的顺序将进程 temp 添加到就绪队列 ready_queue 的合适位置 plist *q, *p; p=q=ready_queue; if(ready_queue q=q-next; /使指针 p-next 指向就绪队列中进程 temp 的插入位置 p-next=temp; temp-next=q; temp-state=1;/修改进程状态 else /当就绪队列为空时，新进入的进程作为就绪队列头部 temp-next=ready_queue; ready_queue=temp; ready_queue-state = 1; /将进程状态设为就