操作系统试题整理 - 图文

简答1简述进程的状态及其转换的原因（图）

进程在其生存期内可能处于如下三种基本状态之一: 1) 运行态(Run): 进程占有处理机资源，正在运行。2) 就绪态(Ready): 进程已分配到除cpu以外所有的必要资源，只要在获得cpu，便可执行3) 阻塞态(Wait):正在执行的程序由于某事件二暂时无法继续执行便放弃处理机而出于暂停状态（1）就绪状态→执行状态：进程分配到CPU资源

（2）执行状态→就绪状态：时间片用完 （3）执行状态→阻塞状态：I/O请求 （4）阻塞状态→就绪状态：I/O完成。 简答2分页和分段有何区别?

a.分页和分段都采用离散分配的方式，且都要通过地址映射机构来实现地址变换，这是它们的共同点； b.对于它们的不同点有三，第一，从功能上看，页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，即满足系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组其意义相对完整的信息，目的是为了能更好地满足用户的需要；第二页的大小固定且由系统确定，而段的长度却不固定，决定于用户所编写的程序；第三分页的作业地址空间是一维的，而分段的作业地址空间是二维的。

简单3比较静态重定位和动态重定位。

1）地址转换时刻：静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地址转换的时刻推迟到指令执行时进行。

2）谁来完成任务：静态重定位是由软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。

3）完成的形式：静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。

4）完成的结果：实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。

简答4什么是虚拟设备？请说明SPOOLing系统是如何实现虚拟设备的。

虚拟设备是指通过虚拟技术，可将一台独占设备变换成若干台逻辑设备，供若干个用户（进程）同时使用。由于多台逻辑设备实际上并不存在，而只是给用户的一种感觉，因此被称为虚拟设备。

SPOOLING系统中，作业执行前，操作系统已将作业通过独占设备预先输入到磁盘或磁鼓上一个特定的存储区域（称之为\输入井\）存放好，称为\预输入\，此后，作业执行使用数据时不用再启动独占设备读入，而把这一要求转换成从辅助存储器中读入。另一方面，作业执行中，也不必直接启动独占设备输出数据，而只要将作业输出数据写入磁盘或磁鼓中的特定存储区域（称之为\输出井\）存放，当作业执行完毕后，由操作系统通过相应的输出设备来组织信息输出，称为\缓输出\。这样做可以提高独占设备的利用率，缩短作业的执行时间。这样，由于一台设备可以和辅助存储器中的若干存储区域相对应，所以在形式上就好像把一台输入设备（或输出设备）变成了许多虚拟的输入设备（或输出设备），即把一台不能共享的输入设备（或输出设备）转换成了一台可共享的缓冲输入设备（或输出设备），使用户产生一个\错觉\，好像他们各自都有一台专用的字符设备，从而实现虚拟设备。 简答5什么是死锁？发生死锁的四个必要条件是？

死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进； 必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件。

第1页 共22页

1. 分时系统的特征：多路性 独立性 及时性 交互性

2. 进程是作为分配资源的基本单位，线程是作为独立运行和独立调度的基本单位 3. 并发和共享是操作系统的两个最基本的特征。（虚拟性、异步性）

4. 处理机管理的主要功能是创建和撤销进程（线程），对诸进程（线程）的运行进行协调，实现进程（线

程）间的信息交流，以及按照一定的算法把处理机分配给进程（线程）。

5. 程序顺序执行特征：顺序性、封闭性、可再现性；程序并发特征：间断性、失去封闭性、不可再现性 6. 前驱图必须不存在循环 有向无循环图

7. 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的

基本单位，一个能与其他进程并发执行的进程。PCB是进程存在的唯一标志

8. 原子操作是指一个操作所有动作要么全做要么全不做。是一个不可分割的基本单位，不允许中断，在

管态下执行，常驻内存。

9. 进程同步两种制约关系：间接制约（共享某种资源）、直接制约（进程合作）

10. AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程。嗲进

程使用完后一起释放也称wait操作 11. 记录型信号量机制遵循“让权等待”原则. 1）消费者和生产者（记录型信号量）

(AND信号量)

2)哲学家进餐问题(记录型信号量)(AND信号量)

第2页 共22页

3)读者—写者问题(记录型信号量)

（AND型信号量）

4)和尚喝水

第3页 共22页

12. 管道机制必须提供三方面协调能力：互斥、同步和确定对方是否存在

13. 创建进程的过程：OS发现请求创建调用创建原语、申请空白PCB、分配资源、初始化进程控制块、插

入就绪队列。撤销进程的过程：从PCB集中检索出PCB读出状态、终止子进程、归还资源、移除PCB 14. 同步机构应遵循的基本准则是：空闲让进、忙则等待、有限等待、让权等待原因：为实现进程互斥进

入自己的临界区。

S1S2S3S4S5S615.

S7

在生产者消费者问题中，如果缺少了signal(full)戒signal(empty),对执行结果有何影响？

如果缺少signal(full)，那么表明从第一个生产者进程开始就没有改变信号量full 值，即使缓冲池产品已满，但full 值还是0，这样消费者进程执行wait(full)时认为缓冲池是空而取不到产品，消费者进程一直处于等待状态。

如果缺少signal(empty)，在生产者进程向n个缓冲区投满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品empty 值并不改变，直到缓冲池取空了，empty 值也是0，即使目前缓冲池有n 个空缓冲区，生产者进程要想 再往缓冲池中投放产品也会因为申请不到空缓冲区被阻塞。

16.在生产消费者问题中，如果将两个wait 操作即wait(full)和wait(mutex)互换位置，戒者将signal(mutex)不signal（full）互换位置，结果如何？

将wait(full)和wait(mutex)互换位臵后，可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了wait(mutex)操作并获得成功，则当再执行wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者进程执行signal(empty)来唤醒自己，在此之前，它不可能执行signal(mutex)操作，从而使试图通过执行wait(mutex)操作而进入自己的临界区的其他生产者和所有消费者进程全部进入阻塞状态，这样容易引起系统死锁。若signal(mutex)和signal(full)互换位臵后只是影响进程对临界资源的释放次序，而不会引起系统死锁，因此可以互换位臵。

例 1）有两个程序，A程序按顺序使用CPU l0s，使用设备甲5s，使用CPU 5s，使用设备乙10 s，最后使用CPU l0s。B程序按顺序使用设备甲10s，他用CPU 10s，使用设备乙5s，使用CPU 5s，使用设备乙10s。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少? 根据题意，A程序的运行时间为：10+5+5+10+10＝40 s， 其中cpu的运行时间为：10+5+10=25s。 B程序的运行时间为：10+10+5+5十10=40s， 其中cpu的运行时间为；10+5＝15s。 cpu的利用率为：（15+25）/（40+40）=50%

2）设有n个进程共享一个程序段，对如下两种情况： （1)如果每次只允许一个进程进入该程序段；

(2)如果每次最多允许m个进程(M＜＝n)同时进入该程序段。 试问：所采用的信号量初值是否相同?信号量值的变化范围如何? 所采用信号量的初值不相同。 在情况(1)中，信号量的初值为1，

第4页 共22页

信号量值的变化范围是l，0，-1?-(n-1)。 在情况(2)中，信号量的初值为M，

信号量值的变化范围是M，m-1，m-2?(m-n)。

3）有一个售票厅只能容纳200人，当少于200人时，可以进入；否则需在外等侯。若将每一个购票者作

为一个进程，请用P、v操作描写其互斥关系。 设公有信号量mutex=200 购票者进程： cobegin p(mutex) 进入购票厅； 购票； v(mutex) coend

4）一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥这看作一个进程，为保证安全，请用PV操作实现正确管理。

begin s：=1; cobegin begin

P(s); 过桥； V(s) end Coend end

s:semaphore;

5）两个并发进程的程序如下：若PROCESS A先执行了三个循环后，PROCESS A和PROCESS B 又并发执行

了一个循环，写出可能出现的打印值。请用PV操作进行管理，使它们并发执行时不出现与时间有关的错误。 若PR0CESS A先执行了三个循环后，N值变为3+5+5+5＝18；这时PROCESS A和PROCESS B并发执行了一个循环,这时可能出现的情况有以下几种： (1)print(N)；N：=0;N：＝N+5； (2)print(N)；N：＝N+5； N:=0； (3)N:=N十5；print(N); N:=0；

当出现情况(1)时，出现的打印值为18;当出现情况(2)时，出现的打印值为18;当出现情况(3)时，出现的打印值为23。为了使它们并发执行时不出现与时间有关的错误，我们采用了PV操作进行管理，其管理

的程序如上：

6）汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。

7）桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。规定每次当盘子空时只能放一个水果供顾客食用。请用信号量机制实现服务员、男顾客和女顾客三个进程的同步。

第5页 共22页

8）桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

9）a,b 两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车时，到达a（或b）的车辆可以进入ab段，但不能从a，b点同时驶入；当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用wait,signal工具对ab段实现正确管理。

第三章

18.高级调度又称作业调度或长程调度。主要功能是根据某种算法，把外存上处于后备队列的那些作业调入内存

19.低级调度称为进程调度或短程调度。主要功能是保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程。三大基本机制：排队器、分派器、上下文切换机制。调度方式：非抢占式、抢占式（优先权原则、短作业优先原则、时间片原则）。它的运行频率最高。 20.中级调度主要是为了提高内存利用率和系统的吞吐量。 21.调度算法（p92）

1）先来先服务（FCFS）算法利于长作业。 2）短作业优先调度（SJF）

完成时间=开始执行+服务时间；周转时间=完成时间-到达时间；带全周转时间=周转时间/服务时间 开始执行时间=上次任务的完成时间 服务时间=进程实际运行时间 开始执行时间-到达时间=等待时间 例有如下三道作业：系统为它们服务的顺序是：1、2、3. 求平均周转时间和平均带权周转时间

第6页 共22页

平均周转时间：T=(2+2.9+3)/3=2.63h平均带权周转时间：W=(1+2.9+12)/3=5.3h

3）高优先权优先调度算法。静态优先权是创建进程是确定的，依据有：进程类型、进程对资源的要求、用户要求。除此之外还有动态优先权。（响应比Rp）优先权=1+等待时间/要求服务时间。 4）时间片轮转法（RR）p95

例A、B、C、D、E五个进程，到达时间分别为0、1、2、3、4；执行时间分别为4、3、5、2、4.

q=1

q=4

5)多级反馈队列调度算法（cpu开销大） FIFO原则

时间片轮转的方式

22.实时调度

提供必要的信息：就绪时间、开始时间和完成截止时间、处理时间、资源要求、优先级。

假设系统中有m个周期性的硬实时任务C:处理时间；p：周期时间 单处理机情况下：需满足下面的限制条

CiCi件系统才是可调度的： 多处理机系统 N?N表处理机个数 ?1??i?1Pii?1Pi1）最早截止时间优先 算法(EDF非抢占式调度方式用于非周期实时任务)

mm

非抢占式调度方式用于非周期实时任务

抢占式调度方式用于周期实时任务 通常的优先级调度不适用于实时系统

例有两个周期性任务A和B。A的周期时间为20ms，每个周期的处理时间为10ms。B的周期时间为50ms，每个周期的处理时间为25ms。

第7页 共22页

2）最低松弛度优先算法（LLF）用于抢占式调度方式中 松弛度=必须完成时间－需运行时间－当前时间

一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。

例假如有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。

23．死锁指多个进程在运行过程中因争夺资源而造成一种僵局。 原因：竞争资源、进程间推进顺序非法。

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

处理死锁的基本方式：预防死锁（易实现）、避免死锁、检测死锁（利用率高）、解除死锁（利用率高）。 24.预防死锁

1）互斥条件：不能改变

2）摒弃“请求和保持”条件：一次性分配资源。简单但浪费资源，系统吞吐量大。 3）摒弃“不剥夺”条件::当进程资源请求不能满足，放弃所有资源。代价大，前功尽弃。 4）摒弃“环路等待：对资源预先排列，依次提出请求。

25.避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。 例：三个进程共享12台磁带机

安全序列：

26.利用银行家算法避免死锁（p109）

27.死锁定理：死锁状态的充分条件，资源分配图不可完全简化

例1) 在一个有N个进程的单处理机系统中，有可能出现N个进程都被阻塞的情况( ) 系统处于不安全状态必然导致系统死锁。( )

2)当一进程运行时，系统可基于某种原则，强行将其撇下，把处理机分配给其他进程，这种调度方式是（） A.非剥夺方式 B.剥夺方式 C.中断方式 D.查询方式

3)在为多道程序所提供的可共享的系统资源不足时可能出现死锁。但是，不适当的（）也可能产生死锁。 A.进程优先权 B.资源的线性分配 C.进程推进顺序 D.分配队列优先权

4)发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏（）条件是不太实际的。A.互斥 B.不可抢占 C.部分分配 D.循环等待

5)在分时操作系统中，进程调度经常采用（）算法。A.先来先服务 B.最高优先权C.时间片轮转D.随机 6)（）优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。 A.先来先服务 B.静态 C.动态 D.短作业

7)某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（）

第8页 共22页

A.9 B.10 C.11 D.12

8)在下列解决死锁的方法中，属于死锁预防策略的是：

A.银行家算法 B.资源有序分配法 C.死锁检测法 D.资源分配图化简法 9)资源的按序分配策略可以破坏（）条件。

A.互斥使用资源 B.占有且等待资源 C.非抢占资源 D.循环等待资源 10)进程的调度方式有两种，一种是（），另一种是（）

11)在（）调度算法中，按照进程进入就绪队列的先后次序来分配处理机。 12)死锁产生的必要条件有四个，即（）、（）、（）、（）。

13)银行家算法中，当一个进程提出的资源请求将导致系统从（）进入（）时，系统就拒绝它的资源请求。 14)对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于（），破坏环路等待条件是属于（），而剥夺资源是（）的基本方法。

15)某分时系统中的进程可能出现如下图所示的状态变化，回答下列问题： （1）根据图示，该系统采用的是什么进程调度策略？ （2）指出图示中的每一个状态变化的原因。

16) n个进程共享某种资源Ｒ，该资源共有m个可分配单位，每个进程一次一个的申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m+n，试证明在这个系统中不可能发生死锁。

设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：

max(1)+?+ max(n)=(need(1)+?+need(n))+(alloc(1)+?+alloc(n))

另一方面所有进程将陷入无限等待状态。 由上述两式可得：need(1)+?+need(n)

上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need(i)=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

17) 有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高.列出所有作业进入内存的时刻以及结束的时刻。计算作业的平均周转时间。

10：00 A到达，无竞争，开始运行；

10：20 B到达，进入主存，优先数为3，优于A,B开始运行 10：30 C到达，不可进入；

10：50 B结束，同时D到达，同C争夺内存，D运行时间短，被调度进入内存；A的优先数高，开始运行；

第9页 共22页

11：10 A结束，C进入内存，C的优先数高于D,开始运行； 12：00 C结束, D开始运行；

12：20 D结束。平均周转时间=280/4=70分钟 18) 在银行家算法中，若出现下述资源分配情：

试问：⑴ 该状态是否安全？⑵ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？

⑴该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。

⑵若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。

19）某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2

和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：(南京大学1999年试题) J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms).

处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题： （1）分别计算作业J1、J2和J3从开始到完成所用的时间。 （2）3个作业全部完成时CPU的利用率。 （3）3个作业全部完成时外设I01的利用率。

20)

假设有4道作业，它们的提交时刻及执行时间由下表给出：计算在单道程序环境下，采用先来先服

先来先服务：1，2，3，4

务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序

第10页 共22页

首次适应算法空闲分区表和最佳适应算法分析表

12）设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为多少位?内存空间有多大? 2048＝ 211， 16＝ 24，逻辑地址至少为15位。 内存：8×2048＝214＝16K

13）在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列是：115，228，120，88，446，

102，321，432，260，167，若作业的第0页已经装入内存，现分配给该作业的主存共300字，页的大小为100字，则：

（1）按FIFO算法将产生_次缺页中断，依次淘汰页号为_ 0，1，2缺页中断率为：5/10=50%

(2)按LRU算法将产生_次缺页中断，依次淘汰页号为_ 2，0，1，3缺页中断率为：6/10=60% 14）有一请求分页存储管理系统，页面大小为每页100字节。有一个50×50的整型数组连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下： int a[50][50]; int i, j;

for (i=0; i<=49; i++) for (j=0; j<=49; j++) a[i][j]=0;

若在程序执行时内存中只有一个存储块用来存放数组信息，试问该程序执行时产生多少次缺页中断？ 由题目可知，该数组中有2500个整数，每个整数占用2个字节，共需存储空间

5000个字节；而页面大小为每页100字节，数组占用空间50页。假设数据从该作业的第 m页开始存放，则数组分布在第m页到第m+49页中，它在主存中的排列顺序为： a[0][0]，a[0][ll，?，a[0][49] 第m页 a[1][0]，a[1][1]，?，a[1][49] 第m+l页 ┇

a[49][0]，a[49][1]，?，a[49][49] 第m+49页

由于该初始化程序是按行进行的，因此每次缺页中断调进一页后，位于该页内的数组元素全部赋予0值，然后再调入下一页，所以涉及的页面走向为m，m+l，?，m+49，故缺页次数为50次。

15）在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为4时，试计算采用先进先出淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并将所得结果填表。

第16页 共22页

缺页率10/12

M=3

如果将前三页计算其中，其缺页次数为9次，缺页率为9/12=75%； 如果不计入前三页，其缺页次数为6次，缺页率为6/12=50%。 M=4

如果将前四页计算其中，其缺页次数为10次，缺页率为10/12=83.3%。块数多了，并没有降低缺页率，反而占内存多。但实际中，统计次数应更多，以便得出更接近实际的结果。 如果不计入前四页，其缺页次数为6次，缺页率为6/12=50%。

16）有一矩阵“int a[100][100]”以行为先进行存储。有一个虚拟存储系统，物理内存共有3页，其中1页用来存放程序，其余2页用于存放数据。假设程序已在内存中占1页，其余2页空闲。 程序A：

for (i=0; i<=99; i++)

for (j=0; j<=99; j++)

a[i][j]=0;

程序B： for (j=0; j<=99; j++)

for (i=0; i<=99; i++)

a[i][j]=0;

个整数呢？

若每页可存放200个整数，程序A和程序B的执行过程各会发生多少次缺页？若每页只能存放100

17）某分页系统的逻辑地址是16位，其中高6位为页号，低10位为页内地址，则这样的地址结构 （1）一页有2^10字节；2^10=1K （2）逻辑地址可有2^6页；2^6=64

（3）一个作业最大的使用空间是2^16-1字节。 18) 有一页式系统，其页表存放在内存中。

第17页 共22页

（1）如果对内存的一次存取需要1.5微秒，问实现一次页面访问的存取时间是多少

（2）如果系统增加有快表，平均命中率为85％，当页表项在快表中时，其查找时间忽略为0，问此时的存取时间为多少？

如果页表在主存的话，那么会两次访问内存：第一次是访问页表，从而找到线性地址对应的物理地址第二次是利用找到的物理地址来访问实际的内存页面。所以需要3微秒

有快表，在快表中得到物理地址到主存找（概率85%）； 表目不在快表中在主存（两次访问主存，一次表目，一次数据）（概率15%）：1.5*0.85+3*0.15=1.725微秒

19) 知某分页系统，主存容量为64KB，页面大小为1KB。对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。

（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址； （2）以十进制的逻辑地址1023为例画出地址变换过程图。

①逻辑地址1023:1023/1k,得到页号为0,页内地址为1023,查页表找到对应的物理块号为2,故物理地址为2×1K+1023=3071。

②逻辑地址2500：2500/1K，得到页号为2,页内地址为452,查页表找到对应的物理块号为6,故物理地址为6×1K+452=6596。

③逻辑地址3500:3500/1K,得到页号为3,:页内地址为428,查页表牛找到对应的物理块号为7,故物理地址为7×1K+428=7596。

④逻辑地址4500:4500/1K,得到页号为4,页内地址为404,因页号不小于页表长度,故产生越界中断。P=int[A/L] 和 d=[A]mod L 其中A为逻辑地址空间，页面大小为L，P为页号，页内地址为d

20) 对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（5，230）转换成物理地址。

21）在一分页式存储管理中，逻辑地址长度为16位（条件变为：用户编程空间共32个页），页面大小为

2048字节，对应页表如下，现有逻辑地址05ACH，2F6AH，经过地址变换后所对应的物理地址各是多少？

页面大小为2048字节，则页内地址需要11位。 页号为 16 – 11 = 5 位。

第18页 共22页

22）

第五章

例当前磁盘读写位于柱面号20，此时有多个磁盘请求，以下列柱面号顺序送至磁盘驱动器：10、22、20、

2、40、6、38。寻道（Track）时，移动一个柱面需6ms，按下列算法计算所需寻道时间（柱面移动顺序及所需时间，总寻道时间；忽略到达指定柱面后所需寻道时间）。(上海交通大学1999年试题) ① 先来先服务。 ② 下一个最邻近柱面。

③ 电梯算法（当前状态为向上）。 先来先服务：

① 磁头移动顺序为：（20）→10→22→20→2→40→6→38 磁头移动总量是146柱面，总寻道时间是：146×6ms＝876ms.

② 下一个最邻近柱面：

磁头移动顺序为：（20）→20→22→10→6→2→38→40 磁头移动总量是60柱面，总寻道时间是：60×6ms＝360ms. ③ 电梯算法

磁头移动顺序为：（20）→20→22→38→40→10→6→2 磁头移动总量是58柱面， 总寻道时间是：58N×6ms＝348ms.

29.寻道时间Ts=m*n+s m=0.2(速度) 旋转延迟时间Tr=1/2r r每秒转数 传输时间Tt=b/rN b每次读取字节数N为磁道字节数 访问时间Ta=Ts+1/2r+b/rN

第六章

30.有一个含10^4N个记录的顺序文件，对他采用顺序查找法去查找，平均需要查找5*10^3N/2个记录。一级索引顺序查找为10^2N^1/2 二级索引 3/2*N^1/3 31.FAT 文件分配表 FCB文件控制块

32.每个盘块大小为1KB 每个盘块号占4字节，则一个索引块可存放256个盘块号。两级索引时，最多可包含的存放文件的盘块的盘块号总数N=256*256=64K个盘块号。两级索引允许文件最大长度为64MB。同理，盘块大小为4KB,单级索引最大文件长度为4MB，两级索引最大文件长度可达4GB。

33.FCB长度为32个字节，对于360KB的软盘，总共可包含112个FCB，共占4KB存储内存。 一个FCB为64B，盘块大小为1KB，则每个盘块中只能存16个FCB

若一个文件目录中有640个FCB，许共占40个盘块，故平均查找一个文件需启动磁盘20次。 目录文件所占盘块为N，查找一个目录项平均需要调入盘块（N+1）/2次

一个FCB为64B，一个盘块为1KB，设共有3076个文件，因一个盘块只能放1024/64=16个FCB，故文件目

第19页 共22页

录占了3076/16=192个块，当要访问某文件，最大调度块数为192次，平均调度块数为（192+1）/2

34. FAT12单个分区的最大容量： 2^12*512B＝2MB

35.

簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n (n为整数)个盘块。

每个簇在FAT表的表项中占4个字节每个簇固定为4KB.

36.

试问该文件系统能否指引一个512MB的磁盘？

例1）．假定一个文件系统的组织方式与MS-DOS相似，在FAT中可有64K个指针，磁盘的盘块大小为512B，解：512MB/512B=1M个盘块，而每个盘块都应有一个指针来指示，所以应该有1M个指针，因此若有64K个指针则不能指引一个512MB的磁盘

2）在UNIX中，如果一个盘块的大小为1KB，每个盘块号占4个字节，即每块可放256个地址。请转换下列文件的字节偏移量为物理地址。

⑴ 9999； ⑵ 18000； ⑶ 420000

盘块大小为1KB，盘块号占4B，即每个盘块最多可存放256个盘块号。又根据UNIX系统中采用的混合索引分配方式可知： 9999/1024=9余783 18000/1024=17余592 420000/1024=410余160

3）有一计算机系统利用图6-33所示的位示图来管理空闲盘块。盘块的大小为1KB，现要为某文件分配量个盘块，试说明盘块的具体分配过程。 分配量个盘块的过程如下：

⑴ 顺序扫描位示图，从中找到第一个值为0的二进制位，得到其行号i=3，列号j=3。 ⑵ 将所找到的二进制位转换成与之对应的盘块号。盘块号计算公式为：b=（3-1）*16+3=35； ⑶ 修改位示图，令map[3，3]=1，并将该盘块分配出去。

类似地，可使用相同的方法找到第二个值为0

的二进制位，得到行号i=4，列号j=7，其对应的盘块号为55，令map[i，j]=1，并将该盘块分配出去。 4）某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理磁盘空间，试问： ⑴ 位示图需要多少字？

⑵ 第i字第j位对应的块号是多少？ ⑶ 给出申请/归还一块的工作流程。 [500/32]z=16个字

b=(i-1)*32+j=32(i-1)+j (b从1开始计数，i，j也从1开始计数) 根据盘块号b求出：

i = (b-1)/32 + 1; j = (b-1)2 + 1;

第20页 共22页

本文来源：https://www.bwwdw.com/article/went.html