北京工业大学计算机学院2009～2010年度第1学期
2007级《操作系统》期末考试题（A）
考试形式：闭卷
时间：2009年12月21日15:25 ∼ 17:00
班级___________ 学号____________ 姓名______________
一、单选题（24分，每题2分）
1、在一个分时系统中，用户进程A因为时间片到而被中断，系统选择用户进程B到CPU上
运行。
在这个过程中，操作系统不需要做什么操作？（）
A、将A的状态信息记录到A的PCB中
B、修改调度算法
C、从B的PCB中读取相关状态信息
D、启动调度程序，执行调度功能
2、系统出现死锁时一定同时保持了四个必要条件。
对资源采用按序分配算法后可破坏其中的（）条件。
A、互斥
B、占有且等待
C、可抢占资源
D、循环等待
3）
A、分页对程序员来说是透明的
B、页式管理中出现的内部碎片可以通过紧凑来解决
C、共享和保护在页式管理中不容易实现
D、处于就绪状态进程的页表起始地址存储在该进程的PCB中
4）
A、连续分配方法会导致很多的外部碎片。
B、链表分配方法会导致数据分散，降低文件的读写效率。
C、链表分配方法适应于文件的随机访问。
D、UNIX采用的索引节点的方法属于带索引的链表分配方法。
5、下面哪个进程调度算法综合考虑到了CPU计算密集型进程和I/O密集型进程？（）
A、多级反馈队列调度
B、优先级调度算法
C、RR调度算法
D、SJF调度算法
6、下面选项中，影响缺页中断率的因素是（）
I. 分配给进程的主存页框数
II. 页框的大小
III. 编程方法
IV. 页面调度算法
A、只有I
B、只有I和II
C、只有I、II和III
D、全部
7、下面哪一条是引入多道程序设计的好处？（）
A、使并发执行成为可能
B、简化操作系统的实现
C、减少对内存容量的需求
D、便于实施存储保护
8、在一个计算机系统中，管态下CPU可以执行（）
A、仅特权指令
B、仅非特权指令
C、全部指令
D、非法指令
9、测得某个采用请求调页策略的计算机系统的部分状态数据为：CPU利用率为20%，用于交换空间的硬盘的利用率为97.9%,其他设备的利用率为5%。
由此断定系统出现异常。
此种情况下，（）能提高资源利用率
A、安装一个更快的硬盘
B、通过扩大硬盘容量，增加对换空间
C、加内存条，增加物理空间容量
D、增加运行进程数量
10、下面关于进程的状态变迁不可能发生的是（）
A、运行→就绪
B、阻塞→运行
C、就绪→运行
D、运行→终止
11、在一个具有n个CPU的多处理器系统中，分别处于就绪态、运行态、阻塞态的进程数量的最大值是（）
A、n、1、n
B、n*n、n、n*n
C、无限制、n、n*n
D、无限制、n、无限制
12、为了匹配I/O设备与CPU之间的处理速度，最适合采用的技术是( )：
A、缓冲技术
B、中断技术
C、通道技术
D、虚拟存储技术
二、简答题（共20分）
1、（8分）虚拟存储管理的策略和方法都基于“程序运行的局部性原理”，虚拟存储又可以简要划分为“分页式管理”和“分段式管理”。
请简要回答以下问题：
(1)在使用分页式机制的系统中，已知一个应用程序的大小为10MB，页面大小为4KB，一
个页表项长度为32个字节。
为了保证该程序的最大运行性能，需要将其所有运行相关的信息保存在内存中，请问至少需要多少个页面存放页表？
(2)假设该系统使用了TLB，如果在取一条指令时，TLB中并未保存该指令所在的页面信息，
它该进行何种操作呢？
2、（6分）考虑一个支持连续分配、链接分配和索引分配策略的文件系统。
对于一个给定文件，如何决定该文件所应采取的策略？
3、(6分)学生小李在Windows XP系统中使用Netbeans集成开发环境编写Java应用程序。
他发现，在他录入代码的同时，立即可以看到源程序中有语法错误的部分被标记出来。
而他在“Windows任务管理器”中，看到只有一个“netbeans.exe”进程。
你认为Netbeans是如何实现在接受用户输入源程序的同时进行语法检查？
三、综合题(46分)
1、（6分）设系统中有四个进程（P1、P
2、P
3、P4），三类资源（R1、R2、R3）。
系统当前的资源分配状况如下列资源分配图所示：
请按银行家算法，回答下列问题：
（1）填写下列表格空白处中的内容：
（2）当前系统是否处于安全状态？请详细说明原因。
2、（8分）设有P1，P2，P3三个进程，它们进入就绪队列的时间、需要运行的时间如下所示：
进程进入时间运行时间（分钟）
P1 8:50 90
P2 9:00 24
P3 9:30 20
若不计调度等所消耗的时间，并采用非抢占调度。
请回答：
(1) 分别写出采用最短作业优先(SJF)调度算法、最高响应比优先（HRRN）算法选中的进程执行的次序。
要求给出计算过程。
(2) 分析RR算法和多级反馈队列调度算法对待短作业是否有利？为什么？
SJF:
HRRN：
3、（8分）一个磁盘有1000个柱面，编号为0到999。
假设刚刚满足的请求在200号磁道，磁头正向999号磁道的方向移动。
当前，按请求提出的时间先后顺序，有对下列磁道的访问请求：100、120、600、300、700。
从现在磁头位置开始，按照SSTF、C-SCAN的磁盘调度算法，要满足队列中即将到来的请求。
回答下列问题：
（1）分别给出响应请求的顺序。
（2）设寻道时每个柱面移动需要（磁头从一个磁道移动到另一个磁道）6ms，求采用SSTF 和C-SCAN算法的寻道时间各是多少？(C-SCAN算法不要求计算从999号磁道返回0号磁道的时间)
SSTF：
C-SCAN：
4、（8分）在请求分页存储管理系统中，一个进程的页面走向为
5、4、3、2、1、0、5、3、2、5。
当分配给该进程的物理页面数为4时（初始均为空），描述分别采用LRU和OPT页面置换算法时：
（1）该进程在访问过程中所发生的缺页次数（要求有图示过程）。
（2）给出被置换的页面号。
LRU：
OPT：
5、（8分）在一个请求分页系统中，页面大小为4KB（4096字节）。
假定：该系统在遇到有进程发生缺页时，如果系统中已没有空闲页框，则进行局部置换（即只能置换进程自己的页面）；否则，为缺页的进程追加分配页框，且选择处于空闲页框链表表头的空闲页框。
设操作系统已经为某进程P分配了4个页框。
该进程的0、3、4、6页面分别装入下列页框：31、14、20、40中。
系统当前还有3个空闲页框，空闲页框链表的元素依次是：30、25、29。
此时，进程P访问下列2个逻辑地址单元的内容，试分别求出相应的物理页框号，并给出计算过程（本题中的数字均为10进制数）。
（1）24748
（2）32596
6、（8分）某文件系统采用索引分配方式组织文件的磁盘块，存放文件磁盘块信息的磁盘块被称为索引盘块。
如：一个文件占用的磁盘块号为：100、30、45、210，它们存在于块号为50的磁盘块中，该块被称为索引盘块。
因此，一个大文件可能需要多个索引盘块。
要求：
（1）请你设计一种方法，如何将属于同一个文件的多个索引盘块组织起来？并对你的方法做出评价（提示：评价指标可以是：占用内存的大小、磁盘I/O次数等）。
（2）假设某个磁盘块可以存放256个盘块号，如果一个文件需要N个磁盘块，对于你所设计的方法，需要几次磁盘I/O才能访问到文件中的数据？
四、（P、V操作题）（10分）
某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零件，装配车间的任务是把A、B两种零件组装成产品。
两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上。
F1存放零件A，F2存放零件B，F1和F2的容量均可以存放10个零件。
装配工人每次从货架上取一个A零件和一个B零件，然后组装成产品。
规定货架一次只能一个人使用。
请用P、V操作进行正确管理。
要求：
（1）给出设置的信号量，写明其含义及初值。
（2）编写程序，用P、V操作实现他们之间的正确并发执行。