操作系统实验1.doc

操作系统实验指导书一、多道程序的转换调度（学时2）实现多道程序的转换调度题目要求：（作业调度和进程调度结合在一起）、 作业流信息是从指定文本文件（TXT文件）中读取作业信息：作业号 进入系统时间 估计运行时间 优先级 内存需求量 磁带机需求量 都为整型 、 作业调度算法：1、先来先服务；2、最短作业优先 （二者选一）进程调度算法：1、先来先服务；2、基于优先级的算法（静态优先级）（二者选一） 、 输出：作业序列 格式：作业号 时间间隔 1 800-810 （/* 8：00-8：10 */） 2 810-900 1 900-930 平均周转时间：总的周转时间/作业总数 周转时间就是作业结束时间减去作业进入系统时间 示例：#include #include #include #include #include #define null 0 #define len sizeof(struct jnote) struct jcb int state; int num; int in; int run; int pri; int mem; int tape; job50; struct jnote int id; int in; int start; int run; int end; int pri; int size; int tape; int *maddr; struct jnote *next; ; int rest=4,memory101,*mh=memory,logo=0,fid=0; struct jcb *p=job; struct jnote *jh=null,*rp=null,*jp=null; txt()/*从txt文件中作业流*/ FILE *fp; char pt; int i,space=0,j=0,data100,h,k,count; char str10; for(i=0;i100;i+) datai=-1; for(i=0;i=0&pt=size) return(mp); while(*cp=1) cp+; mp=cp; return(null); zy_div_free(mp,msize,tape,h)/*资源分配与释放*/ int *mp,msize,tape,h; int *cp,i=msize; cp=mp; if(h=1) for(;i0;i-) *cp=1; cp+; rest=rest-tape; return (1); if(h=2) for(;i0;i-) *cp=0;cp+; rest=rest+tape; return (2); selectrp(plogo,time)/*选择当前运行进程*/ int plogo,time; struct jnote *newj; struct jnote *temp; if(jh=null&rp=null) p=job; for(;p-state=0;) p+; zy_div_free(mh,p-mem,p-tape,1); p-state=0; newj=(struct jnote *)malloc(len); rp=newj; rp-id=p-num; rp-in=p-in; rp-start=p-in; rp-run=p-run; rp-end=0; rp-pri=p-pri;rp-size=p-mem; rp-tape=p-tape; rp-maddr=mh; rp-next=null; return (0); else if(jh!=null&rp=null) rp=jh; jh=jh-next; rp-next=null; rp-start=time; if(plogo=2) selectrp(plogo,time); else return (-1); else if(jh!=null&rp!=null) if(plogo=2) if(logo=0) if(jh-prirp-pri) temp=jh; jh=jh-next; temp-next=rp; printf(%d : %d - %d n,rp-id,rp-start,temp-in); rp-run-=time_time(temp-in,rp-start); rp-start=0; rp=temp; rp-start=rp-in; return (0); if(fid=1) if(jh-prirp-pri) temp=jh; jh=jh-next; temp-next=rp; rp=temp; rp-start=time; selectrp(plogo,time); else rp-start=time; return (0); return (0); else rp-start=time; return (0); return (0); WORK(jlogo,plogo,count) int jlogo,plogo,count; int k=count,sum=0,time,t;/*sum是周转时间之和*/ struct jnote *cp,*p1,*newj; int *mp; selectrp(plogo,0); while(k0) p=job; do if(p-state=0) p+; while(p-state=-1&p-num!=-1&(logo=0&p-instart,rp-run)|(logo=1&p-instart,rp-run) mp=m_pd(p-mem); if(rest=p-tape) t=1; else t=0; if(mp!=null&t=1) zy_div_free(mp,p-mem,p-tape,1); p-state=0; newj=(struct jnote *)malloc(len); newj-id=p-num; newj-in=p-in; newj-start=0; newj-run=p-run; newj-end=0; newj-pri=p-pri; newj-size=p-mem; newj-tape=p-tape; newj-maddr=mp; newj-next=null; if(jh=null) jh=newj; jp=jh; else if (jlogo=1) jp-next=newj;jp=newj; /*作业为FCFS*/ else /*作业为最短运行时间优先*/ jp=cp=jh; if(newj-run=jp-run&jp-next!=null) cp=jp; jp=jp-next; else if(newj-runrun) if(cp=jp) newj-next=jp; jh=newj; else cp-next=newj; newj-next=jp; else jp-next=newj; if (plogo=2) selectrp(plogo,0); p+; while(p-state=0); if (logo=0) zy_div_free(rp-maddr,rp-size,rp-tape,2); logo=1; else rp-end=rpend(rp-start,rp-run); /*此时计算结束时间*/ printf(%d : %d - %d n,rp-id,rp-start,rp-end); sum+=time_time(rp-end,rp-in);/*计算周转时间总和*/ if(k-1=0) p1=rp;rp=rp-next;free(p1); break; time=rp-end; p1=rp; rp=rp-next; free(p1); k-; fid=1; selectrp(plogo,time); fid=0; logo=0; printf(The average time : %d n,sum/count); init() int i; for(i=0;jobi.num!=-1;i+) jobi.state=-1; logo=0;fid=0; main() int i,count; count=txt();/*返回作业总数*/ for(i=0;iname=ID; p-ax=a; p-bx=b; p-cx=c; p-dx=d; p-pc=m; p-psw=n; p-precendence=pfree; p-status=aready; if(head=NULL) head=p; else q-next=p; q=p; printf(ninput the next pcb: ); scanf(n%c,&ID); scanf(%d%d%d%d%d%d,&a,&b,&c,&d,&m,&n); if(q!=NULL) q-next=NULL; q=head; while(q) printf(n peocess name. status. precendence .ax. bx. cx. dx. pc. psw.n ); printf(%10c%5d%8d%5d%5d%5d%5d%5d%5d,q-name,q-status,q-precendence,q-ax,q-bx,q-cx,q-dx,q-pc,q-psw); q=q-next; return head;/*createprocess end*/ void processfifo(pcb *head) /*use fifo */ pcb *p; p=head; printf(n the process use fifo method.n); printf(running the frist process:n); while(p!=NULL) p-status=running; printf(nprocess name status. ax. bx. cx. dx. pc. psw.); printf(n%10c%5d%8d%5d%5d%5d%5d%5d,p-name,p-status,p-ax,p-bx,p-cx,p-dx,p-pc,p-psw); /*check process running status */ p-status=0; p=p-next; printf(ncheck weatherfer the process complete: ); p=head; while(p) printf(n%3c%3d,p-name,p-status); p=p-next; printf(ngame is over!n); main() pcb *head; head=NULL; head=createprocess(head); processfifo(head); 三、存储器管理（学时2）模拟存储管理中内存空间的管理和分配内存空间的管理分为固定分区管理方式，可变分区管理方式，页式存储管理，段式存储管理。题目：模拟内存分配与回收示例：#define n 10 /*假定系统允许的最大作业为，假定模拟实验中n值为10*/ #define m 10 /*假定系统允许的空闲区表最大为m，假定模拟实验中m值为10*/ #define minisize 100 struct float address; /*已分分区起始地址*/ float length; /*已分分区长度，单位为字节*/ int flag; /*已分配区表登记栏标志，用0表示空栏目*/ used_tablen; /*已分配区表*/ struct float address; /*空闲区起始地址*/ float length; /*空闲区长度，单位为字节*/ int flag; /*空闲区表登记栏标志，用0表示空栏目，用1表示未分配*/ free_tablem; /*空闲区表*/ allocate(J,xk) char J; float xk; /*采用最优分配算法分配xk大小的空间*/ int i,k; float ad; k=-1; for(i=0;i=xk&free_tablei.flag=1) if(k=-1|free_tablei.lengthfree_tablek.length) k=i; if(k=-1)/*未找到可用空闲区，返回*/ printf(无可用空闲区n); return; /*找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于msize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配*/ if(free_tablek.length-xk=minisize) free_tablek.flag=0; ad=free_tablek.address; xk=free_tablek.length; else free_tablek.length=free_tablek.length-xk; ad=free_tablek.address+free_tablek.length; /*修改已分配区表*/ i=0; while(used_tablei.flag!=0&i=n) /*无表目填写已分分区*/ printf(无表目填写已分分区，错误n); /*修正空闲区表*/ if(free_tablek.flag=0) /*前面找到的是整个空闲分区*/ free_tablek.flag=1; else /*前面找到的是某个空闲分区的一部分*/ free_tablek.length=free_tablek.length+xk; return; else /*修改已分配表*/ used_tablei.address=ad; used_tablei.length=xk; used_tablei.flag=J; return; /*主存分配函数结束*/ reclaim(J) char J; /*回收作业名为J的作业所占主存空间*/ int i,k,j,s,t; float S,L; /*寻找已分配表中对应登记项*/ s=0; while(used_tables.flag!=J|used_tables.flag=0)&s=n)/*在已分配表中找不到名字为J的作业*/ printf(找不到该作业n); return; /*修改已分配表*/ used_tables.flag=0; /*取得归还分区的起始地址S和长度L*/ S=used_tables.address; L=used_tables.length; j=-1;k=-1;i=0; /*寻找回收分区的空闲上下邻，上邻表目k，下邻表目j*/ while(im&(j=-1|k=-1) if(free_tablei.flag=1) if(free_tablei.address+free_tablei.length=S)k=i;/*找到上邻*/ if(free_tablei.address=S+L)j=i;/*找到下邻*/ i+; if(k!=-1) if(j!=-1) /* 上邻空闲区，下邻空闲区，三项合并*/ free_tablek.length=free_tablej.length+free_tablek.length+L; free_tablej.flag=0; else /*上邻空闲区，下邻非空闲区，与上邻合并*/ free_tablek.length=free_tablek.length+L; else if(j!=-1) /*上邻非空闲区，下邻为空闲区，与下邻合并*/ free_tablej.address=S; free_tablej.length=free_tablej.length+L; else /*上下邻均为非空闲区，回收区域直接填入*/ /*在空闲区表中寻找空栏目*/ t=0; while(free_tablet.flag=1&t=m)/*空闲区表满,回收空间失败,将已分配表复原*/ printf(主存空闲表没有空间,回收空间失败n); used_tables.flag=J; return; free_tablet.address=S; free_tablet.length=L; free_tablet.flag=1; return; /*主存回收函数结束*/ main( ) int i,a; float xk; char J; /*空闲分区表初始化：*/ free_table0.address=10240; free_table0.length=102400; free_table0.flag=1; for(i=1;im;i+) free_tablei.flag=0; /*已分配表初始化：*/ for(i=0;in;i+) used_tablei.flag=0; while(1) printf(选择功能项（0-退出,1-分配主存,2-回收主存,3-显示主存）n); printf(选择功项(03) :); scanf(%d,&a); switch(a) case 0: exit(0); /*a=0程序结束*/ case 1: /*a=1分配主存空间*/ printf(输入作业名J和作业所需长度xk: ); scanf(%*c%c%f,&J,&xk); allocate(J,xk);/*分配主存空间*/ break; case 2: /*a=2回收主存空间*/ printf(输入要回收分区的作业名); scanf(%*c%c,&J); reclaim(J);/*回收主存空间*/ break; case 3: /*a=3显示主存情况*/ /*输出空闲区表和已分配表的内容*/ printf(输出空闲区表：n起始地址 分区长度 标志n); for(i=0;im;i+) printf(%6.0f%9.0f%6dn,free_tablei.address,free_tablei.length, free_tablei.flag); printf( 按任意键,输出已分配区表n); getch(); printf( 输出已分配区表：n起始地址 分区长度 标志n); for(i=0;in;i+) if(used_tablei.flag!=0) printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length, used_tablei.flag); else printf(%6.0f%9.0f%6dn,used_tablei.address,used_tablei.length, used_tablei.flag); break; default:printf(没有该选项n); /*case*/ /*while*/ /*主函数结束*/四、虚拟存储器（学时2）虚拟存储管理器的页面调度页面调度算法主要有：FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU），最佳算法（OPT） 题目要求： 实现三种算法：1、先进先出；2、OPT；3、LRU 页面序列从指定的文本文件（TXT文件）中取出 输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数 示例：#include #include #include #define null 0 #define len sizeof(struct page) struct page int num; int tag; struct page *next; ; struct page *create(int n) /*建立分配的内存空间，并初始化，返回头结点*/ int count=1; struct page *p1,*p2,*head; head=p2=p1=(struct page *)malloc(len); p1-tag=-1;p1-num=-1; while(counttag=-1;p1-num=-1; p2-next=p1; p2=p1; p2-next=null; return(head); void FIFO(array,n) int array,n; int *p; struct page *cp,*dp,*head,*new; int count=0; head=create(n); p=array; while(*p!=-1) cp=dp=head; for(;cp-num!=*p&cp-next!=null;) cp=cp-next; if (cp-num=*p) printf( ! ); else count+; cp=head; for(;cp-tag!=-1&cp-next!=null;) cp=cp-next; if(cp-tag=-1) cp-num=*p; cp-tag=0; printf( * ); else new=(struct page*)malloc(len); new-num=*p; new-tag=0; new-next=null; cp-next=new; head=head-next; printf( %d ,dp-num); free(dp); p+; printf(nQueye Zongshu : %d n,count); void LRU(array,n) int array,n; int count=0,*p=array; struct page *head,*cp,*dp,*rp,*new,*endp; head=create(n); while(*p!=-1) cp=dp=rp=endp=head; for(;endp-next!=null;) endp=endp-next; for(;cp-num!=*p&cp-next!=null;) rp=cp;cp=cp-next; if(cp-num=*p) printf( ! ); if(cp-next!=null) if(cp!=head) rp-next=cp-next; else head=head-next; endp-next=cp; cp-next=null; else count+; cp=rp=head; for(;cp-tag!=-1&cp-next!=null;) cp=cp-next; if(cp-tag=-1) printf( * ); cp-num=*p; cp-tag=0; else new=(struct page *)malloc(len); new-num=*p; new-tag=0; new-next=null; cp-next=new; dp=head; head=head-next; printf( %d ,dp-num); free(dp); p+; printf(nQueye Zongshu : %d n,count); OPT(array,n) int array,n; int *p,*q,count=0,i; struct page *head,*cp,*dp,*new; p=array; head=create(n); while(*p!=-1) cp=head; for(;cp-num!=*p&cp-next!=null;) cp=cp-next; if(cp-num!=*p) count+; cp=head; for(;cp-tag!=-1&cp-next!=null;) cp=cp-next; if(cp-tag=-1) printf( * ); cp-num=*p; cp-tag=0; else i=1;q=p;q+;cp=head; while(*q!=-1&inum&cp-next!=null;) cp=cp-next; if(*q=cp-num) cp-tag=1; i+; q+;cp=head; if(i=n) for(;cp-tag!=0;) cp=cp-next; printf( %d ,cp-num); cp-num=*p; else cp=head; for(;cp-tag!=0;) cp=cp-next; if(cp=head) for(;cp-next!=null;) cp=cp-next; new=(struct page *)malloc(len); new-num=*p; new-tag=0; new-next=null; cp-next=new; dp=head; head=head-next; printf( %d ,dp-num); free(dp); else printf( %d ,cp-num); cp-num=*p; cp=head; for(;cp-next!=null;) cp-tag=0;cp=cp-next; cp-tag=0; else printf( ! ); p+; printf(nQueye Zongshu : %d n,count); main() FILE *fp; char pt; char str10; int i,j=0; int page50,space=0; for(i=0;i=0&pt=9) stri=pt;i+; space=0; else if(pt= |pt=n) if(space=1) break; else stri=0; pagej=atoi(str); if(pt=n) break; else space=1; j+; i=0; /*结束*/ if(pt=EOF) stri=0;pagej=atoi(str); i=0; while(pagei!=-1) printf( %d ,pagei);i+; fclose(fp); printf(n); printf( ! : mean no moved n * : mean have free space nn); printf(FIFO ); FIFO(page,3); printf(nLRU ); LRU(page,3); printf(nOPT ); OPT(page,3); 五、文件管理（学时2）磁盘调度题目要求：、 实现三种算法： 1、先来先服务 ；2、最短寻道优先；3、电梯算法、 磁道服务顺序从指定的文本文件（TXT文件）中取出、 输出：第一行：磁道的服务顺序；第二行：显示移动总道数 示例：#include #include #include #define null 0 #define len sizeof(struct cidaohao) struct cidaohao struct cidaohao *pre; int num; struct cidaohao *next; ; FCFS(array) int array50; int i,j,sum=0; printf(nFCFS : ); for(i=1;arrayi!=-1;i+) printf( %d ,arrayi); i=0; for(i=0,j=1;arrayj!=-1;i+,j+) if(arrayiarrayj) sum+=(arrayi-arrayj); else sum+=(arrayj-arrayi); return(sum); SSTF(head,now) struct cidaohao *head; int now; struct cidaohao *p,*lp,*rp; int sum=0,front,behind; p=head; printf(nSSTF :); while(p-num!=now) p=p-next;/*确定now在连表中的位置*/ lp=p-pre; rp=p-next; do if(p-next!=null&p-pre!=null) front=p-num-lp-num; behind=rp-num-p-num; if(front=behind) sum+=behind; p=rp; printf( %d ,p-num); rp=p-next; else sum+=front; p=lp; printf( %d ,p-num); lp=p-pre; else if(p-next=null) while(lp-num!=0) sum+=p-num-lp-num; p=lp; printf( %d ,p-num); lp=p-pre; return(sum); if(p-pre=null) while(rp-