概览

虚拟化CPU——进程

概述

“操作系统通过让一个进程只运行一个时间片, 然后切换到其他进程, 来提供存在多个虚拟CPU的假象, 是为时分共享CPU技术, 看起来就像多个进程在并行运行. ”

进程创建

1. 将程序的所有代码和静态数据(从持久化存储设备)(惰性)加载到进程的地址空间(内存中的某个页框)

惰性: 分页机制, 用时加载

2. 在内存上分配堆和运行时栈(并初始化)以备用

3. 其他初始化任务(如与I/O相关的文件描述符fd的初始化)

4. 跳转到程序的main()例程, 启动程序

进程状态

三状态模型

1. 运行态: 正在处理器上运行(在调度列表中并获得了调度)

2. 就绪态: 可以运行, 准备运行(在调度列表中但未获得调度)

3. 阻塞态/等待态: 不具备运行条件, 等待条件被满足(不在调度列表中)

七状态模型: 引入挂起(suspend)

• 一般选择等待态进程进入挂起等待态, 选择就绪态进程进入挂起就绪态

• 运行态进程可以挂起自己

• 等待事件结束后, 挂起等待态进入挂起就绪态

• 选择挂起就绪态进程恢复为就绪态

进程存储形式(i.e.数据结构)

进程API

• fork(): 复制当前进程作为子进程, 从调用fork()的行开始执行. fork()在父进程中返回子进程的进程号, 在子进程中返回0, 可以在代码逻辑中用于区分父子进程.

• exec() / execve(): 移交进程控制权到指定的程序, 覆盖当前进程控制流. 成功的exec()调用永远不会返回.

• wait(): 阻塞父进程, 等待子进程返回, 用于同步父子进程的执行.

• kill(): 发送信号要求杀死/睡眠进程.

• ps/pstree: 查看当前系统进程

• top: 查看占用资源最多的进程(自身开销很大)

底层机制: 受限直接执行

直接执行

受限

💡

系统调用的代码遵守系统调用的ABI, 将数据放入约定的位置之后执行trap指令跳转到系统调用例程. 返回时trap例程也需要将返回值放到周知的约定处.

C库中进行系统调用的部分是用汇编手工编码的!

进程间切换(上下文切换)

1. 信任策略(不安全): 用户程序主动进行系统调用(如yield), 定期放弃CPU, 将控制权交还到OS;

2. 非协作方式(安全): 操作系统利用时钟中断定期中断用户程序, 抢占CPU控制权以进行控制.
💡

*补充: 中断控制流程(了解即可)

1. 进入上下文切换的系统调用例程

2. 通过系统调用, 保存当前执行的进程信息(如PCB或特定寄存器的值), 压入内核栈;

3. 通过系统调用, 为即将执行的进程恢复/准备信息(如PCB或特定寄存器的值), 切换内核栈.

4. 从系统调用(中断例程)返回, 则返回到切换后的进程开始执行, 上下文切换完毕,

💡

中断是激活操作系统控制的唯一方式. 狭义的中断: 来源于处理器外, 与当前运行的指令无关; 异常: 运行指令引起的中断事件(地址异常, 算数异常, 越权指令等); 系统异常: 主动执行Trap指令触发系统调用引起的中断.

中断响应过程

• 外部设备向中断控制器发出中断请求IRQ, 在中断寄存器中设置已发生的中断

• 系统发现中断源, 提出中断请求
• 发现中断寄存器中记录的中断
• 决定这些中断是否应该屏蔽
• 当有多个要响应的中断源时, 根据规定的优先级选择一个

• 中断当前程序的执行, 保存当前程序的PSW/PC到核心栈

• 查询中断向量表, 转向操作系统的中断处理程序

上层策略: 进程调度

调度指标

• 周转时间(高效性) = 任务完成时刻 - 任务到达时刻

• 响应时间(交互性) = 任务开始运行时刻 - 任务到达时刻

• 调度的公平性 → 各进程受调度的机会均等

• 调度的优先级 → 根据重要性分配不同的调度机会

FIFO(First In, First Out)

SJF/SPN(Shortest Job First)

STCF/SRTF(Shortest Time to Completion First/Shortest Remaining Time First)

轮转(Round-Robin, RR)

多级反馈队列(SJF和轮转的混合)

1. 若A的优先级>B的优先级, 则运行A不运行B(高级优先);

2. 如果A的优先级=B的优先级, 则轮转运行A和B(同级轮转);

3. 工作进入系统时放在最高优先级队列(接受评估);

4. 一旦工作用完了在某一层的时间配额(时间片)就降低其优先级, 移入低一级队列(对其需要运行的市场的评估值增加, 根据SJF的思想应该靠边站)
💡
高优先级被评估为短工作, 低优先级被评估为长工作.
一个短进程很快就会执行完, 不会在就绪队列中降很多级.

5. 经过一段时间S, 就将系统中所有工作重新加入最高优先级队列(防止长时进程饿死)
💡
S的值需要考量(性能与公平的平衡).

比例份额调度(彩票调度)

步长调度(Stride Scheduling)

• 每个进程分配一个步长(stride), 步长值与其份额(tickets, 即彩票张数)成反比.
• 步长 = 大常数 / tickets

• 每个进程还维护一个通行值(pass value) 初始为0.

• 每次调度选择通行值最小的进程运行, 并将该进程的通行值增加其步长.

• P2 → P1 → P2 → P2 → P1 → P2 → ...

• 比随机的彩票调度更可控、更可预测;

• 适用于实时或对调度公平性有严格要求的场景;

• 实现简单, 仅需维护整数值.

HRRF(Highest Response Ratio First, 最高响应比优先)

• 执行后, A 和 B 的等待时间分别为 1.

• 再次计算响应比:

多处理器调度

虚拟化内存——虚存

需求

地址空间

内存管理API

• malloc(size_t size)

• calloc(size_t size) → 分配并置零

• realloc()

• free(void *ptr)

• brk(): 改变程序分断的位置, 即堆结束的位置. 需要一个参数即新分断的地址来判断是增大还是减小堆的大小.

• sbrk(): 与brk大致相同, 参数是堆大小的增量.

• mmap(): 在程序中创建一个匿名区域, 与swap空间相关联/

底层机制:(基于硬件的)地址转换

基址+界限/动态重定位(原始思想)

分段式(进步)

💡

*补充: “单连续”和”多连续”逻辑地址空间(初学者可以跳过)

在理解“单连续逻辑地址空间”和“多连续地址空间”以及“段式逻辑地址的二维性”时, 我们需要从操作系统对内存的抽象和管理方式来看.

单连续逻辑地址空间

定义:

单连续逻辑地址空间(Single Contiguous Logical Address Space)是指一个程序或进程在运行时, 认为自己拥有一个从0开始, 连续且完整(物理上完全连续)的地址空间. 在这个模型下, 程序内部的所有代码、数据、堆栈等都被看作是存储在这个单一的、线性排列的地址空间中.

特点:

• 线性结构: 地址从0递增, 形成一个一维的线性序列.

• 整体性: 程序认为其所有部分都紧密地排列在这个空间内.

• 简单性(对程序员): 程序员在编写程序时, 可以假设所有内存访问都是相对于这个0地址的偏移量.

• 物理实现可能不连续: 尽管逻辑上是连续的, 但在实际的物理内存中, 这些数据可能被分散存储在不连续的物理块中, 由操作系统通过内存管理单元(MMU)进行地址映射和管理.

例子:

在早期没有虚拟内存的系统中, 或者在某些简化模型中, 一个进程的内存就是一块连续的物理内存. 即使在现代操作系统中, 每个进程的虚拟地址空间也通常被抽象为一个巨大的单连续地址空间(例如, 32位系统通常是4GB, 64位系统远超此值), 程序在这个虚拟空间内进行寻址.

多连续地址空间

定义:

多连续地址空间(Multiple Contiguous Logical Address Spaces), 有时也被称为分段(Segmentation), 是指一个程序或进程的逻辑地址空间被划分为多个独立的、逻辑上连续的段(Segment). 每个段都有其独立的起始地址和长度, 并且这些段在逻辑上可以是相互独立的, 不要求它们在逻辑地址空间中连续(这里放一段, 那里放一段).

特点:

• 结构化: 程序可以根据其逻辑结构(如代码段、数据段、堆栈段、子程序段等)被划分为不同的段.

• 独立性: 每个段都可以被独立地加载、保护和管理. 例如, 代码段可以只读, 数据段可读写.

• 更灵活的分配: 各个段可以独立地分配到物理内存中的不同位置, 甚至可以不全部加载到内存中.

• 对程序员可见: 程序员在编写程序时, 需要显式地指定要访问哪个“段”以及该段内的“偏移量”.

例子:

传统的分段内存管理就是典型的多连续地址空间. 一个程序可能有:

• 代码段: 存放程序的指令.

• 数据段: 存放全局变量和静态变量.

• 堆段: 动态分配内存区域.

• 栈段: 存放函数调用信息和局部变量. 这些段在逻辑上是独立的, 可能在程序员看来, 它们是独立的内存块, 而不是一个统一的巨大线性空间.

为什么说段式逻辑地址是二维的？

这是因为一个段式逻辑地址通常由两部分组成:

1. 段号(Segment Number): 指定要访问哪个逻辑段.

2. 段内偏移量(Offset within Segment): 指定在该段内部的哪个位置.

因此, 一个完整的段式逻辑地址可以表示为: [段号, 段内偏移量].

二维性体现:

地址转换过程: 当CPU要访问一个段式逻辑地址时, 它首先需要根据段号去查找段表(Segment Table). 段表中存放着每个段的基地址(即该段在物理内存中的起始地址)和长度(限长). 然后, 将段的基地址与段内偏移量相加, 才能得到最终的物理地址.

• 第一维(段号): 用于选择程序中的哪个逻辑单元(代码、数据、堆栈等).

• 第二维(段内偏移量): 用于定位该逻辑单元内部的具体位置.

对比一维地址:

相比之下, 一个简单的线性地址(如在纯分页系统中)就是一维的, 它只有一个地址值, 这个值直接代表了从0开始的某个偏移量. 你不需要先选择一个“段”再在其内部进行偏移.

空闲空间管理算法(缝缝补补)

1. 最优匹配/最优适应分配: 遍历整个空闲列表, 找到最小的能满足请求大小的块并分配(遍历开销大);

2. 首次匹配/最先适应分配: 遍历, 分配首个找到的满足要求大小的块(优点速度快, 缺点碎片多);

3. 下次匹配/循环最先适应分配: 多维护一个指针, 从上次遍历结束的位置开始遍历找到并分配首个满足要求的块, 遍历到末尾则回到开头, 将对空闲空间的查找操作扩散到整个列表中去, 避免频繁分割开头;

4. 最差适应分配: 总是选择最大的内存块分割后分配(无实际意义);

5. 分离空闲列表: 使用专门的列表来管理常用大小的内存块(这种内存的分配和释放都很快), 其他照旧管理;

6. (二分)伙伴系统: 分配2的整数次幂大小的空间, 形成一个伙伴树, 树中的兄弟节点互为伙伴. 若节点大小大于待分配内存的两倍则递归对半分割为两个兄弟节点, 若兄弟节点均空闲则向上递归合并为更大的内存块.

分页式(最终解)

• VPN: 虚拟页号(由虚拟地址计算得出)

• PFN: 页框号(物理内存中对应的页帧)

• 有效位: 标记该页是否有效(即是否已映射)

• 修改位: 标记该页是否被写过

• 访问位: 标记该页是否被访问过(用于页面置换)

• 权限: 读写权限控制

💡

页大小的设计权衡:

• 大页 → 命中率高, 缺页异常少, I/O效率高, 内部碎片较多, 页数更少页表更小;

• 小页 → 命中率更低, 缺页异常多, I/O效率更低, 内部碎片少, 页数多页表更大.

页大小达到P时退化为固定分区;

主存内可驻留页面数达到N时代表页面全装载, 不会发生SWAP/缺页异常.

快表(TLB) → 解决问题1(速度太慢)

• 通常是页表的缓存, 只缓存部分映射

• LRU 表示最近使用时间或顺序, 用于替换策略

多级页表 → 解决问题2(页表太大)

反向页表IPT

• 该页框中数据在对应进程中的虚拟页号;

• 进程标识符, 即使用该页的进程号;

• 标志位(有效位, 引用位, 脏位, 保护位, 锁定位等);

• 链指针: 哈希链.

1. 维护工作: MMU通过哈希表把进程标识和虚页号转换成一个哈希值作为该进程的该页在哈希表中的索引, 而哈希表的表项为一个指向反向页表中某一表项的指针;

2. 查询工作: MMU遍历哈希链找到所需进程页在反向页表中的表项, 该项的索引就是页框号, 通过拼接页内偏移即可生成物理地址;

3. 若遍历整个反置页表中未能找到匹配页表项, 说明该页不在内存, 产生缺页中断, 请求操作系统调入.

段页式(分段和分页的混合策略)

• 段式存储管理可以基于页式存储管理实现;

• 每一段不必占据连续的存储空间, 可存放在不连续的主存页框中;

• 能够扩充为段页式虚拟存储管理, 装入部分段, 或者装入段中部分页面;

高速缓存Cache

Swap机制

1. 查TLB命中 → 返回

2. 查TLB未命中 → 查页表装入 → 更新TLB → 重试 → 查TLB命中

3. 查TLB未命中 → 查页表未装入 → 访问磁盘取回页 → 更新页表和TLB → 重试 → 查TLB命中

上层策略: 全局页替换策略(页面调度)

最优替换策略(OPT, 理想情况)

• 替换将来最久不会被访问的页面;

• 理论上页面置换最少, 但需要预知未来访问序列, 实际上只能模拟不能实现;

• 实际中不可实现, 用于评估其他算法性能.

先进先出(FIFO)

• 替换最早进入内存的页面;

• 简单但容易产生“Belady 异常”——增加内存反而页错误更多;

• 用队列实现, 每次插入新页时, 从队首换出.

💡

随机替换(避免边界)

• 随机选择一个页面替换;

• 简单易实现, 避免特定访问模式导致最坏情况;

• 平均性能不稳定, 完全看运气, 但在某些场景下表现良好.

最不常用(LFU)

• 给每个页设置一个计数器;

• 设置一个中断时间间隔, 每次发生中断就将所有页的计数器清零;

• 每访问页一次就给计数器+1;

• 踢出页时选择计数器值最小的页.

最近最少用(LRU)

• 近似模拟最优策略;

• 精确实现需要硬件支持(如访问时间戳), 开销较大.

近似LRU(找差不多最旧的页, 提高效率)

• 常用Clock算法模拟LRU;

• 每个页加一个访问位(Reference Bit), 页被访问时将访问位设为1(说明最近被使用过);

• 要替换页时类似时钟指针循环扫描, 路过访问位为1的页时将其清零, 找到访问位为0的页(最近未用)就进行替换, 替换后指针指向下一页但是不清零(即: 运行周期是考察访问位-移动指针);

• 每次指针扫描都从当前指向的页开始检查访问位.

脏页+写回/写直达

• 脏页(Dirty Page): 在装入期间被修改过的页.

• 写回策略: 写时设置脏位, 脏页被换出前写回磁盘以维持数据一致. 提高效率但增加一致性管理复杂度;

• 写直达: 每次写都直接写入主存或磁盘, 不设置脏位, 开销较大, 适用于不频繁修改的数据.

上层策略: 局部页面替换策略

局部最佳页面替换算法

• 设置一个滑动窗口, 假设覆盖时间区间为;

• 不论发生缺页与否, 在每一次引用页面时都考察一次: 若某页面在覆盖区间内未被引用则将其移出内存, 否则保留.

工作集置换算法

• 工作集(Working Set, WS): 在某一给定时刻 t, 进程的工作集 是指在时间间隔 内进程所访问的页面的集合. 其中, 是一个被称为工作集窗口(Working Set Window) 的参数, 它定义了时间窗口的大小.

• 局部性原理(Principle of Locality): 程序在执行过程中, 在一段时间内, 其访问的地址往往集中在某个局部区域. 这包括时间局部性(最近访问过的页面很可能再次被访问)和空间局部性(最近访问过的页面附近的页面很可能被访问). 工作集算法正是基于时间局部性来设计.

1. 维护页面访问时间戳:
• 对于内存中的每一个页面, 操作系统会维护一个上次访问时间戳(Last Accessed Time, LAT). 当页面被访问时其对应的LAT会被更新为当前的系统时间 t.
• 这个时间戳可以是精确的系统时钟值, 或者为了简化实现, 可以使用一个逻辑时钟或计数器, 每次访问页时递增.

2. 定义工作集窗口 :
• 操作系统需要预设一个工作集窗口 的大小. 是一个时间单位, 表示我们关注的“最近”时间段. 这个值的选择对算法的性能至关重要.
• 可以是固定的, 也可以是动态调整的.

3. 确定当前工作集:
• 在任意时刻 t, 为了确定进程 P 的工作集 , 操作系统会遍历进程P当前在内存中的所有页面(即其页表项或对应的页框).
• 对于每个在内存中的页面 , 检查其上次访问时间 .
• 如果 , 则页面 被认为是工作集的一部分, 因为它在最近 时间内被访问过.
• 如果 , 则页面 不在当前工作集中, 它是一个“陈旧”的页面.

4. 页面置换决策(当发生缺页中断时):
• 当进程 P 发生缺页中断, 需要从磁盘调入一个新页面 时, 如果物理内存已满:
• 首先, 确定进程 P 的当前工作集. 识别出所有不在工作集中的页面.
• 选择置换页: 在所有不在当前工作集中的页面中, 选择一个页面作为牺牲品. 通常会选择其中上次访问时间最早的页面进行置换.
• 如果所有内存中的页面都在当前工作集中, 则通常会选择工作集中的某个页面进行置换(此时算法效果与LRU相似), 但这种情况较少发生, 因为目标是保持工作集在内存中. 在这种极端情况下, 可能需要牺牲工作集中的一个页面(比如LRU策略).

5. 页面淘汰(Trimming/Aging):
• 除了在缺页时进行置换, 工作集算法也可以定期进行“页面淘汰”操作.
• 操作系统会周期性地扫描内存中的所有页面(或某个进程的页面), 将那些长时间不在任何进程工作集中的页面从内存中移除(如果它是一个修改过的脏页, 则先写回磁盘), 以释放物理内存. 这有助于在系统内存不足时提前清理不活跃的页面.

• 高度适应程序局部性: 能够有效地识别并保留程序当前最可能需要的页面, 从而显著降低缺页率.

• 性能优越: 通常能提供比FIFO、LRU等简单算法更好的性能, 尤其是在程序的局部性较强时.

• 实现复杂: 需要维护每个页面的上次访问时间戳, 并在缺页或定期扫描时进行复杂的计算和判断.

• 的选择困难: 的大小对算法性能有很大影响. 过小可能导致频繁置换, 过大可能导致内存浪费. 选择合适的 值通常需要经验或动态调整机制.

• 开销较大: 维护时间戳和定期扫描的工作会带来一定的系统开销.