当前位置：首页 > news >正文

操作系统复习指南：知识点整理与习题解析

news 2024/11/18 11:30:58

第一章

考点：OS的基本特征和功能

基本特征：

1.并发

并行性和并发性是既相似又有区别的两个概念：

并行性：是指两个或多个事件在同一时刻发生；

并发性：是指两个或多个事件在同一时间间隔内发生。

在多道程序环境下，并发性是指在一段时间内，宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。

2.共享

在操作系统环境下，所谓共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用。由于资源属性的不同，进程对资源共享的方式也不同，目前主要有以下两种资源共享方式：

互斥共享

同时共享【”同时“:微观：交替运行】

3.虚拟

操作系统中的所谓“虚拟”，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。物理实体(前者)是实的，即实际存在的；而后者是虚的，是用户感觉上的东西。相应地，用于实现虚拟的技术，称为虚拟技术。在OS中利用了多种虚拟技术，分别用来实现虚拟处理机、虚拟内存、虚拟外部设备和虚拟信道等。

4.异步

在多道程序环境下，允许多个进程并发执行，但只有进程在获得所需的资源后方能执行。在单处理机环境下，由于系统中只有一个处理机，因而每次只允许一个进程执行，其余进程只能等待。由于资源等因素的限制，使进程的执行通常都不是“一气呵成”，而是以“停停走走”的方式运行。

尽管如此，但只要运行环境相同，作业经多次运行，都会获得完全相同的结果。

功能：

处理机功能（进程管理）

存储器功能

设备管理（I/O管理）

文件管理

接口管理

1. 进程控制

2. 进程同步

3. 进程通信

4. 进程调度

1.内存分配

2.内存保护

3.地址映射

4.内存扩充

1.缓冲管理

2.设备分配

3.设备处理

1.文件存储空间的管理

2.目录管理

3.文件的读/写管理和保护

1.命令接口

2.程序接口

3.图形用户接口

例题：

4. 操作系统具有哪些特征？它们之间有何关系？

要点：并发、资源共享、虚拟、异步性；

并发和共享是操作系统最基本的特征、并发和共享互为存在、虚拟以并发和资源共享为前提、异步性是并发和共享的必然结果。

第二章

1.为什么引入进程、基本状态及转换

原因：

在os中引入进程，是为了实现多个程序的并发执行，并且可以对并发执行的程序加以描述和控制。

基本状态：

1) 就绪(Ready)状态：进程已准备好运行，并等待CPU分配。

2) 执行状态：进程正在CPU上执行。

3) 阻塞状态：进程由于等待某种条件（如I/O完成）而无法继续执行。

基本状态转换：

就绪到执行：当CPU空闲时，操作系统从就绪队列中选择一个进程让其运行。
执行到就绪：当一个进程正在运行，但调度程序决定让出CPU（如时间片到期）。
执行到阻塞：进程执行时请求I/O操作，无法立即完成。
堵塞到就绪：I/O操作完成后，进程被唤醒并准备再次运行。

2.信号量含义、物理意义、信号量应用

含义：

信号量是一个计时器，可以用来控制多个进程对共享资源的访问。

它常会被作为一种锁机制，用于防止某进程正在访问共享资源（如共享内存）时，其他进程也来访问该资源。

因此，信号量主要作为进程间以及同一进程内不同线程间的同步手段。

一个信号量S是一个整数量，除对其初始化外，它只能由两个原子操作P和V来访问，分别称为wait(),signal()

wait(){

while(S<=0);

S--;

}

Sign(){

S++;

}

物理意义：

S>0:表示有S个资源可用

S=0:表示无资源可用

S<0:|S|表示S等待队列中的进程个数

应用：

利用信号量实现进程互斥

实现进程互斥时可以分为以下几个步骤：

1、分析并发进程关键活动，划分临界区（如：对临界资源打印机的访问就应放在临界区）

2、设置互斥信号量mutex，初值为1（信号量mutex表示“进入临界区的名额”）

3、在进入区P(mutex)——申请资源

4、在退出区V(mutex)——释放资源

注意：对不同的临界资源需要设置不同的互斥信息量
P、V操作必须成对出现。缺少P操作会导致临界资源不能被互斥访问，缺少V操作会导致资源被访问后无法被释放，等待进程永不会被唤醒

信息量机制实现前驱关系

其实每一对前驱关系都是一个进程同步关系(需要保证一前一后)，因此实现前驱关系可以分为以下步骤：
1、要为每一对前驱关系设置一个同步信息量
2、在“前操作”之后对相应的同步信息量执行V操作
3、在“后操作”之前对相应的同步信息量执行P操作

3.三大经典进程同步问题（尤其是读者-写者问题）

生产者消费者问题

系统中有一组生产者进程和一组消费者进程。生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个进程并使用，那么他们之间具有这样一层关系

生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区。否则必须等待 (缓冲区没满->生产者生产)

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待 (缓冲区不空->消费者消费)

缓冲区是临界资源，各进程访问时要求互斥 (互斥访问)

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问

semaphore empty = n; //同步信号量，表示空闲缓冲区的数量

semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量

生产者生产

消费者消费

producer (){

while(1){

生产一个产品;

P(empty);

P(mutex);

把产品放入缓冲区;

V(mutex);

V(full);

} }

consumer (){

while(1){

P(full);

P(mutex);

从缓冲区取出一个产品;

V(mutex);

V(empty);

使用产品; }

P(mutex)和V(mutex)实现进程的互斥访问，P(empty)实现让缓冲区没满作为生产者生产的前操作，即当empty==0时即无空闲缓冲区数量时，让消费者消费作为生产者生产的前操作

V(full)实现让缓冲区不空作为消费者消费的前操作，即当full==0时即缓冲区全为空时，让生产者生产作为消费者消费的前操作

P(mutex)和V(mutex)实现进程的互斥访问，V(empty)实现让缓冲区没满作为生产者生产的前操作，即当empty==0时即无空闲缓冲区数量时，让消费者消费作为生产者生产的前操作

P(full)实现让缓冲区不空作为消费者消费的前操作，即当full==0时即缓冲区全为空时，让生产者生产作为消费者消费的前操作

哲学家进餐问题

互斥关系
5位哲学家与左右邻居对中间筷子的访问是互斥的

哲学家进餐问题需要每个哲学家同时持有两个临界资源才能开始吃饭，如何避免临界资源分配不当造成的死锁现象，是哲学家进餐问题的精髓。

信号量设置定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问，并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

semaphore chopstick[5]={1,1,1,1,1};semaphore mutex = 1; //互斥地取筷子Pi (){ //i号哲学家的进程while(1){P(mutex);P(chopstick[i]); //拿左P(chopstick[(i+1)%5]); //拿右V(mutex);吃饭…V(chopstick[i]); //放左V(chopstick[(i+1)%5]); //放右思考… } }

读者-写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出

互斥关系
写进程和写进程访问共享数据时互斥
写进程和读进程访问共享数据时互斥

semaphore rw=1; //用于实现对共享文件的互斥访问

int count = 0; //记录当前有几个读进程在访问文件

semaphore mutex = 1;//用于保证对count变量的互斥访问

写者

读者

writer (){

while(1){

P(rw); //写之前“加锁”

写文件…

V(rw); //写完了“解锁” } }

reader (){

while(1){

P(mutex); //各读进程互斥访问count

if(count==0) //由第一个读进程负责

P(rw); //读之前“加锁”

count++; //访问文件的读进程数+1

V(mutex);

读文件…

P(mutex); //各读进程互斥访问count

count--; //访问文件的读进程数-1

if(count==0) //由最后一个读进程负责

V(rw); //读完了“解锁”

V(mutex);

} }

1.以下可能导致一个进程从运行态变为就绪态的事件是（D）。

A．一次I/O操作结束
B．运行进程需做I/O操作
C．运行进程结束
D．出现了比现在进程优先级更高的进程

解析：如果有高优先级的进程出现，当前运行的进程会被抢占，转为就绪态。

2 .（B）必会引起进程切换。

A、一个进程创建后，进入就绪状态
B．一个进程从运行状态变为就绪状态
C．一个进程从阻塞状态变为就绪状态
D．以上答案都不对

解析：因为当一个进程放弃CPU（被中断或者主动让出 CPU），就会将它的状态从运行变为就绪,这将导致调度程序选择另一个就绪状态的进程来运行。

3.一个进程被唤醒，意味着（A）。

A．该进程可以重新竞争CPU B．它的优先权变得最大

C．其PCB移至等待队列队首 D．进程变为运行态

解析：当进程被唤醒时，它会进入就绪队列，有机会重新争夺 CPU

4.下列选项中，会导致进程从执行态变为就绪态的事件是（D）。

A．执行 P(wait)操作

B．申请内存失败

C．启动 I/O 设备

D．被高优先级进程抢占

解析：通常 P 操作可能使进程阻塞，而非变为就绪。

申请内存失败会导致进程阻塞，但不会直接引发变为就绪态。

启动 I/O 通常会导致进程进入阻塞态。

当前进程被高优先级进程抢占会导致它从运行态变为就绪态。

5 .下列选项中，可能导致当前P阻塞的事件是（C）。

Ⅰ.进程 P 申请临界资源

Ⅱ. 进程 P 从磁盘读数据

Ⅲ. 系统将 CPU 分配给高优先权的进程
A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅰ、Ⅱ D.Ⅰ、Ⅱ、Ⅲ

解析：如果申请的资源正在被其他进程占用，需要进入待机状态（阻塞），当前进程将会被阻塞。

磁盘 I/O 操作会导致进程阻塞，等待数据完成读取。

6.下列选项中，可能会将进程唤醒的是（C）。

I. I/ O 结束 Ⅱ. 某进程退出临界区 Ⅲ . 当前进程的时间片用完
A. 仅I B. 仅Ⅲ C. 仅 I、Ⅱ D. I、Ⅱ、Ⅲ

解析：

Ⅰ. I/O 结束：

当一个进程在等待I/O操作（例如读取文件）的完成时，它会进入阻塞状态。一旦I/O操作完成，操作系统会唤醒该进程将其变为就绪状态，因此I/O结束确实能唤醒进程。

Ⅱ. 某进程退出临界区：

如果一个进程在等待进入临界区，而当前临界区被其他进程占用，那么这个进程会处于阻塞状态。当之前占用临界区的进程退出后，等待中的进程将被唤醒并进入临界区。因此，某进程退出临界区也会导致被阻塞的进程唤醒。

Ⅲ. 当前进程的时间片用完：

当进程的时间片用完时，它被抢占并转到就绪状态，但这并不涉及到阻塞状态的转变或唤醒其他进程。时间片用完的进程不是从阻塞状态变为就绪状态，而是从运行状态变为就绪，因此时间片结束本身不会唤醒其他进程。

7.在任何时刻，一个进程的状态变化（C）引起另一个进程的状态变化。

A. 必定 B. 一定不 C. 不一定 D. 不可能

解析：一个进程的状态变化有可能不影响其他进程。

10.不需要信号量就能实现的功能是（D）。

A．进程同步 B．进程互斥
C．执行的前驱关系 D．进程的并发执行

解析：信号量是一种用于实现进程间同步和互斥的机制，主要用于控制对共享资源的访问和协调进程执行的顺序。进程的并发执行本身不依赖于信号量。只有当这些进程之间需要进行同步或互斥时，才需要使用信号量等同步机制。

11.设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待资源的进程数，则M，N分别是(B )
A．0，1 B．1，0
C．1，2 D．2，0

解析：

分析资源的可用个数 M：

信号量的当前值 S（当 S ≥ 0 时），直接表示当前可用的资源数量。

因此：M = 信号量当前值 S = 1

这意味着当前有 1 个资源可用。

分析等待资源的进程数 N：

根据信号量的机制：当信号量的值 S < 0 时，表示有进程在等待资源，等待的进程数量为 |S|（即信号量的绝对值）。

然而：当前信号量的值为 1（S = 1），是大于等于零的，意味着没有进程在等待资源。

因此：N = 0

12.一个正在访问临界资源的进程由于申请等待I/O操作而被中断时，它是(C)。
       A．可以允许其他进程进入与该进程相关的临界区
       B．不允许其他进程进入任何临界区
       C．可以允许其他进程抢占处理器，但不得进入该进程临界区
       D．不允许任何进程抢占处理器

解析：当一个进程正在访问临界资源（处于临界区）时，它持有对该资源的独占访问权限。此时，如果该进程因为等待 I/O 操作而被中断或阻塞，操作系统会将其从 CPU 上调度下来，进入阻塞状态。

进程阻塞后，处理器可以被其他进程抢占使用：被阻塞的进程不再占用 CPU，其他进程可以获得 CPU 时间片。

保持临界资源的互斥性：尽管该进程被阻塞，但它仍然持有临界资源的使用权，其他进程不能进入与之相关的临界区，从而保证数据的一致性和正确性。

14.在操作系统中，P、V操作是一种（D）。

A．机器指令 B．系统调用命令
C．作业控制命令 D．低级进程通信原语

解析：

P、V 操作是荷兰计算机科学家 Dijkstra 提出的用于实现进程间同步和互斥的基本同步原语，通过操作信号量来达到控制进程执行的目的。

作为进程同步和互斥的基本工具，P、V 操作属于低级进程通信原语，提供了进程间同步与通信的基础机制。

15.用P、V操作实现进程同步，信号量的初值为(B)
A．-1 B．0 C．1 D．由用户确定

解析：

进程同步指的是按照特定顺序协调进程的执行，例如一个进程需要等待另一个进程完成某项任务。

用于同步的信号量初值通常设为0，原因是：

等待进程：执行 P(S)，此时 S = 0，执行 P 操作后，S = S - 1 = -1，进程被阻塞。

通知进程：执行 V(S)，将信号量值加 1，若 S ≤ 0，唤醒等待队列中的进程。

通过初始值为 0 的信号量，可以实现进程间的同步等待与通知机制。

16.有三个进程共享同一程序段，而每次只允许两个进程进入该程序段，若用PV操作同步机制，则信号量S的取值范围是(A)。
A．2，1，0，-1 B．3，2，1，0

C．2，1，0，-1，-2 D．1，0，-1，-2

解析：

初始信号量 S 的值为允许进入该程序段的最大进程数，即 S = 2。

当进程执行 P 操作（请求进入）时，S = S - 1。

当进程执行 V 操作（离开）时，S = S + 1。

取值范围计算：

初始时，S = 2。

第一个进程进入（执行 P(S)）：S = 2 - 1 = 1

第二个进程进入（执行 P(S)）：S = 1 - 1 = 0

如果第三个进程尝试进入（执行 P(S)）：S = 0 - 1 = -1，S < 0，进程阻塞。

因此，信号量 S 的可能取值为 2，1，0，-1。

17.若一个系统中共有5个并发进程涉及某个相同的变量A ，则变量A的相关临界区是由(C)个临界区构成的。
A. 1 B．3 C．5 D．6

解析：

每个涉及到共享变量 A 的进程中，对 A 的访问都需要放在临界区内，以保证对共享资源的互斥访问。

共有 5 个并发进程涉及变量 A，因此，每个进程都有自己对应的临界区。

因此，变量 A 的相关临界区总共由 5 个临界区构成。

13.在操作系统中，要对并发进程进行同步的原因是（C）。

A．进程必须在有限的时间内完成 B．进程具有动态性
C．并发进程是异步的 D．进程具有结构性

解析：

并发进程的异步性意味着多个进程在独立执行，执行速度和顺序不可预测，这可能导致对共享资源的竞争和不一致性。

需要对并发进程进行同步，以协调它们在特定条件下的执行顺序，确保共享资源的正确访问，防止竞态条件的发生。

18.进程P0和P1的共享变量定义及其初值为

    boolean flag[2];
    int turn=0;
    flag[0]=false; flag[1]=false;

若进程P0和P1访问临界资源的类C代码实现如下：

则并发执行进程P0和P1时产生的情况是（A）。

A．不能保证进程互斥进入临界区，会出现“饥饿”现象
B．不能保证进程互斥进入临界区，不会出现“饥饿”现象
C．能保证进程互斥进入临界区，会出现“饥饿”现象
D．能保证进程互斥进入临界区，不会出现“饥饿”现象

解析：

1.互斥性：

由于 P0 和 P1 都在检查对方的 flag 状态以及 turn 的标志，两个进程不会同时进入临界区。这确保了互斥性。

2.饥饿现象：

如果 P0 和 P1 交替发生，即：

P0 设置 flag[0] 为 TRUE，然后设置 turn = 1。

P1 紧接着也想进入，将 flag[1] 设置为 TRUE，设置 turn = 0。

在这种情况下，两个进程一直倾向于等待对方并且没有一个进程被允许进入临界区，可能导致饥饿现象的发生。

19.进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示

下列选项中，需要互斥执行的操作是（C）。

A.a=1与a=2 B.a=x与b=x

C.x+=1与x+=2 D.x+=1与x+=3

解析：

A. 这两个操作只是在各自线程内部定义的局部变量 a，与共享变量 x 无关，因此不需要互斥。

B. a=x、b=x要求 “b=x”发生在之后，要求的是需要同步执行。

D.x+=1、x+=3并不在同一个进程之中，两个x并不相同，故无任何关联。

C. 这两个操作都对共享变量 x 进行修改。由于多个线程可以同时对 x 进行写操作，可能导致数据竞争和不一致，因此需要互斥执行，确保在写 x 时不会有其他线程同时修改它。

第三章

1.各进程调度算法的基本思路及特点（利用坐标法解题）

周转时间=作业完成时间-作业提交时间

带权周转时间=作业周转时间/作业实际运行的时间

先来先服务调度算法

算法基本思想：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。

短作业(进程)优先调度算法

SJF算法以进入系统的作业或进程所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。

高响应比优先调度算法

算法基本思想：HRRF算法在当前作业执行完时，计算剩余作业的响应比，选取响应比最高的作业投入运行。

基于时间片的轮转调度算法

算法主要针对分时系统，适用于进程调度

2.死锁的定义、产生的原因及必要条件、预防和检测死锁的方法

定义：

一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

产生死锁的原因：

1. 竞争资源引起进程死锁

(1) 可剥夺和非剥夺性资源

可剥夺资源(处理机,主存)
不可剥夺资源(打印机,磁带机)

(2) 竞争非剥夺性资源

(3) 竞争临时性资源

只可使用一次的资源；如信号量，中断信号，同步信号等（可消耗性资源）

产生死锁的必要条件：

(1) 互斥条件

(2) 请求和保持条件

(3) 不剥夺条件

(4) 环路等待条件

预防和检测死锁的方法:

预防死锁：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或者几个，预防死锁。
避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，避免死锁。
检测死锁：检测死锁的发生，确定与死锁有关的进程与资源，采取措施，从系统中将已发生的死锁清除。
解除死锁：通过撤消和挂起一些进程，回收一些资源，分配给处于阻塞状态的进程，使之转为就绪状态。

3.利用银行家算法避免死锁（与安全性算法的结合)

一、选择题

(1)在三种基本类型的操作系统中，都设置了__C____，在批处理系统中还应设置_B__，在分时系统中除了__C____，通常还设置了__D____。

A.剥夺调度 B.作业调度 C.进程调度 D.中级调度

A. 剥夺调度：这个是描述了进程调度的特性，也适用于分时系统。
B. 作业调度：批处理系统需要将作业从后备作业队列调度到内存中。
C. 进程调度：在所有类型的操作系统中都需要进行进程调度。
D. 中级调度：分时系统通常会实行中级调度，以便适应用户对响应时间的要求。

(2)我们如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用__B____；为照顾紧急作业的用户，应采用___E___；为能实现人机交互作用采用__C____；而能使短作业、长作业及交互作业用户都比较满意时，应采用___D___。

A.FCFS调度算法 B.短作业优先调度算法

C.时间片轮转法 D.多级反馈队列调度算法

E.基于优先权调度算法

(3)产生死锁的基本原因是___B____和___A____，产生死锁的四个必要条件是互斥条件，___C____，不剥夺条件和____B___。

①A.资源分配不当 B.竞争资源

C.作业调度不当 D.资源的独占性

②A.进程推进顺序不当 B.进程调度不当

C.系统中进程太多 D.CPU运行不快

③A.请求和阻塞条件 B.请求和释放条件

C.请求和保持条件 D.释放和阻塞条件

④A.线性增长条件 B.环路等待条件

C.无序释放条件 D.有序请求条件

(4)实际操作系统，要兼顾资源的使用效率和安全可靠，对资源的分配策略，往往采用__D____策略。

A.预防死锁 B.避免死锁 C.检测死锁 D.三者的混合

(5)在下列死锁的解决办法中，属于预防死锁策略的是__B__。

A.银行家算法 B.资源有序分配法

C.死锁检测法 D.资源分配图化简法

B. 资源有序分配法：这是一种预防死锁的策略，因为它遵循先请求一部分，然后再请求更多的原则。
A. 银行家算法：这是一种避免死锁的调度算法。
C. 死锁检测法：属于检测策略。
D. 资源分配图化简法：通常是用于检测和解决死锁。

二、填空题

(1)资源的一次分配法和有序分配法分别破坏了产生死锁的必要条件中的___请求和保持条件

和___环路等待条件，它们属于_预防死锁，而银行家算法属于_避免死锁。

(2)作业调度是从__后备作业队列中选出一_批_作业，为它们分配_资源，并为它们创建__进程。

(3)最有利于提高系统吞吐量的作业调度算法是_短作业优先算法；能对紧急作业进行及时处理的调度算法是__高优先权优先算法；能较好的满足短作业用户要求，又能适当的照顾长作业，以及照顾作业到达次序的调度算法是__高响应比优先算法。

(4)在高响应比优先的调度算法中，当各个作业的等待时间相同时，__短作业将得到优先调度；当各个作业要求的运行时间相同时，__等待时间最长者将得到优先调度。

三、应用题

1.设有三道作业，它们的提交时间和运行时间如下表：

作业号提交时刻(时) 运行时间(小时)

1 10.00 2

2 10.10 1

3 10.25 0.25

求：试给出下面两种调度算法下，作业的执行顺序、平均周转时间和平均带权周转时间。

(1)先来先服务FCFS调度算法

(2)短作业优先SJF调度算法

（2）执行顺序：作业1 → 作业3 → 作业2

作业1：10.00提交，立即开始执行，执行2小时，结束时间为12.00。

作业3和作业2在作业1运行期间到达，分别在10.25和10.10，但需等待作业1完成。

作业1结束后，12.00有两个作业等待：作业2（运行时间1小时）和作业3（运行时间0.25小时）。选择运行时间较短的作业3。

作业3：从12.00开始执行，执行0.25小时，结束时间为12.25。

作业2：作业3结束后，从12.25开始执行，执行1小时，结束时间为13.25。

三、应用题

2.设有四道作业，它们的提交时间和运行时间如下表：

作业号提交时刻(时) 运行时间(小时)

1 8:00 2.0

2 8:50 0.5

3 9:00 0.1

4 9:50 0.2

求：试给出下面三种调度算法下，作业的执行顺序、平均周转时间和平均带权周转时间。

(1)先来先服务FCFS调度算法

(2)短作业优先SJF调度算法

(3)高响应比优先调度算法

总周转时间：120 + 100 + 96 + 58 = 374 分钟

平均周转时间：374 / 4 = 93.5 分钟

总带权周转时间：1 + 3.33 + 16 + 4.83 ≈ 25.16

平均带权周转时间：25.16 / 4 ≈ 6.29

总周转时间：120 + 66 + 28 + 118 = 332 分钟

平均周转时间：332 / 4 = 83 分钟

总带权周转时间：1 + 11 + 2.33 + 3.93 ≈ 18.26

平均带权周转时间：18.26 / 4 ≈ 4.57

总周转时间：120 + 66 + 106 + 58 = 350 分钟

平均周转时间：350 / 4 = 87.5 分钟

总带权周转时间：1 + 11 + 3.53 + 4.83 ≈ 20.36

平均带权周转时间：20.36 / 4 ≈ 5.09

三、应用题(必考)

3.假设某系统中有3种资源(R1,R2,R3)，在某时刻系统中共有4个进程，进程(P1,P2,P3,P4)的最大资源需求数向量和此时已分配的资源数向量分别为：

进程	最大资源需求	当前已分配到资源
P1	(3,2,2)	(1,0,0)
P2	(6,1,3)	(5,1,1)
P3	(3,1,4)	(2,1,1)
P4	(4,2,2)	(0,0,2)

系统中当前可用资源向量为(1,1,2)，问：

(1) 计算还需要资源数组；

(2) 系统此时是否安全？

所有进程都已完成执行，系统为安全状态。

安全序列为：

如果进程P2发出资源请求向量(1,0,1)，系统能否将资源分配给它？

步骤一：验证请求是否合法

① Request2(1, 0, 1)≤Need2(1, 0, 2)

② Request2(1, 0, 1)≤Available2(1, 1, 2

步骤二：尝试分配资源并检查系统的安全性

1. 假设将资源分配给 P2，更新数据：

新的可用资源向量（Available_new）：

Available_new = Available - Request2= (1, 1, 2) - (1, 0, 1)= (0, 1, 1)

进程 P2 的新分配资源（Allocation2_new）：

Allocation2_new = Allocation2 + Request2= (5, 1, 1) + (1, 0, 1)= (6, 1, 2)

进程 P2 的新需要资源（Need2_new）：

Need2_new = Need2 - Request2= (1, 0, 2) - (1, 0, 1)= (0, 0, 1)

④ 再利用安全性算法检查此时系统是否安全。

存在一个安全序列：P2, P3, P4, P1

有进程都已完成执行，系统为安全状态。

(4)如果进程P1发出资源请求向量(1,0,1)，系统能否将资源分配给它？

① Request1(1, 0, 1)≤Need1(2, 2, 2)

② Request1(1, 0, 1)≤Available1(1, 1, 2)

4.假设某系统中有4种资源，在某时刻系统中共有5个进程，进程(P0,P1,P2,P3,P4)的最大资源需求数向量和此时已分配的资源数向量分别为：

系统中当前可用资源向量为(2,1,0,0)，问：

(1) 计算进程还需要请求的资源向量；

(2) 系统当前是处于安全状态么？

(3) 当进程P2申请(0,1,0,0)时，系统能立即满足么？

① Request2(0,1,0,0)≤Need2(6,6,2,2)

② Request2(0,1,0,0)≤Available2(2,1,0,0)

④ 再利用安全性算法检查此时系统是否安全。

存在不安全序列

调度算法（应用题预测）

习题：

假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按照先来先服务（FCFS）、非抢占及抢占的短进程优先(SPF)、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)以及立即抢占的多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

1. 先来先服务（FCFS）

调度顺序： A -> B -> C -> D -> E

进程	到达时间	服务时间	完成时间	周转时间	带权周转时间
A	0	3	3	3	1.0
B	2	6	9	7	1.17
C	4	4	13	9	2.25
D	6	5	18	12	2.4
E	8	2	20	12	6.0

平均周转时间 = (3 + 7 + 9 + 12 + 12) / 5 = 43 / 5 = 8.6
平均带权周转时间 = (1.0 + 1.17 + 2.25 + 2.4 + 6.0) / 5 ≈ 2.564

2. 非抢占短进程优先（SPF）

调度顺序（考虑到 arrival）: A -> B-> E -> C -> D

进程	到达时间	完成时间	周转时间	带权周转时间
A	0	3	3 - 0 = 3	3 / 3 = 1.00
B	2	9	9 - 2 = 7	7 / 6 ≈ 1.17
E	8	11	11 - 8 = 3	3 / 2 = 1.50
C	4	15	15 - 4 = 11	11 / 4 = 2.75
D	6	20	20 - 6 = 14	14 / 5 = 2.80

平均周转时间 =(3 + 7 + 3 + 11 + 14) / 5 = 38 / 5 = 7.6
平均带权周转时间 =(1.00 + 1.17 + 1.50 + 2.75 + 2.80) / 5 = 9.22 / 5 ≈ 1.84

3.抢占式短进程优先（SJF）调度

调度顺序: A -> B-> C->E -> B -> D

进程	到达时间	服务时间	完成时间	周转时间	带权周转时间
A	0	3	3	3	1.00
B	2	6	15	13	2.17
C	4	4	8	4	1.00
D	6	5	20	14	2.80
E	8	2	10	2	1.00

平均周转时间

总周转时间： 3 + 13 + 4 + 14 + 2 = 36
平均周转时间： 36 / 5 = 7.2

平均带权周转时间

总带权周转时间： 1.00 + 2.17 + 1.00 + 2.80 + 1.00 = 7.97
平均带权周转时间： 7.97 / 5 ≈ 1.59

4. 时间片轮转（RR，时间片=1）

调度顺序：

平均周转时间:
- (4 + 16 + 13 + 14 + 7) / 5 = 54 / 5 = 10.8
平均带权周转时间:
- (1.33 + 2.67 + 3.25 + 2.8 + 3.5) / 5 = 13.55 / 5 = 2.71

5. 最高响应比优先算法(HRRN)

调度顺序: A -> B-> C->E -> D

平均周转时间

平均周转时间= 40 / 5 = 8.0

平均带权周转时间

平均带权周转时间 =10.72 / 5 = 2.144

6. 多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)

通过两级队列调度方式模拟计算。

平均周转时间：
- (3 + 15 + 14 + 14 + 6) / 5 = 52 / 5 = 10.4
平均带权周转时间：
- (1.0 + 2.5 + 3.5 + 2.8 + 3.0) / 5 = 12.8 / 5 = 2.56

7.立即抢占的多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)

平均周转时间：
- (4 + 16 + 11 + 14 + 8) / 5 = 53 / 5 = 10.6
平均带权周转时间：
- (1.33 + 2.67 + 2.75 + 2.8 + 4.0) / 5 ≈ 13.55 / 5 = 2.71

1.某系统正在执行三个进程P1、P2和P3，各进程的计算（CPU）时间和I/O时间比例如下表所示。用户工作区系统缓冲区外设905100为提高系统资源利用率，合理的进程优先级设置应为(B)。

A．P1＞P2＞P3 B．P3＞P2＞P1

C．P2＞P1=P3 D．P1＞P2=P3

P3（执行时间短、I/O时间长，最大化利用I/O资源）
P2（计算与I/O时间均衡，可以保证系统资源的合理调度）
P1（计算时间长，未能充分利用I/O资源，影响总体资源有效性）

2.下列调度算法中， (A) 算法不会出现任务“饥饿(starvation)”的情形。
A．时间片轮转算法 B．先来先服务算法
C．可抢占的短作业优先算法 D．静态优先级算法

3.系统采用二级反馈队列系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法，时间片为 10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度 Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2 中的进程；新创建的进程首先进入 Q1；Q1中的进程执行一个时间片后，若未结束，则转入 Q2。若当前 Q1、Q2 为空，系统依次创建进程 P1、P2后即开始进程调度， P1、P2需要的 CPU 时间分别为 30ms 和 20ms，则进程 P1、P2在系统中的平均等待时间为(C)

A. 25ms B. 20ms C. 15ms D. 10ms

4.某进程调度程序采用基于优先数调度策略，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间 cpuTime 和等待时间 waitTime，初值均为 0。进程处于执行态时，cpuTime 定时加 1，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加 1。请回答下列问题。

（1）若调度程序只将 nice 的值作为进程的优先数（小者优先），即 priority=nice，则可能会出现饥饿现象，为什么？

静态优先数仅根据 nice 值确定优先级，可能导致某些低优先级进程长期得不到 CPU 资源，这会使得某些高优先级进程总是优先执行，进而导致低优先级进程一直处于等待状态，产生饥饿现象。

（2）使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。

priority = nice - (cpuTime / k) + (waitTime / m)

其中 k, m 是常数，用于平衡 CPU 时间和等待时间的影响。

当 waitTime 增加时，优先级能够增加，允许长时间等待的进程得到资源。

增加等待时长可提高进程的优先级，避免饥饿现象，使其在资源竞争中不会被低估、长期等待。

5.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的最小值是(C)。
A．2 B．3 C．4 D．5

解析：

6.下列关于银行家算法的叙述中，正确的是(B)。
A．银行家算法可以预防死锁（避免死锁）
B．当系统处于安全状态时，系统中一定无死锁进程
C．当系统处于不安全状态时，系统中一定会出现死锁进程
D．银行家算法破坏了死锁必要条件中的“请求和保持”条件

解析：

银行家算法是避免死锁的方法，并不可以预防死锁，A不正确。并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态;反之，只要系统处于安全状态，系统便可避免进入死锁状态;死锁状态必定是不安全状态，C不正确。破坏“请求和保持”条件是预防死锁的方法，而银行家算法是避免死锁的方法，D不正确。

7.系统中有3个不同的临界资源R1、R2和R3，被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：p1申请R1和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是 C。

1 B. 2 C. 3 D. 4

p1 申请 R1 和 R2；

p2 申请 R2 和 R3；

p3 申请 R1 和 R3；

p4 申请 R2。

解析：

对于本题，先满足一个进程的资源需求，再看其他进程是否能出现死锁状态。因为p4只申请一个资源，当将R2分配给p4后，p4执行完后将R2释放，这时使得系统满足死锁的条件是R1分配给p1，R2分配给p2，R3分配给p3（或者R2分配给p1，R3分配给p2，R1分配给p3）。穷举其他情况如p1申请的资源R1和R2，先都分配给p1，运行完并释放占有的资源后，可以分别将R1、R2和R3分配给p3、p4和p2，也满足系统死锁的条件。各种情况需要使得处于死锁状态的进程数至少为3。(也就是说当先满足一个进程然后再释放出去，这是资源仍然不够进程分配，仍然死锁)

8.若系统 S1 采用死锁避免方法，S2 采用死锁检测方法。下列叙述中，正确的是（B）。

Ⅰ．S1 会限制用户申请资源的顺序，而 S2 不会

Ⅱ．S1 需要进程运行所需资源总量信息，而 S2 不需要

Ⅲ．S1 不会给可能导致死锁的进程分配资源，而 S2 会

仅Ⅰ、Ⅱ B. 仅Ⅱ、Ⅲ C. 仅Ⅰ、Ⅲ D. Ⅰ、Ⅱ、Ⅲ

解析:注意Ⅰ中说的是限制申请资源的顺序，死锁预防才会限制申请顺序，死锁避免影响的是资源分配的顺序

9.下列关于死锁的叙述中，正确的是（B）。

I ．可以通过剥夺进程资源解除死锁

II．死锁的预防方法能确保系统不发生死锁

III．银行家算法可以判断系统是否处于死锁状态（不是判断，是避免了死锁）

IV．当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

A. 仅 II、III B. 仅 I、II、IV C. 仅 I、II、III D. 仅 I、III、IV

设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:

试用信号量与PV操作实现三个工人的合作。
工人1与工人3、工人2与工人3构成生产者与消费者关系，他们通过共同的缓冲区（箱子）相联系。
从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，车架和车轮相当于工人3的资源。
从使用资源的角度考虑，设三个信号量：
- Semaphore empty=N; //空位置
- Semaphore wheel=0; //车轮
- Semaphore frame=0; //车架

三个工人的活动分别为：

考虑：是否在某种状态有死锁发生？

箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制用信号量来表示：
- Semaphore s1=N-2;
- Semaphore s2=N-1;

三个工人的活动分别为：

第四章

1.地址映射、静态和动态重定位

2.内外部碎片、紧凑、对换、各分配算法的基本思路和特点

3.基本分页的地址转换（注意快表）

4.虚拟存储器的定义和特征、请求分页的地址转换（注意地址变换机构）、常用置换算法的原理和特点。

1.某系统某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210B，页表项大小为2B，逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是(B)。

A．64 B．128 C．256 D．512

解析：

页表项的计算：
- 页大小为 1024 字节，即每个页有 1024 个可用地址。
- 每个页表项为 2 字节，其所负责的页面数计为 1024/2 = 512 条。
计算页目录表的大小：
- 总共有 2^{16} 个逻辑页。
- 每个二级页表（即每个单独的页表）能管理 512 个页面。
页目录表（第一层页表）的计算：
- 页目录表需要能访问所有 2^{16} 逻辑页。
- 若每个页表负责管理 512 个页，则需要多少个页表？
- 总的页面数 65536（因为 2^{16} = 65536），被每个页表管理的页面数 512划分：
  - 页目录表的项数 = 65536/ 512 = 128

2.下列选项中，属于多级页表优点的是（D）
A．加快地址变换速度 B 减少缺页中断次数

C ．减少页表项所占字节 D．减少页表所占的连续内存空间

解析：多级页表避免了把所有的页表一直保存在内存中

3.某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：

虚拟地址 2050 1225H 对应的页目录号、页号分别是（A）
A．081H、101H B．081H、401H

C．201H、101H D．201H、401H

【解析】虚拟地址20501225H为十六进制，转换为二进制为00100000010100000001001000100101。那么页目录号(前10位)、页号(11~20位)分别为0010000001、0100000001，转换为十六进制分别为081H、101H，故本题选A。

1.在缺页处理过程中，操作系统执行的操作可能是(D)
Ⅰ．修改页表 Ⅱ．磁盘I/O Ⅲ．分配页框

A．仅Ⅰ，Ⅱ B．仅Ⅱ C．仅Ⅲ D．Ⅰ，Ⅱ和Ⅲ

解析：缺页中断调入新页面，肯定要修改页表项和分配页框，所以I、Ⅲ可能发生，同时内存没有页面，需要从外存读入，会发生磁盘I／O。

2.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（B）

Ⅰ．处理越界错 Ⅱ．置换页 Ⅲ．分配内存
A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅲ D．Ⅰ、Ⅱ和Ⅲ

分析：

用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统会执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。

1. 常用的内存管理方法有 分区管理、分段管理、分页管理和段页式管理 。

2. 动态存储分配时，要靠硬件地址变换机构实现 重定位 。

3. 在存储管理中常用 虚拟存储器 方式来摆脱主存容量的限制。

4. 在页式管理中，页式虚地址与内存物理地址的映射是由页表和 硬件地址变换机构 完成的。

5. 在请求页式管理中，当 硬件变换机构 发现所需的页不在内存时，产生中断信号， 缺页中断机构 作相应的处理。

6. 置换算法是在内存中没有 空闲物理块 时被调用的，它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲物理块存放所调入的页，则不必使用 置换算法 。

7. 在页式管理中，页表的作用是实现从页号到 物理块号 的地址映射，存储页表的作用是 记录内存页面分配情况 。

8. 段式管理中，以段为单位 分配内存 ，每段分配一个 连续的 内存区。由于各段长度不等，所以这些存储区的大小不一，而且同一进程的各段间不要求连续。

9. 在段页式存储管理系统中，面向用户的地址空间是段式划分，面向 物理存储 的地址空间是页式划分。

10. 在存储器管理中，页面是信息的物理单位，分段是信息的逻辑单位。页面大小由系统确定，分段大小由用户确定。

11. 在请求页式存储管理中，若所需页面不在内存中，则会引起（D）。

A. 输入输出中断 B. 时钟中断

C. 越界中断 D. 缺页中断

解析：缺页中断：当所需页面不在内存中时，触发的中断，用于加载页面到内存。

12. 若处理器有32位地址，则它的虚拟地址空间为（B）字节。

A. 2GB B. 4GB C. 100KB D. 640KB

解析:处理器的虚拟地址空间取决于地址的位数。具体来说，虚拟地址空间的大小可以通过以下公式计算：

虚拟地址空间 = 2 的地址位数次方字节

对于32位地址：

2的32次方等于4,294,967,296字节，也就是4 GB。

13. 虚拟存储技术是（B）。

A. 补充内存物理空间的技术 B. 补充相对地址空间的技术

C. 扩充外存空间的技术 D. 扩充输入输出缓冲区的技术

14. 虚拟内存的容量只受（A）的限制。

A. 物理内存的大小 B. 磁盘空间的大小

C. 数据存放的实际地址 D. 计算机地址位数

解析：

虚拟内存的容量受物理内存大小的限制。设置虚拟内存时，一般以物理内存的1.5~3倍容量设置为好，太大也不会有太多的帮助反而会增加硬盘的工作量。

15.（B）是指将作业不需要或暂时不需要的部分移到外存，让出内存空间以调入其他所需数据。

A. 覆盖技术 B. 交换技术

C. 虚拟技术 D. 物理扩充

16. 分区管理要求对每一个作业都分配（A）的内存单元。

A. 地址连续 B. 若干地址不连续

C. 若干连续的帧 D. 若干不连续的帧

解析：分区存储管理是把主存储器中的用户作为一个连续区或者分成若干个连续区进行管理，每个连续区中可装入一个作业。

17.（C）存储管理支持多道程序设计，算法简单，但存储碎片多。

A. 段式 B. 页式

C. 固定分区 D. 段页式

解析：固定分区

优点：算法简单，内存划分为固定大小的多个分区，便于管理。
缺点：由于分区大小固定，容易造成内部碎片和外部碎片。当作业大小不匹配分区大小时，会导致大量碎片。

最容易产生内存碎片的动态分区分配算法是哪一种？

最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用的内存块，即最佳适应算法最容易产生最多的内部碎片。

18.（C）存储管理方式提供一维地址结构。

A. 固定分区 B. 分段 C. 分页 D. 分段和段页式

19. 分段管理提供（B）维的地址结构。

A. 1 B. 2 C. 3 D. 4

解析：分段管理：提供二维地址结构，通常由段号和段内偏移量组成。因此，分段管理提供的是二维的地址结构。

20. 以下存储管理技术中，支持虚拟存储器的技术是（C）。

A. 动态分区法 B. 可重定位分区法 C. 请求分页技术 D. 对换技术

21. 请求分页存储管理中，若把页面尺寸增加一倍，在程序顺序执行时，则一般缺页中断次数会（B）。

A．增加 B．减少 C．不变 D．可能增加也可能减少

解析：

增大页面尺寸意味着每个页面能够覆盖更多的连续地址。在程序顺序执行时，访问的地址跨度较小，较大的页面尺寸可以减少需要加载的页面数量，从而减少缺页中断次数。

22. 采用（B）存储管理方案，系统不可能产生抖动现象。

A. 请求页式 B. 固定式分区 C. 请求段式

解析：

抖动现象：通常发生在分页或分段系统中，当系统过度交换页面或段时，导致大量时间用于内存交换，影响系统性能。
固定式分区：由于内存被分为固定大小的分区，系统不依赖于动态分页或分段，因此不会产生抖动现象。
请求页式和请求段式：都可能因内存不足或频繁交换而导致抖动。

23. 在可变式分区分配方案中，某一作业完成后系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲数减1的情况是（D）。

A.无上邻空闲区，也无下邻空闲区 B.有上邻空闲区，但无下邻空闲区

C.有下邻空闲区，但无上邻空闲区 D.有上邻空闲区，也有下邻空闲区

1. 在分页系统中地址结构长度为16位,页面大小为2K,作业地址空间为6K,该作业的各页依次存放在2、3、6号物理块中，相对地址2500处有一条指令store 1,4500，请给出该作业的页表和该指令的物理单元以及数据存放的物理单元。

解析：

步骤分析

1. 计算页数

页面大小：2K = 2048 字节。
作业地址空间：6K = 6144 字节。
页数 = 作业地址空间 / 页面大小 = 6144 / 2048 = 3页（页编号0、1、2）。

2. 构建页表

页表用于将逻辑页号（虚拟页号）映射到物理帧号。根据已知条件，页表如下：

页号 (Page Number)	页框号 (Frame Number)
0	2
1	3
2	6

3. 转换虚拟地址到物理地址

虚拟地址组成：页号 + 页内偏移

页号位数 = log₂(页面大小) = log₂(2048) = 11 位。
页内偏移位数 = 总地址位数 - 页号位数 = 16 - 11 = 5 位。

但实际上，由于页大小为2048字节，页内偏移需要11位。因此，虚拟地址的组成应为：

页号：前5位（因为3页只需要2位，但为保持整体一致性，可采用更多位）。
页内偏移：后11位。

4. 计算物理地址

a. 指令地址 2500

虚拟地址：2500。
页号 = floor(2500 / 2048) = 1。
页内偏移 = 2500 % 2048 = 452。
页号1 对应 页框号3。
物理地址 = 页框号 * 页大小 + 页内偏移 = 3 * 2048 + 452 = 6144 + 452 = 6596。

b. 数据地址 4500

虚拟地址：4500。
页号 = floor(4500 / 2048) = 2。
页内偏移 = 4500 % 2048 = 404。
页号2 对应 页框号6。
物理地址 = 页框号 * 页大小 + 页内偏移 = 6 * 2048 + 404 = 12288 + 404 = 12692。

总结答案

页表：

页号 (Page Number)	页框号 (Frame Number)
0	2
1	3
2	6

指令 store 1,4500 的物理地址：
- 指令地址：虚拟地址2500 → 物理地址6596。
数据存放的物理地址：
- 数据地址：虚拟地址4500 → 物理地址12692。

2. 设一段表如图所示那么，逻辑地址（2，88）对应的物理地址是多少？逻辑地址（4，100）所对应的物理地址是多少？

解析：

逻辑地址 (2, 88)
- 段号 = 2，段内偏移 = 88
- 从段表中查找段号 2：
  - 基地址 = 90
  - 段长 = 100

计算物理地址：

- 物理地址 = 基地址 + 段内偏移 = 90 + 88 = 178
逻辑地址 (4, 100)
- 段号 = 4，段内偏移 = 100
- 从段表中查找段号 4：
  - 基地址 = 1952
  - 段长 = 96

计算物理地址：

- 因为段内偏移 100 超出了段长 96，因此这是一个越界访问，实际物理地址计算会无效。

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

（1）12KB （2）10KB （3）15KB

（4）18KB （5）12KB

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

4. 某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为128K，页的大小是4K。假定某进程的大小为32页，请回答如下问题：

（1）写出逻辑地址的格式。

（2）如果不考虑权限位，该进程的页表有多少项？每项至少多少位？

解析：

（1）逻辑地址的格式

在页式管理系统中，逻辑地址（虚拟地址）由两个部分组成：页号和页内偏移。

定义逻辑地址格式：

页大小：4K（即4096字节），
物理地址空间：128K（即131072字节），
页的数量 = 128K / 4K = 32页。

页内偏移：

由于每页的大小为4K：

页内偏移的位数 = log₂(页大小) = log₂(4096) = 12位。因此，页内偏移占用12位。

页号：

由于一个进程的大小为32页：

页号的位数 = log₂(页数) = log₂(32) = 5位。因此，页号占用5位。

最终逻辑地址格式：

逻辑地址的格式应为：

页号（5位） + 页内偏移（12位）

因此，逻辑地址的完整格式为：

逻辑地址格式：5位页号 + 12位页内偏移。

（2）该进程的页表项数和每项的位数

页表项数：

每个进程的页表项数等于该进程的页数。

该进程的大小为32页，因此页表有32项。

每项至少多少位：

页表中每项主要用于存储映射关系，通常包含物理页框号和一些控制位（如有效位、修改位、访问位等）。我们此处只讨论物理页框号的位数。

物理地址空间：128K，意味着物理地址可以通过以下方式计算：
- 物理地址大小 = log₂(128K) = log₂(131072) = 17位。
物理页框号：
- 由于页大小为4K，所以物理内存需要分为页框：
- 物理页框数 = 128K / 4K = 32个物理页框。
- 物理页框的位数 = log₂(物理页框数) = log₂(32) = 5位。
控制位：
- 除了物理页框号外，如果不考虑权限位和其他控制位，每项至少为5位，但通常在设计中需要包含状态控制位。为了简化计算，此处假设其他控制位不做具体确定。

因此，每项至少 5 位（指示物理页框号），但是根据操作系统的实际设计，可能会需要更多位数来处理权限、有效性等信息。

5. 假设一个分页存储管理系统具有快表，多数活动页表项都可以存在其中。如果页表放在内存中，内存访问时间是1μs, 若快表的命中率是85%（快表检索时间忽略不计），则有效存取时间为多少？若快表的命中率为50%，那么有效存取时间为多少？

解析：

有效存取时间的计算

有效存取时间（Effective Access Time, EAT）可以用以下公式计算：

EAT = (H * (T_m + T_t)) + ((1 - H) * (T_m + T_p))

其中：

EAT：有效存取时间
H：快表的命中率
T_m：内存访问时间
T_t：快表检索时间（通常可忽略）
T_p：页表在内存中的访问时间

给定条件

内存访问时间 (T_m) = 1微秒（μs）
快表检索时间 (T_t) 可忽略，默认为0。
页表在内存中的访问时间 (T_p) = 1微秒（μs）

1. 快表命中率为85%（H = 0.85）

有效存取时间计算

首先计算命中时和未命中的时间：

命中：有效存取时间 = H * (内存访问时间 + 快表检索时间)
未命中：有效存取时间 = (1 - H) * (内存访问时间 + 页表访问时间)

具体计算为：

EAT = (0.85 * (1 + 0)) + (0.15 * (1 + 1))

计算结果：

EAT = (0.85 * 1) + (0.15 * 2)
EAT = 0.85 + 0.30 = 1.15微秒（μs）

2. 快表命中率为50%（H = 0.50）

有效存取时间计算

类似于上面的步骤，计算有命中和未命中的情况：

EAT = (0.50 * (1 + 0)) + (0.50 * (1 + 1))

计算结果：

EAT = (0.50 * 1) + (0.50 * 2)
EAT = 0.50 + 1.00 = 1.50微秒（μs）

6. 某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。

解析：

虚拟地址 0A5C

计算页号：

- 0A5C (十六进制) = 0 * 4096 + 10 * 256 + 5 * 16 + 12 = 2668 (十进制)
- 虚拟页号（0A5C / 1024）= 2（页号）

计算页内偏移：

- 页内偏移（0A5C % 1024）= 0A5C % 0400 = 0A5C - 2 * 0400 = 0A5C - 0800 = 025C (十六进制) = 604 (十进制)

对应物理块号为：

- 第2页 -> 物理块号4

物理地址计算：

- 物理地址 = 物理块号 * 每页大小 + 页内偏移
- 物理地址 = 4 * 1024 + 604 = 4096 + 604 = 4700 (十进制) => 0x0124C (十六进制)
虚拟地址 103C

计算页号：

- 103C (十六进制) = 1 * 4096 + 0 * 256 + 3 * 16 + 12 = 4156 (十进制)
- 虚拟页号（103C / 1024）= 4（页号）

计算页内偏移：

- 页内偏移（103C % 1024）= 103C & 03FF = 103C - 4 * 0400 = 103C - 1000 = 03C (十六进制) = 60 (十进制)

对应物理块号为：

- 第4页 -> 物理块号4

物理地址计算：

- 物理地址 = 物理块号 * 每页大小 + 页内偏移
- 物理地址 = 10 * 1024 + 60 = 10240 + 60 = 10300 (十进制) => 0x0284C (十六进制)
虚拟地址 1A5C

计算页号：

- 1A5C (十六进制) = 1 * 4096 + 10 * 256 + 5 * 16 + 12 = 6828 (十进制)
- 虚拟页号（1A5C / 1024）= 6（页号）

计算页内偏移：

- 页内偏移（1A5C % 1024）= 1A5C & 03FF = 1A5C - 6 * 0400 = 1A5C - 2400 = 03C (十六进制) = 60 (十进制)

对应物理块号为：

- 第6页没有物理块号分配（题中只给出了第0、1、2、3页），这是无效的地址。

该虚拟地址无效。

7. 一个进程已分配到4个页，如表所示：当进程访问第4页时，产生缺页中断。请分别用FIFO、LRU、改进的CLOCK算法决定换出页面。

解析：

1. FIFO（先进先出）

在FIFO算法中，最早进入内存的页面将被替换。

当前页面状态

页面：0, 1, 2, 3
次序（装入时间）：60（页0）< 130（页1）< 26（页2）< 20（页3）

根据FIFO，最早装入的页是页号 0（装入时间为26），因此将替换出页0。

被替换的页面：页0

2. LRU（最近最少使用）

在LRU算法中，最近最少使用的页面将被替换。

最近访问时间

页2 最近访问时间为161
页1 最近访问时间为160
页0 最近访问时间为162
页3 最近访问时间为163

根据LRU，页1 是最近最少使用的（最近访问时间为160），因此将替换出页1。

被替换的页面：页1

3. 改进的CLOCK算法

改进的CLOCK算法将页面视作一个环形队列，并使用访问位来决定是否替换。访问位为0的页面会被替换。

当前页面状态

页2访问位：0
页1访问位：0
页0访问位：1
页3访问位：1

在改进的CLOCK算法中，我们从最先访问的页面开始检查：

页2 访问位为0：可以被替换。
页1 访问位为0：可以被替换。
页0 访问位为1：不替换，重置为0进行下一个检查。
页3 访问位为1：不替换，重置为0，继续。

因此，页 2 或 1 可以被替换，根据算法选择页 2 ，因为它是第一个可替换的。

被替换的页面：页2

8. 在一个请求分页系统中，加入一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前还未被装入内存，当分配给该作业的物理块数M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页次数和缺页率，并比较所得结果。

解析：

页面访问序列为：4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5。

总缺页次数和缺页率计算

缺页率公式为：

缺页率 = 缺页次数 / 总访问页面次数。

总访问页面次数为 12。

1. 当物理块数 M = 3 时

a. OPT 算法（最佳页面替换）

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，使用 4 替换（因为它在后面时间最长），载入 [3, 2, 1]。
访问页面 4：缺页，使用 3 替换，载入 [2, 1, 4]。
访问页面 3：缺页，使用 2 替换，载入 [1, 4, 3]。
访问页面 5：缺页，使用 1 替换，载入 [4, 3, 5]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 2：缺页，使用 4 替换，载入 [3, 5, 2]。
访问页面 1：缺页，使用 3 替换，载入 [5, 2, 1]。
访问页面 5：命中。

缺页次数（OPT）： 8

缺页率（OPT）： 8 / 12 = 67%。

b. LRU 算法（最近最少使用）

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，使用 4 替换，载入 [3, 2, 1]。
访问页面 4：缺页，使用 3 替换，载入 [2, 1, 4]。
访问页面 3：缺页，使用 2 替换，载入 [1, 4, 3]。
访问页面 5：缺页，使用 1 替换，载入 [4, 3, 5]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 2：缺页，使用 4 替换，载入 [3, 5, 2]。
访问页面 1：缺页，使用 3 替换，载入 [5, 2, 1]。
访问页面 5：命中。

缺页次数（LRU）： 8

缺页率（LRU）： 8 / 12 = 67%。

c. FIFO 算法（先进先出）

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，使用最早的 4 替换，载入 [3, 2, 1]。
访问页面 4：缺页，使用最早的 3 替换，载入 [2, 1, 4]。
访问页面 3：缺页，使用最早的 2 替换，载入 [1, 4, 3]。
访问页面 5：缺页，使用最早的 1 替换，载入 [4, 3, 5]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 2：缺页，使用最早的 4 替换，载入 [3, 5, 2]。
访问页面 1：缺页，使用最早的 3 替换，载入 [5, 2, 1]。
访问页面 5：命中。

缺页次数（FIFO）： 8

缺页率（FIFO）： 8 / 12 = 67%。

2. 当物理块数 M = 4 时

a. OPT 算法

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，载入 [4, 3, 2, 1]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 5：缺页，替换 2，载入 [4, 3, 1, 5]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 2：缺页，替换 1，载入 [4, 3, 5, 2]。
访问页面 1：缺页，替换 4，载入 [3, 5, 2, 1]。
访问页面 5：命中。

缺页次数（OPT）： 6

缺页率（OPT）： 6 / 12 = 50%。

b. LRU 算法

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，载入 [4, 3, 2, 1]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 5：缺页，替换 2，载入 [4, 3, 1, 5]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 2：缺页，替换 1，载入 [4, 3, 5, 2]。
访问页面 1：缺页，替换 4，载入 [3, 5, 2, 1]。
访问页面 5：命中。

缺页次数（LRU）： 6

缺页率（LRU）： 6 / 12 = 50%。

c. FIFO 算法

访问页面 4：缺页，载入 [4]。
访问页面 3：缺页，载入 [4, 3]。
访问页面 2：缺页，载入 [4, 3, 2]。
访问页面 1：缺页，载入 [4, 3, 2, 1]。
访问页面 4：命中。
访问页面 3：命中。
访问页面 5：缺页，替换 4，载入 [3, 2, 1, 5]。
访问页面 4：缺页，替换 3，载入 [2, 1, 5, 4]。
访问页面 3：缺页，替换 2，载入 [1, 5, 4, 3]。
访问页面 2：缺页，替换 1，载入 [5, 4, 3, 2]。
访问页面 1：缺页，替换 5，载入 [4, 3, 2, 1]。
访问页面 5：缺页，替换 4，载入 [3, 2, 1, 5]。

缺页次数（FIFO）： 9

缺页率（FIFO）： 9 / 12 = 75%。

总结

物理块数 M	算法	缺页次数	缺页率
3	OPT	8	67%
3	LRU	8	67%
3	FIFO	8	67%
4	OPT	6	50%
4	LRU	6	50%
4	FIFO	9	75%

讨论

物理块数为 3 时，三种算法的缺页率相同。
物理块数为 4 时，OPT 和 LRU 算法表现较好，缺页率明显降低，而 FIFO 算法的缺页率相对较高。
OPT 算法通常效果最好，因为它能够预测未来的页面需求，而 LRU 算法在大多数案例中也表现良好。

9. 某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序应用内存单元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制数，而内存中尚未装入任何页。

(1) 给出使用LRU算法时的缺页次数，并与FIFO时的情况进行比较。

(2) 画出相应地址变化过程的流程图。

10. 在在某个请求分页管理系统中，假设某进程的页表内容如下表所示。

页号	页框号	存在位
0	101H	1
1	-	0
2	254H	1

页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时问是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H，1565H，25A5H，请问：
(1)依次访问上述三个虚地址，各需多少时间给出计算过程。
(2)基于上述访问序列，虚地址1565H的物理地址是多少请说明理由。

第五章

1.缓冲管理的引用及实现方式（尤其是单缓冲和双缓冲）

5.3.1 缓冲的引入

缓和CPU与I/O设备间速度不匹配的矛盾。

(2) 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。

(3) 提高CPU和I/O设备之间的并行性。

I/O缓冲区设置

(1) 缓冲区实现
1. 硬缓冲：

在设备中(硬件寄存器)设置缓冲区，由硬件实现。

1. 软缓冲：

在内存中开辟一个空间，用作缓冲区。

(2) 缓冲区管理
1. 简单缓冲：单缓冲和双缓冲
2. 多缓冲：循环缓冲和缓冲池

5.3.2 单缓冲和双缓冲

1. 单缓冲(Single Buffer)

I/O共用一个缓冲区。只有该缓冲为空时，才可往里放入。

每当一个用户进程发出一I/O请求时，OS在主存中为之分配一缓冲区。从磁盘把一块数据输入到缓冲区（T）；OS将缓冲区数据传送到用户区（M）；CPU计算（C）对于含有多块的大批数据，往缓冲区输入和计算可以是并行的，所以一块数据的处理时间为MAX(T,C)+M。

若没有缓冲，则约为T+C

当输入一行数据时，进程挂起以等待一行结束；输出时，用户进程将一行数据送入缓冲区后继续计算。当有第二行输出时，若第一行尚未取完，则进程阻塞。

2. 双缓冲(Double Buffer)

(1) 两个缓冲区。当CPU计算某缓冲区中的数据时，可对另一缓冲区进行输入。两个缓冲区也可根据需要一个用于输入、一个用于输出。适合于输入、输出速度基本匹配时。

(2) 一块数据的处理时间约为MAX(T,C+M)。

(3) 两台机器的通信，设置单缓冲，任意时刻只能实现单向数据传送。为实现双向，需为每台机器设置双缓冲。

2.虚拟设备的基本概念、设备驱动程序的功能和特点

虚拟设备：经虚拟技术将一台独占设备变换为若干台逻辑设备，共若干个用户（进程）同时使用，把这种经过虚拟技术处理过的设备称为虚拟设备。

5.5.1 设备驱动程序的功能和特点

设备处理程序又称为设备驱动程序,是I/O进程与设备控制器之间的通信程序。

主要任务是接收上层软件发来的抽象要求，转换成具体要求后，发送给设备控制器，启动设备执行。另外，还要将设备控制器发来的信号传送给上层软件。

设备驱动程序的功能

(1) 将接受到的抽象要求转换为具体要求。

(2) 检查用户I/O请求的合法性，了解I/O设备的状态、传递参数，设置设备的工作方式。

(3) 发出I/O命令，启动分配到的I/O设备，完成指定的I/O操作。

(4) 及时响应控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进程处理。

(5) 若有通道，自动构成通道程序。

2. 设备驱动程序的特点

(1) 是在请求I/O的进程与设备控制器之间的一个通信程序。

(2) 不同类型的设备应配备不同的驱动程序。

(3) 与I/O控制方式紧密相关。

(4) 和硬件紧密相关，部分由汇编语言编写；部分可能固化在ROM中。

(5) 驱动程序可以动态安装或加载

(6) 不允许驱动程序使用系统调用

1.在本地用户通过键盘登陆系统时，首先获得键盘输入信息的程序是(B)
A．命令解释程序 B．中断处理程序

C．系统调用服务程序 D．用户登录程序

解释： 当用户通过键盘输入信息时，键盘设备会首先发出中断信号给CPU，调用中断处理程序来处理输入。

2.系统将数据从磁盘读到内存的过程包括以下操作：

①DMA控制器发出中断请求

②初始化DMA控制器并启动磁盘

③从磁盘传输一块数据到内存缓冲区

④执行“DMA结束”中断服务程序

正确的执行顺序是（B）
A． ③->①->②->④ B． ②->③->①->④

C． ②->①->③->④ D． ①->②->④->③

解释： 首先初始化DMA控制器并启动磁盘（②），然后从磁盘传输数据到内存缓冲区（③），接下来DMA控制器发出中断请求（①），最后执行“DMA结束”中断服务程序（④）。

3.用户程序发出磁盘I/O请求后，系统的正确处理流程是(B)
A. 用户程序→系统调用处理程序→中断处理程序→设备驱动程序

B. 用户程序→系统调用处理程序→设备驱动程序→中断处理程序

C. 用户程序→设备驱动程序→系统调用处理程序→中断处理程序

D. 用户程序→设备驱动程序→中断处理程序→系统调用处理程序

解析：输入/输出软件一般从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。与设备无关的软件层也就是系统调用的处理程序。当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的内核接到该调用请求后请求调用处理程序进行处理，再转到相应的设备驱动程序，当设备准备好或所需数据到达后设备硬件发出中断，将数据按上述调用顺序逆向回传到用户程序中。

4.用户程序发出磁盘I/O请求后，系统的处理流程是：用户程序→系统调用处理程序→设备驱动程序→中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是(C )
A．用户程序 B．系统调用处理程序
C．设备驱动程序 D．中断处理程序

解释： 设备驱动程序负责与硬件设备直接交互，包含具体的计算和控制逻辑，例如确定要访问的数据在磁盘上的位置（柱面号、磁头号、扇区号）。

5.操作系统的I/O子系统通常由4个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是(A)

A．用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序
B．用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序
C．用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序
D．用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序

6. 程序员利用系统调用打开I/O设备时，通常使用的设备标识是(A )
A．逻辑设备名 B．物理设备名
C．主设备号 D．从设备号

解释： 逻辑设备名是程序员在编写代码时使用的，系统通过逻辑设备名来识别和访问特定的设备。

7.下列选项中，不能改善磁盘设备I/O性能的是B
A．重排I/O请求次序
B．在一个磁盘上设置多个分区
C．预读和滞后写
D．优化文件物理块的分布

解释： 设置多个分区主要是为了组织数据，反而可能导致寻道时间和I/O性能的下降，并不能直接改善磁盘I/O性能。

8.某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100 μs ，将缓冲区的数据传送到用户区的时间是50 μs ，CPU对一块数据进行分析的时间为50 μs 。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（B）

A．1500μs，1000μs B．1550μs，1100μs

C．1550μs，1550μs D．2000μs，2000μs

解析：在单缓冲区中，当上一个磁盘块从缓冲区读入用户区完成时，下一磁盘块才能开始读入也就是当最后一块磁盘块读入用户区完毕时所用时间为150×10=1500μs,加上处理最后一个磁盘块的时间50μs,得1550μS。

双缓冲区中，不存在等待磁盘块从缓冲区读入用户区的问题，10个磁盘块可以连续从外存读入主存缓冲区，加上将最后一个磁盘块从缓冲区送到用户区的传输时间50μs以及处理时间50μs,也就是100×10+50+50=1100μS。

单缓冲区总时间=(磁盘写入缓冲区时间+缓冲区读出时间)*磁盘块数+CPU处理最后一块数据的时间=(100+50)*10+50=1550us

双缓冲总时间=磁盘写入缓冲区时间*磁盘块数+读出最后一块数据时间+CPU分析最后一块数据时间=100*10+50+50=1100us

9. 下列关于SPOOLing技术的叙述中，错误的是（D）

A．需要外存的支持

B．需要多道程序技术的支持

C．可以让多个作业共享一台独占式设备

D．由用户作业控制设备与输入输出井之间的数据传送

解释： SPOOLing技术是操作系统管理的，由系统控制数据传送，不由用户作业直接控制。

10.在系统内存中设置磁盘缓冲区的主要目的是(A )

A．减少磁盘 I/O 次数

B．减少平均寻道时间

C．提高磁盘数据可靠性

D．实现设备无关性

解释： 磁盘缓冲区的设置可以有效减少磁盘的I/O次数，从而提升系统的整体性能。

1. 假定把磁盘上一个数据块中的信息输入到一单缓冲区的时间T为100µs，将缓冲区中数据传送到用户区的时间M为50µs，而CPU对该数据的计算时间C为50µs，系统对每一块数据的处理时间是多少？如把单缓冲改为双缓冲，则处理时间为多少？

1. 单缓冲处理时间

在单缓冲结构下，处理时间的确应当如您所述，考虑在数据块从磁盘读取到缓冲区、传送到用户区以及 CPU 对数据进行处理的时间关系。

T = 读取数据块到缓冲区的时间 = 100µs
M = 将缓冲区中的数据传送到用户区的时间 = 50µs
C = CPU 对数据进行计算的时间 = 50µs

对于单缓冲，处理时间确实为：

处理时间 = MAX(T, C) + M

具体计算如下：

MAX(T, C) = MAX(100µs, 50µs) = 100µs
处理时间 = 100µs + 50µs = 150µs

2. 双缓冲处理时间

在双缓冲结构下，理论上可以并行进行读和计算操作。所以，处理时间的计算应更为复杂。

通常情况下，处理时间可以表示为：

处理时间 = MAX(T, C + M)

这是因为 CPU 可以在读取数据的同时进行处理（计算），并在数据读取完成后，立马进行 M 的操作。

计算如下：

处理时间 = MAX(100µs, 50µs + 50µs)
50µs + 50µs = 100µs
MAX(100µs, 100µs) = 100µs

2. 假定磁盘转速为20ms/r，每个磁道被划分为10个扇区。现有10条记录存放在同一磁道上（一条记录正好与一个扇区的大小相等），处理程序从磁盘读出一条记录后需要4ms进行相关处理，现要求按从1到10的顺序处理这10条记录。若磁头处于首条记录的起点位置，则：

(1) 按逆时针方向依次存放这10条记录（磁盘顺时针方向旋转），处理程序读取这10条记录需要多长时间？

(2) 按最优化分布重新安排这10条记录，写出记录的逆时针存放顺序，并计算处理这10条记录需要的时间。

解析：

3. 假设磁盘有200个磁道，磁盘请求序列为55、58、39、18、90、160、150、38、184号，当前磁头在100号磁道上，并向磁道号增加的方向上移动。请给出按FCFS、SSTF、SCAN及CSCAN算法进行磁盘调度时满足请求的序列，并计算出它们的平均寻道长度。

解析：

1. 先来先服务 FCFS

访问顺序: 55 -> 58 -> 39 -> 18 -> 90 -> 160 -> 150 -> 38 -> 184

磁头移动距离:

从 100 移动到 55：|100 - 55| = 45
从 55 移动到 58：|55 - 58| = 3
从 58 移动到 39：|58 - 39| = 19
从 39 移动到 18：|39 - 18| = 21
从 18 移动到 90：|18 - 90| = 72
从 90 移动到 160：|90 - 160| = 70
从 160 移动到 150：|160 - 150| = 10
从 150 移动到 38：|150 - 38| = 112
从 38 移动到 184：|38 - 184| = 146

总移动距离:
45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498

请求的数量:
9

平均寻道时间:
总移动距离 / 请求的数量 = 498 / 9 ≈ 55.3

2. 最短寻道时间优先 SSTF

磁头访问顺序:
从 100 开始，依次选择离当前磁头位置最近的请求。

当前在 100，离 90 最近。
从 90 移动到：|100 - 90| = 10
现在在 90，离 58 最近。
从 90 移动到：|90 - 58| = 32
现在在 58，离 55 最近。
从 58 移动到：|58 - 55| = 3
现在在 55，离 39 最近。
从 55 移动到：|55 - 39| = 16
现在在 39，离 38 最近。
从 39 移动到：|39 - 38| = 1
现在在 38，离 18 最近。
从 38 移动到：|38 - 18| = 20
现在在 18，离 150 最近。
从 18 移动到：|18 - 150| = 132
现在在 150，离 160 最近。
从 150 移动到：|150 - 160| = 10
现在在 160，离 184 最近。
从 160 移动到：|160 - 184| = 24

总移动距离:
10 + 32 + 3 + 16 + 1 + 20 + 132 + 10 + 24 = 248

请求的数量:
9

平均寻道时间:
总移动距离 / 请求的数量 = 248 / 9 ≈ 27.6

3. 扫描算法 SCAN

磁头访问顺序:
从 100 开始，向外移动到最大请求，之后再反向服务。

从 100 移动到 150：|100 - 150| = 50
从 150 移动到 160：|150 - 160| = 10
从 160 移动到 184：|160 - 184| = 24
从 184 反向来到 90：|184 - 90| = 94
从 90 移动到 58：|90 - 58| = 32
从 58 移动到 55：|58 - 55| = 3
从 55 移动到 39：|55 - 39| = 16
从 39 移动到 38：|39 - 38| = 1
从 38 移动到 18：|38 - 18| = 20

总移动距离:
50 + 10 + 24 + 94 + 32 + 3 + 16 + 1 + 20 = 250

请求的数量:
9

平均寻道时间:
总移动距离 / 请求的数量 = 250 / 9 ≈ 27.8

4. 循环扫描算法 CSCAN

磁头访问顺序:
从 100 增加到最大，再循环到最小请求。

从 100 移动到 150：|100 - 150| = 50
从 150 移动到 160：|150 - 160| = 10
从 160 移动到 184：|160 - 184| = 24
从 184 循环回到 0：|184 - 0| = 184
从 0 移动到 18：|0 - 18| = 18
从 18 移动到 38：|18 - 38| = 20
从 38 移动到 39：|38 - 39| = 1
从 39 移动到 55：|39 - 55| = 16
从 55 移动到 58：|55 - 58| = 3
从 58 移动到 90：|58 - 90| = 32

总移动距离:
50 + 10 + 24 + 184 + 18 + 20 + 1 + 16 + 3 + 32 = 328

请求的数量:
9

平均寻道时间:
总移动距离 / 请求的数量 = 328 / 9 ≈ 36.4

第六章

1.文件逻辑结构的基本概念

文件逻辑结构的类型

有结构文件(记录式文件)

(1) 定长记录。

(2) 变长记录。

记录式文件的逻辑组织又可以进一步分为：

(1) 顺序文件：通常适用于定长记录。

(2) 索引文件：通常适用于可变记录。

(3) 索引顺序文件：上述两种文件构成方式的结合。

2. 无结构文件

如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。在UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。

顺序文件

1. 逻辑记录的排序

第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，

第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。

2. 对顺序文件(Sequential File)的读/写操作

3. 顺序文件的优缺点

优点：顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。

缺点：在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。此外，在顺序文件中，如果想增加或删除一个记录，也比较困难。

索引文件

对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i×L

然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则

6.2.4 索引顺序文件

2.各外存分配方式的基本思路和特点、地址转换

连续分配

2. 连续分配的主要优缺点

连续分配的主要优点如下：

(1) 顺序访问容易。

(2) 顺序访问速度快。

连续分配的主要缺点如下：

(1) 文件不能动态增长。

(2) 外部碎片问题。

(3) 必须事先知道文件的长度。

6.3.2 链接分配

1. 隐式链接

2. 隐式链接的主要优缺点

隐式链接的主要优点如下：

(1) 提高磁盘的空间利用率，不存在外部碎片。

(2) 有利于文件的插入、删除和动态扩充。

隐式链接的主要缺点如下：

(1) 存取速度慢，一般只适用于信息的顺序存取。

(2) 可靠性问题。

3. 显式链接

6.3.3 索引分配

1. 单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：

(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。

(2) FAT需占用较大的内存空间。

2. 多级索引分配

2. 索引分配的主要优缺点

索引分配的主要优点如下：

(1) 保持了链接结构的优点，又解决了其缺点。

(2) 有利于文件的插入、删除和动态扩充。

索引分配的主要缺点如下：

索引表本身带来了系统开销。

3. 混合索引分配

例1. 假定盘块大小为1KB，硬盘的大小为500M，采用显式链接分配方式时，其FAT需占用多少存储空间？

例2. 请分别解释在连续分配方式、隐式链接分配方式、显式链接分配方式和索引分配方式中如何将文件的字节偏移量3500转换为物理块号和块内偏移量(设盘块大小为1KB，盘块号需占4个字节)。

例3. 存放在某个磁盘上的文件系统，采用混合索引分配方式。如果每个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址：

(1) 该文件系统允许文件的最大长度是多少？

(2) 将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。

(3) 假设某个文件的FCB已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次？

例4. 设一个文件由100个物理块构成。对于连续（开头已经没有空间扩展文件，但在结尾处还有空间扩展）、链接（单向）和一级索引存储方式，分别计算执行下列操作时所应启动I/O次数（FCB和索引块都在内存，并假定要扩展的信息块已经在主存）。

(1)将一块加在文件的开头 (4)从文件的开头去掉一块

(2)将一块加在文件的中间（51） (5)从文件的中间去掉一块

(3)将一块加在文件的末尾 (6)从文件的末尾去掉一块

分页存储管理-地址结构

1．操作系统对文件实行统一管理，最基本的是为用户提供(A)功能。

A．按名存取 B．文件共享

C．文件保护 D．提高文件的存取速度

解释：按名存取是用户访问文件的基本方式，用户通过文件名来操作文件。

2．按文件用途分类，编译程序是(A)。

A．系统文件 B．库文件

C．用户文件 D．档案文件

解释：编译程序通常被视为系统文件，因为它们是系统中用于代码转换的重要工具。

3．在随机存储方式中，用户以(D)为单位对文件进行存取和检索。

A．字符串 B．数据项 C．字节 D．逻辑记录

解释：随机存储方式通常是以逻辑记录为单位进行访问。

4. 采取哪种文件存取方式，主要取决于(C)。

A．用户的使用要求 B．存储介质的特性

C．用户的使用要求和存储介质的特性

D．文件的逻辑结构

5．文件系统的按名存取主要是通过(B)实现的。

A．存储空间管理 B．目录管理

C．文件安全性管理 D．文件读写管理

解释：目录管理提供文件的命名和定位功能，使得文件按名访问成为可能。

文件管理实际上是对(B)的管理。

A．主存空间 B．辅助存储空间

C．逻辑地址空间 D．物理地址空间

解释：文件管理涉及对辅助存储（如磁盘驱动器）的管理，而主存主要用于程序执行时的临时数据存储。

7. 如果文件系统中有两个文件重名，不应采用(A)结构。

解释：一级目录结构不支持同名文件，因为它不允许两个文件共享同一路径。

9．绝对路径是从( B)开始跟随的一条指向制定文件的路径。

10. 逻辑文件可分为流式文件和(C )两类。

A．索引文件 B．链接文件

C．记录式文件 D．只读文件

解释：逻辑文件通常分为流式文件（如文本文件）和记录式文件（如数据库记录）。

11．由一串信息组成，文件内信息不再划分可独立的单位，这是指(A)。

A．流式文件 B．记录式文件

C．连续文件 D．串联文件

12．记录式文件内可以独立存取的最小单位是由(C )组成的。

A．字 B．字节 C．数据项 D．物理块

13. 下列文件中，(A)的物理结构不便于文件的扩充。

A．顺序文件 B．链接文件

C．索引文件 D．多级索引文件

(B)的物理结构对文件随机存取时必须按指针进行，效率较低。

A．连续文件 B．链接文件

C．索引文件 D．多级索引文件

15. 数据库文件的逻辑结构形式是( C)。

A．链接文件 B．流式文件

C．记录式文件 D．只读文件

16．文件的逻辑记录的大小是(D )。

A．恒定的 B．相同的

C．不相同的 D．可相同也可不同

17．能用来唯一标识某个逻辑记录的数据项为记录的(A )。

A．主键 B．次键 C．索引 D．指针

解释：主键用于唯一标识数据库中的记录。

18. 链接文件解决了顺序结构中存在的问题，它(B)。

A．提高存储空间利用率 B．适合于随机存取方式

C ．不适用于顺序存取 D．指针存入主存速度快

19.文件系统可以为某个文件建立一张(B )，其中存放每个逻辑记录存放位置的指针。

A．位示图 B．索引表

C．打开文件表 D．链接指针表

20. 在文件系统中设置一张(B)，它利用二进制的一位表示磁盘中一个块的使用情况。

A．空闲块表 B．位示图

C．链接指针表 D．索引表

21．“打开文件”操作要在系统设置的( C)中登记该文件的有关信息。

A．索引表 B．链接指针表

C．已开文件表Ｄ．空闲块表

22．对顺序文件做读文件操作时，总是从(A)按顺序读出信息。

A. 文件头部向后 B．文件尾部向前

C．文件中部开始 D．当前位置开始

23. 假定盘块的大小为1KB，硬盘的大小为10GB，采用显示链接分配方式时，请问文件分配表占用多大空间?

磁盘大小：10GB = 10 * 1024 * 1024 KB = 10,240,000 KB
盘块大小：1KB

计算盘块数量：

总盘块数 = 磁盘大小 / 盘块大小
总盘块数 = 10,240,000 KB / 1 KB = 10,240,000（个盘块）

每个盘块需要一个表项，假设每个表项占用4个字节（常见的 FAT 文件系统情况）：

文件分配表（FAT）占用空间的计算：

FAT大小 = 总盘块数 * 每个表项大小
FAT大小 = 10,240,000 * 4 B = 40,960,000 B

换算为 KB：

FAT大小 = 40,960,000 B / 1024 = 40,000 KB

所以，文件分配表占用的空间为： 40,000 KB（或约 39.06 MB）。

24. 某系统中磁盘的每个盘块大小为1KB，外存分配方法采用中的混合索引结构，其中索引节点中直接地址6项，一级索引地址2项，二级索引地址1项，每个盘块号占用4个字节，请问该系统中允许的文件最大长度是多少？

系统中允许的文件最大长度=4X1+2X256X1+256X256X1=6+512+65536=66052KB

25. 有一个大小为500M的硬盘，盘块的大小为1KB,试计算其FAT的大小 (FAT表项的位数是半个字节的整数倍 )。若文件A占用11，12，16，14这4个盘块，画出各盘块间的链接情况图。

26. 一个计算机系统利用如下的位示图来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。

（1）现要从文件分配两个盘块，试具体说明分配过程。

（2）若要释放磁盘的第300块，应如何处理？

1.设置当前工作目录的主要目的是(C)
A．节省外存空间
B．节省内容空间
C．加快文件的检索速度
D．加快文件的读写速度

2.文件系统中，文件访问控制信息存储的合理位置是（A）

A．文件控制块 B．文件分配表
C．用户口令表 D．系统注册表

3.若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（A）

Ⅰ．若该文件的数据不在内存，则该进程进入睡眠等待状态

Ⅱ．请求read系统调用会导致CPU从用户态切换到核心态

Ⅲ．read系统调用的参数应包含文件的名称
A．仅Ⅰ、Ⅱ B．仅Ⅰ、Ⅲ C．仅Ⅱ、Ⅲ D．Ⅰ、Ⅱ和Ⅲ

解析：若该文件的数据不在内存中，则产生缺页，原进程进入阻塞状态(睡眠等待状态)，直到所需数据都被调入内存后才唤醒该进程，Ⅰ正确；read系统调用通过陷入(trap)将CPU从用户态切换到核心态，从而获取相应的系统服务，Ⅱ正确；读文件时首先用open系统调用打开该文件，open中的参数包含文件的路径名和文件名，read只需要使用open返回的文件描述符，不需要使用文件名作为参数。

4.用户在删除某文件的过程中，操作系统不可能执行的操作是(A )

A．删除此文件所在的目录
B．删除与此文件关联的目录项
C．删除与此文件对应的文件控制块
D．释放与此文件关联的内存缓冲区

解释：操作系统通常不会删除文件所在的目录，而是更新目录信息以反映文件的删除。
5.设文件F1当前引用计数值为1，先建立F1的符号链接(软链接)文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是（B）
A．0、1 B．1、1 C．1、2 D．2、1

[解析]

为了使文件实现共享，通常在文件的索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目(引用计数值)。当新文件建立时，一般默认引用计数值为1。

硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。

软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点。建立软链接文件时，文件的引用计数值不会增加。在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件访问被链接文件而己。

因此，在本题中，当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1。F2的引用计数值仍然保持不变。

6.若文件f1的硬链接为f2，两个进程分别打开f1和f2，获得对应的文件描述符为fd1和fd2，则下列叙述中，正确的是（B）

Ⅰ．f1和f2的读写指针位置保持相同

Ⅱ．f1和f2共享同一个内存索引结点

Ⅲ．fd1和fd2分别指向各自的用户打开文件表中的一项

A．仅Ⅲ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅱ D． Ⅰ、Ⅱ和Ⅲ

7.在一个文件被用户进程首次打开过程中，操作系统需要（B）

A．将文件内容读到内存中

B．将文件控制块读到内存中

C．修改文件控制块中的读写权限

D．将文件的数据缓冲区首指针返回给用户进程

解析：

一个文件首次被打开时，系统调用open将文件目录项从外存，复制到内存系统打开文件表的一个表目中，并返回指向该表目的指针(在open调用完成后，操作系统对该文件的任何操作都不再需要文件名，而是使用该指针)

当另一个进程再对该文件执行open时，则在其进程打开文件表中增加一个条目，指向系统打开文件表的相应条目

通常，系统打开文件表的每个条目，还用一个文件打开计数器来记录打开该文件的进程的个数，当计数器为0时，表明该条目对应的文件不再被使用，系统将回收分配给该文件的资源

注：

open调用不会把文件内容读到内存中，只有希望获取文件内容时才会将文件内容读到内存中

FCB的有序集合称为文件目录，一个FCB就是一个文件目录项

8.下列优化方法中，可以提高文件访问速度的是（D）
I. 提前读 II. 为文件分配连续的簇

III. 延迟写 IV. 采用磁盘高速缓存
A．仅 I、II B．仅 II、III

C．仅 I、III、IV D． I 、II、III、IV

解释：所有列出的方式都可以提高文件访问速度：

I. 提前读可以减少等待时间。
II. 分配连续的簇可以减少寻道时间。
III. 延迟写可以优化写入效率。
IV. 磁盘高速缓存可以加速存取。

9.下列文件物理结构，适合随机访问且易于文件扩展的是（B）

A．连续结构

B．索引结构
C．链式结构且磁盘块定长
D．链式结构且磁盘块变长

10.设文件索引结点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度是(C )
A．33KB B．519KB C．1057KB D．16513KB

解析：

索引文件既可以满足文件动态增长的要求又可以方便而讯速地实现随机存取。对一些大的文件，当索表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术这时在由索引表指出的物理块中存放的不是文件存放处而是存放文

件信息的物理块地址。这样，如果一个物理块能存储个地址则一级间接索引将使可寻址的文件长度变成2块，对于更大的文件可以采用二级甚至三级间接索引。根据试题给出的条件，可知表示的单个文件的最大长度为：4×256+2×(256/4)×256+1×(256/4)×(256/4)×256=1057KB

11.为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（A）。

A．连续结构 B．链式结构 C．直接索引结构 D．多级索引结钩

解释：连续结构能减少寻道和访问延迟，从而优化播放性能。

12.若某文件系统索引结点(inode)中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是( A)
A．索引结点的总数

B．间接地址索引的级数
C．地址项的个数

D．文件块大小

13. 在文件的索引结点中存放直接索引指针10个，一级和二级索引指针各1个。磁盘块大小为1KB，每个索引指针占4个字节。若某文件的索引结点已在内存中，则把该文件偏移量（按字节编址）为1234和307400处所在的磁盘块读入内存，需访问的磁盘块个数分别是 ( B)

A． 1,2 B． 1,3 C． 2,3 D． 2,4

解析：10个直接索引指针指向的数据块大小为10*1KB=10B:每个索引指针占4B,则每个磁盘块可存放1KB/4B=256个索引指针，一级索指针指向的数据块大小为：256*1KB=256KB二级索引指针指向的数据块大小为：256*256*1KB=216kB=64MB按字节编址偏移量为1234时，因1234B<10KB,则

由直接索指针可得到其所在的磁盘块地址。文件的索引结点已在内存中，则地址可直接得到，故仅需1次访盘即可。偏移量为307400时，因10KB+256KB<307400B<64MB,可知该偏移量的内容在二级索引指针所指向的某个磁盘块中，索引结点已在内存中，故先访盘2次得到文件所在的磁盘块地址，再访盘1次即可读出内容，故共需3次访盘。

14. 文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的 32～127 号块中，每个盘块占 1024 个字节，盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612，则位图中要修改的位所在的盘块号和块内字节序号分别是（C）

A． 81、1 B． 81、2 C．82、1 D． 82、2

分析：必须要说的是代入法更快。首先看81号，则32~80号共80-32+1 = 49块。则有49*1024*8 = 401408位，可以标记的磁盘块数远小于409612。所以排除A,B。

如果是在块号为82上，则前面共有32~81：81-32+1 = 50块，可以标记的块数为：409600块。OK，块号为409612的其实是第409613块，所以可以确定的是在块82上，一个字节标记8个块，两个字节标记16个，8< 13 <16,所以在第二个字节上。也就是1号字节。

即：82，1.

不必选用什么公式，基本法才是最佳的。

或直接算：409612/(1024*8) = 50.001

表示存在第51块上。因为是从32开始，即块32是第一块，所以32+50 = 82，这是小学数学，但是一不小心就算到83或81，从32开始数51块，32,33,34,35,…81,82。再计算50块可以标记的磁盘块数是409600，还需要两个字节，因此在1号字节上。

此外，位示图存在磁盘块上，似乎觉得影响计算，实际不用管，一样标记被位示图本身占用的磁盘。

15.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是 B

I．位图 II．索引结点

III．空闲磁盘块链 IV．文件分配表（FAT）
A．仅 I、II B．仅 I、III、IV

C．仅 I、III D．仅 II、III、IV

解析：传统的文件系统管理空闲磁盘的方法包括空闲表法、空闲链表法、位示图法和成组链接法，即 I 、III正确；

索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构，存储了文件的描述信息，索引结点属于文件目录管理部分的内容，即 II 不对；

文件分配表（FAT）的表项与物理磁盘块一一对应，并且可以用一个特殊数字 -1表示文件的最后一块，用 -2 表示这个磁盘块是空闲的，因此文件分配表（FAT）不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过FAT对文件存储空间进行管理，即 IV 正确。

1. 某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？

（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

2. 某文件系统空间的最大容量为4TB(1T=240)，以磁盘块为基本分配单位，磁盘块大小为1KB。文件控制块(FCB)包含一个512B的索引表区。请回答下列问题。

(1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节可支持的单个文件最大长度是多少字节。

(2)假设索引表区采用如下结构：第0～7字节采用＜起始块号，块数＞格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

解析：