学习笔记｜操作系统

本文最后更新于：5 years ago

本文系统描述操作系统的主要功能，重点在于全局的知识框架，而非细节。

1.为什么需要操作系统

1.1 操作系统的演进

1.1.1 无操作系统

人工操作
用户独占一台计算机
CPU等待人工操作
资源利用率低

1.1.2 批处理系统

无需等待人工输入
批量输入任务
资源利用率提升
多道程序设计

1.1.3 分时系统

人-机交互
多用户共享
及时调试

1.2 多道程序设计

1.2.1 作用：

早期批处理系统只能一次处理一个任务。
多道程序设计使得批处理系统可以一次处理多个任务。

1.2.2 原理：

多道程序设计：计算机内存中同时存放多个程序。
多道程序在计算机的管理程序下互相穿插运行，以此提高计算机资源的利用率。

1.3 操作系统的功能

操作系统的重要功能：对【多道程序】的管理。

对 多道程序 的管理分为五大功能：

进程管理、存储管理、作业管理、文件管理、设备管理。

1.3.1 进程管理

进程实体
五状态模型
进程同步
Linux 的进程管理

1.3.2 作业管理

进程调度
死锁

1.3.3 存储管理

内存分配与回收
段页式存储管理
虚拟内存
Linux 的存储管理

1.3.4 文件管理

文件管理
Linux 的文件系统
Linux 文件的基本操作

1.3.5 设备管理

设备管理

2操作系统的概览

2.1 什么是操作系统

管理硬件、提供用户交互的软件系统。

具体为：

操作系统是管理计算机硬件资源和软件资源的计算机程序。
管理配置内存、决定资源供需顺序、控制输入输出设备等。
操作系统提供让用户和系统交互的操作界面。

2.2 操作系统的基本功能

2.2.1 统一管理计算机资源

处理器资源
IO设备资源
存储器资源
文件资源

2.2.2 实现对计算机资源的抽象

无需面向硬件接口编程。
IO设备管理软件，提供读写接口。
文件管理软件，提供操作文件接口。

2.2.3 提供用户与计算机之间的接口

图形窗口的形式
命令形式
系统调用形式

2.3 操作系统的相关概念

2.3.1 并发性

并行：两个或者多个事件在 同一时刻 发生。
并发：两个或者多个事件在 同一个时间间隔 发生。

例如：

【并行】一边听课一边记笔记：听和记同一个时刻发生。

【并发】先听课再记笔记：在同一个时间段完成两个事件。

单处理器只存在并发执行。
双处理器每个时刻都是有两个程序并行执行，既有并发也有并行。

2.3.2 共享性

共享性：操作系统中的资源可供多个并发的程序共同使用。
这种共同使用的形式称为：资源共享。

【资源共享】：

多个程序同时使用主存资源。
资源共享分为：互斥共享形式、同时访问形式。
- 互斥共享：当前资源被程序A占用，其他的想使用的话只能等待。
- 同时访问：某资源在一段时间内被 并发地 被多个程序访问。“同时” 是宏观的，宏观上看，该资源可以被同时访问。

举个例子：

互斥共享形式：程序A 占用打印机，程序B 需要等待程序A 使用完毕。
同时访问形式：程序A 和程序B，同时访问主存的不同位置；或者一段时间内，多个程序 并发地 访问某资源。

2.3.3 虚拟性

虚拟性：把一个物理实体转变为若干个逻辑实体。
物理实体是真实存在的，逻辑实体是虚拟的。
虚拟技术：时分复用技术、空分复用技术。

【时分复用技术】

资源在时间上进行复用：不同程序并发使用。
多道程序 分时使用 计算机硬件资源。
提高资源利用率。

（1）虚拟处理器技术

借助多道程序设计技术。
为每个程序建立进程。
多个程序分时复用处理器。

（2）虚拟设备技术

物理设备虚拟成多个逻辑设备。
每个程序占用一个逻辑设备。
多个程序通过逻辑设备并发访问。

【空分复用技术】

实现虚拟内存、虚拟磁盘。
提高资源的利用率，提升编程效率。

（1）虚拟磁盘技术

物理磁盘虚拟为逻辑盘。
C盘、D盘…等为逻辑盘。
更安全、方便地使用。

（2）虚拟内存技术

在逻辑上扩大了程序的存储容量。
便于使用比实际内存更大的容量。
提升编程的效率。

2.3.4 异步性

在多道程序的环境下，允许多个进程并发执行。
进程在使用资源时，可能需要等待或放弃。
进程的执行并不是一气呵成的，而是走走停停的形式推进的。

3.进程管理

3.1 进程实体

3.1.1 为什么需要进程

进程是系统进行 资源分配和调度 的基本单位
进程作为程序的独立运行的载体保障程序正常执行。
因为：进程在运行时会隔离并行资源。
进程存在使得操作系统资源的利用率大幅提升。

3.1.2 主存中的进程形态

进程控制块（PCB）

进程控制块（PCB）：主存中的连续存储空间。
进程控制块的以下信息分为四类：
- 进程的标识符
- 进程状态
- 进程调度信息
- 进程控制信息

信息	作用
标识符（进程ID）	唯一标记一个进程，用于区别其他进程。
状态	标记进程的进程状态。
程序计数器	指向即将被执行的下一条指令的地址。
内存指针	程序代码、进程数据相关的指针。
上下文数据	进程指向时，处理器存储的数据。
IO状态信息	被进程IO操作所占用的文件列表。
记账信息	处理时间、时钟数总和。

（1）进程控制块（PCB）的作用

用于描述和控制进程运行的通用数据结构。
记录进程的当前状态和控制进程运行的全部信息。
PCB 使得进程是能够独立运行的基本单位。

（2）进程控制块（PCB）的位置

PCB 是操作系统进行调度时，经常会被读取的信息。
PCB 是常驻内存的，存在系统专门开辟的PCB区域。

3.2 进程与线程

进程：Process
线程：Thread

一个进程可以有多个线程。

线程是操作系统进行运行调度的最小单位。
线程包含在进程中，是进程中实际运行工作的单位。
一个进程可以并发多个线程，每个线程执行不同的任务。

	进程	线程
资源	资源分配的基本单位	不拥有资源
调度	独立调度的基本单位	独立调度的最小单位
系统开销	进程系统开销大	线程系统开销小
通信	进程IPC	读写同一进程的数据通信

3.3 五态模型

3.3.1 就绪状态

有所有资源（进程控制块、内存、栈空间、堆空间），只差 CPU。

当进程被分配到除 CPU 以为所有必要的资源后，就是就绪状态。
只要获得 CPU 使用权，就可以立即执行。

【就绪队列】：

在一个系统中，多个就绪状态的进程通常排成一个队列：就绪队列。

3.3.2 执行状态

进程获得 CPU，其程序正在执行。
单处理机中，某一个时刻只有一个进程处于执行状态。（不存在并行执行）

3.3.3 阻塞状态

进程因为某种状态，无法继续执行，从而放弃 CPU 的状态为阻塞状态。

【阻塞队列】：

多个阻塞的进程，存放在队列里。

3.3.4 创建状态

创建进程时，拥有 PCB，但 其他资源未就绪 的状态称为 创建状态

【创建进程的两个步骤】：

graph LR
A(1.分配 PCB ) --> B(2.插入就绪队列)

PS：操作系统提供 fork 函数接口创建进程。

3.3.5 终止状态

进程结束由系统清理或者归还 PCB 的状态称为终止状态。

【终止状态的两个步骤】：

graph LR
A(1.清理系统) --> B(2.归还 PCB)

3.3.6 状态转换的过程

理解，默写一边。

3.4 进程同步

3.4.1 生产者消费者问题

（1）问题描述

多个生产者进程生产产品，并放入缓冲区。
多个消费者进程从缓冲区取走这些产品消费。
生产者进程和消费者进程可以并发执行。
在两者之间有 n 个缓冲区的缓冲池。

（2）具体过程

【生产者进程】生产一个产品，放到缓冲区（操作缓冲区数据），三个步骤：

register = count
register 是生产者进程的寄存器。count 是缓冲区，缓冲在 Cache 上。先将缓冲区的 count 数据赋值给生产者进程寄存器 register。
register = register + 1
寄存器加一。
count = register
将生产者进程的寄存器 register 的数据，写入缓冲区 count。

【消费者进程】消费一个产品，从缓冲区取走（操作缓冲区数据），三个步骤：

register = count
register 是消费者进程的寄存器。count 是缓冲区。先将缓冲区的 count 数据赋值给消费者进程寄存器 register。
register = register - 1
寄存器减一。
count = register
将消费者进程寄存器 register 的数据，写入缓冲区 count。

（3）进程不同步会发生的问题

因为生产者进程和消费者进程是并发执行的，而 count 是临界资源，所以会出现问题。

例如：

// 假设 count = 10；
producer.register = count;   // count = 10,  p.register = 10
producer.register++;         // count = 10,  p.register = 11
comsumer.register = count;   // count = 10,  c.register = 10
comsumer.register--;         // count = 10,  c.register = 9
count = comsumer.register;   // count = 9,   c.register = 9
count = producter.register;  // count = 11,  p.register = 11

出现问题：最终 count 应该是 10，但是最后执行完还是 11。

3.4.2 哲学家进餐问题

（1）问题描述

有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共同使用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子。
平时哲学家们只进行思考，饥饿时则试图取靠近他们的左、右两支筷子，只有两支筷子都被他拿到的时候就能进餐，进餐完毕之后，放下左右筷子继续思考。

3.4.3 为什么需要进程同步

从例子来分析：

问题根源：彼此之间没有通信。
生产者消费者问题：生产者通知消费者，我已经生产一件产品了。
哲学家进餐问题：哲学家和旁边的哲学家说我要进餐了。

（1）进程同步的作用：

对竞争资源在多进程间进行使用次序的协调。
使得并发执行的多个进程间，可以有效使用资源和互相合作。

（2）临界资源：

临街资源指一些虽作为共享资源却又无法同时被多个线程共同访问的贡献资源。
当有进程使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该资源，才可以重新竞争该资源。

3.4.4 进程同步的四个原则

空闲让进：资源未被占用，允许使用。
忙则等待：资源被占用，请求进程等待。
有限等待：保证有限的等待时间内，能够使用资源。
让权等待：等待时，进程需要让出 CPU，（执行状态 --> 阻塞状态）。

3.4.5 进程同步的三个方法

消息队列
共享存储
信号量

3.4.6 线程同步

进程的线程共享进程资源。
当多个线程并发使用进程资源时，也需要同步。

3.4.7 线程同步的四个方法

互斥量
读写锁
自旋锁
条件变量

3.5 Linux 的进程管理

3.5.1 进程的类型

**前台进程：**具有终端，可以和用户交互的进程。
后台进程：
- 与前台进程相对，没有占用终端的就是后台进程。
- 后台程序基本不和用户交互，优先级比前台进程低。
- PS：将需要执行的命令以 “&“ 符号结束。
守护进程（daemon）：
- 守护进程是特殊的后台进程。
- 很多守护进程在系统引导的时候启动，一直运行到系统关闭。
- PS：进程以 ”d“ 结尾的一般都是守护进程。如：httpd，sshd，crond，mysqld…

3.5.2 进程的标记

（1）进程的ID

进程 ID 是进程的唯一标记，每个进程拥有不同的 ID。
进程 ID 表现为一个非负整数，最大值由操作系统限定。
top 命令查看所以进程。

（2）进程的层级关系

pstree 命令查看父子进程关系。

（3）特殊的进程

ID 为 0 的进程，idle 进程，是系统创建的第一个进程。
ID 为 1 的进程，init 进程，是 0 号进程的子进程，完成系统初始化。
init 进程是所有用户进程的祖先进程。

3.5.3 进程的状态标记

状态符号	状态说明
R	（TASK_RUNNING）运行状态
S	（TASK_INTERRUPTIBLE）睡眠状态
D	（TASK_UNINTERRUPTIBLE）等待 IO 的睡眠状态
T	（TASK_STOPPED）暂停状态
Z	（TASK_DEAD or EXIT_ZOMBIE）退出状态或僵尸进程

3.5.4 操作进程的命令

（1）ps 命令

显示当前进程状态。

-aux：打印进程的详细信息：进程用户、进程 ID、进程状态、运行时间、执行的命令…

# 查看 root 用户的进程
ps -u root

# 查询 pyhton3 的进程
ps -aux | grep 'python3'

# 打印进程的父子关系
ps -ef --forest   # forest：森林

# 按照 cpu 的使用排序（从大到小）
ps -aux --sort=-pcpu

# 按照 内存 的使用排序（从大到小）
ps -aux --sort=-pmem

（2）top 命令

查看系统所有进程。

PR：优先级。VIRT：进程的虚拟内存。

total：所有的内存。free：所有的内存。used：已经使用的内存。buff：已经缓存的内存。

（3）kill 命令

发送指定信号给进程。

9 表示无条件停止。sigkill。

1 2	`杀死 PID 是 62016 的进程。 kill -9 62016`

4.作业管理

4.1 进程调度

4.1.1 进程调度

**进程调度：**计算机通过决策决定哪个就绪进程可以获得 CPU 使用权。

保留旧进程的运行信息，请出旧进程（收拾包袱）
选择新进程，准备运行环境并分配 CPU（新进驻）

4.1.2 进程调度的三种机制

（1）就绪队列的排队机制

将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。

（2）选择运行进程的委派机制

调度程序以一定的策略选择就绪进程，将 CPU 资源分配给它。

（3）新老进程的上下文切换机制

进程或线程的上下文切换需要消耗 CPU。

保存当前进程的上下文信息，装入被委派执行进程上下文。

将老进程的上下文从 cache 存入主存当中，以便下次继续执行。
1. 将新进程的上下文存入 cache，让 CPU 准备运行环境。

4.1.3 进程调度的两种方法

（1）非抢占式调度

处理器一旦分配给某一个进程，就让该进程一直执行下去。
调度程序不以任何原因抢占正在被使用的处理器。
直到进程完成工作或者因为 IO 阻塞才会让出处理器。

（2）抢占式调度

允许调度程序以一定的策略暂停当前运行的进程。
保留旧进程的上下文信息，分配处理器给新进程。

（3）比较

	抢占式调度	非抢占式调度
系统开销	频繁切换、开销大	切换次数少、开销小
公平性	相对公平	不公平（一个进程可以长期占有 CPU）
应用	通用系统（计算机）	专用系统

4.2 调度算法

4.2.1 先来先服务FCFS

非抢占式调度。
调度顺序为就绪队列的顺序。

4.2.2 短进程优先（最短作业优先SJF）

调度程序优先选择就绪队列中估计运行时间最短的进程。
短进程优先调度算法不利于长作业进程的执行。

PS：

分为抢占式 SJF、非抢占式SJF。

4.2.3 高优先权优先

进程附带优先权，调度程序优先选择权重高的进程。
高优先权优先调度算法使得 紧迫的任务 可以优先处理。
- 前台进程优先级会高于后台进程，因为前台进程需要和用户交互，保证不卡顿。

PS：

优先权太低的进程得不到运行，出现“饥饿”现象。
SJF 是 高优先权优先 的特例。

4.2.4 时间片轮转Round-Robin

按照先来先服务的原则排列就绪进程。
每次从队列头部取出待执行的进程，分配一个时间片执行。
执行完时间片插入就绪队列尾部。

PS：

相对公平的调度算法，但不能保证及时响应用户。
当时间片足够长，就变成了非抢占式调度，也就退化成 FCFS，FCFS 是 RR 的特例。

4.3 死锁

4.3.1 死锁的产生

（1）竞争临界资源

自身占用的资源不释放，等待请求的资源被释放。（哲学家进餐问题）

（2）进程调度顺序不当

进程1 和进程2 都需要传真机和打印机才能执行，

A --> B --> C --> D 则产生死锁。
A --> D --> B --> C 则不会产生死锁。

4.3.2 死锁的四个条件

四个必要条件。

（1）互斥条件

进程对资源的使用是排他性的使用。
资源只能由一个进程使用，其他进程使用只能等待。

（2）请求保持条件

进程至少保持一个资源，又提出新的资源的请求。
新的资源被其他进程占用，新的资源的请求被阻塞。
被阻塞的进程不释放自己的资源。

（3）不可剥夺条件

进程获得资源，在进程未完成使用前，资源不能被剥夺。
获得的资源只能由进程自身释放。

（4）环路等待条件

发生死锁，必然存在 进程-资源环形链 （进程 P1、P2、P3、P4；资源R1、R2、R3、R4）

4.3.3 预防死锁的方法

（1）破坏请求保持条件

系统规定进程运行前，一次性申请所有需要的资源。
进程运行时，不会因为请求资源而产生等待的情况。

（2）破坏不可剥夺条件

进程请求新的资源得不到满足时，必须释放占有的资源。
进程运行时，占有的资源可以被释放，意味着可以被剥夺。

（3）破坏环路等待条件

可用资源线性排序，申请必须按照需要递增申请。
线性申请不再形成环路，从而破坏了环路等待条件。
- 正例：线程A、B申请资源顺序均为R1->R2；
- 反例：A申请顺序为R1->R2，B申请顺序为R2->R1。

4.3.4 银行家算法

是一个可操作的著名的避免死锁的算法。

客户申请的贷款是有限的，每次申请需声明最大资金量。
银行家在能够满足贷款时，给用户贷款。
客户使用贷款后，能及时归还贷款。

所需资源表 - 已分配资源表 = 还需分配资源表。
将 可分配资源表 和 还需分配资源表 进行对比。

5.存储管理

5.1 内存分配和回收

5.1.1 为什么需要存储管理

早期的计算机编程并不需要太多的储存管理。

随着计算机和程序越来越复杂，存储管理成为必要。

5.1.2 三点原因

确保计算机有足够的内存处理数据。
确保程序可以从可用内存中获取一部分内存使用。
确保程序可以归还使用后的内存，以供其他程序使用。

5.2 内存分配的过程

5.2.1 单一连续分配（过时）

系统区内存给操作系统使用，用户区内存给用户程序使用。

单一连续分配是简单的内存分配方式。
只能在单用户、单进程的操作系统中使用。

5.2.2 固定分区分配

固定分区分配是 支持多道程序的最简单 的存储分配方式。
内存空间被划分若干个固定大小的区域。
每个分区只提供给一个程序使用，互不干扰。

5.2.3 动态分区分配

数据结构：

（1）动态分区空闲表结构

（2）动态分区空闲链表结构

算法：

（1）首次适应算法（FF算法）

分配内存时，从开始顺序查找合适内存区。
若没有合适的空闲区，则该次分配失败。
**问题：**每次从头部开始，使得头部的地址空间不断的被划分（很多内存碎片）。每次都需要遍历到尾部的时候，才能分配到内存。
**改进：**循环适应算法

（2）循环适应算法

分配内存时，从上一次检索结束的位置开始。

（3）最佳适应算法（BF算法）

先把空闲区链表按照容量大小排序。
遍历空闲区链表找到合适的空闲区。
好处：从小到大遍历，可以避免大才小用。

（4）快速适应算法（QF算法）

有多个空闲链表
每个空闲链表存储一种容量的空闲区
当需要内存分配的时候，可以快速找到合适大小的空闲区。

5.3 内存回收的过程

四种情况：

（1）回收区位于空闲区后

不需要建立新的空闲区节点。
将空闲区1的节点的容量增大为新的空闲区。

（2）回收区位于空闲区前

将回收区和空闲区1合并。
新的空闲区使用回收区的地址，作为新空闲区节点的地址。

（3）回收区位于两个空闲区之间

将空闲区1、空闲区2、回收区合并。
新的空闲区使用空闲区1的地址，作为新空闲区节点的地址。

（4）单独的回收区

为回收区创建新的空闲节点。
将空闲区节点插入空闲链表中。

5.4 段页式存储管理

从进程的角度管理内存空间。

5.4.1 页式存储管理

（1）页面

**页面：**相对逻辑设备的定义。

字、字块：相对物理设备的定义。

（2）页式存储管理

将进程的逻辑空间等分成若干个大小的页面。
相应的把物理内存空间分成和页面大小相同的物理块。
以页面为单位，把进程空间装进物理内存中分散的物理块。

页面大小应该适中，过大难以分配，过小内存碎片过多。
页面大小通常是512B～8K

（3）页表

页表记录进程逻辑空间与物理空间的映射。

（4）页式存储的问题

现代计算机系统中，可以支持非常大的逻辑地址空间（2^32 ～ 2^64）,页表就变得特别大（占用内存）。

举个例子：

32位系统进程寻址空间为 4G，页面大小为 4KB，
那么就需要 4G / 4KB = 2^20 个页表。
一个页表大小为 1Byte，故每个进程需要 1MB 的内存存储页表。

（5）多级页表

为了解决上面页表过多占用内存的问题。

根页表的每个页面代表的是一个页表，字块指向一个二级页表的地址。
进程执行时，只需要将根页表加载到内存中，再按需取页表。（当用某个二级页表时，再把某个二级页笔加载到内存中。）

（6）页式存储不可改进的问题

若有一段连续的逻辑分布在多个页面中，将大大降低执行效率。

5.4.2 段式存储管理

改进页式存储不可改进的问题。

将进程逻辑空间划分为若干段（非等分）。
段的长度由 连续逻辑的长度 决定。
按照函数的逻辑长度划分，比如主函数 main，子程序段 x，子函数 y等。
拥有一个段表：

5.4.3 段式存储和页式存储的区别

**共同点：**离散地管理了进程的逻辑空间。

不同点：

页是物理单位，按照物理的角度划分的；段是逻辑单位，按照进程的逻辑划分的。
分页是为了合理利用空间，分段是满足用户的需求。
页大小由硬件固定，段长度可动态变化。
页表信息是一维（页号对应页号），段表信息是二维的（记录基址和段长）。

5.4.4 段页式存储管理

采取了页式存储和段式存储的优点。
- 分页可以有效提高内存利用率。
- 分段可以更好地满足用户需求。
- 两者结合，形成段页式存储管理。
先将逻辑空间按照段式管理分为若干段。
再把段内空间按页式管理分为若干页。

5.5 虚拟内存

5.5.1 为什么需要虚拟内存

有些进程实际需要的内存很大，超过物理内存的容量。
因为使用多道程序设计，所以计算机中同时运行着多个进程，使得每个进程的可用物理内存更加稀缺。
不可能无限增加物理内存，物理内存总有不够的时候。

5.5.2 虚拟内存概述

虚拟内存是操作系统内存管理的关键技术。
使得多道程序运行和大程序运行成为现实。
把程序使用内存划分，将部分暂时不使用的内存放置在辅存中。

如图，逻辑空间是程序运行所需的内存，将需要使用的加载到物理内存运行中，不使用的放置在缓存中。

5.5.3 程序的局部性原理

补充：
**时间局部性：**被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
**空间局部性：**如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

局部性原理是指 CPU 访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都聚集在一个较小的连续区域中。

程序运行时，无需全部装入内存，装载部分即可。
如果访问页不在内存中，则发出缺页中断，发起页面置换。
从用户层面看，程序拥有很大空间，即是虚拟内存。

虚拟内存实际上是对物理内存的补充，速度接近于内存，成本接近于辅存。

5.5.4 虚拟内存的置换算法

高速缓存和主存 置换、主存和辅存 置换都会使用到的算法。
虚拟内存 的置换算法是 主存和辅存 的置换。

先进先出算法（FIFO）
最不经常使用算法（LFU）
最近最少使用算法（LRU）

（1）高速缓存的替换时机（高速缓存和主存的置换）

（2）主存的替换时机（主存和辅存的置换）

（3）高速缓存替换、主存替换的区别

替换策略发生在 Cache-主存层次、主存-辅存层次。
Cache-主存层次 的替换策略主要为了 解决速度问题。
主存-辅存层次 的替换主要为了 解决容量问题。

5.6 Linux 的内存管理

5.6.1 Buddy 内存管理算法

Buddy 算法是经典的内存管理算法。
算法基于 **计算机处理二进制具有极高的效率 **的优势。
算法主要是为了解决 内存外碎片 的问题。
- 将 内存内碎片问题 转移成 内存外碎片问题。
- 为什么要转移？——内存外碎片一般比内存内碎片要大。

5.6.2 页内碎片与页外碎片

页内碎片（内存内碎片、内部碎片）：

内部碎片是已经被分配出去（明确指出属于哪个进程）的内存空间，大于所需空间。

已分配的内存空间中不能被利用的内存空间就是内部碎片。

页外碎片（内存外碎片、外部碎片）：

外部碎片是指还没分配出去（不属于任何进程），但是由于太小而无法分配给申请内存空间的新进程的内存空闲块。

5.6.3 Buddy 内存分配原则

原因：计算机处理二进制具有极高的效率。

向上取整为 2 的幂的大小。
- 如需 70K，则分配 128K
- 如需 129K，则分配 256K

5.6.4 伙伴系统

伙伴是指一片内存的伙伴。
一片连续内存 的伙伴是指 相邻的另一片大小一样 的连续内存。

5.6.5 Buddy算法的具体流程

创建一系列的空闲块链表，每一种都是 2 的幂。

（1）分配内存

举个例子：

假设存储空间有 1M 的大小。
其他大小的空闲块链表节点都是空的，1MB的空闲块链表有一个节点。

此时需要分配 100K 的内存，步骤如下：

100K 向上取 2 的幂 = 128K。
查询是否有 128K 内存空闲块？——没有！
查询是否有 256K 内存空闲块？——没有！
查询是否有 512K 内存空闲块？——没有！
查询是否有 1M 内存空闲块？——有！
将 1M 内存空闲块分配出去。
将 1M 中的 512K 放在 512K 的空闲链表中，其余的分配出去。判断是否符合要求。
将分配出去的 512K 中的 256K 放在 256K 的空闲链表中，其余的分配出去。判断是否符合要求。
将分配出去的 256K 中的 128K 放在 128K 的空闲链表中，其余的分配出去。判断是否符合要求。
满足需求，分配完毕。

（2）回收内存

还是上面的例子：

回收 128K 的内存步骤：

伙伴：一片连续内存 的伙伴是指 相邻的另一片大小一样 的连续内存。

判断回收的内存的伙伴是否在 128K 的内存空闲链表上？——在！
移除伙伴，需回收的内存和伙伴合并为 256K 的空闲内存。判断其伙伴在不在 256K 的链表上？——在！
移除伙伴，合并的 256K 的内存和伙伴合并为 512K 的空闲内存。判断其伙伴在不在 512K 的链表上？——在！
移除伙伴，合并的 512K 的内存和伙伴合并为 1M 的空闲内存。判断其伙伴在不在 1M 的链表上？——不在！
将合并的 1M 的空闲块内存插入到 1M 的空闲链表中，回收完成。

5.6.6 Linux 交换空间（Swap）

交换空间（Swap）是磁盘的一个分区。
Linux 物理内存满时，会把一些内存交换至 Swap 空间。
Swap 空间是初始化系统时配置的。

不推荐使用的原因：Swap 交换空间在磁盘，速度相对慢，如果频繁使用，降低系统运行速度。

作用：

冷启动的内存依赖。——一些大型程序启动的时候需要大量的内存，但后续运行的时候，大部分内存会被很少地使用。系统就可以将这部分不怎么使用的数据，保存到 Swap 空间，从而释放更多的物理内存，供其他程序使用。
系统睡眠依赖。——当系统需要睡眠的时候，系统将所有内存数据保存在 Swap 空间中，等下次系统启动的时候，将这部分数据重新加载到内存中，提高系统的启动速度。
大进程的空间依赖。——某些大进程的确需要很大的内存空间。将进程需要使用到的数据暂时保存到 Swap 空间中。

5.6.7 虚拟内存和 Swap 空间的区别

相同点：

都是存在于磁盘（辅存）中。
都是与主存发生置换。

不同点：

Swap 空间是操作系统的概念。
- 站在 Linux 的角度去看待的。
虚拟内存是进程概念。
- 站在进程的角度去看待的。
- 当我们谈到虚拟内存的时候，是指某个进程的虚拟内存。
Swap 空间是为了解决系统物理内存不足的问题。
虚拟内存是为了解决进程物理内存不足的问题。

6.文件管理

6.1 文件的逻辑结构

6.1.1 文件的结构类型

6.1.2 有结构文件

文件内容由 定长记录 和 可变长记录 组成。
定长记录 存储文件格式、文件描述等结构化数据项。
可变长记录 存储文件具体内容。

举个例子—— 以 png 图片的文件格式为例：

定长记录存储文件格式、文件描述等结构化数据项：PNG文件标记、文件结束标记。
可变长记录存储文件具体内容：PNG数据块。

6.1.3 无结构文件（流式文件）

文件内容长度以字节为单位。
如exe文件、dll文件、so文件。

6.1.4 顺序文件

顺序文件指按顺序存放在存储介质中的文件。
磁带的存储特性使得磁带文件只能存储顺序文件。
顺序文件是所有逻辑文件当中存储效率最高的。（只需要按照顺序读和写就可以了。）

**问题：**顺序文件的增删改效率低。

6.1.5 索引文件

可变长文件不适合使用顺序文件格式存储。
索引文件是为了解决可变长文件存储而发明的一种文件格式。
索引文件需要配合索引表完成存储操作。

索引表：

6.2 辅存的存储空间分配

6.2.1 辅存的分配方式

6.2.2 连续分配

举个例子：如果程序需要六个扇区的空间，系统就分配连续六个扇区。

顺序读取文件内存非常容易，速度快。
对存储要求高：要求有 满足容量的连续存储空间。

6.2.3 链接分配

链式分配可以将文件存储在离散的盘块中。
需要 额外的存储空间 存储 文件的盘块链接顺序。

（1）隐式链接

当前盘块内存储了 下一个链接指向。例如：第 2 个盘块存储着 下一个链接指向（第 9个盘块）。
隐式分配适合顺序访问，随机访问效率低。

**问题：**可靠性差，任何一个链接出现问题，都将影响整个文件。

（2）显示链接

解决隐式链接分配的问题（可靠性差，随机访问效率低）。

与隐式链接分配想比，显示链接分配方式，多了一个 FAT 表。（File Allocation Table）

问题：

不支持高效的直接存储。
- FAT 记录项较多，磁盘越大，FAT 的记录项就越多。
- 当在 FAT 文件系统中添加一个较大的文件，就需要检索整个 FAT 表，找到空闲的行块号。
检索时，FAT 表占用较大的存储空间。（需要将整个 FAT 表加载到内存中）

6.2.4 索引分配

每个文件拥有一个索引块，记录所有盘块信息。
当需要读取某一个文件时，将文件索引读取进内存即可。
索引分配方式支持直接访问盘块。
文件较大时，索引分配方式具有明显的优势。

6.3 辅存的存储空间管理

6.3.1 空闲表

空闲盘区的分配与内存分配类似。
也是使用首次适应算法、循环适应算法、最佳适应算法、快速适应算法。
回收过程与内存回收类似。

6.3.2 空闲链表

把所有空闲盘区组成一个空闲链表
每个链表节点存储空闲盘块和空闲数目。

与内存空闲链表类似。

6.3.3 位示图

实际的辅存的存储空间管理就是使用位示图来管理的。

横轴位磁道，纵轴为盘块，1 表示被占用、0 表示未被使用。

优点：

位示图的维护成本低，只需要维护一个表。
位示图可以很容易的找到空闲的盘块。
位示图使用的 0/1 比特位，占用空间小。

作用：使得每一个文件都有唯一的路径。

6.4 Linux 文件

6.4.1 Linux 常用目录

目录	描述
/bin	存放二进制可执行文件(ls,cat,mkdir等)，常用命令一般都在这里
/etc	存放系统管理和配置文件
/home	存放所有用户文件的根目录，是用户主目录的基点，比如用户user的主目录就是 /home/user
/usr	用于存放系统应用程序，比较重要的目录/usr/local 本地系统管理员软件安装目录
/opt	额外安装的可选应用程序包所放置的位置
/proc	虚拟文件系统目录，是系统内存的映射。可直接访问这个目录来获取系统信息。
/root	超级用户（系统管理员）的主目录
/sbin	存放二进制可执行文件，只有root才能访问
/dev	用于存放设备文件
/mnt	系统管理员安装临时文件系统的安装点，系统提供这个目录是让用户临时挂载其他的文件系统。
/boot	存放用于系统引导时使用的各种文件
/lib	存放跟文件系统中的程序运行所需要的共享库及内核模块
/var	用于存放运行时需要改变数据的文件

6.4.2 Linux 文件类型

其中，b 表示块设备，c 表示字符设备。

6.5 Linux 文件系统

6.5.1 文件系统

FAT（File Allocation Table）
- FAT16、FAT32等，微软 Dos/Windows 使用的文件系统。
- 用一张表来保存盘块的信息。
NTFS（New Technology File System）
- WindowsNT环境的文件系统。
- NTFS 对 FAT 进行了改进，取代了旧的文件系统。
EXT（Extended file system）
- 扩展文件系统，EXT2/3/4。
- Linux 的文件系统。

6.5.2 EXT文件系统

**Boot Sector：**启动扇区，安装开机管理程序。
**Block Group：**块组，存储数据的实际位置。

Block Group 中，

Inode table
- Inode table：存放 Inode 的地方。
- Inode 是每个文件的索引节点。（EXT文件系统管理外存的方式是索引分配）
- 每个文件（目录）都有一个 Inode。
- Inode 存储了 索引节点编号、文件类型、文件权限、文件物理地址、文件长度、文件连接计数、文件存取时间、文件状态、访问计数、链接指针。
- 【特殊】文件名不是存放在 Inode 节点上的，而是存放在 目录的 Inode 节点上。
  - 【原因】列出目录文件的时候无需加载文件的 Inode。
Inode bitmap
- Inode 的位示图
- 记录已分配的 Inode 和未被分配的 Inode。
Data block
- Data block 是存放文件内容的地方。
- 每个 block 都有唯一的编号。
- 文件的 block 记录在文件的 Inode 上。
Block bitmap
- 功能和 Inode bitmap 类似。
- 记录 Data block 的使用情况。
Superblock
- 记录整个文件系统相关信息的地方。
- Block 和 Inode 的使用情况。
- 时间信息、控制信息等。
- 一般为 1024 字节。