操作系统上课练习总结

第一章 绪论

    操作系统的两个最基本的特征是（）和（），两者之间互为存在条件。

    答案：并发性；共享性

    实时系统应具有的两个基本特征是（）和（）。

    答案：及时性；高可靠性 

    虽然不同操作系统具有各自的特点，但它们都具有以下4个基本特征（）、（）、（）和（）。

    答案：并发性；共享性；虚拟性；异步性

    下列选择中，（）不是OS关心的主要问题。

A.管理计算机裸机

B.设计、 提供用户程序与计算机硬件系统的界面

C.管理计算机系统资源

D.高级程序设计语言的编译器

    答案：D

    在OS中，并发是指若干事件（）发生。

A.在同一时刻

B.一定在不同时刻

C.在某一时间间隔内

D.一次在不同时间间隔内

    答案：C

    允许多个用户以交互方式使用计算机的OS称为（）；允许多个用户将作业提交给计算机集中处理的OS称为（）；计算机系统能及时处理过程控制数据并作出响应的OS称为（）。

A.批处理OS

B.分时OS

C.多处理机OS

D.实时OS

E.网络OS

    答案：BAD

    操作系统的作用可表现在哪几方面？

    试比较单道与多道批处理系统的特点和优缺点。

    操作系统的基本特征是什么？

    什么是多道程序设计技术？多道程序设计技术的特点是什么？

第一章 进程与线程

                ——进程与线程部分

    并发是现代操作系统的最基本特征之一，为了更好地描述这一特征而引入了（）这一概念。

    答案：进程

    进程的基本特征是（）。

    答案：动态性，并发性，性，异步性，结构特征

    对进程的描述中，下列说法错误的是() 。

A.一个进程可以包含若干个程序

B.一个程序可以对应多个进程

C.进程必须由程序作为其组成部分

D.一个程序仅对应一个进程

    答案：D

    进程与程序的最根本的区别是（）。

A.对资源的占有类型和数量

B.进程是动态的，程序是静态的

C.看它们是否能够并发地在处理机上运行

D.进程规模较小，程序规模较大

    答案：B

    下列有关进程和程序的主要区别中，叙述是错误的是（）。

A.进程是程序的执行过程，程序是代码的集合

B.进程是动态的，程序静态的

C.进程可为多个程序服务，而程序不能为多个进程服务

D.一个进程是一个的运行单位，一个程序段不能作为一个的运行单位

    答案：C

    下列情况下，在（）时，进程从阻塞状态转换到就绪状态。

A.等待的某事件已经发生了

B.时间片用完了

C.分配到必要的资源并获得了处理机

D.等待某事件

    答案：A

    下列几种关于进程的叙述中，（）最不符合操作系统对进程的理解。

A.进程是多道程序并行环境中的完整程序

B.进程可以由程序、数据和进程控制块描述

C.线程是一种特殊的进程

D.进程是程序在一个数据集合上的过程，它是系统进行资源分配和调度的一个单位。

    答案：A,C

    如果单CPU系统中有N个进程，则就绪队列中进程的个数最多可达到（）个。

A.N+1

B.N

C.N-1

D.1

    答案：C

    当一个进程处于这样的状态（）时，称其为等待状态。

A.它正等着输入一批数据

B.它正等着合作进程的一个消息

C.它正等着分给它一个时间片

D.它正等着进入内存

    答案：A,B

    进程的3种基本状态之间，下列（）转换是不能进行的。

A.就绪到运行

B.运行到阻塞

C.阻塞到运行

D.阻塞到就绪

    答案：C

    下列情况下，在（）时，进程从阻塞状态转换到就绪状态。

A.等待的某事件已经发生了

B.时间片用完了

C.分配到必要的资源并获得了处理机

D.等待某事件

    答案：A

    一个进程被唤醒意味着（）。

A.该进程的优先数变为最大。

B.该进程获得了CPU。

C.该进程从阻塞状态变为就绪状态。

D.该进程排在了就绪队列的队首。

    答案：C

    下列关于进程控制块的叙述中，说法错误的是（） 。

A.进程控制块对每个进程仅有一个

B.进程控制块记录进程的状态及名称等

C.进程控制块位于主存储区内

D.进程控制块的内容、格式及大小均相同

    答案：D

    在一个分布式操作系统中，进程可能出现如下图所示的变化，请把产生每一种变化的具体原因填在表格的相应框内。 

变化	原因
1
2
3
4
5

    答案：时间片到；因等待数据资源而阻塞；因I/O而阻塞；数据资源到被唤醒；I/O完成被唤醒

    在多道程序设计环境中，为了提高CPU效率，内存中的进程越多越好。

    答案：错

    一般来说，用户进程的PCB存放在用户区，系统进程的PCB存放在操作系统区。

    答案：错 

    某进程的一个线程处于阻塞状态，则该进程必然处于阻塞状态。 

    答案：错

    进程是基于多道程序设计而提出来的。其基本的特征是并发性和动态性；进程的执行也即在各种基本状态之间多次转换的过程。但只有处于就绪、阻塞、执行这3种状态的进程位于内存。

    答案：错

    程序顺序执行与并发执行有何不同？

    试从动态性、并发性和性上比较进程和程序。

    试说明PCB的作用。为什么说PCB是进程存在的唯一标志？

    试说明进程在三个基本状态之间转换的典型原因。

    用户态和核心态。(目态和管态)

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

    什么是进程。

    简述下列概念的联系与区别：并发与并行。

    什么是线程？试说明进程与线程的关系。

习题课_进程互斥、同步与通信

    在操作系统中，PV操作是一种（）

A.机器指令

B.系统调用命令

C.作业控制命令

D.低级进程通信原语

    答案：D

    临界区是（）

A.一个缓冲区

B.一段共享数据区

C.一段程序

D.一个互斥资源

    答案：C

    若信号量S的初值为2，当前值为-1，则表示有（）个等待进程

A.0

B.1

C.2

D.3

    答案：B

    下面描述中，（）是正确的

A.进程执行的相当速度不能由进程自己来控制

B.PV操作都是原语操作

C.利用信号量的pv操作可以交换大量信息

D.同步是指并发进程之间存在的一种制约关系

    答案：ABD

    下面哪个选项体现了原语的主要特点？（）

A.并发性

B.异步性

C.共享性

D.不可分割性

    答案：D

    下面哪个选项不是管程的组成部分（）

A.局部于管程的共享数据结构

B.对管程内数据结构进程操作的一组过程

C.管程外过程调用管程内数据结构的说明

D.对局部于管程的数据结构设置初始值的语句

    答案：C 

    信箱通信是一种（）通信方式。

A.直接

B.间接

C.低级

D.会合

    答案：B  

    设在公共汽车上，司机和售票员的活动分别是

    司机：启动车辆；正常行车；到站停车

    售票员：关门；售票；开门

    使用信号量和PV操作实现其同步关系 

    售票员关车门后，向司机发开车信号

    到站时司机停车，售票员在车停后开车门

    设S1表示是否允许司机开车，初值为0

    设S2表示是否允许售票员开门，初值为0

Driver()

{

while(true)

   {

       P(S1)

      启动车辆

      正常行车

      到站停车

      V(S2)

}

}

Busman()

{

   while(true)

   {

      关车门

      V(S1)

      售票

      P(S2)

     开车门

   }

}

    在一个小盒子里存放了黑子和白子两种围棋棋子，已知黑子和白子数量皆等于N.试设计两个并发进程A和B，将这些充分混合在一起的棋子分拣开。

    该系统的约束条件

    A专拣白子；B专拣黑子

    两个进程每次只能拣一枚

    两个拣棋子的进程应当交替进行，且拣白子的优先

    设置如下信号量

    s,m为同步信号量，初值分别为1和0

    设置变量I，j用来记录捡到的棋子的个数，初值为0

processA()

{

while(i   {

          P(s)    

          拣一枚白子

          V(m)

          i＋＋

    }

}

processB()

{

while(j  {

       P(m)

       拣一枚黑子

       V(s)

       j＋＋

  }

}

    有三个进程A，B，C协作解决文件打印问题。

    A将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录；

    B将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；

    C将缓冲区2的内容打印，每执行一次打印一个记录。

    缓冲区的大小和一个记录大小一样。

    使用PV操作来保证文件的正确打印。

    Pa与pb共用一个缓冲区1；

    Pb与pc共用一个缓冲区2；

    当缓冲区1为空时，PA可将一个记录读入其中

    若缓冲区1有数据，缓冲区2为空时，PB可将记录从缓冲区1复制到缓冲区2

    若缓冲区2有数据，PC可以打印记录

    其他条件下，相应进程必须等待

    设置如下信号量

    S1,s2为互斥信号量，初值为1，分别用于对缓冲区1，2的互斥访问

    Full1,full2为同步信号量，初值为0，分别表示缓冲区1，2还没有被取用的记录

    Empty1,empty2为同步信号量，初值为1，分别表示缓冲区1，2空闲，可以存放记录

PA()

{

while(true)

   {

      P(empty1)

     从磁盘读一个记录

      

      将记录存入1

       V(full1)

}

}

PB()

{

while(true)

   {

      P(full1)

      从1取记录

      V(empty1)

      P(empty2) 

      将记录存入2

      V(full2)

      

    }

}

PC()

{

while(true)

   {

      P(full2) 

      从2取记录

      v(empty2)

      打印记录

    }

}

    什么是临界资源和临界区？

    同步机制应遵循哪些基本准则？

    试从物理概念上来说明记录型信号量及wait和signal操作。

    你认为整型信号量机制和记录型信号量机制是否完全遵循了同步机制的4条准则？

    实现进程通信的机制主要有哪几个？各有什么优缺点？

    为了让用户进程互斥地进入临界区，可以把整个临界区实现成不可中断的过程，即让用户具有屏蔽所有中断的能力。每当用户程序进入临界区的时候，屏蔽所有中断。当出了临界区的时候，再开放所有中断。你认为这种方法有什么缺点。

    作业

    1. 习题2中的13：针对有限和无限缓冲区的生产者和消费者问题

    2. 习题2中的18题：读写问题

    13题，针对无限缓冲区的生产者、消费者问题

    互斥信号量mutex,初始值为1

    同步信号量full，初始值为0

生产者进程

while(true)

{

 P(mutex);

信息送入缓冲区;

V(mutex);

V(full);

}

消费者进程

while(true)

{

P(full); 

P(mutex);

从缓冲区取信息;

V(mutex);

}

    因为是无限缓冲区，生产者不会因为得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以舍去在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。

    作业

    3.设自行车生产线上有一只箱子，其中有N个位置（N≥3），每个位置可存放一个车架或一个车轮；又设有三个工人，其活动分别为：

    定义3个信号量如下：

    Semaphone empty = N;

    Semaphone wheel = 0;

    Semaphone frame = 0;

工人1活动：

Do{

加工一个车架；

P(empty) ;

车架放入箱中；

V(frame);

}while(1)

工人2活动： Do{ 加工一个车轮； P(empty); 车轮放入箱中； V(wheel); }while(1)

工人3活动： Do{ P(frame);  箱中取一个车架  V(empty);    P(wheel);   P(wheel); 箱中取两个车轮； V(empty); V(empty); 组装为一台车 }while(1)

    工人1推进速度较快时，箱中空位置可能完全被车架占满或只留一个存放车轮的位置，若此时工人3同时取2个车轮将无法得到，而工人2又无法将新加工的车轮放入箱中，陷入死锁

    工人2推进速度较快时，也会出现类似情况

    为防止死锁的发生，箱中车架的数量不可超过N-2；车轮的数量不可超过N-1。

    这些可用两个信号量来表达：

    S1=N-2;

    S2=N-1;

习题课

死锁

•    资源的按序分配策略可以破坏（）条件

A.互斥使用资源

B.占有且等待资源

C.非抢占资源

D.循环等待资源

•    答案：D

•    银行家算法在解决死锁问题中是用于（）的。

A.死锁预防

B.死锁避免

C.死锁检测

D.死锁恢复

•    答案：B

•    为多道程序提供的可共享的资源不足时，可能出现死锁。但是，不适当的（）也可能产生死锁。

A.进程优先权

B.资源的线性分配

C.进程推进顺序

D.分配队列优先权

•    答案：C

•    某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。N的取值不超过（）时，系统不会发生死锁。

A.4

B.5

C.6

D.7

•    答案：B

•    在有m个进程的系统中出现死锁时，死锁进程的个数k应满足的条件是（）。

•    答案：2≤k≤m

•    3个进程共享4个资源，这些资源的分配与释放只能一次一个。已知每一个进程最多需要两个这类资源，则该系统（）。

A.有某进程可能永远得不到该类资源

B.必然有死锁

C.进程请求该类资源立刻能得到

D.必然无死锁

•    答案：D

•    若系统运行中出现如下所示的资源分配情况，该系统是否安全？如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？为什么？

	Work				Need				Allocation				Work+Allocation				Finish
	R1	R2	R3	R4	R1	R2	R3	R4	R1	R2	R3	R4	R1	R2	R3	R4
P0	1	6	2	2	0	0	1	2	0	0	3	2	1	6	5	4	T
P3	1	6	5	4	0	6	5	2	0	3	3	2	1	9	8	6	T
P4	1	9	8	6	0	6	5	6	0	0	1	4	1	9	9	10	T
P1	1	9	9	10	1	7	5	0	1	0	0	0	2	9	9	10	T
P2	2	9	9	10	2	3	5	6	1	3	5	4	3	12	14	14	T

•    若进程P2此时提出资源申请（1，2，2，2）

(1,2,2,2)<=Need2，(1,2,2,2)<=Available

此时再经安全性检测，得知系统进入不安全状态，不进行资源分配。

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

•    详细说明可通过哪些途径预防死锁？

•    死锁与饥饿之间有何相同点与不同点？

•    Dijkstra提出的银行家算法主要思想是什么？它能用来解决实际中的死锁问题吗？为什么？

•    一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用3个资源。若仅考虑此类资源，该系统有无可能产生死锁？为什么？

答案：因为产生死锁的原因有2点。本题介绍的系统，进程所需要的最大资源数为3*20=60，而系统中有资源65个，足够系统内的各进程使用，所有不会死锁。

处理机调度

•    进程调度又称低级调度，其主要功能是（）。

A.选择一个作业调入内存

B.选择一个主存中的进程调出到外存

C.选择一个外存中的进程调入到主存

D.将一个就绪的进程投入运行

•    答案：D

•    若进程P一旦被唤醒就能投入运行，系统可能是（）。

A.分时系统，P的优先级最高

B.抢占调度方式，就绪队列上的所有进程的优先级皆比P的低

C.就绪队列为空

D.抢占调度方式，P的优先级高于当前运行的进程

•    答案：D

•    在分时系统中，若当前运行的进程连续获得了两个时间片，原因可能是（）。

A.该进程的优先级最高

B.就绪队列为空

C.该进程最早进入就绪队列

D.该进程是一个短进程

•    答案：B

•    三种主要类型的操作系统中都必须配置的调度是（）。

A.作业调度

B.中级调度

C.低级调度

D.I/O调度

•    答案：C

•    支持多道程序设计的OS在运行过程中，不断选择新进程运行来实现CPU共享，但其中（）不是引起OS选择新进程的直接原因。

A.运行进程的时间片用完

B.运行进程出错

C.运行进程要等待某一事件发生

D.有新进程进入就绪队列

•    答案：D

•    既考虑作业等待时间，又考虑作业执行时间的调度算法是（）。

A.高响应比优先

B.短作业优先

C.优先级调度

D.先来先服务

•    答案：A

•    下列对多级队列调度和多级反馈队列调度不同点的叙述中，不正确的是（）。

A.多级队列用到优先权，而多级反馈队列调度中没有用到优先权

B.MPQ中就绪队列的设置不是像MQ一样按作业性质划分，而是按时间片的大小划分

C.MQ中的进程固定在某一个队列中，而MPQ中的进程不固定

D.MQ中每个队列按作业性质不同而采用不同的调度算法，而MPQ除了个别队列外均采用相同的调度算法。

•    答案：A

•    下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。

A.静态优先权法

B.抢占式调度中采用动态优先权算法

C.分时处理中的时间片轮转调度算法

非抢占式调度中采用FIFO算法

D.

•    答案：A

•    现有两道作业同时执行，一道以计算为主，另一道以输入输出为主，你将怎样赋予作业进程占有处理机的优先级，为什么？

•    为提高效率，应让管理输入输出的进程与计算进程搭配起来，并给予输入输出进程较高的优先级。

•    有5个批处理的作业ABCDE，它们几乎同时到达一个计算中心，估计的运行时间为2，4，6，8，10min。其优先级分别为1，2，3，4，5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间（进程切换开销可不考虑）。

–    最高优先级优先（22）

–    时间片轮转（时间片为2分钟）（18）

–    FIFO（按C,D,B,E,A）算法（19.2）

–    短作业调度算法（14）

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

–    先来先服务（按A,B,C,D,E）算法

–    优先级调度算法

–    时间片调度算法

•    先来先服务

执行次序	运行时间	优先数	等待时间	周转时间
A	10	3	0	10
B	6	5	10	16
C	2	2	16	18
D	4	1	18	22
E	8	4	22	30
平均周转时间=19.2

•    最高优先级调度算法

执行次序	运行时间	优先数	等待时间	周转时间
B	6	5	0	6
E	8	4	6	14
A	10	3	14	24
C	2	2	24	26
D	4	1	26	30
平均周转时间=20

•    时间片调度算法(令时间片为2min)

–    A,B,C,D,E

–    A,B,D,E

–    A,B,E

–    A,E

–    A

–    TA=30min,TB=22min,TC=6min,

TD=16min,TE=28min

–    平均周转时间=20.4min

•    有3个作业A（到达时间8：50，执行时间1小时），B（到达时间9：00，执行时间0.4小时），C（到达时间9：30，执行时间1小时）。当作业全部到达后，批处理单道系统按照响应比高者优先算法进行调度，则作业被选中的次序是（）

A.ABC

B.BAC

C.BCA

D.CBA

作业	到达时间	运行长度	开始时间	结束时间
A	8:50	1.5	9:54	11:24
B	9:00	0.4	9:30	9:54
C	9:30	1	11:24	12:24

•    作业全部到达后（9：30）系统开始调度

•    此时各作业的响应比为

–    A：1+0.67/1.5=1.4

–    B：1+0.5/0.4=2.25

–    C：1+0/1=1

–    首选B运行。

•    B运行后，各作业的响应比为

–    A：1+1.07/1.5=1.7

–    C：1+0.4/1=1.4

–    选择A运行，再选择C运行

•    答案：B

•    设某计算机系统有1个输入机，1台打印机。现有两道程序同时投入运行，且程序A先开始运行，程序B后运行。

•    A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。 

•    B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试说明

–    两道程序运行时，CPU有无空闲等待？若有，在哪段时间等待？为什么会空闲等待？

–    A,B运行时有无等待现象？若有，在什么时候发生等待？ 

•    CPU有等待时间，在第100ms到第150ms之间共空闲50ms。在此期间，A等待打印完成，B等待数据输入，因此CPU空闲。

•    A运行后无等待

•    B运行后130至150ms间有等待

•    对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行CPU调度？（抢占方式）

进程	到达时间	执行时间	开始截止时间
A	10	20	110
B	20	20	20
C	40	20	50
D	50	20	90
E	60	20	70

•    思考：若为非抢占方式，调度结果如何？

•    在一个有两道作业的批处理系统中，作业调度采用短作业优先级调度算法，进程调度采用抢占式优先级调度算法。设作业序列如表所示。

•其中给出的作业优先数即为相应进程的优先数。其数值越小，优先级越高。

•（1） 列出所有作业进入内存的时间及结束时间。

•（2） 计算平均周转时间和平均带权周转时间。

作业名	到达时间	预估运行时间（分钟）	优先数
A	8:00	40	10
B	8:20	30	5
C	8:30	50	8
D	8:50	20	12

作业	到达时间	进入内存时间	结束时间	周转时间
A	8:00	8:00	9:10	70
B	8:20	8:20	8:50	30
C	8:30	9:10	10:00	90
D	8:50	8:50	10:20	90

•    高级调度和低级调度的主要任务是什么？为什么引入中级调度？

•    在选择调度方式和算法时，应遵循的准则是什么？

•    为什么说多级反馈队列能较好地满足各种用户的需要？

•    在多处理机系统中，比较有代表性的线程调度方式有哪几种？

习题课  存储管理

•    多进程能在主存中彼此互不干扰的环境下运行，OS是通过（）来实现的。

A.内存分配

B.内存保护

C.内存扩充

D.地址映射

•    答案：B

•    动态重定位是在作业的（）中进行的。

A.编译过程

B.装入过程

C.链接过程

D.执行过程

•    答案：D

•    在存储器的可变分区管理中，作业装入内存时，采用的是（）重定位方式。

•    答案：动态

•    程序经编译或汇编以后形成目标程序，其中的指令顺序是以0作为参考地址进行编址的，这些地址称为（）。

•    答案：逻辑地址

•    分区管理中采用“最佳适应”分配算法时，把空闲区按（）次序登记在空闲区表中。

A.长度递增

B.长度递减

C.地址递增

D.地址递减

•    答案：A

•    一个32位的访存地址分为a,b,c,d四个域，a,b,c用于一个三级页表系统，d是页内偏移地址，则系统支持的最大页面数为（）。

•    答案：2（a+b+c）

•    虚拟存储管理系统的基础是程序的（）理论。

A.动态性

B.虚拟性

C.局部性

D.全局性

•    答案：C

•    下列诸项中，（）不是影响缺页中断率的主要因素。

A.缺页中断服务速度

B.分配给作业（进程）的物理块数

C.系统规定页面的大小

D.页面调度算法

•    答案：A

•    设一个段表如下

•    问

•    逻辑地址（2，88）

对应的物理地址是

(  )

•    逻辑地址（4，100）

对应的物理地址是

(  )

•    答案：178；地址越界，无任何物理地址产生

段号	基地址	段长
0	219	600
1	2300	14
2	90	100
3	1327	580
4	1952	96

•    设正在处理机上执行的一个进程的页表如下面所示，表中的虚页号和物理块号是十进制数，起始页号、块号均为0，所有的地址均是存储器字节地址，页的大小为1024字节。

•    计算下列逻辑地址对应于什么物理地址：5499，2221。

虚页号	状态位	引用位	修改位	物理 块号
0	1	1	0	4
1	1	1	1	7
2	0	0	0	-
3	1	0	0	2
4	0	0	0	-
5	1	0	1	0

•    （1）逻辑地址5499

逻辑地址对应的页号=5499/1024=5

逻辑地址对应的页内地址=5499mod1024=379

查页表可知该页在内存中，内存块号为0。

所以，逻辑地址5499对应的物理地址=0×1024+379=379

•    （2）逻辑地址2221

逻辑地址对应的页号=2221/1024=2

查页表可知该页不在内存中，无法知道其对应的物理地址。

•    

某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一个用户页表中已调入内存的页面页号和物理块号如右表。则逻辑地址0A5CH所对应的物理地址为（）。

页号	块号
0	5
1	10
2	4
3	7

•    共32个页面

–    页号占5位

•    每页为1KB

–    页内地址占10位

•    逻辑地址0A5CH对应的二进制形式

–    0000 1010 0101 1100 

•    0A5CH所在页：2；

•    对应块号为：4

答案：

0001 00 10 0101 1100 

125CH

•    

在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像表（即页表）如下：

页号	块号
0	2
1	4
2	6
3	8

•    试借助地址变换图（要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。

•    在一个使用交换技术的系统中，按地址从低到高排列的空闲内存空间长度是10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, 15KB。对于下列顺序的段请求

(1) 12KB  (2) 10KB  (3)15KB 

(4) 18KB  (5) 12KB

分别使用首次适配、最佳适配和下次适配算法说明空间的使用情况，并说明对暂不能分配情况的处理方法。

答案

•    首次适配

•    (1) 12KB     2＃

•    (2) 10KB     0＃

•    (3) 15KB     3＃

•    (4) 18KB     失败

•    (5) 12KB     6＃

答案

•    最佳适配

•    (1) 12KB     6＃

•    (2) 10KB     0＃

•    (3) 15KB     7＃

•    (4) 18KB     3＃

•    (5) 12KB     2＃

答案

•    下次适配

•    (1) 12KB     2＃

•    (2) 10KB     3＃

•    (3) 15KB     7＃

•    (4) 18KB     失败

•    (5) 12KB     6＃

答案

•    当出现暂时不能分配情况时，系统可以采用紧凑技术，将内存中的进程移动到存储器的一端，使夹杂于其间的空闲小空间移动到另一端，形成一个较大的可用空间，以满足用户的需求。

•    某计算机系统一条指令执行需10ns，一次缺页需要额外的20ms，如果每1 000 000条指令发生一次缺页，则指令的平均执行时间为（）ns。

•    10* 1 000 000=10ms

•    10+20=30ms

•    30/ 1 000 000=30ns

•    （北航02）考虑一个仅460字节的程序的下述内存访问序列（该序列的下标均从0开始）10，11，104，170，73，309，185，245，246，434，458，3，且页面大小为100字节，则

–    写出页面的访问序列

–    假设内存中仅有200字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断

–    如果采用最近最久未使用算法（LRU），则又会发生多少次缺页中断

•    写出页面的访问序列

–    0，1，0，3，1，2，4，3

•    假设内存中仅有200字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断

–    6

•    如果采用最近最久未使用算法（LRU），则又会发生多少次缺页中断

–    7

•    FIFO算法

–    0，1，0，3，1，2，4，3

•    LRU算法

–    0，1，0，3，1，2，4，3

•    在一个请求页式存储系统中，一个程序的页面走向为1，2，1，4，3，2，3，5，1，2，1，3。假定分配给该程序的存储块数为4，则采用FIFO和LRU页面置换算法时，访问过程中的缺页率分别为多少？

•    答案

–    FIFO算法：7/12

–    LRU算法:6/12

•    已知一个采用了LRU算法的虚拟分页管理系统，其页面尺寸为4K，内存访问速度为100ns/次，快表访问速度为20ns/次，缺页中断处理耗时为25 ms/次。今有一个长度为30K的进程P进入系统，分配给P的存储块有3块，进程的所有页面都是在该进程运行中动态装入。若P访问快表的命中率为20%，对于下述页面号访问序列：

7，0，1，2，0，3，0，4，2，3，2，1，2，0，1，7，0，1

•    请计算平均有效访问时间？

•    有效存取时间= (1-p)×ma 

        + p×缺页处理时间

•    缺页情况

–    缺页率0.6

–    缺页处理时间25ms

–    0.6*25=15ms

•    无缺页情况

–    快表命中

–    快表未命中

•    有效存取时间= (1-p)×ma 

        + p×缺页处理时间

•    无缺页情况

–    快表命中

–    20%*（20+100）ns

–    快表未命中

–    80%*（20+100+100）ns

•    有效存取时间15 000 080ns

•    可采用哪几种方式将程序装入内存？

•    在动态分区分配方式中，可利用哪些分区分配算法？

•    什么是地址重定位？

•    什么是碎片，内部碎片和外部碎片？

•    虚拟存储器的特征？

•    纯分页与请求式分页存储管理方案的主要区别？

•    在请求分页系统中，页表项包括哪些数据项？

•    什么是抖动？产生抖动的原因？

•    在请求分页系统中，通常采用哪种页面分配方式？（3种）

文件系统与设备管理部分复习

    （）不是文件系统的功能之一。

A.方便用户使用信息

B.提供用户共享信息的手段

C.提高信息安全程度

D.分配磁盘的存储空间

E.驱动外部设备

    答案：E

    文件系统中，使用（）管理文件 。

A.堆栈结构

B.指针

C.目录

D.页表

    答案：C

    文件系统按名存取的功能是通过（）来实现的 。

A.查文件目录

B.查作业控制块

C.查位示图

    答案：A

    在文件管理中可以利用位示图来实现（） 。

A.磁盘的调度

B.磁盘空间的管理

C.性能

D.文件目录查找

    答案：B

    文件分配的方法有（    ） 。

    答案：连续方式、链接块方式、索引方式

    在实现文件系统时把文件目录的目录项分解为索引结点和符号名目录项，这样的做的好处是什么？

    减少查找文件时读磁盘块的次数。

    有利于维护索引结点的安全性

    文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块号中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。

    块长为512字节，每个块号长3字节，所以一个索引块可以存放170个盘块号。

    二级索引时，最多可包含存放文件的盘块的盘块号总数为170*170，所以可寻址的文件的最大长度为170*170*512B

    三级索引时，最多可包含存放文件的盘块的盘块号总数为170*170*170，所以可寻址的文件的最大长度为170*170*170*512B

    在UNIX系统中，假定磁盘块大小是1KB，每个块号长4B，文件索引节点的磁盘地址明细表如图，请将下列文件的字节偏移量转换为物理地址。

    8000，13000，350000

    8000/1024 = 7，8000 % 1024=832

直接寻址，物理地址为101块内832字节

    13000/1024=12，13000%1024=712

12小于（256+10），一级索引，物理地址为954块内712字节

    磁盘的主要作用是（） 。

A.存放FAT表

B.用作交换区

C.存储文件

D.存放程序运行的中间结果

    答案：C

    引入块高速缓冲的主要目的是（） 。

A.提高CPU的利用率

B.提高I/O设备的利用率

C.改善CPU和I/O设备之间速度不匹配的情况

D.节省内存

    答案：C

    CPU输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用（） 。

A.并行技术

B.缓冲技术

C.需存技术

D.覆盖技术

    答案：B

    对于硬盘上存放的信息，物理上读写的最小单位是一个（） 。

A.二进位

B.字节

C.物理块

D.逻辑记录

    答案：C

    以下工作在I/O软件层的哪一层完成？

    为一个读操作计算磁道和扇区

    在设备寄存器中设置命令

    向设备寄存器写命令

    检查用户是否有权使用设备

    维护一个最近使用块的缓存

    将二进制整数转换成ASCII码以便打印

    答案：设备驱动程序层（3）；与设备无关软件层（2）；用户层（1）

    假定磁盘有200个柱面，编号是0至199。在完成了磁道125处的请求后，当前正在磁道143处为一个请求服务，若请求的队列的先后顺序是：86，147，91，177，94，150，102，175和130。

    用SCAN算法完成上述请求，存取臂共移动（）柱面

    用最短寻道时间优化算法，存取臂共移动（）柱面（比如：从0道移到2道，再移到1道，共移动3个柱面）

    答案

    SCAN算法：143->147->150->175->177->130->102->94->91->86.柱面移动数为125

    最短寻道时间优化算法：143->147->150->130->102->94->91->86->175->177.柱面移动数为162