2011—12操作系统复习题答案(基本全部答案)



进程同步1

进程P1和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后，才能执行P2的代码段S2.为描述这种同步关系，：试设计相应的信号量，：给出信号量的初始值，：给出进程P1和P2的结构

解答: 信号量变量申明为 Typedef struct {

int value; //信号量中的值，表示资源的数量 struct PCB *L; //等待该信号量的队列 }semaphore;

设信号量semaphore synch; 初始值为：synch.value=0 进程P1和P2的结构为

P1: { P2: { ⋮ ⋮ S1 wait(synch); signal(synch); S2 ⋮ ⋮ } } 

进程同步2

问题描述：(理发店问题)一个理发店有一间配有n个椅子的等待室和一个有理发椅的理发室。如果没有顾客，理发师就睡觉；如果顾客来了二所有的椅子都有人，顾客就离去；如果理发师在忙而有空的椅子，顾客就会坐在其中一个椅子；如果理发师在睡觉，顾客会摇醒他。 ① 给出同步关系

② 设计描述同步关系的信号量；

③ 给出满足同步关系的进程结构(请完成满足同步关系的进程结构)。

解答：顾客customer应满足的同步关系为： a:顾客来时要等空的椅子，否则不进理发室

b:座椅上的顾客要等理发椅空才有可能与别的顾客竞争理发椅，如果顾客坐上 理发椅，就要腾空其座椅给新来顾客，同时叫理发师给其理发。 c：一旦顾客理发完，就要让别的等待顾客有机会理发。

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

信号量定义如下：

Typedef struct {

int value; //信号量中的值，表示资源的数量 struct PCB *L; //等待该信号量的队列 }semaphore; 互斥信号量定义如下： Typedef struct { bool flag; struct PCB *L;

}binary_semaphore;

理发店问题的解决需要信号量和互斥信号量为：

semaphore chair; binary_semaphore barber_chair, hair_cut; 它们的初始值为：

chair.value=n; barber_chair.flag=1; hair_cut.flag=0;

顾客和理发师进程分别为：

customer { barber { wait(chair); do {

waiting in the chair； wait(hair_cut);

wait(barber_chair); cutting hair； signal(hair_cut); signal(barber_chair); sitting in barber chair for haircut; }while(1) signal(chair); } }



进程同步2

设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为

关车门，售票，开车门。

给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。 用信号量和wait, signal操作实现他们间的协调操作。

解答：根据一般的常识，有

售票员应满足的同步关系为：当司机停车后，才将车门打开让顾客上下车。 司机的同步关系为：当售票员关门后，才能开车.

设互斥信号量 binary_semaphore bus_closed,bus_stopped; 初始值为bus_closed.flag=0; bus_stopped.flag=0;

//表达初始情况第一次用到信号量时情形为车门没有关，车是开着的 进程为:

driver { busserver { do { do {

wait(bus_closed); closing the door; bus starting up； signal(bus_closed); bus is driving； ticket selling; bus is parking； wait(bus_stopped); signal(bus_stopped); opening the door; }while(1) getting onoff the bus; } }while(1) }



进程同步3：

某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定： (1) 每两个学生组成一组，各占一台机器，协同完成上机实习；

(2) 只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房； (3) 上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。 试用信号量机制（P/V操作）实现它们的同步关系。

解

(1) 确定并发和顺序操作

在这个问题中，学生(student)、检查教师(teacher)和门卫(gategard)是并行操作的，因此, 有多个学生(student)进程、一

个检查教师(teacher)进程和一个门卫(gategard)进程。

(2) 确定互斥和同步的规则

gateguard：只有凑够两个学生，并且此时机房有空闲机器时，门卫才分配计算机给学生，允许该组学生进入机房； student：只有门卫分配完计算机后，学生才能进入机房上机操作。只有老师检查完毕才能离开。 Teacher：只有老师检查完学生的实习，才准许学生离开。 (3) 每个进程的操作流程

设立有学生到达标志，通知gateguard进程； 学生是否可进入？ 上机实习；

设立实习完成标志，通知教师； 教师是否可检查，等待教师检查完毕； 学生释放一台计算机资源；

repeat

是否有学生１实习完成？

是否有学生２实习完成？ （是否有一组学生实习完成）

检查学生实习结果； 检查完成，允许学生1离开； 检查完成，允许学生2离开； until false repeat

等待学生1到达; 等待学生2到达; 是否有可用的计算机1; 是否有可用的计算机2; 分配计算机； 设置学生1可进入标志; 设置学生2可进入标志; until false

(4) 确定信号量的个数和含义 student：是否有学生;

computer：是否有可用的计算机； enter：学生是否可以进入机房； finish：是否有学生完成实习； test： 老师是否检查完一组学生。 (5) 确定信号量的初值

在初始状态，各信号量的初值如下： student=0 学生没有到达;

compute=2m 有2m个可用的计算机；

enter=0 不允许学生进入机房，因为需要得到门卫允许； finish=0 没有学生实习完成； test=0 老师没有检查学生。 (6) 确定P、V操作的位置

设立有学生到达标志，通知gateguard进程 =>V(student) 学生是否可进入？=> P(enter) 上机实习；

设立实习完成标志，通知教师 => V(finish)

教师是否可检查，等待教师检查完毕 => P(test(i)) 学生释放一台计算机资源 => V(computer) repeat

是否有学生１实习完成？=>P(student)

是否有学生２实习完成？=>P(student) （是否有一组学生实习完成）

检查学生实习结果；

检查完成，允许学生1离开 => V(test(i)) 检查完成，允许学生2离开 => V(test(i)) until false repeat

等待学生1到达 =>P(student) 等待学生2到达 =>P(student)

是否有可用的计算机1 => P(computer) 是否有可用的计算机2 => P(computer) 分配计算机；

设置学生1可进入标志 => V(enter) 设置学生2可进入标志 => V(enter) until false

(7) P、V操作实现 程序如下： student:=0; computer:=2m; enter:=0; finish:=0; test(i):=0; parbegin

Student i: Begin

V(student); /*表示有学生到达，通知gateguard进程 */ P(enter); /*学生是否可进入*/

上机实习；

V(finish); /*实习结束，通知教师,有需要检查的学生*/ P(test(i)); /*等待教师检查完毕*/ V(computer); /*释放计算机资源} End;

. Teacher:Begin repeat

P(finish); /*是否有需要检查的学生，等待实习完成*/ P(finish); /*是否有需要检查的学生，等待实习完成*/ 选出可检查的第i组学生；

检查第i组学生实习结果；

V(test(i)); /*检查完成*/ V(test(i)); /*检查完成*/ until false End; Gategard:Begin repeat.

P(student); /*等待学生到达*/ P(student); /*等待另一学生到达*/ P(computer); /*是否有可用的计算机*/ P(computer); /*是否有可用的计算机*/ 分配计算机；

V(enter); /*设置学生1可进入标志*/ V(enter); /*设置学生2可进入标志*/ untile false End; Parend;

在student进程中，如果在一个学生到达后，立即向gateguard进程发信号，在gateguard进程为其分配计算机后，该学生才被允许进入机房，因此避免了让该学生争夺计算机的使用权和死锁的发生。

进程同步4：

多个进程对信号量S进行了5次 P操作，2次V操作后，现在信号量的值是 -3，与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？

解

(1) 因为S的当前值是-3，因此因为S处于阻塞状态的进程有3个；

(2) 因为每进行一次P(S)操作，S的值都减1，每执行1次V操作S的值加1，故信号量的初值为-3+5-2=0;

进程同步5：

使用多个进程计算Y=F1(X)+F2 (X). 解

(1) 确定并发和顺序操作

在这个问题中，F1(X)和F2 (X)的计算是可以并行处理的，因此F1(X)和F2 (X)可以分别

出现在两个进程中。

(2) 确定互斥或同步的规则

在F1(X)+F2 (X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。

(3) 同步的操作流程 〈进程main〉

创立进程p1来计算F1(X)； 创立进程p2来计算F2(X)；

F1(X)计算是否完成？没有，等待；① F2(X)计算是否完成？没有，等待；② 进行加法运算。

〈进程p1〉

y1= F1(X)；

设置F1(X)计算完成标志； ③

〈进程p2〉 y1= F2(X)；

设置F2(X)计算完成标志。 ④

(4) 确定信号量的个数和含义

根据同步规则以及操作流程确定信号量的个数是2个，S1和S2： S1含义是F1(X)计算是否完成； S2含义是F2(X)计算是否完成。 (5) 确定信号量的初值 S1=0； S2=0。

(6) 确定P、V操作的位置

上面①处是一个P操作，P(S1)； 上面②处是一个P操作，P(S2)； 上面③处是一个V操作，V(S1)； 上面④处是一个V操作，V(S2)。 解法1 Main ( )

Public y, y1, y2,. P1, P2 Semaphore S1,S2 {

S1=0; S2=0;

P1=Creat(N-F1, F1,x,……); P2=Creat(N-F2, F2, x,……); P(S1); P(S2); y=y1+y2;

}

Procedure F1(x) {

y1= 计算1; V(S1)； }

Procedure F2(x) {

y2=计算2; V(S2)

}

解法2 Main ( )

Public y, y1, y2,. P1,x Semaphore S1 { input(x); S1=0;

P1=Creat(N-F1, F1,x,……); Y2=F2(x); P(S1); y=y1+y2; }

Procedure F1(x) {

y1= 计算1; V(S1) }

采用2个进程和1个信号量来实现Y=F1(X)+F2 (X)的时候，采用的方法是父进程创立子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此F1(X)和F2(X)计算仍然是并发进行的。S1信号量的含义为F1(X)是否完成。改进的方法比原来的方法节约一个进程和一个信号量，但并发操作的程度并没有降低。

进程同步6：

例3.2.10 如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。BUFF1的容量为m，BUFF2的容量是n, PUT、 MOVE、 GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用Ｐ、Ｖ原语协调PUT、 MOVE的操作，并说明每个信号量的含义和初值。

PUT GET MOVE Buff1 Buff2

图 4.2 进程操作图

解

(1) 确定并发的操作

本问题是把2个消费者和生产者问题综合在一起。多个PUT操作与一个MOVE操作并发进行，多个GET操作与一个MOVE操作并发进行。因此本题涉及三类进程：PUT类进程，有多个；GET类进程，有多个；MOVE类进程，有1个。

(2) 操作规则

1) 只有buff1有空间才能进行PUT操作；

2) 只有buff1有数据，buff2有空间才能进行MOVE操作； 3) 只有buff2有数据才能进行GET操作； 4) 不允许多个进程同时操作buff1； 5) 不允许多个进程同时操作buff2。

(3) 操作流程

{

repeat

判断buff1是否有空间，没有则等待； 是否可操作buff1；

PUT；

设置buff1可操作标志； 设置buff1有数据的标志； until false }

{

repeat

判断buff1是否有数据，没有则等待；

判断buff2是否有空间，没有则等待； 是否可操作buff1； 是否可操作buff2；

MOVE；

设置buff1可操作标志； 设置buff2可操作标志；

设置buff1有空间标志； 设置buff2有数据标志； until false }

{

repeat

判断buff2是否有数据，没有则等待； 是否可操作buff2； GET；

设置buff1可操作标志； 设置buff1有空间标志； until false

}

(4) 信号量

设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如下：

1) full1表示buff1是否有数据，初值为0； 2) empty1表示buff1有空间，初值为m； 3) B-M1表示buff1是否可操作，初值为1； 4) Full2表示buff2是否有数据，初值为0； 5) Empty2表示buff2有空间，初值为n； 6) B-M2表示buff2是否可操作，初值为1； (5) P、V操作实现

{

repeat

P(empty1)； /*判断buff1是否有空间，没有则等待 */ P(B-M1)； /*是否可操作buff1*/ PUT；

V(B-M1)； /*设置buff1可操作标志 */ V(full1)； /*设置buff1有数据的标志 */ until false }

{

repeat

P(full1)； /*判断buff1是否有数据，没有则等待*/

P(empty2)； /*判断buff2是否有空间，没有则等待*/ P(B-M1)； /*是否可操作buff1 */ P(B-M2)； /*是否可操作buff2 */ MOVE；

V(B-M1)； /*设置buff1可操作标志*/ V(B-M2)； /*设置buff2可操作标志*/

V(empty1)； /*设置buff1有空间标志*/ V(full2)； /*设置buff2有数据标志*/ until false }

{

repeat

P(empty2)； /*判断buff2是否有空间，没有则等待 */ P(B-M2)； /*是否可操作buff2*/ GET；

V(B-M2)； /*设置buff2可操作标志 */ V(full2)； /*设置buff2有数据的标志 */ until false

}

进程同步7：

一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。

解 〈购票者进程〉 { ┋ P(S)；

进入售票厅； 购票；

退出售票厅； V(S)； }

信号量的初值 S=300

进程同步8：

针对如下所示的优先图解答下列问题： S1

S4 S2 S3

S5

S6

图 4.4 进程优先图

（1）仅使用并发语句能否将其转换成正确的程序？如果能则写出相应程序，如果不能则说明为什么？

（2）若可以使用信号量机构，该优先图将如何转换成正确的程序？ 解

(1) 如果仅用并发语句不能将其转换成程序。 S3 S5 S2 S5 S2 S4 S1S4

因为S5有２个前趋，S4有２个前趋，S6有２个前趋。

(2) 使用信号量机构，就可以将其转换成程序。 Var a, b, c, d, e, f, g, h: Semaphores; {初值均为0} Parbegin

Begin S1; V(a); V(b); V(c); End Begin P(a); S2; V(d); V(e); End

Begin P(b); S3; V(f); End Begin P(c); S4; V(h); End Begin P(d); P(f); S5; V(g); End Begin P(g); P(h); S6; End Parend

（二）死锁



死锁1 ：

5个进程，3种资源，某个时刻，资源分配情况如下：

Allocation Max Available

A B C A B C A B C P0 0 1 0 7 5 3 ,3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3

问：系统是否处于安全状态？如果P1再提出请求1个A类，2个C类资源，是否该批准？

解答：由Allocation 和Max矩阵得到，系统未来需求矩阵为：

P0P1Need=P2P3P4ABC3122Available(3, ,在当前的资源分配状态可以有安全的分配序列{p1,p3,p4,p2,p0},具体分析如下：

6000114313, 2)可以满足P1的未来请求(1, 2, 2),P1得到执行，释放资源；

Available(5, 3, 2)可以满足P3的未来请求(0, 1, 1),P3得到执行, 释放资源； Available(7, 4, 3)可以满足P4的未来请求(4, 3, 1),P4得到执行，释放资源； Available(7, 4, 5)可以满足P2的未来请求(6,0,0),P2得到执行，释放资源； Available(9, 4, 5)可以满足P0的未来请求(6, 4, 3),P0得到执行，释放资源。 所以，系统当前的状态是安全的。

对P1提出的分配请求(1, 0, 2)，假设分配予以满足后，系统状态为：

P0P1 Allocation=P2P3P4解答：



死锁2：

ABCP0100302P1 ，Need=302P2P3211002P4ABC3020，Available=(2, 3, 0),由于可用资源无法满足任

600011431何一个进程未来的请求，这样系统就处于不安全状态，所以，对进程P1的请求，不能予以满足。

假设一个系统有某类资源m个，被n个进程共享，进程每次只请求和释放一个资源， 证明只要系统满足下面两个条件，就不会发生死锁： (1) (2)

解答：由题目有条件 ： i= 1 Maxi < m + n， m Maxi 1, ： Needi=Maxi-Allocationi 。 如果存在死锁，还有条件： i=1 Allocationi= m

由和得： i= 1Needi+ i= 1Allocationi= i= 1 Maxi < m + n

由得： i= 1Needi+ m < m + n, i= 1Needi < n，所以，至少一个进程满足Needi=0,该进程可以执行完，释放占有的资源，所以，目前状态不是死锁状态。 

死锁3：和死锁1相同，系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。

MAX Allocation Need Available 进程 P0 P1 P2 P3 P4 分析进程P0的请求(0, 1, 0)能否满足？



死锁4：假设系统有4个相容类型的资源被3个进程共享，每个进程最多需要2个资源，证明这个系统不会死锁。 证明：

每个进程请求共享资源的最大量相等，且为x，（0个共享资源，并各自最多再申请一个资源就可以运行完毕，进而释放它们所占有的全部资源。

此刻，系统剩余的可用资源数为：4 - 3*(x-1)。

此时不论x为1还是2，4 – 3*(x-1)≥1时，系统不会出现死锁的。

A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2 A B C 每个进程需求资源的最大值在1到m之间； 所有进程需要资源的最大值的和小于m+n。

进程调度与死锁5：

有三个进程P1，P2和P3并发工作，进程P1需用资源S3和S1，进程P2需用资源S1和S2，进程P3需用资源S2和S3。回答。

• (1)若对资源分配不加，会发生什么情况?为什么? • (2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 答：

• (1)可能会发生死锁现象。例如，进程P1，P2和P3分别获得资源S3，S1，和S2后再继续申请资源时都要等待，这是循环等待。

• (2)可有以下几种答案：

• 1)采用静态分配，由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。

• 2)采用按序分配，不会出现循环等待资源现象。

• 3)采用银行家算法，在分配时，保证了系统处于安全状态。

进程调度与死锁:6：

有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。

(1) 先来先服务（按A，B，C，D，E）算法。 (2) 优先级调度算法。 (3) 时间片轮转算法。 解

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

执行次序 A B C D E 运行时间 10 6 2 4 8 优先数 3 5 2 1 4 等待时间 0 10 16 18 22 周转时间 10 16 18 22 30 根据表中的计算结果，5个进程的平均周转时间T为：

T=（10+16+18+22+30）/5=19.2min

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

执行次序 B E 运行时间 6 8 优先数 5 4 等待时间 0 6 周转时间 6 14 A C D 10 2 1 3 2 1 14 24 26 24 26 27 它们的平均周转时间为：

T=（6+14+24+26+27）/5= 19.4min

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

第1轮：（A，B，C，D，E） 第2轮：（A，B，D，E） 第3轮：（A，B，E） 第4轮：（A，E） 第5轮：（A） 显然，5个进程的周转时间为：T1=30min、 T2=22min、 T3=6min、T4=16min、T5=28min。它们的平均周转时间T为：

T=（30+22+6+16+28）/5=20.4min

进程调度与死锁7：

设某系统进程的状态除了最基本的三种状态外，还增加了创建状态、延迟状态和完成状态。试画出系统的进程状态变迁图，并说明状态变迁可能的原因。

解 一般的多道程序运行环境中，进程最基本的状态有3个：就绪、运行、阻塞。本题又增加了创建、延迟、完成3种状态，使进程状态增至6个。

图4.3 进程状态转换配图

(1) 就绪→运行：进程具备运行条件，当进程调度程序选择了进程后，便将其转入运行状态。

(2) 运行→阻塞：进程需要等待某种事件的发生，如执行了输入输出指令，或者请求资源得不到满足时，进程转阻塞状态。

(3) 阻塞→就绪：进程等待的I/O已完成，或者请求的资源得到满足，进程转为就绪状态。

(4) 创建→就绪：进程尚不具备运行条件，所需的资源尚未得到满足。当进程创建完成后，进程可转入就绪状态。

(5) 运行→延迟：进程运行过程中，因某种原因需要延迟运算，则设定好延迟时间后被转入延迟状态。

(6) 运行→完成：进程运行时遇到结束指令后，被转入完成状态

进程调度与死锁8：

一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求两台，试问，N的值如何选取时系统中绝对不会出现死锁？

解 本题的考核要点是资源竞争与死锁问题。已知系统中的每个进程需要两台打印机，那么在最坏的情况下，各进程都占用了其中的一台，而且都在请求自己所需的另一台。如果此时系统尚有多余的一台，那么就可以满足其中一个进程运行完毕。

因此说，如果让6-1台打印机分给N个进程，满足它们每人一台的话，进程数量N必然小于等于5。

当该进程运行完毕释放出它所占有的打印机后，又可以进一步满足其他进程。系统就不会出现死锁。

（三）内存管理

内存管理1：

在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us，假设页表的查询与快表的查询同时进行 。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。

(1) 求对某一数据进行一次次存取可能需要的时间？

(2) 现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间? 解答：

(1) 当系统对数据进行存取时，有3种可能性。

① 所存取的数据的页面在内存，其页表项已经存储到快表，此时存取数据的时间是： 查询快表的时间+存取内存数据的时间=1us+8us= 9us

② 所存取的数据的页面在内存，但是其页表项没有存储到快表，没有命中快表，此时存取数据的时间是： 查询页表的时间+存取内存数据的时间=8us+8us= 16us

③ 所存取的数据的页面不在内存，发生缺页中断，此时存取数据的时间是： 查询页表的时间+缺页中断的时间+查询页表的时间+ 存取内存数据的时间=8us+20us+8us+8us = 44us (2) 当对某一数据进行4次连续读取时：

① 第1次可能的时间为：

1us+8us= 9us；8us+8us= 16us；8us+20us+8us+8us。

② 第2次时，对应页面的页表项已经交换到快表中。因为存取是连续的，不存在页面被淘汰的可能性，所以第2次、第3次、第4次的存取时间是一样的，消耗的时间为1us+8us= 9us。

内存管理2：

若在一分页存储管理系统中，某作业的页表如下所示。已知页帧大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址（注：此处块号即为页帧号）。

页号 0 块号 2 1 2 3 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

因页号超过页表长度，该逻辑地址非法。 

内存管理3：

假设一个请求分页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换时通过在主存中的页表来进行的，每次内存访问时间为1s。为了提供性能，加入一个块表，当页表项在块表中，可以减少内存的访问次数。假设80%的访问发生在快表汇总，而且剩下中的10%会导致页错误，内存的有效访问时间是多少？（假设块表的查找时间可以忽略）



内存管理4：

假设有下面也引用序列1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. LRU页面置换算法会导致多少次页错误？假设内存帧数分别为2,3,4

内存管理5：

有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式如下：

段号 段内地址 29 20 19 0

求其虚拟存储器的实际容量？

解 虚拟内存的实际大小由系统的逻辑地址结构、主存辅存容量共同决定。虚拟内存容量的理论值是210 *220=1G；最大段内地址为220=1M，远大于内存容量，其段长超过512K的内存容量，故最大实际段长为512k而不是1M。

所以可计算虚拟存储容量为210 *512K =210 *0.5M=0.5G。 0.5G<2G，因此虚拟存储器的实际容量是0.5G。

内存管理6：

有这样一种页面置换算法，它给每一个内存块(块与页大小相等)设置一个计数器，以计数曾经装入过该块的页面数。当需要置换一个页面时，该算法总是将其计数值最小的那个块内的页面换掉，当有多个最小值时，按FIFO执行。

若某进程分得4个内存块，现对1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，解答如下问题：

(1) 求在上述算法下的页面失效数； (2) 求在OPT.算法下的页面失效数。 解 （1）求解过程如下表所示 页面号 √ √ √ √ √ √ √ √ √ √ √ √ √ 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2 2 2 2 2 2 2 1 1 1 1 1 1 9 9 9 9 9 9 9 9 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 5 5 5 5 4 4 4 4 4 4 7 7 7 7 7 7 7 7 7 4 4 4 B1 1 1 1 1 5 5 5 5 5 5 8 8 8 8 8 8 8 8 8 8 8 2 B2 B3 B4 C1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 C2 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 C3 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 C4 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3

注：打“√”的表示缺页，共有13次缺页。

说明：在上面的求解过程中，B1～B4表示进程分得的4个块号，C1～C4表示与这4块对应的计数器；表中的每一列记录了每一块当前装入的页面及其计数器的值。

（2）在OPT.算法下的页面失效次数为11。

（四）文件系统



文件系统1：

设想一个在磁盘上的文件系统的块大小为512B，假设每个文件的信息已经在内存中。对三种分配方法：连续分配、链接分配(假设链接指针占1个字节)和索引分配，假设文件的线性逻辑地址从0开始线性增长，分别回答下面的问题： (1) (2)

逻辑地址到物理盘块地址的映射是怎样进行的？

假设现在处于盘块10，现在想访问盘块4，那么必须从磁盘上读多少个物理块？ 解答：假设Z是文件的起始块物理地址, 访问文件的逻辑地址为LS。

对连续分配：X=LS div 512，Y=LS mod 512, 将X加上Z就是要读取文件所在的盘块，Y是文件在盘块

中的偏移址。如果要从10#盘块访问4#盘块，则只需要读取1次磁盘。

对链接文件，X= LS div 511, Y= LS mod 511，从起始地址沿链接追踪X+1个块，就是所要访问的块，Y+1是快内的偏移址。要从10#盘块访问4#盘块，需要读入4个物理块。

对索引文件，X= LS div 512, Y=LS mod 512, 读入文件的索引节点，在索引表中第X栏目中给出的盘块地址就是所要读取的文件盘块，Y是盘块内偏移址。如要从10#盘块访问4#盘块，则需要读入2个物理盘块。

 

文件系统2： 文件系统3：

假定一个盘组共有100个柱面，每个柱面上有16个磁道，每个盘面分成4 个扇区，问： （1）整个磁盘空间共有多少个存储块？

（2）如果用字长为32位的单元来构造位示图，共需要多少个字？ （3） 位示图中第18个字的第16位对应的块号是多少？

答

（1） 4*16*100＝00 （2） 00/32＝200 （3） 18*32+16＝592

 

文件系统4： 文件系统5：

假定有一个磁盘组共有100个柱面，每个柱面有8个磁道，每个盘面划分成8个扇区。现有一个5000个逻辑记录的文件，逻辑记录的大小与扇区大小相等，该文件以顺序结构被存放在磁盘组上，柱面、磁道、扇区均从0开始编址，逻辑记录的编号从0开始，文件信息从0柱面、0磁道、0扇区开始存放。请问：

（1）该文件的3468个逻辑记录应存放在哪个柱面的第几个磁道的第几个扇区上。 （2）第56柱面上的第8磁道的第5扇区中存放的是该文件的第几个逻辑记录。

答：

.（1） 柱面号：3468/＝ 磁道号：（3468%）/8＝1 扇区号：（3468%）％8＝4 （2）56*+8*8+5＝3652

（五）I/O系统



i/O系统1：

假定在某移动臂磁盘上，刚刚处理了访问60号柱面的请求，目前正在73号柱面上读信息，并有下列请求序列等待访问磁盘：

请求序列欲访问的柱面号：150 50 178 167 87 43 23 160 85 试用最短任务优先算法和电梯调度算法，分别排出实际上处理上述请求的次序。 解：9 5 2 6 7 1 8 4 3

9 5 1 8 4 3 2 6 7

  

i/O系统2： i/O系统3： i/O系统4：

（六）概念复习：

1.

当时引入多道程序的目的在于（ C ）。

A.有利于代码共享，减少主、辅存信息交换量 B．充分利用存储器 C.充分利用CPU，减少CPU等待时间 D．提高实时响应速度 2.

在单处理机计算机系统中，（ B ）是并行操作的。 A.程序与程序

B.处理机的操作与通道的操作 C.主程序与子程序

D.用户程序与操作系统程序 3.

当线程处于阻塞状态时，线程( B )。

A. 正在占用处理机 B.没有占用处理机

C. 将进入执行状态 D.将进入结束状态

4.

当多道程序系统中发生死锁时，（ C ）。 A.计算机系统不能处理任何事情 B.某个进程不能够执行

C.一组进程相互等待，并进入阻塞状态 D.不能进行输入和输出 5.

下面哪一个不是程序在并发系统内执行的特点（ B ）。 A.产生死锁的必然性 B.资源分配的动态性 C.程序执行的间断性 D.相互通信的可能性 6.

进程和程序的一个本质区别是( D )。 A. 进程分时使用CPU，程序独占CPU B．进程存储在内存，程序存储在外存 C. 进程在一个文件中，程序在多个文件中 D．进程为动态的，程序为静态的

进程是操作系统发展以后引进的一个称谓。本质上他是运行起来的程序在从系统里面申的资源的管理代表。以这样说：

进程是运行中的程序。󰀀 B答案的错误是：

即使是程序也可以存储在内存里。 7.

在文件系统中，采用位图主要是实现（ B ）。 A. 磁盘的驱动调度 B. 磁盘空间的分配和回收 C. 文件目录的查找 D. 页面置换

Bitmap（位图） 把它看作一个磁盘空间占用/空闲状态的一维数组 8.

进程调度的基本功能是选择( A ).

A.就绪的进程 B.后备的作业 C.空闲内存 D.空闲设备 进程调度的三个具体功能：(1)记录系统中所有进程的执行情况 (2)选择占有处理机的进程 (3)进行进程上下文切换 9.

对于普通用户而言，OS的（ B ）是最重要。

所以可󰀀 A.开放性 B.方便性 C.有效性 D.可扩充性 10.

计算机的普通用户通常通过（ B ）使用OS所提供的服务。 A.中断键盘 B.控制接口 C.特权指令 D.系统调用 11. （ B ）进程调度算法适合分时系统.

A.先来先服务 B.轮转 C.短作业优先 D.最高优先级 其余三个多见于批处理系统

12. 进程的控制信息和描述信息存放在（ B ）。

A.JCB B.PCB C.AFT D.SFT

13. 下列有可能导致一进程从运行变为就绪的事件是（ D ）。

A.一次I/O操作结束 B.运行进程需作I/O操作 C.运行进程结束

D.出现了比现运行进程优先权更高的进程

15. 与计算机硬件关系最密切的软件是（ D ）.

A.编译程序 B.数据库管理系统 C.游戏程序 D.OS

16. 与设备控制器关系最密切的软件是（ B ）。

A.编译程序 B.设备驱动程序 C.存储管理程序 D.处理机管理 17. ( C )进程调度算法适合紧急事件的处理。

A.先来先服务 B.轮转 C.可抢占优先级 D.优先级 18.

若进程P一旦被唤醒就能够投入运行，系统可能（ D ）。 A.在抢占调度方式中，P的优先级高于当前运行的进程 B.进程P的优先级最高 C.就绪队列为空队列

D.在抢占调度方式中，P的优先级高于就绪队列中所有的进程 19. 进程依靠什么从阻塞状态过渡到就绪状态（ D ）。 A.操作人员的命令 B.系统服务

C.等待下一个时间片到来 D.由\"合作\"进程唤醒

20.

在下面的I/O控制方式中，需要CPU干预最少的方式是（ C ）。 A. 程序I/O方式 B. 中断驱动I/O控制方式 C. 直接存储器访问DMA控制方式 D. I/O通道控制方式 21. 新创立的进程首先进入( A )状态。

A.就绪 B.执行 C.阻塞 D.挂起

22. 在OS中，文件的存取控制可以使（ A ）。

A. 用户间不能相互删除文件 B. 内存中的多道程序间不相互破坏 C. 内存中的程序不破坏OS D. 防止黑客攻击

23. 页的逻辑地址形式是:页号24位，页内地址10位,内存128M,辅存10G，那么虚拟存储器最大实际容量可能

是( C ) 。

A.1024K B.16G C.10G D.10G+128M

24. 分页存储管理的存储保护是通过( A )完成的。

A.页表 B.快表 C.存储键 D.索引

25.

用户使用（ D ）形式的文件。

A.链接 B.连续 C.物理 D.逻辑

26. 能够装入内存任何位置并能执行的程序代码必须是可( B )。

A.动态链接 B.重定位 C.可重入的 D.静态链接

27. . 若系统中只有用户级线程，则处理机调度单位是（ A ）。

A.线程 B.进程 C.程序 D.作业

28. 如果要使装入内存的程序，在内存中移动后仍能正常运行，必须要有( B )的支持。

A. 静态重定位 B.动态重定位 C. 动态链接 D.静态链接 29.

采用（ B ）不会产生内部碎片。

A.分页式存储管理 B.分段式存储管理

C.固定分区式存储管理 D.段页式存储管理

解：C.将产生大量的内部\"碎块

A.不产生外部碎片，产生的内碎片不超过页大小 D.没有解决碎片问题，有内部碎片

30.

假脱机技术中，对打印机的操作实际上是用对磁盘存储实现的，用以替代打印机的部分是指（ C ）。

（A）共享设备 （C）虚拟设备

31

32 最短进程优先技术的一个困难在于 答案：D

33时系统中的当前运行进程连续获得了两个时间片，原因可能是 答案：B

34进程依靠（）从阻塞状态过渡到就绪状态 答案：D

（B）独占设备 （D）物理设备

（七）简答题：

1.

为什么要区分系统态和用户态？ 解 区分系统态和用户态主要原因如下：

(1) 为了防止操作系统及关键数据受到用户程序有意或无意的破坏，通常将处理机的执行状态分成系统态和用户态两种。处于用户态执行的程序的操作要受到，不能去执行特权指令，访问操作系统区域和其他程序的区域，这就防止了用户程序对操作系统和其他用户程序的破坏。操作系统的内核通常是运行在系统态的，用户态的程序通过系统调用接受系统态程序运行的服务。

(2) 用户态下的进程能存取它们自己的指令与数据，但不能存取内核指令和数据或其他进程的指令和数据。然而，系统态下的进程能够存取内核和用户地址。例如，一个进程的虚拟地址空间可划分成仅在系统态下可存取及在系统态和用户态都可存取的两部分。某些机器指令是特权指令（Privilege Instruction），如I/O指令等。在用户态下执行的进程没有执行特权指令的能力，在用户态下执行特权指令会引起错误。而在系统态下的进程可以执行一切指令。

2.

进程和线程的主要区别是什么？

解：线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度实体。

在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行线程。在有进程和线程的系统中，进程是系统资源分配的单位，而线程是可调度运行的单位。

进程和线程的区别是：

(1) 线程是进程的一个组成部分；

(2) 进程的多个线程都在进程的地址空间活动；

(3) 资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它；

(4) 处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程； (5) 同一进程中的线程在执行过程中，可能需要同步。 3.

进程能自己将自己唤醒吗？进程能自己将自己撤消吗？

解：唤醒进程和撤消进程都是要通过在CPU上运行程序来实现的。一个进程入睡了，它就不可能被调度到CPU上运行；一个进程在撤消前必须先进入终止状态，而处于终止状态的进程不可能被调度到CPU上运行。因此，进程被唤醒、被撤消都不能由自己来完成，只能由别的进程实现。 4.

程序并发执行的主要特性是什么？

解：可分割性(即可中断性)、失去封闭性、失去可再现性。 5.

何为死锁？产生死锁的原因和必要条件是什么？

解：死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。

产生死锁的原因有：资源不足资源、进程推进次序不当。

产生死锁的必要条件有：互斥条件、请求和保持条件、不可剥夺条件、环路等待条件 6.

在解决死锁问题的几个方法中，哪种方法最容易实现？哪种方法使资源的利用率最高？

解：预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。

避免死锁方法，比较实用的有银行家算法（Banker Algorithm）。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。

检测死锁方法是基于死锁定理设计的，定期运行该算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各种死锁解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。 7.

分页存储管理存在的局限性是什么?

逻辑地址空间：页是物理单位，共享困难，不便对代码进行分类管理，不能进行动态连接。 8.

为什么说分段系统较之分页系统更易于实现信息共享和保护？如何实现。 解 a)

在分页和分段存储管理系统中，多个进程并发运行，共享同一内存块里的程序或数据是可行的。为了实现共享，必须在各共享者的段表或页表中分别有指向共享内存块的表目。 b)

对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的逻辑段，相对来说比较易于实现。

c) 对分页管理，则要困难的多。首先，必须保证被共享的程序或数据占有整数块，以便与非共享部分分开。其次，由于共享程序或数据被多个进程访问，所以每个进程对共享程序或数据的访问都应该是有条件的。

d) 因此，从共享和保护的实现上来看，须共享的程序段或数据段是一个逻辑单位，而分段存储管理中被共享的程序或数据作为一个整体（一段）,实现共享和保护就要方便得多。

e) 分段系统的共享是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。每段设置访问方式，就可以实现段的保护。

f) 9.

多道程序系统为什么能提高CPU的利用率？

答：利用了原来CPU的等待时间。

10. 文件的逻辑结构有哪些？

解：文件的三种物理结构是 顺序文件、链接文件和索引文件。

一种是无结构的流式文件，是指对文件内信息不再划分单位，它是依次的一串字符流构成的文件。

一种是有结构的记录式文件,是用户把文件内的信息按逻辑上的含义划分信息单位，每个单位称为一个逻辑记录（简称记录）。所有记录通常都是描述一个实体集的，有着相同或不同数目的数据项，记录的长度可分为定长和不定长记录两类。

11. 什么是设备性？

解：其基本含义是： 设备性又称为设备无关性。它指的是应用程序在使用设备进行I/O时，使用的是逻辑设备，而系统在实际执行时使用的是物理设备，由操作系统负责逻辑设备与物理设备的映射。引入设备性可以使设备的分配具有极大的灵活性，并易于实现I/O重定向。

12. 为什么要引入线程，解释一下线程与进程之间的相互关系。

解：线操作系统的并发进,引进了线程.这样,进程是分配资源的基本单位,而线程则是系统调度的基本单位.一个进程内部的线程可以共享该进程的所分配到的资源.线程的创建与撤消,线程之间的切换所占用的资源比进程要少很多.总的来说就是为了更进一步提高系统的并发性,提高CPU的利用率.

通常在一个进程中可以包含若干个线程，它们可以利用进程所拥有的资源。在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为运行和调度的基本单位。由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小得多，能更高效的提高系统内多个程序间并发执行的程度，从而显著提高系统资源的利用率和吞吐量。 13.

死锁的必要条件是什么？

解：产生死锁的四个必要条件：󰀀󰀀

（1） 互斥条件：一个资源每次只能被一个进程使用。

（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。󰀀 （3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。󰀀 （4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。󰀀

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

14. 什么是虚拟内存？

解 虚拟存储器通过把主、辅存统一起来管理，给用户造成一种仿佛系统内有巨大主存供用户使用的假象。例如页

式存储管理，一道作业被划分成若干页，其中较活跃的几页放在内存，而其余不活跃的页被放在辅存，当需要访问辅存内的页时，就可通过页面调度将其调入内存运行；但用户感觉不到这种变化，他会以为作业的所有部分都存在于主存。这样可以让更多的作业进入主存，提高系统的效率。虚拟盘是物理上不存在这样的盘，而是操作系统为用户借助其它存储介质实现的。

15. 说明静态重定位和动态重定位的区别。

解 “重定位”，在实际上指的是这样相互联系的两件事情：一是确定一个待执行程序在内存中的位置；二是将程序中的逻辑地址转换成物理地址。说它们是相互联系的，是因为后一件事情是由前一件事情决定的。

静态重定位，指的是在程序装入时实现的重定位。具体的讲，就是将程序装入内存后，立即根据其装入位置将程序中需重定位的逻辑地址转换成物理地址，包括指令地址、数据地址、子程序入口地址等。这种“定位”的特点是“定位”之后，内存中的代码发生了变化，程序不能在内存移动，CPU按物理地址运行程序。

动态重定位，是在程序执行的过程中，根据执行的需要动态地装入、链接和定位。它不是根据程序在内存的位置立即将指令和数据的逻辑地址转换成物理地址，而是把这种位置信息送入一个称之为“地址映射机构”的硬件中，然后，CPU按逻辑地址执行程序。在执行中，由“映射机构”将逻辑地址及时地转换成正确的访存物理地址。这种定位方法的主要特点是重定位后，内存中的代码没有发生了变化，允许程序在执行的过程中在内存移动位置，这只要更换“映射机构”中的启址信息就可将同一程序映射到内存不同的地方。这种位置移动对提高内存空间的利用率是有好处的。

16. 假脱机技术是什么？

解：SPOOLing系统，把独享设备分割为若干台逻辑上的独占的设备，使用户感受到系统有出若干独占设备在运行。当然，系统中至少一台拥有物理设备，这是虚拟设备技术的基础。

SPOOLing系统又称“假脱机I/O系统”，其中心思想是，让共享的、高速的、大容量外存储器（比如，磁盘）来模拟若干占设备，使系统中的一台或少数几占设备变成多台可并行使用的虚拟设备。

SPOOLing系统主要管理外存上的输入井和输出井，以及内存中的输入缓冲区和输出缓冲区。其管理进程主要有输入和输出进程，负责将输入数据装入到输入井，或者将输出井的数据送出。它的特点是：提高了 I/O操作的速度；将独占设备改造为共享设备；实现了虚拟设备功能。

为什么在分页和分段管理下取一条指令或一个操作数通常需两次访存？如何解决这一问题？

解 这是因为用于地址变换的页表或段表也是存放在内存的，为了将CPU给出的逻辑地址变成物理地址，首先就要访问内存的页表和段表，然后，根据形成的物理地址再取指令或数据，这就要两次访存。解决这一问题的办法是提供一个称之为“快表”的硬件，用以存放当前运行进程的页表或段表的部分内容，“快表”的访问时间很快，因此可以节约访问页表和段表的时间。 存储器访问具有时间和空间的“局部性”，因此快表的命中率一般可达70%到90%；页表和段表是在系统执行过程中，每时每刻都需要访问的，因此，访问时间的微小缩短，其累计节约的时间却可以达到很大。

17

18为什么要引入设备性？如何实现设备性？

引入设备性，可使应用程序于具体的物理设备，显著改善资源的利用率及可

适应性；还可以使用户于设备的类型。 实现性：在应用程序中应使用逻辑设备名称来请求使用某类设备。当应用程序用逻辑设备名请求分配I/O 设备时，系统必须为它分配相应的物理设备，关在逻辑设备表LUT中建立一个表目。

19对目录管理的主要要求是什么？ 答：文件系统所要解决的核心问题，就是按照充分发挥主机和外部设备效率的原则，把信息的逻辑结构映像成设备介质上的物理结构，把用户的文件操作转换成相应的I/O指令。转换

过程所使用的主要数据结构是文件目录和辅存空间使用情况表。所以目录管理的基本功能就是通过查目录能实现符号名与具体地址之间的转换。要求目录的编排应以如何能准确地找到所需文件为原则，而选择目录的方法应以查找速度快为准则。