操作系统考点总结

type

status

date

slug

summary

os考点

第一章:

1.中断:

1.硬中断(中断/外中断):

来自CPU执行指令外部的事件，通常用于信息输入/输出

外中断又可以分为可屏蔽中断和不可屏蔽中断

时钟中断，表示一个固定的时间片已到，让处理机处理计时、启动定时运行的任务等。

2.软中断(异常/内中断):

来自CPU执行指令内部的事件，例如程序的非法操作码、地址越界等。异常不能被屏蔽，一旦出现就应立即处理

异常都是不可屏蔽的

异常可以分为故障、Trap和终止

故障一般是指令执行引起的异常
Trap用于在用户态下调用操作系统内核程序
终止指出现了使得CPU无法继续执行的硬件故障

处理外部事件：中断允许外部设备（如硬件设备或其他程序）向处理器发出信号，以便操作系统能够及时响应外部事件，如I/O完成、时钟信号等。

提高系统的响应性：通过中断，操作系统可以立即对紧急事件做出响应，而不需要等待某个任务的完成。这有助于提高系统的实时性和响应性。

实现多任务处理：中断允许操作系统在多个任务之间进行快速切换，从而实现多任务处理。当一个任务被中断时，操作系统可以暂停当前任务的执行，转而执行中断处理程序，然后再返回到原任务。

提高系统的效率：中断允许操作系统在需要时才进行处理，而不是持续地轮询或忙等待。这有助于节省处理器资源，提高系统的效率。

实现设备驱动：中断机制也被用于设备驱动程序，允许外部设备与处理器进行通信和交互。

2.计算机发展历史:

操作系统的发展大致经历了以下几个阶段：

手工操作阶段

批处理阶段

分时操作系统

实时操作系统

网络操作系统和分布式计算机系统

个人计算机操作系统

其中比较重要的有:

1.多道程序设计:

属于"批处理阶段",批处理阶段包括单道批处理系统和多道批处理系统

多道程序设计的特点是多道、宏观上并行、微观上串行：

多道：内存中存放多道程序。
宏观上并行：同时进入系统的多道程序都在执行过程中
微观上串行：内存中的多道程序轮流占有CPU

优点:

作业流程自动化
效率高
吞吐量高

缺点

无交互手段
调试程序困难

2.分时操作系统:

分时技术：把处理器的运行时间分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用。

分时操作系统：多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而互不干扰。实现分时系统的关键是如何使用户能与自己的作业进行交互。分时系统的主要特征为：

同时性（多路性）：允许多个终端用户同时使用一台计算机。
交互性
独立性
及时性

3.实时操作系统

根据对实时程度的要求，实时操作系统可以分为:

硬实时操作系统：某个动作必须在规定的时刻内完成。
软实时操作系统：能够接受偶尔违反时间规定且不会引起任何永久性的损害。

3.并发和并行的区别

并发:两个或多个事件在同一间隔内发生(操作系统的特征之一,另外三个为:共享,虚拟,异步)

系统具有处理多个任务的能力,这些任务可以在重叠的时间段内启动、运行和完成。在并发系统中，多个任务可以同时存在，但实际上在某一时刻只有一个任务在执行，通过时间片轮转或事件驱动等方式实现任务之间的切换。并发通常用于提高系统的响应性、资源利用率和性能。

并行:

系统同时执行多个任务，每个任务在不同的处理器核心或计算单元上独立运行。在并行系统中，多个任务同时执行，可以显著提高程序的执行速度和吞吐量。

4.模式:

1.用户态(目态)和核心态(管态):CPU的两种运行模式

用户态和核心态的区别在于对计算机资源的访问权限不同

处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理机是可被抢占的

处于核心态执行的进程，则能访问所有的内存空间和对象，其所处于占有的处理机不可被抢占

2.众多指令

特权指令:不允许用户直接使用的指令，例如I/O指令、置中断指令等。从指令系统（指令集）角度定义，在指令系统中拥有用于管理硬件和整个系统安全的指令，让程序随意使用具有极高危险性。不得在用户态（目态）执行，只能在核心态（管态）执行，用户态程序如果运行特权指令将发生异常，并切换到管态由操作系统接管cpu。

非特权指令:不能直接访问计算机的软硬件资源

访管指令:顾名思义,"请求访问管态的指令",从指令集的角度定义，或者说从硬件角度（cpu状态). 用户程序自愿进管的指令（进管同时也意味着程序放弃cpu的控制权），该指令本身属于非特权指令，可在用户态执行，执行后进入核心态。
陷入指令:原则上可看作访管指令，但是从操作系统的角度定义的。

访管强调的是cpu从用户态切换到了核心态，可以执行指令集中的所有指令。而陷入（自陷、陷阱）指令强调程序从用户程序切换到了操作系统，陷入指令即汇编中的中断指令，执行陷入指令后程序中断，跳转到中断服务程序（操作系统的代码）。所以访管强调的是可以执行特权指令，陷入强调的是进程放弃cpu，交还给操作系统。
用户程序所依靠的指令，用于发起系统调用，请求操作系统提供服务。

广义指令（系统调用）：从操作系统的角度定义的。指用户程序需要借助操作系统来完成的特定操作，通过陷入指令可以进行系统调用。系统调用是一段代码而不是一条代码，在高级语言层面可能是一条，比如c语言的系统调用write()，在汇编层面这条语句包括，初始化相关参数和寄存器，执行陷入（中断）指令，跳转到中断服务程序，中断返回。

之所以需要系统调用是因为用户程序不能执行特权指令，所以当需要完成特权指令才能做的特定操作，必须通过系统调用由操作系统完成。但系统调用一词并非强调程序不能使用特权指令，即不强调“需要”操作系统服务，仅仅强调“希望”让操作系统服务，表达的含义不是"不能"而是"不需要"，即目标操作用户程序不需要自己做，直接调用操作系统即可完成，进行系统调用时也并非一定为了执行特权指令，也可能相关操作过于复杂，或者用户程序自身难以实现（有权做但做起来麻烦），而操作系统刚好给出了相应的接口供直接使用。

库函数:操作系统提供的函数，供用户程序直接调用，简化程序的编写。编程时调用库函数直接使用操作系统已经实现的功能即可。与系统调用有些相似，不过库函数调用可以在用户态执行(不需要执行特权指令时)，和普通的函数调用应该并没有什么区别。

第二章

1.系统调用

系统调用：运行在使用者空问的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供了用户程序与操作系统之问的接口。大多数系统交互式操作需求在内核态执行。或：操作系统中一组用于实现各种功能的子程序，用户在应用程序中可以通过系统调用命令调用他们。

系统调用是指用户在程序中调用操作系统所提供的一些子功能，可视为特殊的公共子程序。通常，系统调用可以分为以下几类：

设备管理：设备的请求和释放、启动
文件管理：文件的读、写、创建以及删除
进程管理：进程的创建、撤销、阻塞以及唤醒
进程通信：进程之间的消息传递或信号传递
内存管理：完成内存的分配、回收以及获取作业占用内存大小以及起始地址等功能

系统调用的执行要由内核完成，运行在核心态。用户编写的程序通过执行陷入（trap）指令发起系统调用，要求操作系统提供服务，由操作系统代为执行。

从核心态转入用户态一般是由中断返回指令完成，他是一条特权指令；由用户态进入内核态则会用到访管指令，他不是特权指令。
由用户态进入核心态，不仅状态需要切换，程序堆栈也需要进行切换。

向操作系统传递参数的方法：

寄存器

内存的块/表，传递内存地址

堆栈

2.操作系统结构(简单结构、分层方法、微内核、模块化、虚拟机)

操作系统最重要的一点是要有多道程序处理能力。多道程序设计通过组织作业（编码或数据）使CPU 总有一个作业在执行，从而提高了CPU 的利用率。

1.简单结构

MS-DOS和UNIX。

2.分层方法

操作系统分成若干层（级）。最底层（层0）为硬件，最高层（层N）为用户接口。(理想方法，困难在于如何划分层）

3.微内核

微内核方法将所有非基本部分从内核中移走，并将它们实现为系统或用户程序，这样得到了更小的内核。

微内核的主要功能是使客户程序和运行在用户空间的各种服务之间进行通信。

4.模块

大多数现代操作系统按模块方式实现内核采用面向对象的方法，每个核心组件是分开的，每部分与已知接口的其他部分通信。可以是动态加载方式，每部分根据需要加载到内核总之，类似于层，但更灵活。

5.虚拟机

虛拟机（Virtua lNachine）指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的“完整”计算机系统。

第三章

1.进程和线程

1.进程

进程可以有不同的定义，通常称他为程序的一次执行过程，即“进行中的程序”。为了描述进程，操作系统中有专门的数据结构PCB（进程控制块）来描述进程的基本情况和运行状况，进而控制和管理进程。进一步的，程序段、相关数据段和PCB三部分共同构成了进程实体（进程映像）。

创建进程，指的其实是创建进程实体中的PCB，撤销进程也是撤销进程的PCB。

进程映像是静态的，进程是动态的；PCB是进程存在的唯一标志。

进程具有五个特征：

动态性：是进程的最基本的特征，表现在进程由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡。
并发性：多个进程实体同存于内存中，能在一段时间内同时执行。
独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。
异步性：指进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。
结构特征：从结构上看，进程实体由程序段、数据段以及进程控制块（PCB）组成，这三部分也称为进程映像。

2.进程的状态与转换

进程总共有五种状态，基本状态为前三种：

运行态：进程在处理机上运行。对单处理机来讲，同一时刻只有一个进程运行。

就绪态：进程获得了除处理机以外的所有资源。系统中处于就绪态的进程一般有多个，他们按顺序排列组成了就绪队列。

阻塞态（等待态）：进程正在等待某一事件而暂停运行。根据阻塞原因的不同，操作系统一般会组织多个阻塞队列。

创建态：进程正在被创建，尚未转到就绪态。创建进程时，需要先申请一个空白PCB，向PCB中写入控制和管理进程的信息、为该进程分配运行所需的资源，将该进程转入就绪态并插入就绪队列。

结束态：进程正在从系统中消失。系统会先将一个进程标志为结束态，然后进行资源的释放和回收。

进程状态之间的转换有四种：

就绪态 -> 运行态：获得处理机资源。

运行态 -> 就绪态：时间片用完，退出运行态；或者在可剥夺的操作系统中，被优先级更高的进程剥夺执行权。

运行态 -> 阻塞态：进程请求某项资源（I/O或者用户交互），进程以系统调用的形式请求操作系统服务。

阻塞态 -> 就绪态：进程等待的时间到来或者资源获取。

进程从运行态到阻塞态是主动的行为，从阻塞态变成就绪态是被动的行为。

3.进程的组织

进程是一个独立的运行单位，也是系统进行资源分配和调度的基本单位。它包括程序段、相关数据段和PCB。

1.PCB

PCB:系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用PCB 来控制和管理进程，所以PCB 是系统感知进程存在的唯一标志；进程与 PCB 是一一对应的；通常进程队列是进程所对的 PCB 队列；操作系统通过 PCB 来感知进程的存在。

PCB保存了进程的基本信息，在进程的整个生命周期中，系统总是通过PCB对进程进行控制。PCB的内容包括：

进程描述信息：

进程标识符：标志各个进程，每个进程都有唯一的标识符。
用户标识符：进程归属的用户，主要为共享和保护服务。

进程控制和管理信息：

进程当前状态：描述进程的状态信息，作为处理机分配调度的依据。
进程优先级：描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机。

资源分配清单：说明内存地址空间或虚拟地址空间的状况，打开的文件列表和所使用的输入/输出信息。
处理机相关信息（处理机的上下文）：处理机中各寄存器的值。

在系统中，可以使用就绪队列/阻塞队列来管理PCB，也可以通过索引方式，将统一状态的进程组织在一个索引表（PCB表）中，索引表的项指向相应的PCB。

2.程序段

程序段是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可以被多个进程共享，也就是多个进程运行了同一个程序。

3.相关数据段

一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

4.进程控制

1.进程创建

进程可以由另一个进程创建，此时原来的进程成为父进程，新进程成为子进程，他会继承父进程所拥有的资源。子进程被撤销时，将归还其从父进程获得的资源；父进程被撤销时，也会撤销其所有的子进程。

操作系统中，创建一个进程的操作如下（创建原语）：

分配唯一的PID，申请空白PCB。若没有空白PCB，则创建失败。

为进程分配其运行所需要的资源。如果资源不足，将处于创建态，等待内存资源。

初始化PCB，主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。

若进程就绪队列能够接纳新进程，则将新进程纳入就绪队列，等待被调度运行。

操作系统中的PCB数量是有限的

进程通过Fork()创建。内核为子进程做一个父进程的上下文的拷贝(复制父进程的PCB 作为子进程的 PCB)，子进程与父进程共享子进程创建之前父进程所有的资源，父进程和子进程在不同的地址空间上运行。

父子进程具有独立的内存空间；父子进程资源的共享与分离：父进程中在fork之前创建的变量先继承，后分离，子进程继承了父进程的私有变量，作为自己的私有变量；fork 之后各自创建的变量完全分离；子进程继承了父进程的所有资源，其中包括父进程的这些私有变量，但继承以后互相不能访问。

2.进程终止

引起进程终止的事件有:

正常结束，表示进程的任务已经完成并准备退出运行
异常结束，运行时发生了某种异常事件使程序无法继续运行
外界干预，例如进程被kill

操作系统终止进程的操作如下（终止原语）：

根据被终止进程的标识符，查出其PCB，并从中读出进程状态

若被终止进程处于执行状态，立即终止执行，将处理机资源分配给其他进程

若该进程还有子孙进程，则将所有的子孙进程终止

将该进程的全部资源归还给其父进程或者操作系统

将该PCB从所在队列中删除

3.进程阻塞和唤醒

进程在等待资源分配或事件响应时会进入阻塞态。阻塞原语如下：

找到要被阻塞进程的PCB

若该进程为运行态，保护现场，转为阻塞态停止运行

将该PCB插入相应的等待队列，将处理机资源调度给其他进程

唤醒原语如下：

在该事件的等待队列中找到相应的PCB

将其从等待队列中移出，设置其状态为就绪态

将PCB插入就绪队列，等待分配处理机资源

5.进程通信

进程通信是指进程之间的信息交换，PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。主要包括共享存储、消息传递和管道通信三种。

1.共享存储

在通信的进程之间有一块可直接访问的共享空间，对这个共享空间进行读写操作实现进程之间的信息交换。在进行读写操作时，需要使用同步互斥工具（例如P、V操作）以控制对该空间的访问。

共享存储又分为两种，低级方式的共享是基于数据结构的共享；高级方式的共享是基于存储区的共享。操作系统只负责提供可共享使用的存储空间和同步互斥工具，数据交换由用户自己实现。

进程空间一般都是独立的，因此这种共享一般需要特殊的系统调用来实现。

2.消息传递

基于消息传递的系统，进程间的数据交换以格式化的消息为单位。若通信的进程之间不存在可以直接访问的共享空间，则必须使用操作系统提供的消息传递方式进行数据交换，是当前使用最广泛的进程间通信机制。消息传递方式也有以下分类：

直接通信方式：发送进程直接把消息发送给接受进程，并挂在接受进程的消息缓冲队列上，接受进程从消息缓冲队列中取得消息

间接通信方式：发送进程把消息发送给某个中间实体，接受进程从中间实体取得消息。这种中间实体一般称为信箱。

3.管道通信

管道通信是消息传递的一种特殊方式。管道是指连接一个读进程和一个写进程以实现他们之间通信的共享文件。为了协调双方通信，管道机制要求互斥、同步和确定对方存在的能力。空则可读，满则可写。

管道能够克服使用文件进行通信的两个问题：

限制管道的大小。

读进程也可能工作的比写进程快。

因此，管道的通信是半双工通信。

6.线程

引入线程的原因：进程时空开销大、通信代价大、不能很好的利用多处理器系统、不适合并行计算和分布计算的要求。

线程是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。

线程是进程中的一个实体，自己不拥有系统资源。引入线程后，进程只作为除CPU外的系统资源的分配单元，线程则作为处理机的分配单元。由于一个进程内有多个线程，若线程的切换发生在一个进程内，则只需要很少的时空开销。

线程的优点：并发程度高、响应度高；易于调度，开销小；资源共享；多处理器体系结构的利用。

进程和线程的区别:

一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。

每当创建一个进程时，至少要同时为该进程创建一个线程，否则该进程无法被调度执行。

地址空问和其他资源（如打开文件)：进程间相互独立，同一进程的各线程间共享一一某进程内的线程在其他进程不可见。

通信：进程间通信采用 IPC，线程间可以直接读写进程的数据段（如全局变量）来进行通信；所有线程可共享进程的主存，不需要特殊的通信机制。

调度：线程上下文切换比进程上下文切换要快得多。

OS中引入进程和线程的目的：

进程：使多个程序并发执行，以便改善资源使用率和提高系统效率。

线程：减少程序并发执行时所付出的时空开销，并发性更好。

7.多线程模型

多对一模型：多个用户线程映射到一个内核线程。

一对一模型：每个用户线程映射到一个内核线程，当一个线程阻塞时其他线程可以继续执行。

多对多模型：可以创建任意多的必要用户线程，且相应内核线程能在多处理器系统中并发执行；一个线程阻塞时，另一个线程可以继续执行。

8.线程池

在进程建立时就创建若干线程，将这些线程放在一个“池”中等待工作。当服务器接收到一个请求时，就唤醒池中一个线程，并将要处理的请求传递给它；一旦线程完成了任务，它会返回到池中再等待其它的工作；如果池中没有可用的线程，服务器就会一直等待，指导有空闲线程为止。

优点：用现有线程处理请求通常臂等待创建新线程快；线程池限定了任何时候可存在线程的数量。

2.进程状态转换图(重点)

1.三种基本状态的转换

2.五种状态的转换

（1）创建状态：①进程申请一个空白PCB；②向PCB中填写用于控制和管理进程的信息；③为该进程分配运行所需要的的资源；④将该进程转入就绪状态并插入就绪队列中
（2）终止状态：①等待操作系统进行善后处理（操作系统保留该进程的信息供其他的进程提取）；②将该进程的PCB清零，北京将PCB控件返还系统

3.状态转换图

3.调度程序

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行

如上图所示，进程调度有三个层次：

高级调度（作业调度）：按照一定的原则从外存上处于后备队列的作业中挑选一个（或多个），给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利。简言之，作业调度就是内存与辅存之问的调度。对于每个作业只调入一次、调出一次。

中级调度（内存调度）：引入中级调度的目的是提高内存利用率和系统吞吐量。为此，将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。中级调度实际上是存储器管理中的对换功能。

低级调度（进程调度）：按按照某种算法从就绪队列中选取一个进程，将处理机分配给它。进程调度是最基本的一种调度，在各种操作系统中都必须配置这级调度。进程调度的频率很高，一般几十毫秒一次。

调度程序的功能有：

保存现场

选择进程

完成上下文切换

调度常用的评价标准有：

CPU利用率

系统吞吐量：表示单位时间内 CPU 完成作业的数量。

周转时间：指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队在处理机上运行及输入/输出操作所花费时间的总和。周转时间的计算方法如下：周转时间 = 作业完成时间 - 作业提交时间

等待时间：指进程处于等处理机的时间之和，等待时间越长，用户满意度越低。

响应时间：指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。

上面的指标中：

面向用户的：响应时间、周转时间、优先级
面向系统的：吞吐量、CPU利用率、公平、资源的平衡使用、系统开销

在操作系统中，用于调度和分派 CPU 的组件称为调度程序，它通常由三部分组成，如下图：

主要包含一下部分：

排队器。将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列中。

分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU 分配给新进程。

上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的 CPU 现场信息装入处理机的各个相应寄存器。

在一些情况下，进程不会进行调度与切换，主要是：

处理中断的过程中

进程在操作系统内核临界区中

其他需要完全屏蔽中断的原子操作中

在上下文切换时，需要执行大量 load 和store指令，以保存寄存器的内容，因此会花费较多时间。现在已有硬件实现的方法来减少上下文切换时间，通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前奇存器组即可。

对于通常的进程而言，其创建、撤销及要求由系统设备完成的 I/O 操作，都是利用系统调用而进入内核，再由内核中的相应处理程序子以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

上下文切换实质上是处理机从一个进程的运行转到另一个进程的运行，这个过程发生了环境的实质性改变。其切换流程为：

挂起进程，保存CPU上下文，例如PC和其他寄存器

更新PCB信息（进程状态等）

把进程的PCB移入相应的队列

选择另一个进程，并更新其PCB

跳转到新进程PCB中的PC所指位置继续执行

恢复处理机上下文

调度和切换的区别：调度是指決定资源分配给哪个进程的行为，是一种决策行为；切换是指实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。

第四章

1.用户级线程和内核级线程的定义和比较

线程的实现可以分为两类：用户级线程（User-Level Thread，ULT)和内核级线程（Kernel-Level Thread，KLT)。

1.用户级线程:由应用程序通过线程库实现。

线程库：应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程，无需内核支持。

特点：

内核不了解用户线程的存在；

用户线程切换不需要内校特权；

速度快。线程的创建和调度由应用软件内部进行，无需用户态/核心态切换，所以速度特别快。

优点：

线程切换不调用核心

调度是应用程序特定的：可以选择最好的算法

ULT 可运行在任何操作系统上（只需要线程库）

2.内核级线程

有关线程的所有管理工作都在OS内核完成，应用程序部分没有线程管理的代码，只有一个到内核线程的 API 线程切换由内核完成；内核维护进程和线程的上下文信息。

优点：

一个线程发起系统调用而阻塞，不会影响其它线程的运行，内核可以继续调度同一个进程中的另一个线程

内核可以将同一进程中的多个线程调度到多个处理器上。

缺点：

由于有内核的参与，需要额外开销

线程之问的切换需要内核的模式切换。

第五章

1.调度算法(非常重要，应知必会)

[FCFS、SJF、抢占式SJF、优先级、RR、最高响应比、多级队列]

FCFS（先来先服务）：可以用于作业调度和进程调度。属于不可剥夺算法。算法简单，效率低；对长作业有利，短作业不利；有利于CPU繁忙，不利于IO繁忙。

从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略，但它常被结合在其他调度策略中使用。

SJF/SPF（短作业/进程优先）：选择一个估计运行时间最短的作业/进程。对长作业不利，可能导致长作业陷入饥饿；未完全考虑作业的紧迫程度；不一定能真正做到短作业优先。

具有最少的平均等待时间和平均周转时间。

优先级调度算法：根据是否抢占正在进行的进程可以分为非抢占式优先级调度算法和抢占式优先级调度算法；根据进程创建后其优先级能否改变可以分为静态优先级和动态优先级（依据进程占有CPU时间的长短、就绪进程等待CPU时间的长短调整）。一般来说，进程优先级可以按照：

系统进程 > 用户进程
交互型进程 > 非交互型进程
I/O型进程 > 计算型进程

高响应比优先调度算法：主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

可以看出：

等待时间一样，要求服务时间越短响应比越高，有利于短作业，类似SJF

要求服务时间相同，等待时间越长响应比越高，类似FCFS

对于长作业，克服了饥饿现象

时间片轮转调度算法：主要用于分时系统。

在这种算法中，系统将所有就绪进程按 FCFS 策略排成一个就绪队列，调度程序总是选择就绪队列中的第一个进程执行，但仅能运行一个时间片，如 50ms。在使用完一个时间片后，即使进程并未运行完成，它也必须释放出(被剥夺)处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。
对于时间片轮转调度算法来讲，时间片的大小是比较敏感的。时间片的大小通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

多级队列调度算法：前述的各种调度算法，由于系统中仅设置一个进程的就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。在多处理机系统中，这种单一调度策略实现机制的缺点更为突出，多级队列调度算法能在一定程度上弥补这一缺点。

最短剩余时间优先调度算法：

多级反馈队列调度算法（最牛逼的）：多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统日标。其基本实现思想如下：

设置多个就绪队列，并赋予不同的优先级。

赋予各个队列不同的时间片，优先级越高时间片越小。

每个队列采用FCFS策略。

按队列优先级调度。

2.抢占式调度和非抢占式调度

进程调度方式：当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理时的处理机分配。有两种方式：

非抢占式调度（非剥夺方式）：非抢占调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统

抢占调度（剥夺方式）：抢占调度方式对提高系统吞吐率和响应效率都有明显的好处。但“抢占”不是一种任意性行为，必须遊循一定的原则，主要有优先权、短进程优先和时间片原则等。

第六章

1.临界区和信号量的定义

1.临界资源：一次仅允许一个进程使用的资源称为临界资源。

对临界资源的访问可以分成四个部分：

进入区：检查能否进入临界区，若能进入置一个标志防止其他进程进入临界区。

临界区（临界段）

退出区：清除标志。

剩余区。

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待。

有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。

让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

2.信号量

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语 wait(S)和 signal(S)访问，也可记为 “P操作〞和“V操作”。原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。信号量的实现有两种：

整型信号量：会存在忙等的状态。实现示例：

记录型信号量：需要一个额外的进程链表，链接所有等待该资源的进程。实现示例：

2.同步和互斥的定义

进程之间的关系存在两种制约：

同步：同步亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。(等待同步)

互斥：互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。(唯一性维持)

3.信号量如何处理同步互斥问题

1.生产者-消费者问题

适合解决描述了“缓冲区”的题目，解决的关键一是适当使用互斥锁；二是使用empty和full这样成对的信号量来进行协作。

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为1的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析:

关系分析。生产者和消贵者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。

整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步 PV 操作的位置。

信号量设置。信号量 mutex 作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1：信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为0。信号量 empty 用于记录当前缓冲池中的“空” 缓冲区数，初值为n。

代码描述:

一个更为复杂的问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果：仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析：这里的关系要稍复杂一些。由每次只能向其中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。father()和 dauthger()、mother()和 son()必须连续执行，正因为如此,也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即 V(plate)操作。

代码描述:

2.读者-写者问题

读者-写者问题有一个关键的特征”共同读”,即有一个互斥访问的计数器 count，因此遇到一个不太好解决的同步互斥问题时，要想一想用互斥访问的计数器 count 能否解决问题。

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：

①允许多个读者可以同时对文件执行读操作

②只允许一个写者往文件中写信息

③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让己有的读者和写者全部退出。

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到己在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的 writer()和 reader()函数中各增加一对 PV 操作，就可以得到写进程优先的解决程序：

3.哲学家就餐问题

问题描述：一张圆桌边上坐着 5 名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子己在他人手上，则需要等待。 饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

防止死锁发生(都拿同一边,等另一边)，可对哲学家进程施加一些限制条件，比如至多允许 4 名哲学家同时进餐(预先静态分配,破坏请求并保持)；仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子(暂时释放,破坏不释放条件)：对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反(顺序资源分配,破坏循环等待)。采用第二种方法，可以这样实现：

第七章

1.死锁定义

死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

死锁产生的可能原因有：

系统资源的竞争

进程推进顺序非法

2.死锁产生的条件

产生死锁的必要条件有：

互斥条件

不剥夺条件:指进程已经获得的资源在未使用完之前，不能被强行剥夺，只能由进程自己释放。即进程获得的资源只能由自己释放，而不能被其他进程抢占。

请求并保持条件:指进程在请求资源时可以保持已经获得的资源不释放。换句话说，一个进程可以请求新的资源，同时保持它已经占有的资源不被其他进程抢占。

循环等待条件:指系统中若干进程形成一种头尾相接的循环等待资源关系，每个进程都在等待下一个进程所占有的资源。这种情况下，每个进程都在等待其他进程释放资源，从而导致循环等待的状态。

3.死锁避免/死锁预防

死锁的处理策略有三种：

死锁预防

避免死锁

死锁的检测与解除

预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低：避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

1.死锁预防

预防死锁只需破坏导致死锁的四种情况即可：

破坏互斥条件：不太可行

破坏不剥夺条件：暂时释放已经保持的资源。常用于状态易于保存和恢复的资源，例如CPU的寄存器和内存资源。

破坏请求并保持条件：采用预先静态分配的方法。

破坏循环等待条件：采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源 R，则该进程在以后的资源申请中就只能申请编号大于R的资源。

2.死锁避免

定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不子分配，否则予以分配。

不需像死锁预防那样，事先采取限制措施破坏产生死锁的必要条件；在资源的动态分配过程中，采用某种策略防止系统进入不安全状态，从而避免发生死锁。

安全状态：系统能按某种进程推进顺序为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称该顺序为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。

3.死锁恢复

将死锁恢复的方法有：

进程终止：终止所有的死锁进程。OS中常用方法；一次只终止一个进程直到取消死锁循环为止一基于某种最小代价原则。

资源抢占：逐步从进程中强占资源给其它进程使用，直到死锁环被打破为止。

4.银行家算法

银行家算法是最著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家货款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程己占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

5.资源分配图

按以下规则绘制资源分配图：

圆圈代表进程，方框代表资源

方框中的点表示一个资源

分配边：从资源节点指向进程节点，表示资源已经分配。

请求边：从进程指向资源节点，表示正处于阻塞状态，等待资源变为可用。

化简方法：假设某个RAG 中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简；当 Pi 有请求边时，首先将其请求边变成分配边(即满足 Pi 的资源请求），而一旦 Pi 的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时 Pi 只有分配边，删去这些分配边（实际上相当于消去了 Pi 的所有请求边和分配边），使Pi 成为孤立结点。

死锁条件：有向图形成环路

注意:化简后不能保证所有进程都是孤立节点

第八章

内存管理的主要功能有：

内存空间的分配与回收：由操作系统完成内存空间的分配管理

地址转换：进行逻辑地址与内存中物理地址的转换

内存空间的补充：虚拟存储技术或自动覆盖技术-

内存共享：允许多个进程访问内存的同一部分

存储保护：保证各道程序工作在各自的存储空间里。

1.逻辑地址和物理地址绑定

1.地址重定位：将逻辑地址转变为物理地址的过程。

静态地址重定位：在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址-都改成实际的物理内存地址。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。程序的存储空间只能是连续的一片区域不能再移动。

动态地址重定位：在程序运行过程中要访问内存数据时再进行地址变换，即在逐条指令执行时完成地址映射。OS 可以将一个程序分散存放于不连续的内存空间，可以移动程序。

2.覆盖与交换

覆盖：在任何时候只在内存中保留所需的指令和数据：当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间。

特点：覆盖不需要 OS 提供特殊的支持，但程序员必须适当地设计和编写覆盖结构。

交换：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出），而将外存中由阻塞变为就绪的进程的地址空问读入到内存中，并将该进程送到就绪队列（换入）。交换单位为整个进程的地址空间。

与覆盖的比较：与覆盖技术相比，交换技术不要求用户给出程序段之间的迎辑覆盖结构。

交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。

2.内存分配方式

不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像。一个进程的内存映像一般有几个要素：

代码段：即程序的二进制代码，代码段是只读的，可以被多个进程共享。

数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。

进程控制块 (PCB)：存放在系统区。操作系统通过 PCB 来控制和管理进程。

堆：用于存放动态分配的内存。通过调用 malloc 两数动态地向高地址分配空间。

栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长。每次函数调用时，都会在栈上创建一个新的栈帧，用于存储函数的参数、局部变量和返回地址等信息。

代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样。当调用像malloc 和 free 这样的一标准库的数时，堆可以在运行时动态地扩展和收缩。用户栈在程序运行期间也可以动态地扩展和收缩，每次调用一个两数，栈就会增长：从一个的数返回时，栈就会收缩。

1.连续分配

连续分配方式是指为一个用户程序分配一个连续的内存空间，皆如某用户需要 100MB 的内存空间，连续分配方式就在内存空问中为用户分配一块连续的 100MB 空间。连续分配方式主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配:

内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间由该程序独占。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。在划分分区时有两种不同的方法。

分区大小相等。程序太小会造成浪费，程序太大又无法装入，缺乏灵活性。
分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区。

为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包括每个分区的始址、大小及状态。

这种方式存在两个问题：一是程序可能太大而放不进任何一个分区，这时就需要采用覆盖技术来使用内存空间；二是当程序小于固定分区大小时，也要占用一个完整的内存分区，这样分区内部就存在空间浪费，这种现象称为内部碎片。

动态分区分配

又称可变分区分配，它是在进程装入内存时，根据进程的实际需要，动态地为之分配内存，并使分区的大小正好适合进程的需要。因此，系统中分区的大小和数目是可变的。

动态分区在开始时是很好的，但随着时间的推移，内存中会产生越来越多小的内存块，内存的利用率也随之下降。这些小的内存块称为外部碎片，它存在于所有分区的外部，这与固定分区中的内部碎片正好相对。

克服外部碎片可以通过压缩技术来解决，即操作系统不时地对进程进行移动和整理。但这需要动态重定位寄存器的支持，且相对费时。

在进程装入或换入主存时，若内存中有多个足够大的空闲块，则操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略。考虑以下几种算法：

首次适应（First Fit）算法。空闲分区以地址递增的次序链接。分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给作业。最简单，通常也是最好最快的，但会使得内存的低地址部分出现很多小的空闲分区，导致查找时的开销。

临近匹配（Next Fit）算法。又称循环首次适应算法，由首次适应算法演变而成。不同之处是，分配内存时从上次查找结束的位置开始继续查找。通常比首次适应要差，常常在内存空间的尾部分裂成小碎片。

最佳匹配（Best Fit）算法。空闲分区按容量递增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业，避免“大材小用”。

最差匹配（Worst Fit）算法。空闲分区以容量递减的次序链接，找到第一个能满足要求的，即最大的分区，从中分割一部分存储空间给作业。

2.分页分配:见下

3.分页管理、分页机制、单级页表和多级页表及其设计方案、快表机制(非常重要，应知必会）

1.分页分配

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。

我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想：把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

基本概念：

页面和页面大小：进程中的块称为页或页面(Page），内存中的块称为页框或页帧 (Page Frame)，外存也以同样的单位进行划分，直接称为块或盘块(Block）。为方便地址转换，页面大小应是2的整数幂，同时页面大小应该适中。

地址结构：前一部分为页号，后一部分为偏移量。地址结构决定了寻址空间的大小。

页表：为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中。页表一般要求连续内存,因此使用在逻辑地址结构中偏移量表示在页框内的不同位置,而在页表内只寻找某一块连续内存(页框)

页表是由页表项组成的，初学者容易混滑页表项与地址结构，页表项与地址都由两部分构成，而且第一部分都是页号，但页表项的第二部分是物理内存中的块号(页框号)，而地址的第二部分是页内偏移；页表项的第二部分与地址的第二部分共同组成物理地址。5

地址变换机构的任务是将逻辑地址转换为内存中的物理地址，地址变换是借助于页表实现的。

在系统中通常设置一个页表寄存器（PTR），存放页表在内存的起始地址 F 和页表长度L。

2.快表(TLB)

单级页表场景下，每次访存需要两次（读页表获得物理块号一次，访问数据一次）。为了提高效率引入TLB（快表）提高效率。

TLB全称（Translation Lookaside Buffer，转换检测缓冲区）是一个内存管理单元，用于提高虚拟地址到逻辑地址的转换速度。TLB是一个小的、虚拟寻址的缓存(因此访问TLB不属于访存),每一行都保存由单个PTE(Page Table Entry即页表项）所组成的块。如果没有TLB，每次取数据都要两次访问内存，即查页表获得物理地址和取数据。TLB 快表，用来存放当前访问的若干页表项，与此对应。

3.多级页表

随着内存容量的扩大，页表变大，因页表要求连续内存，造成内存管理变得困难，采用多级页表，使得内层页表不必要连续。

如下图所示,一个进程的页表变为页目录,指向数个页表,便可以利用非连续空间(单个页表依旧指向连续空间)

4.总结

1.对于一般情况下的单页表结构,逻辑思路为:

进程中多个Page→每个Page存在一个页号唯一表示该Page→众多页号存储在页表中(页表在内存中),指向对应内存的块(页框)→根据逻辑地址前半部分”页号”查找页表获得页框(第一次访存)→根据逻辑地址后半部分”页内偏移量”查找页框内具体位置(第二次访存),指向具体的物理地址

2.对于多级页表结构,逻辑思路为:

进程中多个Page→每个Page存在一个页号唯一表示该Page→部分页号位于不同的非连续内存中→每一个非连续内存有一个页表→多个页表地址组成页目录(页目录地址位于寄存器中)→查找页目录→查找页表→查找具体地址

3.对于TLB快表结构,逻辑思路为:

存在数个页表(页表前逻辑不变)→将常用页号存入TLB中(TLB位于缓存)→先查快表,命中则直接获得页号对应页框号→若未命中,查找页表,并把页号存入快表中→在页框内查找

第九章

1.局部性原理与缺页中断

1.虚拟内存系统

前面讨论的各种内存管理策略都是为了同时将多个进程保存在内存中，以便允许进行多道程序设计。它们都具有以下两个共同的特征：

一次性。作业必须一次性全部装入内存后，才能开始运行。这会导致两种情况：1）当作业很大而不能全部被装入内存时，将使该作业无法运行；2）当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。

驻留性。作业被裝入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程会因等待I/O而被阻塞，可能处于长期等待状态。

由以上分析可知，许多在程序运行中不用或暂时不用的程序(数据)占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。

从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，又适用于数据结构，表现在两个方面：

时间局部性。程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。

空间局部性。一旦程序访问了某个存储单元，在不久后，其附近的存储单元也將被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式族聚存储的。

时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。

虚拟内存技术实际上建立了 “内存-外存”的两级存储器结构，利用局部性原理实现高速缓存。基于局部性原理，在程序装入时，仅须将程序当前要运行的少数页面或段先装入内存，而将其余部分暂留在外存，便可启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统將内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虛拟存储器。

虚拟存储器有以下特征：

多次性。是指无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚未调入的那部分程序时，再将它调入。多次性是虚拟存储器最重要的特征。

对换性。是指无须在作业运行时一直常驻内存，在进程运行期间，允许将那些暂不使用的程序和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存 (换进）。正是由于对换性，才使得虚拟存储器得以正常运行。

虚拟性。是指从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量。这是虛拟存储器所表现出的最重要特征，也是实现虛拟存储器的最重要目标。

虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有三种：

请求分页存储管理。

请求分段存储管理。

请求段页式存储管理。

无论哪种方式都需要一定的硬件支持：

一定容量的内存和外存

页表机制（段表机制）作为主要的数据结构

中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。

地址变换机构，逻辑地址到物理地址的变换

2.缺页中断

在虚拟内存不断的在内存和外存间来回进出调用的时候，难免会出现(应该说经常出现）访问已经映射在虚拟地址空间中的页面，但是该页面还未调入物理内存中，出现“缺页“情况。

有下列几种情况的缺页：

软性缺页：即相关页已经加载进内存中，但是其物理地址并未向MMU注册；解决方法只需将物理地址注册即可

硬性缺页：顾名思义，实打实的缺少页面，未加载进内存的情况；解决方法便是将页面加载进物理内存，寻找空页框，读入数据，注册…；当硬性缺页过于频繁的发生时，便是系统颠簸

无效：访问的虚拟地址不存在于虚拟地址空间的时候，则发生无效页缺失；解决方式一般与操作系统有关（是否向程序报告），若程序并未有所响应，默认处理方式通常为转出内存，终止进程，向用户报告等。

3.请求分页管理方式

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虛拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存中时，再通过调页功能将其调入，同时还可通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址机构。

请求分页机制下必须面临如何发现和处理页面不在内存中的情况，这需要向页表项中添加四个字段：

状态位P：用于指示该页是否己调入内存，供程序访问时参考。

访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时问未被访问，供置换算法换出页面时参考。

修改位M：标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存。

外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。缺页中断作为中断，同样要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：

在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部异常。

一条指令在执行期间，可能产生多次缺页中断。

缺页率 = 缺页次数/内存访问此次数

3.页框分配

操作系统必须决定读取多少页也就是给进程分配几个页框，一个进程分配的物理页框的集合就是这个进程的驻留集。需要考虑以下几点：

分配给一个进程的页框越少，驻留在主存中的进程就越多，从而可提高 CPU 的利用率。

若一个进程在主存中的页面过少，则尽管有局部性原理，缺页率仍相对较高。

若分配的页框过多，则由于局部性原理，对该进程的缺页率没有太明显的影响。

请求分页系统有固定分配和可变分配两种内存分配策略，置换时有全局置换和局部置换两种策略，因此能组合出三种策略：

固定分配局部置换：为每个进程分配一定数目的物理块，在进程运行期问都不改变。所谓局部置换，是指如果进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略时，难以确定应为每个进程分配的物理块数目：太少会频繁出现缺页中断，太多又会降低CPU和其他资源的利用率。

可变分配全局置换：先为每个进程分配一定数目的物理块，在进程运行期间可根据情况适当地增加或减少。所谓全局置换，是指如果进程在运行中发生缺页，系统从空闲物理块队列中取出一块分配给该进程，并将所缺页调入。这种方法比固定分配局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。

可变分配局部置换：为每个进程分配一定数目的物埋块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度：反之，若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块，但不能引(起其缺页率的明显增加。这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牲是值得的。

采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法：

平均分配算法

按比例分配算法

优先权分配算法

为确定系统将进程运行时所缺的页面调入内存的时机，可采取以下两种调页策略：

预调页策略

请求调页策略

请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘 IO 速度比文件区的更快。这样，当发生缺页请求时，系统从何处將缺页调入内存就分为三种情况：

系统有足够的对换区空间

系统缺少足够的对换区空间

UNIX方式

2.掌握几种替换页选择方法：最佳算法、先进先出、最近最久未使用，能给出页面替换序列和次数(非常重要，应知必会）

1.页面置换算法

进程运行时，若其访问的页面不在内存中而需将其调入，但内存己无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或以后较长时间内不会再访问的页面先调出。

常见的置换算法有四种：

最佳（OPT）置换算法：最佳置换算法选择的被淘汰页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。然而，由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。但可利用该算法去评价其他算法。

先进先出（FIFO）置换算法：优先淘汰最早进入内存的页面，即海汰在内存中驻留时间最久的页面。该算法实现简单，只需把己调入内存的页面根据先后次序链接成队列，设置一个指针总是指向最老的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

FIFO 算法还会产生所分配的物理块数增大而页故障数不減反增的异常现象，称为 Belady 异常。只有FIFO 算法可能出现 Belady 异常，LRU 和 OPT 算法永远不会出现Belady 异常。

最近最久未使用（LRU）算法：选择最近最长时问未访问过的页面子以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

LRU 算法的性能较好，但需要寄存器和栈的硬件支持。LRU 是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现 Belady 异常。FIFO 算法基于队列实现，不是堆栈类算法。

时钟（CLOCK）/二次机会算法：LRU 算法的性能接近 OPT 算法，但实现起来的开销大。因此，操作系统的设计者尝试了很多算法，试图用比较小的开销接近 LRU 算法的性能，这类算法都是 CLOCK 算法的变体。

简单的CLOCK算法
改进型CLOCK置换算法

需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写），则把该位置置1。把各个页面组织形成环形链表（类似钟表面），把指针指向最老的页面（最先进来）。当发生一个缺页中断时，考察指针所指向的最老页面。若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

增强二次机会算法：将引用位和修改位作为一组有序对来改进第二次机会算法：

组合	含义
(0, 0)	近期既没有被使用过，也没有被修改过，是最佳的页面置换。
(0, 1)	近期没有被使用过但是被修改过的页面，是不太好的页面置换，因为需要将该页面写回磁盘。
(1, 0)	近期被使用过但是没有被修改的页面，可能很快会被再次使用。
(1, 1)	近期既被使用过又被修改过，可能很快会再次使用，并且置换时需要写回磁盘。

3.系统颠簸[现象描述、产生原因、解决办法]（非常重要，应知必会）

在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。

系统发生抖动的根本原因是，系统中同时运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统將所缺页面调入内存。这会使得在系统中排队等待页面调入/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生处理机的利用率急剧下降并趋于零的情况。

抖动是进程运行时出现的严重问题，必须采取相应的措施解决它。由于抖动的发生与系统为进程分配物理块的多少有关，于是又提出了关于进程工作集的概念。

工作集是指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。一般来说，工作集𝑊W可由时间𝑡t和工作集窗口大小ΔΔ来确定。实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口ΔΔ小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页，所以为了防止这种抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。

发生颠簸时如何处理——利用虚拟内存技术保留尽可能多的进程在内存中，或者选择合适的页面置换算法：

修改页面置换算法

正确的选择工作集大小

降低多道程序设计的程度

挂起该进程

内存映射文件

内存映射文件（Memory-Mapped Fies）与虚拟内存有些相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件IO操作，也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。

第十章

1.文件系统的定义及其基本概念

1.文件系统简介

文件系统：包含若干文件以及其属性说明、对文件进行操纵和管理的软件，以及系统向用户提供的使用文件的接口等的集合。文件系统是操作系统的一个重要组成部分。

2.文件共享

文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。现代操作系统实现的方法主要有两种：

基于索引结点的共享方式（硬链接）：在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件。

在这种共享方式中，诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点（即文件）上的用户目录项的数目。

利用符号链实现文件管理（软链接）：为使用户B能共享用户A的一个文件F，可以由系统创建一个 LINK 类型的新文件，也取名为F，并将该文件写入用户 B的目录中，以实现用户 B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名，当用户 B 要访问被链接的文件F且正要读 LINK 类新文件时，操作系统查看到要谈的文件是 LINK 类型，则根据该文件中的路径名去找到文件 F，然后对它进行读，从而实现用户B对文件F的共享。这样的链接方法被称为符号链接。261

在利用符号链方式实现文件共享时，只有文件主才拥有指向其奈引结点的指针。而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件主把一个共享文件删除后，若其他用产又试图通过符号链去访问它时，则会访问失败，于是将符号链删除，此时不会产生任何能啊。

3.文件基本操作（打开文件）

操作系统的系统调用一般提供以下基本操作：

创建文件：有两个步骤一是分配必要的外存空间，二是在目录中创建一个目录项。

写文件：

读文件：

重新定位文件（文件定位）

删除文件

截断文件

当用户对一个文件实施操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，大多数操作系统要求，在文件使用之前通过系统调用 open 被显式地打开。操作系统维护一个包含所有打开文件信息的表（打开文件表）。

所谓“打开”，是指调用 open 根据文件名搜索目录，将指明文件的属性（包括该文件在外存上的物理位置），从外存复制到内存打开文件表的一个表目中，并将该表目的编号(也称索引）返回给用户。当用户再次向系统发出文件操作请求时，可通过索引在打开文件表中查到文件信息，从而节省再次搜索目录的开销。当文件不再使用时，可利用系统调用 close 关闭它，操作系统将会从打开文件表中删除这一条目。

在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：每个进程表和整个系统表。每个进程表根据它打开的所有文件，表中存储的是进程对文件的使用信息。系统打开文件表包含文件相关信息，如文件在磁盘的位置、访问日期和大小。一旦有进程打开了一个文件，系统表就包含该文件的条目。当另一个进程执行调用open 时，只不过是在其进程打开表中增加一个条目，并指向系统表的相应条目。通常，系统打开文件表为每个文件关联一个打开计数器 (Open Count），以记录多少进程打开了该文件。每个关闭操作close 使count 递滅，当打开计数器为0时，表示该文件不再被使用，并且可从系统打开文件表中删除相应条目。

文件名不必是打开文件表的一部分，因为一旦完成对 FCB 在磁盘上的定位，系统就不再使用文件名。对于访问打开文件表的索引，UNIX 称之为文件描述符，而 Windows 称之为文件句柄。每个打开文件具有如下关联信息：

文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件屆性分开保存。

文件打开计数。计数器跟踪当前文件打开和关闭的数量。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。

文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息

访问权限。每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等)。该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的 UO 请求。

第十一章

1.FCB 定义以及FCB 与文件之间的关系

文件控制块(FCB）是用于存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB 的有序集合称为文件目录，一个FCB 就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB 并存放在文件目录中，称为目录项。

FCB主要包括以下信息：

基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。

存取控制信息，包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。

使用信息，如文件建立时间、上次修改时间等。

一个文件目录也被视为一个文件，称为目录文件。

文件目录通常存放在磁盘上，当文件很多时，文件目录会占用大量的盘块。在查找目录的过程中，要先将存放目录文件的第一个盘块中的目录调入内存，然后用给定的文件名逐一比较，若末找到指定文件，就还需要不断地将下一盘块中的目录项调入内存，逐一比较。

我们发现，在检索目录的过程中，只用到了文件名，仅当找到一个目录项（其中的文件名与要查找的文件名匹配〕时，才需从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需要调入内存。因此，有的系统（如 UNIX）便采用了文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称i结点(inode)。在文件目录中的每个目录项仅文件名和指向该文件所对应的i结点的指针构成。索引结点又可分为两类：

磁盘索引结点

内存索引结点

2.分配方法[连续分配、链接分配、索引分配，各种分配方法的优缺点]（重要）

1.文件的逻辑结构

文件的逻辑结构与存储介质特性无关，它实质上是文件的内部，数据逻辑上是如何组织起来的。根据逻辑结构文件可以分为：

无结构文件（流式文件）：无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累、保存，它是有序相关信息项的集合，以宇节(Byte）为单位。由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，因此这种文件形式对大多数应用不适用。但宇符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，如源程序文件、目标代码文件等。

有结构文件（记录式文件），可以分为以下几种：

顺序文件：文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储。顺序文件有串结构和顺序结构两种。

在对记录进行批量操作，即每次要该或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的。此外，对手顺序存储设备（如磁带），世只有顺序文件才能被存储并能有效地工作。在经常需要查找、修改、增加或删除单个记录的场合，顺序文件的性能也比较差。

索引文件：对于定长记录文件，可以通过计算位置直接访问到文件。但是对于变长文件，只能通过顺序查找，为此可以建立索引表，每个表项包括索引号、长度和指向变长记录的指针。

索引顺序文件：索引顺序文件是顺序文件和索引文件的结合。索引顺序文件将顺序文件中的所有记录分为若于组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。查找一条记录时，首先通过索引表找到其所在的组，然后在该组中使用顺序查找就能很快地找到记录。

直接文件/散列文件：给定记录的键值或通过散列西数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。

2.文件的物理结构

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配：

连续分配：连续分配方法要求每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。其优点是实现简单、存取速度快，但有很多缺点：

文件长度不宜动态增加

为了保持文件的有序性，删除和插入文件时需要移动相邻的文件。

反复增删文件后会产生外部碎片

难以确定一个文件所需要的大小，只适合保存长度固定的文件。

链接分配：链接分配是一种采用离散分配的方式。它消除了磁盘的外部碎片，提高了磁盘的利用率；可以动态地为文件分配盘块，因此无须事先知道文件的大小；对文件的插入、删除和修改也非常方便。链接分配又可分为隐式链接和显式链接两种形式：

隐式链接：目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都含有指向文件下一个盘块的指针，这些指针对用户是透明的。由于使用链表进行存储，因此其只适合顺序访问，随机访问效率很低。

通常，一个解决方案是使用簇（几个盘块）来分配以减少查找时间。

显式链接：显式链接是指把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表 (File Allocation Table， FAT)。每个表项中存放链接指针，即下一个盘块号。文件的第一个盘块号记录在目录项“物理地址”字段中，后续的盘块可通过查FAT找到。

不难看出，文件分配表 FAT 的表项与全部磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，可以用-2表示这个磁盘块是空闲的（当然也可指定为一3，-4)。因此，FAT 不仅记录了文件各块之间的先后链接关系，同时还标记了空闲的磁盘块，操作系统也可以通过 FAT 对文件存储空间进行管理。当某进程请求操作系统分配一个磁盘块时，操作系统只需从 FAT 中找到-2的表项，并将对应的磁盘块分配给进程即可。

链接分配也存在一些缺点：

（不使用FAT时）不能有效支持直接随机访问

FAT需要较大的内存空间（因为FAT会在系统启动时被载入内存）

索引分配：在打开某个文件时，其实只需要将该文件对应盘块的编号调入内存，不需要将整个FAT调入内存。因此，索引分配将每个文件所有的盘块号都集中在一起构成索引块（表）。每个文件都有自己的索引块，每个条目指向该文件的一个块。

索引分配能够有效解决随机访问等问题，但是索引块的大小设定是一个问题。过大会占用空间，过小无法保存大文件，为此有以下机制：

链接方案：链接多个索引块。
多层索引：分层索引。
混合索引：混合多种方式，也就是下面的混合索引分配。

混合索引分配：混合索引分配的思路是为了照顾不同规模的文件采用不同的索引方式。对于小文件，尽量将他们的盘块地址直接放入FCB，中大型文件使用层数更多的多层索引。UNIX采用了这种设计方式，其索引节点中有13个地址项：

直接地址：10个直接保存盘块号的位置，用于存放小文件。

假设每块4KB，共能存储40KB

一次间接地址：进行一次间接地址计算。

一块能存1024个地址，共能存储4MB文件

多次间接地址

可以进行二次间址和三次间址

3.空闲空间管理（重要）

1.文件系统布局

文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。文件系统可能包括如下信息：启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。

主要结构包括：

主引导记录（MBR）：位于磁盘的0号扇区，其后跟分区表。表中的一个分区被标记为活动分区，计算机启动后BIOS读入并执行MBR，MBR确定活动分区，然后读入第一块——引导块。

引导块：MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统。Windows 系统称之为分区引导扇区。

超级块：包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被载入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB 数量和FCB 指针等。

文件系统中空闲块的信息，可以使用位示图或指针链接的形式给出。后面也许跟的是一组i结点，每个文件对应一个结点，i结点说明了文件的方方面面。接着可能是根目录，它存放文件系统目录树的根部。最后，磁盛的其他部分存放了其他所有的目录和文件。

内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。这些结构的类型可能包括：

内存中的安装表：包含每个已安装文件系统分区的有关信息。

内存中的目录结构的缓存：最近访问目录的信息。

整个系统的打开文件表：包含每个打开文件的 FCB 副本及其他信息。

每个进程的打开文件表：包含一个指向整个系统的打开文件表中的适当条目的指针，以及其他信息。

基于逻辑文件系统进行调文件操作：

创建新的文件：应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式，它将为文件分配一个新的 FCB。然后，系统将相应的目录读入内存，使用新的文件名和 FCB 进行更新，并将它写回磁盘。

打开一个文件：系统调用open()将文件名传递给逻辑文件系统。调用open()首先搜索整个系统的打开文件表，以确定这个文件是否已被其他进程使用。如果己被使用，则在单个进程的打开文件表中创建一个条目，让其指向现有整个系统的打开文件表的相应条目。该算法在文件已打开吋，能节省大量开销。如果这个文件尚未打开，则根据给定文件名来搜索目录结构。部分目录结构通常缓存在内存中，以加快目录操作。找到文件后，它的 FCB 会复制到整个系统的打开文件表中。该表不但存储 FCB，而且跟踪打开该文件的进程的数量。然后，在单个进程的打开文件表中创建一个条目，并且通过指针将整个系统打开文件表的条目与其他域（如文件当前位置的指针和文件访问模式等）相连。调用open()返回的是一个指向单个进程的打开文件表中的适当条目的指针。以后，所有文件操作都通过该指针执行。一旦文件被打开，内核就不再使用文件名来访问文件，而使用文件描述符（ Windows 称之为文件句柄)。

关闭一个文件：当进程关闭一个文件时，就会删除单个进程打开文件表中的相应条目，整个系统的打开文件表的文件打开数量也会递减。当所有打开某个文件的用户都关闭该文件后，任何更新的元数据将复制到磁盘的目录结构屮，并且整个系统的打开文件表的对应条目也会被删除。

2.外存空闲空间管理

一个存储设备可以按整体用于文件系统，也可以细分。包含文件系统的分区通常称为卷（volume）。卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成 RAID 集：

在一个卷中，存放文件数据的空间（文件区）和 FCB 的空间（目录区）是分离的。卷在提供文件服务前，必须由对应的文件程序进行初姶化，划分好目录区和文件区，建立空闲空问管理表格及存放卷信息的超级块。文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。常用的方法有：

空闲表法：空闲表法属于连续分配方式，它与内存的动态分配方式类似，为每个文件分配一块连续的存储空问。系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法和最佳适应算法等。

空闲链表法：将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，分为两种形式：

空闲盘块链：以盘块为单位将空闲的盘块拉成一条链。
空闲盘区链：将空闲盘区拉成一条链，每个盘区除了指针以外还需要有用于指明本盘区大小的信息。

位示图法：位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当其值为 “0”时，表示对应的盘块空闲；为“1〞时，表示已分配。这样，一个m*n 位组成的位示图就可用来表示m*n个盘块的使用情况：

成组链接法：在UNIX 系统中采用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法，它具有上述两种方法的优点，克服了两种方法均有的表太长的缺点。

在这个图中，蓝色框表示一组磁盘块，红色的为一组磁盘块中的第一块。这样的第一个磁盘块会有三部分，首先是记录下一组的磁盘块数，一个用来保存下一组块地址的栈以及空余不用的区域。

第十二章

1.RAID

RAID (Redundant Arrays of Independent Disks，独立磁盘冗余阵列）：

解释1：其基本思想就是把多个相对便宜的硬盘组合超来，成为一个硬盘阵列组，使性能达到甚至超过一个价格昂贵、容量巨大的硬盘。根据选择的版本不同，RAID 比单颗硬盘有以下一个或多个方面的好处：增强数据集成度，增强容错功能，增加处理量或容量。另外，磁盘阵列对于计算机来说，看起来就像一个单独的硬盘或逻辑存储单元。简单来说， RAID 把多个硬盘组合成为一个逻辑扇区，因此，操作系统只会把它当作一个硬盘。RAID 常被用在服务器计算机上，并且常使用完全相同的硬盘作为组合。

解释2：独立磁盘冗余阵列，简称磁盘阵列。把一个或多个独立的磁盘块按照某种方式组合起来形成一个磁盘组，从而提供比单个磁盘更高的存储性能和数据备份技术。通过引入冗余来提高数据可靠性，存储在正常情况下不需要的信息，以便在数据故障时修复数据。通过并行来提高性能，将数据按位或按块拆分到多张磁盘，从而达到并行读取数据，提高效率。

解释3：独立磁盘冗余阵列，简称磁盘阵列，是把一块或者多块独立的物理磁盘按照不同的方式组合起来形成一个硬盘组，从而提供比单个硬盘更高的存储性能和额外的数据备份等功能。通过引入冗余来提高数据可靠性，存储正常情况下不需要的数据，以便在数据故障是修复数据。

2.磁盘调度算法 [PCFS、SSTF、SCAN 、C-SCAN、 LOOK、C-LOOK]（非常重要，应知必会）

1.磁盘调度

磁盘初始化：一个新的磁盘只是一个磁性记录材料的空白盘。在磁盘可以存储数据之前，必须将它分成扇区，以便磁盘控制器能够进行读写操作，这个过程称为低级格式化(或称物理格式化）。低级格式化为每个扇区使用特殊的数据结构，填充磁盘。每个扇区的数据结构通常由头部、数据区域(通常为 512B 大小）和尾部组成。头部和尾部包含了一些磁盘控制器的使用信息。

分区：

引导块：计算机启动时需要运行一个初始化程序（自举程序），它初始化 CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，自举程序找到磁盘上的操作系统内核，将它加载到内存，并转到起始地址，从而开始操作系统的运行。自举程序通常存放在 ROM 中，为了避免改变自举代码而需要改变 ROM 硬件的问题，通常只在 ROM 中保留很小的自举装入程序，而将完整功能的引导程序保存在磁盘的启动块上，启动块位于磁盘的固定位置。具有启动分区的磁盘称为启动磁盘或系统磁盘。

2.磁盘调度算法

磁盘的调度算法有：

FCFS/FIFO：先来先服务算法。这种算法的思想比较容易理解。假设当前磁道在某一位置，依次处理服务队列里的每一个磁道，这样做的优点是处理起来比较简单，但缺点是磁头移动的距离和平均移动距离会很大。

最短寻找时间优先（SSTF）：这种算法的本质是利用贪心算法来实现，假设当前磁道在某一位置，接下来处理的是距离当前磁道最近的磁道号，处理完成之后再处理离这个磁道号最近的磁道号，直到所有的磁道号都服务完了程序结束。

这样做的优点是性能会优于FCFS算法，但是会产生距离。当前磁道较远的磁道号长期得不到服务，也就是“饥饿”现象，因为要求访问的服务的序列号是动态产生的，即各个应用程序可能不断地提出访问不同的磁道号的请求。

扫描（SCAN）/LOOK算法：先按照一个方向(比如从外向内扫描），扫描的过程中依次访问要求服务的序列。当扫描到最里层的一个服务序列时反向扫描，这里要注意，假设最里层为0号磁道，最里面的一个要求服务的序列是5号，访问完5号之后，就反向了，不需要再往里扫。结合电梯过程更好理解，在电梯往下接人的时候，明知道最下面一层是没有人的，它是不会再往下走的。不访问到磁盘的最尽头扇区时就是LOOK算法。

循环扫描（C-SCAN）/C-LOOK算法：CSCAN算法，循环扫描算法，来看一下上一种算法，有什么问题。仔细一看，我们会发现，在扫描到最里面的要求服务的序列时，接着会反向，在接下来的很大一部分时问里，应该是没有要求服务的磁道号的，因为之前已经访问过了。什么意思，就是说从初始磁道号到最里层的一个磁道号之问的所有序列都已经访问过了，所以SCAN会增加等待的时问。为了解决这样的情况，CSCAN算法的思想是，访问完最里面一个要求服务的序列之后，立即回到最外层访问磁道。也就是始终保持一个方向。故也称之为单向扫描调度算法。从最里面的一个磁道立即回到最外层欲访问的磁道，这步的距离是两者磁道号差的绝对值。

第十三章

1.I/O 控制方式的轮询方式，中断方式，DMA 方式

I/O控制方式有三种：

程序直接控制方式(轮询)

中断驱动方式

DMA方式

其中DMA方式是最好的方式，它的特点为：

基本单位是数据块

所传送的数据是从设备直接送入内存的。

仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在 DMA 控制器的控制下完成的

I/O软件采用层次结构设计，包括以下层次：

用户层I/O软件：提供用户层的操作函数。

设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备的保护及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空问。在应用程序中，使用逻辑设备名来请求某类涉别，系统执行时映射成物理设备名使用，这样的好处是：

增加设备分配的灵活性

易于实现I/O重定向

为了实现设备独立性（设备无关性），需要在驱动程序之上提供一层设备独立性软件。负责1）执行所有设备的共有操作2）向用户层提供统一接口。

设备驱动程序：与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序。通常，每类设备配置一个设备驱动程序，它是I/O进程与设各控制器之间的通信程序，常以进程形式存在。

中断处理程序：用于保存被中断进程的CPU环境等。

当执行一个文件操作时，经历的过程为：

当用户要读取某设备的内容时，通过操作系统提供的read 命令接口，这就经过了用户层。

操作系统提供给用户使用的接口，一般是统一的通用接口，也就是几乎每个设备都可以响应的统一命令，如read 命令，用户发出的read 命令，首先经过设备独立层进行解析，然后交往下层。

接下来，不同类型的设备对read 命令的行为会有所不同，如磁盘接收 read 命令后的行为与打印机接收 read 命令后的行为是不同的。因此，需要针对不同的设备，把read 命令解析成不同的指令，这就经过了设备驱动层。

命令解析完毕后，需要中断正在运行的进程，转而执行 read 命令，这就需要中断处理程序。

最后，命令真正抵达硬件设备，硬件设备的控制器按照上层传达的命令操控硬件设备，完成相应的功能。

I/O系统与高层的接口中，由于设备类型不同又区分为若干接口：

字符设备接口

块设备接口

网络设备接口

阻塞/非阻塞IO

2.两种方式接口：阻塞（同步）、非阻塞（异步）

I/O程序提供阻塞和非阻塞两种I/O：

阻塞I/O是指当用户进程调用I/O操作时，进程就被阻塞，需要等待I/O操作完成，进程才被唤醒继续执行。

非阻塞I/O是指用户进程调用I/O操作时，不阻塞该进程，该I/O调用返回一个错误返回值，通常，进程需要通过轮询的方式来查询I/O操作是否完成。比如：打印机的输入和输出。

大多数操作系统提供的都是阻塞I/O。

阻塞I/O使用的轮询技术主要有四种：

read：最原始、性能最低，通过重复调用来检查I/O的状态来完成完整数据的读取。在得到数据前，CPU一直消耗在等待上。

select：改进了read，通过对文件描述符上的事件状态来进行判断。有一个较弱的限制为由于它采用一个1024长度的数组来存储状态，所以它最多可以同时检查1024个文件描述符。

poll：对select改进，采用链表方式避免数组长度的限制，其次它能避免不需要的检查。但当文件描述符较多时，它的性能还是低下。

epoll：Linux下效率最高的I/O事件通知机制，在进入轮询的时候如果没有检查到I/O事件，将会进行休眠，直到事件发生将它唤醒。它是真实利用了事件通知、执行回调的方式，而不是遍历查询，所以不会浪费CPU，执行效率较高。

kequeue：与epoll类似，仅在FreeBSD系统下存在。