操作系统概念题库及答案解析

1、进程Pl和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后才能执行

P2的代码段S2为描述这种同步关系

（1）：试设计相应的信号量

（2）：给出信号量的初始值

（3）：给出进程P1和P2的结构

答：

（1）信号量申明为：

Typedefstruct{

Intvalue;〃表示资源数量

structPCB*L〃信号量等待队列

Jsemaphore

设信号量semaphoresynch;

(2)初始值为：synch.value=O

进程P1和P2的结构为

Pl：{P2:{

SIwait(synch);

Signal(synch);S2

})

2、|一个理发店有一间配有N个椅子的等待室和一个有理发椅的理发室。如果没有顾客，理

发师就睡觉;如果顾客来了而所有椅子都有人,顾客就离去；如果理发师在忙而又空的椅子，

顾客就会坐在其中一个椅子上；如果理发师在睡觉，顾客会摇醒他。

（1）给出同步关系，设计描述同步关系的信号量

（2）给出满足同步关系的进程结构（清完成满足同步关系的进程结构）

（对于同步关系和信号量进行深一步的研究）

（3）给出满足同步关系的进程结构（清完成满足同步关系的进程结构）

答：

（1）顾客的同步关系为：

a、顾客来的时候要等空的椅子，否则不进理发室。

b、座椅上的顾客要等理发椅空才有可能和别的顾客竞争理发椅，如果顾客坐上理发椅，就

要腾空座位给新来顾客，同时叫理发师理发。

c、一个顾客理发完后，就要让别的等待顾客有机会理发。

理发师的同步关系为：一旦被顾客唤醒就给顾客理发，之后睡觉。

（2）信号量定义如下：

Typedefstruct{

Intvalue;〃表示资源数量

structPCB*L〃等待队歹U

}semaphore

互斥信号量定义如下：

Typedefstruct{

boolflag;

structPCB*L

Jbinarysemaphore

(3)顾客和理发师进程分别为：

customer{barber(

wait(chair);do{

waitinginthechair;wait(hair_cut);

wait(barber_chair);cutinghair;

signal(hair_cut);signal(barber__chair);

sittinginbarberchairforhaircut;}while(l)

signal(chair);)

)

3、有一个将页表存放在内存的分页系统：

（1）页表分页的目的是什么

（2）如果一次内存访问需要200ns,访问一页内存要用多长时间

（3）如果假如TLB,并且75%的页表引用发生在TLB,内存有效访问时间是多少

（考察分页和访问内存的有关知识）

答：

（1）分页的页表可以变得足够大简化内存分配问题，确保当前未使用的部分页表可以交换

（2）400ms

（3）0.75*200ms+0.25*400ms=250ms

4、如果有内存块100KB、500KB、200KB>300KB,600KB,放置大小分别为212KB、417KB、

112KB、426KB的进程

（1）首次适应算法将如何放置

（2）最佳适应算法将如何放置

（3）最差适应算法将如何放置

（4）哪一种算法的内存利用率最高

（考察三种适应算法）

答：

（1）首次适应算法：212K放入500K；417K放入600K；112K放入288K；426K等待

（2）最佳适应算法：212K放入300K；417K放入500K；112K放入200K；426K放入600K

（3）最差适应算法：212K放入600K；417K放入500K,112K放入300K；425K等待

（4）最佳适应算法充分利用了内存空间

5、考虑下列进程集，进程占用的CPU区间长度以毫秒来计算:

进程区间时间优先级

P1103

P211

P323

P414

P552

假设在时刻0以进程Pl、P2、P3、P4、P5的顺序到达

（1）用FCFS、SJF、非抢占优先级和RR算法下的周转时间是多少

（2）每个进程在四种调度算法下的等待时间是多少

（3）哪一种调度算法的平均等待时间对所有进程而言最小

答：

(1)

FCFSRRSJF非抢占优先级

P110191916

P211211

P3137418

P4144219

P5191496

(2)FCFSRRSJF非抢占优先级

P10996

P210100

P3115216

P4133118

P514942

(3)SJF

6、假定要在一台处理器上执行如下图所示的作业，它们在0时刻以1,2,3,4,5的顺序

到达。给出采用下列调度算法时的调度顺序、平均周转时间(turnaroundtime)和平均响应时

间(responsetime)

(1)先到先服务调度算法FCFS

(2)非抢占式SJF(shortestjobfirst)

(3)非抢占式优先级调度(数字小的优先级大)

作业执行时间优先级

P1103

P211

P322

P434

P552

答：

画出调度顺序

(1)FCFS:

PlP2P3P4P5

01011131621

平均响应时间=(0+10+11+13+16)/5=10

平均周转时间=(10+11+13+16+21)/5=14.2

(2)SJF

P2|P3|P4|P5|P1

01361121

平均响应时间=(11+0+1+3+6)/5=4

平均周转时间=(21+1+3+6+11)/5=8.4

(3)Priority

|P2P3

01381821

平均响应时间=(8+0+1+18+3)/5=6

平均周转时间=(18+1+3+21+8)/5=10.2

7、磁盘请求以10、22、20、2、40、6、38柱面的次序到达磁盘驱动器。移动臂移动一个

柱面需要6ms,实行以下磁盘调度算法时，各需要多少总的查找时间？假定磁臂起始时定

位于柱面20o

(a)先来先服务;

(b)最短查找时间优先；

(c)电梯算法(初始由外向里移动)。

答：

(a)先来先服务时，调度的顺序是20-lOf22f20f2f40-6-38,总共划过的柱面数

是：

10+12+2+18+38+34+32=146

因此，总的查找时间为：146X6=876ms。

(b)最短查找时间优先时，调度的顺序是20f22flOf6-2-38—40(由于磁臂起始时

定位于柱面20,所以可以把后面第20柱面的访问立即进行)，总共划过的柱面数是：

2+12+4+4+36+2=60

因此，总的查找时间为：60X6=360ms。

(c)电梯算法(初始由外向里移动)时，调度的顺序是20f22f38f40-10-6f2(由

于磁臂起始时定位于柱面20,所以可以把后面第20柱面的访问立即进行)，总共划过的柱

面数是：

2+16+2+30+4+4=58

因此，总的查找时间为：58X6=348ms。

8、考虑下面一组进程，进程占用的cpu区间长度以毫秒来计算:

进程区间时间优先级

P1103

P211

P323

P414

P552

假设在。时刻进程以Pl、P2、P3、P4、P5的顺序到达.

a、每个进程在每种调度算法下的周转时间是多少？

b、每个进程在每种调度算法下的等待时间是多少？

c、哪种调度算法的平均等待时间最小（对所有的进程）？

答：

a.周转时间

FCFSRRSJF非抢占优先级

P110191916

P211211

P3137418

P4144219

P5191496

b.等待时间

FCFSRRSJF非抢占优先级

P10996

P210100

P3115216

P4133118

P514942

C、SJF

9、分别写出读者优先问题中读者与写者的进程结构:

答案：

写者进程结构

do{

wait(wrt)

//writingisperformed

signal(wrt)

}while(TRUE)

读者进程结构

do{

wait(mutex)

readcount++;

lf(readcount==l)

wait(wrt);

signai(mutex);

//readingisperformed

wait(mutex);

readcount-;

lf(readcount==0)

signal(wrt);

signal(wrt);

}while(TRUE)

10、假设有如图所示的交通死锁情况：

a.说明什么是死锁

b.证明这个例子中实际上包括了死锁发生的4个必要条件

c.给出一个简单的规则使这个系统避免发生死锁

,2

成状位循观,1,1业也

定4

造锁的是中,。的作址

就规0,2故

而死上形2示地

信于路后图地为第=，对

表方

通处待最确号的致绝

道从来次。

此统等据。易明块存一的

）果，位8位

彼系环占占容主0小2存

于称循如块2的大1主

车抢很6到2

由时）辆也口5配用/的占，

程4非路

者此（一件2分应方块应始

进是字成次

或。占示条被址分分开

去锁就十分0

源抢表（的,地2存部0

资下死待个被3存址从

非开待,的主

争进为等等一,主与地号

称）动入M22

竞推3并移环,而为该内编

法程（进11

于有置循为因度应页的

由无进待占。得,，的块

，。位量0。长小

将的等展不方大中，

中置前容为？址的）

都待并发车次的址

程位当存号示地块节

们等有前汽0页地

过相间上，主页表始2一字

它占向分辑K

行，互空路是，其来起的每

）车，息逻4（

执用在2个道汽则中位的2而

§AH.（页？信，节

在作远一从的规统少中于因

斥4示业是

程力永的能后的系多块等，字

互上的占表？用存块作于个

进外些不随锁M，。

）路理间来少应主166

的无这车待死5中节9

，1（道。管空位多移在而20

上若辆等通,统字4

，锁：据交储址少是偏页成

以一车交系个为

象死件占。相存地多度内一M分

个个种1的6小

两现了条车进生式的用长页每被9

每这为理0大

或的生要辆前产页业该的的的间4

为免量管的

个塞产必一待避会分作：应页中中空为

因容。存块

两阻统个有等，的不用某答址一址业存应

9。存节储存

指种系4只且待。单就采回地每地作主度

5主字式主

是一或的是并等到简样某5。存业辑出的6长

2于9页为

锁的态锁件置环察个这设中主作逻写M0的

.））））由14在因

：死死条一假.块=页

...51234：））））

答b的.、.（（（（12方一

ac1.,答（（3（4（

斥121次每

互

是从0开始的，故每个主存块的起始地址为：块长*块号=4K*块号。现作业被分成四页（页

号为0,1,2,3）且分别装入第2,4,1,5块中，那么，这四页信息所在主存块起始地址应依次为：

8K,16K,4K,20K。

12、一个请求分页系统中，采用FIFO、最近最久未使用，假如一个作业的页面走向为4、3、

2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理版块书M分别为3和4时，试计

算在访问过程中所发生的缺页次数和缺页率。并比较所得结果。

答案：

（1）分配给该作业3个物理块时，采用FIFO页面替换算法，执行过程中页面置换如下表:

432143543215

444111555

3344422

2223331

f⑷f⑶f(2)f(l)f(4)f⑶

上表中，第一行为进程执行时要访问的页面次序，第二行为最先调入主存的页面，最后一行

为发生缺页中断时替换的页面。所以缺页次数为9,缺页中断率为9/12。

（2）分配给该作业4个物理块时，采用FIFO页面替换算法，执行过程中页面置换如下表:

432143543215

4444555511

333344445

22223333

1111222

f(4)f(3)f(2)f(l)f⑸f(4)

上表中，第一行为进程执行时要访问的页面次序，第二行为最先调入主存的页面，最后一行

为发生缺页中断时替换的页面。所以缺页次数为10,缺页中断率为10/12。

结果分析：多分配一个物理块没有减少缺页次数。

（3）分配给该作业3个物理块时，采用LRU页面替换算法，执行过程中页面置换如下表:

432143543215

4441115222

333444411

22233335

f(4)f(3)f(2)f(l)f⑸f(4)f(3)

缺页次数为10，缺页中断率为10/12。

分配给该作业4个物理块时，采用LRU页面替换算法，执行过程中页面置换如下表:

432143543215

44444445

3333333

225511

11222

f(2)f⑴f⑸f⑷

缺页次数为8,缺页中断率为8/12。

结果分析：多分配一个物理块可以有效减少缺页次数。

13、有5个任务A、B、C、D、E,它们几乎同时到达，预计它们的运行时间为10、6、2、

4、8min。其优先级分别为3、5、2、1和4,这里5为最高优先级。对于下列每一种调度算

法，计算其平均进程周转时间。

(1)先来先服务(按ABCDE)算法。

(2)优先级调度算法。

(3)时间片轮转算法。(时间片为2分钟)

答案：

(1)采用先来先服务调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如

下表所示：

执行次序运行时间优先数等待时间周转时间

A103010

B651016

C221618

D411822

E842230

T=(10+16+18+22+30)/5=19.2min。

(2)(2)采用最高优先级调度算法时，5个任务在系统中的执行顺序、完成时间及周转时

间如下表所示：

执行次序运行时间优先数等待时间周转时间

B6506

E84614

A1031424

C222426

D412630

T=(6+14+24+26+30)/5=20min«

(3)采用时间片轮转算法，令时间片为2分钟，5个任务轮流执行的情况为：

第一轮：(A,B,C,D,E)

第二轮：(ABD.E)

第三轮:(A,B,E)

第四轮:(A,E)

第五轮：(A)

丁1=30!71访、12=22|11而、T6=6|71而、丁4=16111同、丁5=28|71而。平均时间T=(30+22+6+16+28)/5=20.4min。

14、在单CPU和两台I/O(11,12)设备的多道程序设计环境下，同时投入三个作业运行。它

们的执行轨迹如下：

J0P1：12(30ms)、CPU(10ms)、11(30ms)、CPU(10ms)

JOB2:I1(20ms)、CPU(20ms)、12(40ms)

JOB3:CPU(30ms)、11(20ms)

如果CPU、11和12都能并行工作，优先级从高到低为jobl、job2和job3,优先级高的作业

可以抢占优先级低的作业的CPU。试求：

(1)每个作业投入到完成分别所需要的时间.

(2)从作业的投入到完成CPU的利用率。

(3)I/O设备利用率。

答案：

(1)jobl：80ms；job2:90ms；job3:90ms«

(2)CPU空闲时段为：60ms至70ms,80ms至90ms。所以CPU得利用率为(90-20)

/90=77.78%»

(3)设备11空闲时间段为：20ms至40ms,故II的利用率为(90-20)/90=77.78%。设备12

空闲时段为:30ms至50ms,故12的利用率为(90-20)/90=77.78%。

15、在一个分页存储管理系统，页面大小为4KB。已知某进程的第0、1、2、3、4页一次存

在内存中的6、8、10,14、16物理块号中，现有逻辑地址为12138B、3A5CH、分别求其所

在的页号，页内相对地址，对应的物理块号以及相应的物理地址并描述逻辑地址和物理地址

的区别。

答案：

(1)物理地址就是唯一的，按照物理硬件定义的地址；

逻辑地址就是认为规定的，方便通讯的而定义的地址

(2)已知页面大小4KB=4096D,页号p=2,页内位移d=3946D。查页表可知页号2对应物

理块为10.由地址转换原理可得：块内位移等于页内位移。所以物理地址

=10*4096+3946=449068o

(3)已知页面大小为4KB=4096D,逻辑地址3A5cH=14940D。页号p=3,页内位移d=2652D,

查表可知页号3对应物理块号为14o由地址转换原理可得：块内位移等于页内位移。所以

物理地址=14*4096+2652=59996D。

16、假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384

个磁盘块的空闲状态。

(1)请说明在上述条件下如何进行磁盘块空闲状态管理。

(2)设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均

移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号大的方向移动，磁道

号请求队列为50、90、30、120,对请求队列中的每个磁道需读取1个随机分布的扇区，则

读完这4个扇区点共需要多少时间？要求给出计算过程。

(3)如果将磁盘替换为随机访问的Flash半导体存储器(如U盘、SSD等)，是否有比CSCAN

更有效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

答案：

(1)可采用位示图法表示磁盘块的空闲状态，一个磁盘块在位示图中用一个二进制位表示，

为0表示磁盘块空闲，为1表示磁盘块已分配。16384个磁盘块共占用

16384bit=16384/8B=2048B=2KB,正好可放在系统提供的内存中。

(2)采用CSCAN调度算法，磁道的访问次序为120305090,如下图所示：

因此访问过程中移动的磁道总数为(120-100)+(120-30)+(90-30)=170,故总的寻道

时间为170*lms=170ms；100120903050由于每转需要1/6000分钟=10ms,则平均旋转

延迟时间为10ms/2=5ms,总的旋转延迟时间为5ms*4=20ms；由于每个磁道有100个扇

区，则读取一个扇区需要10ms/100=0.1ms,总的读取扇区时间(传输时间)为

0.1ms*4=0.4ms；综上，磁盘访问总时间为170ms+20ms+0.4ms=190.4ms。

(3)采用FCFS(先来先服务)调度策略更高效。因为Flash半导体存储器的物理结构不

需要考虑寻道时间和旋转延迟时间，可直接按I/O请求的先后顺序服务。

17、某文件系统为一级根目录结构，文件的数据一次性写入磁盘，已写入的文件不可修

改，但可多次创建新文件。请回答如下问题。

(1)在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。

(2)为定位文件数据块，需要在FCB中设置哪些相关描述字段？

(3)为快速找到文件，对于FCB,是集中存储好，还是与对应的文件数据块连续存储好？

要求说明理由。

答案：

(1)连续方式更合适。因为一次写入不存在插入问题，而且写入文件之后不需要修改，

连续的数据块组织方式很适合一次性写入磁盘不再修改的情况。同时连续存储相对链式

和索引省去了指针的空间开销，支持随机查找，查找速度最快。

(2)在连续方式中，为定位文件数据块，需要在FCB中设置文件在外存的起始地址(即

首个盘块号)及文件的长度(即文件占用的盘块数)。

(3)FCB集中存储较好。FCB中存放了关于描述和控制文件的重要信息，同时是文件目

录的重要组成部分，在检索文件时，通常会访问文件的FCB。如果将FCB集中存储，可

减少检索文件时访问磁盘的次数，提高文件的访问速度.

18、某系统有A、B、C、D四类资源可供五个进程Pl、P2、P3、P4、P5共享。系统对这

四类资源的拥有量为:A类3个、B类14个、C类12个、D类12个。进程对资源的需求

和分配情况如下：

进程己占有资源最大需求数

ABCADBCD

P100102012

P210010750

P313524356

P406302652

P500104656

按银行家算法回答下列问题：

(1)现在系统中的各类资源还剩余多少？

(2)现在系统是否处于安全状态？为什么？

(3)如果现在进程P2提出需要A类资源。个、B类资源4个、C类资源2个和D类资

源0个，系统能否去满足它的请求？请说明原因。

答案：

(1)A：1；B：5；C：2；D：0

(2)need矩阵为：P10000

P20750

P31002

P40020

P50642

存在安全序列，如PLP3,P4,P5,P2,所以安全

（3）能，因为试探分配后，可用资源为1,1,0,0。可找到安全序列，所以可分配

19、考虑RR调度算法的一个变种，在这个算法里，就绪队列里的项是指向PCB的指针。

⑴.在就绪队列中如果把两个指针指向同一进程，会有什么效果？

⑵.这个方案的两个主要优点和两个主要缺点是什么？

⑶.如何修改基本的RR调度算法不用两个指针达到同样的效果？

答案：

（1）实际上，这个过程将会增加他的优先权，因为通过得到时间它能够优先得以运行。

（2）优点是越重要的工作可以得到更多的时间。也就是说，优先级越高越先运行。然而，

结果将由短任务来承担

（3）分配一个更长的时间给优先级越高的程序。换句话说，可能有两个或多个时间片在RR

调度中。

20、现有一台16位字长的专用机，采用页式存储管理。主存储器共有4096块（块号为。〜

4095）,现用位示图分配主存空间。试问：

（1）该位示图占用几个字？

（2）主存块号3999对应位示图的字号和位号（均从0开始）各是多少？

（3）位示图字号199,位号9对应主存的块号是多少？

答案：（1）256

（2）24915

（3）3193

21、设某计算机系统有一个CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪

就绪状态，且进程A先得到CPU运行，进程B后进行。进程A先得到CPU运行，进程B后

进行。进程A的运行轨迹为：计算50ms,打印信息100ms,再计算50ms,打印信息100ms,

结束。进程b的运行轨迹为：计算50ms,输入数据80ms,再计算100ms,结束。

（1）开始运行后，cpu有无空闲等待？若有，在哪段时间内等待？计算CPU的利用率。

答：有，在100~150ms等待，利用率=[300-（150-100）]/300*100%=89.3%

（2）进程A运行时有无等待现象？若有，在什么时候发生等待现象？

答：无

(3)进程B运行时有无等待现象？若有，在什么时候发生等待现象？

答：有，在0~50ms,180~200ms时发生等待现象。

22、有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用

抢占式优先级调度算法。作业的运行情况见表2-1,其中作业的优先数即为进程的优先数,

优先数越小，优先级别越高。

作业名到达时间运行时间优先级

18：0040分钟5

28：2030分钟3

38：3050分钟4

48：5020分钟6

表2-1

(1)列出所有作业进入内存的时间

答：1、8：002、8：203、9：104、8：50

(2)列出所有内存结束的时间