操作系统课程设计说明书郑丽波

1、. . . . 中北大学操作系统课程设计说 明 书 学 院、系：软件学院专 业：软件工程学 生 姓 名：丽波学 号：1121011747设 计 题 目：基于Linux的模拟进程调度算法的实现起 迄 日 期:2013年11月22日- 2013年12月6日指 导 教 师:康珺   2013 年 12 月 6日1 需求分析在操作系统中，进程调度实际就是给进程分配存资源，随着计算机系统的发展，为了更充分的利用系统资源以与提高计算机的运行效率，因此需要在不同的环境下采用不同的调度算法，使得系统具有合理的响应时间，就要求系统能按照某种算法，动态的把处理机分配给就绪队

2、列中的一个进程，使之执行。因此，就需要设计出几种不同的算法，通过比较，选出一种最优的。本程序主要实现基于linux的进程调度算法的实现。共实现了三种不同的调度算法，分别是：先来先服务调度算法，短作业优先调度，高响应比调度算法。在程序的执行过程中，可以自主输入进程的个数以与进程必要的信息，如：进程的创建时间，服务时间等，然后通过不同的调度算法实现进程的调度，每一种算法都能动态的演示进程调度的过程，时间间隔为一秒钟，并且可以计算出每种调度算法下的平均周转时间和平均带权周转时间，通过排序比较各种调度算法的优劣。2 总体设计本程序主要分为四大模块：1. 创建进程：可以手动创建进程，用户可以自主决定进程

3、的个数，并且在创建进程时自主决定进程名，进程的创建时间以与执行时间。2. 几种不同的调度算法：分别是先来先服务调度算法，短作业优先调度和高响应比调度算法。3. 显示结果函数：在各个调度算法中，每一步执行完后都会以表格的形式显示出进程的信息，包括：进程名，创建时间，服务时间，开始执行时间，完成时间，周转时间，带权周转时间。4. 比较各算法的优劣：对平均周转时间和平均带权周转时间按照由小到大的顺序进行排序比较。结构图如下：基于linux的进程调度算法三种调度算法 显示结果 先来先服务 FCFS短作业优先SJF高响应比调度 HHRN存放PCB信息结构体数组录入PCB信息比较各算法的优劣程序中采用结构

4、体来存储进程信息，其中包括：进程名，进程的创建时间，服务时间，执行时间，完成时间，周转时间，带权周转时间，等待时间，优先权，时候完成等，各个进程共同组成一个结构体数组。数据结构如下：struct Pro/进程调度信息结构体char name;/进程名float creat_time;/创建时间float serve_time;/服务时间float excute_time;/执行时间float finish_time;/完成时间float zhou_time;/周转时间float d_time;/带权周转时间float wait_time;/等待时间 float priority;/优先权int

5、 finish;/是否已经完成;3详细设计先来先服务调度算法：当在进程调度算法中采用该算法时，每次调度都是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程一直到运行完成或是发生某时间而阻塞后才放弃处理机。核心代码： int Input(struct Pro a)/输入函数int n,i;printf("输入要创建的进程个数:");scanf("%d",&n);printf("输入进程名、开始时间和服务时间:n");getchar();for(i=0;i<n;i+)scanf("%c

6、 %f %f",&,&ai.creat_time,&ai.serve_time);getchar();ai.d_time=0;ai.finish_time=0;return n;void compare() /比较函数 float temp;if(fs>ss)temp=fs;fs=ss;ss=temp;if(fs>hs)temp=fs;fs=hs;hs=temp;if(ss>hs)temp=ss;ss=hs;hs=temp;printf("平均周转时间由小到大以此为: %8.2f %3.2f %3.2fn",

7、fs,ss,hs);if(ft>st)temp=ft;ft=st;st=temp;if(ft>ht)temp=ft;ft=ht;ht=temp;if(st>ht)temp=st;st=ht;ht=temp;printf("平均带权周转时间由小到大以此为：%3.2f %3.2f %3.2fn",ft,st,ht);void Display(struct Pro a,int n) /显示函数int i;printf("数据输出:n");printf("进程名 创建时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间n&q

8、uot;);for(i=0;i<n;i+)printf(" %c",);printf(" %10.2f",ai.creat_time);printf(" %10.2f",ai.serve_time);printf(" %10.2f",ai.excute_time);printf(" %12.2f",ai.finish_time);printf(" %10.2f",ai.zhou_time);printf(" %13.2f",ai.d_t

9、ime);printf("n");main() int n,k; struct Pro a20,b20,c20; show_welcome(); printf("nn"); n=Input(a);for(k=0;k<19;k+)bk=ak; ck=ak; FCFS(a,n); printf("*n"); SJF(b,n); printf("*n"); HRRN(c,n); printf("对于平均周转时间： 采用FCFS算法为：%3.2f SJF算法为：%3.2f HRRN算法为：%3.2fn&qu

10、ot;,fs,ss,hs); printf("对于平均带权周转时间：采用FCFS算法为：%3.2f SJF算法为：%3.2f HRRN算法为：%3.2fn",ft,st,ht); compare();运行结果：4.心得体会通过这次课设，让我对进程先来先服务，有了更深入的认识！初步理解了操作系统对于进程处理的基本思想！并且对linux操作系统有了初步的了解，学会了一些基本的操作，在合作过程中，体会到了团体合作的快乐。附：#include<stdio.h>#include<unistd.h> struct Pro/进程调度信息结构体char name;/

11、进程名float creat_time;/创建时间float serve_time;/服务时间float excute_time;/执行时间float finish_time;/完成时间float zhou_time;/周转时间float d_time;/带权周转时间float wait_time;/等待时间 float priority;/优先权int finish;/是否已经完成;float Pjzhou_time,Pjd_time; /平均周转时间和平均带权时间float s,t; /分别存储周转时间和带权时间的和float fs,ft,ss,st,hs,ht; /分别存储各算法中的平均

12、周转时间和平均带权时间void Display(struct Pro a,int n) ;/显示函数void FCFS(struct Pro a,int n)/FCFS算法int i,j;int min=1;/最早到达int max=1;/最晚到达int temp=0;/记录上一次运行进程for(j=0;j<n;j+)min=max;for(i=0;i<n;i+)if(amin.creat_time>ai.creat_time)&&(ai.d_time=0)/选出当前未运行进程中到达时间最短进程 min=i;if(amax.creat_time<ai.c

13、reat_time)&&(ai.d_time=0)/选出当前未运行进程中到达时间最长进程 max=i;if(atemp.finish_time=0)/第一个执行进程amin.excute_time=0; amin.finish_time=0+a0.serve_time;elseamin.excute_time=atemp.finish_time; amin.finish_time=amin.excute_time+amin.serve_time;amin.zhou_time=amin.finish_time-amin.creat_time;/周转时间=完成时间-创建时间amin

14、.d_time=amin.zhou_time/amin.serve_time;/带权周转时间=周转时间/服务时间;temp=min; printf("nn");printf("FCFS:n"); Display(a,n);sleep(1); s=0,t=0; for(i=0;i<n;i+) s+=ai.zhou_time; t+=ai.d_time; Pjzhou_time=s/n; Pjd_time=t/n; fs=Pjzhou_time; ft=Pjd_time; printf("n"); printf("平均周转

15、时间 t=%5.3fn平均带权周转时间 w=%5.3fn",Pjzhou_time,Pjd_time); printf("n"); printf("n");void SJF(struct Pro a,int n) /SJC算法int i,j;int min=1;int max=1;int temp=0;a0.excute_time=0;a0.finish_time=0+a0.serve_time;a0.zhou_time=a0.finish_time-a0.creat_time;a0.d_time=a0.zhou_time/a0.serve_t

16、ime;for(j=1;j<n;j+)min=max;for(i=1;i<n;i+)if(amin.serve_time>=ai.serve_time)&&(ai.d_time=0)&&(ai.creat_time<=atemp.finish_time)/选出当前未运行进程中服务时间最短进程 min=i;if(amax.serve_time<=ai.serve_time)&&(ai.d_time=0)&&(ai.creat_time<=atemp.finish_time)/选出当前未运行进程中服

17、务时间最长进程 max=i; amin.excute_time=atemp.finish_time;amin.finish_time=amin.excute_time+amin.serve_time;amin.zhou_time=amin.finish_time-amin.creat_time;/周转时间=完成时间-创建时间amin.d_time=amin.zhou_time/amin.serve_time;/带权周转时间=周转时间/服务时间;temp=min; printf("nn");printf("SJF:n"); Display(a,n);sle

18、ep(1); s=0,t=0; for(i=0;i<n;i+) s+=ai.zhou_time; t+=ai.d_time; Pjzhou_time=s/n; Pjd_time=t/n; printf("n"); ss=Pjzhou_time; st=Pjd_time; printf("平均周转时间 t=%5.3fn平均带权周转时间 w=%5.3fn",Pjzhou_time,Pjd_time); printf("n"); printf("n");int HRN(struct Pro a,int pre,in

19、t n) /优先权的判断int current=1,i,j;/* 优先权 =(等待时间+服务时间)/服务时间*/for(i=0; i<n; i+) ai.wait_time=apre.finish_time-ai.creat_time; /*等待时间 =上一个进程的完成时间-创建时间*/ ai.priority=(ai.wait_time+ai.serve_time)/ai.serve_time;for(i=0; i<n; i+)if(!ai.finish)current=i; /*找到第一个还没完成的进程*/break;for( j=i; j<n; j+) /*和后面的进程

20、比较*/if( !aj.finish) /* 还没完成(运行)*/if(acurrent.creat_time<=apre.finish_time) /*如果进程在上一个进程完成之前创建*/if(aj.creat_time<=apre.finish_time && aj.priority>acurrent.priority )current=j;/* 找出创建时间在上一个进程完成之前，优先权高的进程*/else /* 如果进程是在上一个进程完成之后创建*/if(aj.creat_time<acurrent.creat_time)current=j; /*

21、 找出比较早创建的一个*/if(aj.creat_time=acurrent.creat_time) /* 如果同时创建*/if(aj.priority>acurrent.priority)current=j; /*找出服务时间比较短的一个*/return current;/*返回当前进程*/void HRRN( struct Pro a,int n) /最高响应比算法int i;int current=0, times=0, pre=0; /当前，次数，前一个apre.finish_time=0; for(i=0;i<n;i+) /初始化优先权和完成时间都为0 ai.priori

22、ty=0; ai.finish=0; for(times=0; times<n; times+) /开始执行current=HRN(a,pre,n);i=current;if(times=0) / 第一个进程 ai.excute_time=ai.creat_time;ai.finish_time=ai.excute_time+ai.serve_time; ai.zhou_time=ai.serve_time;ai.d_time=1.0; else if(ai.creat_time>apre.finish_time) ai.excute_time=ai.creat_time; els

23、eai.excute_time=apre.finish_time; ai.finish_time=ai.excute_time+ai.serve_time; ai.zhou_time=ai.finish_time-ai.creat_time; ai.d_time=ai.zhou_time/ai.serve_time; ai.finish=1; pre=current;printf("nn"); printf("HRRN:n"); Display(a,n);sleep(1); s=0,t=0; for(i=0;i<n;i+) s+=ai.zhou_t

24、ime; t+=ai.d_time; Pjzhou_time=s/n; Pjd_time=t/n; hs=Pjzhou_time; ht=Pjd_time; printf("n"); printf("平均周转时间 t=%5.3fn平均带权周转时间 w=%5.3fn",Pjzhou_time,Pjd_time); printf("n"); printf("n");int Input(struct Pro a)/输入函数int n,i;printf("输入要创建的进程个数:");scanf(&quo

25、t;%d",&n);printf("输入进程名、开始时间和服务时间:n");getchar();for(i=0;i<n;i+)scanf("%c %f %f",&,&ai.creat_time,&ai.serve_time);getchar();ai.d_time=0;ai.finish_time=0;return n;void compare() /比较函数 float temp;if(fs>ss)temp=fs;fs=ss;ss=temp;if(fs>hs)temp=fs;fs

26、=hs;hs=temp;if(ss>hs)temp=ss;ss=hs;hs=temp;printf("平均周转时间由小到大以此为: %8.2f %3.2f %3.2fn",fs,ss,hs);if(ft>st)temp=ft;ft=st;st=temp;if(ft>ht)temp=ft;ft=ht;ht=temp;if(st>ht)temp=st;st=ht;ht=temp;printf("平均带权周转时间由小到大以此为：%3.2f %3.2f %3.2fn",ft,st,ht);void Display(struct Pro a,int n) /显示函数int i;printf("数据输出:n");printf("进程名创建时间服务时间开始执行时间完成时间周转时间带权周转时间n");for(i=0;i<n;i+)printf(" %c",);printf(" %10.2f",ai.creat_time);printf(" %10.2f",ai.serve_time);printf(" %10.2f",ai.excute_time);printf(" %12.2f&