操作系统知识框架梳理

目录

一.计算机系统概述

1.操作系统（软件）概念

操作系统（OS） 是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。

2.操作系统基本特征

• 并发：指两个或多个事件在同一时间间隔内发生；并行（在同一时刻发生）。
• 共享：指系统中的资源可供内存中多个并发执行的进程共同使用。
• 虚拟：指把一个物理上的实体变为若干逻辑上的对应物。
• 异步：多道程序环境允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进。

3.操作系统的目标和功能

3.1.操作系统作为计算机系统资源的管理者

• 处理机管理
• 存储器管理
• 文件管理
• 设备管理

3.2.操作系统作为用户与计算机硬件系统之间的接口

（1）命令接口

• 联机命令接口（适用于分时或实时系统的接口，由一组键盘操作命令组成）
• 脱机命令接口（适用于批处理系统，由一组作业控制命令组成）

（2）程序接口（由一组系统调用组成）

3.3.操作系统实现了对计算机资源的扩充

4.操作系统的发展历程

4.1.手工操作阶段

4.2.批处理阶段

（1）单道批处理系统

• 自动性
• 顺序性
• 单道性

（2）多道批处理系统

• 制约性
• 间断性
• 共享性

4.3.分时操作系统

• 同时性
• 交互性
• 独立性
• 及时性

4.4.实时操作系统

• 及时性
• 可靠性

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

4.6.个人计算机操作系统

5.操作系统运行环境

5.1.处理机运行模式

• 时钟管理
• 中断机制
• 原语

5.2.中断和异常

• 中断（外中断）：I/O结束中断，时钟中断
• 异常（内中断）：程序的非法操作码、地址越界、运算溢出、虚拟系统的缺页及专门的陷入指令。

5.3.系统调用

• 用户程序可执行 陷入指令（访管指令或trap指令） 来发起系统调用，请求操作系统提供服务。

6.操作系统结构

6.1.分层法

最底层（层0）为硬件，最高层（层N）为用户接口，每层只能调用紧邻它的低层的功能和服务。

6.2.模块化

将操作系统按功能划分为若干具有一定独立性的模块。

• 内聚性
• 耦合度

6.3.宏内核

将系统的主要功能模块都作为一个紧密联系的整体运行在核心态 ，从而为用户程序提供高性能的系统服务。

6.4.微内核

指将内核中最基本的功能保留在内核 ，而将那些不需要在核心态执行的功能移到用户态执行，从而降低内核的设计复杂性。

6.5.外核

对机器进行分区，给每个用户整个资源的一个子集。

二.进程与线程

1.进程与线程

1.1.进程的概念与特征

（1）进程实体： 由程序段、相关数据段和PCB三部分构成。

（2）概念： 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

（3）特征

• 动态性：是进程最基本的特征。
• 并发性：指多个进程实体同存于内存中，能在一段时间内同时运行。
• 独立性
• 异步性

1.2.进程的状态与转换

• 运行态：程序正在处理机上运行。
• 就绪态：进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。
• 阻塞态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入输出完成。
• 创建态：进程正在被创建，尚未转到就绪态。
• 结束态：进程正从系统中消失，可能是进程正常结束或其他原因退出运行。

1.3.进程的组织

（1）进程控制块（PCB）

• 进程描述信息
• 进程控制和管理信息
• 资源分配清单
• 处理机相关信息

（2）程序段

（3）数据段

1.4.进程控制

• 进程的创建
• 进程的终止
• 进程的唤醒和阻塞

1.5.进程的通信

（1）共享存储

（2）消息传递（以格式化的信息为单位）

• 直接通信方式
• 间接通信方式：发送进程把消息发送到某个中间实体（信箱）。

（3）管道通信

1.6.线程和多线程模型

（1）线程概念 ：线程是进程中的一个实体，是被系统独立调度和分派的基本单位，不拥有系统资源。

（2）线程的实现方式

• 用户级线程（ULT）
• 内核级线程（KLT）

（3）多线程模型

• 多对一模型
• 一对一模型
• 多对多模型

2.处理机调度

2.1.调度的层次

• 高级调度（作业调度）：外存->内存（面向作业），无->创建态->就绪态。
• 中级调度（内存调度）：外存->内存（面向进程），挂起态->就绪态。
• 低级调度（进程调度）：内存->CPU，就绪态->运行态。

2.2.调度的目标

• CPU利用率
• 系统吞吐量：表示单位时间内CPU完成作业的数量。
• 周转时间：指从作业提交到作业完成所经历的时间。
• 等待时间
• 响应时间：从用户提交请求到系统首次产生响应所用的时间。

2.3.进程调度的方式

• 非抢占调度方式：只能由当前运行的进程主动放弃CPU。
• 抢占调度方式：可由操作系统剥夺当前进程的CPU使用权。

2.4.经典调度算法

（1）先来先服务（FCFS）调度算法： 按照到达的先后顺序调度。

（2）短作业优先（SJF）调度算法： 每次调度时选择当前已经到达且运行时间最短的作业/进程。 （会导致饥饿现象）

（3）优先级调度算法： 适用于实时操作系统，可能发生饥饿现象。

• 静态优先级：在创建进程时确定的，且在进程的整个运行期间保持不变。
• 动态优先级：在进程运行过程中，根据进程情况的变化动态调整优先级。
• 优先级

1. 系统进程>用户进程
2. 交互型进程>非交互型进程（或前台进程>后台进程）
3. I/O型进程>计算型进程

（4）高响应比优先调度算法（非抢占式调度算法）： 响应比=（等待时间+要求服务时间）/  要求服务时间。

（5）时间片轮转调度算法： 适用于分时系统。

（6）多级队列调度算法

（7）多级反馈队列调度算法

• 设置多个就绪队列，并为每个队列赋予不同的优先级。
• 各队列的进程运行时间片的大小各不相同，优先级越高的队列中，每个进程的时间片就越小。
• 每个队列都采用FCFS算法。
• 按队列优先级调度。

3.同步与互斥

3.1.同步与互斥的基本概念

（1）临界资源

• 进入区：设置正在访问临界区的标志。
• 临界区：进程中访问临界资源的那段代码。
• 退出区：将正在访问临界区的标志驱除。
• 剩余区：代码中的其余部分。

（2）同步

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

（3）互斥： 也称间接制约关系。

3.2.实现临界区互斥的基本方法

（1）软件实现方法

• 单标志法（违背“空闲让进”）
• 双标志法先检查（违背“忙则等待”）
• 双标志法后检查（违背“空闲让进”、“有限等待”，导致饥饿现象）
• Peterson’s Algorithm（违背“让权等待”）

（2）硬件实现方法

• 中断屏蔽方法：不适合多处理机，只用于操作系统内核进程。
• 硬件指令方法

1. TestAndSet指令：执行该代码时不允许被中断。
2. Swap指令：交换两个字（字节）的内容。

3.3.互斥锁（通常采用硬件机制来实现）

3.4.信号量

• wait(S)：P操作
• signal(S)：V操作
• 利用信号量实现同步：必须保证“一前一后”执行两个操作。

1. 在“前操作”之后执行V(S)
2. 在“后操作”之前执行P(S)

• 利用信号量实现进程互斥：临界区之间执行P操作，临界区之后执行V操作。
• 利用信号量实现前驱关系
• 对于不同的临界资源需要设置不同的互斥信号量。

3.5.管程

• 管程的名称
• 局部于管程内部的共享数据结构说明。
• 对该数据结构进行操作的一组过程（或函数）–管程内的过程。
• 对局部于管程内部的共享数据设置初始值的语句。

3.6.经典同步问题

• 生产者-消费者问题：实现互斥的P操作需在实现同步的P操作之后。
• 读者-写者问题
• 哲学家进餐问题
• 吸烟者问题

4.死锁

4.1.死锁的定义

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

4.2.死锁产生的原因

• 系统资源的竞争
• 进程推进顺序非法
• 信号量使用不当

4.3.死锁产生的必要条件

• 互斥条件
• 不剥夺条件
• 请求并保持条件
• 循环等待条件

4.4.死锁的处理策略

（1）死锁预防

• 破坏互斥条件
• 破坏不剥夺条件
• 破坏请求并保持条件：采用预先静态分配方法
• 破坏循环等待条件：采用顺序资源分配法

（2）死锁避免：银行家算法

（3）死锁的检测及解除

• 资源分配图
• 死锁定理
• 死锁解除

1. 资源剥夺法
2. 撤销进程法
3. 进程回退法

三.内存管理

1.内存管理概念

1.1.内存管理的主要功能

• 内存空间的分配与回收
• 地址转换
• 内存空间的扩充
• 内存共享
• 存储保护

1.2.程序的链接与装入

• 静态链接
• 装入时动态链接
• 运行时动态链接
• 内存装入模块装入内存方式

1. 绝对装入
2. 可重定位装入
3. 动态运行时装入

1.3.逻辑地址与物理地址

1.4.进程的内存映像

• 代码段
• 数据段
• 进程控制块
• 堆
• 栈

1.5.内存保护

• 在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址。
• 采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护。

1.6.内存共享

1.7.内存分配与回收

2.覆盖与交换

• 覆盖：内存中能更新的地方只有覆盖区的段，不在覆盖区中的段会常驻内存（对用户不透明）。
• 交换：把处于等待状态的程序从内存移到辅存，把准备好竞争CPU运行的程序从辅存移到内存。

3.连续分配管理方式（为用户程序分配一个连续的内存空间）

3.1.单一连续分配

• 无外部碎片，仅有一道用户程序。

3.2.固定分区分配

• 无外部碎片，用于多道程序存储管理方式。

3.3.动态分区分配

• 首次适应算法：空闲分区以地址递增的次序链接。
• 邻近适应算法：分配内存时从上次查找结束的位置开始继续查找。
• 最佳适应算法：空闲分区按容量递增的次序形成空闲分区链。（会产生外部碎片）
• 最坏适应算法：空闲分区以容量递减的次序链接。

4.基本分页存储管理（一维）

4.1.页面和页面大小

• 进程中的块称为页或页面。
• 内存中的块称为页框、页帧、内存块、物理块或物理页面。
• 外存中的块称为块或盘块。

4.2.地址结构

• 页号P
• 页内偏移量W

4.3.页表：记录页面在内存中对应的物理块号，一般存放在内存中。

• 由页表项组成

1. 页号
2. 物理内存中的块号

4.4.地址变换机构

• 将逻辑地址转换为内存中的物理地址。

4.5.具有块表的地址变换机构

4.6.两级页表

5.基本分段存储管理（二维）

5.1.分段：按照用户进程中的自然段划分逻辑空间。

• 段号S
• 段内偏移量W

5.2.段表

5.3.地址变换机构

5.4.段的共享和保护

• 存取控制保护
• 地址越界保护

6.段页式管理（二维）

6.1.段号

6.2.页号

6.3.页内偏移量

6.4.段表（只有一个）：由段表表项组成

• 段号
• 页表长度
• 页表始址

6.5.页表（可能有多个）：由页表表项组成

• 页号
• 块号

7.虚拟内存管理

7.1.虚拟存储的基本概念

（1）局部性原理

• 时间局部性： 程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。（产生原因是程序中存在着大量的循环操作）
• 空间局部性： 一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

（2）虚拟存储器的特征

• 多次性
• 对换性
• 虚拟性

7.2.请求分页管理方式（系统必须提供一定的硬件支持）

（1）页表机制

• 页号
• 物理块号
• 状态位P
• 访问字段A
• 修改位M
• 外存地址

（2）缺页中断机构

（3）地址变换机构

7.3.页框分配

（1）驻留集：给一个进程分配的物理页框的集合

（2）内存分配策略

• 固定分配局部置换
• 可变分配全局置换
• 可变分配局部置换

7.4.页面置换算法

• 最佳（OPT）置换算法
• 先进先出（FIFO）页面置换算法
• 最近最久未使用（LRU）置换算法
• 时钟（CLOCK）置换算法

7.5.抖动和工作集

• 抖动
• 工作集：指在某段时间间隔内，进程要访问的页面集合。

四.文件管理

1.文件系统基础

1.1.文件的基本概念：文件是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。

• 数据项
• 记录
• 文件

1.2.文件控制块和索引节点

（1）文件的属性

• 名称
• 类型
• 创建者
• 所有者
• 位置
• 大小
• 保护：对文件进行保护的访问控制信息。
• 创建时间、最后一次修改时间和最后一次存取时间。

（2）文件控制块（FCB）

• 基本信息
• 存取控制信息
• 使用信息

（3）索引结点

• 磁盘索引结点
• 内存索引结点

1.3.文件的操作

• 创建文件
• 写文件
• 读文件
• 重新定位文件
• 删除文件
• 截断文件
• 文件的打开与关闭

1.4.文件保护

• 口令保护
• 加密保护
• 访问控制：用于控制用户对文件的访问方式

1.5.文件的逻辑结构

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

（2）有结构文件（记录式文件）

• 顺序文件
• 索引文件
• 索引顺序文件
• 直接文件或散列文件

1.6.文件的物理结构

（1）连续分配：支持顺序访问和直接访问。

（2）链接访问（离散分配方式）

• 隐式链接（不支持随机访问）
• 显示链接（支持随机访问和顺序访问）

（3）索引分配（支持随机访问和直接访问）

• 链接方案
• 多层索引
• 混合索引

（4）混合索引分配

• 直接地址
• 一次间接地址
• 多次间接地址

2.目录

2.1.目录的概念：FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。

2.2.目录结构

• 单级目录结构（文件不允许重名）
• 两级目录结构（不能对文件分类）

1. 主文件目录（MFD）
2. 用户文件目录（UFD）

• 树形目录结构（不便实现文件共享）
• 无环图目录结构（实现了文件共享）

2.3.文件共享

• 基于索引结点的共享方式（硬链接）：多个指针指向一个索引结点，保证只要还有一个指针指向索引结点，索引结点就不能删除。
• 利用符号链实现文件共享（软链接）：把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。
• 建立符号链接时，引用计数值直接复制；建立硬链接时，引用计数值加1。

3.文件系统

3.1.文件系统结构

• I/O控制
• 基本文件系统
• 文件组织模块
• 逻辑文件系统

3.2.文件系统布局

（1）文件系统在磁盘中的结构

• 主引导记录
• 引导块
• 超级块
• 文件系统中空闲块的信息，可使用位示图或指针链接的形式给出。

（2）文件系统在内存中的结构

• 内存中的安装表
• 内存中的目录结构的缓存包含最近访问目录的信息。
• 整个系统的打开文件表
• 每个进程的打开文件表

3.3.外存空闲空间管理

（1）空闲表法（连续分配方式）

（2）空闲链表法

• 空闲盘块链
• 空闲盘区链

（3）位示图法

• “0”表示对应的盘块空闲。
• “1”表示已分配。

（4）成组链接法

3.4.虚拟文件系统

（1）Linux抽象四种对象类型

• 超级块对象
• 索引结点对象
• 目录项对象
• 文件对象

（2）分区和安装

五.输入/输出（I/O）管理

1.I/O管理概述

1.1.I/O设备

• 块设备：信息交换以数据块为单位。
• 字符设备：信息交换以字符为单位。
• 低速设备：鼠标、键盘。
• 中速设备：激光打印机。
• 高速设备：磁盘机、光盘机。

1.2.I/O接口（位于CPU与设备之间）

（1）设备控制器与CPU接口

• 数据线
• 地址线
• 控制线

（2）设备控制器与设备的接口

（3）I/O逻辑：用于实现对设备的控制。

1.3.I/O端口：指设备控制器中可被CPU直接访问的寄存器。

• 数据寄存器
• 状态寄存器
• 控制寄存器

1.4.I/O 控制方式

（1）程序直接控制方式

（2）中断驱动方式

（3）DMA方式

（4）通道控制方式

• I/O通道指专门负责输入/输出的处理机（硬件）。
• 一个通道可控制多个设备控制器，每个设备控制器可以控制多个设备。
• 通道与CPU共享内存。

1.5.I/O软件层次结构

• 用户层I/O软件（实现与用户交互的接口）
• 设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备的保护及设备的分配与回收。
• 设备驱动程序（每类设备配置一个）：与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。
• 中断处理程序：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程。

1.6.应用程序I/O 接口

• 字符设备接口
• 块设备接口
• 网络设备接口
• 阻塞/非阻塞I/O

2.设备独立性软件

2.1.高速缓冲与缓冲区

（1）磁盘高速缓存

（2）缓冲区

• 单缓冲
• 双缓冲
• 循环缓冲
• 缓冲池

1. 空缓冲队列
2. 装满输入数据的缓冲队列（输入队列）
3. 装满输出数据的缓冲队列（输出队列）

2.2.设备分配与回收

（1）设备分配

• 独占式使用设备
• 分时式共享使用设备
• 以SPOOLing方式使用外部设备（实现了对设备的I/O操作的批处理）

（2）设备分配的数据结构

• 设备控制表（DCT）
• 控制器设备表（COCT）
• 通道控制表（CHCT）
• 系统设备表（SDT）：整个系统只有一张。

2.3.SPOOLing技术（假脱机技术）

• 输入井和输出井（在磁盘中开辟两个存储区域）
• 输入缓冲区和输出缓冲区
• 输入进程和输出进程
• 特点

1. 提高了I/O的速度
2. 将独占设备改造为共享设备
3. 实现了虚拟设备功能

3.磁盘和固态硬盘

3.1.磁盘的管理

• 磁盘初始化
• 引导块
• 分区
• 坏块

3.2.磁盘调度算法

• 寻找时间Ts
• 旋转延迟时间Tr
• 传输时间Tt
• 先来先服务（FCFS）算法
• 最短寻找时间优先（SSTF）算法：会产生“饥饿”现象。
• 扫描（SCAN）算法（电梯调度算法）
• 循环扫描（C-SCAN）算法

3.3.固态硬盘（SSD）