第46周：操作系统与体系结构

字数统计: 3.5k字   |   阅读时长≈ 14分

第46周：操作系统与体系结构

目标：掌握操作系统与体系结构核心知识，能够深入讨论进程调度、内存管理、并发原语、缓存一致性等面试高频题。

1. 进程调度

1.1 Linux CFS 调度器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CFS（Completely Fair Scheduler）：

  核心思想：
  - 给每个进程一个"虚拟运行时间"（vruntime）
  - 总是选择 vruntime 最小的进程运行
  - 公平性：所有进程获得等比例 CPU 时间

  关键数据结构：
  - 红黑树：按 vruntime 排序
  - O(log n) 的进程选择
  - 增加进程/移除进程/选择下一个进程

  关键概念：
  - 权重（weight）：决定进程占用 CPU 的比例
  - 优先级（prio）：影响 weight
  - 实际时间 vs 虚拟时间
  - nice 值：-20 ~ 19

1.2 调度策略

1
2
3
4
5
6
7
8
9
10
11
# 查看进程调度策略
chrt -p <pid>          # SCHED_FIFO / SCHED_RR / SCHED_OTHER
ps -o pid,cls,pri,rtprio,cmd -p <pid>

# 设置实时优先级
chrt -f -p 99 <pid>     # SCHED_FIFO, 优先级 99
chrt -r -p 99 <pid>     # SCHED_RR

# 设置 CPU 亲和性
taskset -p 0x3 <pid>     # 绑定到 CPU 0,1
taskset -pc 0-3 <cmd>   # 启动时绑定

1.3 进程状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
进程状态：

  NEW (创建)
    ↓
  READY (就绪，等待调度)
    ↓ schedule
  RUNNING (运行)
    ↓ 时间片用完/阻塞
  READY / BLOCKED
    ↓
  BLOCKED (等待 I/O / 信号 / 锁)
    ↓ 事件就绪
  READY
    ↓ exit
  EXIT (退出，僵尸)

Linux 中实际状态：
  - TASK_RUNNING (R)：就绪或运行
  - TASK_INTERRUPTIBLE (S)：可中断睡眠
  - TASK_UNINTERRUPTIBLE (D)：不可中断睡眠
  - TASK_STOPPED (T)：已停止
  - TASK_TRACED：被跟踪
  - EXIT_ZOMBIE (Z)：僵尸
  - EXIT_DEAD：已释放

1.4 调度延迟

1
2
3
4
5
6
7
8
9
CFS 目标：
  - 任何任务都能在「目标延迟」内获得一次运行机会
  - 目标延迟 = sysctl_sched_latency（默认 6ms）
  - 时间片 = 目标延迟 / 任务数

  例：
    1 个任务：6ms 时间片
    10 个任务：600μs 时间片
    100 个任务：60μs 时间片

1.5 调度域（sched_domain）

1
2
3
4
5
6
7
8
9
10
11
多核调度：

  调度域：CPU 拓扑被组织为多个调度域
    - SMT 域（超线程）
    - MC 域（一个 socket 的所有核）
    - NUMA 域（跨 socket）

  调度粒度：
    - 同一物理核的超线程竞争（负载均衡）
    - 同一 socket 的核（缓存共享）
    - 跨 socket（远程访问）

2. 虚拟内存

2.1 虚拟地址到物理地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
地址翻译过程：

  虚拟地址 VA (48-bit)
  ┌──────────┬──────────┬──────────┬──────────┐
  │   PGD    │   PUD    │   PMD    │   Offset │
  │ (9 bit)  │ (9 bit)  │ (9 bit)  │ (12 bit) │
  └────┬─────┴────┬─────┴────┬─────┴────┬─────┘
       │          │          │          │
       ▼          ▼          ▼          │
   PGD 页表   PUD 页表   PMD 页表       │
   (entry)    (entry)    (entry)        │
       │          │          │          │
       └──────────┴──────────┘          │
                                     │
  物理地址 PA：page_frame_number | Offset

2.2 TLB（Translation Lookaside Buffer）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TLB：地址翻译缓存

  - 缓存虚拟页 → 物理页的映射
  - 通常 64-1024 项
  - 命中：1 个 cycle
  - 未命中：需访问页表（数十个 cycles）

  TLB miss 后果：
  - 性能下降 10-100x
  - 高负载时 TLB miss 占 CPU 时间 30%+

  优化：Hugepage（之前讲过）
    - 2MB 大页：TLB 覆盖 512x 范围
    - 1GB 大页：覆盖 262144x 范围

2.3 TLB shootdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
多核 TLB 一致性：

  问题：
  - 一个 CPU 修改了页表
  - 其他 CPU 的 TLB 还有旧映射
  - 需要失效（invalidate）其他 CPU 的 TLB

  解决：
  - IPI（Inter-Processor Interrupt）
  - TLB shootdown IPI
  - 范围：失效特定虚拟地址

  性能影响：
  - 大量 TLB shootdown 严重降级性能
  - 优化：减少页表修改（如使用 hugepage）

2.4 内存映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 进程虚拟内存布局（典型 64-bit Linux）：

0x0000000000000000 ┌──────────────┐
                    │  空（保留）    │
0x0000555555554000 ┌──────────────┐
                    │  .text 段     │  ← 代码
                    │  .rodata     │  ← 只读数据
                    │  .data       │  ← 已初始化数据
                    │  .bss        │  ← 未初始化数据
                    │  堆（向上增长） │  ← malloc
0x00007fff00000000 ┌──────────────┤
                    │  共享库       │  ← libc.so
                    │  栈（向下增长）│  ← 局部变量
0x00007fffffffe000 ┌──────────────┤
                    │  内核空间     │  ← 内核（用户不可访问）
                    └──────────────┘

3. 缓存与一致性

3.1 多级缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
典型 CPU 缓存层次（Intel）：

  ┌─────────────┐
  │   L1 缓存   │  32 KB  ~1ns  (per core)
  │  (D + I)    │
  ├─────────────┤
  │   L2 缓存   │  256 KB  ~4ns  (per core)
  ├─────────────┤
  │   L3 缓存   │  8-30 MB  ~12ns  (shared)
  ├─────────────┤
  │   主内存    │  32+ GB  ~100ns
  └─────────────┘

  访问时间差：
    - L1 hit vs main memory: 100x
    - L2 hit vs main memory: 25x
    - L3 hit vs main memory: 8x

3.2 缓存行（Cache Line）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Cache Line = 缓存最小单位（64 字节）

对齐 64 字节的 struct：
  struct foo {
      int a;        // 4 bytes
      char pad[60]; // 填充到 64
  } __attribute__((aligned(64)));

False sharing 问题：
  ┌──────────────────────────────────────┐
  │ Cache Line (64 bytes)                │
  ├────────┬────────┬────────┬─────────┤
  │ CPU 0  │ CPU 1  │ CPU 2  │ CPU 3   │
  │ 写的变量│ 写的变量│ 写的变量│ 写的变量│
  └────────┴────────┴────────┴─────────┘
  → 任何一个 CPU 写，都导致其他 CPU 缓存失效！
  → 性能下降 10-100x

解决方案：
  - Per-CPU 数据：每个 CPU 独立
  - 缓存行填充：每个变量占满一个 cache line

3.3 MESI 协议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MESI（缓存一致性协议）：

  状态：
  M (Modified)：已修改，与主存不一致
  E (Exclusive)：独占，与主存一致
  S (Shared)：共享，多个核有相同数据
  I (Invalid)：失效

  转换：
  - 读：I → S（如果其他核已读）/ E（独占）
  - 写：S → M（需要 Invalidate 其他核的 S 状态）
  - E → M（本地修改）

  性能：
  - 命中：L1 1 cycle
  - S → M：需要广播 RFO（Read For Ownership），~20-50 cycles

4. 内存屏障

4.1 重排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
为什么需要内存屏障？

  CPU 为了性能，会重排序指令：
  - 编译器重排序
  - CPU 硬件重排序

  例：
  // 线程 A：
  data = 1;        // 写
  ready = true;     // 写

  // 线程 B：
  while (!ready);   // 读
  print(data);      // 读
  // 可能：CPU 重排了 A 的写 → B 看不到 data=1

  解决：内存屏障（memory barrier）

4.2 内存屏障类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// === Linux 内核内存屏障 ===

// 通用屏障（完全屏障）
smp_mb();    // 阻止所有重排序

// 写屏障（仅写操作顺序）
smp_wmb();    // 之前的写都完成，才执行之后的写

// 读屏障（仅读操作顺序）
smp_rmb();    // 之前的读都完成，才执行之后的读

// === 编译器屏障（防止编译器重排，CPU 可重排） ===
barrier();

// === ARM 架构 ===
// dmb（Data Memory Barrier）
// dsb（Data Sync Barrier）
// isb（Instruction Sync Barrier）

4.3 acquire/release 语义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Acquire：之后的读写不能提前
// Release：之前的读写不能推后

// 写锁释放
spinlock_release(lock);
data = 42;       // 必须在释放锁之前对其他核可见
flag = true;     // 释放锁

// 读锁获取
if (flag) {
    spinlock_acquire(lock);
    // 读取 data 保证看到 42
    print("%d", data);
}

// Linux 中：
// smp_store_release(&flag, 1);
// if (smp_load_acquire(&flag)) { ... }

5. 原子操作

5.1 原子操作 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// === Linux 内核原子操作 ===

#include <linux/atomic.h>

// 整型原子
atomic_t v = ATOMIC_INIT(0);

atomic_set(&v, 5);
atomic_inc(&v);
atomic_dec(&v);
atomic_add(&v, 3);
atomic_sub(&v, 2);

int old = atomic_read(&v);

// CAS（Compare And Swap）
int old = atomic_cmpxchg(&v, expected, new);
// 如果 v == expected，v = new，返回 old
// 否则返回 v 的旧值

// 64 位
atomic64_t v = ATOMIC64_INIT(0);

// === 用户态（GCC 原子） ===
#include <stdatomic.h>

atomic_int v = 0;
atomic_fetch_add(&v, 1);  // 返回旧值
__atomic_compare_exchange_n(&v, &expected, new, ...);

5.2 无锁数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// === 无锁计数器 ===
// 关键：原子操作 + 内存屏障

struct counter {
    atomic_long_t value;
};

void counter_inc(struct counter *c) {
    // 原子加即可，无需额外屏障
    atomic_long_inc(&c->value);
}

// === 无锁队列（CAS 实现） ===
struct node {
    int val;
    struct node *next;
};

struct lock_free_queue {
    atomic_long_t head;  // 头指针（生产端）
    atomic_long_t tail;  // 尾指针（消费端）
};

void lfq_push(struct lock_free_queue *q, int val) {
    struct node *n = malloc(sizeof(*n));
    n->val = val;
    n->next = NULL;

    struct node *tail;
    do {
        tail = (struct node *)atomic_long_read(&q->tail);
    } while (atomic_long_cmpxchg(&q->tail,
                                  (long)tail, (long)n) != (long)tail);

    // 之前的 tail 节点的 next 指向 n
    // ... 需要处理 race
}

// === 无锁单生产者单消费者队列（SPSC） ===
// 简单且高效

struct spsc_queue {
    void **ring;
    int capacity;
    atomic_int head;  // 生产者写
    atomic_int tail;  // 消费者读
};

int spsc_push(struct spsc_queue *q, void *val) {
    int h = atomic_load_explicit(&q->head, memory_order_relaxed);
    int t = atomic_load_explicit(&q->tail, memory_order_acquire);

    if ((h + 1) % q->capacity == t) return 0;  // 满

    q->ring[h] = val;
    atomic_store_explicit(&q->head, (h + 1) % q->capacity,
                          memory_order_release);
    return 1;
}

void *spsc_pop(struct spsc_queue *q) {
    int t = atomic_load_explicit(&q->tail, memory_order_relaxed);
    int h = atomic_load_explicit(&q->head, memory_order_acquire);

    if (t == h) return NULL;  // 空

    void *val = q->ring[t];
    atomic_store_explicit(&q->tail, (t + 1) % q->capacity,
                          memory_order_release);
    return val;
}

6. 锁的深入

6.1 锁类型对比

锁 适用 性能
spinlock 短临界区、单核外 中（忙等）
mutex 通用、可能阻塞 中（含睡眠切换）
rwlock 读多写少 读快写慢
seqlock 极少写多读 读极快
RCU 极少写 读无开销
futex 用户态同步 内核态最轻

6.2 RCU 机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
RCU（Read-Copy-Update）：

  适用场景：
  - 读多写极少（如路由表、配置）
  - 读端不能阻塞
  - 写端可以阻塞

  三个关键点：
  1. 读端：用 rcu_read_lock() / rcu_read_unlock() 保护
     - 无锁读
     - 不会阻塞

  2. 写端：
     - 创建新副本
     - 修改副本
     - 用 rcu_assign_pointer() 替换指针
     - 等待所有读者退出（synchronize_rcu()）
     - 释放旧副本

  性能：
  - 读端：0 开销（无锁）
  - 写端：需要等待所有读者

  应用：路由表、fd 表、内存分配器

6.3 futex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// futex：用户态同步原语
// 避免无竞争的 syscall

// 简单实现
int futex_wait(int *uaddr, int expected) {
    if (*uaddr != expected) return 0;  // 已被改变，不等
    // 真的等待（syscall 进入内核）
    syscall(SYS_futex, uaddr, FUTEX_WAIT, expected, NULL);
    return 0;
}

int futex_wake(int *uaddr, int count) {
    syscall(SYS_futex, uaddr, FUTEX_WAKE, count);
    return 0;
}

// pthread_mutex 是基于 futex 实现的
// 无竞争时：纯用户态操作（CAS）
// 有竞争时：进入内核（futex）

7. 中断与软中断

7.1 中断分层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Linux 中断处理层次：

  硬中断（Top Half）
    - 极短，只做最必要
    - 标记需要处理的数据
    - 唤醒软中断
    - 在中断上下文中

  软中断（Bottom Half / ksoftirqd）
    - 可被调度
    - 完成大部分工作
    - 在进程上下文中可睡眠
    - 由 ksoftirqd 内核线程处理（高负载时）

  tasklet（基于 softirq）
    - 简化版软中断
    - 不能睡眠
    - 同一类型不能并发（vs 软中断可）

  workqueue
    - 可睡眠
    - 由 worker thread 执行

7.2 网卡中断负载均衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
问题：
  单个网卡的硬中断都在 CPU 0
  → CPU 0 满载
  → 其他 CPU 闲置

解决：

1. RSS（硬件）：网卡多队列分配
   - 网卡有 4/8/16 个 RX 队列
   - 每个队列分配不同 CPU
   - 不同连接落到不同队列
   - 但需要网卡支持

2. RPS（软件）：在驱动后多核分发
   echo "f" > /sys/class/net/eth0/queues/rx-0/rps_cpus
   # f = 0-3
   - 适合所有网卡
   - 软件开销小

3. RFS（软件）：与应用 CPU 亲和
   echo 32768 > /proc/sys/net/core/rps_sock_flow_entries
   - 提高缓存命中率
   - 应用在 CPU 0 处理 → 收包中断到 CPU 0

4. 队列数与 CPU 数对齐
   - 1:1 映射最佳
   - 避免多个队列绑到同一 CPU

8. 进程、线程、协程对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
进程（Process）：
  - 独立地址空间
  - 重量级（创建/切换慢）
  - 隔离性好

线程（Thread）：
  - 共享地址空间（同一进程内）
  - 中量级
  - 共享需要同步

协程（Coroutine）：
  - 用户态线程
  - 极轻量（切换只需几条指令）
  - 协作式调度
  - 例：Go goroutine, C++20 coroutine, libco

goroutine 实现（Go）：
  - 用户态调度器
  - M:N 调度（M 线程跑 N 协程）
  - work stealing
  - 抢占式（基于协作）

9. 常见面试题

9.1 进程 vs 线程

1
2
3
4
5
6
7
Q：进程和线程的区别？
A：
  1. 资源占用：进程独立地址空间，线程共享
  2. 创建/切换开销：线程轻量
  3. 隔离性：进程隔离，线程共享（一个崩溃影响其他）
  4. 通信：进程用 IPC（pipe/socket），线程可直接共享
  5. 多核利用：进程/线程都能多核

9.2 协程 vs 线程

1
2
3
4
5
6
7
Q：协程和线程的区别？
A：
  1. 调度：协程协作式，线程抢占式
  2. 切换开销：协程用户态（< 1μs），线程内核态（10μs+）
  3. 并行：线程可多核并行，协程通常单线程
  4. 适用：协程适合 I/O 密集，线程适合 CPU 密集
  5. 调试：协程更难（栈信息不完整）

9.3 内存屏障

1
2
3
4
5
6
7
8
9
10
11
12
Q：什么是内存屏障？为什么需要？
A：
  内存屏障是 CPU 指令，防止编译器和 CPU 重排序。
  
  例：双线程的发布订阅模式
    线程 A：data=1; ready=true;
    线程 B：while(!ready) print(data);
  
  如果没有内存屏障，A 的写可能被重排为 ready=true; data=1;
  B 看到 ready=true 后读 data，可能读到 0。
  
  解决：smp_store_release(&ready, true) + smp_load_acquire(&ready)

9.4 CAS 的 ABA 问题

1
2
3
4
5
6
7
8
9
10
11
12
13
Q：什么是 CAS 的 ABA 问题？
A：
  CAS（Compare-And-Swap）比较并交换。
  假设：
    1. 读 v=A
    2. 另一个线程将 v 改为 B，又改回 A
    3. CAS 看到 v==A，交换成功
  但实际值已经变化过。
  
  解决：
  - 加版本号（双字 CAS）
  - 用 LL/SC 指令（如 ARM）
  - 延迟回收（hazard pointer）

9.5 进程/线程切换的开销

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Q：进程切换的开销来自哪里？
A：
  1. 切换页表（CR3）→ TLB 失效 → TLB miss 风暴
  2. 保存/恢复寄存器
  3. 调度器开销
  4. 缓存失效（代码、数据）
  
  线程切换：
  1. 保存/恢复寄存器
  2. 切换栈
  3. 缓存失效（数据）
  
  协程切换：
  1. 切换栈
  2. 保存/恢复少量寄存器
  3. 用户态，几乎无缓存失效

9.6 CPU 缓存一致性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Q：多核 CPU 如何保证缓存一致性？
A：
  MESI 协议：
  - Modified：已修改（脏）
  - Exclusive：独占（与主存一致）
  - Shared：共享（多个核有相同数据）
  - Invalid：失效
  
  流程：
  1. CPU A 写 X：从其他核广播 "Invalidate X"
  2. 其他核收到，标记 X 为 Invalid
  3. CPU A 收到确认，标记 X 为 Modified
  4. 后续 CPU A 读 X 直接命中（独占）
  
  性能开销：
  - 总线带宽
  - CPU 等待
  - 优化：减少 false sharing

10. 实战：内核配置优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# === CPU 调度调优 ===
# 查看 CFS 目标延迟
cat /proc/sys/kernel/sched_latency_ns  # 默认 6ms

# 调整为更小（适合短任务）
echo 3000000 > /proc/sys/kernel/sched_latency_ns

# 调整迁移成本（多核负载均衡）
echo 500000 > /proc/sys/kernel/sched_migration_cost_ns

# === 内存调优 ===
# TLB 优化
echo always > /sys/kernel/mm/transparent_hugepage/enabled

# 内存回收策略
echo 1 > /proc/sys/vm/zone_reclaim_mode  # NUMA 友好

# === 中断负载均衡 ===
echo "f" > /sys/class/net/eth0/queues/rx-0/rps_cpus

# === 内核参数综合调优 ===
cat >> /etc/sysctl.d/99-net-tuning.conf <<EOF
# 调度
kernel.sched_latency_ns = 6000000
kernel.sched_migration_cost_ns = 500000
kernel.sched_min_granularity_ns = 750000

# 内存
vm.zone_reclaim_mode = 1
vm.swappiness = 10

# 网络
net.core.somaxconn = 65535
net.ipv4.tcp_tw_reuse = 1
EOF

sudo sysctl -p /etc/sysctl.d/99-net-tuning.conf

11. 资源推荐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
必读：
  - 《深入理解 Linux 内核》（第 3 章进程、第 4 章中断、第 8 章虚拟内存）
  - 《操作系统：精髓与设计原理》
  - Linux Kernel 官方文档

课程：
  - MIT 6.828（操作系统）
  - CMU 15-213（CSAPP）
  - B 站：哈工大李志军操作系统

资源：
  - Linux 内核源码（kernel.org）
  - perf + ftrace 工具
  - Brendan Gregg 的 perf 教程
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、Linux开发、
公众号开发、开源爱好者、Linux

联系QQ:562054870