05春操作系统试卷点评

2005春操作系统试卷点评近几年内，这将是我最后一次教OS，没准也是这辈子的最后一次了，不再出来害人了，也不会再出题了，试卷就完全公开了。任何人可以以任何形式随意使用这些题目、答案和点评，只要使用后告诉我一声就行。一、单选题（每题2分，共10分）(1)操作系统是（）A.硬件B.软件C.中间件D.人件答案是B，这个很显然。不过回答C的人不是凡人，也得分。这道题充分体现了计算机学科很多概念不能机械描述的特点。中间件的普遍特点是粘合两个不同系统，并使这两个系统之间的耦合度降低。OS符合这个特点，所以说它是一种中间件并不为过。OS的一些功能还要依赖CPU的“特别关照”实现，从这一点看，它也不能说就是纯软。我一直很讨厌名词解释、填空这样的题目，选择也不喜欢，就是因为这种机械的题目无法表达计算机的多样化特色。(2)下列事物不是操作系统的是（）A.JVMB.CP/MC.MS-DOSD.UNIX答案是A。不过JVM某种程度上也具备了OS的特质，拿它做一个只跑java程序的OS也是可以的，但与其它三个纯种OS比起来，它是最佳答案。(3)下列语言中，不能用来编写操作系统的是（）A.ASMB.JavaC.CD.C++答案是B。虽然没学过汇编，可能没有人在课堂告诉你ASM是什么，但这是你应该知道的。就算你不知道，学过java应该也知道java的本质是不能用来编写OS的。但是，如果强词夺理地说，做一个java到本地代码的编译器，再扩上一些不在乎跨平台能力的功能库，没有什么语言不能做OS。语言只是一个描述而已，其能力体现在你赋予它什么。计算机科学真奇妙呀(4)下列资源一般不由操作系统管理的是（）A.内存B.声卡C.CPUD.以上皆非答案是D。没啥可说的。有几个人选B，难道你连windows都没setup过？(5)下列说法中正确的是（）A.任何应用程序都不能绕过操作系统而直接与硬件交互B.没有操作系统的计算机是无法执行任何程序的C.设备驱动程序必须由设备厂商开发D.文件的长度与它占用的物理空间大小是一致的E.以上都不正确答案是E。基本来说，非常肯定的说法一定是错误的。计算机软件完全人造的东西，它的一切都是人为控制的，而不是由大自然或上帝主宰，所以一切皆有可能。A.如果OS允许，这是可以的，比如DOSB.操作系统本身就是程序。BIOS也是程序。更有很多应用程序是完全在硬件平台之上构建，没有OS支持的C.谁说M$不能写驱动程序？你也能写驱动程序D.只在很少的情况下一致二、简答题（20分）1.进程VS线程！请说出两者的最大相同和最大不同。（4分）两者都可以并行执行（2），但线程之间可以共享更多的资源，进程则较难甚至不能共享资源（2）。有的人就是把进程是什么、线程是什么抄了上去，字没少写，但，你是让我来总结相同和不同吗？开卷考试考的是你的大脑，不是手指2.从操作系统角度看，最实际的直面死锁的方法是什么？为什么是它？从程序员角度看，举出一种可以避免死锁的办法。（4分）鸵鸟策略，即不理会它（1）。因为发生死锁的概率很低（1），而处理死锁的算法都很复杂（1），得不偿失。避免死锁的方法很多，只要具体一点写就可以。3.如果没有CPU的“特别关照”，很多现代操作系统功能的实现都会效率很低甚至不可实现。请举出两个例子来证明这一观点。（4分）没有TSL指令，P、V的原语性很难实现；没有MMU、TLB，页面的地址转换会很慢；没有对R和M位的支持，页面置换算法很难实现；“特别关照”，就是说CPU特意为OS准备的东西。CPU速度快、DMA、中断、MMX、3DNOW等是CPU的通用功能，和OS无关4.一般一个操作系统要提供三类接口给不同类型的使用者，是哪三类接口？各给什么类型的使用者？（4分）Shell，给操作人员；应用开发接口，也叫系统调用，给应用程序开发人员；系统开发接口，给在核心做开发的人，比如驱动程序开发者。5.产生死锁的4个必要条件是什么？（4分）这题是送分的，没有人在此题丢分。三、求解题（20分）1.下面的示意性代码片段摘自一个运行在用Round-Robin算法进行线程调度的操作系统上的程序。它建立了若干个同优先级的线程，其中一个线程执行thread_worker2()，其余线程执行thread_work1()。这里面当然肯定存在着竞争（RaceCondition）。请举出一种因为竞争而导致错误的情况，并用P、V原语操作解决这里的竞争问题。（10分）intcounter=0;thread_worker1()//多个线程执行它{while(TRUE){object=CreateANewObj();//CreateANewObj()不访问任何全局资源AddToListTail(object);//把object加到链表的尾部counter=counter+1;}}thread_worker2()//只有一个线程执行它{while(TRUE){while(counter==0);object=GetFromListHead(object);//得到链表头部的object，//并将其从链表删除counter=counter-1;Process(object);}}链表和counter都是临界资源，问题是出在没有对他们实施保护。可悲的是有不少同学看不懂“while(counter==0);”是怎么回事，结果分析得乱七八糟。这个是实验课练习过的问题，做成这样，可以想象实验课的“诚信”二字飞到哪里去了。两种修改方法：intcounter=0;intmutex=1;thread_worker1()//多个线程执行它{while(TRUE){object=CreateANewObj();//CreateANewObj()不访问任何全局资源P(mutex);AddToListTail(object);//把object加到链表的尾部V(mutex);V(counter);}}thread_worker2()//只有一个线程执行它{while(TRUE){P(counter);P(mutex);object=GetFromListHead(object);//得到链表头部的object，//并将其从链表删除V(mutex);Process(object);}}intcounter=0;intmutex=1;thread_worker1()//多个线程执行它{while(TRUE){object=CreateANewObj();//CreateANewObj()不访问任何全局资源P(mutex);AddToListTail(object);//把object加到链表的尾部counter=counter+1;V(mutex);}}thread_worker2()//只有一个线程执行它{while(TRUE){P(mutex);object=GetFromListHead(object);//得到链表头部的object，//并将其从链表删除counter=counter-1;V(mutex);Process(object);}}注意P、V所处位置要尽量不影响系统的并行性2.某操作系统采用WSClock算法，顺时针搜索，τ取值为500。在2204时刻页面的分配和访问情况如下图所示。如果此时在一个tick内连续产生四次缺页错，那么依次会有哪些页面被换出？（10分）在我的计划中，此题是送分，但要用上你一点时间。但实际上好像用了大量的时间。之前我强调过这个算法在实践中的重要，但肯定有不少人复习时根本没有看这个算法。正确答案是我特意选择的一个吉利话“我要发了（5186）”，可惜看到这个吉利话的人不多，不过估计就算看到了，在当时的情况下可能也无心情反应。WSClock也不是一个铁板钉钉的算法，它也可以有各种不同的实现策略，前面的答案是按教材得出的，出于不死教条的原则，其它合理答案也得分，比如5816、5813等，给分比较宽泛。但如果第一选择不是5，0分，然后第二选择不是8或6，3分。58和56至少得6分。四、分析题（20分）1.如果把下图中的虚线条5和6删掉就是一个标准的进程状态转换图。那么请回答，为什么5和6不会或不应该存在于进程状态转换图中呢？（10分）此题体现了同学们的盲从心理，只知道接受知识，却不去思考知识是否合理。从OS的设计者角度看，5号转换可以存在，只要给blocked里刚获得资源的进程分配CPU就行了。但这么做系统的复杂度大大增加，blocked和ready之间不容易协调，所以不这么做。印象中这是我上课讲过的。绝大多数同学的回答大抵可以总结为“OS不这么做，所以它不存在”。不要成为知识的奴隶呀！220141151213008168001920841111620006203210420201132003112204当前虚拟时间虚页号最后一次访问时间R位M位RunningReadyBlocked1234566基本都答对了，因为ready的进程不执行，不可能申请资源，所以不可能有这种情况。2.微软公司发行了一种CD-ROM，根目录下有三个子目录，每个子目录内分别是Windows2000的Professional版、Server版和AdvancedServer版的全部安装文件。已知Windows2000的每个版本的安装文件的总和都大于500MB，而一张光盘的容量只有640MB。同时我们还知道，三个版本的Windows2000除了体积很小的数十个文件不同以外，大多数文件都是完全相同的。请你分析，这种光盘的制作原理是什么。（10分）一定有不少同学用过这样的光盘，但对其原理有好奇心的就非常少了。好奇心！好奇心！这很重要！首先这是一个CD-ROM，所以就要按照CD-ROM的标准来做，那就是ISO9660。ISO9660的目录项里有一个LocationofFile，将其指向同一个block，FileSize和Dateandtime以及Filename等都用完全一样的设置，就成了。五、设计题（30分）Google公司正准备开发一种专用的操作系统。因为你在操作系统课程取得的优异成绩，Google公司高薪聘用你为这个操作系统的主设计师。Google从网络上抓来大量的网页，分别保存在数千台主计算机上，以备搜索之用。如果某台主计算机故障，则搜索结果中就会缺少它所保存的数据，所以必须对数据进行备份。Google打算用几百台专用计算机来承担备份工作。为了最大化地发挥硬件能力，要根据需求的特点来开发专用的操作系统。需求如下：1.每台备份机对若干台主计算机提供备份服务，并且只对它们提供服务；2.需要备份的数据从网络发送过来，每个网络数据包大小为64KB。每台主计算机会连续发送64个数据包，把它们按次序连接在一起便构成一个完整的备份数据包，也就是说每个备份数据包的大小是4MB；3.因为网络自身的分时特性，当两台以上的主计算机同时发送数据时，它们的数据是以网络数据包为单位交错到达的，而且数据包的交错情况是完全随机的，没有规律。例如：主计算机A发出的网络数据包为A0、A1、A2、……、A63；主计算机B发出的网络数据包为B0、B1、B2、……、B63；备份计算机接受到数据包的一种可能顺序为：A0、A1、B0、A2、B1、B2、A3、B3、A4、A5、A6、……、B62、A58、B63、A59、A60、A61、A62、A63不过，可以通过网络自身的特性准确得知数据包来自那台主计算机；4.4MB备份数据包的前4个字节是该数据包的唯一的ID，是一个32位的无符号整型数；5.每台备份机所要处理的备份数据包的ID数值都是在0x00000001—0xFFFFFFFF之间，不会为0；6.如果接收到相同ID的备份数据包，无论它是否来自于同一台主机，都说明后到的数据包是原数据包的更新，直接覆盖原数据包即可；7.当某台主计算机数据丢失，它会向备份机请求数据恢复。每个请求都会说明它需要恢复的备份数据包的ID。备份机只要把相应的4MB备份数据包再拆成64个64KB的网络数据包发送给主计算机即可；8.每台主机都连接着一个64位的海量存储器，我们可以