搜索
1南开大学信息技术科学学院考试卷2007-2008年度第一学期期末操作系统A卷（共16页）专业▁▁▁▁年级▁▁▁学号▁▁▁▁姓名▁▁▁▁成绩▁▁▁▁考生注意：请将答案写在空白的答题纸上，答题时标明题号。第一部分：简答题（共30分，每题6分）答题要求：请用简洁精练的文字回答以下问题1.进程调度的策略分为剥夺式调度和不可剥夺式调度，请简要解释两种策略的含义以及差别，并对每种调度策略列出至少两种对应的调度算法。剥夺式调度：操作系统按照进程调度算法控制多个进程分享CPU，使得CPU在多个进程之间进行切换，这种机制叫做剥夺式调度。(定义1分)而非剥夺式调度是指：进程一旦占用CPU，就会一直运行到结束，其他进程只能等待该进程释放CPU后才能依次占用CPU，这种机制叫非剥夺式调度。。(定义1分)剥夺式调度算法：时间片轮转，优先级调度，最短剩余时间优先等。(每个1分)非剥夺式调度算法：先来先服务，最短作业优先等。(每个1分)2.请简要解释DMA机制的工作方式，并分析DMA驱动I/O与中断驱动I/O的差别。DMA，即直接存储器存取，是指在外设和存储器之间开辟一个直接得分2的数据通道，数据传输由另外的DMA控制器来完成(2分)。DMA控制器在开始传输之前获取目的地址，由DMA控制器控制外设将数据写入存储器。(2分)这种方式驱动I/O和中断驱动I/O的最主要的区别在于不再需要CPU的参与。(2分)3.虚拟存储管理的内在思想是什么？从技术角度如何实现这种思想？虚拟存储器的思想是：程序、数据、堆栈的总大小可能超过可用的物理内存的总大小。操作系统通过某种方案来将当前使用的那部分数据方法内存中，而将其他部分放在磁盘上。虚拟存储器管理的本质是利用了程序数据的局部性原理。(3分)采用分页(Paging)、分段(Segment)一类技术，通过对内存面面的调度来实现。(1分)(具体解释略。)(2分)4.文件的逻辑结构分为几种形式？文件的磁盘布局分为几种形式？文件的逻辑结构主要分两大类：字符流式的无结构文件和记录式的有结构文件。(2分)字符流式的文件管理简单，用户操作较为简单，常见的如源代码文件、目标代码文件等。记录式文件将文件中的记录按照一定的方式进行排列，从而形成不同的逻辑结构，用户方便对其进行修改、追加、查找等功能。(1分)文件的磁盘布局是指文件存储在磁盘上的具体实现方式，主要有连续分配、链表分配、在内存中采用表的链表分配（索引文件）、i结点等几种方式。(3分)5.请列出至少6种你认为合理的CPU性能评价参数。主频、倍频、外频、指令集、流水线条数、前端总线频率、一级数3据cache、一级指令cache、二级cache等。(每个1分)4第二部分：编程计算题（共4题，必做，共45分）请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的答题顺序评分第一题（15分）第二题（12分）第三题（10分）第四题（8分）6.进程同步互斥与死锁问题的解决（默认分值：15分）有一条南北双向的国家公路，其中一段路程共享一个单车道的隧道，行驶的汽车到达隧道入口处时，没有迎面而来的汽车时才能使用隧道。为了避免事故的发生，需要设计一套传感和信号系统。当一辆汽车接近隧道时，传感器通过Arrive函数向信号控制系统传递汽车运行的方向参数；当一辆汽车离开隧道时，传感器通过Depart函数向信号控制系统传递汽车的运行参数。控制系统使用一个单核多线程CPU作为处理器，并在隧道两端设置信号灯如下：绿灯表示行进，红灯表示停止。图1是该问题的示意图：请回答以下问题：1）分析该问题中存在的同步和互斥关系，并确定需要使用几个传感器和信号灯，说明使用方式和设置位置。隧道是两边车的竞争条件。(1分)使用两个传感器和两个信号灯，分别在左右进入隧道的路上每条路上设置一个传感器和一个信号灯。信号灯位置在隧道口前，传感器位置得分车道车道车道车道隧道5在离隧道口更远一点的地方，在经过传感器后如果信号灯立即改变，有充分时间让司机停车。(2分)2）用伪代码设计该控制系统的软件框架（描述每个进程的处理过程）。答案参考猴子过桥问题：1.信号量定义typedefintsemph;semphLMutex=1;semphRMutex=1;semphConcur=1;intiL2RCount=0;intiR2LCount=0;2.左侧汽车过隧道进程//记录过隧道猴子数，对右侧信号量进行P操作P(Concur);//在通过传感器时开始P(LMutex);iL2RCount++;if(iL2RCount==1){P(RMutex);SetRLightRed();}V(LMutex);V(Concur);//过隧道Pass_Bridge(L,R);//过隧道后的信号灯恢复P(LMutex);6iL2RCount--;if(iL2RCount==0){V(RMutex);SetRLightGreen();}V(LMutex);3.右侧汽车过隧道进程与左侧类似。(6分)3）在你设计的软件框架中，是否存在死锁的可能？如果有的话，你如何处理死锁问题？不会产生死锁。(1分)7.虚拟存储管理——缺页调度问题的分析（默认分值：12分）使用“分页式”虚拟存储管理技术，假设一个进程P的页面访问顺序如下：012301401234。该进程创建时没有加载任何页面，即该进程启动时其所有指令和数据都不在内存中。1）设分配给该进程的物理页帧为3个，使用FIFO页面置换算法时，请问会发生多少次缺页中断？使用硬件实现的LRU算法，会发生多少次缺页中断？FIFO:9次(2分)当前页012301401234物理桢000333444444/11100000222//2221111133是否中断●●●●●●●●●替换页///012301LRU:10次(2分)当前页012301401234物理桢000333444222/11100000033//22211111147是否中断●●●●●●●●●●替换页///01234012）对于以上两种页面置换算法，如希望减少缺页中断的次数，是否可以通过增加物理页帧来解决？为什么？FIFO在这种情况下不能减少缺页中断，反而会增加(列表说明)。这是Belady异常现象。(2分)而LRU和其他如最优置换算法这类为栈式算法，增加物理页帧后必然能提高命中率。(2分)3）在分页系统中将I/O设备的数据缓冲区映射到内存空间后，其对应的页面是否能够被替换？为什么？不行。因为I/O设备的数据缓冲区映射到内存空间后，是虚拟的地址空间，并不真的存在于内存之中，因此不能进行页面替换。(2分)8.I/O设备与I/O软件问题的分析和解决（默认分值：12分）设有一台32位计算机，使用单核CPU。你负责基于这台计算机设计一种新的网卡驱动程序，网卡的数据缓冲区为1M大小，为了完成这个任务，你必须分析并解决以下问题：1）I/O软件问题：用户进程通过该网卡向局域网中的另一台计算机发送数据，请遵循I/O软件的层次和控制流程，描述用户进程数据被保存到网卡缓冲区中的完整处理过程。注意：必须说明有哪些系统进程/服务进程参与，以及各自的作用。8库例程(Systemcalllibraries)作用是给相应的系统调用提供参数并调用；守护进程(daemonprocess)是用于假脱机(spooling)技术，使用在如打印机等独占设备上；(6分)2）网卡的工作模式如下：用户发出一个系统调用，请求将数据发送到局域网的另一台计算机上。然后操作系统将数据复制到一个内核缓冲区中，再将数据复制到网卡的数据缓冲区中。当所有数据都安全存放在网卡的数据缓冲区后，再将它们以每秒10M位的速率发送。接收端的网卡以每微秒1位的速率保存它们。当最后一位被接受后，目标计算机的CPU将被中断。OS将新到达的数据包复制到内核缓冲区中，并检查该数据包属于哪个接收进程，然后将数据复制到接收进程的内存空间中。设每一个中断及其相关的处理过程需花费1毫秒，数据包为1024字节（忽略包头），并且复制一个字节花费1微秒时间。请问从发送进程提出请求，到接收进程获得数据的最小时间间隔是多少？interruptHardwaredriverUserprocessDeviceindependenceI/O请求I/O响应Systemcalllibraries,daemonprocesssuchasspoolingNaming,protection,sharingErrorhandling,registerssettingHandleI/Ointerrupt91ms(系统调用，请求发出)+2*1024byte/(1byte/us)(复制到网卡缓存)+1024byte/(10M*bit/s)(发送数据)+1024byte/(1bit/s)(接收数据)+1ms(接收完成，中断)+2*1024byte/(1byte/us)(复制)(3分)大约15ms(1分)9.进程管理问题（默认分值：8分）设操作系统中的进程状态有如下七个：New、Ready、Run、Blocked、Exit、SuspendReady、SuspendBlocked，请回答以下问题：1）请分析New、Exit和Suspend状态的作用。New状态指该进程的数据结构已创建，但内存映像还没有被加载。(1分)Exit状态指该进程的全部工作已经完成，但是由于被其他进程引用等原因，数据结构还没有删除。(1分)Suspend状态指该进程内存映像已经被替换出内存。(1分)2）请描述在计算机中何时处理进程调度？如果采用多级队列调度算法，请尝试设计一个进程调度程序的软件框架。1.在创建一个新进程时；2.在某进程退出时；3.当某进程被阻塞时；4.在一个I/O中断发生时。如果在周期性提供时钟中断的系统中，可以在每k个时钟中断时做出调度策略。(2分)进程调度程序框架设计要点：1.使用多级队列；102.动态优先级调度；3.响应时间短；4.防止饥饿。(5分)第三部分：系统分析题（共3题，选做2题，共25分）请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的答题顺序评分。本部分只需选做2题，多做题目不加分。第一题（15分）第二题（10分）10.文件系统综合设计（默认分值：15分）假定你负责设计一个基于32位计算机的文件系统，如果存储磁盘的容量是60G，磁盘扇区大小为1M，文件的最大容量为2GB，文件名仅支持8.3格式。该文件系统主要满足商用I/O操作，因此空间变化比较频繁，请设计一种合理的文件系统磁盘空间管理方式。包括目录、文件的逻辑结构与物理实现。结合操作系统教材上的方法设计，涉及东西较多，实际上就是一个真是的文件系统了。由于用于商用I/O操作，需要对文件记录进行频繁的修改、增删、查找等操作，并且可能使用到大的数据量，为了有序地管理目录和文件，使用层次级的目录结构，对文件则选择记录序列的逻辑组织结构。在物理实现时，选用i节点方式对文件目录进行管理。得分1111.系统安全分析（默认分值：10分）操作系统的安全性越来越重要，为了实现对数据和信息的安全保护，在操作系统设计过程中，需要设计很多方法技术。请回答以下问题：1)从内存管理的角度分析，可以有哪些安全保护手段？在PSW中加入对内存的控制信息，如上下界保护法，为每一个进程设立上下界寄存器，里面存放着被保护程序和数据的起始地址和终止地址；在页表中增加对访问的限制位，如保护键法为每一个被保护的存储块分配一个单独的保护键；第三种方法结合第一种，当CPU处于用户态时使用第一种方案的方法。核心态不做保护。2)为防止某些数据文件被非法访问，可以有哪些保护手段？保护域，对进程进行约束，让进程在某保护域中执行，由保护域限制进程访问的数据；存取控制表，对文件进行约束，在访问文件数据时按存取控