自考操作系统上机.docVIP

北京自考吧(ZIKAOBA.COM) 北大操作系统（本）上机考试题总结（完整版） 布丁整理一、 进程调度 进程调度算法有FIFO，优先数调度算法，时间片轮转调度算法，分级调度算法，目前主要是考FIFO和优先数调度算法（静态优先级）。 进程调度算法的数据结构主要有：进程 函数定义：建立进程函数，进程调度函数 一个网友做的一个FIFO调度算法的示例： #include stdio.h #define max 100 #define pfree 0 /*process end*/ #define running 1 /*process running status*/ #define aready 2 /*process aready status */ #define blocking 3 /*process aready blocking status*/ typedef struct node char name; int status; int precendence; int ax,bx,cx,dx; int pc; int psw; struct node *next; /*pcb define*/ pcb; pcb *createprocess(pcb *head) pcb *p,*q; int a,b,c,d,m,n; char ID; int s; q=NULL; printf(ninput the first seven status pcb:); scanf(n%c,&ID); scanf(%d%d%d%d%d%d,&a,&b,&c,&d,&m,&n); while(ID!=*) p=(pcb*)malloc(sizeof(pcb); p-name=ID; p-ax=a; p-bx=b; p-cx=c; p-dx=d; p-pc=m; p-psw=n; p-precendence=pre; 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.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); .二、 模拟存储管理中内存空间的管理和分配 内存空间的管理分为固定分区管理方式，可变分区管理方式，页式存储管理，段式存储管理。下面是页式存储管理和可变分区管理的两个例子： 如2002（？）的北京大学主考的上机试题： 内存被划分成2048块（页）。用32位字长的字存放位示图，为0的位表示该块尚未分配，为1的位表示该块已分配。 实习检查： 1、运行程序，由检查教师给出文件名，该文件中存有内存目前状况的位示图的数据（0和1的文件）。（程序应做提示，界面友好）。 2、你所编制的程序应读入数据，存放在相应的数据结构中。 3、显示友好的用户界面，由检查教师输入内存申请（总块数）。 4、根据申请和位示图状态，为用户分配内存，并建立页表。 5、输出位示图和页表。 我这个题目编了一个，但是还没有输进去，相信大家都能做出来。 数据结构：用一个数组来表示内存状况，页表。 函数定义：内存申请函数 以下是论坛上网友提供的另一道模拟内存分配与回收的试题的答案，具体试题不知道是什么： #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*/ /*主函数结束*/三、 虚拟存储管理器的页面调度 页面调度算法主要有：FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU），最佳算法（OPT） 这几种算法的调度都有可能在考试中碰到。 关于这一类型，大家还可以参看书本251页的实验指导。 如2001年考题： 要求： 1。实现三种算法： 1。先进先出 2。 OPT 3。 LRU 2。页面序列从指定的文本文件（TXT文件）中取出 3。输出： 第一行：每次淘汰的页面号 第二行：显示缺页的总次数 以下是网友做的答案： #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); 四、 文件管理 文件管理的试题比较多，主要就是模拟*作系统中的 建立文件、打开文件、读文件、写文件、关闭文件、 、删除文件、建立目录、显示目录内容、显示文件内容、改变文件属性等*作。大家可以参考书本253页的上机指导。 北大2001年试题： 建立一个树型文件目录 假设程序启动运行后在根目录下且根目录为空。 实习检查： 1、运行程序，由检查教师给出文件名，该文件中存有相应的若干命令。（程序应做提示，界面友好）。 2、要求实现两个命令： mkdir 目录名（目录已存在，应给出错误信息。） cd 目录名（目录不存在，应给出错误信息。） 3、你所编制的程序应读入文件，并执行其中的每一条命令。 4、在屏幕上显示文件目录的结构。（界面自己设计，但要清晰明了。） 2002年北京大学的试题： *作系统上机考试题 *作系统上机考试题 题目：模拟文件系统 要求：模拟一个文件系统，包括目录文件，普通文件，并实现对它们的一些 基本*作。 假定每个目录文件最多只能占用一个块；一个目录项包括文件名（下一级目录 名），文件类型，文件长度，指向文件内容（下一级目录）的指针内容。普通文件可以 只用目录项（FCB）代表。（详细的数据结构见后面的说明） 程序功能方面的要求： 需要实现一个命令行*作界面，包含如下命令： 1 改变目录 格式：CD目录名 功能：工作目录转移到指定的目录下，只要求完成改变到当前目录的某一个子目录 下的功能，不要求实现相对目录以及绝对目录。 2 创建文件 格式：CREATE文件名文件长度 功能：创立一个指定名字的新文件，即在目录中增加一项，不考虑文件内容，但必 须能输入文件长度。 3 删除文件 格式：DEL希望删除的文件名 功能：删除指定的文件 4 显示目录 格式：LSALL 功能：显示全部目录以及文件，输出时要求先输出接近根的目录，再输出子目录。 图示如图。 5 创建目录 格式：MD目录名 功能：在当前路径下创建指定的目录 6 删除目录 格式：RD目录名 功能：删除当前目录下的指定目录，如果该目录为空，则可删除，否则应提示是否 作删除，删除*作将该目录下的全部文件和子目录都删除。 对于上述功能要求，完成1-4为及格，完成1-5为良，完成1-6为优。 程序实现方面的要求： 1 对于重名（创建时），文件不存在（删除时），目录不存在（改变目录时）等错误* 作情况，程序应该作出相应处理并给出错误信息，但是程序不得因此而退出。 2 界面友好，程序强壮。 3 界面的提示符为#，提示的命令以及调试的方法应和前面的要求一致。不要自己设计命 令或者附加不要求的功能。 4 在考卷的说明部分（背面）有一段程序的源代码以及对源代码的说明，考试的编码应 在这个程序的基础上修改而成。这段源代码中规定了文件系统使用的数据结构和需要实 现的函数框架，请将你的实现代码填写到合适的位置中去，可以自己添加辅助数据结构、 变量、常量以及函数，但是不得改变已有的代码（如数据结构的定义以及函数的名称以 及参数说明）。 5 考试提交的源程序请命名为filesys.c。 6 程序设计环境使用TC2.0，在DOS*作系统下完成全部程序代码。 初始化程序代码： #include stdio.h #include string.h #include malloc.h struct NomalFile char name50; /*file name*/ int type; /*0-directory file,1-common file*/ int size; /*file size*/; struct DirectoryNode int tag; /*0-dump node,1-real node*/ char name50; int type; /*0-directory file 1-comman file*/ union struct NomalFile *p_nomFile; /*point to comman file */ struct DirectoryFile *p_dirFile; /*point to dirctory file*/ p_File; /*look on initializing code*/ ; struct DirectoryFile /*directory file composed by a node array*/ /*nodes*/ struct DirectoryNode nodesArray10; ; /*initializing file system*/ void init() int i,j; struct DirectoryFile root; struct NomalFile * newNomFile; struct DirectoryNode * newNode; struct DirectoryFile * newDirFile; struct DirectoryFile * curDirFile; for (i=0;i10;i+) /*initial a directory*/ root.nodesArrayi.tag=0; newDirFile=(struct DirectoryFile*) malloc(1100); for (i=0;inodesArrayi.tag=0; root.nodesArray0.tag=1; strcpy(root.nodesA,A); root.nodesArray0.type=0; root.nodesArray0.p_File.p_dirFile=newDirFile; newDirFile=(struct DirectoryFile*)malloc(1100); for(i=0;inodesArrayi.tag=0; root.nodesArray1.tag=1; strcpy(root.nodesA,B); root.nodesArray1.type=0; root.nodesArray1.p_File.p_dirFile=newDirFile; newDirFile=(struct DirectoryFile*)malloc(1100); for(i=0;inodesArrayi.tag=0; root.nodesArray2.tag=1; strcpy(root.nodesA,C); root.nodesArray2.type=0; root.nodesArray2.p_File.p_dirFile=newDirFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F1); (*newNomFile).type=1; (*newNomFile).size=500; printf(%sn,(*newNomFile).name); root.nodesArray3.tag=1; strcpy(root.nodesA,(*newNomFile).name); root.nodesArray3.type=(*newNomFile).type; root.nodesArray3.p_File.p_nomFile=newNomFile; newNomFile=(struct NomalFile *)malloc(108); strcpy(*newNomFile).name,F2); (*newNomFile).type=1; (*newNomFile).size=50; printf(%sn,(*newNomFile).name); root.nodesArray4.tag=1; strcpy(root.nodesA,(*newNomFile).name); root.nodesArray4.type=(*newNomFile).type; root.nodesArray4.p_File.p_nomFile=newNomFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F3); (*newNomFile).type=1; (*newNomFile).size=5; printf(%sn,(*newNomFile).name); root.nodesArray5.tag=1; strcpy(root.nodesA,(*newNomFile).name); root.nodesArray5.type=(*newNomFile).type; root.nodesArray5.p_File.p_nomFile=newNomFile; curDirFile=root.nodesArray1.p_File.p_dirFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F4); (*newNomFile).type=1; (*newNomFile).size=123; printf(%sn,(*newNomFile).name); curDirFile-nodesArray0.tag=1; strcpy(curDirFile-nodesA,(*newNomFile).name); curDirFile-nodesArray0.type=(*newNomFile).type; curDirFile-nodesArray0.p_File.p_nomFile=newNomFile; printf(%sn,curDirFile-nodesArray0.p_File.p_nomFile-name); curDirFile=root.nodesArray2.p_File.p_dirFile; newDirFile=(struct DirectoryFile*)malloc(1100); for(i=0;inodesArrayi.tag=0; curDirFile-nodesArray0.tag=1;strcpy(curDirFile-nodesA,D); curDirFile-nodesArray0.type=0; curDirFile-nodesArray0.p_File.p_dirFile=newDirFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F5); (*newNomFile).type=1; (*newNomFile).size=321; printf(%sn,(*newNomFile).name); curDirFile-nodesArray1.tag=1; strcpy(curDirFile-nodesA,(*newNomFile).name); curDirFile-nodesArray1.type=(*newNomFile).type; curDirFile-nodesArray1.p_File.p_nomFile=newNomFile; curDirFile=curDirFile-nodesArray0.p_File.p_dirFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F6); (*newNomFile).type=1; (*newNomFile).size=10; printf(%sn,(*newNomFile).name); curDirFile-nodesArray0.tag=1; strcpy(curDirFile-nodesA,(*newNomFile).name); curDirFile-nodesArray0.type=(*newNomFile).type; curDirFile-nodesArray0.p_File.p_nomFile=newNomFile; newNomFile=(struct NomalFile*)malloc(108); strcpy(*newNomFile).name,F7); (*newNomFile).type=1; (*newNomFile).size=70; printf(%sn,(*newNomFile).name); curDirFile-nodesArray1.tag=1; strcpy(curDirFile-nodesA,(*newNomFile).name); curDirFile-nodesArray1.type=(*newNomFile).type; curDirFile-nodesArray1.p_File.p_nomFile=newNomFile; int cd(char *str)return 0; /*change current dirctory */ int create(char *str,int num)return 0; /*create file*/ int delete(char *str)return 0; /*delete file*/ void lsall() /*display all directory files*/ int md(char *str)return 0; /*create dirctory*/ int rd(char *str)return 0; /* delete dirctory*/ void main() 五、 磁盘调度 2001年的试题 磁盘调度算法 要求： 1。实现三种算法： 1。先来先服务 2。最短寻道优先（老师会给当前磁头的位置） 3。电梯算法 2。磁道服务顺序从指定的文本文件（TXT文件）中取出 3。输出： 第一行：磁道的服务顺序 第二行：显示移动总道数 参考题目：书 P130 以下是网友的答案： #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,