操作系统课程方案说明书郑丽波

个人资料整理 仅限学习使用中北大学操作系统课程设计说明书学院、系：软件学院专业：软件工程学学生姓名：郑丽波号：1121011747设计题目：基于Linux的模拟进程调度算法的实现起迄日期:2018年11月22日-2018年12月6日指导教师:康珺2018年12月6日需求分析在操作系统中，进程调度实际就是给进程分配内存资源，随着计算机系统的发展，为了更充分的利用系统资源以及提高计算机的运行效率，因此需要在不同的环境下采用不同的调度算法，使得系统具有合理的响应时间，就要求系统能按照某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。因此，就需要设计出几种不同的算法，通过比较，选出一种最优的。本程序主要实现基于 linux 的进程调度算法的实现。共实现了三种不同的调度算法，分别是：先来先服个人资料整理 仅限学习使用务调度算法，短作业优先调度，高响应比调度算法。在程序的执行过程中，可以自主输入进程的个数以及进程必要的信息，如：进程的创建时间，服务时间等，然后通过不同的调度算法实现进程的调度，每一种算法都能动态的演示进程调度的过程，时间间隔为一秒钟，并且可以计算出每种调度算法下的平均周转时间和平均带权周转时间，通过排序比较各种调度算法的优劣。总体设计本程序主要分为四大模块：创建进程：可以手动创建进程，用户可以自主决定进程的个数，并且在创建进程时自主决定进程名，进程的创建时间以及执行时间。几种不同的调度算法：分别是先来先服务调度算法，短作业优先调度和高响应比调度算法。显示结果函数：在各个调度算法中，每一步执行完后都会以表格的形式显示出进程的信息，包括：进程名，创建时间，服务时间，开始执行时间，完成时间，周转时间，带权周转时间。比较各算法的优劣：对平均周转时间和平均带权周转时间按照由小到大的顺序进行排序比较。结构图如下：基于linux的进程调度算法存放PCB信息结构体数组录入PCB信息三种调度算法先来先服务 短作业优先 高响应比调度FCFS SJF HHRN显示结果比较各算法的优劣程序中采用结构体来存储进程信息，其中包括：进程名，进程的创建时间，服务时间，执行时间，完成时间，周转时间，带权周转时间，等待时间，优先权，时候完成等，各个进程共同组成一个结构体数组。数个人资料整理 仅限学习使用据结构如下：structPro//进程调度信息结构体{charname。//进程名floatcreat_time。//创建时间floatserve_time。//服务时间floatexcute_time。//执行时间floatfinish_time。//完成时间floatzhou_time。//周转时间floatd_time。//带权周转时间floatwait_time。//等待时间floatpriority。//优先权intfinish。//是否已经完成}。3．详细设计先来先服务调度算法：当在进程调度算法中采用该算法时，每次调度都是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程一直到运行完成或是发生某时间而阻塞后才放弃处理机。核心代码：intInput(structProa[]>//{

输入函数intn,i 。printf(" 输入要创建的进程个数scanf("%d",&n> 。

:">

。printf("getchar(>

输入进程名、开始时间和服务时间。

:\n">

。for(i=0{

。i<n。i++>scanf("%c%f%f",&a[i].name,&a[i].creat_time,&a[i].serve_time>getchar(> 。a[i].d_time=0 。a[i].finish_time=0 。

。}returnn

。}voidcompare(>

//

比较函数{floattempif(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.2f\n",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.2f\n",ft,st,ht>

。}voidDisplay(structProa[],intn>//{

显示函数inti 。printf("printf("

数据输出进程名

:\n">。创建时间

服务时间

开始执行时间

完成时间

周转时间

带权周转时间\n">

。for(i=0{

。i<n。i++>printf("%c",a[i].name> 。printf("%10.2f",a[i].creat_time>printf("%10.2f",a[i].serve_time>printf("%10.2f",a[i].excute_time>printf("%12.2f",a[i].finish_time>printf("%10.2f",a[i].zhou_time>printf("%13.2f",a[i].d_time>printf("\n"> 。

。

。。。。。}}main(>{intn,k

。structProa[20],b[20],c[20]

。show_welcome(>printf("\n\n">

。。n=Input(a>for(k=0

。。k<19。k++>个人资料整理 仅限学习使用{b[k]=a[k] 。c[k]=a[k] 。}FCFS(a,n> 。printf("*****************************************************************************\n"> 。SJF(b,n> 。printf("*****************************************************************************\n"> 。HRRN(c,n> 。printf(" 对于平均周转时间： 采用 FCFS算法为：%3.2fSJF 算法为：%3.2fHRRN 算法为：%3.2f\n",fs,ss,hs> 。printf(" 对于平均带权周转时间：采用 FCFS算法为：%3.2fSJF 算法为：%3.2fHRRN 算法为：%3.2f\n",ft,st,ht> 。compare(> 。}运行结果：心得体会个人资料整理 仅限学习使用通过这次课设，让我对进程先来先服务，有了更深入的认识！初步理解了操作系统对于进程处理的基本思想！并且对 linux操作系统有了初步的了解，学会了一些基本的操作，在合作过程中，体会到了团体合作的快乐。附：#include<stdio.h>#include<unistd.h>structPro//进程调度信息结构体{charname。//进程名floatcreat_time。//创建时间floatserve_time。//服务时间floatexcute_time。//执行时间floatfinish_time。//完成时间floatzhou_time。//周转时间floatd_time。//带权周转时间floatwait_time。//等待时间floatpriority。//优先权intfinish。//是否已经完成}。floatPjzhou_time,Pjd_time。//平均周转时间和平均带权时间floats,t。//分别存储周转时间和带权时间的和floatfs,ft,ss,st,hs,ht。//分别存储各算法中的平均周转时间和平均带权时间voidDisplay(structProa[],intn>。//显示函数voidFCFS(structProa[],intn>//FCFS 算法{inti,j。intmin=1。//最早到达intmax=1。//最晚到达inttemp=0。//记录上一次运行进程for(j=0。j<n。j++>{min=max。for(i=0。i<n。i++>{if((a[min].creat_time>a[i].creat_time>&&(a[i].d_time==0>>// 选出当前未运行进程中到达时间最短进程min=i。if((a[max].creat_time<a[i].creat_time>&&(a[i].d_time==0>>// 选出当前未运行进程中到达时间最长进程max=i。}if(a[temp].finish_time==0>// 第一个执行进程{a[min].excute_time=0。a[min].finish_time=0+a[0].serve_time 。}else{a[min].excute_time=a[temp].finish_time 。a[min].finish_time=a[min].excute_time+a[min].serve_time 。}个人资料整理 仅限学习使用a[min].zhou_time=a[min].finish_time-a[min].creat_time。//周转时间=完成时间-创建时间a[min].d_time=a[min].zhou_time/a[min].serve_time。//带权周转时间=周转时间/服务时间。temp=min。printf("\n\n">。printf("FCFS:\n">。Display(a,n>。sleep(1>。}s=0,t=0。for(i=0。i<n。i++>{s+=a[i].zhou_time。t+=a[i].d_time。}Pjzhou_time=s/n。Pjd_time=t/n。fs=Pjzhou_time。ft=Pjd_time。printf("\n">。printf("平均周转时间 t=%5.3f\n平均带权周转时间 w=%5.3f\n",Pjzhou_time,Pjd_time> 。printf("\n">。printf("\n">。}voidSJF(structProa[],intn>//SJC算法{inti,j。intmin=1。intmax=1。inttemp=0。a[0].excute_time=0。a[0].finish_time=0+a[0].serve_time。a[0].zhou_time=a[0].finish_time-a[0].creat_time 。a[0].d_time=a[0].zhou_time/a[0].serve_time 。for(j=1。j<n。j++>{min=max。for(i=1。i<n。i++>{if((a[min].serve_time>=a[i].serve_time>&&(a[i].d_time==0>&&(a[i].creat_time<=a[temp].finish_time>>//选出当前未运行进程中服务时间最短进程min=i。if((a[max].serve_time<=a[i].serve_time>&&(a[i].d_time==0>&&(a[i].creat_time<=a[temp].finish_time>>//选出当前未运行进程中服务时间最长进程max=i。}a[min].excute_time=a[temp].finish_time 。a[min].finish_time=a[min].excute_time+a[min].serve_time 。a[min].zhou_time=a[min].finish_time-a[min].creat_time 。//周转时间=完成时间-创建时间a[min].d_time=a[min].zhou_time/a[min].serve_time 。//带权周转时间 =周转时间/服务时间。temp=min。printf("\n\n">。printf("SJF:\n">。Display(a,n>。sleep(1>。个人资料整理 仅限学习使用}s=0,t=0。for(i=0。i<n。i++>{s+=a[i].zhou_time

。t+=a[i].d_time

。}Pjzhou_time=s/n。Pjd_time=t/n。printf("\n">

。ss=Pjzhou_time。st=Pjd_time。printf("平均周转时间printf("\n">。printf("\n">。

t=%5.3f\n

平均带权周转时间

w=%5.3f\n",Pjzhou_time,Pjd_time>

。}intHRN(structProa[],intpre,intn>//{

优先权的判断intcurrent=1,i,j。/*优先权=(等待时间+服务时间>/服务时间*/for(i=0。i<n。i++>{a[i].wait_time=a[pre].finish_time-a[i].creat_time 。/*等待时间 =上一个进程的完成时间a[i].priority=(a[i].wait_time+a[i].serve_time>/a[i].serve_time 。}

-创建时间

*/for(i=0。i<n。i++>{if(!a[i].finish>{current=i。/*找到第一个还没完成的进程 */break。}}for(j=i。j<n。j++>/*和后面的进程比较 */{if(!a[j].finish>/* 还没完成(运行>*/{if(a[current].creat_time<=a[pre].finish_time>/* 如果进程在上一个进程完成之前创建 */{if(a[j].creat_time<=a[pre].finish_time&&a[j].priority>a[current].priority>current=j。/*找出创建时间在上一个进程完成之前，优先权高的进程*/}else/*如果进程是在上一个进程完成之后创建 */{if(a[j].creat_time<a[current].creat_time>current=j。/*找出比较早创建的一个*/if(a[j].creat_time==a[current].creat_time>/*如果同时创建*/if(a[j].priority>a[current].priority>current=j。/*找出服务时间比较短的一个 */}}}returncurrent。/*返回当前进程*/}voidHRRN(structProa[],intn> // 最高响应比算法{inti。个人资料整理 仅限学习使用intcurrent=0,times=0,pre=0。//当前，次数，前一个a[pre].finish_time=0。for(i=0。i<n。i++>

//初始化优先权和完成时间都为

0{a[i].priority=0

。a[i].finish=0

。}for(times=0。

times<n。

times++>

//开始执行{current=HRN(a,pre,n>。i=current。if(times==0>

// 第一个进程{a[i].excute_time=a[i].creat_time。a[i].finish_time=a[i].excute_time+a[i].serve_time 。a[i].zhou_time=a[i].serve_time。a[i].d_time=1.0。}else{if(a[i].creat_time>a[pre].finish_time>a[i].excute_time=a[i].creat_time。elsea[i].excute_time=a[pre].finish_time 。a[i].finish_time=a[i].excute_time+a[i].serve_time 。a[i].zhou_time=a[i].finish_time-a[i].creat_time 。a[i].d_time=a[i].zhou_time/a[i].serve_time 。}a[i].finish=1。pre=current。printf("\n\n">。printf("HRRN:\n"> 。Display(a,n>。sleep(1>。}s=0,t=0。for(i=0。i<n。i++>{s+=a[i].zhou_time。t+=a[i].d_time。}Pjzhou_time=s/n。Pjd_time=t/n。hs=Pjzhou_time。ht=Pjd_time。printf("\n">。printf("平均周转时间 t=%5.3f\n平均带权周转时间 w=%5.3f\n",Pjzhou_time,Pjd_time> 。printf("\n">。printf("\n">。}intInput(structProa[]>//输入函数{intn,i。个人资料整理 仅限学习使用printf("输入要创建的进程个数 :">。scanf("%d",&n>。printf("输入进程名、开始时间和服务时间 :\n">。getchar(>。for(i=0。i<n。i++>{scanf("%c%f%f",&a[i].name,&a[i].creat_time,&a[i].serve_time> 。getchar(>。a[i].d_time=0。a[i].finish_time=0。}returnn。}voidcompare(> //比较函数{floattemp。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.2f\n",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.2f\n",ft,st,ht> 。}voidDisplay(structProa[],intn>// 显示函数个人资料整理 仅限学习使用{inti。printf("数据输出:\n">。printf("进程名创建时间服务时间开始执