广工操作系统实验报告.doc

1、广工操作系统实验报告操作系统实验报告学生学院计算机学院专业班级 2010 级计算机科学与技术四班学 号3110006015 学生姓名张法光指导教师何翠红2013年 1 月 05 日目录实验一、进程调度. 4实验二、作业调度. 8实验三、动态分区分配方式的模拟. 16实验四、文件系统 . 2431 实验一 进程调度1、 实验目的编写并调试一个模拟的进程调度程序，采用“短进程优先”调度算法对五个进程进行调度。以加深对进程的概念及进程调度算法的理解(2、实验原理在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对调度的处理又都可采用不同的调度方式和调度算法。调度算法是指:

2、根据系统的资源分配策略所规定的资源分配算法。短进程优先调度算法是指对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。短进程优先调度源程序如下:#include#define n 5#define num 5#define max 65535typedef struct proint PRO_ID;/进程号int arrive_time;/到达时间int sum_time;/运行总时间int flag;Pro;/ 整数排序int bubble(int temp)int i,j,tem=0;f

3、or(i=1;inum;i+)4int lastX=1;for(j=0;jtempj+1)tem=tempj;tempj=tempj+1;tempj+1=tem;lastX=0;if(lastX=1) break;return temp0;/ 进程排序Pro bubble(Pro p)int i,j;Pro temp=0;Pro snum;for(i=0;inum;i+)si=pi;for(i=1;inum;i+)int lastX=1;for(j=0;jsj+1.sum_time)temp=sj;sj=sj+1;sj+1=temp;lastX=0;if(lastX=1) break;retu

4、rn s0;5void SPF(int p)if(n0)int i,j,k,l,tc=0;Pro seqn;Pro temp_seqn;printf(*n);printf(10计科 4 班 张法光 3110006015n);printf(n);printf(实验一 : 短进程优先调度算法SPFn);printf(请依次输入 5 个进程的进程号、到达时间和执行时间n);printf( 成员变量用逗号隔开 ; 进程间用回车隔开 n); printf(*n);for(i=0;in;i+)scanf(%d,%d,%d,&seqi.PRO_ID,&seqi.arrive_time,&seqi.sum_t

5、ime);printf(调度顺序是 :n);/ 初始化 tc int tempnum; for(i=0;inum;i+)tempi=seqi.arrive_time;tc=bubble(temp);/tc是断点啊/flag表示对应 i 的 pro 的队列情况/-1 表示未进入过队列， 0 表示在队列中， 1 表示被清除了 for(i=0;in;i+)seqi.flag=-1;for(i=0;in;i+)for(j=0;jn;j+)if(seqj.flag!=1&seqj.arrive_time=tc)seqj.flag=0;for(j=0;jn;j+)temp_seqj=seqj;if(seq

6、j.flag!=0)temp_seqj.sum_time=max;6l=bubble(temp_seq).PRO_ID;for(j=0;jn;j+)if(l=seqj.PRO_ID)k=j;tc=tc+bubble(temp_seq).sum_time;seqk.flag=1;printf(%d,l);printf(n);void main()SPF(n);运行结果 :结果分析与实验小结非抢占式的短进程优先调度相对简单，有个易错的地方就是最早来的不管所需服务时间长短均必须先服务，而且数量可能不止一个，此时可以再根据短进程优先法则调度。总的来说，短进程优先调度算法可以照顾到实际上在所有进程中占很

7、大比例的短进程，使它能比长进程优先执行，但不利于长进程的执行。72 实验二 作业调度1、实验目的本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。2、实验内容及要求1、为单道批处理系统设计一个作业调度程序(1) 、编写并调试一个单道处理系统的作业调度模拟程序。(2) 、作业调度算法 : 分别采用先来先服务 (FCFS)、响应比高者优先 (HRN)的调度算法。(3) 、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所

8、占用的 CPU时限等因素。(4) 、每个作业由一个作业控制块 JCB表示， JCB可以包含如下信息 : 作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待 W(Wait) 、运行 R(Run)和完成 F(Finish) 三种状。 态之一。每个作业的最初状态总是等待 W(5) 、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。2、模拟批处理多道操作系统的作业调度(1) 、写并调试一个作业调度模拟程序。(2) 、作业调度算法 : 分别采用先来先服务 (FCFS

9、)和短作业优先调度算法。(3) 、在批处理系统中，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求，所需要的资源是否得到满足。作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理器运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业的要求，那么，作业调度必须按一定的算法在这些作业中作出选择。当作业正常运行完毕或因发生错误非正常终止时，作业进入完成状态，此时，系统将收回该作业所占用的全部资源，并清除有关的J

10、CB。并输出显示作业运行情况及作业输出结果。3、实验设计方案及原理1、编写并调试一个单道处理系统的作业等待模拟程序。假设在单道批处理环境下有四个作业JOB1、 JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务(FCFS)，最短作业优先 (SJF) 、响应比高者优先 (HRN)的调度算法，计算出作业的平均周转时间和带权的平均周转时间 。8对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。4、源程序清单 ( 需附详细的注释 )#include #include

11、#include #define getpch(type) (type*)malloc(sizeof(type)#define null 0int n;float T1=0,T2=0;int times=0;struct jcb /作业控制块char name10; /作业名int reachtime; /作业到达时间int starttime; /作业开始时间int needtime; /作业需要运行的时间float super; /作业的响应比int finishtime; /作业完成时间float cycletime; /作业周转时间float cltime; /作业带权周转时间char

12、 state; /作业状态struct jcb *next; / *ready=NULL,*p,*q;结构体指针typedef struct jcb JCB; void inital() /建立作业控制块队列, 先将其排成先来先服务的模式队列int i;printf(n输入作业数 :);scanf(%d,&n);for(i=0;iname);getch();p-reachtime=i;printf(作业默认到达时间 :%d,i);printf(n输入作业要运行的时间 :);scanf(%d,&p-needtime);p-state=W;9p-next=NULL;if(ready=NULL) r

13、eady=q=p;elseq-next=p;q=p;void output(JCB* q,int j) /*显示所有作业的情况*/JCB *pr=ready;float f=0.0;printf(所有作业的情况: n);/列表显示所有作业的情况if(j=3) printf(作业名 tt到达时间 t所需运行间 t响应比 tt作业状态n);printf(%stt%dtt%dtt%ft%cn, q-name,q-reachtime,q-needtime,q-super,q-state);while(pr) if(pr-supername,pr-reachtime,pr-needtime,f,pr-s

14、tate);else printf(%stt%dtt%dtt%ft%cn, pr-name,pr-reachtime,pr-needtime,pr-super,pr-state);pr = pr-next;else printf( 作业名 tt 到达时间 t 所需运行间 t 作业状态 n); printf(%stt%dtt%dtt%ctn, q-name,q-reachtime,q-needtime,q-state);while(pr) printf(%stt%dtt%dtt%ctn, pr-name,pr-reachtime,pr-needtime,pr-state);pr = pr-nex

15、t;void disp(JCB* q,int m) /显示作业运行后的周转时间及带权周转时间等if(m=3) /显示高响应比算法调度作业后的运行情况 output(q,m);printf(n作业 %s正在运行，估计其运行情况:n,q-name);printf( 开始运行时刻 t 完成时刻 t 周转时间 t 带权周转时间 t 相应比 nn); printf(%dtt%dtt%ft%ft%fn,q-starttime,q-finishtime,q-cycletime,q-cltime,q-super);getch();else /显示先来先服务 , 最短作业优先算法调度后作业的运行情况output

16、(q,m);printf(n 作业 %s正在运行，估计其运行情况 :n,q-name); 10printf( 开始运行时刻 t 完成时刻 t 周转时间 t 带权周转时间 nn); printf(%dtt%dtt%ft%fn,q-starttime,q-finishtime,q-cycletime,q-cltime);getch();void running(JCB *p,int m) / 运行作业if(p=ready) /先将要运行的作业从队列中分离出来ready=p-next;p-next=NULL;elseq=ready;while(q-next!=p) q=q-next;q-next=p

17、-next;p-starttime=times; / 计算作业运行后的完成时间 , 周转时间等等 p-state=R; p-finishtime=p-starttime+p-needtime; p-cycletime=(float)(p-finishtime-p-reachtime); p-cltime=(float)(p-cycletime/p-needtime); T1+=p-cycletime;T2+=p-cltime;disp(p,m); /调用 disp() 函数 , 显示作业运行情况times+=p-needtime;p-state=F;printf(n作业 %s已经完成 !n 请

18、输入任意键继续 .n,p-name);free(p); /释放运行后的作业getch();void super() /计算队列中作业的高响应比JCB *padv;padv=ready;do if(padv-state=W&(padv-reachtime)super=(float)(times-padv-reachtime+padv-needtime)/padv-needtime;padv=padv-next;while(padv!=NULL);void final() /最后打印作业的平均周转时间, 平均带权周转时间float s,t;11t=T1/n;s=T2/n;getch();print

19、f(nn作业已经全部完成!);printf(n%d个作业的平均周转时间是:%f,n,t);printf(n%d个作业的平均带权周转时间是%f:nnn,n,s);void hrn(int m) /高响应比算法JCB *min;int i,iden;system(cls);inital();for(i=0;istate=W&p-reachtimesupermin-super) min=p;p=p-next;while(p!=NULL); running(min,m); /调用running()函数 /forfinal(); /调用running()函数void fcfs(int m) /先来先服务

20、算法int i,iden;system(cls);inital();for(i=0;istate=W&p-reachtimenext;while(p!=NULL&iden) ;if(iden)i-;printf(n没有满足要求的进程, 需等待 );times+;12if(times100)printf(n时间过长);getch();elserunning(p,m); /调用running()函数final(); /调用running()函数void main() /主函数int m;while(1)printf(*);printf(nn 10 计科 4 班 张法光 3110006015n);

21、printf( 实验 2- 作业调度系统 n); printf(1. 先来先服务算法 n);printf(2.响应比高者优先算法 n);printf(3.退出程序 n);printf(*n);printf(选择所要操作 :n);scanf(%d,&m);switch(m)case 1:fcfs(m);getch();times=0;main();break;case 2:hrn(m);getch();times=0;main();break;case 3:exit(0);default:printf(选择错误 , 重新选择 .);getch();system(cls);135、程序运行结果5.

22、1 先来先服务算法145.2 响应比高者优先算法6、结果分析与实验小结参考了几个作业调度的范例，作业调度实践起来并不难，但需要慢慢调试。和同学讨论了设计思路之后就开始做了，虽然有小错误，但是经过反复调试也修正了BUG。153 实验三 动态分区分配方式的模拟1、实验目的 : 了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解2、实验内容 :(1) 用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲分区链 ( 表 ) 来管理 ; 在进行内存分配时，系统优先使用空闲区低端的空间。) 假设初始状态下，可用

23、的内存空间为640KB，并有下列的请求序列 : (2?作业 1 申请 130KB?作业 2 申请 60KB?作业 3 申请 100KB?作业 2 释放 60KB?作业 4 申请 200KB?作业 3 释放 100KB?作业 1 释放 130KB?作业 5 申请 140KB?作业 6 申请 60KB?作业 7 申请 50KB?作业 8 申请 60KB请分别采用首次适应算法和最佳适应算法进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。3、思考 : 讨论各种分配算法的特点。(1) 首次适应算法。使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲

24、分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。(2) 最佳适应算法。该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算

25、法似乎是最 16优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。4、源程序清单 ( 需附详细的注释 )#include #include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为 640KB typedef int Status;typedef struct freearea/定义一个空闲区说明表结构int ID; /分区号

26、long size; /分区大小long address; /分区地址int state; /ElemType;状态/-线性表的双向链表存储结构 -typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next; /后继指针DuLNode,*DuLinkList;DuLinkList block_first; /头结点DuLinkList block_last; /尾结点Status alloc(int);/内存分配Status free(int);

27、 /内存回收Status First_fit(int,int);/首次适应算法Status Best_fit(int,int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的内存空间链表 17block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_l

28、ast-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-data.size=MAX_length;block_last-data.ID=0;block_last-data.state=Free;return OK;/-分配主存-Status alloc(int ch)int ID,request; coutID;coutrequest;if(request0 |request=0)cout 分配大小不合适，请重试endl;return ERROR;if(ch=2) /选择最佳适应算法if(B

29、est_fit(ID,request)=OK) cout分配成功 endl;else cout内存不足，分配失败 endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout分配成功endl;else cout内存不足，分配失败data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/ 有大小恰好合适的空闲块p-data.

30、state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/ 有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;/

31、-最佳适应算法- StatusBest_fit(int ID,int request) int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; / 记录最佳插入位置while(p) /初始化最小空间和最佳位置if(p-data.state=Free &19(p-data.sizerequest | p-dat

32、a.size=request) )q=p;ch=p-data.size-request;break;p=p-next;while(p)if(p-data.state=Free & p-data.size=request)/ 空闲块大小恰好合适p-data.ID=ID;p-data.state=Busy;return OK;break;if(p-data.state=Free & p-data.sizerequest)/空闲块大于分配需求if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/ 更新最佳位置指向p=p-next;if(q=NULL

33、) return ERROR;/ else没有找到空闲块/ 找到了最佳位置并实现分配temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;/-主 存 回 收 -Status free(int ID)20DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if

34、(p-prior-data.state=Free)/p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;与前面的空闲块相连if(p-next-data.state=Free)/p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;break;与后面的空闲块相连p=p-next;return OK;/-显示主存分配情况- void show()cout+n;cout+ 主 存 分 配 情 况 +n; coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout 起始地址 :data.addressendl;cout 分区大小 :data.size KBendl;coutdata.state=Free) cout空 闲e