操作系统初识

OS 基本概念

操作系统是控制软件

• 管理应用程序
• 为应用程序提供服务
• 分配资源
  • CPU (CPU 调度、进程、线程)
  • 内存 (物理内存、虚拟内存)
  • 磁盘 (文件系统)
• 管理外设

并发、并行

• 并发(concurrent)，在一段时间内多个程序交替运行
• 并行(parallel), 在一个时间点上有多个程序同时运行

启动、中断、异常、系统调用

启动

BIOS： Basic Input Output System， 一组固化到 ROM 上的程序，是计算机启动时加载的第一个程序

BIOS 启动固件 作用

• 基本输入输出程序

• 系统设置信息

• 开机后自检程序

• 系统自动程序(BIOS)

  将加载程序从磁盘的引导扇区(512 字节)加载到 0x7c000,之后跳转到 0x7c00

加载程序(bootloader)

将操作系统代码、数据从硬盘加载到内存，并跳转到操作系统起始地址

中断、异常、系统调用

• 中断(hardware interrupt)， 来自硬件设备的处理请求； 异步响应
• 异常(exception)，非法指令或其他原因导致当前指令执行失败； 同步响应
• 系统调用(system call)， 应用程序主动向操作系统发出的服务请求； 异步或同步

中断（中断、异常、系统调用）处理机制

• 硬件处理，在 CPU 初始化时 设置 中断使能标志；
  • 依据内部或外部事件设置中断标志
  • 依据 中断向量表 调用相应中断服务例程
• 软件
  • 现场保存 (编译器)
  • 中断服务处理 (服务例程)
  • 清除中断标记 (服务例程)
  • 现场恢复 (编译器)

中断嵌套

• 硬件中断服务可被打断

  • 不同硬件的中断源可能在硬件中断处理时出现
  • 硬件中断服务例程中 需要 临时禁止中断请求
  • 中断请求会保持到 CPU 做出响应

• 异常服务例程 可被 打断、嵌套

  • 异常服务例程执行时 可能出现硬件中断
  • 异常服务例程可能出现缺页

系统调用的实现

• 每个系统调用对应一个系统调用号， 系统调用接口根据系统调用号来维护表的索引

• 系统调用接口调用内核态中的系统调用功能实现，并返回系统调用的状态和结果

• 用户不需要知道系统调用的实现， 仅需设置调用参数和获取返回结果

函数调用、系统调用 差异

• 系统调用
  • INT和 IRET指令
  • 发生 堆栈切换、特权级 转换
• 函数调用
• • CALL 和 RET 指令
  • 没有 堆栈切换

中断、异常、系统调用的开销

• 引导机制
• 建立内核堆栈
• 验证参数
• 内核态映射到用户态的地址
• 内核态独立地址空间

内存管理(物理内存) - 连续分配

内存的层次结构

• CPU 内部 包含 ALU(算术逻辑单元)、MMU(内存管理单元)、寄存器、cache,其容量小， 访问速度快。

• 主存(物理内存)，存放操作系统和各应用，通过 交换/分页和 磁盘交互，将永久保存的数据放到磁盘中(虚拟内存)

  

操作系统的内存管理

• 抽象，逻辑地址空间

• 保护，独立地址空间

• 共享，访问相同内存

• 虚拟化，更大的地址空间

操作系统的内存管理方式

目前多数操作系统采用 按需页使虚拟存储

• 重定位(relocation)
• 分段(segmentation)
• 分页(paging)
• 虚拟存储 (virtual memory)

地址空间

• 物理地址空间， 硬件支持的地址空间，起始地址 0， 到 MAX_sys
• 逻辑地址空间，在 CPU 运行的进程中看到的地址，起始地址 0， 到 MAX_prog ， 通过映射关系，落在物理空间上。
• 逻辑地址生成过程：
  • C 程序通过编译、汇编、链接 link、载入（重定位）生产可执行文件，将逻辑地址映射到物理空间上。
  • C 程序中函数的位置(入口)，变量名就是逻辑地址，
  • 编译后(.o 文件)起始地址为 0，把变量名和函数名转为相应的从 0 开始的连续逻辑地址
  • link 把多个.o 文件和成一个，存放在硬盘中，通过 loader 应用程序把可执行文件载入内存中执行，这里有分配地址空间和映射(偏移)的过程
• 物理地址生产过程：
  • CPU 执行指令，ALU 需要逻辑地址的内存内容，发生请求、传递参数，参数就是逻辑地址
  • 查表，根据 CPU 中 MMU，查表 将 逻辑地址 转换为 物理地址
  • 找到后 CPU 给内存发请求，请求一个物理地址
  • 内存会通过总线把内容传递给 CPU，CPU 执行指令

地址生成时机和限制

• 编译时

  • 假设起始地址已知；
  • 如果起始地址改变，必须重新编译

• 加载时

  • 如果编译时起始位置未知，编译器需生成可重定位的代码；

  • 加载时，生成绝对地址

• 执行时

  • 执行时代码可移动
  • 需要地址转换（映射）硬件支持

连续内存分配

给进程分配一块不小于指定大小的连续的物理内存区域

• 内存碎片， 空闲内存不能被利用
  • 外部碎片，分配单元之间的未被使用内存
  • 内部碎片，分配单元之内的未被使用内存，取决于分配单元大小是否要取整

动态分区的分配策略

• 最先匹配(First Fit Allocation)，分配 n 个字节，使用第一个可用的空间比 n 大的空闲块

  原理/实现

  • 空闲分区列表按 地址顺序排序
  • 分配过程时，搜索一个合适的分区
  • 释放分区时，检查是否可与临近的空闲分区合并

  优、缺点

  • 简单、在高地址空间有大块的空闲分区
  • 外部碎片，分配大块时较慢

• 最佳匹配(Best Fit Allocation), 分配 n 个字节，查找并使用不小于 n 的最小空闲分区

  原理/实现

  • 空闲分区列表按大小排序
  • 分配时，查找合适分区
  • 释放时，查找并合并临近的空闲分区

  优缺点

  • 大部分分配的尺寸较小时，效果很好； 可避免大的空闲分区被拆分；可减小外部碎片的大小
  • 产生外部碎片，释放分区较慢，容易产生很多无用的小碎片

• 最差匹配(Worst Fit Allocation)， 分配 n 个字节，使用尺寸不小于 n 的最大空闲分区

  原理/实现

  • 空闲分区列表按由大到小排序
  • 分配时，选最大的分区
  • 释放时，检查是否可与临近的空闲分区合并，并调整空闲分区列表顺序

  优缺点

  • 中等大小的分配较多时，效果最好， 避免出现太多的小碎片
  • 释放分区慢，产生外部碎片，容易破坏大的空闲分区，导致后续难以分配大的分区

碎片整理

通过调整进程占用的分区位置来减少/避免分区碎片

• 碎片紧凑(compaction)
  • 通过移动分配给进程的内存分区，以合并外部碎片
  • 条件： 所有的应用程序可动态重定位
  • 问题：， 何时移动？ 开销？
• 分区对换(swapping in/out),
  • 通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
  • 问题：换哪个程序？开销？

内存管理(物理内存) - 非连续分配

连续分配有缺点

• 分配给程序的物理内存必须连续
• 存在碎片(外部、内部)
• 内存分配的动态修改困难
• 内存利用率教低

非连续分配

分配给一个程序的物理空间是非连续，提高内存利用效率和管理灵活性

优点

• 允许共享代码和数据
• 支持动态加载和动态链接

缺点

• 有额外的管理开销， 要建立虚拟地址和物理地址之间的转换

如何实现虚拟地址和物理地址的转换？

• 软件实现(灵活、开销大)
• 硬件实现(够用，开销小)

段式存储管理

段的概念

• 表示访问方式和存储数据等属性相同的一段地址空间
• 其对应一个连续的内存块
• 若干个段组成进程逻辑地址空间

段访问

• 段基址 + 段内偏移

• 逻辑地址由二元组(s, addr)表示， s 段号， addr，段内偏移

页式存储管理

页帧（帧、物理页面 Frame）

• 将物理地址空间划分为大小相同的基本分配空间单位
• 2 的 n 次方，如 512，4096
• 内存物理地址的表示，二元组(f,o) = f * 2^S + o
  • f, 帧号，F 位，共有 2^F 个 帧
  • o，帧内偏移，S 位， 每帧有 2^S 字节

页面（页、逻辑页面 Page）

• 将逻辑地址空间也划分为相同大小的基本分配单位

• 帧、页 大小必须是相同的

• 进程中的逻辑地址的表示，二元组(p,o) = p*2^S + o

  • p ,页号 (P 位， 2^P 个页)
  • o, 页内偏移(S 位， 每页有 2^S 字节)

页到帧的转换 （地址映射）

• 逻辑地址到物理地址的转换

• 页表， 保存了逻辑地址到物理地址之间的映射关系

• MMU、TLB

• 逻辑地址中的页号 是连续的，物理地址中的帧号是不连续的

• 不是所有的页都有对应的帧，缺页

  具体过程： 首先 CPU 得到逻辑地址，逻辑地址分块，一块表示页号，一块表示页内偏移。通过查找页表，页表的索引就是页号，内容是帧号。帧号+偏移，就是物理地址，找到对应的内存空间

页表

每个进程都有一个页表

• 每个页表对应一个页表项

  • 页表项标志
    • 存在位 (resident bit)
    • 修改位 (dirty bit)
    • 引用位 (clock/reference bit)

• 其随进程运行状态而动态变化

• 页表基址寄存器(PTBR， Page Table Base Register)

页式存储管理机制的性能问题

• 内存访问性能， 访问一个内存单元需要 2 次内存访问
  • 第一次，获取页表项
  • 第二次，访问数据
• 页表 大 小 ，可能非常大
• 如何 处理？ 缓存、间接访问

快表(TLB，Translation Look-aside Buffer)

快表是一种高速缓冲存储器，用缓冲近期访问的页表项

过程

• 根据逻辑地址推算出目标页表项的索引，查询快表
  • 若命中，则结合逻辑地址的低若干位推算出最终物理地址
  • 若没有命中，则去查页表并更新对应的页表项到 TLB 中
  • 当 TBL 被写满又有新的页表项要写进来，则按照策略擦除快表中的一个旧页表项

间接访问，多级页表

通过间接引用将页号分成 k 级，使等将对一个大地址范围的寻址分为对几个小的页表的寻址

优点：可离散存储，进程中未使用的页暂存时可以不用为其建立页表，只有在进程实际需要一个页表时才给该页表分配内存

大地址空间问题？

逻辑地址空间增长速度快于物理地址空间

思路， 不让页表与逻辑地址空间的大小相对应，让页表与物理地址空间的大小相对于

• 页寄存器(Page Registers)

  每个帧 与 一个 页寄存器 管理，寄存器内容包括:

  • 使用位， 此帧是否 被 进程占用
  • 占用页号，对应的页号 p
  • 保护位

  示例

  物理内存大小： 4096 _ 4096 = 4K_ 4K = 16 MB

  页面大小： 4096 bytes = 4KB

  页帧数： 4096

  页寄存器使用的空间(假设每个页寄存器占 8 字节)： 8 * 4096 = 32KB

  则页寄存器带来的开销： 32K/16M = 0.2%

  虚拟内存的大小： 任意

  优点， 本身物理存址小，节省空间，不再是每个进程都要页表，整个系统只用 一个

  缺点， 需求高，需要软硬件配合，有冲突

• 反置页面

  基于 HASH 映射值查找对应页表项中的帧号

段页式存储管理

在端式存储的基础上，给每个段 加 一级页表

逻辑地址： 段号 + 若各个页号 + 页内偏移

物理地址：帧号 + 页内偏移

内存共享，通过指向相同的页表基址，实现进程间的端共享

虚拟存储

覆盖技术

在较小的可用内存中运行较大的程序

• 依据程序逻辑结构，将程序划分为若干功能相对独立的模块
• 将不会同时执行的模块共享同一块内存区域
• 必要、常用功能的代码和数据 常驻内存
• 可选，不常用功能，只在需要时装入 内存
• 不存在调用关系的模块 可相互 覆盖，共用同一块内存区域

交互技术

增加正在运行或需要运行的程序的内存

• 将暂时不用运行的程序放到外存

• 换入换成的基本单位，整个进程的地址空间

局部性原理

程序在执行过程的一个较短时期，所执行的指令的地址，指令的操作数地址都局限于一定区域；

存在时间、空间、分支局限性；

局部性原理的意义：该原理表明 理论上虚拟存储技术是可以实现的

虚拟存储技术

物理内存+ 磁盘 = 虚拟存储

• 只把部分程序放到内存中，从而运行比物理内存大的程序，有操作系统自动完成
• 实现进程在内存和外外存直接的交换，从而获得更多的空闲内存空间

原理：

• 在装入程序时，只把当前指令执行需要的部分页、段装入内存
• 当执行到指令或数据不存在时(缺页、缺段异常)，处理器通知操作系统将相应的页、段调入内存
• 操作系统将内存中暂时不用的页、端保存到外存

实现方式：

• 虚拟页式存储
• 虚拟段式存储

基本特征：

• 不连续性
  • 物理内存 分配 非连续
  • 虚拟地址空间 使用 非连续
• 大用户空间， 提供给用户的虚拟内存 可 大于 时间的物理内存
• 部分交换，只对部分虚拟地址空间进行 调入 和 调出

技术支持：

• 硬件，页式或短时存储中 地址转换机制
• 操作系统，管理内存和外存 间 页、端的换入、换出

虚拟页式存储管理

在页式存储管理的基础上，增加 请求调页 、页面置换

思路

• 当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行
• 进程在运行中发现有需要的代码或数据不在内存时，想系统发出缺页异常请求
• 操作系统在处理缺页异常时，将外存中相应的页面调入内存，使得进程能继续运行

虚拟页式存储中 页表项 结构

驻留位： 表示该页面是否在内存； 1 在 内存，0 在外存，访问时缺页异常

修改位： 表示在内存中的该页是否被修改过； 回收物理页面时据此决定是否把内容写会外存

访问位：表示该页面是否被访问过(读、写)，被访问过设置为 1

保护位：表示该页面的允许访问方式，只读、可读写、可执行等

缺页异常的处理流程

1、如果在内存中有空闲的物理空间，则分配一个物理页帧 f，然后转至 5，否则 2

2、采用某种页面置换算法，选择一个被替换的物理页帧，其对应的逻辑页为 q，（如果没修改过可直接释放，如果修改位是 1，则要写会外存）

3、如果 q 被修改过，则把它写回外存

4、把 q 对应页面驻留位设置为 0

5、把需要访问的页面 p 装入物理页面 f 中

6、修改 p 对应页表项，驻留位设置 1，物理页帧设置为 f

7、重新执行产生缺页的指令

页面置换算法

当出现缺页异常，需要调入新的页面而内存已满时，置换算法选择被置换的物理页面

目标：

• 尽可能减少页面的调入调出次数
• 把未来不再访问或短期内不访问的页面调出

页面锁定（frame locking）

• 描述 必须 常驻内存的逻辑页面
• 操作系统的关键部分
• 要求响应速度的代码和数据
• 页表中的锁定标志位

局部页面置换算法

置换页面的选择范围 仅限于 当前进程占用的物理页面内

• 最优页面置换算法(OPT)
  • 思路：未来最长时间不访问的页面 作为置换页面
  • 实现： 缺页时，计算内存中每个逻辑页面的下一次访问时间，选择未来最长时间不访问的页面
  • 特征： 理想情况，OS 无法实现
• 先进先出算法(FIFO)
  • 思路： 选择在内存驻留时间最长的页面进行置换
  • 实现： 维护一个记录所有位于内存中的逻辑页面，链表元素按驻留内存的时间排序，链首最长，链尾最短；出现缺页时，置换链首页面，新页面添加值链尾
  • 特征： 性能差，调出的页面可能是常用页面； 出现 Belady 现象
• 最近最久未使用算法(LRU)
  • 思路： 选择最长时间没被引用的页面进行置换；如果某些页面长时间未被访问，则它在将来还可能长时间不会访问
  • 实现：
    • 维护一个按最近一次访问时间排序的链表，链首是最近刚刚访问的页面，链尾是最久为使用的页面
    • 访问内存时，找到相应页面，并把它移到链首
    • 缺页时，置换链表尾节点的页面
  • 特征： 最优置换算法的一种 近似， 开销比较大
• 时钟页面置换算法(Clock)
  • 思路： 仅对页面的访问情况进行大致统计； 在页表项增加 访问位，描述页面在过去一段时间的内存访问情况
  • 实现：
    • 各页面组成环形链表，指针指向最先调入的页面
    • 访问页面时，在页表项纪录页面访问情况， 访问位 1 (初始时 0)
    • 缺页时，从指针处开始顺序查找 未被访问的页面进行置换
      • 从指针当前位置顺序检查环形链表
      • 访问位 为 0 ， 则置换该页面
      • 访问位 为 1，则 置为 0，指针移动到下一个页面，直到找到可置换的页面 ∫
  • 特征： 是 LRU 和 FIFO 的折中
• 最不常用算法(LFU)
  • 思路：选择页面访问次数最少的页面
  • 实现： 对每个页面设置访问计数器，当一个页面被访问+1,置换数值最小的页面
  • 特征： 开销，硬盘计数器开销，排序查找开销

Belady 现象

采用 FIFO 算法时，可能出现分配的物理页面增加，缺页次数反而升高的异常现象

LRU、FIFO、CLock 算法比较

• LRU 和 FIFO 本质上都是先进先出的思路
  • LRU 依据 页面的 最近访问时间排序， 需要动态的调整顺序
  • FIFO 依据 页面 进入 内存的时间排序，是固定不变的
• LRU 可 退化 成 FIFO， 页面进入内存后没被访问，最近访问时间 与 进入内存的时间 相同
• LRU 算法性能较好，但系统开销大
• FIFO 系统开销较小，但会发生 Belady 现象
• Clock 是它们的折中
  • 页面访问时，不动态调整页面的在链表中的顺序，仅做标记
  • 缺页时，再把它移动到链表末尾
  • 对应 未被访问的页面，Clock 和 LRU 算法表现的一样好
  • 对于被 访问过的页面，Clock 算法 不能记录 准确访问顺序，而 LRU 算法可以

全局页面置换算法

置换页面的选择范围 是 所有可换出的 物理页面

进程在不同阶段的内存需求是变化的，分配给进程的内存也需要在不同阶段有所变化

• 工作集算法

  • 思路： 换出不在工作集中的页面
  • 实现：
    • 访问链表，维护窗口内的访存页面链表
    • 在防存时，换出不在工作集的页面，缺页时，换入页面，更新访存链表

  工作集

  一个进程当前使用的逻辑页面集合，用二元函数 w(t,Δ)，t 是当前时刻，Δ 是工作集窗口，一个定长的页面访问的时间窗口。t+Δ 构成一个时间段，w(t,Δ)就是在当前时刻 t 之前的 Δ 时间内所有访问页面组成的集合，在随 t 不断更新。

  在进程开始后，随着访问新页面逐步建立起较稳定的工作集

  常驻集

  在当前时刻，进程实际驻留在内存当中的页面集合

• 缺页率算法

  缺页率： 缺页次数/内存访问次数= 1/缺页的平均时间间隔

  • 思路： 动态调整常驻集的大小； 若缺页率高则增加工作集来分配更多的物理页面，过低则减少工作集来减少其物理页面。

抖动和负载控制

抖动：如果分配给一个进程的物理页面太少，常驻集远小于工作集，则缺页率很大，频繁在内外存之间替换页面，使进程的运行慢，此状态为”抖动”

产生抖动原因： 随着驻留内存的进程数目增加，分配给每个进程的物理页面数据不断减少，缺页率上升。因此 OS 要选择一个适当的进程数目和进程需要的帧数，在并发和缺页率之间达到平衡。

负载控制： 通过调节并发进程数来进行系统负载控制。平均缺页间隔时间 = 缺页异常处理时间

进程

进程定义

一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程

只有当一个程序被 OS 加载到内存中，cpu 对其执行时，这个过程是动态的，称为进程

进程的组成

进程包含了正在运行的一个程序的所有状态信息

• 代码
• 数据
• 状态寄存器
• 通用寄存器
• 进程占用系统资源

进程特点

• 动态性，动态的创建、结束进程
• 并发性，可并独立调用并占用处理机运行
• 独立性，不同进程的工作相互独立
• 制约性，因访问共享数据、资源，或进程间同步 而产生制约

进程与程序的联系

• 进程是操作系统处于执行状态程序的抽象
• 进程 = 执行中的程序 = 程序(静态文件) + 执行状态
• 同一个程序的多次执行过程对应不同进程
• 进程执行需要资源，内存（保存代码、数据），CPU(执行指令)

进程控制块 (PCB，Process Control Block)

• 操作系统管理控制进程运行所用的信息集合
  • 操作系统用 PCB 来描述 进程的基本情况 以及 运行变化的过程
  • PCB 是 进程存在的唯一标志

PCB 三大类信息

• 进程标识，本进程标识、父进程标识、用户标识
• 处理机状态保存，保存进程的现场信息，主要是寄存器
• 进程控制信息
  • 调度和状态信息，调度进程、处理机使用情况
  • 进程间通信信息，通信相关的各种标识、信号
  • 存储管理信息，指向本进程映像存储空间的数据结构，内存信息
  • 进程所用资源， 打开使用的系统资源
  • 有关数据结构连接信息，与PCB 相关的进程队列

PCB 组织方式

• 链表，同一状态的进程其 PCB 成一链表，多个状态对应多个不同的链表；如 就绪链表、阻塞链表
• 索引表，同一状态的进程归入一个索引表(由索引执行 PCB)，多个状态对应多个不同的索引表

进程生命周期

• 创建

  引起进程创建情况

  • 系统初始化
  • 用户请求创建一个新进程
  • 正在运行的进程执行了创建进程的系统调用

• 执行

  内核选择一个就绪的进程，让它占用处理机并执行

• 等待

  进入等待的情况

  • 请求并等待系统服务，无法马上完成
  • 启动某种操作，无法马上完成
  • 需要的数据没有到达

• 抢占

  进程抢占的情况

  • 高优先级进程就绪
  • 进程执行当前时间用完

• 唤醒

  唤醒进程情况

  • 被阻塞进程需要的资源被满足
  • 被阻塞进程等待的事件到达

  进程只能被别的进程或操作系统唤醒

• 结束

  进程结束情况

  • 正常退出
  • 错误退出
  • 致命错误
  • 被其他进程杀死

进程挂起

处于挂起状态的进程映像在磁盘上，以减少进程占用的内存

挂起状态

• 等待挂起状态(Blocked-suspend)，进程在外存 并等待某事件的出现
• 就绪挂起状态(Ready-suspendReady-suspend)，进程在外存，但只要进入内存即可运行

挂起状态转换

• 从内存转到外存
  • 等待 -> 等待挂起， 没有进程处于就绪状态，或就绪进程 要求更多内存资源
  • 就绪 -> 就绪挂起，当有高优先级等待进程（系统认为会很快就绪的）和低优先级就绪进程
  • 运行 -> 就绪挂起，对抢占式分时系统，当有高优先级等待挂起进程因事件出现而进入就绪挂起
• 在外存时的状态转换
  • 等待挂起 -> 就绪挂起， 有等待挂起进程 因相关事件出现
  • 激活， 外存到内存，需要运行该进程时
  • 就绪挂起 -> 就绪，没有就绪进程，或 挂起就绪进程高于 就绪进程
  • 等待挂起 -> 等待， 当一个进程释放足够内存，并有高优先级等待挂起进程

状态队列

由操作系统维护一组队列，表示系统中所有进程的当前状态

不同队列表示不同状态

线程

线程概念

线程是进程的一部分，描述指令流 执行状态。它是进程中的指令执行流 的最小单元，是CPU 调度的基本单位

线程 = 进程 - 共享资源

线程优缺点

• 一个进程中可同时存在多个线程
• 各个线程之间可以并发执行
• 各个线程之间可共享地址空间和文件等资源
• 一个线程崩溃，会导致其所属进程的所有线程崩溃

线程、进程 比较

• 进程是资源分配单位，线程是 CPU 调度单位
• 进程拥有一个完整的资源平台，线程只独享指令流执行的必要资源，如寄存器、栈
• 线程能减少并发执行的时间（切换时间短，能直接通信）和空间开销(共享内存和文件资源)

进程控制

进程切换(上下文切换)

切换时机

• 暂停当前运行状态，从运行状态变成其他状态
• 调度另一个进程，从就绪状态变成运行状态

进程切换要求

• 切换前，保存进程上下文
• 切换后，恢复进程上下文
• 要快速切换
• 保存进程生命周期信息(寄存器、CPU 状态、内存地址空间)

进程控制块 PCB

• 内核为每个进程维护了对应的进程控制块(PCB)
• 相同状态的进程的 PCB 放置在同一队列

进程创建 (fork/exec)

• fork() 复制一个进程，复制父进程信息，创建一个新的子进程。
  • 复制父进程所有变量和内存
  • 复制父进程的所有 CPU 寄存器
  • 子进程的 fork()返回 0
  • 父进程的 fork()返回进程标识符
  • 子进程使用 getpid()获取 PID
• exec() 加载 新程序取代当前运行进程

进程等待和退出

• wait() 用于 父进程等待子进程的结束

  • 子进程 结束 时通过 exit()向父进程返回一个值，父进程通过 wait()接受并处理这个值
  • 有子进程存活时，父进程进入等待状态，等待子进程的返回结果；当子进程调用 exit()时，唤醒父进程，将 exit()返回值作为父进程中的 wait()调用的返回值()
  • 有僵尸子进程等待时，wait()立即返回其中一个值
  • 无子进程存活时，wait()立即返回

• exit(),进程的有序终止

  • 将调用才是作为 进程的”结果”
  • 关闭所有打开的文件等占用资源
  • 释放内存
  • 释放大部分 进程相关的内核数据结构
  • 检查父进程是非存活
    • 存活，保留结果的值 直到 父进程需要它，进入僵尸（zombie）状态
    • 没有，释放所有的数据结构，进程结束
  • 清理所有等待的僵尸进程

处理机调度

• 进程切换，切换 CPU 的当前任务，从一个进程/线程到另一个，保存当前在 PCB/TCB 中的执行上下文，读取下一个的上下文
• CPU 调度，从就绪队列中挑选一个进程/线程作为 CPU 将要运行的下一个进程/线程

调度准则

• CPU 使用率： CPU 处于忙状态的时间百分比
• 吞吐量：单位时间内完成的进程数量
• 周转时间：进程从初始化到结束的总时间
• 等待时间：进程在就绪队列中的总时间
• 响应时间：从提交请求到产生响应所花费的总时间

调度算法

• 先来先服务（FCFS，First Come，First Served)，依据进程进入就绪状态的先后顺序

  • 优点，简单
  • 缺点
    • 平均等待时间波动大，短进程可能排在长进程后面
    • I/O 资源和 CPU 资源利用率低，CPU 密集型进程导致 I/O 设备闲置，反之亦然

• 短进程优先，选择就绪队列中执行时间最短进程 占用 CPU 进入运行状态

  • SPN，Shortest Process Next (短进程)，
  • SJF，Shortest Job First (短作业)
  • SRT，Shortest Remaining Time (短剩余时间)
  • 优点： 具有最优平均周转时间
  • 缺点：
    • 可能导致饥饿，连续的短进程会使长进程无法获得 CPU 资源
    • 需要预知未来，预估 CPU 使用的时间

• 最高响应比优先 (HRRN，Highest Response Ratio Next)

  • R = (等待时间 + 执行时间) / 执行时间
  • 在短进程优先算法的基础上改进，不可抢占，关注进程的等待时间，可防止长进程无限期推迟

• 时间片轮转 (RR， Round Robin)

  • 时间片，分配处理机资源的基本时间单元
  • 开销，额外的上下文切换；
    • 时间片太长，等待时间过长，极限情况下，退化成 FCFS
    • 时间片太小，反应迅速，但产生大量上下文切换，增加开销

• 多级队列(MQ，Multilevel Queues)

  • 就绪队列分为 多个相对独立的队列，调度在队列间进行，每个队列拥有自己的调度策略。如 前台交互，使用 RR，保证响应速率；后台/批处理，使用 FCFS
  • 队列间调度
    • 固定优先级，先前台，再处理后台，可能导致饥饿
    • 时间片轮转，每个队列都等到一个确定的，能够调度其进程的 CPU 总时间。如 80%CPU 时间用于前台，后台 20%

• 多级反馈队列 (MFQ， Multilevel Feedback Queues)

  • 优先级队列中的时间片轮转有动态调整
    • 一个进程可以在不同队列中移动，N 级优先队列
    • 每个队列内部 使用 RR 轮换
    • 时间片大小随优先级增加而增加，若进程在当前时间片没有完成，则降到下一个优先级
    • I/O 幂集型进程 停留 在 高优先级

• 公平共享 (FSS，Fair Share Scheduling)

同步互斥

• 原子操作(Atomic Operation)， 一次不存在任何中断或失败的操作，要么成功，要么操作没执行

• 利用 2 个原子操作实现一个锁

• Lock.Acquire

  • 在锁别释放前一直等到，然后获得锁
  • 如果 2 给线程都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能够获得锁

• Lock.release

进程间交互关系

• 互斥(mutual exclusion)， 一个进程占用资源，其它进程不能使用

• 死锁 (deadlock)，多个进程各占用部分资源，形成循环等待

• 饥饿 (starvation)， 一个进程一直得不到资源，而其它进程可能轮流占用资源

临界区 (Critical Section)

entry section       // 进入区
	cirtical section  // 临界区
exit section        // 退出区
	remainder section

• 临界区，进程中 访问临界资源的一段 需要 互斥执行的代码
• 进入区，检查可否进入临界区的一段代码，如果可，则设置”正在访问临界区”标志
• 退出区，清除”正在访问临界区”标志

临界区访问规则

• 空闲则入，没有进程在临界区，任何进程可进入
• 忙则等待，有进程在临界区，其他进程不能进入
• 有限等待，等待进入临界区的进程 不能无限期等待
• 让权等待，不能进入临界区的进程，应释放 CPU

锁 (抽象的数据结构)

• 一个二进制变量
• Lock::Acquire(), 锁被释放前一直等待，然后得到锁
• Lock::Release()， 锁释放后，唤醒任何等待进程

信号量与管程

信号量(Semaphore)

信号量，是操作系统提供的一种协调共享资源的方法

信号是一种抽象数据结构，由一个整形变量和两个原子操作组成

• P(), sem—, 如果 sem<0,等待，类似 Lock::Acquire()
• V(),sem++, 如果 sem<=0,说明当前有等着的进程，唤醒在信号量上的进程，一个或多个

信号量分类

• 二级制信号量，约等于锁，取值 0，1
• 资源信号量，资源数目为任何 非负值

用信号量解决生产-消费问题

生产者 —> 缓冲区 —> 消费者

• 一个或多个生产者 在生产数据后 放在 一个缓存区 中
• 单个消费者从缓冲区 取出数据
• 任何时刻只能有一个生产者 或消费者 可访问缓冲区 (互斥访问)
• 缓存区空时，消费者必须等待生产者 (条件同步)
• 缓冲区满时，生产者必须等待消费者 (条件同步)

管程

管程，是一种用于多线程互斥访问 共享资源的程序结构。其组成：

• 一个锁，控制管程代码的互斥访问
• 0 或多个条件变量，管理共享数据的并发访问

条件变量

• 进入管程的线程因资源被占用而进入等待状态
• 每个条件变量表示一种等待原因，对应一个等待队列
• Wait()
  • 将自己阻塞在等待队列
  • 唤醒一个等待者或释放管程的互斥访问
• Signal()
  • 将等待队列中的一个线程唤醒
  • 如果等等待队列为空，则等同于 空操作

死锁、进程通信

死锁，一组阻塞的进程，持有一种资源，等待获取另一个进程所占用的资源，而导致谁都无法执行。

死锁必要条件

• 互斥
• 持有并等待
• 无抢占，一个资源只能被进程自愿释放
• 循环等待，形成闭环

死锁处理方法

• 死锁预防(Deadlock Prevention)， 确保系统永远不会进入死锁状态
  • 限制申请方式，任何时刻都不满足死锁的必要条件
    • 互斥 - 把互斥的共享资源 封装 成可同时访问
    • 只有并等待， 进程请求资源时，要求它不持有任何其它资源；允许进程在开始执行时，一次请求所有需要的资源
    • 非抢占，进程请求不能立即分配的资源，则释放已占用资源；只在能够同时获得所有需要资源时，才执行分配操作
    • 循环等待， 对资源排序，要求进程按顺序请求资源
• 死锁避免 (Deadlock Avoidance)，在使用前进行判断，只允许不会出现死锁的进程 请求资源
  • 利用额外的先验信息，在分配资源时判断是否会出现死锁，只在不会死锁时分配资源
    • 要求进程声明需要资源的最大数目
    • 限定提供、分配的资源数量，确保满足进程的最大需求
    • 动态检查 资源分配状态，确保不会出现环形等待
• 死锁检测和恢复(Deadlock Detection & Recovery)，在检查到死锁后，进行恢复
  • 允许系统进入死锁
  • 维护系统的资源分配图
  • 定期调用死锁检测算法 搜索 图中是否存在死锁
  • 出现死锁时，用死锁恢复机制 进行恢复

安全状态

• 系统处于安全状态，一定没有死锁

• 系统处于不安全状态，可能出现死锁

银行家算法

银行家算法是一个避免死锁产生的算法，它以银行借贷分配策略为基础，判断并保证系统处于安全状态

• 客户在第一次申请贷款时，声明所需最大资源量，在满足所有贷款要求并完成项目时，及时归还

• 客户贷款数量不超过银行拥有的最大值时，银行家尽量满足客户需要

• 类比

  • 银行家 - 操作系统
  • 资金 - 资源
  • 客户 - 申请资源的线程

进程通信(IPC， Inter-Process Communication)

• 直接通信，一条链路对应一对通信进程，没对进程间只能有一个链路存在
• 间接通信
  • 通过操作系统维护的消息队列实现进程间的消息
    • 每个消息队列都有一个唯一的标识
    • 只有共享了相同消息队列的进程，才能够通信

共享内存

• 共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制
• 进程，每个进程都

文件系统

文件系统是操作系统中管理持久性数据的子系统，提供数据存储和访问功能

文件是具有符号名，由字节序列构成的数据项集合。 它是文件系统的基本数据单元。文件名是文件的标识符号

文件系统的功能

• 分配文件磁盘空间，管理文件块(位置或顺序)，管理空闲空间，分配算法
• 管理文件集合，定位(文件及其内容)，命名，文件系统结构
• 数据可靠和安全， 安全(多层次保护数据)，可靠

文件头： 文件系统元数据中的文件信息(文件属性、文件存储位置、顺序)

文件描述符

• 内核跟踪进程 打开的所有文件，操作系统为每个进程维护一个打开文件表；文件描述符就是打开文件的标识
• 文件描述符： 操作系统在打开文件表中维护的打开文件状态和信息
  • 文件指针： 最近一次读写位置； 每个进程分别维护自己的打开文件指针
  • 文件打开计数： 当前打开文件的次数， 当最后一个进程关闭文件时，将其从打开文件表中移除
  • 文件的磁盘位置：缓存数据访问信息
  • 访问权限： 每个程序访问模式信息

文件的 用户视图 和 系统视图

用户视图， 持久的数据结构

系统视图， 数据块的集合(块时逻辑存储单元，扇区是物理存储单元)

用户视图 到 系统视图

数据块 是 文件系统中基本操作单位，即使每次只访问 1 字节的数据，也需要缓存目标数据的一个数据块(4096 字节 4KB)

• 进程度文件
  • 获取字节 所在的数据块
  • 返回数据块内对应部分
• 进程写文件
  • 获取数据块
  • 修改数据块中对应部分
  • 写回数据块

访问模式

• 顺序访问， 按字节一次读取
• 随机访问，随机读取
• 索引访问，依据数据特征索引

分层文件系统

文件是以目录的方式组织起来

目录： 是一类特殊的文件， 其内容是文件索引表<文件名，指向文件的指针>

文件别名， 2 个多多个文件名 关联 同给一个文件

• 硬链接， 多个文件项 指向 一个文件，删除时，可能有个隐形计数器，删除一次减一，直到为 0 时才真正删除
• 软链接，以快捷方式指向其他文件 (通过存储 真实文件 的逻辑名称 来实现)。 删除时，这个别名成为一个空指针

名字解析(路径遍历)

把逻辑名字转换成物理资源，递归先读文件头，在读数据块，搜索子项

• 依次遍历路径名，在文件系统中找到实际文件位置
• 遍历文件目录 直到 直到目标文件

例如： 解析 /bin/ls

• 读取根目录的文件头(在磁盘固定位置)
• 读取根目录的数据块 ，搜索 “bin” 项
• 读取 bin 的文件头
• 读取 bin 的数据块 ，搜索 “ls” 项
• 读取 ls 的文件头

文件系统挂载

一个文件系统需要先挂载才能被访问，挂载点 在用户 看来 相当于 目录。

将额外的文件系统 与 根文件系统的某个 现存的目录建立关联关系，进而使得该目录作为其他文件访问入口

虚拟文件系统(VFS，Virtual File System)

对不同文件系统的抽象，提供相同的文件和文件系统接口，管理所有文件和文件系统关联的数据结构

文件系统的基本数据结构

• 文件卷控制块
  • 每个文件系统一个
  • 文件系统详细信息
  • 块、块大小、空余块、计数/指针等
• 文件控制块
  • 每个文件一个
  • 文件详细信息
  • 访问权限、拥有者、大小、数据块位置等
• 目录项
  • 每个目录项一个
  • 将目录项 数据结构及树型布局 编码成 树型数据结构
  • 指向文件控制块、父目录、子目录等

文件系统的存储结构

• 持久存储在外存
• 当需要时加载进内存
  • 卷 控制块，当文件系统挂载时进入内存
  • 文件 控制块，当文件被访问是进入内存
  • 目录节点，在遍历一个文件路径时进入 内存

文件系统打开文件的数据结构

• 文件描述符
  • 每个被打开的文件都有一个文件描述符
  • 文件状态信息 (目录项、当前文件指针、文件操作设置…)
• 打开文件表
  • 每个进程一个进程打开文件表
  • 有一个系统级的打开文件表
  • 有文件被打开时，文件卷就不能被卸载

文件分配

如何表示分配给一个文件数据块的位置和顺序

分配方式

• 连续分配
  • 文件头指定起始块和长度
  • 最先匹配，最佳匹配
  • 优点，文件读取表现好，高效的顺序和随机访问
  • 缺点，碎片，文件增长问题(预分配、按需分配)
• 链式分配
  • 文件以数据块链表方式存储，文件头 包含 了 第一块 和 最后一块 的指针
  • 优点，创建、增大、缩小容易；没有碎片
  • 缺点，无法实现随机访问；可靠性差(破坏一个链，后面的数据块就丢了)
• 索引分配
  • 为每个文件创建一个索引数据块，指向文件数据块的指针列表；文件头 包含了索引数据块 指针
  • 优点，创建、增大、缩小容易；没有碎片，支持直接访问
  • 缺点，文件很小时，存储索引开销大；大文件索引难处理

UFS 多级索引分配

• 文件头包含 13 个指针
  • 前 10 个指针指向数据块
  • 第 11 个指针 指向 索引块
  • 第 12 给指针指向二级索引块
  • 第 13 个指针指向三级索引块

空闲空间管理

用位图代表空闲数据块列表

使用简单但是可能会是一个很大的向量表， 160G 磁盘 -> 40M 数据块 -> 5MB 位图

假设空闲空间在磁盘中均匀分布，则找到 “0”之前要扫描 n(数据块总数)/r(空闲块总数)

磁盘分区、文件卷

通常磁盘通过分区来最大限制 减少寻道时间

• 分区 是 一组柱面的集合
• 每个分区 都可视为 逻辑上独立的磁盘

文件卷： 已个拥有完整文件系统实例的外存空间，通常常驻在磁盘的单个分区上

多磁盘管理

使用多磁盘可改善 吞吐量（通过并行），可靠性和可用性 （通过冗余）

RAID 冗余磁盘队列（RedundantArray of Inexpensive Disks）

• RAID-0，磁盘条带化

  把数据块分成多个子块，存储在独立的磁盘中；通过独立磁盘上并行数据块访问 提供更大的磁盘带宽

• RAID-1，磁盘镜像

  向 2 个磁盘写入，从任何一个读取；可靠性成倍增长，读取性线性增加

• RAID-4，带校验的磁盘条带化

  数据块级 的磁盘条带化 + 专用奇偶校验磁盘； 能从任意一个故障磁盘中恢复

• RAID-5，带分布式校验的磁盘条带化

I/O 子系统

常见设备接口类型

• 字符设备，键盘、鼠标、串口等，以字节单位顺序访问，get(),put()
• 块设备，磁盘驱动器、光驱等，均匀的数据块访问，原始 IO 或文件系统接口，内存映射文件系统接口
• 网络设备，以太网、无线、蓝牙等，格式化报文交换，send/receive 网络报文，网络接口

同步、异步 I/O

• 阻塞 I/O，”wait”
  • 读数据时，进程 将进入 等待状态，直到完成数据读取
  • 写数据时，进程 将进入 等待状态，直到设备完成数据写入处理
• 非阻塞 I/O， “Don’t Wait”
  • 立即从 read/write 系统调用返回，返回值 为成功传输字节数，可能为 0
• 异步 I/O， “Tell Me Later”
  • 读数据时，使用指针标记好用户缓冲区，立即返回；稍后内核将填充缓冲区并通知用户
  • 写数据时，使用指针标记好用户缓冲区，立即返回；稍后内核 将 处理数据并通知用户

I/O 结构

CPU 北桥连 高速设备， 南桥 连 IO 设备

CPU 与设备的连接

• 设备控制器： CPU 与 IO 间的接口，向 CPU 提供特殊指令和寄存器
• IO 地址： CPU 用来控制 IO 硬件，内存地址或端口号
• CPU 与设备的通信方式： 轮询 、设备中断、DMA（直接内存访问）

IO 指令、内存映射 IO

• IO 指令，通过 IO 端口号访问 设备寄存器，特殊 CPU 指令
• 内存映射 IO，设备寄存器/存储 被映射到 内存物理地址空间中
  • 通过 内存 load/store 指令 完成 IO 操作
  • MMU 设置映射，硬件跳线或程序启动是设置地址

I/O 请求声明周期

CPU 与 设备控制器 的数据传输

• **程序控制 IO(PIO)**， 通过 CPU 的 load/store 传输所有数据

  • 硬件简单、编程容易，消耗的 CPU 时间和数据量成正比
  • 适用于简单的、小型的设备 I/O

• 直接内存访问（DMA）， 设备控制器可 直接 访问 系统总线，控制器直接与内存互相传输数据

  • 设备传输数据不影响 CPU，需要 CPU 参与设置
  • 适用高吞吐量 I/O

通过直接 I/O 寻址 读取 磁盘数据

I/O 设备通知操作系统的机制

• 操作系统需要了解设备状态
  • I/O 操作完成时间
  • I/O 操作遇到的错误
• 通知方式
  • CPU 主动轮询 ：IO 设置在特定的状态寄存器中放置状态和错误信息，操作系统定期检测寄存器
  • 设备中断