操作系统原理期末考试试题B卷(2008)_参考答案

第1页，共10页 南开大学信息技术科学学院本科生2008-2009年度第一学期操作系统原理课程期末试卷（B卷） 专业▁▁▁▁▁年级▁▁▁▁▁姓名▁▁▁▁▁▁学号▁▁▁▁▁▁成绩▁▁▁▁▁

一、简答题（本题共30分，每题6分，必做） 草稿区 1. 请简述分时操作系统中两种最主要的进程调度策略，并对每种策略举出2种实例。 剥夺式调度：操作系统按照进程调度算法控制多个进程分享CPU，使得CPU在多个进程之间进行切换， 这种机制叫做剥夺式调度。 (定义1分) 而非剥夺式调度是指： 进程一旦占用CPU，就会一直运行到结束， 其他进程只能等待该进程释放CPU后才能依次占用CPU，这种机制叫非剥夺式调度。。(定义1分) 剥夺式调度算法：时间片轮转，优先级调度，最短剩余时间优先等。(每个1分) 非剥夺式调度算法：先来先服务，最短作业优先等。(每个1分)

2. 请简要解释DMA机制的工作方式，并分析DMA驱动I/O与中断驱动I/O的差别？ DMA，即直接存储器存取，是指在外设和存储器之间开辟一个直接的数据通道， 数据传输由另外的DMA控制器来完成(2分)。 DMA控制器在开始传输之前获取目的地址，由DMA控制器控制外设将数据写入存储器。(2分) 这种方式驱动I/O和中断驱动I/O的最主要的区别在于不再需要CPU的参与。(2分)

得 分 第2页，共10页

3. 文件的逻辑结构分为几种形式？文件的磁盘布局分为几种形式？ 文件的逻辑结构主要分两大类：字符流式的无结构文件和记录式的有结构文件。(2分) 字符流式的文件管理简单，用户操作较为简单，常见的如源代码文件、目标代码文件等。 记录式文件将文件中的记录按照一定的方式进行排列，从而形成不同的逻辑结构， 用户方便对其进行修改、追加、查找等功能。(1分) 文件的磁盘布局是指文件存储在磁盘上的具体实现方式，主要有 连续分配、链表分配、在内存中采用表的链表分配（索引文件）、i结点等几种方式。(3分) 草稿区 4. 解释什么是中断，并对中断的处理过程做简要描述。

中断是指计算机在执行期间，系统内发生任何非寻常的或者非预期的急需处理的事件， 使得CPU暂时中断当前正在执行的的程序转去执行相应的事件处理程序， 待处理完毕后又返回原来被中断处继续执行或者调度新的进程执行的过程。（3分） 一般中断处理程序主要由以下几步完成，判断中断响应文件、关中断、保存中断现场、 分析中断原因转中断处理子程序、执行中断处理子程序、恢复现场、开中断、返回中断点。（3分）

5. 请列出至少3种你认为CPU中比较重要的跟操作系统有关的寄存器。 CPU中最重要的寄存器有：程序计数器PC，其中装有下一周期要被执行的指令的地址。（2分） 指令寄存器IR，内装有待执行的指令。（2分） 程序状态字PSW，该寄存器中的各个比特位代表着系统中当前的各种不同状态与信息。 例如执行模式是否允许中断等。（2分） 第3页，共10页

二、编程计算题（本题共四小题，共计45分，必做） 草稿区  请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。  必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。  如填写内容无效或者不填写表格，则按照默认的题面分值评分 第一题（15分） 第二题（12分） 第三题（10分） 第四题（8分）

6. 进程同步互斥与死锁问题的解决（默认分值：15分） 有一条南北双向的国家公路，其中一段路程共享一个单车道的隧道，行驶的汽车到达隧道入口处时，没有迎面而来 的汽车时才能使用隧道。为了避免事故的发生，需要设计一套传感和信号系统。当一辆汽车接近隧道时，传感器通 过Arrive函数向信号控制系统传递汽车运行的方向参数；当一辆汽车离开隧道时，传感器通过Depart函数向信号 控制系统传递汽车的运行参数。控制系统使用一个单核多线程CPU作为处理器，并在隧道两端设置信号灯如下： 绿灯表示行进，红灯表示停止。 图1是该问题的示意图：

请回答以下问题： 1）分析该问题中存在的同步和互斥关系，并确定需要使用几个传感器和信号灯，说明使用方式和设置位置。

隧道是两边车的竞争条件。(1分) 使用两个传感器和两个信号灯，分别在左右进入隧道的路上每条路上设置一个传感器和一个信号灯。 信号灯位置在隧道口前，传感器位置在离隧道口更远一点的地方，在经过传感器后如果信号灯立即改变， 有充分时间让司机停车。(2分)

2）用伪代码设计该控制系统的软件框架（描述每个进程的处理过程）。 在你设计的软件框架中，是否存在死锁的可能？如果有的话，你如何处理死锁问题？

得 分 车道 车道 车道 车道 隧道 第4页，共10页

1. 信号量定义 typedef int semph; semph LMutex = 1; semph RMutex = 1; semph Concur = 1; int iL2RCount = 0; int iR2LCount = 0; 2. 左侧汽车过隧道进程 // 记录过隧道汽车数，对右侧信号量进行P操作 P(Concur); // 在通过传感器时开始 P(LMutex); iL2RCount++; if(iL2RCount == 1) { P(RMutex); SetRLightRed(); } V(LMutex); V(Concur); // 过隧道 Pass_Bridge(L,R); // 过隧道后的信号灯恢复 P(LMutex); iL2RCount--; if(iL2RCount == 0) { V(RMutex); SetRLightGreen(); } V(LMutex); 3. 右侧汽车过隧道进程与左侧类似。(6分) 第5页，共10页

草稿区 7. 虚拟存储管理——缺页调度问题的分析（默认分值：10分）

使用“分页式”虚拟存储管理技术，假设一个进程P的页面访问顺序如下：0 1 2 3 0 1 4 0 1 2 3 4。 该进程创建时没有加载任何页面，即该进程启动时其所有指令和数据都不在内存中。 1） 设分配给该进程的物理页帧为3个，使用FIFO页面置换算法时，请问会发生多少次缺页中断？使用硬件实现的 LRU算法，会发生多少次缺页中断？ FIFO: 9次(2分) 当前页 0 1 2 3 0 1 4 0 1 2 3 4

物理桢 0 0 0 3 3 3 4 4 4 4 4 4 / 1 1 1 0 0 0 0 0 2 2 2 / / 2 2 2 1 1 1 1 1 3 3 是否中断 ● ● ● ● ● ● ● ● ● 替换页 / / / 0 1 2 3 0 1

LRU: 10次(2分) 当前页 0 1 2 3 0 1 4 0 1 2 3 4

物理桢 0 0 0 3 3 3 4 4 4 2 2 2 / 1 1 1 0 0 0 0 0 0 3 3 / / 2 2 2 1 1 1 1 1 1 4 是否中断 ● ● ● ● ● ● ● ● ● ● 替换页 / / / 0 1 2 3 4 0 1

2） 对于以上两种页面置换算法，如希望减少缺页中断的次数，是否可以通过增加物理页帧来解决？为什么？

FIFO在这种情况下不能减少缺页中断，反而会增加 (列表说明)。这是Belady异常现象。(2分) 而LRU和其他如最优置换算法这类为栈式算法，增加物理页帧后必然能提高命中率。(2分) 3）在分页系统中将I/O设备的数据缓冲区映射到内存空间后，其对应的页面是否能够被替换？为什么？

不行。因为I/O设备的数据缓冲区映射到内存空间后，是虚拟的地址空间， 并不真的存在于内存之中，因此不能进行页面替换。(2分) 第6页，共10页

草稿区 8. I/O设备与I/O软件问题的分析和解决（默认分值：12分）

设有一台32位计算机，使用单核CPU。你负责基于这台计算机设计一种新的网卡驱动程序，网卡的数据缓冲区为 1M大小，为了完成这个任务，你必须分析并解决以下问题： 1）I/O软件问题：用户进程通过该网卡向局域网中的另一台计算机发送数据，请遵循I/O软件的层次和控制流程，描 述用户进程数据被保存到网卡缓冲区中的完整处理过程。注意：必须说明有哪些系统进程/服务进程参与， 以及各自的作用。

库例程(System call libraries)作用是给相应的系统调用提供参数并调用； 守护进程(daemon process)是用于假脱机(spooling)技术，使用在如打印机等独占设备上；(6分) 2)网卡的工作模式如下：用户发出一个系统调用，请求将数据发送到局域网的另一台计算机上。然后操作系统将数据 复制到一个内核缓冲区中，再将数据复制到网卡的数据缓冲区中。当所有数据都安全存放在网卡的数据缓冲区后， 再将它们以每秒10M位的速率发送。接收端的网卡以每微妙1位的速率保存它们。当最后一位被接受后，目标计算 机的CPU将被中断。OS将新到达的数据包复制到内核缓冲区中，并检查该数据包属于哪个接收进程，然后将数据 复制到接收进程的内存空间中。设每一个中断及其相关的处理过程需花费1毫秒，数据包为1024字节（忽略包头）， 并且复制一个字节花费1微秒时间。请问从发送进程提出请求，到接收进程获得数据的最小时间间隔是多少？

interrupt Hardware

driver

User process Device independence

I/O请求 I/O响应 System call libraries, daemon process

Naming, protection,

Error handling, registers setting

Handle I/O