文章内容不包含Linux部份！
 

第 1 章    操作系统概论

1.1    操作系统概观

现代计算机系统
现代计算机操作系统由 硬件 和 软件 两个部份组成，是硬件和软件相互交织形成的集合体，构成一个解决计算问题的工具。

软件
软件由 程序、数据 及 文档 组成。 可分为 系统软件、支撑软件 和 应用软件。

系统软件
系统软件（操作系统）层是最靠近硬件的一层软件，它一方面直接和硬件交互，负责管理和控制机器硬件并对其做首次扩充和改造；另一方面和上层的支撑软件和应用软件交互，把它们与计算机硬件隔离开，为程序员提供方便的编程接、有力的功能支撑、良好的运行环境。

支撑软件
支撑软件层的工作基础建立在操作系统扩充功能的机器上，利用操作系统所提供的扩展指令集，支持应用软件的开发和运行。

应用软件
应用软件层解决用户特定的或不同应用所需要的信息处理问题，任何计算机系统的价值都要通过应用软件的价值来评定和体现。

操作系统与支撑软件、应用软件之间的主要区别

1. 都是软件，但是操作系统有权分配资源，而支撑软件和应用软件只能通过操作系统使用资源。
2. 操作系统直接作用于硬件之上，隔离其他上层软件，并为其提供接口和服务。

三种密切相关的资源管理技术
1）复用
由于计算机系统的物理资源是宝贵和稀有的，操作系统让众多的进程共享物理资源，这种共享称为 资源复用。物理资源复用有两种基本方法：空分复用共享 和 时分复用共享。
①空分复用共享
空分复用共享 表明资源可以从 “空间” 上分割成更小的单位供进程使用。
②时分复用共享
时分复用共享 表明资源可以从 “时间” 上分割成更小的单位供进程使用。

2）虚拟
虚拟的本质是对资源进行转化、模拟或整合，把一个物理资源转变成多个逻辑上对应物，也可以把多个物理资源变成单个逻辑上对应物，即创建无须共享的多个独占资源的假象，或创建易用且多于实际物理资源数量的虚拟资源假象，以达到多用户共享一套计算机物理资源的目的。

3）抽象
复用和虚拟的主要目标是解决物理资源数量不足的问题，抽象则多用于处理系统复杂性，重点解决资源易用性。
资源抽象 是指通过创建软件来屏蔽硬件资源的物理特性和实现细节，简化对硬件资源的操作、控制和实使用，即不考虑物理细节而对资源执行操作的技术。

操作系统定义
管理系统资源、控制程序执行、改善人机界面、提供各种服务，并合理组织计算机工作流程和为用户方便有效地使用计算机提供良好运行环境的一种系统软件。

操作系统在计算机系统中起4个方面的作用

1. 服务用户 观点——操作系统作为用户接口和公共服务程序。
2. 进程交互 观点——操作系统作为进程执行的控制者和协调者。
3. 系统实现 观点——操作系统做为扩展机或虚拟机。
4. 资源管理 观点——操作系统作为资源的管理者和控制着。

资源管理观点 操作系统的5项主要功能

1. 处理器管理
2. 存储管理
3. 设备管理
4. 文件管理
5. 联网与通信管理

操作系统主要特征

1. 并发性——并发性指两个或以上的活动或事件在同一时间间隔内发生。
2. 共享性——共享性指计算机系统中的资源可以被多个并发执行的程序共用，而不是被某个程序独占。
3. 异步性——在多道程序环境中允许多个程序并发进行，并发活动会导致随机事件的发生，由于资源有限而程序众多，每个程序的执行并非连贯的，而是“走走停停”。

并发于并行的区别
并发：
指多个事件在同一时间间隔内发生。这些事件在宏观上是同时发生的，但在微观上是交替发生的。

并行：
指多个事件在同一时刻同时发生。

1.2    操作系统形成与发展

多道程序设计
多道程序设计是指允许多个作业（程序）同时进入计算机系统的内存并启动交替计算的方法。

从宏观上看是并行的，多道程序都处于运行过程中，但尚未运行结束；从微观上看是串行的，各道程序轮流占用 CPU 交替地执行。

操作系统引入多道程序设计的优缺点

1. 提高 CPU、内存和设备的利用率
2. 提高设备吞吐率，使单位时间内完成的作业数量增加
3. 可以充分发挥系统的并行性，使设备与设备之间、CPU 与设备之间均可并行工作
4. 主要缺点是延长了作业的周转时间

批处理操作系统优缺点

1. 采用多道程序设计技术，系统资源利用率高，作业吞吐量大
2. 作业周转时间延长，不具备交互式计算能力，不利于程序的开发和调试

批处理操作系统的特点

1. 批量集中处理
2. 多道程序运行
3. 作业脱机工作（作业运行过程中不能干预）

1.3    操作系统基本服务和用户接口

用户接口
程序接口 是操作系统对外提供服务和功能的手段，它由一组 系统调用组成，应用程序可以使用 系统调用 获得操作系统的低层服务，访问或使用系统管理的各种软件资源。

操作接口由一组控制命令和（或）作业控制语言组成，是操作系统为用户提供的组织和控制其作业（应用程序）执行的手段。

内核程序
实现操作系统的程序称为 内核程序。

内核
由很多内核程序组成了 操作系统内核，或简称 内核（Kernel)。

内核是一组程序模块，作为 可信软件 来提供支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于内核态，具有直接访问硬件设备和所有内存空间的权限，是仅有的能够执行特权指令的程序。

一个操作系统只要有内核就够了(eg: Docker—>仅需Linux内核)。操作系统的功能未必都在内核中，如图形化用户界面GUI就不在内核中。

系统调用
操作系统为了达到 为应用程序的运行创建良好环境 这个目标，内核提供一系列 具有预定功能 的服务例程，通过一组称为 系统调用 的接口呈现给用户，系统调用把应用程序的请求传送至内核，调用相应服务例程完成所需处理，将结果返回给应用程序。
（就像是C语言中调用 printf函数，printf函数 看作系统调用的话，那么具体的实现（在屏幕输出）就通过低层的请求完成，然后返回结果）

系统调用的作用

1. 内核可以基于权限和规则对资源访问进行裁决，保证系统的安全性。
2. 系统调用对资源进行了抽象，提供一致性接口，避免用户在使用资源时发生错误，且编程效率大大提高。
3. 系统调用是应用程序获得操作系统服务的唯一途径。

系统调用分类

1. 进程控制。
2. 文件管理。
3. 设备管理。
4. 存储管理。
5. 进程通信。
6. 信息维护。

系统调用的实现
操作系统实现系统调用功能的机制称为 陷阱或异常处理机制。由于系统调用而引起的处理器中断的机器指令称为 访管指令、自陷指令 或 中断指令。

1.4    操作系统结构和运行模型

单体式结构
把模块作为操作系统的基本单位，按照功能需要而不是根据程序和数据的特性把整个系统分解为若干模块，每个模块具有一定独立功能，各个模块间可以不加控制自由调用。（模块类似C语言中的各个函数）

单体式结构优缺点

1. 结构紧密、组合方便，对不同环境和用户的不同需求可以组合不同的模块来满足，灵活性大。
2. 针对某个功能可用最有效的算法和任意调用其他模块来实现，系统效率高。
3. 模块独立性差，模块间牵连多，形成复杂的调用关系。

层次式结构
这种结构把操作系统划分为内核和若干模块（进程），这些模块（进程）按功能的调用次序排列成若干层次，各层之间只能存在单向依赖或单向调用关系，即 低层为高层服务，高层可以调用低层功能，反之则不能，这样结构更清晰。

层次式结构优缺点

1. 整体问题局部化，层次之间的依赖和调用关系更为清晰规范。
2. 增加、修改或替换层次不影响其他层次，有利于系统的维护和扩充。
3. 系统效率降低。

微内核结构
操作系统仅将所有应用必需的核心功能放入内核，曾为 微内核，其他功能都在内核之外，由在用户态运行的服务进程来实现，通过微内核所提供的消息传递机制完成进程之间消息通信。

微内核结构优缺点

1. 对进程的请求提供一致性接口。
2. 具有较好的可扩充性和易修改性。
3. 可移植性好。
4. 运行效率较低，因为进程间必须通过内核的通信机制才能进行通信。

第 2 章    处理器管理

2.1    处理器状态

内核态与用户态
CPU有两种状态，内核态 和 用户态。
处于内核态时，说明此时正在运行的是内核程序，此时可以执行 特权指令。
处于用户态时，说明此时正在运行的是应用程序，此时只能执行 非特权指令。

别名：
内核态 = 核心态 = 管态；用户态 = 目态

特权指令和非特权指令
特权指令 是指仅在内核态下才能使用的指令，如:内存清零指令。这些指令影响重大, 执行这些指令不仅影响运行程序本身，而且干扰其他程序及操作系统。

非特权指令 在目态和管态下都能工作。

应用程序 只能使用 非特权指令，如：加法指令、减法指令等。

处理器状态及其转换
以下情况会导致处理器从用户态向内核态转换

• 程序请求。
• 中断。
• 异常。

处理器从内核态向用户态转换：通过系统提供的 加载程序状态字的特权指令 返回用户态。

用户栈
用户进程空间中开辟的一块空间，用于保存应用程序的子程序（函数）间的相互调用的参数、返回值、返回点以及子程序的局部变量。

核心栈
内存中属于操作系统空间的一块区域。

作用为：

1. 用于保存中断现场。
2. 保存操作系统程序（函数）间相互调用的参数、返回值、返回点以及程序局部变量。

每个进程被创建时捆绑一个核心栈，具有 可读可写不可执行 属性。

程序状态字
操作系统将程序运行时的一组动态信息汇集到一起，称为程序状态字（PSW），存放在处理器的一组特殊寄存器里。

PSW用来 指示运行程序的状态，控制指令执行顺序，并且 保留和指示与运行程序有关的各种信息，主要作用是 实现程序状态的保护和恢复。

2.2    中断技术

中断源分类

1. 外中断（中断或异步中断）——指来至处理器之外的中断信号，如时钟中断、键盘中断等。
2. 内中断（异常）——指来至处理器内部的中断信号。

中断/异常的响应过程

1. 发现中断源。
2. 保护现场。硬件将现场信息（PSW）保存至核心栈。
3. 转向中断/异常事件处理程序执行。
4. 恢复现场。恢复原运行程序的PSW，重新返回中断点以便执行后续指令。

中断优先级注意事项
时钟中断 比 访管中断 优先级高

2.3    进程及其实现

进程定义
进程是具有独立功能的程序在某个数据集合上的一次运行活动，也是操作系统进行资源分配和保护的基本单位。

进程的属性

1. 动态性。
   进程是程序在数据集合上的一次执行过程，是动态的概念，有生命周期；而程序是一组有序指令序列，是静态概念，作为系统中的一种资源是永久存在的。
2. 共享性。
   同一程序同时运行于不同数据集合上时构成不同进程，进程和程序不是一一对应的。
3. 独立性。
   每个进程都是一个独立实体，拥有自己的虚存空间、程序计数器和内部状态。
4. 制约性。
   进程因共享资源或协同工作产生相互制约关系。
5. 并发性。
   多个进程的执行在时间上可以重叠，可并发或并行执行。因此，进程的执行是可以被打断的。

三态模型
按进程在执行过程中的不同情况至少定义有三种进程状态：

• 运行态：进程占有处理器正在运行的状态。
• 就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态。
• 等待态：又称 阻塞态 或睡眠态，指进程不具备运行条件。

处于运行态的进程个数不能大于处理器个数，处于就绪态和等待态的进程可以有多个。

进程控制块（PCB）
进程控制块是进程存在的唯一标识，是操作系统用来记录和刻画进程状态及环境信息的 数据结构。

PCB是操作系统中最为重要的数据结构，它包含管理进程所需的所有信息。

进程映像
程序和数据是进程必需的组成部分，两者刻画了进程的静态特征。

某时刻进程的内容及其状态集合 称为进程的映像，包含以下要素：

1. 进程控制块（PCB）。
   每个进程捆绑一个，进程创建时建立进程控制块，进程撤销时回收进程控制块，与进程一一对应。它用来存储进程的各种信息。
2. 进程程序块。
   被进程执行的程序。
3. 进程数据块。
   进程私有的地址空间，存放各种私有数据，用户栈 也在数据块中开辟。
4. 进程核心栈。
   每个进程捆绑一个，进程在 内核态工作时 使用，用来保存中断 / 异常现场。

进程上下文
操作系统中，进程物理实体 和 支持进程运行的环境 合成进程上下文。

进程上下文由三部分组成：

1. 用户级上下文。
   由程序块、数据块、用户栈、共享内存区组成，占用进程的 虚存空间。对换至磁盘的分段或页面任然是用户级上下文的组成部分。
2. 寄存器上下文。
   由处理器状态寄存器、指令计数器、栈指针、通用寄存器等组成。进程不处于运行态时，处理器状态信息保存在寄存器上下文中。
3. 系统级上下文。
   由程序控制块（PCB）、内存管理信息、核心栈等操作系统管理进程所需要的信息组成。

进程上下文切换和处理器状态转换

进程创建
进程一般创建过程：

1. 在进程列表中增加一项，从PCB池中申请一个空闲PCB，为新进程分配唯一进程标识符。
2. 为新进程的进程映像分配地址空间。
3. 为新进程分配各种资源。
4. 初始化PCB。
5. 把新进程的状态设置为就绪态，并将其移入就绪队列。
6. 通知操作系统某些模块。

线程与进程
线程是进程中能够并发执行的实体，是进程的组成部分，也是 系统调度和分派的基本单位。

进程是资源分配的最小单位。

线程与进程的区别

2.6    处理器调度

处理器调度层次

1. 高级调度
   从输入系统的一批作业中按照预定的调度策略 挑选若干作业进入内存，为其分配所需资源并创建对应作业的用户进程。
2. 中级调度
   根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存的进程对换工作。
3. 低级调度
   根据某种原则决定就绪队列中的哪个进程/线程获得处理器，并将处理器出让给它使用。
   低级调度是操作系统最核心的部份。

选择调度算法的5条原则

1. 资源利用率。
   CPU 资源利用率 = CPU 有效工作时间 / CPU 总的运行时间
   CPU 总的运行时间 = CPU 有效工作时间 + CPU 空闲等待时间
2. 吞吐率。
   单位时间内 CPU 处理作业的个数。
3. 公平性。
   CPU 和资源分配合理，不会出现饥饿现象。
4. 响应时间。
   从交互式进程提交一个请求（命令）直到获得响应之间的时间间隔称为响应时间。
5. 周转时间。
   从 向系统提交作业 开始到 作业完成 为止的时间间隔称为作业的周转时间。实际上是作业在系统中的等待时间和运行时间之和。
    
   作业周转时间 = 作业提交给系统的时刻 - 完成时刻
   作业的带权周转时间 = 周转时间 / 运行时间

作业和进程的关系
作业（job）是用户提交给操作系统计算的一个独立任务。
 
作业是任务的实体，进程是完成任务的执行实体；没有作业任务，进程无事可做；没有进程，作业任务无法完成。

低级调度算法

1. 先来先服务算法（FCFS）。
   按照作业进入系统后备作业队列的先后次序来挑选作业。这是一种非剥夺式调度算法。
    
   

2. 最短作业优先算法（SJF）。
   以进入系统作业所要求的 CPU 运行时间的长短为标准，总是选取预计计算时间最短的作业投入运行。这是也一种非剥夺式调度算法。
    
   

3. 最短剩余时间优先算法（SRTF）。
   假设当前有进程正在运行，新进的进程所需的 CPU 运行时间比当前的进程所需要的剩余 CPU 时间还短，则将强行剥夺当前执行者的控制权，调度新进程执行。这是一种 剥夺式 调度算法。
    
   

4. 最高响应比优先算法（HRRF）
   响应比 = 作业周转时间/作业处理时间
               = (作业等待时间 + 作业处理时间) / 作业处理时间
               = 1 + 作业等待时间 / 作业处理时间
    
   每当调度作业时，计算后备队列中每个作业的响应比作为其优先级，选择响应比最高者投入运行。
    
   
   

5. 优先级调度算法
   根据确定的优先级来选取进程，总是选择就绪队列中优先级高者投入运行。

6. 轮转调度算法（RR）
   调度程序每次把 CPU 分配给就绪队列首进程使用规定的时间间隔，称为 时间片，就绪队列中的每个进程 轮流地运行一个是时间片，当时间片耗尽时就强迫当前进程让出处理器，转而排列到就绪队列尾部。

第 3 章    同步、通信与死锁

3.1    并发进程

顺序程序设计特征

1. 执行的顺序性。
   严格按序执行，每个操作必须在下一个操作开始前结束。
2. 环境的封闭性。
   独占全机资源，资源状态不受外界因素影响。
3. 结果的确定性。
   程序执行结果与它的执行速度无关。
4. 过程的可再现性。
   重复执行程序会获得相同的执行过程和计算结果。

程序并发执行
程序并发执行是指一组程序的执行在时间上是重叠的。
程序的并发执行产生资源共享的需求，从而使程序是去封闭性、顺序性、确定性和可再现性。

Bernstein 条件
R ( P i ) = { a i , a 2 , . . . , a n } ， 程 序 P i 在 执 行 期 间 所 引 用 的 变 量 集 R(P_i) = \{a_i, a_2, ..., a_n\}，程序P_i在执行期间所引用的变量集 R(Pi​)={ai​,a2​,...,an​}，程序Pi​在执行期间所引用的变量集
W ( P i ) = { b i , b 2 , . . . , b n } ， 程 序 W i 在 执 行 期 间 所 改 变 的 变 量 集 W(P_i) = \{b_i, b_2, ..., b_n\}，程序W_i在执行期间所改变的变量集 W(Pi​)={bi​,b2​,...,bn​}，程序Wi​在执行期间所改变的变量集

若两个进程$P_1$和$P_2$能满足 Bernstein 条件，即引用变量集与改变变量集的交集为空集
$R(P_1)\bigcap W(P_2)\bigcup R(P_2)\bigcap W(P_1)\bigcup W(P_1)\bigcap W(P_2)=\varnothing$

则并发进程的执行与时间无关。

进程互斥
进程互斥是指若干进程因相互争夺 独占型资源 而产生的竞争制约关系。

进程同步
进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或信息所产生的协作制约关系。

3.2    临界区管理

临界区和临界资源
并发进程中与共享变量有关的 程序段 称为 临界区。
共享变量所代表的资源称为 临界资源，即一次只能供一个进程使用的资源。

临界区调度的三个原则

1. 一次至多只有一个进程进入临界区内执行。
2. 如果已有进程在临界区内，试图进入临界区的其他进程应等待。
3. 进入临界区内的进程应在有限时间内退出，以便让等待队列中的一个进程进入。

3.3    信号量与 PV 操作

信号量
一个进程在某一关键点上被迫停止执行直至接收到 对应的特殊变量值，通过这一措施，任何复杂的进程交互要求均得到满足，这种特殊变量就是信号量（semaphore）。

PV 操作特点

• 除赋初值外，信号量仅能由同步原语 PV 对其进行操作，不存在其他方法检查或操作信号量。
• PV 操作都是原语，执行中不能被打断。

关于信号量和 PV 操作的推论

1. 若信号量为正值，此数值等于在封锁进程之前可对信号量施行 P 操作数，即 信号量代表实际可用的物理资源。
2. 若信号量为正值，其 绝对值 等于登记排列在信号量队列之中等待的进程个数，恰好等于对信号量实施 P 操作而被封锁进入等待队列的进程个数。
3. 通常 P 操作意味着请求一个资源，V 操作意味着释放一个资源，在一定条件下，P 操作代表挂起进程的操作，V 操作代表唤醒被挂起进程的操作。

3.4    管程

管程
在进程共享一个内存的前提下，把分散在各个进程中互斥访问的共享变量及其操作集中到一起统一控制和管理，这样就可以方便地管理和使用共享资源，使并发进程之间的相互作用更为清晰。

代表共享资源的数据结构及并发进程在其上执行的一组过程就构成了管程。

基本思想：
把分散在各进程中的临界区集中起来管理，并把共享资源用 数据结构 抽象地表示，由于临界区是访问共享资源的代码段，建立一个“秘书”程序管理程序到来的访问，“秘书” 每次只让一个进程来访。后来，“秘书”程序更名为管程。

定义：
管程是由 局部于自己的若干公共变量及其声明 和所有 访问这些公共变量的过程 组成的软件模块，它提供一种互斥机制，进程可互斥地调用管程中的过程。

注意点：
1）一个管程最多只有一个进程在执行。
2）管程中的 signal 原语与信号量中的 V 操作不同，当没有进程在等待时，signal 操作相当于空操作，信号不被保存。

3.7    死锁

死锁现象
当操作系统允许多个进程并发执行时可能出现进程永远被阻塞现象，如两个进程分别等待对方所占有的一个资源，于是两个进程都不能执行而处于永远等待状态，此现象称为死锁。

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

死锁主要解决方法

• 死锁防止
• 死锁避免
• 死锁检测和恢复

死锁防止
死锁产生的条件
产生死锁必定同时保持如下4个必要条件：

1. 互斥条件 —— 进程应互斥且排斥地使用临界资源。
2. 占有和等待条件 —— 进程在请求资源得不到满足而等待时，不释放已占资源。
3. 不剥夺条件 —— 已获资源只能由进程自愿释放。
4. 循环等待条件 —— 存在循环等待链，其中，每个进程都在等待链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态。

死锁防止策略

1. 破坏条件1
   使资源可同时访问而非互斥使用。但由于一些资源的特殊性质只能互斥地占有，而不能被同时访问，所以这种做法在许多场合行不通。
2. 破坏条件2
   采用 静态分配 策略，即进程必须在执行前就申请需要的全部资源，且直到所要的资源都得到满足后才开始执行。
   这样虽然解决了破坏了条件2，但是会严重降低资源利用率。
3. 破坏条件3
   剥夺调度能够防止死锁，但是只适用于内存和处理器资源。
4. 破坏条件4
   采用 层次分配 策略。
   层次分配策略的一个变种是 按序分配 策略。把系统的所有资源按顺序编号，规定进程请求所需资源的顺序必须按照资源的编号依次进行。即规定进程不得在占用资源 i（1 ≤ i ≤ m）后再申请资源 j（j ＜ i）。

死锁避免
死锁避免允许系统中同时存在前三个必要条件，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁。
死锁避免方法不是对进程随意强加规则，而是动态地确定是否分配资源给提出请求的进程。如果一个进程当前请求资源会导致死锁，系统将拒绝启动此进程；如果一个资源分配会导致系统下一步死锁，便拒绝本次分配。

银行家算法

资源分配图

• 一个方框表示一个 资源类。
• 方框中的黑点表示此资源类中的各个 资源。
• 一个圆圈表示一个 进程。
• $P_i\to R_j$为请求边，这条有向边从进程开始指向资源类方框的边缘，表示此进程等待得到$R_j$类资源的状态。
• $R_j\to P_i$为分配边，冲方框内的某个黑点出发指向进程，表示$R_j$类资源的一个资源被进程$P_i$占用。

进程 - 分配图中存在环路并不一定发生死锁。

有环路而无死锁的例子：

死锁定理
系统处于死锁状态的从分条件是：当且仅当此状态的进程 - 资源分配图是 不可完全简化 的，这一充分条件称为死锁定理。

第 4 章    存储管理

4.1    存储器工作原理

存储器层次
自上而下依次为：寄存器、缓存、内存、磁盘、磁带5层。

访问速度由下而上越来越快，容量越来越小，价格越来越高。

应用程序在计算机系统上运行的过程
首先，编写和编辑应用程序，所编写的程序称为源程序，其中使用符号名集合所限定的空间称为 程序名字空间；

接着 编译程序或汇编程序 处理源程序并生成目标代码（程序）；

链接程序 把它们链接为一个可重定位代码（程序），此时该程序处于逻辑地址空间中；

下一步 装载程序 将可执行代码装入物理地址空间，直到此时程序才能运行。

程序链接的三种方式

1. 静态链接。
   在程序装载到内存和运行前，就已经将它的所有目标模块及所需要的库函数进行链接和装配成一个完整的可执行程序且此后不再拆分。
2. 动态链接。
   在程序装载时一边装载一边链接，生成一个可执行程序。
3. 运行时链接。
   将某些目标模块或库函数的链接推迟到执行时才进行。

程序装载
通常，装载程序把可执行文件装入内存的方式有三：

1. 绝对装载。
   模块中出现的所有地址都是内存绝对地址。
2. 可重定位装载。
   根据内存使用情况，决定将装载代码模块放入内存的物理位置。模块内使用的地址都是相对地址。
3. 动态运行时装载。
   为提高内存利用率，装入内存的程序可换出到磁盘上，适当时候再换入内存，前后程序在内存中的位置可能不同，此时模块内使用的地址必为 相对地址。

地址重定位
可执行程序逻辑地址转换（绑定）为物理地址的过程称为地址重定位。

4.2    连续存储管理

固定分区存储管理
又称 静态分区模式，基本思想：内存空间被划分为 数目固定不变 的分区，给分区 大小不等，每个分区只能装入一个作业，若多个分区中装有作业，则它们可以并发执行。

为说明个分区分配和使用情况，需设置一张内存分配表。

系统初次启动时，管理员根据当天作业情况将内存划分为大小不等但数目固定的分区。

固定分区优缺点

• 能够解决单道程序运行在并发环境下不能与 CPU 速度匹配的问题。
• 解决了单道程序运行时内存空间利用率低的问题。
• 分区大小已预先规定，大作业无法装入。
• 内存空间利用率不高，作业很少会恰好填满分区。
• 作业在运行过程中要求动态扩充内存空间的要求难以实现。
• 分区数目固定，限制了多道运行程序的道数。

可变分区存储管理
按照作业大小来划分分区，但划分的事件、大小、位置都是动态的。

常用的可变分区分配算法

1. 最先适应（first fit）分配算法。
   按顺序查找未分配区表或链表，直到找到 第一个能满足长度要求 的空闲区为止。
2. 下次适应（next fit）分配算法。
   从未分配区的上次扫描结束处顺序查找未分配区表或链表，直到找到第一个能满足长度要求的空闲区为止。
3. 最优适应（best fit）分配算法。
   从空闲块中挑选一个能满足用户进程要求的 最小分区 进行分配。
4. 最坏适应（worst fit）分配算法。
   从空闲块中挑选一个最大的空闲区分割给作业使用。
5. 快速适应（quick fit）分配算法。

对换技术
如果当前一个或多个驻留进程都处于等待态（阻塞态），此时选择其中一个进程，将其暂时移出内存，腾空间给其他进程使用；同时把磁盘中的某个进程换入内存，让其投入运行，这种互换称为对换。

4.3    分页存储管理

物理地址的计算
①物理地址 = 页框号 × 块长 + 页内偏移

②如果页长为2的倍数
物理地址 = 块号的二进制形式 拼接上 页内偏移的二进制形式

位示图的分页存储管理页框分配算法
先检查空闲块数能否满足用户进程的要求，若不能则令进程等待；

能则查找位示图，找出相应数量的位为 0 的那些位，置占用标志，从空闲块数中减去本次占用块数，按所找到的位的位置计算对应页框号，填入此进程的页表。

进程执行结束归还内存时，根据归还的页框号计算出对应位在位示图中的位置，将占有标志置0，并将归还块数加入空闲块数中。

4.4    分段存储管理

引入主要目的
满足用户（程序员）编程和使用上的要求。

分段和分页比较
分段
①分段是信息的 逻辑单位，由源程序的逻辑结构及含义所决定。
②用户可见。
③段长可自定。
④满足用户模块化程序设计的需要。

分页
①分页是信息的 物理单位，与源程序的逻辑结构无关。
②用户不可见。
③页面只能从页大小的整数倍地址开始。
④实现离散分配并提高内存利用率。

4.5    虚拟存储管理

虚拟存储器概念
在具有层次结构存储器的计算机系统中，自动实现部分装入和部份替换功能，在逻辑上为用户提供一个比物理内存容量大得多的、可寻址的“内存储器”。

抖动 / 颠簸
刚被淘汰的页面立刻又要调用，而调入不久随即被淘汰，淘汰不久再被调入，如此反复，使得整个系统的页面调度非常频繁，以至于大部分时间都花费在来回调度页面上，而不是执行计算任务，这种现象叫做“抖动”或者“颠簸”。

Belady 异常
增加可用物理页框数量反而导致更多的缺页异常，这种现象称为 Belady 异常。

全局页面替换策略

1. 最佳页面替换算法（OPT）。
   淘汰页面时，淘汰以后不再访问的页，或距现在最长时间才访问的页。
2. 先进先出页面替换算法（FIFO）。
   淘汰最先进入内存的页面。
3. 最近最少使用页面替换算法（LRU）。
   淘汰在最近一段时间内最久未被访问的页面。
4. 第二次机会页面替换算法（SCR）。
5. 时钟页面替换算法（Clock）。

第 5 章    设备管理

5.3    缓冲技术

缓冲技术的作用
解决 CPU 与设备之间速度不匹配的矛盾及协调逻辑记录大小与物理记录大小不一致的问题，提高 CPU 和设备的并行性，减少 I/O 操作对 CPU 的中断次数，放宽对 CPU 中断响应时间的要求。

缓冲技术的基本思想
当进程执行写操作输出数据时，先向系统申请一个 输出缓冲区，然后将数据输出到缓冲区，若是顺序写请求，则不断把数据写入缓冲区，直到装满为止，此后进程可以继续计算，同时，系统将缓冲区的内容写到设备上。

当进程执行读操作时，先向系统申请一块输入缓冲区，系统将设备上的一条物理记录读至缓冲区，根据要求把当前所要的逻辑记录从缓冲区中选出并传送给进程。

5.4    驱动调度技术

存储设备的物理结构
文件信息通常记录在同一柱面的不同磁道上。

访问磁盘上的一条物理记录，必须给出三个参数：柱面号、磁头号、扇区号。

磁盘寻找柱面这个动作的执行速度较慢，称为 查找时间，等待被访问的扇区旋转到读写磁头下时，按扇区号存取信息，称为 搜索延迟。

磁臂粘性
在一段时间内进程重复请求访问同一柱面会垄断整个设备，造成磁盘臂停留在柱面上不动，称为“磁臂粘性”。

搜查定位

1. 先来先服务服务算法（FCFS）。
2. 最短查找时间优先算法。
   总是执行查找时间最短的请求。
3. 扫描算法。
   移动臂每次沿着一个方向移动，扫过所有柱面，遇到请求便进行处理，直至到达最后一个柱面后，再向相反方向移动回来。
4. 电梯调度算法。
   与扫描算法类似，不同处为：电梯调度算法遇当前方向上最后一个请求后，就可以立即向相反方向移动了，不必扫描到头。

5.5    设备分配

设备独立性
用户通常不指定具体的物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开来，再通过其他途径建立逻辑设备与物理设备之间的映射，设备的这种特性称为“设备独立性”。

设备独立性的好处

• 应用程序与物理设备无关，系统增减或变更设备时对源程序不必加以任何修改。
• 易于应对 I/O 设备故障，提高系统的可靠性，增加设备分配的灵活性，能更有效地利用设备资源，实现多道程序设计。

第 6 章    文件管理

6.1    文件

文件概念
文件是由信息按一定结构方式组成，可持久性保存的抽象机制。

文件命名
文件机制中最重要的是 文件命名。

文件名由 文件名 和 扩展名 两部分组成，前者用于识别文件，后者用来区分文件类型。

6.2    文件目录

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

文件目录
通常把 FCB 汇集和组织在一起形成 文件目录，文件目录包含许多目录项。文件目录的基本功能是将文件名转换成此文件信息在磁盘上的物理位置。

目录项
目录项有两种，分别用于描述子目录和描述文件。

目录文件
全部由目录项所构成的文件称为目录文件，保存在外存上，查找文件时调入内存工作区。

6.3    文件组织与数据存储

文件逻辑结构
从用户观点出发，研究用户概念中抽象的信息组织方式，这是用户所能观察到的、可加以处理的数据集合。由于数据可独立于物理环境构造，故称为逻辑结构，相关数据的集合构成逻辑文件。

文件的逻辑结构分为两种形式：流式文件 和 记录式文件。

逻辑记录 是文件内独立的最小信息单位。

成组和分解
若干逻辑记录合并成一组，写入一块叫做 记录成组，这时每块中的逻辑记录的个数称为 块因子。
把逻辑记录从块中分离出来的操作叫做 记录的分解。

文件物理结构
文件的物理结构和组织是指逻辑文件在物理存储空间中的存放方法和组织关系，这时的文件看做物理文件，即相关物理块的集合。

常用的几种文件物理结构和组织方法：顺序文件、连接文件、索引文件、直接文件。

6.4    文件系统功能及实现

创建和删除文件
1）创建文件
文件创建成功后，存取权限被记录在相应的 inode 的 i_mode 中。之后用户打开文件表中相应文件表项序号。由此可见创建兼具文件的“打开”功能，在以后的操作中无须执行“打开”操作。

2）删除文件
把指定文件从其所在的 目录文件 中去除。如果没有连接的用户，还要把文件所占用的存储空间释放。
删除操作还需要用户对文件具有“写：操作。

打开和关闭文件
1）打开文件
把文件的磁盘 inode 复制到内存活动 inode 表中，同时系统打开文件表的一个表项。

2）关闭文件
释放相应文件的活动 inode。

文件读和写
1）读
文件读入到用户数据区中。

2）写
把用户数据中的信息写入文件。

文件链接
在物理上一处存储、从多个目录可以到达此文件的“多对一关系”称为文件连接。

文件静态共享
两个或多个进程可通过文件链接到达共享同一个文件的目的，无论进程是否运行，其文件的链接关系都是存在的，因此称为静态共享。

文件动态共享
系统中不同应用进程或同一用户的不同进程并发地访问同一文件，这种共享关系只有当进程存在时才可能出现，一旦进程消亡，其共享关系也就随之消亡。