操作系统复习题集及答案.doc

- .
操作系统复习题集

三、简答题
1. 分页存储管理存在的局限性是什么?
逻辑地址空间：页是物理单位，共享困难、不便对代码进展分类管理，不能进展动态连接。

2. 多道程序系统为什么能提高CPU的利用率？
利用了原来CPU空闲等待时间

3. 文件的逻辑构造有哪些？
一种是无构造的流式文件，是指对文件信息不再划分单位，它是依次的一串字符流构成的文件；一种是有构造的记录式文件, 是用户把文件的信息按逻辑上独立的含义划分信息单位，每个单位称为一个逻辑记录〔简称记录〕。所有记录通常都是描述一个实体集的，有着一样或不同数目的数据项，记录的长度可分为定长和不定长记录两类。

4. 什么是设备独立性？
应用程序独立于具体使用的物理设备。设备独立性又称为数据无关性。它指的是应用程序在使用设备进展I/O时，使用的是逻辑设备，而系统在实际执行时使用的是物理设备，由操作系统负责逻辑设备与物理设备的映射。

5. 为什么要引入线程，解释一下线程与进程之间的相互关系。
因为虽然进程可以提高CPU的利用率，但是进程之间的切换是非常消耗资源和时间的,为了能更进一步的提高操作系统的并发进,引进了线程.这样,进程是分配资源的根本 单位,而线程那么是系统调度的根本单位.一个进程部的线程可以共享该进程的所分配到的资源.线程的创立与撤消,线程之间的切换所占用的资源比进程要少很多.总的来说就是为了更进一步提高系统的并发性,提高CPU的利用率.  线程是进程的根底，进程包含多个线程，是线程的载体。

6. 死锁的必要条件是什么？
死锁：当某进程提出资源申请后，使得系统中一些进程处于无休止的阻塞状态，在无外力作用下，永远不能再继续前进。产生死锁的必要条件：互斥条件：某段时间某资源只能由一个进程使用。不剥夺条件：资源在未使用完前，不能被剥夺，由使用进程释放。局部分配〔请求和保持〕：进程因请求资源而阻塞时，对已分配给它的资源保持不放。环路条件：发生死锁时，有向图必构成一环路。

7. 什么是虚拟存？
虚拟存是计算机系统存管理的一种技术。它使得应用程序认为它拥有连续的可用的存〔一个连续完整的地址空间〕，而实际上，它通常是被分隔成多个物理存碎片，还有局部暂时存储在外部磁盘存储器上，在需要时进展数据交换。

8. 假脱机技术是什么？
通过共享设备来模拟独享设备所采用的操作是假脱机操作，即在联机情况下外部设备设备同时操作。所使用的假脱机技术称之为假脱机技术。

9. 为银行取款机系统配备的操作系统应归类于什么类型的操作系统？

10. 多道程序设计的主要优点是什么？
解：多道程序设计是指在主存中同时存放多道用户作业，使它们都处于执行的开场点和完毕点之间，这些程序共享计算机系统资源。多道程序设计的主要优点有：(1) 提高CPU的利用率。在多道程序环境下，多个程序共享计算机资源，当某个程序等待I/O操作时，CPU可以执行其他程序，大大提高了CPU的利用率。(2) 提高设备的利用率。在多道程序环境下，多个程序共享系统的设备，大大提高系统设备的利用率。(3)提高系统的吞吐量。在多道程序环境下，减少了程序的等待时间，提高了系统的吞吐量。

11. 请为的下面应用环境的计算机选择适合的操作系统。
(1〕飞机的导航〔2〕办公室自动化系统〔3〕航空订票系统〔4〕复杂的科学计算〔5〕图书检索系统

12. 什么是并发、并行？
并发和并行是即相似又有区别的两个概念，并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生。在多道程序环境下，并发性是指在一段时间宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。倘假设在计算机系统中有多个处理机，那么这些可以并发执行的程序便可被分配到多个处理机上，实现并行执行，即利用每个处理机来处理一个可并发执行的程序，这样，多个程序便可以同时执行

13．什么是临界区？
一次仅允许一个进程使用的资源称为临界资源，在进程中对于临界资源的程序段称为临界区。

14. 引入缓冲的目的是什么？
答：〔1〕缓和外部设备和CPU的速度差异；〔2〕减少CPU被中断的次数；〔3〕实现CPU和设备、设备和设备之间的并行操作。

15. 设备驱动程序的主要任务是什么？
设备驱动程序是请求I/O的进程与设备控制器之间的一个通信程序，主要功能有：
①将用户的要求转换为具体要求。
②检查用户的合法性，了解设备状态，根据要求传递参数，设置设备的工作方式。
③向设备控制器发I/O命令启动设备，完成具体的I/O操作。
④及时响应外设的中断请求，根据中断类型调用相应的中断处理程序。
⑤具有通道的控制系统，还要构造通道程序。

四、综合题
1. 信号量的PV操作解决进程的同步问题。
2. 银行家算法判断系统状态是否平安。
3. 分页系统中逻辑地址和物理地址的转换。
4. 页面置换算法，主要掌握先进先出、LRU、最正确置换。
5. 磁盘调度算法，包括FCFS、短寻道优先、电梯算法、LOOK算法等。
6. 进程调度算法，包括FCFS、短任务优先、最短剩余时间优先、时间片轮转等。

综合题案例：
1.考虑以下进程集，进程占用的CPU区间长度以毫秒来计算：
进程 区间时间 优先级
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

假设在时刻0以进程P1，P2，P3，P4，P5的顺序到达。
a.画出4个Gantt图分别演示用FCFS、SJF、非抢占优先级〔数字小代表优先级高〕和RR〔时间片＝1〕算法调度时进程的执行过程。
b.在a里每个进程在每种调度算法下的周转时间是多少？
c.在a里每个进程在每种调度算法下的等待时间是多少？
d.在a里哪一种调度算法的平均等待时间对所有进程而言最小？
答：a.甘特图〔看教材138页〕
FCFS:
P1
P2
P3
P4
P5
0 10 11 13 14 19
SJF:
P2
P4
P3
P4
P5
0 1 2 4 9 19
非抢占优先级:
P2
P5
P1
P3
P4
0 16 16 17 19
RR:
P1
P2
P3
P4
P5
P1
P3
P5
P1
P5
P1
P5
P1
P5
P1
P1
P1
P1
P1
0 19

b.周转时间

FCFS
RR
SJF
非抢占优先级
P1
10
19
19
16
P2
11
2
1
1
P3
13
7
4
18
P4
14
4
2
19
P5
19
14
9
6
c.等待时间

FCFS
RR
SJF
非抢占优先级
P1
0
9
9
6
P2
10
1
0
0
P3
11
5
2
16
P4
13
3
1
18
P5
14
9
4
2
d.SJF

2.考虑一个运行十个I/O限制任务和一个CPU限制任务的系统。假设，I/O限制任务一次分配给一个I/O操作1毫秒的CPU计算，但每个I/O操作的完成需要 10毫秒。同时，假设间接的上下文切换要0.1毫秒，所有的进程都是长进程。对一个RR调度来说，以下情况时CPU的利用率是多少：
a.时间片是1毫秒
b.时间片是10毫秒
答：a.时间片是1毫秒：不管是哪个进程被调度，这个调度都会为每一次的上下文切换花费一个0.1毫秒的上下文切换。CPU的利用率是1/1.1*100=92%。
b.时间片是10毫秒：这I/O限制任务会在使用完1毫秒时间片后进展一次上下文切换。这个时间片要求在所有的进程间都走一遍，因此，10*1.1+10.1(因为每个I / O限定任务执行为1毫秒，然后承当上下文切换的任务，而CPU限制任务的执行10毫秒在承当一个上下文切换之前) 。因此，CPU的利用率是20/21.1*100=94%。

3.考虑下面的一个系统在某一时刻的状态：
Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
使用银行家算法答复下面问题：
a.Need矩阵的容是怎样的？
b.系统是否处于平安状态？
c.如果从进程P1发出一个请求〔0 4 2 0〕，这个请求能否被满足？
答：a.Need矩阵的容是
P0〔0 0 0 0〕
P1〔0 7 5 0〕
P2〔1 0 0 2〕
P3〔0 0 2 0〕
P4〔0 6 4 0〕。
b. .系统处于平安状态，因为Available矩阵等于〔1 5 2 0〕，进程P0和P3都可以运行，当进程P3运行完时，它释放它的资源，而允许其它进程运行。
c.可以被满足，满足以后，Available矩阵等于〔1 1 0 0〕，当以次序P0，P2, P3, P1,P4运行时候，可以完成运行。

4.按顺序给出5个局部的存，分别是100KB,500KB,200KB,300KB和600KB，用 first-fit,best-fit和worst-fit算法，能够怎样按顺序分配进程212KB,417KB,112KB,426KB和426KB？哪个算法充分利用了存空间？
答：
a. First-fit:
b. 212K is put in 500K partition
c. 417K is put in 600K partition
d. 112K is put in 288K partition (new partition 288K = 500K −212K)
e. 426K must wait
f. Best-fit:
g. 212K is put in 300K partition
h. 417K is put in 500K partition
i. 112K is put in 200K partition
j. 426K is put in 600K partition
k. Worst-fit:
l. 212K is put in 600K partition
m. 417K is put in 500K partition
n. 112K is put in 388K partition
o. 426K must wait
Best-fit:算法充分利用了存空间。

5. 考虑一个分页系统在存中存储着一页表。
a.如果存的查询需要200毫秒，那么一个分页存的查询需要多长时间？
b.如果我们加上相关联的存放器，75%的页表查询可以在相关联的存放器中找到，那么有效的查询时间是多少？〔假设如果入口存在的话，在相关的存放器中找到页表入口不花费时间〕
答：a.400毫秒：200毫秒进入页表，200毫秒进入存中的字
b.有效进入时间=0.75*200毫秒+0.25*400毫秒=250毫秒

6. 假设有一个请求调页存储器，页表放在存放器中：处理一个页错误，当有空的帧或被置换的页设有被修改正时要用8ms，当被置换的页被修改正明用20ms，存储器时间为100ns。
假设被置换的页中有70％被修改正，有效时间不超过200ns时最大可承受的页错误率是多少？
答：0.2 sec = (1 −P) ×0.1 sec + (0.3P) ×8 millisec + (0.7P) ×20 millisec
0.1 = −0.1P + 2400 P + 14000 P
0.1=16,400 P
P =0.000006

7. 假设一个请求调页系统具有一个平均和传输时间为20ms的分页磁盘。地址转换是通过在主存中的页表来进展的，每次存时间为1µs。这样，每个通过页表进展的存引用都要存两次。为了提高性能，参加一个相关存，当页表项在相关存中时，可以减少存引用的次数。
假设80%的发生在相关存中，而且剩下中的10%〔总量的2%〕会导致页错误。存的有效时间是多少？
答:
有效时间= (0.8) × (1 µsec)+ (0.1) × (2 µsec) + (0.1) × (5002 µsec)
= 501.2 µsec≈ 0.5 millisec

8. 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。试问：
〔1〕逻辑地址的有效位是多少？
〔2〕物理地址需要多少位？
〔3〕假定某时刻系统用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0A5C和093C变换为物理地址。
解
〔1〕程序空间的大小为32KB，因此逻辑地址的有效位数是15位。
〔2〕存空间的大小是16KB，因此物理地址至少需要14位。
〔3〕当页面为1KB时，虚地址0A5C表示页号为00010，页地址是1001011100。该页在存的第4块，即块号为0100，因此0A5C的物理地址是01001001011100，即125CH。
〔4〕用同样的方法可以求得，093C的物理地址是113CH。
9. 假设在一分页存储管理系统中，某作业的页表如下所示。页面大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址〔注：此处块号即为页面号〕。

页号
块号
0
1
2
3
2
3
1
6
解 此题中，为了描述方便，设页号为P，页位移为W，逻辑地址为A，存地址为M，页面大小为L，那么
P=int(A/L)
W=A mod L

对于逻辑地址1011
P=int(1011/1024)=0
W=1011 mod 1024=1011
A=1101=(0,1101)
查页表第0页在第2块，所以物理地址为M=1024*2+1101= 3059。

对于逻辑地址为2148
P=2148/1024=2
W=2148 mod 1024=100
A=2148=(2,100)
查页表第2页在第1块，所以物理地址为M=1024*1+100=1124。

对于逻辑地址为3000
P=3000/1024=2
W=3000 mod 1024=952
A=3000=(2,952)
查页表第2页在第1块，所以物理地址为M=1024*1+952=1976

对于逻辑地址5012
P=5012/1024=4
W=5012 mod 1024=916
因页号超过页表长度，该逻辑地址非法。

10.某段式存储管理系统中，有一作业的段表〔SMT〕如下表所示，求逻辑地址[0，65]，[1，55]，[2，90]，[3，20]对应的主存地址〔按十进制〕。〔其中方括号中的第一个元素为段号，第二个元素为段地址〕

段号
段长〔容量〕
主存起始地址
状态
0
1
2
3
200
50
100
150
600
850
1000
—
1
1
1
0
解 逻辑地址[0，65]：对应的主存地址为600＋65＝665。
逻辑地址[1，55]：因段地址超过段长，所以产生段地址越界中断。
逻辑地址[2，90]：对应的主存地址为1000＋90＝1090。
逻辑地址[3，20]：因为状态位为0，即该段在辅存中，所以产生缺段中断。

11．对页面串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大为3时，使用FIFO、OPT和LRU替换算法的缺页次数。(OPT和LRU如果出现多项选择项时使用FIFO)
答： FIFO: 缺页11次
页面号
√

1
√

2
√

3
√

4
√

1
√

2
√

5

1
√

2
√

3
√

4
√

5

1
1
1
4
4
4
4
4
2
2
2
5

2
2
2
1
1
1
1
1
3
3
3

3
3
3
2
5
5
5
5
4
4
OPT: 缺页7次
页面号
√

1
√

2
√

3
√

4

1

2
√

5

1

2
√

3
√

4

5

1
1
1
1
1
1
1
1
1
3
3
3

2
2
2
2
2
2
2
2
2
4
4

3
4
4
4
5
5
5
5
5
5
LRU: 缺页10次
页面号
√

1
√

2
√

3
√

4
√

1
√

2
√

5

1

2
√

3
√

4
√

5

1
1
1
4
4
4
5
5
5
3
3
3

2
2
2
1
1
1
1
1
1
4
4

3
3
3
2
2
2
2
2
2
5

12.假设一个磁盘驱动器有5000个柱面，从0到4999，驱动器正在为柱面143的一个请求提供效劳，且前面的一个效劳请在柱面125.按FIFO顺序，即将到来的请求队列是
86，1470，913，1774，948，1509，1022，1750，130
从现在磁头位置开场，按照下面的磁盘调度算法，要满足队列中即将到来的请求要求磁头总的移动距离〔按柱面数计〕是多少？
a. FCFS
b. SSTF
c. SCAN
d. LOOK
e. C-SCAN
答：
a. FCFS的调度是143 ， 86 ， 1470 ， 913 ， 1774 ， 948 ， 1509 ， 1022 ， 1750 ， 130 。总寻求距离是7081 。
b. SSTF的调度是143 ， 130 ， 86 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774。总寻求距离是1745。
c. SCAN的调度是143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774 ， 4999 ， 130 ， 86 。总寻求距离是9769 。
d. LOOK的调度是143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774， 130 ， 86 。总寻求距离是3319 。
e. C-SCAN的调度是143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 4999 ， 86 ， 130 。总寻求距离是9813 。
f. C-LOOK的调度是143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 86 ， 130 。总寻求距离是3363 。

13.假设有两个并发进程P1和P2, 程序代码为
P1: begin P2: begin
A; C;
B； D;
end end
其中，A, B, C和D均为原语。请给出P1和P2两个进程所有可能的执行过程。
答：ABCD，ACBD,ACDB,CDAB,CABD,CADB

14.桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。
分析 在此题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。假设放入果盘中的是苹果，那么允许女儿吃，儿子必须等待；假设放入果盘中的是桔子，那么允许儿子吃，女儿必须等待。此题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。
解 在此题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为1；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：
int S=1;
int Sa=0;
int So=0;
main( )
{
cobegin
father();
son();
daughter();
coend
}
father()
{
while(1)
{
P(S );
将水果放入盘中；
if 〔放入的是桔子〕 V(So);
else V(Sa);
}
}
son( )
{
while(1)
{
P(So);
从盘中取出桔子；
V(S);
吃桔子；
}
}
daughter( )
{
while(1)
{
P(Sa);
从盘中取出苹果；
V(S);
吃苹果；
}
}

. word.zl.