操作系统试卷2006-2007答案.doc

河北大学课程考核参考答案及评分标准（2006 2007学年第一学期）考核科目 操作系统 课程类别 必修课 考核方式 闭卷 卷别 A 一、选择题：（共15分，每小题1分）目的：考查学生对操作系统基本原理的掌握；满分值：15分；答案：CCBACCCAADABBCB（或者BC）评分标准：每小题1分二、填空题：（共15分，每小题1分）目的：考查学生对操作系统基本原理的掌握；满分值：15分；答案：1、文件控制块 2、命令接口 程序接口 （或者程序接口 命令接口）3、操作系统内核 核心态 4、应用程序 物理设备 5、 临界资源 程序段 6、共享文件 7、系统调用 8、撤销进程 剥夺资源 （或者 剥夺资源 撤销进程）9、块一致性检查 文件的一致性检查（或者文件的一致性检查 块一致性检查）评分标准：每小题1分三、选择题问答和计算题：（共35分）1. 目的：考查学生对设备分配的掌握；满分值：4分；答案：设备分配策略与下列因素有关：（1）I/O设备的固有属性，对于独占设备，共享设备、虚拟设备等具有不同属性的设备，通常采用相应的分配算法。（2）设备分配算法，常见的有先来先服务算法、优先级高者优先算法（3）设备分配的安全性，即避免死锁的产生。（4）设备独立性，设备独立性指应用程序独立于具体使用的物理设备。评分标准：共4个要点，每个要点1分2、目的：考查学生对文件的索引结构的掌握；满分值：6分；答案：66054KB 解题步骤及其评分标准：直接地址可用的磁盘空间为1KB66KB（1分）；1级索引项可用的磁盘空间为1KB2562=512KB（2分）；2级索引项可用的磁盘空间为1KB256256=64MB（2分）；求和：6KB+512KB+64MB=66054KB3、目的：考查学生对文件的物理结构和目录的掌握；满分值：6分；答案：连续文件：第一个磁盘块的块号和文件长度；链接文件：第一个磁盘块的块号索引文件：索引盘块号。评分标准：共3个要点，每个要点2分4、目的：考查学生对页式存储管理的地址转化的掌握；满分值：6分；答案：内存空间大小为1MB；每块的大小为1KB；每个作业最大长度为64KB; 逻辑地址0420H对应的物理地址是1C20H.评分标准：前三问无步骤，每问1份；第四问2分，解题步骤及其评分标准：逻辑地址0420H对应的页号为1，主存块号为7，页内地址20H（1分），得到物理地址1C20H（1分）。5、目的：考查学生对缺页中断机构的掌握；满分值：4分；答案：缺页中断与一般中断的主要区别： 在指令执行期间产生和处理中断信号。一条指令在执行期间，可能产生多次缺页中断。评分标准：共2个要点，每个要点2分6、目的：考查学生对进程状态及其转换的掌握；满分值：6分；答案：进程的三种基本状态：就绪状态执行状态阻塞状态发生等待事件运行态阻塞态就绪态进程调度 落选等待事件结束评分标准：基本状态2分，进城转换图4分7、目的：考查学生对作业调度算法的掌握；满分值：4分；答案：10：0060分钟10：2511:10120分钟10：0010：2570分钟评分标准：无步骤，每问0.5分四、写算法：（35分）1、目的：考查学生对同步问题的掌握；满分值：17分；答案：semaphore mutexP=1,mutexC=1,empty=n,full=0;item buffern;int in=out=0;void producer() while (1) 输入一个数据放入x中; wait(empty); wait(mutexP); bufferin=x; in=(in+1) mod n; signal(mutexP); signal(full); void consumer()while (1) wait(full); wait(mutexC); y=bufferout; out=(out+1) mod n; signal(mutexC); signal(empty); 输出y中的数据; main()cobegin producer();consumer();评分标准：信号量定义5分，生产者进程6分，消费者进程6分2、目的：考查学生对死锁避免的掌握；满分值：18分；答案：方法多种，下面仅是一种（银行家算法）testsafety( )/* 检测系统是否安全，若安全返回true，不安全返回false*/ int workn; int finishm; int i,k; work = available;/*finishi表示进程i能否执行完，能执行完为true，否则false*/ for(i=0;im;i+)finishi=false; k=0；i=0; while(k=needi&finishi=false) work=work+allocationi; finishi=true; k=0 i=(i+1)%m;k+; flag=true; /*检测是否有进程没有执行完，若有flag为false*/ for(i=0;im&flag;i+) if(finishi=false)flag=false;return(flag);banker_allocation(int requestn,int i)/*银行家分配算法,分配成功返回true,不成功返回false*/if(!(request=needi)return(false);if(!(request=available)return(false);availble=available-request;allocaitioni=allocaioni+request;needi=needi-request;if(testsatefy( )return(true);else availble=available+request; allocaitioni=allocaioni-request; needi=needi+request; return(false); 评分标准：数据结构定义4分，安全检测算法9分，资源分配算法5分河北大学课程考核参考答案及评分标准（2006 2007学年第一学期）考核科目 操作系统 课程类别 必修课 考核方式 闭卷 卷别 B 一、选择题：（共15分，每小题1分）目的：考查学生对操作系统基本原理的掌握；满分值：15分；答案：CBBCDBCBCCDCCBD评分标准：每小题1分二、填空题：（共15分，每小题1分）目的：考查学生对操作系统基本原理的掌握；满分值：15分；答案：1、进程控制块 程序 数据（顺序可以颠倒）2、消息通信管道通信（顺序可以颠倒）3、资源拥有 调度和分派4、人为因素系统因素5、命令接口程序接口（顺序可以颠倒）6、竞争资源进程推进顺序不当（顺序可以颠倒）7、主存 外设（顺序可以颠倒）评分标准：每小题1分三、问答和计算题：（共35分）1、目的：考查学生对设备分配过程的掌握；满分值：3分；答案：可按下述步骤进行设备分配： 分配设备。分配控制器。分配通道。评分标准：共3个要点，每个要点1分2、目的：考查学生对磁盘驱动调度的掌握；满分值：6分；答案：“电梯调度”与“最短寻找时间优先”都是要尽量减少移动臂移动时所花的时间；不同的是“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的那个柱面的访问者，这种选择可能导致移动臂来回改变移动方向；“电梯调度”是沿着臂的移动方向去选择离当前读写磁头最近的那个柱面的访问者，仅当沿臂移动方向无等待访问者时才改变臂的移动方向；由于移动臂改变方向是机械动作，速度相对较谩。相比之下，电梯调度算法是一种简单、实用且高效的调度算法。但是，在实现时除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向。评分标准：共3个要点，每个要点1分3、目的：考查学生页表的掌握；满分值：4分；答案：在分页虚拟存储管理时使用的页表，最少包括以下内容：物理块号、状态位、修改位、外存地址。评分标准：共4个要点，每个要点1分4、目的：考查学生页面置换算法的掌握；满分值：5分；答案：方案多个，下面仅是其一：为了实现LRU，必须在主存维护一张作业所有页的链表，表中各项按访问时间先后排序，最近访问的页排在表头，最久末用的页排在表尾，这就是所谓的栈式算法。每当要置换一页时，必须对链表中的各项进行修改。若被访问的页在主存，则将其移到表头，调整相应项。若不在主存，则将新调的页放表头，其它项依次后移，将表尾一项挤掉。评分标准：数据结构2分，操作方法3分5、目的：考查学生对作业调度算法的掌握；满分值：4分；答案：10：00120分钟11：2512:10180分钟11：0011：25130分钟评分标准：无步骤，每问0.5分6、目的：考查学生对进程创建的掌握；满分值：6分；答案：引起进程创建的典型事件有分时系统中的用户登录、批处理系统中的作业调度、系统提供服务、应用进程本身的应用请求等。创建进程：申请空白PCB。为新进程分配资源。初始化进程控制块。将新进程插入就绪队列。评分标准：引起进程创建的典型事件共4个要点，每个要点0.5分，创建进程共4个要点，每个要点1分。7、目的：考查学生对死锁概念及避免的掌握；满分值：7分；答案：假设系统中有x个进程的进程，则资源至少要有mx+1个，由于系统资源有mn+1个，则可列出不等式：mx+1mn+1解不等式，得到xn，所以系统允许同时执行的最大进程数为n。证明：假设在系统允许同时执行的最大进程数为n时，仍然出现了死锁，此时应该存在一组进程进程都在等待资源，而且系统已无资源可用。则此时该组进程最多n个，每个进程没有执行完时最多占用m个资源，所以现在系统分配出去的资源最多mn，少于系统资源mn+1，所以不可能有死所出现。因此，系统允许同时执行的最大进程数为n时系统不会有死锁发生评分标准：求进程数4分，证明3分四、目的：考查学生对同步问题的掌握；满分值：18分；答案：Semaphore S1=1,S2=1,Sab=1; int ab=ba=0; void Pab () while(1) wait(S1);if(ab=0) wait(Sab);ab=ab+1;signal(S1); 车辆从a点驶向b点; wait(S1); ab=ab-1; if(ab=0)signal(Sab); signal(S1); void Pba ()while(1) wait(S2); if(ba=0)wait(Sab); ba=ba+1; signal(S2); 车辆从b点驶向a点; wait(S2); ba=ba-1; if(ba=0)signal(Sab); signal(S2); main()cobeginPab ();Pba ();评分标准：信号量定义6分，a到b管理进程6分，b到a管理进程6分五、目的：考查学生对磁盘空间管理方法的掌握；满分值：17分；答案：方法多种，下面仅是一种空闲块的组织：把每100个空闲块作为一组，每一组的第一个空闲块中登记下一组空闲块的块号和空闲块数，余下不足100块的那部分空闲块的块号及块数登记在一个专用块中，登记最后一组块号的那个空闲块（其中第2个单元填“0”，表示该块中指出的块号是最后一组的块号，空闲块链到此结束。空闲块的分配和回收：系统初始化时先把专用块内容读到主存储器，当需分配空闲块时，就直接在主存中可找到哪些块是空闲的，每分配一块后把空闲块数减1。但要把一组中的第一个空闲块分配出去之前应把登记在该块中的下一组的块号及块数保存到专用块中。当一组空闲块被分配完后，则再把专用块的内容读到主存储器，指出另一组可供分配的空闲块。当归还一块时，只要把归还块的块号登记到当前组中且空闲块数加1。如果当前组已满100块，则把主存中的内容写到归还的那块中，该归还块作为新组的第一块。假设初始化时系统已把专用块读入主存储器单元L开始的区域中，分配和回收的算法如下：分配一个空闲块的算法：Typedef int to