目录

第一章 操作系统概述

1.操作系统的定义（19-20-1-A已考）

2.操作系统的作用

3.用户接口的定义

4.程序接口的定义

5.系统调用的定义

6.系统调用的实现原理、陷阱机制

7.应用程序与系统调用之间传递参数的方法（19-20-1-A已考）

8.系统调用与函数调用的区别

9.微内核结构的原理

10.微内核结构的特点

第二章 处理器管理

1.特权与非特权指令

2.内核态与用户态

3.处理器状态转换

4. 程序状态字（Program Status Word, PSW）

5.中断的定义

6.中断的分类

7.进程的定义

8.进程的状态与转换（七态模型）

9.进程控制块

10.进程上下文

11.线程

12.处理器调度（高级调度与低级调度）

13.周转时间的计算

14.处理器调度算法（计算题8’ ）【19-20-1-A已考两道批处理作业系统调度】

第三章 同步、通信与死锁

1.临界区与临界资源

2.信号量与PV操作（应用题15’）

第四章 存储管理

1.可执行程序的地址转换

2.分页存储管理

3.快表

4.多级页表（19-20-1-A 已考 论述题 15’）

5.反置页表

6.分段与分页的比较

7.请求分页虚拟存储管理的基本原理

8.页面替换策略（19-20-1-A 已考 计算题 8’）

9.抖动

10.工作集

第五章 设备管理

1.I/O控制方式

2.I/O软件四个层次【19-20-1-A已考 简答题 4’】

3.I/O操作执行步骤

4.磁盘调度算法【19-20-1-A已考 计算题 8’】

第六章 文件管理

1.文件存取方式

2.文件控制块（File Control Block,FCB）

3.索引文件【19-20-1-A已考 计算题 8’】

第七章 Windows结构分析

1. 系统结构【19-20-1-A已考 简答题 4’】

2.系统安全组件【19-20-1-A已考】

3. LPC的3种交换信息方式

4.用户登录过程【19-20-1-A已考 简答题 4’】

附录  2018/2019学年第一学期《操作系统结构分析》期末试卷（A）

第一章 操作系统概述

1.操作系统的定义（19-20-1-A已考）

操作系统是最基本的系统软件，是一组有效管理和控制计算机硬件和软件资源、合理地对各类作业进行调度以组织和控制系统工作流程，并方便用户使用计算机的程序的集合。

2.操作系统的作用

（1）操作系统应隐藏复杂的、困难的、丑陋的、特殊的硬件细节，向应用程序提供一种简单的、高度抽象的处理；

（2）操作系统是用户与计算机系统进行交互的界面；

（3）操作系统需要对资源进行监控、分配、回收和保护，以使资源得到充分合理的利用；

（4）操作系统是工作流程的组织者，协调各个任务的推进速度。

3.用户接口的定义

用户接口（User Interface，简称 UI）是系统和用户之间进行交互和信息交换的媒介，它实现信息的内部形式与人类可以接受形式之间的转换。通常指软件接口，一般有命令接口、程序接口、图形接口三种。

4.程序接口的定义

程序接口由一组系统调用（System Call）组成，用户程序使用“系统调用”就可获得操作系统的底层服务，使用或访问系统的各种软硬件资源。

5.系统调用的定义

操作系统为了达到为应用程序的运行提供良好的环境，系统内核提供了一系列具备预定功能的内核函数，这一组特殊接口称为系统调用。

6.系统调用的实现原理、陷阱机制

第一步，编写系统调用函数；第二步，设计系统调用入口地址表，每个入口地址都指向一个系统调用的内核函数，部分包含系统调用自带参数的个数；第三步通过陷阱处理机制，开辟现场保护区，保存发生系统调用时的处理器现场。

由系统调用引起的处理器中断的机器指令称为访管指令、自陷指令、中断指令。访管指令为非特权指令，CPU目态执行下转为内核态。

7.应用程序与系统调用之间传递参数的方法（19-20-1-A已考）

（1）访管指令或自陷指令自带参数

（2）通过CPU通用寄存器传递参数

（3）在内存中开辟专用堆栈区传递参数

8.系统调用与函数调用的区别

9.微内核结构的原理

操作系统仅将所有应用必需的核心功能放入内核，称为微内核，其他功能都在内核之外，由在用户态运行的服务进程实现。运行在内核态的内核提供系统基本功能，运行在用户态的进程层采用客户—服务器模型，由相对独立的若干服务器进程提供操作系统其他部分功能，采用消息传递机制进行通信。

10.微内核结构的特点

（1）对进程的请求提供一致性接口；

（2）具有较好的可扩充性和易修改性，可移植性好；

（3）对分布式系统提供有力支撑；

（4）进程间必须通过内核的通信机制才能通信，运行效率较低。

第二章 处理器管理

1.特权与非特权指令

（1）特权指令

具备改变机器状态、修改寄存器内容、启动设备I/O等特权的机器指令，如启动I/O设备、设置时钟、置中断屏蔽位、清空内存、建立存储键，加载程序状态字等。特权指令仅能由操作系统使用，应用程序如果运行特权指令，将会导致异常。

（2）非特权指令

指令系统中除了特权指令之外的指令。非特权指令既可以被操作系统使用，也可以被应用程序使用。

2.内核态与用户态

（1）内核态

操作系统管理程序运行的状态，较高的特权级别，可以执行全部指令，使用所有资源，并具有改变处理器状态的能力，又称为核心态、管态。

（2）用户态

用户程序运行时的状态，较低的特权级别，只有非特权指令能执行，又称为普通态（普态）、目态。

3.处理器状态转换

（1）内核态→用户态

执行特权指令(如Intel x86中iret指令)将用户程序的程序状态字PSW加载到PSW寄存器，实现从内核态返回用户态，CPU的控制权转交给用户程序。

（2）用户态→内核态

①程序执行系统调用，请求操作系统服务；

②程序运行时发生中断事件，运行程序被中断，转去执行中断处理程序；

③程序在执行时发生了异常事件，运行程序被打断，转去执行异常处理程序。

4.程序状态字（Program Status Word, PSW）

通常操作系统为每个运行中的程序引入程序状态字PSW来区别不同的处理器工作状态，并且保留和指示与运行程序有关的各种信息，存放在程序状态字寄存器中。PSW主要内容有程序基本状态（程序计数器PC；条件码：反映指令执行后的结果特征；处理器状态：内核态、用户态）、中断码（保存程序执行当时发生的中断事件）、中断屏蔽码（指明程序执行中发生中断事件时，是否响应出现的中断事件）。PSW的主要作用是实现程序状态的保护和恢复。

5.中断的定义

中断指在程序执行过程中遇到急需处理的事件时，暂时中止现行程序在CPU上的运行，转而执行相应的事件处理程序，待处理完成后再返回断点或调度其他程序执行的过程。

6.中断的分类

（1）外中断

①又称为中断或异步中断；

②泛指来自处理器之外的中断信号，包括外部设备中断、时钟中断、键盘中断和它机中断等；

③分为可屏蔽中断和不可屏蔽中断；

④高优先级中断可以部分或全部屏蔽低级中断。

（2）内中断

①又称为异常或同步中断；

②泛指来自处理器内部的中断信号，往往由于在程序执行过程中，发现与当前指令关联的、不正常的或错误的事件；

③细分为访管中断、硬件故障中断、程序性异常；

④内中断不能屏蔽，一旦出现应立即响应并处理。

（3）区别

7.进程的定义

进程（Process）是具有独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配、调度和保护的基本单位。

8.进程的状态与转换（七态模型）

①新建态：进程正在创建

②就绪态：一个进程已经具备运行条件，等待分配处理器。

③挂起就绪态：进程具备运行条件但仍在外存中，只有被调入内存才能得以被调度执行。

④运行态：进程占有CPU，并在CPU上运行。

⑤等待态（阻塞、睡眠）：进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）

⑥挂起等待态：进程正在等待某事件并且在外存中。

⑦终止态：进程已经完成执行

9.进程控制块

（1）定义

进程控制块（Process Control Block, PCB）是系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的动态变化过程。

（2）内容

①标识信息，存储在进程控制块中的数字标识符（通常是0~32767），包括：该进程的标识符(进程ID)、创建该进程的父进程的标识符和用户标识符（用户ID）。

②现场信息，通用寄存器、PC寄存器、用户栈指针寄存器、PSW等。

③控制信息，包括进程调度信息、进程组成信息、进程间的族系信息、进程间通信信息、进程段/页表、进程映像在外存中的地址、CPU占用和使用信息、进程特权信息、资源清单和文件传输和I/O信息等。

10.进程上下文

在操作系统中，进程物理实体和支持进程运行的环境合称进程上下文（Process Context），进程切换时需要实施进程上下文切换，保存老进程的上下文且装入新进程的上下文，以便新进程运行。

①用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段、用户栈和共享内存区；

②寄存器上下文： PSW寄存器、处理器状态寄存器、栈指针、通用寄存器的值；

③系统级上下文：进程控制块、内存管理信息（进程页表或段表）、核心栈（进程内核态运行时的工作区）等。

11.线程

（1）定义

线程是CPU使用的一个基本单元，它包括线程ID、程序计数器、寄存器组和堆栈。它与同一进程的其他线程共享代码段、数据段和其他操作系统资源，如打开文件和信号。引入线程后，进程作为系统分配和保护的独立单位，无须频繁地切换；线程作为系统调用和分派的基本单位，会被频繁地调度和切换。单线程（Single-threaded）进程又被为重量级（Heavyweight）进程，多线程（Multithreaded）进程又被称为轻量级（Lightweight）进程。

（2）线程和进程的区别与联系

12.处理器调度（高级调度与低级调度）

调度是多道程序系统的关键所在。系统运行性能（如吞吐量大小、周转时间长短、响应及时性等）在很大程度上都取决于调度，特别是处理器调度。

（1）高级调度（作业、长程调度）

①把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程和分配必要资源；

②再将新创建进程插入到就绪队列上准备执行；

③作业完成后还要做结束阶段的善后工作。

（2）低级调度（进程、短程调度）

用来决定就绪队列中的哪个进程将获得处理机，然后再由分派程序（Dispatcher）执行把处理机分配给该进程的具体操作。

A. 剥夺调度方式（Preemptive Mode）

允许暂停正在执行进程和重新分配处理机；抢占原则（优先权/短作业优先/时间片原则）；分时、实时及批处理系统均可，如 Win98/2K/XP, Linux, Unix等。

B. 非剥夺调度方式（Non-preemptive Mode）

处理机分配给进程直至完成或阻塞；引起进程调度的因素：当前进程执行完毕或因发生事件、提出I/O请求、执行原语操作而阻塞；实现简单、系统开销小，但难以满足紧急任务要求，故不宜在实时系统中采用，如DOS , Windows 3.x等系统。

13.周转时间的计算

假设作业i提交给系统的时刻是ts，完成的时刻是tf，所需运行时间为tk，那么：

①作业i的周转时间              ti = tf -ts

②平均作业周转时间             T=i=1nti∕n,

③平均作业带权周转时间     W=i=1nwi∕n,，其中单个作业的带权周转时间wi = ti / tk

14.处理器调度算法（计算题8’ ）【19-20-1-A已考两道批处理作业系统调度】

（1）先来先服务算法（First-Come,First-Served）

【非剥夺】选择最先进入就绪队列的进程投入执行，即进程按照请求CPU的顺序使用CPU。

解如下图所示。

等待时间分别是              P1= 0；P2= 28；P3 = 37

平均等待时间是              （0 + 28 + 37）÷ 3 = 22

平均作业周转时间是      （28 + 37 + 40）÷ 3 = 35

（2）最短作业优先算法（Shortest Job First）

【非剥夺】以进入系统作业/进程所要求的CPU时间长短为准，总是选取时间要求最短的投入运行。

（3）最短剩余时间优先算法（Shortest Remaining Time First）

【SJF+剥夺】如果一个新就绪进程所需的CPU时间比当前正在执行的进程所剩余时间短，那么新进程将抢占CPU。

                                  SRTF                                                     SJF

平均周转时间    T =（17+4+24+7)÷4 =13             T =（8+11+14+24）÷4 =14.25

平均等待时间    （9+0+15+2）÷4 = 6.5                  （0+7+9+15）÷4 = 7.75

（4）最高响应比优先算法（Highest Response Ratio First）

【非剥夺】短作业/进程优先调度算法+动态优先权机制。

响应比（优先级）=作业周转时间作业处理时间=作业等待时间+作业处理时间作业处理时间=1+作业等待时间作业处理时间

10:00     J2=1+70/50=2.4 ; J3=1+60/10=7 ; J4=1+10/20=1.5         J3 First

10:10     J2=1+80/50=2.6 ; J4=1+20/20=2                                      J2 First

（5）优先级调度算法（Priority）

每个作业/进程被赋予一个优先级（权），允许优先级（权）最高的就绪作业/进程先被调度；分为剥夺式和非剥夺式两种策略。

（6）时间片轮转调度算法（Round Robin）

每个进程被分配一个时间片，如果在时间片结束时该进程还在运行，则剥夺其CPU并分配给另一个进程，被剥夺CPU的进程则插入到就绪队列末尾，等待下次调度；如果该进程在时间片内阻塞或结束，则立即切换CPU。

算法执行结果如下图

等待时间     P1 =（68-20）+（112-88）+（145-132）= 85

P2 =（20-0）+（88-40）+（132-108）= 92

P3 =（40-0）+（108-60）= 88

P4 =（60-0）= 60

平均等待     （85+92+88+60）÷4 = 81.25

平均周转     （153+145+112+68）÷4 = 119.5

（7）多级反馈队列调度算法（Multi-Level Feedback Queue）

设置多个就绪队列并赋予各个队列不同优先权；不同队列中进程执行的时间片大小各不相同；是优先级调度算法、时间片轮转调度算法、先来先服务调度算法相结合的产物。

第三章 同步、通信与死锁

1.临界区与临界资源

（1）临界资源：一次只能供一个进程使用的资源

①许多物理设备都属于临界资源，如打印机、扫描仪等；

②许多可被多个进程共享的变量和文件也属于临界资源；

③对于临界资源的访问必须采用互斥方式。

（2）临界区：在并发进程中，访问临界资源的程序段

（3）锁（Lock）：阻止某进程做某事

在进入临界区前应该上锁；在离开临界区时要开锁；进程见到锁必须等待直到锁被打开；锁是实现临界区互斥访问的基本手段。

2.信号量与PV操作（应用题15’）

（1）信号量

信号量是一个数据结构，负责协调各个进程，以保证它们能够正确、合理的使用公共资源。

typedef struct semaphore

  {   int value;               //信号量的值

      struct pcb* list;     //信号量队列指针

  } semaphore;

semaphore s ;

信号量代表对某种公共资源的管理，其初值是一个非负整数，表征资源的数量。

要使用资源的进程需通过信号量：有资源时顺利通过；若没有资源可用，则所有进程都将进入对应信号量的等待队列。

当一个进程归还资源时，此时若信号量队列有等待进程则释放一个。

（2）PV操作

①P操作用于申请信号量管理的资源。（信号量的值减1，有条件阻塞自己）

②V操作用于释放资源。（信号量的值加1，有条件唤醒其它进程）

PV操作是原语，执行过程不可中断；除了初始化之外，P、V操作是两个唯一能对信号量进行处理 的操作。

// P操作
void P(semephore s) 
{
   	s.value = s.value - 1 ; 
    if (s.value < 0)    
         sleep(s.list);  //资源不足(或事件未到)则阻塞自己
}

//V操作
void V(semephore s)
{
   s.value = s.value + 1;
   if (s.value < = 0)
      wakeup(s.list);  //有进程等待资源(或事件)则唤醒“他人”
}

（3）用信号量机制实现同步

同步问题实质上是让那些随机发生的事件变得有序。实现的方法是调节并发进程的执行速度，让某些进程必须等待另一些进程的执行而得以继续。在同步问题里，我们利用P操作会引发等待的效果来实现调节并发进程执行速度的目标。为了让一个进程等待，信号量的值应该为0，一般此种信号我们称为私有信号量。私有信号量用于联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，而其它相关进程可在其上施行V操作。

（4）生产者与消费者问题★

生产者(P)与消费者(C)共用一个缓冲区，P进程不能往“满”的缓冲区中放产品，C进程不能从“空”的缓冲区中取产品。因为共享了缓冲区，故并发的P、C进程有可能产生与时间相关的错误，因而要采取措施使两进程执行同步。分别为P和C进程设置两个信号量，用于指示进程是否可以执行。单个缓冲区的情况，初始状态为空。

K个缓冲区的情况，初始状态为空。

PV操作必须成对出现，有一个P操作就一定有一个V操作。当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。如果P(full)或P(empty)和P(mutex)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前，而两个V操作无关紧要。

（5）读者写者问题★【19-20-1-A已考 写者优先 15'】

有两组并发进程：读者和写者，共享一个文件，要求：允许多个读者同时执行读操作；写者执行写操作前，应让已有的写者和读者全部退出；任一写者在完成写操作之前不允许其它读者或写者工作。

概括      某一时刻，允许存在多个读者，但仅能有一个写者。

思路      一个写者到达时，如果发现有读者正在读，则等待；否则开始写

一个读者到达时，如果有写者正在写，则等待；否则开始读

读者和写者使用文件时会发生竞争问题，读者和读者可以共存。

先设置一个信号量db解决读者和写者之间的竞争，表示是否允许写。

如何判断是否有读者以及读者离开时是最后一个？设置一个int变量rc记录当前正在读文件的读者数量。

3.死锁

（1）定义

如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件，而无限期陷入僵持的局面称为死锁。

（2）产生条件

①互斥使用，一个时刻，一个资源仅能被一个进程占有

②不可剥夺，除了资源占有进程主动释放资源，其它进程都不可抢夺其资源

③占有和保持，一个进程请求资源得不到满足等待时，不释放已占有资源

④循环等待（上面三个条件同时存在的结果），每一个进程分别等待它前一个进程所占有的资源。

（3）死锁与饥饿

4.银行家算法（计算题8’）【19-20-1-A已考】

（1）死锁的避免

死锁的避免允许同时存在四个必要条件，试图在系统运行过程中避免死锁的发生。

方法：系统对进程每次发出的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

安全状态——如果存在一个由系统中所有进程构成的序列P1 ... Pn，按照此序列分配资源不会导致死锁，则系统处于安全状态（安全序列可能不止一个）。

不安全状态——不存在任何一个安全序列，则系统处于不安全状态，不安全状态会导致死锁。|

（2）银行家算法

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

为保证资金的安全，银行家规定：

①当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

②顾客可以分期贷款，但贷款的总数不能超过最大需求量；

③当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

④当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金。

A.单种资源的银行家算法

B.多种资源的银行家算法

每一个新进程进入系统时，必须声明需要每种资源的最大数目，其数目不能超过系统所拥有的的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程，若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态如果不会才将资源分配给它，否则让进程等待。

银行家算法中的数据结构

①Available向量：系统中可利用的资源数目；

②Max/Claim矩阵：每个进程对每种资源的最大需求；

③Allocation矩阵：每个进程已分配的各类资源的数目；

④Need矩阵：每个进程尚需的各类资源数。

实例 假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}各类资源的数目分别是10,5,7，已知T0时刻资源分配情况如下：

将可利用的资源分配给某个需要资源小于可利用资源的进程，让这个进程运行完成，进程运行完成之后已分配的资源就会被释放，然后继续执行上述操作，只要能找到满足Need小于Available，就分配资源，让该进程运行完成，最后将资源释放，也就是将已分配的资源加到可利用的资源，如果最后每一个进程都能运行完成就得到了我们的安全序列，所以系统就是安全的，如果存在一个进程，可利用资源不能满足需求就不再分配。

Step.1 将Available和Need对比，P0的Need>Available，不满足，往后找；

Step.2 进程P1的Need小于Available，所以资源分配给P1，P1就能运行完成，最后释放资源{2,0,0}，所以现在的资源就是{3,3,2}+{2,0,0}={5,3,2}；

Step.3 然后继续向下找，P2不满足条件，P3满足条件，将资源分配给P3，让其运行完成，并释放空间{2,1,1}，所以现在的资源就是{5,3,2}+{2,1,1}={7,4,3}；

Step.4 依次类推得到安全序列为{P1,P3,P4,P2,P0}。

第四章 存储管理

1.可执行程序的地址转换

（1）静态地址重定位

由装载程序在将装入模块装入内存时一次性完成重定位，将其中所有逻辑地址修改成物理地址。在进程执行前一次完成，无需硬件支持，易于实现；需要连续存储空间，装入后位置固定，不能移动。

（2）动态地址重定位

装载程序对逻辑地址不做任何修改，程序内存起始地址被置入基址寄存器（Base Register, BR），在程序执行过程中要访问数据时再进行地址变换。

2.分页存储管理

（1）基本原理

页框（Frame）：把内存空间划分成大小相等的若干存储区域，每个区称为一个物理块，又称页框。从0开始连续编号。

页面（Page）：程序逻辑地址空间按页框大小分为若干页，不足一页的部分补齐为一页，依序从0、1……编号，称为页面。逻辑地址由页号和页内位移两部分组成。

页表（Page Table）：是在进程装入内存时，由系统根据内存分配情况建立的，是程序页面和内存页框的对照表 ，其大小随进程大小而定。为了减少系统开销，系统在内存中开辟存储区专门存放进程页表。

（2）基本地址变换（计算题 8’）

页表基址寄存器：存放当前运行进程页表的起始地址。

物理地址=页框号×块长+页内位移

例 某系统采用分页存储管理方式，设计如下：页面大小为4KB，允许用户逻辑地址空间最大为16页，允许系统物理内存最多为512个页框。试问该系统逻辑地址寄存器和物理地址寄存器的长度各是多少？

解 页面大小L=4KB=212字节，即页内偏移量占12位。页框大小等于页面大小，为4KB。

允许用户逻辑地址空间最大为16页=24页，即页号占4位；

允许系统物理内存空间最多为512个页框=29个内存块，即内存块位数占9位；

逻辑地址寄存器位数=页号位数+页内偏移量位数=16位；

物理地址寄存器位数=页框号位数+页框内偏移量位数=21位。

例 已知某分页系统，主存容量为64KB，页面大小为1KB，对于一个4页的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。

解 如下表所示

3.快表

快表（TranslationLook-aside Buffer, TLB）一组存放进程最近访问的部分页表项的高速缓冲区，它基于程序局部性原理，能显著缩短地址转换过程的时间，解决CPU运算速度快和主存访问速度相对慢之间的瓶颈问题。

① 读出CPU给出的有效逻辑地址，分成页号和页内地址，由地址变换机构自动将页号与快表中的页号比较，这种比较是同时进行的。

② 若其中有相匹配的页号，表示快表存在所要访问的页表项，直接读出对应的页框号，送物理地址寄存器形成物理地址。

③ 若在快表中未找到对应的页表项，则MMU访问内存中的页表，  形成物理地址，并将该条页表项记入TLB。

④ 若快表已满，则系统根据某种算法找到一个不再需要的页表项换出，如FCFS算法。

例 假定快表检索时间为20ns，内存访问时间为100ns，则若能在快表中找到CPU给出的页号，CPU为存取一个数据将需要（100+20）= 120ns；而若不能在快表中找到CPU给出的页号，CPU为存取一个数据将需要（100+100+20）=220ns （单级页表情况下）。进一步说，若假定快表查找命中率为90%，则其有效访问时间为120×90%＋220 ×（1－90%）=130ns。

4.多级页表（19-20-1-A 已考 论述题 15’）

对页表按内存页框大小进行分页，对它们进行编号并离散地存放于不同的页框中；同时为离散分配的页表分页再建立一张页表，称之为外层页表，以记录各页表分页对应的页框号。以前述32位逻辑地址空间、页面大小为4KB的系统为例，若采用一级页表结构，则每个进程页表的页表项可达1M个；而若采用两级页表结构，由于各页表分页包含4KB/4B=1K个页表项，故需1K个页表分页即可，因此外层页表的外层页号及内层页号均为10位。此时逻辑地址结构为：

地址转换如下图所示。

5.反置页表

反置页表（Inverted Page Table,IPT）是为每一个页框设置一个页表项并将按页框号排序，其中的内容则是页号及其隶属进程的标志符。

地址转换如下图所示。

6.分段与分页的比较

7.请求分页虚拟存储管理的基本原理

请求分页虚存管理是将进程信息副本存放在外存中，当它被调度投入运行时，程序和数据没有全部装进内存，仅装入当前使用页面，进程执行过程中访问到不在内存的页面时，再由系统自动调入。

缺页异常是由于发现当前访问页面不在内存时由硬件所产生的一种特殊中断信号，是在指令执行期间产生并由系统处理的。

缺页中断率=缺页中断次数/页面访问次数

8.页面替换策略（19-20-1-A 已考 计算题8’）

（1）最佳页面替换算法（OPTimal Replacement,OPT）

从页面访问序列中选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。

例 某进程分配获得三个页框

缺页中断次数为9 次，缺页率9/20=45%

（2）先进先出替换算法（First - In First - Out Replacement,FIFO）

在当前页框中选择驻留时间最久的页面淘汰出内存，进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面。

缺页中断次数为15 次，缺页率15/20=75%

（3）最近最久未使用替换算法（Least Recently Used Replacement,LRU）【19-20-1-A 已考】

根据局部性原理，以“最近的过去”作为“最近的将来”的近似，在当前页框中选择最近一段时间最长时间未被访问的页面淘汰出内存。

如上图，使用一个特殊队列实现，队列存放当前内存中的页号，队列头指向最久未访问的页，队列尾指向最近访问的页，每执行一次页面访问就做一次队列调整：如果页面在内存中，则将该页调整到队列尾；如果发生缺页，则淘汰队列头指向的那一页。

缺页中断次数为12 次，页面替换次数为9次，缺页率12/20=60%

9.抖动

定义：当主存中调出一个页面后又要使用这个页面，系统不断地产生缺页中断，这种反复地出现页面替换和页面调入的现象称为抖动现象。

成因：内存中同时运行的进程太多，而分配给每个进程的页框太少，不能满足他们正常运行的需要。由于出现频繁缺页异常，使得排队等待页面对换的进程数目剧增，从而使磁盘的有效时间大都花费在对换页面上，处理器的有效利用率则大大降低，系统产生抖动。

10.工作集

一个进程运行在时刻t-Δ到时刻t之间的时间间隔内所访问的页面集合称为该进程的在时刻t的工作集，用W(t, Δ)表示。Δ为工作集窗口。

|W(t, Δ)|表示工作集尺寸，即最近Δ时间内工作集中所包含页面的数目。

第五章 设备管理

1.I/O控制方式

①轮询，简单的忙-等待方式。

②★中断驱动I/O控制方式，中断机制的引入。

CPU启动I/O设备后，不必查询I/O设备是否就绪，继续执行现行进程或进程阻塞后重新调用其他就绪进程；设备一旦就绪则发出中断通知CPU；中断处理程序中，CPU全程参与数据传输操作。

③★直接存储器访问控制方式，DMA控制器、数据传输单位扩大。【19-20-1-A已考 名词解释 4’】

在DMA方式中，内存和外设之间有一条数据通路，在内存和外设之间成块传送数据过程中，由DMA控制器取代CPU来控制数据传输，直接执行到数据块传输完成。

④I/O通道控制方式，通道、I/O操作组织和数据传送的独立。

2.I/O软件四个层次【19-20-1-A已考 简答题 4’】

（1）I/O中断处理程序

（2）I/O设备驱动程序

（3）独立于设备的I/O软件

（4）用户空间的I/O软件

3.I/O操作执行步骤

①应用进程对已打开文件的文件描述符执行读系统调用（库函数）；

②独立于设备的I/O软件检查参数是否正确，若正确，检查高速缓存中有无要读取的信息块；若有，从缓冲区直接读至用户区，完成I/O请求；

③若数据不在缓冲区，执行物理I/O操作，独立于设备的I/O软件将设备的逻辑名转换成物理名，检查对设备操作的许可权，将I/O请求排队，阻塞应用进程且等待I/O操作完成；

④内核启动设备驱动程序，分配存放读出块的缓冲区，准备接收数据并向设备控制寄存器发送启动命令，或建立DMA传输，启动I/O；

⑤设备控制器操作设备，执行数据传输；

⑥当采用DMA控制器控制数据传输时，一旦传输完成，硬件产生I/O结束中断；

⑦CPU响应中断，转向磁盘中断处理程序。它检查中断产生原因和设备的执行状态，若设备有错，向设备驱动程序发信号，查是否能重复执行，如果允许，重发启动设备命令，再次传输；否则，向上层软件报告错误。若设备I/O正确完成，将数据传输到指定的用户进程空间，唤醒阻塞进程并将其放入就绪队列；然后，系统检查有无I/O请求在排队，若有，再启动设备，继续传输。至此，中断处理完成且返回，将成功或失败的信息逐层向上报告；

⑧当应用进程被再次调度执行时，从I/O系统调用的断点处恢复执行。

4.磁盘调度算法【19-20-1-A已考 计算题 8’】

（1）磁盘的结构

盘片：磁性数据载体，分单面和双面

磁道：能被磁头访问的一组同心圆

扇区：数据存放的基本单位，通常为512B

柱面：磁头位置下所有磁道组成的柱体

柱面号：指盘面上的磁道号，磁道号从0开始由外向里编号，不同盘面上具有相同编号的磁道属于同一柱面；

磁头号：指出读写磁头所在的盘面，磁头号按从上到下的盘面次序从0开始编号；

扇区号：按磁盘旋转方向从0开始给各扇区编的号。

计算：设m为每个柱面的磁头数，k为每个磁道的扇区数，某个块号的定位参数为(a, b ,c)，其中a, b, c分别表示该块的柱面号、磁头号和扇区号，则对应的块号x为：x = a*m*k + b*k + c

由块号求它在磁盘上的位置, 则：a= x DIV (m*k)、b = (x MOD (m*k)) DIV s、c = (x MOD (m*k)) MOD k

例 某磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字（0-199）来组成位示图来管理盘空间。现问：①位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少？②现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0？

解 ①位示图第15个字的第7位对应的块号=15×16（字长）+7=247，而块号247对应的：柱面号=247/（8×4）=7（从0编号，向下取整），磁头号=（247 MOD 32）/4=5，扇区号=247 MOD 32 MOD 4=3。

②块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇区=56×（8×4）+6×4+3=1819，字号=1819/16=113，位号=1819 MOD 16=11。所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。

（2）磁盘的调度

用户进程需要访问磁盘时，会向操作系统发出磁盘I/O请求，如果磁盘控制器正忙则会将请求插入一个等待队列。具有多个进程的系统，磁盘队列可能有多个待处理的请求。当一个请求完成时，这时OS可以决定谁下一个访问磁盘，这种调度技术被称为驱动调度技术，或磁盘调度技术。

①先来先服务调度（First-Come First Served,FCFS）【19-20-1-A已考】

按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置。

算法公平简单，但未对寻道进行优化，平均寻道时间较长，仅适合磁盘请求较少的场合。

例 200个柱面，编号0~199，I/O请求队列 = 98、183、37、122、14、124、65、67，磁头开始于53；求平均寻道长度。

(45+85+146+85+108+110+59+2)=640

平均寻道长度为640/8=80

②★最短寻道时间优先调度（Shortest-Seek-Time-First,SSTF）【19-20-1-A已考】

选择所访问磁道与磁头当前所在磁道距离最近的I/O请求优先调度。

具较好的寻道性能，但可能导致进程饥饿现象。

(12+2+30+23+84+24+2+59)=236

平均寻道长度为236/8=29.5

③扫描调度（SCAN）

移动臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直到磁盘的最后一个柱面后，再向相反方向移动回来。

既能获得较好的寻道性能，又能防止进程饥饿，广泛用于大中小型机及网络中。

(16+23+14+65+2+31+24+2+59)=236

平均寻道长度为236/8=29.5

④循环扫描调度（Circular SCAN, C-SCAN）

与SCAN相似，只是C-SCAN在扫描到最大柱面后直接返回0号柱面重复进行，归途中不再服务，构成了一个循环。

(12+2+31+24+2+59+16+199+14+23)=382

平均寻道长度为382/8=47.75

⑤★电梯调度（LOOK）

电梯调度不像扫描算法那样一直扫到底，如果沿着目前的方向无请求的话则立即折返。

(12+2+31+24+2+59+146+23)=299

平均寻道长度为299/8=37.375

第六章 文件管理

1.文件存取方式

①顺序存取

文件信息按顺序进行处理，存取时按照从前到后的顺序，每读/写完一个记录，指针自动推进以指示下一个要读/写的记录位置。

②直接存取

流式文件或定长记录文件，可实现直接访问。要读/写第i个字节/记录时，相对于文件首部的偏移是Nxi，N表征字节或记录长度，用户每次存取时要告之访问相对记录号（块号）。

③索引存取

一个逻辑文件中的记录过多时，读取一个想要的块可能要花费大量的时间去查找。

对记录创建索引表，文件的记录按键值排序，用户通过键值查找文件记录(通常使用折半查找)。

此方法需要占用存储空间存放索引表，索引表的大小与文件记录的数量成正比。

2.文件控制块（File Control Block,FCB）

操作系统为每个文件建立的唯一数据结构，其中包含了全部文件属性，其目的是为方便操作系统对文件的管理、控制和存取。

文件被创建时，系统为其建立一个FCB，用来记录文件的属性信息；每当存取文件时，先找到其FCB，再找到文件信息盘块号、首块物理位置或索引表，随后存取文件信息。

文件= FCB +文件体

3.索引文件【19-20-1-A已考计算题8’】

（1）多级索引结构下，文件最大长度问题【19-20-1-A已考】

例 假如每个盘块大小为1KB，每个盘块号占4B，则：

单级索引：256*1KB=256KB

二级索引：256*256*1KB=64MB

三级索引：256*256*256*1KB=4GB

例 假如每个盘块大小为4KB，每个盘块号占4B，则：

单级索引：1K*4KB=4MB

二级索引：1K*1K*4KB=4GB

三级索引：1K*1K*1K*1KB=1TB

（2）Unix混合索引下文件的字节偏移量转换成物理地址【19-20-1-A已考】

例 假定每个盘块1KB,每个盘号占4B，文件索引节点中的磁盘地址明细表如图所示，如何将下列文件的字节偏移量转换为物理地址？

①9000

②14000

③350000

① 字节偏移量为9000

逻辑块号为：9000/1024＝8

块内偏移量为：9000－8×1024＝808

因逻辑块号小于10，因此该块为直接块。其物理盘块号为367，该块中的第808字节即为文件的第9000字节。

② 字节偏移量为14000

逻辑块号为：14000/1024＝13

块内偏移量为：14000－13×1024＝688

因逻辑块号10<13<266，因此该块为一级间接块。由图可知，一级间接的盘块号为428，从一次间接块中读出盘块号表，查得其物理块号为952，该块中的第688字节即为文件的第14000字节。

③ 字节偏移量为350000

逻辑块号为：350000/1024＝341

块内偏移量为：350000-341×1024＝816

因逻辑块号266<341<65802，因此该块为二级间接索引块。

由图可知，二次间接索引块的盘块号为9156。

由于一个一次间接索引块中可容纳256个块号，341-10-256＝75<256

因此，字节偏移量350000在二次间接索引块的第0个一次间接块的第75个表项中，其盘块号为333，该块中的第816字节即为文件第350000字节。

第七章 Windows结构分析

1. 系统结构【19-20-1-A已考 简答题 4’】

分层+客户/服务器（微内核）结构

（1）用户模式进程

系统支持进程：管理系统所需的用户模式服务，如会话管理程序；

服务进程：打印机后台管理程序、事件记录器、与设备驱动协作的用户模式构件、不同的网络服务程序等；

环境子系统：提供不同的操作系统个性化设置；

用户应用程序：为充分利用系统功能而为用户提供的可执行程序(EXE) ，一般针对特定的环境子系统；

子系统动态链接库 NTDLL.DLL：用户进程无法直接使用系统服务，它们必须通过子系统DLL与系统交互。

（2）内核模式组件

内核：控制处理器执行；

执行体：提供操作系统核心服务；

设备驱动：用于扩展执行的动态库，实现系统的扩充功能；

硬件抽象层：用于提供虚拟硬件接口，以隐蔽硬件差异性；

窗口和图形系统：提供GUI函数。

2.系统安全组件【19-20-1-A已考】

SRM：执行体的一个组件，负责安全检查、权限处理；

LSA：一个用户态进程lsass.exe,本地安全策略执行；【19-20-1-A已考 名词解释 2’】

Winlogon：用户态进程winlogon.exe,将账号和密码交给LSA验证；

LSA策略数据库：保存安全策略设置；

SAM数据库：包含本机上的用户、组口令和其他属性。

3.LPC的3种交换信息方式

（1）小于256bytes：将消息从发送方的缓冲拷贝到系统空间，再从系统空间拷贝到接收方进程地址空间；

（2）大于256bytes：双方共享一块存储区域；

（3）消息量很大：直接读或写对方的存储空间。

4.用户登录过程【19-20-1-A已考 简答题 4’】

（1）用户按下SAS（Ctrl+Alt+Del）；

（2）winlogon捕获到启动GINA，用户输入用户名和密码；

（3）winlogon调用msgina.dll的函数将取得的用户名与密码通过LPC告之lsass；

（4）lsass调用认证数据包msv1_0.dll的函数，将口令作Hash后与SAM数据库进行比对，相同则登录成功。

附录  2018/2019学年第一学期《操作系统结构分析》期末试卷（A）