操作系统知识点一览

一、操作系统概述

操作系统是一组主管并控制计算机操作、运用和运行硬件、软件资源和提供公共服务的系统软件程序，是计算机系统的内核与基石。同时提供操作界面。

操作系统的特征

并发：多个活动在同一时间间隔内运行
共享：资源被多个进程共用
异步：进程以不可预知的速度向前推进
虚拟：物理的实体抽象成逻辑的对应物

并发与并行的区别：前者对多个进程交替处理，后者同时运行多个进程

操作系统的功能

处理机管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等
存储器管理：内存分配、地址映射、内存保护与共享、内存扩充等
文件管理：文件存储空间管理、目录管理、文件读写管理和保护等
设备管理：缓冲管理、设备分配、设备处理、虚拟设备等
用户接口：不常见

操作系统的历程

手工操作阶段（纸带）
单道批处理阶段
多道批处理阶段（真正意义上的操作系统）
- 实现并发功能
分时操作系统
- 提供人机交互，不能插队
实时操作系统（可以插队）
- 硬实时：必须控制对象在规定时间运行
- 软实时：不必须……

处理机状态

核心态（管态、内核态）：可以执行除访管指令外的所有指令
用户态（目态）：只能执行非特权指令
用户态 -> 核心态：中断（由硬件完成）
核心态 -> 用户态：特权指令psw的标志位，0用户1核心

访管指令：用户态 -> 核心态的确认指令

基本概念

特权指令：仅操作系统使用（IO、中断等）
非特权指令：普通运算（加法等）
内核程序：系统的管理者，可执行一切指令，运行在核心态
应用程序：普通用户启动的程序，只能使用非特权指令，运行在用户态

原语

处在操作系统最底层，是最接近硬件的软件部分
这些程序的运行具有原子性，操作不可再分，只能一气呵成
运行时间较短，调用频繁

中断、系统调用、体系结构

内中断（内部信号，如异常）：
- 自愿中断：指令中断，如Ctrl + c
- 强迫终端：错误异常
外中断（外设请求、人工干预等，如打印机没纸）
系统调用：系统给程序提供的唯一接口，可获得OS的服务，在用户态发生核心态处理
体系结构：大内核、微内核

二、进程管理

进程：操作系统的基本执行单位。对于面向进程设计的系统，是程序的基本执行实体；对于面向线程设计的系统，是线程的容器。

进程的特征

动态性：动态产生，动态消亡
并发性：可以与其他进程一起并发执行
独立性：系统分配资源和调度的独立单位
异步性：按各自独立的、不可预知的速度向前推进
结构特征：
- PCB进程控制：保存进程运行期间相关的数据，是进程存在的唯一标志
- 程序段：能被进程调度到CPU的代码
- 数据段：存放数据

进程状态图

进程的状态

运行态：进程正在占用CPU
就绪态：进程准备好了，一旦得到处理机资源（时间片）则立即运行
阻塞态：进程由于等待某一事件不能占用CPU
创建状态：进程正在被创建
结束状态：进程正在从系统消失

进程的状态切换

就绪态 -> 运行态：被CPU调度，获得处理机资源（时间片）
运行态 -> 就绪态：时间片结束或更高级进程进入
运行态 -> 阻塞态：进程需要的某个资源未准备好
阻塞态 -> 运行态：进程等待的事件到来或资源准备好

线程

线程是操作系统运算调度的最小单位，是进程中实际运作单位，一个进程可以并发多个线程。

处理机调度

从就绪队列中按照给定的算法选择一个进程并分配资源，以实现进程并发地执行。
分类：
- 高级调度（作业）
- 中级调度（内存）
- 低级调度（进程）
调度方式：剥夺式（会强制停掉进程）、非剥夺式
调度准则：CPU利用率、系统吞吐量、周转时间、等待时间、响应时间等

调度算法

先来先服务FCFS：传统队列的方式调度进程，优先考虑等待时间最长的作业，不考虑运行时间长短。可能因为长时间进程造成堵塞。
短作业优先SJF：单调堆的方式调度进程，优先考虑短时间作业。可能使长时间进程分配不到资源。
优先级调度算法HPF：优先队列的方式调度进程，根据优先值考虑先后顺序。可能使优先级低的进程分配不到资源。
高响应比优先调度算法时间片轮转HRN：根据FCFS和SJF的综合平衡响应比1 + W/T来决定先后顺序。
多级反馈调度算法：根据优先级分成数个FCFS队列，队列间考虑优先级，但队列中不会让渡。

调度算法的各个时间（对于单个进程来说）

运行时间：完成时间 - 开始时间
周转时间：完成时间 - 到达时间
带权周转时间：周转时间 / 运行时间
等待时间：周转时间 - 运行时间

进程同步

原因：协调进程之间的相互制约关系
制约关系：
- 直接制约关系（同步）：进程之间相互合作传递信息，需要线程协调其
- 间接制约关系（互斥）：数个进程间，只能有一个进程占用临界资源
临界资源：一次仅允许一个进程使用的资源
临界区：限制同时执行该区域程序的线程数量（通常为1），确保资源访问互斥，避免数据不同步。

临界区的作用

保护共享资源：限制同时访问数量，避免数据不同步。
防止静态条件：避免线程的先后顺序导致的结果不确定性。
提高程序稳定性

临界区的实现依赖于互斥锁、信号量、条件变量

临界区互斥

原则：
- 空闲让进
- 忙则等待
- 有限等待：进程要在有限时间内退出。
- 让权等待：进程若不能进入自己的临界区，应让出CPU资源，避免忙等现象。
基本方法：信号量S，利用PV操作实现互斥

申请资源P：S - 1后，若S >= 0进程继续执行；S < 0进程被阻塞后放入等待队列，然后转进程调度。

释放资源V：S + 1后，若S > 0进程继续执行；S <= 0从等待队列释放一个等待进程，在返回原进程继续执行或转进程调度。

生产者消费者问题

又称有限缓冲问题，即有数个线程创建数据到缓冲区（生产者），另有数个线程从缓冲区使用/消耗/删除数据（消费者）。该问题要保证生产者不会在缓冲区满的时候生产，消费者不会在缓冲区空的时候消费。

重点有二：

线程间同步：一个线程生产/消费时，其它线程静默

互斥锁

死锁

定义：多个进程因竞争资源造成的僵局，若无外力，进程无法推进
原因：非剥夺资源的竞争和进程的不恰当推进顺序
解决方法：
1. 预防：
  - 破坏互斥条件
  - 破坏不剥夺条件
  - 破坏请求和保持条件
  - 破坏循环等待条件
2. 避免死锁：安全状态、银行家算法
3. 检测死锁：利用死锁定理
4. 解除死锁：资源剥夺法、撤销进程法、进程回退法
避免死锁的资源申请公式：
最多资源申请数 = （资源总数 / 进程数）+ 1（不能整除时 + 1）

银行家算法

一种判断进程申请资源是否安全的算法（避免死锁）。举例（四个数字代表四个资源）：

Process（进程）	Allocation（返还）	Need（需要）	Available / Work（空余）
P0	0 0 3 2	0 0 1 2	1 6 2 2
P1	1 0 0 0	1 7 5 0
P2	1 3 5 4	2 3 5 6
P3	0 3 3 2	0 6 5 2
P4	0 0 1 4	0 6 5 6

其中，安全序列是一条路径下始终满足资源供给的进程调用路径，若没有，则该状态是危险的。

下一个资源调用的值按照Allocation与上一个Work之和为准。

三、内存管理

目的：更好的支持多道程序的并发执行，提高系统性能。

主要功能

内存空间的分配与回收
存储的保护和共享，保证各道作业互不干扰
地址转换：变换逻辑与物理地址
内存扩充：逻辑上扩充内存

地址空间

逻辑地址（给程序看）：便于查看的假定编号，如0、1、2、3…
物理地址（给内存看）：实际存储的地址编号，如2347892

本章核心即为两种地址的转换

程序的装入

绝对装入：
- 编译时，若知道程序驻留在内存的位置，则直接生成绝对地址的目标代码（不重定位），按照物理内存的位置赋予实际的物理地址。
- 优点：效率高
- 缺点：
  1. 受内存大小显示，能装入内存并发执行的进程数大幅减少。
  2. 需要知道内存的空闲地址，多通道程序下不可能实现，所以仅限于单道程序环境。
静态重定位：
- 在程序开始执行前，程序种指令和数据的各个地址均已完成重定位。地址变换通常在装入时一次完成，以后不再改变。
- 优点：不需要硬件支持（重定位寄存器）。
- 缺点：不能在内存中搬动，且要求程序的存储空间是连续的（对比动态重定位，类似数组与链表的物理存储方式）。
动态重定位：
- 把地址转换推迟到程序执行时再进行。
- 优点：可以解决碎片问题（不需要连续内存）。
- 缺点：需要硬件支持（重定位寄存器），否则会影响指令的执行速度。

重定位：虚拟地址到物理地址的映射

程序的链接

静态链接：程序运行之前，将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
装入时链接：编译后得到一组目标模块，装入内存时，边装入边链接。
运行时链接：程序需要该目标模块时，再去链接，便于修改修改和更新。

内存空间的分配与回收

连续分配管理方式
- 单一连续分配：分配到内存固定的区域（单用户/单任务的操作系统）
- 固定分区分配：分配到内存不同的固定区域
- 动态分区配置：按照程序的需要（算法）进行动态划分
  - 首次适应：以地址递增的次序链接。分配内存时顺序查找，找到空间大小满足的分区。
  - 最佳适应：按容量递增的方式形成分区链，找到第一个满足要求的分区。
  - 最坏适应：以容量递减的次序链接，找到第一个满足要求（空间最大）的分区。
  - 临近适应：在首次适应的基础上，再次划分时，从上次查找结束的位置继续。
非连续分配管理方式：
将内存空间分为一个个大小相等的分区，每个分区是一个内存块 / 页框 / 页帧 / 物理块，每个内存块有一个编号，从0开始。将用户进程的地址空间也分为与内存块大小相等的一个个区域，称为页 / 页面，每个页也有一个编号，从0开始。
操作系统以内存块为单位分配空间，进程的每个页分别放入一个内存块内，两者存在哈希对应关系。

万变不离其宗，经典的连续与离散问题

非连续内存分配管理图

快表（TLB）查询：只记录最近访问的页表项的副本，可以加快地址变换的速度（TLB不是内存）

快表查询

分段式存储管理：与分页式类似，作业的地址空间被分为若干个段，页表改为段表。主要部分离散，分出去的集合连续。

分段产生外部碎片，分页产生内部碎片

地址变换过程

算页号、页内偏移量
检查页号合法性
（TLB）查快表，若命中跳5，否则继续4
查页表，找到对应内存块号，（TLB）并将页表项复制到快表中
根据内存快好与页内偏移量得到物理地址
访问目标内存单元

内存扩充

覆盖（同一进程中）：将程序分为多个模块，常用的常驻内存，不常用的按需调入内存。
交换（不同进程之间）：内存空间紧张时，系统将某些进程暂时换出外存，将外存中具备条件的进程换入内存。（进程在内外存之间动态调度）’
虚拟内存：
- 原理：在逻辑上扩充内存
- 组成部分：页表机制、中断机制（缺页中断）、地址变换机制、内存与外存
- 整体流程：地址变换过程 + 置换算法
- 置换算法：
  1. 先进先出（FIFO）：淘汰最先进入内存的页面，可能会有Belady异常现象（经典队列）
  2. 最近最久未用（LRU）：将内存中最长时间未被访问的页面淘汰（需要寄存器与栈）
  3. 最近最少用（clock）：将内存中当前使用最少的页面淘汰
  4. 最优（OPT）：将以后不再使用或最长时间内不再使用的页面淘汰（理论，不可实现）

四、文件系统

文件是以计算机硬盘为载体，存储在计算机上的信息集合。

文件系统是操作系统中负责操纵和管理文件的一整套设施，实现文件的共享和保护。

影响文件安全的主要因素：人为、自然、系统

功能

文件管理
目录管理
文件空间管理
文件共享和保护
提供接口

文件逻辑结构的分类

无结构（流式）文件：最简单的文件组成形式
- 将数据按顺序组织成记录并累积保存，是有序相关信息的集合，以字节byte为单位。
- 没有结构，对记录的访问只能穷举搜索。故不适用于大多数应用，但管理简单。
- 对基本信息单位操作不多的文件适用，如源程序文件、目标代码文件等。
有结构（记录式）文件：
- 顺序文件：文件中的记录像数组一样顺序排列，访问时需要顺序搜索文件。
- 索引文件：通过一个索引 / 哈希表来检索文件。
- 索引顺序文件：上两者结合。

文件控制块（FCB）：文件系统内部，每个文件均唯一地设置一个文件控制块。用于描述和控制文件的数据结构，与文件一一对应。
- 基本信息：文件名、物理地址、逻辑结构、物理结构等。
- 存取控制信息：是否可读 / 写、访问用户黑名单等。
- 使用信息：创建时间、修改时间等。
目录结构：单级、二级、树形（常见的“文件夹”结构）、图形

文件实现

文件分配方式：连续分配、链接分配、索引分配（对应三大种数据结构）
文件存储空间管理：
- 空闲表法：于内存管理中的动态分区相似，按照程序的需要（算法），为文件动态划分一个连续的存储空间。
  - 同样可使用首次适应、最佳适应、最坏适应、临近适应等算法。
  - 回收：动态分区相似，根据前后的临近空间分为四种情况，回收时要注意表项的合并问题。
- 空间链表法：操作系统保存链头、链尾指针。
  - 分配：若某文件申请K个盘块，则可以采用分配算法从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
  - 回收：若与某个空闲盘区相邻，则要将回收区合并到空闲盘区中。若没有相邻，则作为单独的空闲盘区挂在链尾。
- 位示图法：以二维布尔数组（位示图）表示盘块状态，两个维度的序号分别表示字号和位号。
  - 分配：顺序扫描位示图，找到K个相邻或不相邻的空闲位置，再根据字号、位号算出对应盘块号，分配给文件，最后设置对应位置为已分配。
  - 回收：根据盘块号计算字号和位号，将设置对应位置为空闲。

磁盘管理（机械硬盘）

需要注意的是，固态硬盘在逻辑构造上接近内存，其物理结构也与机械硬盘大不相同，不适用下述概念。

机械硬盘构造：
- 盘片：记录信息的载体，理解为纸张，一个盘片可能含两个盘面，理解为纸张正反面使用。一块硬盘可以有多块盘片。
- 磁头：修改指定位置的Byte位，理解为笔。一块硬盘可以有多个磁头，每个盘面均对应一个磁头。
- 磁臂：固定磁头悬浮在盘面上，理解为手。只存在一个磁臂，所有磁头平行排列于磁头上，所以所有磁头共进退，所有盘面中相对位置相同的磁道组成柱面。
磁盘地址结构：柱面号、盘面号、扇面号
磁盘调度算法：主要目标是优化机械硬盘的寻道时间，固态硬盘对应的查找时间几乎可以忽略不计，故不需要调度算法。
- 先到先服务FCFS：按请求到达的顺序进行处理，不做优化。
- 最短查找时间优先SSTF：选择距离当前磁头位置最近的请求进行处理，目的是最小化磁头的寻址时间。
- 扫描 / 电梯算法SCAN：磁头在盘片上从一个方向移动到另一个方向，处理经过的所有请求。到了盘片的末端后，磁头反转方向并继续处理。
- 循环扫描算法C-SCAN：类似于SCAN，但当磁头到达盘片的最远端时，会立即跳回起始端，而不是反向扫描。
- LOOK和C-LOOK：类似于SCAN和C-SCAN，但磁头在到达最后一个请求后会停止，而不是继续走到盘片的尽头。

多级索引

将索引表分层，使第一层索引块指向第二层的索引块，还可以跟布局文件大小的要求继续建立更多索引块。顶层索引表只占一个索引块，非底层的索引表表项记录指向下一层索引表的开始地址，底层的索引表表项指向数据块地址。

假设磁盘块大小为1kb，一个索引表项占4b，则一个磁盘块能存放1kb / 4b = 256个索引项。

若改用两层索引，则文件的最大长度可达256 ^ 2 * 1kb = 64mb。

五、输入输出（IO）设备管理

与设备无关，目的是管理统一化。

设备简述

分类：存储 / 输入输出设备、块 / 字符设备、低 / 中 / 高速设备。
控制方式：
- 程序直接控制（查询方式）：CPU监听设备控制器是否将数据放到了存储器中（或者反过来），当监听到操作后（即完成IO）CPU才能干别的事（参考代码编程时的控制台输入）。
- 中断方式：设备控制器将数据放到了存储器中（或者反过来）后，向CPU发出中断请求。
- DMA方式：中断方式的优化。中断方式是以字节为单位进行中断，DMA将数据直接存入内存，待IO结束后再向CPU发出中断。
- IO通道控制方式：上述方式只能传输一个连续的数据块，IO通道控制方式则可以传输不连续的数据块，减少CPU干预。

缓冲区

目的：
1. 缓和CPU与外设间速度不匹配的矛盾
2. 提高CPU与外设之间的并行性
3. 减少对CPU的中断次数
设置方式：
- 单缓冲：信息输入 / 输出率相差很大时，可采用该方式。
- 双缓冲：信息输入 / 输出率相差不大时，利用该方式，实现两者并行。
- 多缓冲：对于阵发性的IO，为了解决速度不匹配的问题，可以设立多个缓冲区。

常用设备分配技术

根据使用性质分类：
- 独占设备：不能共享的设备，只允许一个进程独占，如打印机。
- 共享设备：可以多个进程共享的设备，如磁盘。
- 虚拟设备：利用技术手段，将独占设备改造为共享设备。
针对三种设备采用三种分配技术：
- 独占分配：将独占设备固定第分配给一个进程，直至该进程完成IO操作并释放为止。
- 共享分配：适用于高速、大容量的直接存储设备。由多个进程共享一台设备，每个进程只用其中一部分。
- 虚拟分配：利用共享设备模拟独占设备，从而使独占设备成为可共享的、快速的IO设备，如假脱机操作。