一、名词解释题（每题5分，共25分） 1. 缓冲区
2. 进程
3. 文件控制块(FCB)
4. 特权指令
5. 临界资源
二、判断题（每题1分，共5分）
1、 并发进程的执行结果只取决于进程本身，不受外界影响。 （ ）
2、 任何一个进程在申请新资源前总是先归还已得到的资源，则系统不会死
锁。 （ ）
3、 P、V操作不仅可用来实现进程的同步与互斥，而且可以防止系统死锁。
（ ）
4、 银行家算法是在保证至少有一个进程能得到所需的全部资源的前提下进
行资源分配的。（ ）
5、 如果不能控制并发进程执行的相对速度，则它们在共享资源时一定会出现
与时间有关的错误。 （ ）
三、简答题（每题5分，共20分）
1、 操作系统在进程管理方面的五项主要活动是什么？
2、操作系统在存储管理方面有哪三项主要活动？
3、操作系统在外存管理方面有哪三项主要活动？
4、操作系统在文件管理方面有哪五项主要活动？
1
四、死锁问题（共15分）
1 下面的资源图（a）和（b）是否会出现死锁？（5分）
（a）
（b）
2、假设在一个系统中，有m个同类资源，由n个进程共享。进程每次只可以申请
与释放一个资源。若如下两个条件成立，证明该系统不存在死锁： a. 每个进程的最大资源需求量Maxi在1与m之间。 b. 所有进程的最大需求量之和少于m+n。 注：建议在证明中采用如下符号： Maxi每个进程的最大资源需求量
Needi每个进程的仍待满足的资源需求量
Allocationi每个进程的已经被满足的资源需求量 （10分）
五、进程同步（共１5分）
1、 描述进程间通信原语P操作与V操作的定义。（5分）
2
2、在公共汽车上，司机和售票员的工作流程如下：
司机 启动车辆 行车 到站停车
售票员 关车门 售票 开车门
为保证乘客的安全，司机和售票员应密切配合协调工作。假定初始状态为：车辆
正在起点站停着车、开着门，等待第一批乘客。当发车时间到，售票员关好车门后司机可以启动车辆。若用P、V操作来实现司机与售票员之间的协调工作，请回答下列问题：
（1）司机与售票员之间的关系是同步还是互斥？
（2）用P、V操作来管理时应定义几个信号量？初值为多少？ （3）请在司机与售票员的工作流程中填上适当的P操作和V操作，使他们能安全、协调地工作。
六、存储管理（10分）
一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0xC0300000开始映射第一级页表所占的4KB空间，请问4MB大小页表空间起始位置应映射在什么位置？并说明理由。（注意B代表字节，一个32位地址占4字节）
3
七、进程调度问题（10分）
有5个进程如下表。时间从0开始，单位为1，最高优先级为0. 进程 到达时间 优先级 所需运行时间
A 0 2 3 B 2 3 8 C 4 4 6 D 6 1 5 E 8 0 4 绘图说明以下进程调度过程：（1 CPU系统，所有进程只使用CPU）。 先来先服务（FCFS）；
轮转调度（Round-Robin）时间片=2；
优先级轮转法（Priority Round-Robin）时间片=2； 最短进程优先算法（Shortest Process Next）。
注：请使用时间为横向坐标轴，并请在图中标明每个进程的“等待”和“运行两种状态。
操作系统试卷（2010年）
二、名词解释题（每题4分，共24分） 6. 进程控制块
7. 原语
8. 临界区
9. 虚拟存储器
10. 缓冲区
11. 文件目录
二、判断题（每题1分，共6分）
6、 一个进程可以涉及一个或若干个程序的执行；反之，同一个程序只可以对
应一个进程。 （ ）
7、 信号量是只允许由P/V操作进行访问和修改的数据结构。 （ ） 8、 并发是指多个任务在多个处理机上正在同时运行，在微观上看，这些任务
是在各自的物理处理机上分别运行。 （ ）
9、 进程的同步与互斥可以发生在一个进程之中。 （ ）
10、中断方式的数据传送是在中断处理时由CPU控制完成的；DMA方式则
4
不经过CPU，而是在DMA控制器的控制下完成的。 （ ）
11、动态重定位便于程序浮动，其实现时采用的硬件机构是重定位寄存器和
加法器。 （ ）
七、简答题（每题4分，共20分）
1、 实时系统和分时系统各有什么特点？有什么本质的区别？
2、 进程与线程之间有何区别？
3、 简述段页式存储管理的基本原理。
4、 简述设备管理的主要功能。
5、 什么是文件的物理结构？常见的文件物理组织有几种？
八、资源分配（共5分）
假设有三个进程P1，P2和P3并发工作。进程P1需用资源S1和S2；进程P2需用资源S3和S1；进程P3需用资源S2和S3。请回答：
(1) 若对资源分配不加，是否会发生死锁现象？请举例说明。（2分） (2) 为保证进程的正确工作，可采用怎样的资源分配策略？为什么？（3分）
九、进程同步（共15分）
设有三个并发进程：进程Reader负责从输入设备读入信息并传送给进程Handler，进程Handler将信息加工并传送给进程Printer，进程Printer将进行打印
5
输出。其中，三个进程共享同一个缓冲区，且缓冲区大小为K。请使用P/V操作，写出正确的并发程序。请注意以下说明：
(1) 所使用的信号量：同步信号量或(和)互斥信号量，并说明信号量的名称、
含义及初值。（3分）
(2) 分别写出进程Reader、Handler、Printer及主进程的代码。（12分）
十、银行家算法（10分）
假设有A、B、C、D四类资源，在银行家算法中，若出现如下资源分配情况： Process Allocation Need Available P0 0032 0012 1623 P1 1000 1750 P2 13 2356 P3 0332 0652 P4 0014 0656
请问：
(1) 当前状态是否是安全的？若是，给出一个安全序列。（5分）
(2) 如果进程P2提出安全请求Request[2]=(1,2,2,2)，系统能否将资源分配给
它？说明原因。（5分）
十一、 存储管理（20分）
1、假定某页式存储管理系统，主存为KB，分成16块，块号为0，1，2，……，15。假设某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6块。请问：（共8分）
(1) 该作业的总长度为多少字节？（按十进制）（2分） (2) 写出该作业每一页在主存中的起始地址。（2分）
(3) 若给出逻辑地址[0,100]，[1,50]，[2,0]，[3,60]，请计算出相应的内存地址。
（4分）
6
2、在一个请求页式存储管理系统中，进程P共有5页，访问串是4、3、2、1、4、3、5、4、3、2、1、5，且开始执行时主存中没有页面。当分配给该进程的物理页面数为3和4时，试用如下页面淘汰算法，计算访问过程中发生的缺页率，并比较所得结果。（12分）
(1) FIFO (2) LRU (3) OPT
操作系统试卷（2010
年）参
三、名词解释题（每题4分，共24分） 12. 进程控制块
答案：进程控制块是一个与动态过程相联系的数据结构，记载了进程的外部特性（名字、状态等）以及与其他进程的联系（通信关系），还记录了进程所拥有的各种资源。进程控制块是进程存在的标志。
13. 原语
答案：原语通常由若干条指令所组成，用来实现某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。
14. 临界区
答案：必须互斥执行的程序段称为相对于临界资源的临界区。
15. 虚拟存储器
答案：虚拟存储技术是在主存和辅存之间，增加部分软件及必要的硬件支持，使主、辅之间的信息交换、程序的重定位、地址转换都能自动进行，从而主、辅存形成一个有机的整体，这种存储器的概念成为虚拟存储器。
16. 缓冲区
答案：为了解决外部设备和内存或外部设备和CPU之间的数据传送速度不匹配的问题，在系统中引入缓冲区来暂存数据。
17. 文件目录
答案：目录是文件系统层次结构的一个非终结节点，一个目录通常包含有许多目录项，每个目录项可能是一个文件或目录。
二、判断题（每题1分，共6分）
12、一个进程可以涉及一个或若干个程序的执行；反之，同一个程序只可以
对应一个进程。 （）
13、信号量是只允许由P/V操作进行访问和修改的数据结构。 （） 14、并发是指多个任务在多个处理机上正在同时运行，在微观上看，这些任
务是在各自的物理处理机上分别运行。 （）
15、进程的同步与互斥可以发生在一个进程之中。 （）
7
16、中断方式的数据传送是在中断处理时由CPU控制完成的；DMA方式则
不经过CPU，而是在DMA控制器的控制下完成的。 （）
17、动态重定位便于程序浮动，其实现时采用的硬件机构是重定位寄存器和
加法器。 （）
十二、 简答题（每题4分，共20分）
6、 实时系统和分时系统各有什么特点？有什么本质的区别？ 答案：
（1） 实时系统通常是一个专用系统，它的特点是响应时间快，快的程度依赖于
实时系统的种类，如果是实时控制系统，则响应时间依赖于实时控制对象的需求，根据需要及时响应；如果是实时信息管理系统，其响应时间与分时系统的要求相似，只要使用者不抱怨响应慢即可，一般不超过3秒。实时系统对安全性要求较高，系统的安全可靠是实时系统的保障。
（2） 分时系统亦称交互式系统，其特点是对用户的响应及时，当多个用户同时
使用计算机时，都有独占的感觉。
（3） 实时系统对响应时间的要求比分时系统更高，一般要求响应时间为妙级、
毫秒级甚至微妙级。与分时系统相比，实时系统没有那么强的交互会话功能，通常不允许用户通过实时终端设备去编写新的程序或修改已有的程序。实时终端设备通常只是作为执行装置或询问装置，属专用系统。
7、 进程与线程之间有何区别？ 答案： 进程是操作系统中并发单元，也是能分得资源的最小单位。线程是在进程内部活动的并发单元，它只是进程行为的一条的执行路线，它能使用的资源仅限于它所在的进程范围之内，惟一能通过线程获得的资源就是使用处理机的时间片。有时也把线程称为轻量级进程。
8、 简述段页式存储管理的基本原理。 答案： 段页式系统的基本原理是分段和分页原理的结合。即先将用户程序分为若干个段，再把每个段划分成若干个页，并为每个段赋予一个段名。在段页式系统中，为了实现从逻辑地址到物理地址的转换，系统中需同时配置段表和页表。段表的内容还要包括页表起始地址和页表长度。
9、 简述设备管理的主要功能。 答案：
（1） 提供设备管理程序和进程管理系统的接口。当进程申请设备资源时，
该接口将进程的请求转发给设备管理程序。
（2） 进行设备分配。按照设备类型和相应的分配算法，把设备和其他相关
的硬件分配给请求该设备的进程，并把未分配到所请求设备的进程放入等待队列。
（3） 实现设备和设备、设备和CPU之间的并行操作。针对相应的硬件支
持，采用不同的输入/输出控制方式。
8
（4） 进行缓冲区管理。设备管理程序负责进行缓冲区分配、释放及有关的
管理工作。
10、 什么是文件的物理结构？常见的文件物理组织有几种？ 答案：
（1） 文件的物理结构是指文件记录在文件管理系统内部采用的、与物理存
储介质的特性相适应的方式，是为系统使用的。
（2） 顺序文件结构、随机文件结构、串联文件。
十三、 资源分配（共5分）
假设有三个进程P1，P2和P3并发工作。进程P1需用资源S1和S2；进程P2需用资源S3和S1；进程P3需用资源S2和S3。请回答：
(3) 若对资源分配不加，是否会发生死锁现象？请举例说明。（2分） (4) 为保证进程的正确工作，可采用怎样的资源分配策略？为什么？（3分） 答案：
（1） 可能会发生死锁。例如：进程P1，P2和P3分别获得资源S1，S3和S2
后，再继续申请资源时都要等待，即发生循环等待。(或进程在等待新源时均不释放已占资源)
（2） 可有几种答案：
A. 采用静态分配：由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
B. 采用按序分配：不会出现循环等待资源现象。
C. 采用银行家算法：因为在分配时，保证了系统处于安全状态。
十四、 进程同步（共15分）
设有三个并发进程：进程Reader负责从输入设备读入信息并传送给进程Handler，进程Handler将信息加工并传送给进程Printer，进程Printer将进行打印输出。其中，三个进程共享同一个缓冲区，且缓冲区大小为K。请使用P/V操作，写出正确的并发程序。请注意以下说明：
(3) 所使用的信号量：同步信号量或(和)互斥信号量，并说明信号量的名称、
含义及初值。（3分）
(4) 分别写出进程Reader、Handler、Printer及主进程的代码。（12分） 答案：
（1） 同步信号量：empty，表示空缓冲块数目，初值为k；full，表示可进行信
息加工的缓冲块数目，初值为0；ok，表示可进行信息输出的缓冲块数目，初值为0。
互斥信号量：mutex，用于实现临界区互斥访问，初值为1。
（2） 代码如下： var
empty, full, ok, mutex: semaphore; inR, outR, inP, outP: integer; buffer: array 0..k-1 of item; procedure Reader
9
begin
while true do begin 输入数据data1; P(empty); P(mutex); buffer(inR) := data1; inR := (inR+1) mod (k); V(mutex); V(full); end end
procedure Handler begin
while true do begin P(full); P(mutex); data2 := buffer(outR); outR:= (outR+1) mod (k); V(mutex); 对data2加工; P(mutex); buffer(inP) := data2; inP:= (inP+1) mod (k);
V(mutex);
V(ok); end end
procedure Printer begin
while true do begin P(ok); P(mutex); data3 := buffer(outP); outP := (outP+1) mod (k); V(mutex); V(empty); 打印data3; end end begin
seminitial(empty.v,k; full.v,0; ok.v, 0; mutex.v,1); inR:=0; outR:=0; inP:=0; outP:=0; cobegin
10
Printer; Handler; Printer; coend end
十五、 银行家算法（10分）
假设有A、B、C、D四类资源，在银行家算法中，若出现如下资源分配情况： Process Allocation Need Available P0 0032 0012 1623 P1 1000 1750 P2 13 2356 P3 0332 0652 P4 0014 0656
请问：
(3) 当前状态是否是安全的？若是，给出一个安全序列。（5分）
(4) 如果进程P2提出安全请求Request[2]=(1,2,2,2)，系统能否将资源分配给
它？说明原因。（5分）
答案：
（1）当前状态是安全状态。
令Work = Available=（1, 6, 2, 3），运行安全性检测算法：
1）Finish[0]=false并且Need[0]=(0, 0, 1, 2) （2）运行银行家算法，由于Request[2]=（1, 2, 2, 2）&& Need[2]=（2, 3, 5, 6），因而请求合法。进一步，Request[2]=（1, 2, 2, 2）&& Available=（1, 6, 2, 3），故该请求是可以满足的。假设将资源分配给p2，则系统状态变为： Process Allocation Need Available P0 0032 0012 0401 P1 1000 1750 P2 2576 1134 P3 0332 0652 P4 0014 0656 11 运行安全性检测算法，Work=Available=（0, 4, 0, 1），Finish[i]=false，此时所有Need[i] && Work[i]均不成立，结果Finish[i]均为false，不存在安全进程序列，系统处于不安全状态。系统将取消资源分配并恢复原来状态，进程p2等待。 十六、 存储管理（20分） 1、假定某页式存储管理系统，主存为KB，分成16块，块号为0，1，2，……，15。假设某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6块。请问：（共8分） (4) 该作业的总长度为多少字节？（按十进制）（2分） (5) 写出该作业每一页在主存中的起始地址。（2分） (6) 若给出逻辑地址[0,100]，[1,50]，[2,0]，[3,60]，请计算出相应的内存地址。 （4分） 答案： （1）每块的长度=KB/16=4KB，因为块的大小与页面的大小相等，所以每页为4KB。因此，作业的总长度为4KB*4=16KB。 （2）因为页号为0，1，2，3，被分别装入主存的2，4，1，6块中，即块表为： 页号 块号 0 2 1 4 2 1 3 6 所以该作业的： 第0页在主存中的起始地址为4K*2=8K； 第1页在主存中的起始地址为4K*4=16K； 第2页在主存中的起始地址为4K*1=4K； 第3页在主存中的起始地址为4K*6=24K。 （3）逻辑地址[0,100]的内存地址为4K*2+100=8192+100=8292 逻辑地址[1,50]的内存地址为4K*4+50=16384+50=134 逻辑地址[2,0]的内存地址为4K*1+0=4096+0=4096 逻辑地址[3,60]的内存地址为4K*6+60=24576+60=24636 2、在一个请求页式存储管理系统中，进程P共有5页，访问串是4、3、2、1、4、3、5、4、3、2、1、5，且开始执行时主存中没有页面。当分配给该进程的物理页面数为3和4时，试用如下页面淘汰算法，计算访问过程中发生的缺页率，并比较所得结果。（12分） (4) FIFO (5) LRU (6) OPT 答案： （1）根据所提供的访问次序，采用FIFO淘汰算法的页面置换情况如下： 3 2 1 4 3 5 4 3 2 1 5 访问4 次序 12 3 2 1 4 3 5 5 5 2 1 物理4 页1 4 3 2 1 4 3 3 3 5 2 物理 页2 4 3 2 1 4 4 4 3 5 物理 页3 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为9/12。 3 2 1 4 3 5 4 3 2 1 5 访问4 次序 3 2 1 1 1 5 4 3 2 1 5 物理4 页1 4 3 2 2 2 1 5 4 3 2 1 物理 页2 4 3 3 3 2 1 5 4 3 2 物理 页3 4 4 4 3 2 1 5 4 3 物理 页4 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为10/12。 由结果可以看出，对于FIFO页面淘汰算法，增加分配给进程的物理页数，缺页率反而上升。因此，FIFO页面淘汰算法有异常现象。 （2）根据所给访问串，采用LRU淘汰算法的页面置换情况如下： 3 2 1 4 3 5 4 3 2 1 5 访问4 串 3 2 1 4 3 5 4 3 2 1 5 物理4 页1 4 3 2 1 4 3 5 4 3 2 1 物理 页2 4 3 2 1 4 3 5 4 3 2 物理 页3 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为10/12。 3 2 1 4 3 5 4 3 2 1 5 访问4 串 3 2 1 4 3 5 4 3 2 1 5 物理4 页1 4 3 2 1 4 3 5 4 3 2 1 物理 页2 4 3 2 1 4 3 5 4 3 2 物理 页3 4 3 2 1 1 1 5 4 3 物理 13 页4 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为8/12。 由结果可以看出，对于LRU页面淘汰算法，增加分配给进程的物理页数，缺页率降低。 （3） 根据所给访问串，采用OPT淘汰算法的页面置换情况如下： 4、3、2、1、4、3、5、4、3、2、1、5 3 2 1 4 3 5 4 3 2 1 5 访问4 串 4 4 4 4 4 4 4 4 2 2 2 物理4 页1 3 3 3 3 3 3 3 3 3 1 1 物理 页2 2 1 1 1 5 5 5 5 5 5 物理 页3 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为7/12。 3 2 1 4 3 5 4 3 2 1 5 访问4 串 4 4 4 4 4 4 4 4 4 1 1 物理4 页1 3 3 3 3 3 3 3 3 3 3 3 物理 页2 2 2 2 2 2 2 2 2 2 2 物理 页3 1 1 1 5 5 5 5 5 5 物理 页4 缺页 缺 缺 缺 缺 缺 缺 缺页率为6/12。 由结果可以看出，对于OPT页面淘汰算法，增加分配给进程的物理页数，缺页率下降。OPT页面淘汰算法仅是一种理论算法，因为它根据未来页面的走向决定淘汰哪一页，而在实际执行时无法准确地知道未来行为。所以，该算法不作为实用算法，仅用于算法的比较和评价。 14 操作系统试卷（2011年） 四、名词解释题（每题5分，共25分） 18. 文件控制块 19. 临界资源 20. 虚拟存储器 21. 死锁 22. 页表 二、判断题（每题1分，共5分） 18、由于P、V操作描述同步、互斥等问题的能力不足，所以有必要引入其 它的通讯原语或机制，如send， receive或Monitor等。（ ） 19、信号量是只允许由P/V操作进行访问和修改的数据结构。（ ） 20、在请求页式存储管理中，页面淘汰所花费的时间不属于系统开销。（ ） 21、预防死锁就是破坏死锁存在的某个必要条件。（ ） 22、磁盘是一类典型的字符设备。（ ） 十七、 简答题（每题5分，共20分） 11、 如果普通用户程序可以自行修改页表，会产生什么问题？ 12、 进程与线程之间有何区别？ 13、 简述并比较SCAN（扫描）磁盘调度算法与最短寻道时间优先算法。 14、 信号量的物理意义是什么？ 十八、 资源分配（共10分） 某计算机系统中有8 台打印机,有k个进程竞争使用,每个进程最多需要3 台打印机. 该系统可能会发生死锁的k 的最小值是多少？并说明理由。 十九、 进程同步（共15分） (5) 写出P、V操作的定义。（5分） (6) 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时， 若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。试用PV操作同步顾客和营业员的活动过程。（10分） 二十、 存储管理（15分） 某计算机提供给用户232字节的虚拟存储空间，虚拟存储器采用一级页表实现，页面大小是4K字节。某进程的页表内容如下表所示，操作系统最多为进程分配2页物理内存，采用最近最少使用置换算法(LRU)和局部淘汰策略。设有虚地址访问序列为2111H、191AH、2315H，请问： 15 （1） 进程页表占用多少内存空间？请说明理由。（5分） （2） 191AH的物理地址是多少？请说明理由。（10分） 页号 页框号（物理块号） 特征位（存在位）* 0 10H 1 1 0 2 41H 1 * 1表示在内存，0表示不在内存。 二十一、 并发问题（10分） 下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之： cobegin var x：integer； procedure P1 procedure P2 var y，z：integer； var t，u：integer； begin begin x：=1； x：=0； y：=0； t：=0； if x1 then y：=y+1； if x1 then t：=t+2； z：=y； u：=t； end end coend 操作系统试卷（2011年）参 五、名词解释题（每题4分，共24分） 23. 文件控制块 答案：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志 文件控制块一般包括的内容 文件名 文件类型 物理地址 文件大小 最近访问日期 最近修改日期 文件主标识 访问权限 16 24. 临界资源 答案：一次仅允许一个进程使用的共享资源。 25. 虚拟存储器 答案：虚拟存储技术是在主存和辅存之间，增加部分软件及必要的硬件支持，使主、辅之间的信息交换、程序的重定位、地址转换都能自动进行，从而主、辅存形成一个有机的整体，这种存储器的概念成为虚拟存储器。 26. 死锁 答案：两个以上的进程相互等待一个永远不可能发生的条件出现，这种僵 27. 页表 答案：页式存储管理使用的数据结构，主要用于逻辑地址到物理地址的映射。 二、判断题（每题1分，共6分） 23、由于P、V操作描述同步、互斥等问题的能力不足，所以有必要引入其 它的通讯原语或机制，如send， receive或Monitor等。 （） 24、信号量是只允许由P/V操作进行访问和修改的数据结构。 （） 25、在请求页式存储管理中，页面淘汰所花费的时间不属于系统开销。（） 26、预防死锁就是破坏死锁存在的某个必要条件。（） 27、磁盘是一类典型的字符设备。 （） 二十二、 简答题（每题5分，共20分） 15、 如果普通用户程序可以自行修改页表，会产生什么问题？ 答案：页表用于完成地址映射。如果用户可以修改页表，那么该用户就可以访问任何地址，从而产生安全问题。 16、 进程与线程之间有何区别？ 答案： 进程是操作系统中并发单元，也是能分得资源的最小单位。线程是在进程内部活动的并发单元，它只是进程行为的一条的执行路线，它能使用的资源仅限于它所在的进程范围之内，惟一能通过线程获得的资源就是使用处理机的时间片。有时也把线程称为轻量级进程。 17、 简述并比较SCAN（扫描）磁盘调度算法与最短寻道时间优先算法。 答案：最短寻道时间优先算法选择访问磁道与当前磁头所在磁道距离最近的进程，容易产生饥饿现象。SCAN优先考虑磁头移动方向（按照一个方向移动）。 18、 信号量的物理意义是什么？ 答案：信号量的值为正时，表示系统中某类资源的数量；为负时，表示等待进程个数。 17 二十三、 资源分配（共10分） 某计算机系统中有8 台打印机,有k个进程竞争使用,每个进程最多需要3 台打印机. 该系统可能会发生死锁的k 的最小值是多少？并说明理由。 答案：k=4. 分析：假设k=3，3 个进程共享8 台打印机，每个进程最多可以请求3 台打印机，若3个进程都分别得到2 台打印机，系统还剩下2 台打印机，接下去无论哪个进程申请打印机，都可以得到满足，3 个进程都可以顺利执行完毕，这种情况下不会产生死锁。假设k=4，4个进程共享8 台打印机，都得不到满足，产生了互相等待，可能会发生死锁。 二十四、 进程同步（共15分） (7) 写出P、V操作的定义。（5分） (8) 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时， 若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。试用PV操作同步顾客和营业员的活动过程。（10分） 答案： (1) S为一个信号量，P、V操作可描述为： P(S): while S<=0 do skip S := S-1; V(S): S := S+1; (2) 程序结构2分 信号量初值2分 程序逻辑6分 二十五、 存储管理（15分） 某计算机提供给用户232字节的虚拟存储空间，虚拟存储器采用一级页表实现，页面大小是4K字节。某进程的页表内容如下表所示，操作系统最多为进程分配2页物理内存，采用最近最少使用置换算法(LRU)和局部淘汰策略。设又虚地址访问序列2111H、191AH、2315H，请问： （3） 进程页表占用多少内存空间？请说明理由。（5分） （4） 191AH的物理地址是多少？请说明理由。（10分） 页号 页框号（物理块号） 特征位（存在位） 0 10H 1 1 0 2 41H 1 答： （1）4MB （2）物理地址为1091AH。 虚地址191AH被分成两部分，页号P=1，页内偏移D=91AH。由于进程工作集为 18 2，需要替换第0页，因此191AH的对应的物理块号为10H。物理地址为10H*4K+91AH=1091AH。 二十六、 并发问题（10分） 下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之： cobegin var x：integer； procedure P1 procedure P2 var y，z：integer； var t，u：integer； begin begin x：=1； x：=0； y：=0； t：=0； if x1 then y：=y+1； if x1 then t：=t+2； z：=y； u：=t； end end coend 答：不能正确运行。例如：先执行完整个P1，再执行P2，那么P1中y的值为1。但是如果执行到P1：x:=1;时，切换到P2执行，然后再执行P1，那么那么P1中y的值为0。同样条件的两次运行，其结果是不确定的。 有很多种改正方法，下面是一个例子。 cobegin var empty: semaphore := 0； var x：integer； procedure P1 procedure P2 var y，z：integer； var t，u：integer； begin begin P(empty); x：=1； x：=0； y：=0； t：=0； if x1 then y：=y+1； if x1 then t：=t+2； z：=y； u：=t； V(empty); end end coend 《操作系统》试卷2012 一、 名词解释题（每题4分，共24分） 1、 并发与并行 2、 临界资源与临界区 3、 系统调用 19 4、 进程互斥 5、 中断屏蔽 6、 目录 二、 判断题（每题1分，共6分） 1、 用P、V操作可以解决一切互斥与同步问题。（ T ） 2、 同一进程或不同进程内的线程都可以并发执行。（ T ） 3、 采用多道程序设计技术的计算机系统，极大地提高了计算机系统的系统效率，但可能使每个作业的执行时间延长。（ T ） 4、 作业调度的先来先服务算法，按照作业到达的先后次序调度作业，排队等待时间最长的作业被优先调度。（ F ） 5、 采用SPOOLing技术实现的共享设备，在同一时刻可以让多个进程使用它进行I/O。（ F ） 6、 设备性（或无关性）是指能实现设备共享的一种特性。（ F ） 三、 简答题（每题5分，共20分） 1、 何谓缓冲区？为什么要引入缓冲？ 2、 什么是死锁？产生死锁的必要条件是什么？ 3、 DMA方式与中断方式有何不同？ 4、 什么是重定位？如何实现程序运行时的动态重定位？ 四、死锁检测（10分） 设有进程,下表所示： 进程 申请资源申请资源释放资源 进程 申请资源申请资源释放资源 并发执行，都需要使用资源 , ，使用资源情况如 试判断是否会产生死锁，并说明原因。 五、设备管理（10分） 有5个记录A,B,C,D，存放在某磁盘的某磁道上，假定这个磁道划分成5块，每块存放一个记录，安排如下表所示： 20 块号 记录号 1 A 2 B 3 C 4 D 5 E 现在要顺序处理这5个记录，若磁盘旋转一周需要20ms，处理程序每读出一个记录后要花费6ms进行处理。处理程序处理数据时，磁盘照常旋转。 问： （1）处理完这5个记录需要的总时间是多少？ （2）为了减少磁盘的旋转周数，应该如何安排这5个记录，并计算所需要的时间。 六、 进程同步（15分） 有一个超市，最多可容纳N个人进入购物，当N个顾客满员时，后到的顾客在超市外等待；超市中有1个收银员。可以把顾客和收银员看作两类进程，两类进程间存在同步关系。请利用P、V操作描述这些进程之间的同步关系。 七、 存储管理（15分） 设某计算机的逻辑地址空间和物理地址空间均为KB，按字节编址。操作系统最多为一个进程分配4页物理内存，页的大小为1KB，并采用固定分配局部置换策略。在时刻260前，某进程内存分配与访问情况如下表所示： 页号 页框号 装入时间 访问时间 0 1 2 3 7 4 2 9 130 230 200 160 250 230 240 245 当该进程执行到时刻260时，要访问逻辑地址17CA H。请回答下列问题： (1)、该逻辑地址对应的页号是多少? (2)、若采用先进先出(FIFO)置换算法，计算该逻辑地址对应的物理地址?要求给出计算过程。 (3)、采用最近最久未使用(LRU)置换算法，计算该逻辑地址对应的物理地址?要求给出计算过程。 21 参： 一、 名词解释题 1、 并行：指多个任务在多个处理机上正在同时运行。 并发：指多个任务在单处理机下分时运行。 2、 临界资源：指一次仅允许一个进程使用的资源。 临界区：指访问临界资源的那段程序。 3、 系统调用：在操作系统核心设置的一组用于实现各种系统功能的子程序（过程）。 4、 进程互斥：指在多道程序环境中，每次只允许一个进程对临界资源进行访问。 5、 中断屏蔽：指在中断请求产生之后，系统用软件方式有选择地封锁部分中断而允许其余部分的中断仍能得到响应。 6、 目录：目录是保存目录结构信息的文件，在目录文件中保存着该目录所包含的目录或文件记录，每个记录包括目录或文件的名字、大小、存储位置、存取权限及其他相关数据项。 二、 判断题 1、 正确 2、 正确 3、 正确 4、 错误 5、 错误 6、 错误 三、 问答题 1、 缓冲区是使用专用硬件缓冲器或在内存中划出一个区域用来暂时存放输入/输出数据的地方。 引入缓冲是为了匹配外设和CPU之间的处理速度，减少中断次数和CPU的中断处理时间。 2、 死锁：两个以上的进程相互等待一个永远不可能发生的条件，这种僵持的局面成为死锁。 死锁产生的必要条件：互斥条件；不剥夺条件；请求和保持条件；循环等待条件。 3、 DMA方式与中断方式的不同点： 1) 中断方式在每个数据传送完后中断CPU，而DMA方式则是在所 要求传送的一批数据全部传送结束时中断CPU； 2) 中断方式的数据传送是在中断处理时由CPU控制完成，而DMA 方式则是在DMA控制器的控制下完成。 22 4、 所谓重定位是把作业的地址空间中的相对地址转换成内存空间的物理地址的调整过程。 在程序实际运行前，由操作系统把程序在内存的开始地址送入重定位寄存器；在程序运行期间，凡遇到访问内存的操作，就由硬件机制自动把用户程序的相对地址加上重定位寄存器的内容，相加之和就是实际访问内存的有效地址。 四、死锁检测 这一段过程，在不同的运行推进速度下，就可能产生死锁。如按顺序：先申请资源得到，然后先申请资源也得到，过一会又申请资源，则因正占用而阻塞，等待释放；而接着申请资源又因占用而阻塞、等待。和两个进程都因申请不到所需的资源而处于阻塞状态，都不能执行下去，相互等待对方释放资源，从而形成死锁。如改变进程的运行顺序，这两个进程是不会有死锁的。 五、设备管理 （1）所需要的总时间为：20ms*5+6ms=106ms。因为每转过一个记录需要20ms/5=4ms，每读出一个记录后需要6ms的处理时间，等处理完再处理下一个记录时，只能等到下一周。所以，每旋转一周读出一个记录，每读出第5个记录时，第5周刚好转完，因此，需要另外加6ms。 （2）为了减少磁盘旋转的周数，将记录安排改进为：块号1,2,3,4,5分别存放记录A,C,E,B,D。总时间是4ms*3*4+4ms+6ms=58ms。 六、进程同步 同步信号量：client，等待付款的顾客数量，初值为0， 同步信号量：wait，等待收银员完成工作，初值为0, 信号量：empty,超市还可容纳的顾客的个数，初值为N。 Var client, casher, empty: semaphore; Client:=0; wait:=0; empty:=N; 收银员: begin while true do begin P(client) 收银 V(wait) End 23 End 顾客i: begin while true do begin P(empty) 进入店内购物 V(client) P(wait) 付钱 V(empty) End End 七、存储管理 (1)17CAH转换为二进制为：0001 0111 1100 1010,页的大小为1KB，所以页内偏移为10位，于是前6位是页号，所以其页号为0001 01，转换为10进制为5，所以，17CA对应的页号为5。 (2)若采用先进先出置换算法，则被置换出的页号对应的页框号是7，因此对应的二进制物理地址为：0001 1111 1100 1010，转换为16进制位的物理地址为1FCAH。 (3)若采用LRU，应该置换的页框号是4，因此对应的二进制物理地址为：0001 0011 1100 1010，转换为16进制物理地址为13CA H。 24 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- fupindai.com 版权所有 赣ICP备2024042792号-2
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务