专业课数据库数据库复习资料-问答题

2.1.2

1.为什么要引入进程概念?进程的基本特点是什么？它与程序有何联系和区别。

2.父进程创建子进程与主程序调用子程序有何不同？

3.一个进程进入等待状态时，其断点存放在何处？它被唤醒后从何处继续原来的执行？

4.为什么说中断是进程切换的必要条件，但不是充分条件?

5.根据Bernstein条件,则有以下4条语句:

Si:a=x+yS2：b=z+lS3:c=a+bS4:w=c+l

则，和S2两条语句、S3和S4两条语句是否可以并发执行？

6.已知一个求值公式(A2+3B)/(B+5A),若A、B已赋值，试画出该公式求值过程的前趋图。

7.设系统中有n（n>2）个进程，且当前不执行进程调度程序，试考虑下述4种情况:

①没有运行进程，有2个就绪进程，n个进程处于等待状态。

②有1个运行进程，没有就绪进程，n-l个进程处于等待状态"

③有1个运行进程，有1个就绪进程，n-2个进程处于等待状态。

④有1个运行进程，n-l个就绪进程，没有进程处于等待状态。

上述情况中，不可能发生的情况是哪些？

8.在单用户系统中，有n个进程，问排在就绪队列和等待队列中进程个数的范围是什么？

9.回答以下问题：

（1）若系统中没有运行进程，是否一定没有就绪进程？为什么？

（2）若系统中既没有运行进程，也没有就绪进程，系统中是否就没有进程？为什么？

（3）在采用优先级进程调度时，运行进程是否一定是系统中优先级最高的进程？

2.2.2

1.什么是多线程？多线程与多任务有什么区别？

2.从调度性、并发性、拥有资源及系统开销几个方面，对进程和线程进行比较。

3.简要比较用户级线程和内核级线程的不同点。

2.3.2

1.简述作业和进程的区别。

2.分析作业、进程、线程三者之间的关系。

3.一个作业从提交开始直到运行完毕，可能经历哪些调度？每种调度的功能是什么？若在后备作业队列中同时等待运

行的有3个作业A、B、C,已知它们各自的运行时间为a、b、c,且满足a<b«,证明采用短作业优先调度算法能获

得最小平均周转时间，并说明短作业优先调度算法会产生什么问题。

4.高级调度与低级调度的主要功能是什么？为什么要引入中级调度？

5.对于时间片轮转算法，可抢占处理器的优先数调度算法和不可抢占处理器的优先数调度算法，分别画出进程状态转

换图。

6.某进程被唤醒后立即投入运行，就说这个系统采用的是剥夺调度方法，这种说法对吗？为什么？

7.假设某操作系统采用时间片轮转调度策略，时间片大小为100ms,就绪进程队列的平均长度为5,如果在系统中运

行一个需要在CPU上执行0.8s时间的程序，问该进程的平均周转时间和平均等待时间各为多少（不考虑I/O情况）？

8.有5个待执行的作业，分别是A、E、C、D、E,各自估计的运行时间是9、6、3、5、X。试问采用哪种运行次序使

平均周转时间最短，其平均周转时间是多少？（提示：答案依赖于X）。

3.1.2

1.简述进程同步与互斥之间的区别和联系。

2.进程之间存在哪几种制约关系？各是什么原因引起的？以下活动各属于哪种制约关系？

（1）若干学生去图书馆借书。

（2）两队进行篮球比赛。

（3）流水线生产的各道工序。

（4）商品生产和社会消费。

3.以下两个进程A和B之间体现出一种什么关系？为什么？

进程A:进程B:

while（true）while(true){

（(

Al：收到监视器的信号；Bl:延迟10分钟；

A2：count=count+l；B2:打印count的值；

}B3：count=0：

4.下列解决临界段问题的软件算法能保证临界段的互斥访问吗？请说明原因。

进程Pi（i=l,2,….…）:

whileItrue）

{while（s<=0）;

s-；

临界区代码；

S++；

非临界区代码；

）

其中，S为一个整型变量，初值为1.

5.以下是对•两个进程P0和P1互斥进入临界区的解法，指出该解法存在的问题并予以改正。

enumboolean{false,true};

booleanflag[2]-{false,false};

intturn;

进程PO：

do

{flag[O]=true;

while(turn!=O)

{while(flag[l]==true);

turn=0;

)

临界区;

flag[O]=false;

其他代码；

}while(true);

进程Pl：

do

{flag[O]=true;

while(turn!=l)

{while(tlaglOJ==true);

turn=l;

)

临界区；

flag[l]=true;

其他代码；

}while(true);

6.以下算法用于解决两个临界问题，判断其正确性。如果不正确，举例子说明该算法违背了关于临界段问题的哪条准

则。

两个进程PO、P1共享如下变量：

boolflag[Ol]={false,false);〃flag数组元素初值均为false

intturn=O或1;//turn的初值为。或1

进程P0：

do

{flag[O]=true;

while(turn==l)

{while(flag[O]);

turn=0;

)

flag[l]=false;

临界区;

非临界区;

}while(true);

进程Pl：

do

flag[l]=true;

while(turn==O)

{while(flag[l]);

turn=l;

)

flag[O]=false;

临界区;

非临界区；

}while(true);

7.进入A和B共享个变量，因此在各自的程序里都有自口的临界区。现在进程A在临界区里。试问进程A的执行

能够被别的进程打断吗？能够被进程B打断吗？(这里“打断”的含义是调度新进程运行，使进程A暂停执行)。

8.信号量上的P、V操作只是对信号量的值进行减1或加1操作吗？在信号量上不能执行除P、V操作外的其他操作

吗？

9.请问需要互斥操作的两进程有执行先后次序要求吗？列举一个用P、V操作进行互斥访问的例子，说明信号量初值。

10.以下两个并发执行的进程，它们能正确运行吗？如果不能，请改正。

intx;

main()

{Cobegin

{进程Pl

{inty,z;

x=l;y=0;

if(x>=l)y=y+l;

z=V；

)

进程P2

{intt,u;

x=0;t=0;

if(x<=l)t=t+2;

u=t;

|

)

Coend

)

11.设有4个进程共享一个程序段，而每次最多允许两个进程进入该程序段，则信号展的取值范围是多少？

12.设有n个进程共享一个程序段，对于如下两种情况：

（1）如果每次只允许一个进程进入该程序段。

（2）如果每次最多允许m个进程（mA）同时进入该程序段。

试问所采用的信号量初值是否相同？信号量的变化范围如何？

13设有两个优先级相同的进程P1和P2,如下所示,信号量S1和S2的初值均为0,试问Pl、P2并发执行后，x、y、

Z的值各是多少？

进程P1:进程P2：

y=i;x=l;

y=y+2；x=x+l;

v（si）；P(S1)；

z=y+i;x=x+y;

P(S2);V(S2);

y=z+y;z=x+z;

14.设缓冲区大小为n,指出以下生产者-消费者问题解决中的错误，并改正。

Producer()〃生产者进程

{while(true)

{生产一个产品nextp;

D(mutex);

P(mutex);

3uffer(in)=nextp;

in=(in+l)%n

V(mutex);

)

)

Consumer()〃消费者进程

{while(true)

{P(mutex);

P(full);

nextc=buffer(out);

Out=(out+l)%n;

V(mutex);

消费产品nextc;

)

15.某车站售票厅，任何时间最多可容纳100名购票者进入，当售票厅少于100名购票者可立即进入，否则需在外面

等待。若把一个购票者看作一个进程，请回答以下问题：

(I)P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

(2)根据所定义的信号量，插入应执行的P、V操作以保证进程能够正确地并发执行。

main()

{Cobegin

Processp1(i=l»2,...)

{进入售票厅；

退出；

}

Coend

}

(3)右购票者最多为“个人，写出信号量可能的变化范围(最大值和最小值)。

16.用P、V操作解决读者-写者问题如下:

SemaphoreS=l;

SemaphoreSr=l;

intrc=O;

main()

{Cobegin

{读者进程Reader।(i=l,,ni

{while(true)

{P(Sr);

rc=rc+l;

if(rc==l)P(S);

V(Sr);

读文件；

P(Sr)；

rc=rc-l;

if(rc==O)V(S);

V(Sr);

)

)

当者进程Writerj(j=l,m)

{while(true)

{P(S)；

写文件；

V(s)；

)

)

)

Coend

请回答以下问题:

(1)信号量Sr的作业是什么？

(2)程序中什么语句用于读•写互斥、写•写互斥？

(3)若规定最多只有5个进程同时读，怎么修改程序?

17.有一对夫妻在某银行申请了一个共同的账号，办理了正副两张银行卡，每张银行卡都可独立存款和取款，规定每

次存款或取款的金额为1000元(约定可透支)。自动存取款机中为设行卡设置了如下两个进程：

intamount=0;

main()

{Cobegin

{SAVE()〃进程SAVE

{intk;

k=amount;

k=k+1000;

amount=k;

)

TAKE()〃进程TAKE

{intt;

t=amount;

t=t-1000;

amount=t;

)

}

Coend

)

问答下列问题：

(1)上述进程执行时会产生怎样的错误？为什么？

(2)为保证系统的安全，可采用P、V操作来管理。请完善上述程序，以确保系统的安全。

18.管理是由哪几部分组成的？为什么要引入条件变量？

进程描述题

1.如图3.13(a)所示，给出6个进程合作完成某一任务的前趋图，试用P、V操作描述它。

(a)前趋图

2.使用信号量机制实现：进程A和进程B共享浮点数组data[1000],它们共同完成对data中浮点数据的累加计算,

由进程A输出最终的累加结果。

3.对于生产者•消费者问题，若缓冲区中缓冲区单元只有一个，生产者和消费者各只有一人，如图3.14所示。用P、V

原语实现生产者和消费者的同步操作。

缓冲区(1个单元)

生产者用费--者

>

图3.14一个单元的缓冲区

4.有n+1个进程，即A1,,An和B,如图3.15所示，A1,,An进程通过同一缓冲区各自不断地向B发送消

息，B不断地获取消息，刚开始时缓冲区为空，使用P、V操作来正确实现它。

缓冲区(1个单元)

想——>1

A2>B、

An

图3.15n+1个进程

5.对于生产者-消费者问题，若缓冲区中缓冲区的单元有n个，生产者和消费者各只有一人，如图3.16所示。用P、V

原语实现生产者和消费者的同步操作.

缓冲区（n个单元）

生产者消费者

3.16n个单元的缓冲区

6.某杂技团进行走钢丝表演。在钢丝的A、B两端各有n名演员（n>l）在等待表演。只要钢丝上无人时便允许一名

演员从钢丝的一端走到另一端。现要求两端的演员交替地走钢丝，且从A端的一名演员先开始。请问，把一名演员

看作一个进程时，怎样用P、V操作来进行控制？请写出能进行正确管理的程序。

7.在一个盒子里，混装了个数相等的闱棋白子和黑子。现在要用自动分拣系统把白子和黑子分开，设系统有两个进程

P1和P2,其中P1拣白子，P2拣黑子。规定每个进程每次只拣一子。当一个进程正在拣子时，不允许另一个进程同

时拣子；当一•个进程拣一子后，必须让另一个进程去拣。试写出这两个并发进程能正确执行的程序。

8.设公共汽车上有一个司机和一个售票员，它们的活动如图3.18所示，问这两个活动是什么同步关系？请用信号量

机制实现它们的同步。

图3.18司机和售票员的活动

9.有3个并发进程R、T、P,它们共享了一个可•循环使用的缓冲区3缓冲区B中共有n个单元。进程R负责从输入

设备读信息，每读一个字符后，把它存放到缓冲区B的一个单元中；进程T负责处理读入的字符，若发现读入的字符

中有空格符，则把它改为“，”：进程P负贡把处理后的字符取出并引印输出。当缓冲区B单元中的字符被进程P取

出后，则又可用来存放下一次读入的字符，如图3.20所示。请用P、V操作为同步机制写出它们能正确并发执行的程

序。

缓冲区（n个单元）

图3.20n个单元的缓冲区

10.设有4个进程A、B、C、D共享一个缓冲区，如图3.21所示，进程A负责循环地从文件读一个整数并放入缓冲区:

进程B从缓冲区中循环读取M0D3为0的整数并累计求和；进程C从缓冲区中循环读取M0D3为1的整数并累计求

和：进程D从缓冲区中循环读取M0D3为2的整数并累计求和。请用P、V操作写出能正确执行的程序。

缓冲区(1个单元)

图3.21一个单元的缓冲区

11.有3个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区1,每执行一次读一个

记录；PB将缓冲区1的内容复制到缓冲区2,每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一

次打印一个记录，如图3.22所示。缓冲区的大小和一个记录大小一样。请用P、V操作来保证文件的正确打印。

PAPBPC

>缓冲区1缓冲区2A

从磁盘读入复制打印

图3.22进程间的合作方式

12.有3个进程GET、COPY和PUT,它们的工作流程如图3.23所示，用PV操作解决它们的同步问题。

13.桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果(apple),妈妈专

向盘子放桔子(orange)。两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、

妈妈、儿子、女儿之间的同步与互斥关系。

14.桌子上有一个盘子，可以放一个水果。爸爸总是放苹果到盘子中，而妈妈总是放香蕉到盘子中，一个儿子专等吃

盘了中的香蕉，而个女儿专等吃盘了中的苹果。请用P、V操作来实现爸爸、妈妈、儿了、女儿之间的同步与互斥

关系。

15.有一个师父进程和三个学徒进程、每个学徒连续不断地组装产品。做一个产品需要A、B、C三种零件各一个，这

三个学徒分别掌握A零件、B零件、C零件多个。师傅源源不断提供上述三种零件，但他每次只将其中的两种零件各

一个放在桌面上，具有另一种零件的学徒就可以组装产品，且做完后给师傅发信号，然后师傅再拿出两种零件各一个

放在桌面上，如此反复，试写出一算法描述他们的活动。(假设通过i=rand()%3产生0~2的随机数)。

16.有一个东西方向的独木桥，如图3.26所示，每次只能有一人通过，且不允许人在桥上停留。东、西两端各有若干

人在等待过桥。请用P、V操作来实现东西两端人过桥的问题。

__________独木桥_________

图3.26独木桥过桥问题

17.假设有一座东西向的车辆单行道的桥，如图3.27所示，每次允许同方向的若干车辆通过(即桥上可以有多个同方

向的车辆通过）。在桥上没有车辆时，任何一端的车辆都允许上桥通过，当有车辆上桥后，同端的主辆可以继续上桥,

但另一端的车辆不能上桥。请用p、V操作来实现东西两端人过桥佗问题。

图3.27车辆过桥问题

18.对于上题的单车道简易桥，最大可载重4辆汽车。请定义合适的信号量，正确使用P、V操作，给出任一车辆通

过该桥的管理算法。

19.有两个合作进程Pl、P2,它们从一台输入/输出设备读入数据，P1进程读入数据a,P2进程读入数据b,输入设

备是一台独占设备，如图3.28所示。两个进程做如下计算：

Pl：x=a-b

P2：y=a*b;

图3.28两个进程的工作流程

计算完成后结果x、y由进程P1输出。用信号量实现进程Pl、P2的同步算法。

20.有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每座位列出一个表目，包括座位号、姓名,

读者离开时撤销登记信息。阅览室有100个座位。试用P、V操作描述这些进程间的同步关系。

21.复印室有一个操作员为顾客复印资料，有5把椅子供顾客休息并等待复印。如果没有顾客，则操作员休息。当顾

客来到复印室时，如果有空椅子则坐下来。当操作员空闲时顾客站起来唤醒操作员进行复印，复臼完后离开复卬室：

如果没有空椅了则离开复卬室。试用P、V操作实现顾客和操作员活动的同步。

22.画图说明管程的组成，并利用管程解决生产者-消费者问题。

3.2.2例题解析

1.进程之间有哪些基本的通信方式?它们分别有什么特点?适用于哪些场合?

2.简要比较消息队列与管道通信机制不同点。

3.什么是管道?无名管道和有名管道的主要差别是什么？

3.3.2例题解析

1.什么是死锁，产生死锁的原因是什么？

2.产生死锁的必要条件是什么？解决死锁问题常采用哪几种措施？

3.在某一时刻，系统中是否可能出现既无运行态进程乂无就绪态进程？若可能，在什么情况下会产生？

4.进程死锁与“饥饿”之间有何相同点和不同点？

5.简述防止死锁的分配策略中各自存在哪些缺点？

6.为什么说不能通过破坏“互斥条件”来预防死锁。

7.下面关于死锁问题的叙述哪些是正确的，哪些是错误的？说明原因。

⑴参与死锁的所有进程都占有资源。

⑵参与死锁的所有进程中至少有两个进程占有资源。

⑶死锁只发生在无关进程之间。

⑷死锁可发生在任意进程之间。

8.设系统中仅有一类数最为M的独占型资源，系统中N个进程竞争该类资源，其中各进程对该类资源的最大需求量

为W,当M、N、W分别取下列值时，试判断哪些情况会发生死锁，为什么？

(1)M=2.N=2,W=1

(2)M-3,N-2,W-2

(3)M=3.N=2,W=3

(4)M=5.N=3,W=2

(5)M=6,N=3,W=3

9.一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没

有死锁危险，并说明原因。

10.回答以下问题

(1)3个进程共享4个同类型资源，每个进程最大需要两个资源，请问该系统是否会因为竞争该资源而死锁?

(2)n个进程(编号为l~n)共享m个同类资源，若每个进程都需要用该类资源，且各进程最大需求量之和小于m+n,试

证明这个系统不会因为竞争该资源而发生死锁。

⑶在(2)中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？

11.Dijkstra于1965年提出的银行家算法，其主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？

12.一个系统具有150个存储单元，在To时刻按表3.7所示分配给3个进程。

表3.73个进程分配情况

进程最大需求存储单元当前已分配单元数

P16025

P26040

P36045

对下列请求应用银行家算法分析判断是否安全？

⑴第4个进程P4到达，最大需求60个存储单元，当前请求分配25个单元。

(2)第4个进程P4到达，最大需求50个存储单元，当前请求分配35个单元。

如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明原因。

13.若系统运行中出现如表3.11所示的资源分配情况，该系统是否安全？如果进程P2此时提出资源申请(1,2,2,

2),系统能否将资源分配给它？为什么？

进程AllocationNeedAvailable

P0003200121622

P110001750

P213542356

P303320652

P400140656

14.有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是

否会由于对这种资源的竞争而产生死锁。

15.现有某类资源12个，供3个进程共享。假定进程A已占1个资源，其最大需求4个，进程B已占4个资源，其

最大需求6个，进程C已占5个资源，其最大需求8个。当进程都请求尚需的资源时.，系统应按怎样的次序为它们分

配以保证不发生死锁，并解释之。

16.设系统中有3种类型的资源(A、B和C)和5个进程Pl、P2、P3、P4、P5,A资源的数量为17,B资源的数量为5,

C资源的数最为200在TO时刻系统状态如表3.14所示。系统采用银行家算法实施死锁避免策略。

表3.14To时刻系统状态

进程最大资源需求量已分配资源数量

ABCABC

P1559212

P2536402

P34011405

P4425204

P5424314

剩余资源数ABc

233

(1)T时刻是否为安全状态？若是，请给出安全序列。

⑵若在Ta时刻进程P2请求资源(03,4),是否能实施资源分配？为什么？

⑶在⑵的基础上，若进程P4请求资源(2,0,1),是否能实施资源分配？为什么？

⑷在⑶的基础上，若进程P1请求资源(0,2,0),是否能实施资源分配？为什么？

17.某系统有RI、R2和R3共3种资源，在T时刻Pl、P2、P3和P4这4个进程对资源的占用和需求情况如表3.20

所示，此时系统的可用资源向量为(2,1,2)。

表3.20To时刻4个进程对资源的占有和需求情况

进程最大资源需求量已分配资源数量

RIR2R3R1R2R3

Pl322100

P2613411

P3314211

P4422002

试问：

⑴将系统中各种资源总数和此刻各进程对•各资源的需求个数用向量或矩阵表示出来。

(2)如果此时P1和P2均发出资源请求向量Request(l,1),为了保证系统的安全性，应该如何分配资源给这两个进程？

说明你所采用策略的原因。

⑶如果(2)中两个请求立即得到满足后，系统此刻是否处于死锁状态？

18.现有5个进程A、B、C、D、E,有4种类型的资源RI、R2、R3、R4在TO时刻系统状态如表3.24所示。RI、R2、

R3、R4的剩余资源数依次为3、3、0、3。若采用银行家算法避免死锁，回答下列问题：

⑴T。时刻是否为安仝状态？

⑵若这时D提出申请（1,2,0,3）,是否能实施资源分配?

表3.24To时刻5个进程对资源的占用和需求情况

进最大资源需求量己分配资源数量

程R1R2R3R4R1R2R3R4

A00120012

B20002750

C003466S6

D10514356

E03320652

19.假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位R2有一个单位），它们被进程P1和P2所共

享，且已知两个进程均以下列顺序使用两类资源：

一申请R1-申请R2-申请R1-释放R1-释放R2-释放R1-

试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程资源图）

20.试化简图3.39中的进程资源图，并利用死锁定理给出相应的结论。

(b)

21.有3个进程Pl、P2和P3并发工作，进程P1需用资源S3和S1,进程P需用资源S1和S2,进程P3需用资源S2

和$3=试回答下面两个问题。

⑴若对资源分配不加限制，会发生什么情况？为什么？

⑵为保证进程正确工作，应采用怎样的资源分配策略？

4.1.2

【例4-1-24］为什么要引入动态重定位?

【例4-1-25】什么是交换技术，什么是覆盖技术?

4.2.2

【例4-2-26］如表4.1所示，给出了某系统中的空闲分区表，系统采用可变式分区存管理策略。现有以下作业序列：

96KB、20KB、200KB。若采用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可■以满足该作业序

列的请求，为什么？

表4.1某系统中的空闲分区表

分区号大小起始地址

132KB100KB

210KB150KB

35KB200KB

4218KB220KB

596KB530KB

【例4-2-27］给定内存空闲分区，按地址从小到大为：100K、500K、200K、300K和600K。现有用户进程依次分别为

212K、417K>112K和426K。回答以下问题:

⑴分别用首次适应算法、最佳适应算法和最坏适应算法将它们装入到内存的哪个分区？

(2)哪些算法能适合该进程序列？

【例4-2-28］某操作系统采用动态分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB

处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为已分配区＜在执行以下申请、

释放操作序列后：请求300KB；请求100KB；释放300KB；请求150KB；请求50KB；请求90KB,进行以下回答：

（1）采用首次适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。

（2）采用最佳适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。

（3）若随后又要请求80KB,针对上述两种情况产生什么后果？说明了什么问题？

4.3.2

【例4-3-27］某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内偏移量，则在这样的地址结构中,

请回答：

（1）一页有多少个字节？

（2）逻辑地址可有多少页？

（3）一个作业最大的地址空间是多少字节？

【例4328】在某个分页管理系统中，某一个作业有4个页面，被分别装入到主存的第3、4、6、8块中，假定页面

和块大小均为1024字节，当作业在CPU上运行时，执行到其地址空间笫500号处遇到一条传送命令：

MOV2100,3100

请计算出MOV指令中两个操作数的物理地址。

【例4-3-29】对一个将页表存放在内存中的分页系统，请问答：

（1）如果访问内存需要0.2US,一个数据的有效访问时间是多少？

（2）如果加一个快表，且假定在快表中找到页表项的命中率为90%,则访问一个数据的有效访问时间又是多少（假定

查快表需要花费的时间为0）?

【例4330】已知某分页系统，主存容量为64KB,页面大小为1KB,对于一个4页的作业，其0、1、2、3页分别被

分配到主存的2、4、6、7块中。

(1)将十进制的逻辑地址1023、2500、3500>4500转换成物理地址。

(2)以十进制的逻辑地址1023为例，画出地址变换过程图。

【例4331】某系统采用分页存储管理方式，设计如下：

页面大小为4KB,允许用户虚地址空间最大为16页，允许系统物理内存最多为512个内存块。试问该系统虚地址寄

存器物理地址寄存器的长度各是多少位？

【例4-3-32］在一个分页存储管理系统中，页的大小为2KB。设主存容量为512KB描述主存分配的位示图如图4.28

所示，0表示未分配，1表示已分配，此时系统要将一个张B的作业装入内存，回答以下问题：

⑴为作业分配内存后，请给出该作业的页表(分配内存时首先分配内存的低地址端)。

⑵分页存储管理有无碎片存在？若有，会存在什么碎片？为该作业分配内存后，会生零头吗？如果产生，碎片大小

为多少？

(3)若某系统采用分页存储管理，内存容量为64MB,也采用位示图管理内存，页面大小为4KB,该位示图占用多大内

存？

1111110111111111

1101110011100110

0000101111111111

1000000000000000

1111100000101010

图4.28内存位示图

4.5.2

【例4-5-40］什么是虚拟存储器，其特点是什么？为什么从逻辑上说采用虚拟存储器能扩大内存存储空间？

【例4-5-41】在请求分页存储管理系统中，什么时候为进程分配内存？分配的单位是什么？

【例4-5-42］覆盖技术与虚拟技术本质有何不同？

【例4-5-43】试述缺页中断与般中断的主耍区别。

【例4-5-44］简述操作系统是如何处理缺页中断和缺段中断的。

【例4-5-45］在请求分页存储管理中影响缺页中断有哪几个主要因素？

【例4-5-46］什么是请求分页管理方式？能满足用户哪些需要？

【例4-5-47］考虑•个请求调页系统，它采用全局置换策略和平均分配内存块的算法(即若有m个内存块和n个进程,

则每个进程分得m/n个内存块)。如果该系统中测得如下的CPU和对换盘的利用率，请问能否用增加多道程序的道数

来增加CPU的利用率？为什么？

的利用率为对•换盘的利用率为

(l)CPU13%,97%O

(2)CPU的利用率为87%,对换盘的利用率为3%

(3)CPU的利用率为13%,对换盘的利用率为3%

【例4-5-48】假设一个具有下面时间度量利用率的请求调页系统：CPU利用率为20%,分页磁盘为97.7%,其他I/O

设备为5%。试说明下面哪些方法可以提高CPU的利用率，为什么？

A.安装一个更快的CPU。

B.安装一个更大的分页磁盘。

C.提高多道程序设计程序。

D.降低多道程序设计程度。

E.安装更多内存。

F.安装一个更快的硬盘，或对多个硬盘使用多个控制器。

G.对页面调度算法采用预调页策略。

H.增加页面大小。

【例4-5-49】在分页虚拟存储管理系统中，为什么说一条指令执行期间可能产生多次缺页中断？

【例4-5-50］某虚拟存储器的用户编程空间共32个页面:每页1KB.主存为16KB。假定某时刻该用户页表中已调入

主存的页面的页号和物理块号为：(0,5),(1,10),(2,4),(3,7)。求出虚地址0A5cH和1A5cH对应的物理地址，

若在内存中找不到对应的页面，会出现什么情况？

【例4-5-51】主存储器容量为4MB,虚存容量为1GB(23%),虚拟地址和物理地址各为多少位？根据寻址方式计算出

来的有效地址是虚拟地址还是物理地址？如果采用分页管理，且页面大小为4KB,则页表长度是多少？

【例4-5-52】某系统采用请求分页存储管理，设计如下：页面大小为4KB,允许用户虚地址空间最大为16页，允许

系统物理内存最多为512个内存块。试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位？做必要的说明。

【例4-5-53］现要求对一个请求分页系统设计进程调度的方案，使系统同时满足以下:

⑴有合理的响应时间。

⑵有较好的外部设备利用率。

⑶缺页对程序执行速度的影响降到最低程度。

【例4-5-54］回答以下问题:

⑴一个32位计算机系统有主存128MB和辅助存储器10GB,这个系统的虚拟空间是多少？

(2)某请求分页存储管理中采用位示图技术，设主存有16384块，采用32位的512个字作为位示图。若块号、字号和

位号(从高位到低位)分别从1、0、。开始°试计算5998块对应的字号和位号：192字的20位时应于哪一块？

【例4-5-55］某请求分页存储管理系统，允许用户空间为32个页面(每页1KB),主存为16KB,如一个用户程序有

10页长，且在某时刻该用户进程的页表如表4.14所示。

表4.14个页表

文号物理块号是否在TLB中

08是

17是

24否

310否

45否

53是

62是

其他无效

⑴如果程序执行时遇到以下两个虚地址：OAC5(H)、1AC5(H),试计算它们对应的物理地址。

⑵页表存放在主存中，对主存的一次存取需要1.5US,对TLB表(快表)的查找时间忽略为0,试问这两次访问共耗

费多少时间？

【例4-5-56】考虑下述页面走向：

1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6

当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？

【例4-5-57】已知页面走向为1、2、1、3、1、2、4、2、1、3、4,且开始执行时内存中没有页面，若只给该作业分

配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需

要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又为多少？

【例4-5-58］在请求分页存储管理方式中，若采用先进先出(FIFO)页面淘汰算法会产生一种奇怪的现象：分配给作业

的页面越多，进程执行时的缺页率反而越高。试举例说明这种现象。

【例4-5-59］考虑下面的访问串:

2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6

假定有4、5、6个页块，应用下面的页面替换算法，计算各会出现多少次缺页中断，并求相应的缺页率和命中率（提

示：所给定的页块初始均为空，因此，首次访问一页时就会发生缺页中断

⑴LRU（最近最久未使用算法）。

（2）FIFO（先进先出算法）。

（3）0PT（最佳算法）。

【例4-5-60】在某个请求分页系统中，一个进程己分配到4个页框（PageFrame）,如表431所示（所有数字都为十

进制数，且以。开始）。操作系统采用固定分配局部置换策略为此进程分配4个页框。当进程访问第4页时，产生缺

页中断，请分别用FIFO、LRU算法，决定缺页中断服务程序选择换H的页面。

表4.31进程使用页框情况表

页号页框号装入时间最近访问时间访问位修改位

206016101

1113016000

022616210

332016311

【例4-5-61】在某个请求分页系统中,某程序在一个时间段内有如下的存储器引用：12、351、190、90、430、30、

550（以上数字为虚存的逻辑地址）。假定内存中每块的大小为100B,系统分配给该作业的内存块数为3块。回答如

下问题：

（1）对于以上的存储器引用序列，给出其页面走向.

（2）设程序开始运行时，己装入第。页。在先进先出页面置换算法和最久未使用页面置换算法（LRU算法）下，分

别画出每次访问时该程序的内存页面情况；并计算出缺页中断次数和缺页率。

【例4-5-62】在某个请求分页系统中，缺页中断时间由哪几部分构成？当存储器访问时间为100ns,缺页中断时间为

25ms（含全部缺页中断处理的时间），如果希望缺页时有效访问时间的延长与没有缺页时相比不超过10%,请问此时

的缺页率f不得超过多少？

【例4-5-63】在某个请求分页管理系统中，如果页面在内存中，满足一个内存请求需要250ns。如吴页面不在内存中，

若有空用物理块或换出的页没有被修改则需要5ms（lms=106ns）：如果换出的页已修改，则需要12ms。如果缺页率

为2%,并有40%的要换出的页被修改，问有效访问时间是多长？假设系统只运行一个进程且交换时CPU空闲。

【例4-5-64】某请求分页管理系统中，页表保存在寄存器中。若有一个可用的空页或被置换的页未修改，则它处理•

个缺页中断需要8ms（含全部缺页中断处理的时间）；若被置换的页已被修改，则处埋一缺页中断因增加写I可外存时

间而需要20ms,一次内存的存取时间为1us。假设70%被置换的页被修改过，为保证有效访问时间不超过2us,可

接受的最大缺页率是多少？

【例4-5-65］假设一个请求分页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换是通过在内存中的

页表来进行的，每次内存访问时间为1US。这样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能,

加入一个快表，当页表项在快表中时，可以减少内存引用的访问次数。假设80%的访问发生在快表中，而且剩下中的

10%（总量的2%）会导致页错误.内存的有效访问时间是多少？

【例4-5-66】对丁个使用快表的请求分页存储管理系统，设快表的命中率为70%（访问快表的时间忽略不冲），次

内存的存取时间是1ns。缺页处理时，若内存有可用空间或被置换的页面在内存中未被修改过，则处理一个缺页中断

需要8000ns,否则需要20000ns。假定被置换的页面60%是属于后一种情况，则为了保证有效访问时间不超过2ns,

求可接受的最大缺页率是多少？

【例4-5-67］某系统使用请求分页存储管理，通过查找联想寄存器（快表）访问已换入的内存IX域需要花150nso如果

必须使用主存页表，其访问时间为400ns。如果要替换的页已经修改，则导致中断的访问时间为8ms（lms=1000000ns）,

否则只要3ms。如果缺页率为2%,联想寄存器的命中率为70%,且50%的替换页都是修改过的，求有效访问时间。

【例4-5-68］某计算机有Cache、辅存来实现虚拟存储器。如果数据在Cache中，访问它需要20ns；如果在内存但不

在Cache中，需要60ns将其装入缓存，然后才能访问：如果不在内存而在辅存中，需要12ms将其读入内存，然后

用60ns再读入Cache,然后才能访问,假设Cache命中率为0.9,内存命中率为0.6,则数据平均访问时间是多少?

【例4-5-69］已知一个采用了LRU置换算法的请求分页存储管理系统中，页面大小为4KB,内存方问速度为100ns/

次，快表访问速度为20ns/次，缺页中断处理时间为25ms/次。今有一个长度为30KB的进程P进入系统，分配给P

的存储块有3块，进程的所有页面都是在该进程运行中动态装入。若访问快表的命中率为20%,对应于下述页面访问

序列：

7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0.、1

计算20个页面的平均有效访问时间是多少？

【例4-5-70】某系统用32位的实地址，48位虚地址，页面大小4KB,页表项为8B,每段程序最大为4GB。问答以下

问题：

⑴系统将采用多少级页表？

⑵假设用一级页表，TLB命中率为98%,TLB访问时间为10ns,访存时间为100ns,并假设TLB访问失败才访存，问

平均页面访问时间为多少？

（3）如果是二级页表，页面平均访问时间是多少？

【例4-5-71】在请求分页存储管理系统中，假设页表内容如表4.43所示，页面大小为212B,主存的访问时间是100ns,

联想存储器的访问时间是10ns,换入页面（含重新设置页表项，并用新页表项置入联想存储器）的平均时间为

100000900ns,进程所用页帧固定且驻留集大小为2,采用LRU页面淘汰算法，当进程被调度执行时，依次访问虚地

址：（23362）8、（14565）8、（24575）8，问各需要多少访问时间？（14565k的物理地址是多少并解释（假设联存储器初始为

空，变址时先访问联想存储器）？

表4.43一个页表（表中的数均为八进制）

页号页帧号（主存块号）驻留位（标志）磁盘地址