操作系统原理期末试卷(参考答案及评分标准)

重庆大学试卷教务处07版第1页共6页《操作系统原理》课程试卷2012~2013学年第一学期开课学院：软件学院课程号：09000925考试日期：2012-12-16考试方式：考试时间：120分钟一、单项选择题（10分每题1分）1、页表中的脏数据位(DirtyBit)可以（B）（A）用来判断该页是否在物理内存中（B）用来减少PageFault中磁盘数据交换的开销（C）用来实现LRU算法（D）用来完成LRU的堆栈实现2、关于系统调用（systemcall），下列哪一个是正确的？（C）（A）系统调用与库函数调用是完全一样的。（B）应用程序可以替换系统调用。（C）系统调用是应用程序请求操作系统服务的唯一入口。（D）所有的操作系统都具有相同的系统调用。3、对于微核(micro-kernel)操作系统下列哪种说法是正确的（D）（A）微核操作系统不易于扩展（B）微核操作系统中用户空间与内核空间的通信开销较低（C）微核操作系统移植性较差（D）微核操作系统将部分内核模块移动到了用户空间4、外部碎片说法正确的是（C）（A）相对于内部碎片问题，外部碎片在操作系统内核之外（B）是由不连续分配方案导致的空间浪费问题（C）相对于内部碎片问题，外部碎片在进程之外（D）内部碎片可以合并而外部碎片不行5、用户编写的程序中所使用的地址是（A）（A）逻辑地址（B）线性地址（C）物理地址（D）页表地址6、关于临界区（Criticalsection），下列哪个说法是正确的？（B）（A）临界区中允许多个进程同时运行。（B）临界区是一段访问共享资源的代码。（C）临界区是一块需要保护的数据。（D）如果没有对临界区进行保护，程序每一次运行一定都会得到错误的结果。7、下列对操作系统的描述哪个是正确的（C）（A）计算机系统由运算器、控制器、存储器、输入、输出以及操作系统组成（B）操作系统需要提供人机界面，因此操作系统介于用户和应用程序之间（C）进程在操作系统中运行时会不断的在内核态于用户态之间切换（D）操作系统的设计与计算环境不相关8、同一进程内的线程间可共享（B）（A）栈（stack）（B）文件（C）CPU寄存器（D）局部变量9、假设一个系统的逻辑地址空间为8个页面，其中每一个页面占1024字节，物理内存为32个页帧（frame），该系的逻辑地址和物理地址各需要多少位？（A）（A）13，15。（B）15，17。（C）15，13。（D）17，13。10、关于虚拟内存，哪一个是正确的？（D）（A）虚拟内存只能通过请求式调页（demandpaging）实现。（B）虚拟内存是一个纯软件的系统，不需要硬件的支持也能实现。（C）如果一台32位的计算机拥有4GB的物理内存，那么它永远都不会发生“颠簸（thrashing）”。（D）在虚拟内存中，有效内存访问时间近似正比于缺页异常发生的概率。二、多项选择题（30分每题3分）命题人：刘寄组题人：洪明坚审题人：张毅命题时间：2012年11月28日教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊封线密重庆大学试卷教务处07版第2页共6页1、进程同步的经典问题包括（ACE）（A）读者写者问题（B）拜占庭问题（C）哲学家进餐问题（D）皮特森问题（E）有限缓冲区问题2、操作系统服务有（ABCDE）（A）人机界面（B）I/O操作（C）文件系统管理（D）进程间通信（E）资源分配3、进程调度可分为（CDE）（A）I/O调度（B）资源调度（C）长期调度（D）短期调度（E）中期调度4、下列文件系统的分配方式具有随机访问能力的是（AC）（A）连续分配（B）单向链表分配（C）单级索引分配（D）双向链表分配（E）循环链表分配5、同步问题的解决方法有（AD）(A)信号量（semaphore）(B）银行家算法(C)LRU算法(D)管程（monitor）(E)API6、下面哪一个说法是正确的？（ACD）（A）策略和机制分离是操作系统设计应该遵循的重要原则。（B）如果资源分配图中包含一个环，一定发生了死锁。（C）如果系统采用两级页表结构，则每一个进程必须有独立的页表。（D）为了获得最好的地址转换性能，页面大小一般都设为2的幂次方。7、下列哪几个数据结构或算法的局部性不好？（ABD）（A）哈希表（Hashtable）。（B）指针。（C）顺序查找（sequentialsearch）。（D）二分查找（binarysearch）。（E）栈（stack）8、属于抢占式（preemptive）的进程调度算法是（BDE）（A）先来先服务（FCFS）。（B）轮转（Round-Robin，RR）。（C）优先级调度。（D）多级反馈队列调度（Multilevelfeedbackqueue）。（E）最短作业优先（Shortestjobfirst,SJF）9、常见的页表结构有（ADE）(A)层次（hierarchy）(B)堆栈(C)链表(D)哈希（hashtable）(E)反向（inverted）10、下列属于文件基本操作的是（ABCDE）（A）截断truncate（B）读取read（C）写入write（D）创建create（E）删除delete三、简答题（24分）1、（4分）请解释PCB的含义并列举至少三项PCB的内容。2、（6分）画出进程的状态变迁图，并给出状态变迁的原因。3、（8分）请解释什么是PageFault，并用画图或简述的方式描述PageFault的处理过程。4、（6分）请简述死锁的必要条件,并用资源分配图列举一个发生死锁的例子。四、算法题（36分）1、(8分)请写出读者写者（reader-writer）问题的算法伪代码。2、(10分)系统中有已经到达的5个进程,请用FCFS，SJF和RR（时间片为10）画出调度过程的甘特图并计算三种算法的平均等待时间。ProcessBurstTimeP110命题人：刘寄组题人：洪明坚审题人：张毅命题时间：2012年11月28日教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊封密重庆大学试卷教务处07版第3页共6页P229P33P47P5123、(18分，软件工程专业题目)假设有一个32位系统的页面大小为1K字节，采用FIFO页面置换算法，当前进程分配4个物理帧，代码用了1个物理帧并常驻内存。现有两个进程分别运行如下的代码：（A）(B)其余3个物理帧用来保存数组a的数据，临时变量temp、i和j保存在寄存器中，一个“int”占用4个字节。请计算A和B各自产生了多少次Pagefault？（4分）如果这三个物理帧的首地址分别是：79A65400H79C65400H79E65400H请计算两种算法里当i=6，j=10时a中对应元素的物理地址？（6分）假设采用二级页表无TLB，1个内存访问周期为1μs，PageFault的时间开销各项分别为：pagefaultoverhead=10μs；swappageout=300μs；swappagein=30μs；restartoverhead=10μs；两种算法对数组总访问时间分别为多少？（8分）4、(12分，数字媒体专业题目)给定进程分配到的页帧数为3，页请求序列为0,1,4,2,0,2,6,5,1,2,3,2,1,2,6,2,1,3,6,2,分别给出FIFO、LRU和最优三种算法的页面调度的过程并计算缺页异常数。5、（6分，数字媒体专业题目）一个文件系统的FCB（FileControlBlock）能存储13个磁盘块地址，其中前面的10个地址指向文件的前10个磁盘块，第11个地址指向一个一级索引块（singleindirectblock），第12个地址指向一个二级索引块（doubleindirectblock）；第13个地址指向一个三级索引块（tripleindirectblock）。假设一个磁盘块有1024字节，每一个磁盘块可以存储256个磁盘块地址。请计算该文件系统能存储的最大的文件是多少字节？（只列出表达式即可）inttemp=0;inta[][]=newint[128][128];for(inti=0;i128;i++)for(intj=0;j128;j++)switch(imod4){case0:break;case1:temp+=a[i][j];break;case2:a[i][j]=i+j;break;case3:break;}inttemp=0;inta[][]=newint[128][128];for(inti=0;i128;i++)for(intj=0;j128;j++)switch(jmod4){case0:break;case1:temp+=a[j][i];break;case2:a[j][i]=i+j;break;case3:break;}命题人：刘寄组题人：洪明坚审题人：张毅命题时间：2012年11月28日教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊密重庆大学试卷教务处07版第4页共6页答题纸单项选择题1、（B）2、（C）3、（D）4、（C）5、（A）6、（B）7、（C）8、（B）9、（A）10、（D）多项选择题1、（ACE）2、（ABCDE）3、（CDE）4、（AC）5、（AD）6、（ACD）7、（ABD）8、（BDE）9、（ADE）10、（ABCDE）简答题1答：PCB是Processcontrolblock进程控制块的缩写（1分），PCB中的内容有：进程状态（ProcessState）、程序计数器（ProgramCounter）、CPU寄存器（CPURegister）、CPU调度信息（CPUSchedulingInformation）、内存管理信息（Memory-managementInformation）、资源调度信息（AccountingInformation）、I/O状态信息（I/OStatusInformation）（任意答对3个即给3分）2答：命题人：刘寄组题人：洪明坚审题人：张毅命题时间：2012年11月28日教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊重庆大学试卷教务处07版第5页共6页必须画出5个状态，否则为零分；状态之间转移方向画错一个扣一分，扣完为止；转移条件少写一个扣一分，扣完为止；3答：用图或者文字画出或写出上述6步即得分，少写不得分，顺序错误扣一半4答：互斥（Mutualexclusion）、拥有并等待（Holdandwait）、不可剥夺性（Nopreemption）、循环等待（Circularwait）（4分每个一分）画图（2分，只要是死锁即可不要求和参考答案一样）算法题1答：信号量WRT=1；信号量MUTEX=1；共享变量ReadCount=0（3分）（变量和信号量的名字可自己定义）作者Writer（1分）Wait(WRT)；CriticalSectionSignal(WRT)；读者Reader（4分）Wait(MUTEX)；ReadCount++;If(ReadCount==1)Wait(WRT)；Signal(MUTEX)；CriticalSectionWait(MUTEX)；ReadCount--;重庆大学试卷教务处07版第6页共6页If(ReadCount==0)Signal(WRT)；Signal(MUTEX)；2答：FCFS、SJF、RR的甘特图如下：P1P2P3P4P5P1P2P3P4P5P2P5P210394249P3P4P1P5P2310203210202330405052画图FCFS（1分）SJF（1分）RR（1分）FCFS平均等待时间：(0+10+39+42+49)/5=28（2分）SJF平均等待时间(0+3+10+20+32)/5=13（2分）RR平均等待时间(0+10+20+23+30+20+10+2)/5=23（3分）写对算式计算错误扣一半3答：3.1算法A产生PageFault共64次（2分）；算法B共产生PageFault共64*128=8192次。（2分）3.2算法A中a[6,10]按照FIFO算法应该放入首