广工操作系统试验报告广东工业大学13级2016年用.docx

实 验 报 告 课程名称_操作系统实验_ 学生学院_计算机学院_专业班级 计算机科学与技术一班学 号_xxxxxxxxxx_ 学生姓名_xxxx_ _ 指导教师 孙为军_2015 年 12 月 30 日实验一 进程调度一、实验目的 编写并调试一个模拟的进程调度程序，以加深对进程的概念及进程调度算法的理解二、实验内容1. 采用“短进程优先”调度算法对五个进程进行调度。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。 2. 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。在文档最后我添加了一些个人的总结和心得，应该会对大家有些帮助请注意看，另外本实验的代码已经被我上传至CSDN网站上，需要参考的同学请去搜索。三、实现思路在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对调度的处理又都可采用不同的调度方式和调度算法。调度算法是指：根据系统的资源分配策略所规定的资源分配算法。短进程优先调度算法是指对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。四、主要的数据结构#include stdio.h #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL0struct pcb /* 定义进程控制块PCB */ char name10; /进程名 char state; /状态 int super; /优先数 int ntime; /需要运行时间 int rtime; /运行时间 struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB; int num;sort() /* 建立对进程进行短进程优先排列函数*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p-ntime)ntime) /*需要运行时间最小者,插入队首*/ p-link=ready; ready=p; else /* 进程比较需要运行时间,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-ntime)ntime) /*若插入进程比当前进程需要运行时间小,*/ /*插入到当前进程前面*/ p-link=second; first-link=p; second=NULL; insert=1; else /* 插入进程需要运行时间最大,则插入到队尾*/ first=first-link; second=second-link; if(insert=0) first-link=p; void input() /* 建立进程控制块函数*/ int i; /clrscr(); /*清屏*/ printf(n 请输入进程数:); scanf(%d,&num); for(i=0;iname); printf(n 输入进程需要运行时间:); scanf(%d,&p-ntime);printf(n);p-rtime=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 qname t state t ndtime t runtime n); /t super printf(|%st,pr-name); printf(|%ct,pr-state); printf(|%dt,pr-ntime); printf(|%dt,pr-rtime); printf(n); check() /* 建立进程查看函数 */ PCB* pr; printf(n * 当前正在运行的进程是:%s,p-name); /*显示当前运行进程*/ disp(p); pr=ready; printf(n *当前就绪队列状态为:n); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr-link; destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ printf(n 进程 %s 已完成.n,p-name); free(p); running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ (p-rtime)+; if(p-rtime=p-ntime) destroy(); /* 调用destroy函数*/ else p-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 按任一键继续.); ch=getchar(); printf(nn 进程已经完成.n); ch=getchar(); 五、算法流程图六、运行与测试七、改进的方向可以调整为自动进行不用每次都按ENTER键来模拟CPU加1。实验二 作业调度一、 实验目的 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。二、 实验内容1 写并调试一个单道处理系统的作业等待模拟程序。2 作业等待算法：分别采用先来先服务（FCFS）、响应比高者优先（HRN）的调度算法。 3 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。4 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。5 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。三、实现思路作业调度从系统已接纳的暂存在输入井中的一批作业中挑选出1个可运行的作业，并为这个被选中的作业分配所需的系统资源。对被选中运行的作业必须按照它们各自的作业说明书规定的步骤进行控制。 采用先来先服务算法算法模拟设计作业调度程序。 （1）、作业调度程序负责从输入井选择1个作业进入主存，为它分配必要的资源，占用处理器运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业的要求，那么，作业调度必须按一定的算法在这些作业中作出选择。先来先服务算法是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业。 四、主要的数据结构#include stdio.h #include #include #define getpch(type) (type*)malloc(sizeof(type) #define NULL0struct pcb /* 定义进程控制块PCB */ char name10; /进程名 char state; /状态 int super; /优先数 int ntime; /需要运行时间 int rtime; /运行时间 int ctime; /提交时间 int stime; /开始时间 int ftime; /完成时间 int ttime; /周转时间 float dtime; /带权周转时间 struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB; int num;void sort() /* 建立对进程先来先服务排列函数*/ PCB *first, *second; int insert=0; if(ready=NULL)|(p-ctime)ctime) /*达到时间最小者,插入队首*/ p-link=ready; ready=p; else /* 进程比较到达时间,插入适当的位置中*/ first=ready; second=first-link; while(second!=NULL) if(p-ctime)ctime) /*若插入进程比当前进程到达时间小,*/ /*插入到当前进程前面*/ p-link=second; first-link=p; second=NULL; insert=1; else /* 插入进程到达时间最大,则插入到队尾*/ first=first-link; second=second-link; if(insert=0) first-link=p; void input() /* 建立进程控制块函数*/ int i; /clrscr(); /*清屏*/ printf(n 请输入进程数:); scanf(%d,&num); for(i=0;iname); printf(n 输入提交时间:); scanf(%d,&p-ctime); printf(n 输入进程需要运行时间:); scanf(%d,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort(); /* 调用sort函数*/ void main() /*主函数*/ PCB *first,*second; int i,x,y; float s1=0,s2=0; char ch; input(); ch=getchar(); /输出 printf(进程名t 开始时间t 完成时间t 周转时间t 带权周转时间n); second=ready; first=ready; first-ftime=0; for(i=num;i0;i-) if(second-ctimefirst-ftime) /*计算完成时间，周转时间等*/ second-stime=second-ctime; else second-stime=first-ftime; second-ftime=(second-ntime)+(second-stime); second-ttime=(second-ftime)-(second-ctime); x=second-ttime; y=second-ntime; second-dtime=(float)x/(float)y; printf( %s t %d t %d t %d t %f n,second-name,second-stime,second-ftime,second-ttime,second-dtime); s1=s1+second-ttime; s2=s2+second-dtime; if(second-link!=NULL) first=second; second=second-link; s1=s1/num; s2=s2/num; printf(n平均周转时间=%fn,s1); printf(平均周转时间=%fnn,s2); printf(按任意键结束); ch=getchar(); /响应比#include #include #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 ctime; /作业到达时间 int stime; /作业开始时间 int ntime; /作业需要运行的时间 float super; /作业的响应比 int ftime; /作业完成时间 float ttime; /作业周转时间 float dtime; /作业带权周转时间 char 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); printf(n输入作业到达时间:); scanf(%d,&p-ctime); printf(n输入作业需要运行的时间:); scanf(%d,&p-ntime); p-state=W; p-next=NULL; if(ready=NULL) ready=q=p; else q-next=p; q=p; void output(JCB* q) /*显示所有作业的情况*/ JCB *pr=ready;float f=0.0; printf(所有作业的情况：n);/列表显示所有作业的情况 printf(作业名tt到达时间t所需运行间t响应比tt作业状态n); printf(%stt%dtt%dtt%ft%cn, q-name,q-ctime,q-ntime,q-super,q-state); while(pr) if(pr-supername,pr-ctime,pr-ntime,f,pr-state); else printf(%stt%dtt%dtt%ft%cn, pr-name,pr-ctime,pr-ntime,pr-super,pr-state); pr = pr-next; void disp(JCB* q) /显示作业运行后的周转时间及带权周转时间等 /显示高响应比算法调度作业后的运行情况 output(q); printf(n作业%s正在运行，估计其运行情况：n,q-name); printf(开始运行时刻t完成时刻t周转时间t带权周转时间t相应比nn); printf(%dtt%dtt%ft%ft%fn,q-stime,q-ftime,q-ttime,q-dtime,q-super); getchar(); void running(JCB *p) /运行作业 if(p=ready) /先将要运行的作业从队列中分离出来 ready=p-next; p-next=NULL; else q=ready; while(q-next!=p) q=q-next; q-next=p-next; p-stime=times; /计算作业运行后的完成时间,周转时间等等 p-state=R; p-ftime=p-stime+p-ntime; p-ttime=(float)(p-ftime-p-ctime); p-dtime=(float)(p-ttime/p-ntime); T1+=p-ttime; T2+=p-dtime; disp(p); /调用disp()函数,显示作业运行情况 times+=p-ntime; p-state=F; printf(n作业%s已经完成!n请输入任意键继续.n,p-name); free(p); /释放运行后的作业 getchar();void super() /计算队列中作业的高响应比 JCB *padv; padv=ready;do if(padv-state=W&(padv-ctime)super=(float)(times-padv-ctime+padv-ntime)/padv-ntime; padv=padv-next; while(padv!=NULL);void final() /最后打印作业的平均周转时间,平均带权周转时间 float s,t; t=T1/n; s=T2/n; getchar(); printf(nn作业已经全部完成!); printf(n%d个作业的平均周转时间是：%f,n,t); printf(n%d个作业的平均带权周转时间是%f：nnn,n,s); void hrn() /高响应比算法 JCB *min; int i,iden; system(cls); inital(); for(i=0;istate=W&p-ctimesupermin-super) min=p; p=p-next; while(p!=NULL);running(min); /调用running()函数 final(); /调用running()函数void main() /主函数 hrn(); getchar(); printf(按回车结束n); getchar(); 五、算法流程图六、运行与测试1）响应比七、改进的方向实验三 动态分区分配方式的模拟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 请分别采用首次适应算法和最佳适应算法进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。三、实现思路首次适应算法:使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。最佳适应算法:该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。四、主要的数据结构#include #include stdio.h #include #include #define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为KBtypedef int Status; typedef struct freearea/定义一个空闲区说明表结构int ID; /分区号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); /内存回收Status First_fit(int,int);/首次适应算法Status Best_fit(int,int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表 Status Initblock()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-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(char ch)int ID=0,request=0;printf(请输入作业(分区号)：); scanf(%d,&ID);printf(请输入需要分配的主存大小(单位:KB)：); scanf(%d,&request);if(requestdata.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.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;/- 最佳适应算法 -Status Best_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 &(p-data.sizerequest | p-data.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) 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)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(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.sta