《操作系统》实验报告.doc

操作系统实验报告学 院 计算机学院 专 业 计算机科学与技术 班 级 2009级6班 学 号 姓 名 指导教师 林穗 2012年 12月 计算机 学院 计算机科学与技术 专业 6 班 学号： 姓名： 协作者：_无_ 教师评定： 考勤情况程序运行情况程序质量实验技能创新精神实验报告设计文档实验 一 题目 进程调度第 10 周 星期 五 实验 二 题目 作业调度 第 10 周 星期 五 实验 三 题目 动态分区分配方式的模拟 第 12 周 星期 五 实验 四 题目 文件管理 第 15 周 星期 五 学号： 姓名： 协作者：无 实验一 题目 进程调度 第 10 周 星期 五 1、 实验目的编程模拟进程调度，加深对操作系统中进程调度的理解。2、 实验内容和要求编写并调试一个模拟的进程调度程序，采用“短进程优先”调度算法对五个进程进行调度。以加深对进程的概念及进程调度算法的理解可参考OS实验指导书中“动态优先数”的调度程序源代码。三、实验原理及设计方案1、实验原理短进程优先SPN(Shortest Process Next)的原理是：对预计执行时间短的进程优先分派处理机；优点：比FCFS改善平均周转时间和平均带权周转时间、缩短进程的等待时间、提高系统的吞吐量；缺点：对长进程非常不利，可能长时间得不到执行、未能依据进程的紧迫程度来划分执行的优先级、难以准确估计进程的执行时间，从而影响调度性能。2、设计方案以进程服务时间的长度为标准，建立就绪队列。短进程在前，长进程在后。3、相关数据结构图1 进程控制块PCB 4、主要模块的算法流程图图2 sort()函数 流程图 图3 main()函数 流程图 5、程序清单 #include stdio.h #include #include #definegetpch(type) (type*)malloc(sizeof(type) #define NULL 0 struct pcb /* 定义进程控制块PCB */ char name10; /*进程名字*/char state; /*进程状态，Ready,Wait*/int serviceT; /*服务时间*/int runT; /*运行时间*/int completionT; /*完成时间*/struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB;sort() /*按照进程长度排序*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p-serviceT)serviceT) /*长度最短的进程放于队首*/ p-link=ready; ready=p; else /*比较长度 */ first=ready; second=first-link; while(second!=NULL) if(p-serviceT)serviceT) /*如果长度比当前进程短，*/ p-link=second; /*则将其插入到当前进程的前面*/first-link=p; second=NULL; insert=1; else first=first-link; second=second-link; if(insert=0) /*将最长的进程放在队尾*/ first-link=p; input() /* 建立 PCB*/ int i,num; clrscr(); /*清屏*/ printf(n How many process you want to test? n); scanf(%d,&num); for(i=0;iname); printf(Input the service time: ); scanf(%d,&p-serviceT); p-runT=0;p-completionT=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 Name t State t ServiceTime t RunTime n); printf(|%st,pr-name); printf(|%ct,pr-state); printf(|%dtt,pr-serviceT); printf(|%dt,pr-runT); check() /* 建立进程查看函数 */ PCB* pr; printf(n * The running process is:%s,p-name); /*显示当前运行进程*/ disp(p); pr=ready; printf(n *The ready queue *); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr-link; destroy() /*销毁已执行完的进程*/ printf(nProcess %s is finished!n,p-name); printf(The completion time is :%dn, p-completionT);free(p); running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ printf(nnRunning.);(p-runT)+; if(p-runT=p-serviceT) p-completionT+=p-serviceT;ready-completionT=p-completionT;destroy(); /*调用destroy函数*/ elsep-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); p=ready; ready=p-link; p-link=NULL; p-state=R; check(); running(); printf(n Enter anything to continue.n); ch=getchar(); printf(nn Processes have finished!n); ch=getchar(); 6、 使用说明书1 输入要模拟的进程总数；2 根据提示分别输入每个进程的名字与服务时间；3 每次模拟进程执行前会打印出当前进程队列的状态；4 任意输入一个字符模拟进程运行。四、实验结果及分析1、测试数据进程名ABCD服务时间4352完成时间95142执行顺序D - B - A - C2、运行结果图1 输入图2 执行前 图3 进程d完成图4 进程b完成图5 进程a完成图6 进程c完成2、 实验结果的分析及说明实验正确地模拟了短进程优先调度，执行顺序是D - B - A - C；同时也正确地表现了进程的完成时间。不足之处：没有对进程的到达时间进行模拟，即假设了所有进程都是0时刻到达的；也没有模拟中途进入新进程的情况，即假设了后续没有新进程进入就绪队列。五、调试总结及心得体会通过这次实验，我对操作系统的进程调度有了进一步的理解。短进程调度原理十分浅显易懂，这次实验模拟的是SPN算法核心内容，但若要模拟一个完整的调度过程，待考虑的问题还有很多，比如“到达时间”、“随时可能发生的中断请求”等等。学号： 姓名： 协作者：无 实验二 题目 作业调度 第 10 周 星期 五 1、 实验目的用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。2、 实验内容和要求1 写并调试一个单道处理系统的作业等待模拟程序。2 作业等待算法：分别采用先来先服务（FCFS）、高响应比优先（HRN）的调度算法。 3 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。4 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。5 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。三、实验原理及设计方案1、实验原理（1）先来先服务（FCFS）算法先来先服务作业调度算法即每次调度是从后备作业队列中选择一个最先进入该队列的作业调入内存，分配资源、创建相应的进程，放入进程就绪队列准备运行。FCFS算法利于长作业，不利于短作业，而大多数的作业是I/O繁忙的短作业。（2）响应比高者优先（HRN）的调度算法采用响应比高者优先调度算法，进行调度时必须计算出系统中的所有满足必要条件作业的响应比；从中选择响应比最高的一个作业装入主存储器、分配资源，由于是实验，所以就用将作业的作业控制块出队，并输出作业的作业名代替装入主存储器，同时修改系统的资源数量；用同样方法选择第二个、第三个直到不再有满足必要条件的作业。2、 设计方案采用作业调度算法（采用先来先服务（FCFS）调度算法 最短作业优先算法 响应比高者优先调度算法。）对作业进行排序，运行当前已经到达的最优作业。3、 相关数据结构多道程序系统作业调度中typedef struct JCB/定义作业控制块JCBchar name10;/作业名int stime;/开始运行时刻int rtime;/需要运行时间，即提供服务的时间char state;/作业状态JCB *next;/链指针JCB;JCB *ready=NULL,*p;int T;/时间量int ttime;/总周转时间float trtime;/总的带权周转时间4、主要模块的算法流程图5、程序清单#include stdio.h #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0 int n;/ 要测试的数据组数float total_T=0; / 周转时间总数float total_WT=0; /带权周转时间总数struct jcb char name10; char state; /作业状态Ready,Wait,Finishint ArrivalTime; / 到达时刻（提交时刻）int ServiceTime; / 服务时间int BeginTime;/开始运行时刻int RunningTime;/作业执行时间int FinishTime; / 完成时刻int TurnaroundTime; /周转时间Tfloat WeightTurnaroundTime; /带权周转时间W（W=T/服务时间）struct jcb* link; *ready=NULL,*p; typedef struct jcb JCB;sort() /按照到达时刻排序 JCB *first, *second; int insert=0; if(ready=NULL)|(p-ArrivalTime)ArrivalTime) /最先到达的作业放在队首 p-link=ready; ready=p; else / 比较 first=ready; second=first-link; while(second!=NULL) if(p-ArrivalTime)ArrivalTime) /如果到达时刻早于当前作业， p-link=second; /则将其插入当前作业的前面first-link=p; second=NULL; insert=1; else first=first-link; second=second-link; if(insert=0) / 最后到达的作业放于队尾first-link=p; input() /* 建立 JCB*/ int i; clrscr(); /*清屏*/ printf(nHow many jobs you want to test? n); scanf(%d,&n); for(i=0;iname); printf(Input arrival time: ); scanf(%d,&p-ArrivalTime); printf(Input service time: ); scanf(%d,&p-ServiceTime); printf(n); p-RunningTime=0; /初始化p-BeginTime=0;p-FinishTime=0;p-TurnaroundTime=0;p-WeightTurnaroundTime=0; p-state=W; p-link=NULL; sort(); /* 调用sort()*/ int space() int l=0; JCB* pr=ready; while(pr!=NULL) l+; pr=pr-link; return(l); disp(JCB * pr) /*打印作业运行情况*/ printf(n Name t State t ArrivalTimet ServiceTime t Begin tRuningTime n); printf(|%st,pr-name); printf(|%ct,pr-state); printf(|%dtt,pr-ArrivalTime); printf(|%dtt,pr-ServiceTime); printf(|%dt,pr-BeginTime); printf(|%dt,pr-RunningTime); check() JCB* pr; printf(-Display current state-); disp(p); pr=ready; while(pr!=NULL) disp(pr); pr=pr-link; destroy() /*当某作业完成后，撤销该作业.*/ printf(nJob %s is finished!n,p-name); printf(Finish Time =%dn, p-FinishTime);p-TurnaroundTime=p-FinishTime - p-ArrivalTime; /计算T和Wp-WeightTurnaroundTime=(float)(p-TurnaroundTime) )/ p-ServiceTime;printf(Turn-around Time=%dn,p-TurnaroundTime);printf(Weight Turn-around Time=%.2f n, p-WeightTurnaroundTime);total_T+=p-TurnaroundTime;total_WT+=p-WeightTurnaroundTime;free(p); running() printf(nnRuning.n);(p-RunningTime)+; if(p-RunningTime=p-ServiceTime) p-FinishTime=p-RunningTime+p-BeginTime;ready-BeginTime=p-FinishTime;ready-FinishTime=ready-BeginTime;destroy(); elsep-state=W;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); p=ready; ready=p-link; p-link=NULL; p-state=R; check(); running(); printf(n Enter anything to continue. n); ch=getchar(); printf(nn All Jobs have finished!n); printf(Average Turn-around Time is: %.2fn,total_T/n); /平均周转时间printf(Average Weight Turn-around Time is: %.2fn,total_WT/n); /平均带权周转时间ch=getchar(); ch=getchar(); 4、 实验结果及分析1、 测试数据算法作业（进程）名ABCDE平均到达时间02468服务时间36452FCFS完成时间39131820-周转时间37912128.6带权周转时间11.172.252.462.56执行顺序A - B - C - D - E HRRN完成时间39132015-周转时间3791478带权周转时间11.172.252.83.52.14执行顺序A - B - C - E - D 2、 运行结果1.1 输入1.2 FCFS2、实验结果的分析及说明先来先服务作业调度算法是从作业队列中选择一个先进入该队列的作业2调入内存，分响应比高者优先调度算法，进行调度时必须计算出系统中的所有满足必要条件作业的响应比；从中选择响应比最高的一个作业执行。五、调试总结及心得体会FCFS实现起来简单。只需考虑到达时间。而HRN实现起来较为复杂，特别是在C语言中，对链表的操作显得臃肿，未能想出更优雅的实现方法。在实现HRN过程中，遇到很多困难，最头疼的是对排序问题，因为每执行一次进程，要重新计算就绪队列里面的每一个进程的优先数，并选出最大的，同时要考虑有无新进程进入。这导致了问题的复杂性。6、 思考题:比较各种算法的优缺点。1.先来先服务是最简单的调度算法，按先后顺序进行调度。比较有利于长作业，而不利于短作业。因为长作业会长时间占据处理机。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。 2. 轮转法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。 3. 优先级算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。 4短作业优先是对FCFS算法的改进，其目标是减少平均周转时间。 优点:比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量； 缺点： 对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。 5. 最高响应比优先法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 学号： 姓名： 协作者：无 实验三 题目 动态分区分配方式的模拟 第 12 周 星期 五 1、 实验目的了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解2、 实验内容和要求（1）用C语言分别实现采用“首次适应算法”和“最佳适应算法”的动态分区分配过程和回收过程。其中，空闲分区通过空闲分区链（表）来管理；在进行内存分配时，系统优先使用空闲区低端的空间。（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200KB作业3释放100KB作业1释放130KB作业5申请140KB作业6申请60KB作业7申请50KB作业8申请60KB请分别采用“首次适应算法”和“最佳适应算法”进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。三、实验原理及设计方案1、实验原理主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。2、设计方案主存空间分配：设计作业申请队列，动态输入构造空闲区表，并显打印示构造好的空闲区表。键盘接收内存申请尺寸大小。根据申请，实施内存分配，并返回分配所得内存首址。分配完后，调整空闲区表（即扣除分配部分），并显示调整后的空闲区表。若分配失败，返回分配失败信息。要求每次分配后显示出空闲内存分区表（链）的情况。主存空间回收：当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。此时，相邻空闲区的合并问题，要求考虑四种情况：1）、释放区下邻空闲区（低地址邻接）2）、释放区上邻空闲区（高地址邻接）3）、释放区上下都与空闲区邻接4）、释放区上下都与空闲区不邻接动态输入构造空闲区表，并显示构造好的空闲区表。根据空闲区表，按内存回收的四种情况从键盘接收回收区域的内存首址与大小。回收区域，调整空闲区表（与前面空闲区相连、与后面空闲区相连、与前后空闲区相连则合并、与前后空闲区都不相连则插入该项），并显示调整后的空闲区表。要求每次回收后显示出空闲内存分区表（链）的情况。3、 相关数据结构 struct jcb /* 定义作业控制块JCB */ char name5; int size; /* 定义作业需要的空间 */int address; /*定义作业分配的地址*/int t;struct jcb* link; *ready=NULL,*p;struct biao /* 定义空闲分区表 */int address;int size;struct biao *link;4、 主要模块的算法流程图开始界面3最佳算法4.退出1.首次适应可执行查看分区表情况、调入作业和回收内存等操作可执行查看分区表情况、调入作业和回收内存等操作5、程序清单#include string.h#include stdio.h #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL 0 struct jcb /* 定义作业控制块JCB */ char name5; int size; /* 定义作业需要的空间 */int address; /*定义作业分配的地址*/int t;struct jcb* link; *ready=NULL,*p;struct biao /* 定义空闲分区表 */int address;int size;struct biao *link; *sub=NULL,*q;typedef struct jcb JCB;typedef struct biao BIAO;int choice,h; char na5; void sort() /* 建立基于先来先服务作业排列函数*/ JCB *first, *second; if(ready=NULL) /*插入队首*/ p-link=ready; ready=p; else /* 进程插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) first=first-link; second=second-link; first-link=p; p-link=NULL; void sort2() /* 建立空闲区表函数*/ BIAO *first, *second; int insert=0; if(sub=NULL)|(q-address)address) /*插入链首*/ q-link=sub; sub=q; else /* 空区插入适当的位置中*/ first=sub; second=first-link; while(second!=NULL) if(q-address)address) /*若插入空闲首地址比当前空闲块低*/ /*插入到当前作业前面*/ q-link=second; first-link=q; second=NULL; insert=1; else /* 插入空闲的首地址最高,则插入到队尾*/ first=first-link; second=second-link; if(insert=0) first-link=q; void input() /* 建立作业控制块函数*/ int i,num; printf(n 请输入作业数：); scanf(%d,&num); for(i=0;iname); printf( 请输入所需内存空间(K)：); scanf(%d,&p-size); p-address=0; /*初始地址为0*/ p-t=0; p-link=NULL; sort(); void disp(JCB * pr) /*建立作业显示函数,用于显示当前作业*/ printf(n 作业%s申请空间的情况:,pr-name); printf(n作业名申请空间(K)在内存的首地址n); printf( %s ,pr-name); printf( %d ,pr-size); printf( %d ,pr-address); printf(n); void disp1() /*建立空闲块显示函数*/ BIAO *pr; int i=1; pr=sub; printf(n 显示空闲区表); while(pr!=NULL) printf(n空闲块号空闲块的大小(K)空闲块的首地址n); printf( %d ,i); printf( %d ,pr-size); printf( %d ,pr-address); printf(n); i+; pr=pr-link; void destroy() /*建立作业回收空间函数*/ BIAO *pr,*f; JCB *p1,*p2; p1=p2=ready; while(p1!=NULL) if(strcmp(p1-name,na)=0&p1-t=1) break; p2=p1; p1=p1-link; if(p1!=NULL) printf(n 作业 %s 释放空间情况,p1-name); printf(n*-*作业名*-*释放空间(K)*-*在内存的首地址n); printf( |%s ,p1-name); printf( |%d ,p1-size); printf( |%d ,p1-address); printf(n); pr=sub; while(pr!=NULL) if(pr-address+pr-size=p1-address) break; pr=pr-link; if(pr!=NULL) f=pr-link; if(p1-address+p1-size=f-address) /*前后面都相连*/ pr-link=f-link; pr-size=pr-size+p1-size+f-size; free(f); else /*只和前面相连*/ pr-size=pr-size+p1-size; else pr=sub; while(pr!=NULL) if(p1-address+p1-size=pr-address) break; pr=pr-link; if(pr!=NULL) /*只和后面相连*/ pr-size=pr-size+p1-size; pr-address=p1-address; h=pr-address; else /*前后不相连*/ q=getpch(BIAO); q-size=p1-size; q-address=p1-address; h=q-address; q-link=NULL; sort2(); p2-link=p1-link; free(p1); else printf(n没有找到请求释放的作业或输入的作业名出错); getch(); void check(JCB * p5) /* 建立作业分配空间函数 */ BIAO *pr,*pr1,*pr2; if(choice=1) /*首次适应算法*/ pr=sub; while(pr-sizesize&pr!=NULL) /*查找大小满足的空闲分区*/ pr=pr-link; if(pr!=NULL) p5-address=pr-address; pr-address=p5-address+p5-size; pr-size=pr-size-p5-size; p5-t=1; if(pr-size=0) pr1=sub; while(pr1-link!=pr) pr1=pr1-link; pr1-link=pr-link; free(pr); disp(p5); else printf(n作业长度过大，内存不足，分区分配出错!n); printf(n 按任一键继续.); getch(); if(choice=2) /*最佳适应算法*