操作系统复习资料1

⼀、关于PV操作1.投篮问题：

A，B两组学⽣进⾏投球⽐赛，规定A组(或B组)的⼀个学⽣投了⼀个球后应让B组(或A组)的⼀个学⽣投⼀个球。假定让A组的学⽣先开始投球，⽤PV操作控制时，回答如下问题：(1)应定义的信号量的个数和初值：定义两个信号量，初值分别为1和0，即s1∶=1 s2∶=0(2)在两组⼯作流程的⽅框位置填上适当的P、V操作，使其能按规定进⾏。A组： B组：P (S1) P（S2）

投⼀个球投⼀个球 V（S2） V（S1）2.⽤信号量实现司机和售票员的同步。

解：设S1和S2分别为司机和售票员的私⽤信号量，初值均为0，则司机和售票员的同步过程描述如下：

3.数据采集和打印

某数据采集系统由两个进程组成，进程R负责采集数据，并把采集到的⼀批数据存⼊缓冲器B中，进程W把缓冲器B中的数据取出后打印输出。假定每次采集的数据长度不变且缓冲器B正好可以容纳采集到的数据。现采⽤PV操作来协调进程R、W的并发执⾏，请回答下列问题：(1)应定义的信号量及初值S1=1, S0=0。

(2)进程的程序如下，请在⽅框位置填上适当的P、V操作，使两进程能正确并发执⾏。

4．设进程A、B是两个相互合作的进程，共⽤⼀个缓冲区。进程A从卡⽚输⼊机读⼊卡⽚送到缓冲区，进程B取⾛缓冲区中卡⽚信息进⾏加⼯。进程A在完成将卡⽚送⼊缓冲区后，给进程B发⼀个信号。进程B收到信号后，取⾛卡⽚信息进⾏处理。反之，进程B取⾛卡⽚信息后，给进程A发⼀个信号，进程A再将卡⽚信息读⼊缓冲区。为此我们⽤两个私⽤信号量S1和S2，其初值均为0，S1表⽰缓冲区是否有卡⽚信息，S2表⽰缓冲区信息是否被取⾛。利⽤P、V操作实施进程A、B的同步过程如下：

5.假定⼀个阅览室可供50个⼈同时阅读。读者进⼊和离开阅览室时都必须在阅

览室⼊⼝⼊的⼀个登记表上登记，阅览室有50个座位，规定每次只允许⼀个⼈登记或注销登记。要求：

（1）⽤PV操作描述读者进程的同步算法（可⽤流程图表⽰，登记、注销可⽤⾃然语⾔描述）；

（2）指出流程图中所⽤信号量的名称、作⽤及初值。答：S1=50,S2=1⼆、 调度算法平均周转时间：带权周转时间：W =T/TS1. 先来先服务调度算法

↘ n i Si i T T n W 11↘ i i i T n T 11

1.有四道作业，其提交时间和计算时间如下表：作业提交时间计算时间（⼩时）J1 10：00 2J2 10：30 1J3 10：50 1.5J4 11：00 0.5

按“先来先服务算法”将各个作业的开始时间，完成时间，周转时间分别填⼊下⾯的表中。（短作业优先、响应⽐⾼优先）作业开始时间完成时间周转时间1 10.0 12.0 22 12.0 13.0 2.53 13.0 14.5 3.34 14.

5 15.0 4

2.在单道批处理系统中，有四个作业进⼊系统，进⼊时间及所需计算时间如下表所⽰。现忽略作业调度所花时间。当第⼀个作业进⼊系统后就可开始调度。作业进⼊时间所需计算时间1 8∶00 2⼩时2 8∶30 30分钟3 9∶00 6分钟4 9∶30 12分钟

（1）将分别采⽤“短作业优先”和“响应⽐最⾼者优先”调度算法时，各个作业的开始时间，完成时间，周转时间分别填⼊下⾯的表中。短作业优先 响应⽐最⾼者优先作业 开始时间

完成时间 周转时间 开始时间 完成时间 周转时

间 1 8.0 10.0 2 8.0 10.0 2.0 2 10.3 10.8 2.3 10.1 10.6 2.1 3 10.0 10.1 1.1 10.0 10.1 1.1 410.110.30.810.610.81.3

（2）采⽤“短作业优先”调度算法时，平均周转时间为 1.55 。 采⽤“响应⽐最⾼者优先”调度算法时，平均周转时间为 1.625 。≥1

先来先服务调度算法计算结果最短作业优先作业算法计算结果要求服务时间要求服务时间

等待时间优先权+=)(Rp作业进⼊时间

估计运⾏时间 （分钟） 开始时间 结束时间周转时间 （分钟） 带权周转时间 JOB1

8：00 120 8：00 10：00 120 1 JOB2 8：50 50 10：00 10：50 120 2.4 JOB3 9：00 10 10：50 11：00 120 12 JOB49：50 20 11：0011：20

90 4.5 作业平均周转时间 T = 112.5 作业带权平均周转时间 W = 4.97545019.9作业进⼊时间

估计运⾏时间 （分钟） 开始时间 结束时间周转时间 （分钟） 带权周转时间

JOB1 8：00 120 8：00 10：00 120 1 JOB2 8：50 50 10：30 11：20 150 3 JOB3 9：00 10 10：00 10：10 70 7 JOB49：50 20 10：1010：30

40 2 作业平均周转时间 T = 95 作业带权平均周转时间 W = 3.2538013

最⾼响应⽐优先作业算法计算结果三、找安全序列

1.在系统中仅有m 个同类资源，由n 个进程互斥使⽤。如果每个进程对该类资源的最⼤需求量为w,那么当m,n,w 分别取下表列出的值时，问在表中(a) ~ (e)各种情况下，哪种可能发⽣死锁？如果可能死锁，请举例说明：

答：C 因为c 中2个进程每个进程都只占有⼀个，那么系统就没有更多的资源了，因此它们就相互等待了，⽽进⼊了死锁。作业进⼊时

间 估计运⾏时间 （分钟）

开始时间 结束时间 周转时间 （分钟） 带权周转时间 JOB1 8：00

120 8：00 10：00 120 1 JOB2

8：50 50 10：10 11：00 130 2.6 JOB3 9：0010 10：00 10：10 70 7 JOB49：50 20 11：00 11：20 90 4.5作业平均周转时间 T=102.5 作业带权平均周转时间 W = 3.775 41015.1

2.某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银⾏家算法能安全分配吗？请说明分配过程。

解答：系统能为进程P3分配剩余的2台打印机（3分）。因为尽管此时10台打印机已分配给进程P1 有4台，P2有2台和P3有4台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运⾏下去，能释放占⽤的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银⾏家算法是安全的。四、资源分配图的化简

没办法化简，系统不安全这就是答案 答题步骤：：1、检测有⽆环路；

2、环路中每个资源类中是否只有⼀个资源；3、在环路中查找⾮阻塞也⾮独⽴的进程4、此资源分配图⽆法化简，所以必定死锁

1.化简以下进程—资源图，判断系统是否处于死锁状态：P 1P 2R 1

R 2P 1P 2R 1R 2P 1P 2R 1R 2P 1P 2R 1R 2P 1P 2R 1R 2

2.资源分配图的化简

五、页⾯置换算法

先进先出算法（First In First Out）的基本思想是，总是先淘汰那些驻留在主存时间最长的页⾯，即先进⼊主存的页⾯先被淘汰最近最久未⽤置换算法(LRU)的基本思想是：如果某⼀页被访问了，那么它很可能马上⼜被访问；反之，如果某⼀页很久没有被访问，那么最近也不会再被访问。所以这种算法的实质是：当需要置换⼀页时，选择在最近⼀段时间最久未⽤的页予以淘汰。例1 设页⾯⾛向为P=4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5，主存容量M=3，置换算法采⽤FIFO，则缺页中断次数及缺页率按表4 - 4 给出。

例 2 设M=4，其余同例 1。缺页中断次数和缺页率如表 4-5 所⽰。表4-5 FIFO 性能分析例(M=4)

F=10 f=10/12=83%

例 3 设页⾯⾛向如上，M=3，置换算法为LRU ，则系统模型如表 4-6 所⽰。在表 4-6 中，由于采⽤LRU 算法，M 中各列按访问的时间顺序排列，最近被访问的页⾯在最前。由表 4-6 算出缺页中断次数F=10， 缺页率f=10/12=83%。表4-4 FIFO 性能分析例(M=3)表4-6 LRU性能分析例(M=3)

例4 设M=4，其余同例3，则系统性能模型如表4-7 所⽰。表4-7 LRU性能分析例(M=4)

1.在请求分页管理系统中, ⼀个程序的页⾯⾛向

为:1,2,3,4,1,3,4,2,5,2,4,1，设分配给该程序的存储块为4，分别采⽤FIFO算法和LRU页⾯置换算法，请计算缺页次数和缺页率。（1）采⽤先进先出（FIFO）调度算法，页⾯调度过程如下：

（2）采⽤最近最少使⽤（LRU）调度算法，页⾯调度过程如下：

1.在采⽤页式虚拟存储管理的系统中，某个⽤户作业依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，设分配给该作业的主存共300字，页的⼤⼩为100字，请按FIFO调度算法⽤表解法推算缺页中断次数，依次淘汰的页号和缺页中断率。

⾸先根据作业的主存共300字，页的⼤⼩为100字，得出来：每页的⼤⼩为：300/100=3；所以M=3剩下是2种答案都对

1、⼀共三页，从0开始数是0,1,2

115，228，120，88，446，102，321，432，260，1671 2 1 0 4 1 3 4 2 11 1 1 1 4 4 4 42 2

2 2 2 2 1 1 1 1 10 0 0 3 3 3 3

缺页中断次数：7 依次淘汰页号：1 2 0 4 缺页中断率：70%2、⼀共三页，从1开始数是1,2,3

115，228，120，88，446，102，321，432，260，1672 3 2 1 5 2 4 5 3 22 2 2 2 5 5 5 53 3

3 3 3 3 2 2 2 2 21 1 1 4 4 4 4

缺页中断次数：7 依次淘汰页号：2 3 1 5 缺页中断率：70% 3.某系统采⽤请求分页管理内存, 采⽤FIFO页⾯置换算法. 作业A的页⾯⾛向为5,1,2,3,4,3,5,4,2,3;内存块M=3, 试计算运⾏时的缺页率. 解：1 2 3 4 5 6 7 8 9 10 11 12时刻

P 4 3 1 3 2 4 2 3 5 2 6 3M 4＋3＋4 1＋34134－213－4＋21421－3＋4

2－5＋34－2＋53－6＋25－3＋62

F ＋＋＋＋＋＋＋＋＋F=9 f=F/12*100 %=75％六、磁盘调度算法

1.某硬盘系统，某时刻OS的相关模块收到系列柱⾯读写请求依次为{ 53,78,25,98,176,32,35,92 150,12 } 。

答：1. FCFS调度算法的访问序列为53,78,25,98,176,32,35,92 150,12。移动柱⾯距离＝（78－53）＋（78－25）＋（98－25）＋（176－98）＋（176－32）＋(35－32)+(92-35)+(150-92)+(150-12)=629

2.若⼲个等待访问磁盘者依次要访问的柱⾯为20，44，40，4，80，12，76，假设每移动⼀个柱⾯需要3毫秒时间，移动臂当前位于40号柱⾯，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。

答：（1）先来先服务算法；3毫秒×292=876毫秒

40 →20 →44 →4 →80 →12 →76

（20）（24）（4）（36）（76）（68）（64）共移动292柱⾯

（2）最短寻找时间优先算法。40 →44 →20→12 →4 →76 →80（4）（24）（8）（8）（72）（4）共移动120柱⾯

3.在⼀个请求分页系统中，采⽤FIFO页⾯置换算法时假如⼀个作业⾛向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M别是3和4时，试计算在访问过程中所发⽣的缺页次数和缺页率，并⽐较所得结果。解：M=3

●1 2 3 4 5 6 7 8 9 10 11 12●4 3 2 1 4 3 5 4 3 2 1 5●4 4 4 1 1 1 5 5 5 5 5 5● 3 3 3 4 4 4 4 4 4 2 2● 2 2 2 3 3 3 3 3 3 1●9,9/12=75%M=4

●1 2 3 4 5 6 7 8 9 10 11 12●4 3 2 1 4 3 5 4 3 2 1 5●4 4 4 4 4 4 5 5 5 5 1 1● 3 3 3 3 3 3 4 4 4 4 5● 2 2 2 2 2 2 3 3 3 3● 1 1 1 1 1 1 2 2 2●10,10/12=83%七、位⽰图

分页式存储空间的分配由于块的⼤⼩是固定的，可以⽤⼀张位⽰图

(Bit map)来构成主存分配表。现设主存有8192块，可⽤字长为32位的256个字作为位⽰图。若块号，字号，位号(从⾼位到低位)分别从0、0、0开始，试问5999块对应的字号和位号?99字的19位对应哪⼀块?

若块号、字号、位号从1,0,0●字号=INT（5999/32）=187=>186●位号=5999 mod 32=15=>14●99字19位对应：●99X32+19=3187●100X32+20=3220练习题：

如图所⽰，现有作业A须申请40K内存，写出选⽤以下各分配策略时，作业A的⾸地址和末地址，图中⽹格为占⽤区。

A. 最先适应法１００Ｋ～１４０ＫB. 最佳适应法３３０Ｋ～３７０ＫC. 最差适应法４１０Ｋ～４５０ＫD.单⼀连续分配１００Ｋ～１４０Ｋ选择题

1、采⽤动态重定位⽅式装⼊的作业，在执⾏中允许（C）将其移动。A、⽤户有条件地B、⽤户⽆条件地C、操作系统有条件地D、操作系统⽆条件地

2、分页式存储管理中，地址转换⼯作是由（A）完成的。A、硬件

B、地址转换程序C、⽤户程序D、装⼊程序

3.页式虚拟存储管理的主要特点是（B）A.不要求将作业装⼊到主存的连续区域B.不要求将作业同时全部装⼊到主存的连续区域C.不要求进⾏缺页中断处理D.不要求继续页⾯置换

4.在固定分区分配中,每个分区的⼤⼩是（C）A.相同

B.随作业长度变化C.可以不同但预先固定

D.可以不同但根据作业长度固定

5.段式存储管理中，每次从主存中取指令或取操作数，⾄少要(C)访问主存。A.0次B.1次C.2次D.3次

6.⽀持程序放在不连续内存中的存储管理⽅法有（CDE）A.可变式分区分配B.固定分区分配C.分页式分配D.分段式分配E.段页式分配

7.采⽤虚拟存储管理时，与运⾏作业的数量或⼤⼩有关的实体有(AB )等。A.主存B.辅存C.⾼速缓存D.页表

8.段式和页式存储管理的地址结构很类似，但是它们之间有实质上的不同，表现为（ABCD）A、页式的逻辑地址是连续的，段式的逻辑地址可以不连续B、页式的地址是⼀维的，段式的地址是⼆维的C、分页是操作系统进⾏的，分段是⽤户确定的

D、各页可以分散存放在主存，每段必须占⽤连续的主存空间E、页式采⽤静态重定位⽅式，段式采⽤动态重定位⽅式9、通道是⼀种（B）A.通⽤处理机B.专⽤处理机C.传输电⼦线路D.保存I/O信息的部件。

10、系统利⽤Spoiling技术实现(B)

A.对换⼿段B. 虚拟设备C.虚拟存储D.快速输⼊

11.下⾯关于DMA⽅式的描述，不正确的是。(C)

A. DMA⽅式使外设接⼝可直接与内存进⾏⾼速的数据传输B. DMA⽅式在外设与内存进⾏数据传输时不需要CPU⼲预C. 采⽤DMA⽅式进⾏数据传输时，⾸先需要进⾏现场保护D. DMA⽅式执⾏I/O交换要有专门的硬件电路12.设备按使⽤属性分为。(D)A.私有设备B.共享设备

C.实体设备和虚拟设备D.输⼊设备

13.许不同⽤户的⽂件可以具有相同的⽂件名，通常采⽤（D）证按名存取的安全。A、重名翻译机构B、建⽴索引表C、建⽴指针D、多级⽬录结构

14.物理记录和逻辑记录顺序⼀致的⽂件结构是(B)A.记录式⽂件B.顺序⽂件C.链接⽂件D.流式⽂件

15⽂件系统按名存取主要通过（A）实现的。A.⽂件⽬录B.⽰图C.地址表D.页表

16.对于磁盘⽽⾔，读写信息的单位是（A）。A.⽂件B.字节C. 块D. 字符E. 记录

17.逻辑⽂件不必存放在连续存储空间的存储结构有(C)。A.流式结构B.记录式C.链接式D.索引式。

18.属于⽂件管理⽅法的是(CE)。A.先来先服务算法B.作业控制语⾔C.⼝令核对法D.银⾏家算法E.⽤户权限

19.属于⽂件管理⽅式的是(BCD)。A. 后备队列B.⽬录树C.FAT表D.⽂件夹E.可变分区。