2025操作系统

计算机体系结构

硬件结构

RISC和CISC

项目RISC（Reduced Instruction Set Computer）CISC（Complex Instruction Set Computer）
含义精简指令集计算机复杂指令集计算机
核心思想少而精，指令简单，执行快多而全，指令复杂，功能强
代表ARM系列X86
补充：ISA 是计算机体系结构的核心部分，决定程序如何与处理器交互。全称 Instruction Set Architecture，指令集架构

常见的Linux指令

序号指令功能简介
1cp复制文件或目录（copy）
2mv移动或重命名文件/目录（move）
3rm删除文件或目录（remove）
4chmod修改文件或目录的权限（change mode）
5chown修改文件或目录的所有者（change owner）
6tar打包压缩/解压文件（tape archive）
7curl用于发送网络请求，支持多种协议（如HTTP、FTP）
8du显示目录或文件所占磁盘空间（disk usage）
9kill发送信号（如终止）给进程
10top实时显示系统进程资源使用情况
11ls列出目录下的文件和目录（list）
12cd切换当前目录（change directory）
13mkdir创建新目录（make directory）
14touch创建空文件或修改文件时间戳
15cat查看文件内容，合并文件（concatenate）
16grep在文本中查找匹配的内容（global regular expression print）
17find查找文件（比grep更注重文件名/路径）
18df查看磁盘分区使用情况（disk free）
19ps查看当前系统运行的进程（process status）
20wget从网络下载文件（非交互式）

特权级

特权级指 处理器对当前执行代码的权限限制级别。常见的特权级别有：

名称数值（x86）说明
Ring 00（最高权限）操作系统内核（Kernel mode）
Ring 1/21、2很少使用（部分驱动或中间件）
Ring 33（最低权限）普通用户程序（User mode）

特权级的意义

  • 资源访问控制：防止用户程序直接操作硬件、内存或敏感寄存器；
  • 隔离故障：用户态崩溃不会影响内核态；
  • 系统调用入口控制：用户程序通过系统调用接口请求服务，由内核代为完成。

不同级别之间的转换

转换实现方式
用户态 → 内核态中断、异常、系统调用
内核态 → 用户态系统调用返回、进程调度、异常处理结束

AArch64 的四个特权级（Exception Levels）

特权级名称权限级别用途
EL0用户态（User）最低普通应用程序运行所在层
EL1内核态（Kernel）中等操作系统内核所在层（调度、内存管理等）
EL2虚拟机监控器（Hypervisor）高虚拟化支持层（例如 KVM、Xen 的 Hypervisor）
EL3安全监控器（Secure Monitor）最高ARM TrustZone 安全世界的入口，切换 Secure/Non-secure 模式

缓存结构（路组相连）及寻址

映射方式映射规则命中效率实现复杂度
直接映射每个主存块只能映射到一个特定 Cache 块低低
全相联映射每个主存块可映射到任意一个 Cache 块高高
组相联映射每个主存块可映射到一组中的任意块折中中

全相联映射:主存物理地址 = 标记 + 块内地址
组相联映射:主存物理地址 = 标记+ 组号 + 块内地址
直接映射:主存物理地址 = 标记 + cache 行号 + 块内地址

其中的重点是组相连映射：

结构定义：

  • Cache 被划分为若干“组”（Set）；
  • 每组内有若干个“路”（Way）或“块”（Block）；
  • 常见的有 2 路、4 路、8 路组相联等。

例如：

一个 4 路组相联 Cache，表示：

每组有 4 个块，主存块只能映射到某一组，但可放入组内任意一块

假设：

  • 物理地址为 N 位，
  • Cache 行大小为 B 字节，
  • Cache 总大小为 C 字节，
  • Cache 为 K 路组相联。

则地址划分如下：

物理地址（N 位） =[ Tag | Set Index | Block Offset ]
  • Offset（块内偏移）：log₂(B) 位
  • Set Index（组号）：log₂(C / (B × K)) 位（组数取对数）
  • Tag（标记）：剩余高位，用于匹配判断是否命中

寻址流程：

  1. 从地址 A 中：
    • 取出 Offset → 定位块内字节
    • 取出 Set Index → 定位对应 Cache 的某一组
    • 取出 Tag → 与该组中每个块的 Tag 比较
  2. 若命中（Tag 匹配 + 有效位有效）：
    • 直接读取该块中的对应字节
  3. 若未命中（Tag 不匹配或无效）：
    • 从主存加载数据 → 放入该组的某个块中（通过替换策略）

例题：

已知：

物理地址长度：36位

缓存大小：16KB

缓存行大小：64B

于是：

缓存总块数 = 缓存大小/缓存行大小 = 2^14/2^6 = 2^8 = 256 块

四路组组数 = 缓存总块数/路数 = 2^8/2^2 = 2^6 = 64 组

偏移量offset = 缓存行大小取对数 = log₂(64B) = 6 位

直接映射：

块号set = 缓存总块数取对数 = 8 位

标记位数Tag = 物理地址长度 - 块号set - 偏移量offset = 22 位

四路组相连映射：

组号set = 四路组组数取对数 = log₂(2^6) = 6 位

标记位数Tag = 物理地址长度 - 块号set - 偏移量offset = 24 位

这里要特别注意组号和块号的区别，由于直接映射没有分组，所以它的Set Index直接就是块号。但是四路组映射的Set Index是组号，每组有四个块，某个块 Tag 匹配 → 命中 → 那块就是“实际块号”。在命中之前，我们是无法知道具体块号的。

异常向量表中存储的内容是什么

存储异常源和其对应的处理函数的关系

寄存器全称功能简要说明
PCProgram Counter程序计数器，指向下一条将要执行的指令地址。每执行一条指令，PC 自动递增或跳转。
SPStack Pointer栈指针寄存器，指向当前栈顶位置。函数调用、局部变量、返回地址等通常保存在栈中。
FPFrame Pointer帧指针寄存器，指向当前函数栈帧的基地址，用于访问函数参数和局部变量，便于栈帧管理（常与调试有关）。
LPLink Pointer链接寄存器，用于保存函数调用返回地址（例如 BL 指令会将返回地址存入 LP）。

系统控制相关寄存器

TTBR0 / TTBR1Translation Table Base Register 0/1页表基址寄存器。TTBR0 用于 EL0 用户态访问，TTBR1 用于 EL1（内核态）页表基地址。地址转换（虚拟 → 物理）时从此处开始查页表。
VBARVector Base Address Register异常向量表基址寄存器，指向当前异常级（如 EL1）的异常处理程序入口表地址。

当某个CPU是四路组相联时，它的含义是什么

表示每个Set最大支持的Tag数目为4

操作系统结构

常见内核架构

内核架构结构特征性能水平稳定性/安全性可扩展性典型代表操作系统
宏内核所有服务（驱动、文件系统、调度等）运行在内核空间高较低较差Linux、传统 UNIX（如 BSD）
微内核仅保留最小内核（调度、IPC 等），其他服务运行在用户空间较低高高MINIX、QNX、GNU Hurd
混合内核在单体内核基础上实现模块化设计，部分服务用户态，部分内核态中高中等中等Windows NT、macOS（XNU）
外核极简内核，资源管理策略下放，应用层直接控制硬件资源非常高灵活但依赖开发者最高Exokernel（实验）、Nemesis 等

内存管理

虚拟地址和物理地址

what

概念定义
物理地址（Physical Address）内存芯片上的真实地址，由内存控制器管理，是 CPU 访问实际 RAM 的唯一标识。
虚拟地址（Virtual Address）程序运行时看到的地址，是一种“抽象地址”，由操作系统 + MMU 翻译为物理地址。

why

目的解释
1. 地址隔离每个进程有自己独立的地址空间，互不影响，提高系统安全性。
2. 内存保护防止非法访问内核空间或其他进程地址。
3. 内存共享多进程可以共享同一物理内存（如共享库），但使用不同虚拟地址。
4. 简化编程模型程序无需关心内存分布，操作系统提供连续的虚拟空间。
5. 支持虚拟内存虚拟地址空间 > 实际物理内存，可通过磁盘换页实现大内存。

how

通过地址映射与分页机制（Paging）

分段和分页地址转换的计算方法

对于分页：

Q4.1如何确定一个逻辑地址对应的页号和页内偏移量

页号 = 逻辑地址/页面长度 （取整数部分）

页内偏移量 = 逻辑地址%页面长度

当然，由于二进制的特性，只要页面大小是2的整数幂，我们就有一种更简单的方法。

结论:如果每个页面大小为2K2^KB，用二进制数表示逻辑地址:则末尾K位即为页内偏移量，其余部分就是页号。

例题：

每页1KB = 2^10B → 末尾10位（低地址）为页内偏移量offset

主存16KB，每页1KB → 主存最多容纳16页

1.逻辑地址 0x0AC5H 转换为二进制 为 0000 1010 1100 0101.

所以 10 1100 0101 就是页内偏移量。

剩下的 0000 10 就是逻辑页号

0000 10 转换为十进制为 2，先检查页号合法性，发现2<9(一共十页，从0开始)合法，于是查询页表可知，对应的物理帧号为 4。把物理帧号转换为二进制 000100替换逻辑页号，offset不变。

于是，物理地址为 0001 0010 1100 0101，即 0x12C5H

2.逻辑地址 0x1AC5H 转换为二进制后，页号超出已有的逻辑页号，但仍旧合法，于是发生缺页中断（Page Fault）。

3.逻辑地址 0x3AC5H 转换为二进制后，页号超出已有逻辑页号，且不合法，发生错误 内存访问越界。

对于分段：

分段与分页的机制很像，只是要更多的检查一次合法性，也就是偏移量是否超过段长。

例题：

对于表A0号，起始地址 210 段长500，表B记录0号段offset 为430，430<500合法，对应物理地址为起始地址+offset = 430 + 210 = 640.

对于表B5号，offset = 32，但是在表A中查询不到，发生段错误。

4级页表寻址计算

例题：

虚拟页大小为4KB =2^12B

offset = 虚拟页大小取对数 = 12 位

索引 = 虚拟页大小/页表项 的对数 = 9 位

由于存在四级，则需要四级索引，也就是36位，正好满足虚拟地址低48位参与地址翻译。

格式为: L1(9位)L2(9位)L3(9位)L4(9位)offset(12位)

页的大小修改为8KB，offset = 13位

索引 = 10 位

我们可以把L4修改为5位，其他L1L2L3改为10位，offset保持13位不变。

⚠️注意：各级页表大小不能超过一个页面。

几种页面替换策略的计算

Q6.1：最佳置换算法(OPT)

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

但是在现实中无法实现，不可能提前知道访问顺序。

Q6.2：先进先出置换算法(FIFO)

把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最大长度取决于系统为进程分配了多少个内存块。

优点：实现简单

缺点：Belady异常—分配的物理块数增大，缺页次数不减反增。因为最先进入的页面也有可能最多被访问。

Q6.3：最近最久未使用算法(LRU)

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t.当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

在做题时，直接逆向扫描之前已经出现过的页号，在扫描过程中最后一个出现的页号就是要替换的页号。

Q6.4 Second Chance算法

Second Chance 的核心改进

  • 给页一个“第二次机会”：若它近期被访问过，不立即淘汰，而是“放一马”。

第一种：基于FIFO改进

访问页 P：

  1. 若 P 已在内存中 → 命中 → 设置 P.R = 1
  2. 若 P 不在内存中 → 缺页：
    从队头开始查找：
    a. 如果当前页 R=1 → 清零，移到队尾
    b. 如果 R=0 → 替换该页，插入 P，P.R=1

步骤演示：

步骤当前访问页队列状态（页号:R）操作说明
1AA:1缺页，入队，R=1
2BA:1, B:1缺页，入队
3CA:1, B:1, C:1缺页，入队
4AA:1, B:1, C:1命中，A.R=1
5BA:1, B:1, C:1命中，B.R=1
6DA:1, B:1, C:1缺页，需替换：① A.R=1 → 清零，放队尾② B.R=1 → 清零，放队尾③ C.R=1 → 清零，放队尾④ 回到 A.R=0 → 替换 A → D 入队，R=1
7AB:0, C:0, D:1缺页，替换 B（R=0）→ 入队 A:1
8DC:0, D:1, A:1命中
9BC:0, D:1, A:1缺页，替换 C（R=0）→ B:1
10CD:1, A:1, B:1缺页，所有 R=1，轮一圈清零后 C 入队替换 D
11EA:0, B:0, C:1缺页，A.R=0 → 替换 A → E:1

虚拟内存功能

四大功能的Idea

共享内存：

  • 允许同一个物理页在不同的程序间共享
  • 满足进程间通信、传递数据

写时拷贝：

  • 以只读方式共享内存
  • 需要写的时候才触发缺页
  • 通过拷贝实现

内存去重：

  • 扫描内存中具有相同内容的物理页面，执行去重
  • 操作系统主动发起，对用户态的应用程序完全透明

内存压缩：

  • 当内存资源不充足的时候， 将“最近不太会使用”的内存页进行数据压缩
  • 应用程序再次访问资源时，操作系统将其解压
  • 都在内存中进行，可快速腾出空间，快速压缩数据，避免I/O

大页的idea及优势

在 AArch64（ARMv8-A）架构中，采用多级页表结构（最多可支持 4 级），每级页表不仅可指向下一级页表（即“页表项”），也可以直接映射到较大的内存页，这就叫做 大页机制（Large Page Mechanism）。

每一级页表项都包含一个 Descriptor Type 字段，用于标识：

  • 当前项是否是 页表项（继续指向下一级页表）
  • 或者是 块项（Block Entry），直接映射到内存页（即大页）

如果L1, L2, L3页表项中的第一位是0，该页表项对应的页的大小是多少（AArch64）？

页表级别bit[0] = 0 含义页大小
L1Block entry（大页）1 GB
L2Block entry（大页）2 MB
L3❌ 无效（不支持 bit[0]=0）非法项
仅L1，L2支持大页！L0只指向L1！L3 不支持 block，仅支持 page（bit[0] = 1）

进程与线程

进程控制块（PCB，Process Control Block）

描述进程的数据结构：进程控制块

操作系统管理控制进程运行所用的信息/状态集合

包含：上下文、虚拟地址空间、内核栈、进程标识符(PID)、进程关系、资源等

PCB是进程存在的唯一标志

PCB的三大信息：

进程标识信息：进程标识符（PID）、用户标识符（UID）

进程状态信息：进程当前的状态信息——就绪、运行、阻塞等。程序计数器：进程将要执行的下一条指令地址。寄存器集。

进程控制信息：进程的优先级、调度指针、内存管理信息：如页表。

相关的Linux指令

Linux里，使用fork()来创建进程，使用wait()/waitpid()来回收进程，使用exec函数家族来执行进程

fork() 的作用是：

创建一个与当前进程几乎完全相同的子进程。
  • 子进程是父进程的副本（包括代码段、堆、栈、文件描述符等）。
  • 子进程与父进程拥有独立的地址空间（通过写时复制机制 COW 实现内存共享优化）。

fork() 的返回值

返回值含义
> 0（正整数）在父进程中，表示子进程的 PID
= 0在子进程中，表示 fork 成功
< 0（负数）表示 fork 失败（例如资源不足）
缺点说明
资源开销大尽管使用写时复制，但仍需复制页表、进程上下文
进程切换成本高父子进程调度开销大于线程切换
通信复杂父子进程内存独立，需要 IPC（如管道、共享内存）通信
不能直接共享变量与多线程（线程共享地址空间）相比，无法直接访问彼此变量

用户态线程和内核态线程的主要区别是什么？

类型定义
用户态线程（ULT）线程由用户空间的线程库（如 pthread）管理，内核感知不到线程的存在
内核态线程（KLT）线程由操作系统内核直接管理与调度，每个线程都是内核调度的实体

操作系统调度

调度指标

常见调度指标

CPU使用率、吞吐量、等待时间、周转时间、响应时间

调度机制

长期/中期/短期

调度策略

经典策略

FCFS策略：

  • 先来先服务
  • 缺点：短任务不友好，IO密集任务不友好

SJB短任务优先策略：

  • 短任务优先
  • 进程进入等待或结束状态时，就绪队列中的执行时间最短的进程占用CPU

STCF短完成任务优先策略：

  • 短任务优先的升级抢占版，解决短任务等待问题
  • 缺点：长任务饥饿，极端情况饿死长任务

RR时间片轮转：

  • 按时间片轮流执行
  • 注意！同一时刻，当前时间片结束且新任务到达，新到达的任务先入队，然后再把时间片结束的任务放到队尾！

HRRN高响应比优先：

  • 响应比 =（T等待/T运行） +1
  • 非抢占式
  • 开销大

MLQ多级队列：

  • 提前分好优先级队列
  • 抢占式，被抢占的进程放回队尾！
  • 可能导致低优先任务饿死

MLFQ多级反馈队列：

  • 队列内部以RR为策略调度，时间片大小随优先级级别降低而增加
  • 进程未在一个时间片中完成则自动降低到下一个优先级队列
  • 定时提升优先级

调度的负载均衡概念

概念

NUMA（Non-Uniform Memory Access，非一致性内存访问）是一种多处理器系统的内存架构设计。

在 NUMA 架构中，每个 CPU（或 CPU 组）拥有自己的本地内存，并可以访问其他 CPU 的内存，但访问远程内存的延迟更高、带宽更低。

NUMA 是为了解决多核/多处理器系统中内存访问瓶颈的问题，通过让每个 CPU 拥有自己的本地内存，提高访问效率。但这也要求操作系统或应用更好地管理线程和内存之间的“亲和性”。

并发控制

并发和并行、同步和异步?

概念并发（Concurrency）并行（Parallelism）
定义多个任务在时间片上交替执行多个任务在同一时刻真正同时执行
目标提高资源使用率、提升响应性提高执行速度、缩短总运行时间
资源要求不一定需要多核/多处理器需要多核/多处理器以支持真正的同时运行
例子单核 CPU 通过时间片轮转运行多个线程多核 CPU 同时运行多个线程/进程
编程模型线程、协程、事件循环（如 async/await）多线程、多进程、GPU 并行计算
概念同步（Synchronous）异步（Asynchronous）
定义调用者必须等待操作完成调用者无需等待操作完成，可继续执行其他任务
编程行为按顺序执行，阻塞当前线程提交任务后立即返回，结果通过回调/事件通知
举例读取文件 → 等待完成 → 继续执行启动文件读取 → 同时执行其他操作 → 等待回调
应用场景控制简单，适用于实时性要求高的操作高并发场景（如网络编程、UI响应）

为什么需要IPC，宏内核的IPC和微内核的IPC区别，微内核IPC成
功在哪里？同步和异步IPC有什么不同？

防止竞态、处理进程间调度、进程之间协调。

宏内核的IPC和微内核的IPC区别：

比较维度宏内核（Monolithic Kernel）微内核（Microkernel）
IPC 使用频率相对较少，许多功能直接在内核中完成非常频繁，所有服务（驱动、文件系统）都通过 IPC
通信机制内核函数调用或共享内存（效率高）严格的消息传递（封装成消息包）
通信路径内核内部模块直接调用应用 ↔ 微内核 ↔ 服务进程，多次上下文切换
通信效率高，函数调用/共享内存操作低，但可控（受限于上下文切换/复制次数）
典型系统Linux、Windows NTMinix 3、L4、QNX、Fuchsia

微内核中 IPC 的典型优化措施

优化点优化手段
1. 减少上下文切换次数- 使用 direct process switch（直接从 sender 切换到 receiver）- 避免 sender → kernel → scheduler → receiver 的慢路径
2. 零拷贝（Zero-copy）传输- 通过 共享内存页面映射，避免 sender → kernel → receiver 的数据复制- 或只传递内存引用（capability）而非真实数据
3. 快速路径处理- 对小消息使用 寄存器传参（Register-based IPC），避免内存访问- 内核对常见通信路径进行专门优化
4. 内核数据结构极简- 使用紧凑、对齐良好的 IPC 缓冲区结构，减少调度器和 IPC 逻辑之间的开销
5. 消息缓存和延迟绑定- 将消息暂存在内核，并在 receiver 有空时传递，减少忙等
6. 异步/同步混合支持- 允许线程通过异步发送、同步等待等方式组合使用，适配不同场景
7. 时间预算（Time-bounded IPC）- 如 L4 实现支持限制 IPC 最长时间，避免恶意进程拖慢系统

进程间通信的主要方式

信号、信号量、匿名管道、命名管道、消息队列、共享内存

临界区的实现方法

Peterson算法：

先请求再谦让，最后一次谦让的让对方先运行。

缺陷：不满足 忙则让权

自旋锁：CAS实现 Compare And Swap

缺陷：仍旧不满足忙则让权

排号自旋锁（ticket lock）：

先叫号，每个进程FIFO拿号，使用后号+1，释放资源给下一个人使用。

使用FAA指令实现（拿取并累加，Fetch-and-Add）、按照申请顺序传递（FIFO）

缺陷：仍旧不满足忙则让权，维护队列需要额外开销

条件变量：

设置条件变量 int waiting = 0

每次请求时，waiting++，