CPU/内存虚拟化, 调度和并发

发表于 更新于 分类于 阅读次数：

本文是 OSTEP (Operating System: Three Easy Pieces) 的简单笔记, 由于 OSTEP 和我写博客的叙述思路很像(日常往自己脸上贴近hhh), 所以这里就只列一个大纲供自己复习.

并且本文建立在 一条操作系统的使命 | Amiriox’s Storage 和 CSAPP3e第六章(存储器层次结构) | Amiriox’s Storage 两篇文章的叙述之上, 仅仅增量补充了必要的内容

一些重要的主题 (如调度和并发) 可能 (几乎是一定) 会单独开一篇文章, 在基于这本书介绍的内容下再补充一些我其他地方学到的相关知识和经验.

OSTEP 是一本无论从知识本身还是讲解技巧上都比较不错的书, 推荐读原书而非总结博客.

CPU 虚拟化:

(机制)时钟中断:

  1. 时钟中断的意义: 定期把控制权交还给操作系统
  2. 初始化陷阱表
  3. 时钟中断保存和恢复的上下文由硬件操作(很有限), 操作系统执行的上下文切换(如调度)保存和恢复的状态更多
  4. 协作式可能导致恶意程序一直抢占CPU

测量上下文中断: 把两个进程绑定到同一cpu, 然后利用两个管道导致两个进程阻塞, 强迫 Linux CFS 根据亲和性轮流调度这两个进程 ( gettimeofday 的精度其实不太够看, 懒得改了)

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
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <sys/time.h>
#include <sys/wait.h>
#include <unistd.h>

#define ITERATIONS 1000000

void bind_to_cpu0(pid_t pid) {
    cpu_set_t mask;
    CPU_ZERO(&mask);
    CPU_SET(0, &mask);
    sched_setaffinity(pid, sizeof(mask), &mask);
}

signed main() {
    /* WARN: No check func() < 0 */
    int pipe1[2], pipe2[2];
    pipe(pipe1);
    pipe(pipe2);

    bind_to_cpu0(0); // child extends from father

    /**
     * lmbench
     * F [1]pipe1[0] C
     * C [1]pipe2[0] F
     */
    int child = fork();
    if (child == 0) {
        // child
        close(pipe1[1]);
        close(pipe2[0]);

        char c;
        for (int i = 0; i < ITERATIONS; i++) {
            read(pipe1[0], &c, 1);
            write(pipe2[1], "c", 1);
        }
    } else {
        // father
        close(pipe1[0]);
        close(pipe2[1]);

        printf("Clock is on.\n");
        struct timeval st, ed;
        gettimeofday(&st, NULL);
        char c;
        for (int i = 0; i < ITERATIONS; i++) {
            write(pipe1[1], "c", 1);
            read(pipe2[0], &c, 1);
        }
        gettimeofday(&ed, NULL);
        int wc = wait(NULL);

        long total_us = (ed.tv_sec - st.tv_sec) * 1000000LL + (ed.tv_usec - st.tv_usec);
        double result_us = (double)total_us / (ITERATIONS * 2.0);
        printf("Total: %ld us (%ld ns)\n", total_us, total_us * 1000);
        printf("Cost of context switch: %lf us (%lf ns)\n", result_us, result_us * 1000);
    }
    return 0;
}

(策略)进程调度:

  1. 进程调度与线程调度
  2. 调度指标: 周转时间(T完成-T初次开始); 公平性; 响应时间
  3. 假设能够得知所有任务时长; 假定所有任务同时到达(T初次开始相同), 假设所有任务时长相等
  • FIFO: 简单 | 周转时间无法保证, 公平性无法保证, 响应时间无法保证.
  1. 假设能够得知所有任务时长; 假定所有任务同时到达(T初次开始相同)
  • SJF: 短的任务先做可以避免护航效应, 周转时间短 | 实际情况中任务不一定同时到达
  1. 假设能够得知所有任务时长;
  • STCF: 对 SJF 添加抢占, 新工作进入系统时 reschedule 找能最快完成的任务 | 响应时间差
  • RR: 为每个任务分配时间片, 时间片用完 reschedule | 响应时间快, 公平; 周转时间长, 需要考虑上下文切换开销和时间片大小的平衡
  • 关于 I/O: 在 I/O 时可以调度其他任务实现 overlap. (未来)
  1. 无假设:
  • MLFQ:
    1. 设置多个队列, 每个队列有不同的优先级, 容纳一些任务
    2. 若 A 所在队列优先级 > B 所在队列优先级, 则运行 A 而不运行 B
    3. 如果 A B 在同一队列(优先级相同), 分配相同长度时间片轮转 A 和 B 缺点: 如果有两个任务 A 和 B 在最高优先级队列, 低一些优先级的 C 会一直饿死
    4. 任务初次进入加入最高优先级队列 4a. 任务用完整个时间片(优化: 某任务在某优先级的配额)后降低一个优先级 4b. 如果任务在用完时间片之前就主动释放 CPU, 则优先级不变 缺点: 多个交互型工作 I/O 过多使得这些工作长久占用 CPU, 其他任务饿死.
    5. 一定时间后洗牌: 将所有任务放在最高优先级
  • CFS:
    1. \(vruntime_{tid} = init\_time_{tid} + \frac{\delta}{prior}\)
    2. 新任务 vruntime 初始化为 最小值, 让其尽快被调度(响应时间快)
    3. 每次时钟中断时 \(\delta\) 递增, 除以 \(prior\) 优先级
    4. vruntime 最小的放在任务调度队列队首
  • 其他: BFS

(策略)多处理器调度:

(SMP 对称多处理架构上的操作系统支持)

  1. 缓存一致性: (多处理器有分别的 L1/2/3 缓存) : 总线窥探 (监听对某个地址的读写, 作废缓存)
  2. 同步: 加锁/原子操作
  3. 缓存亲和度: (反复作废缓存太浪费了):
    1. 单队列调度所有任务导致需要对队列加锁保证原子性, 而且缓存亲和度差
    2. 多队列调度: 避免加锁, 但不对称的任务数可能导致负载不均(1 队列 A, 2 队列 B, C, 则 A 获得了 B/C 两倍的时间片)
    3. 多队列调度+任务迁移: B 反复在 CPU1 和 CPU2 两个队列之间迁移, 保证公平

内存虚拟化

  1. 现代操作系统已经弱化了分段的概念, 主要以分页+逻辑段为主
  2. 地址空间: (不)透明(抽象屏障) + 保护 +- 效率, 为实现地址空间, 实现地址转换 ## (机制)地址转换

将物理地址映射到虚拟地址, 应用程序仅能够使用虚拟地址(除非读/proc), 由 MMU 翻译回物理地址来访问

由于 MMU 并不知道具体的翻译规则, 所以需要读取 OS 放置在内存某处中的某些映射规则(如分段或页表), 而访存相比位于 CPU 的 MMU 是很慢的, 所以需要 TLB 作为缓存:

  • TLB 是全相联缓存, 只有一个组所以不需要组索引, 标记为 VPN 号, 块偏移为虚拟地址的页内偏移
  • 上下文切换时需要 flush TLB (或支持 ASID 位的多任务共享 TLB)
  • 替换策略一般是 LRU

(策略)分页:

  1. 把整块虚拟内存分为定长的页映射到同样划分的虚拟内存(但映射关系由页表项决定), 称之为页帧(一般为 4 KB). 在页帧上映射逻辑段进去(如代码段/数据段/栈等)
  2. 根据页数将虚拟地址的前几位划分为虚拟页号, 余下位为页内偏移
  3. 页表条目
  4. 多级页表: [CSAPP 的图] 更好一些. 虚拟页号分为几个部分(取决于页表级数), 分别对应每一级页表的索引, 最后在最低级页表中找到实际包含物理地址数据的页表条目, 然后和偏移合并起来

Linux 中的内存管理:

  • mmap: 文件映射, 匿名映射

  • (机制)交换到磁盘(存在位与 PAGE_FAULT, 内存中页的换出(交换)策略, 高低水位线)

  • (策略)内存中页的换出策略: Optimal, FIFO, Random, LFU, LRU, ### Windows 中的内存管理:

  • 提交页, 分配页

    利用分页的 TLB miss 测量 L1/L2 缓存大小

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
72
#define _GNU_SOURCE
#include <assert.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

int NUMOFPAGES, ITERATIONS;

double iter(int total_pages, const int *page_indices, int *arr) {
    int PAGESIZE = getpagesize();
    int stride = PAGESIZE / sizeof(int);
    
    struct timespec st, ed;
    clock_gettime(CLOCK_MONOTONIC, &st);

    for (int it = 0; it < ITERATIONS; ++it) {
        for (int i = 0; i < total_pages; ++i) {
            int page_index = page_indices[i];
            arr[page_index * stride] += 1;
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &ed);
    
    long long duration_ns = (ed.tv_sec - st.tv_sec) * 1000000000LL + (ed.tv_nsec - st.tv_nsec);

    return 1.0 * duration_ns / ITERATIONS / total_pages; // result is in ns
}

signed main(int argc, const char **argv) {
    assert(argc == 3);

    cpu_set_t mask;
    CPU_ZERO(&mask);
    CPU_SET(0, &mask);
    sched_setaffinity(0, sizeof mask, &mask);

    NUMOFPAGES = atoi(argv[1]);
    ITERATIONS = atoi(argv[2]);

    int *page_indices = malloc(sizeof(int) * NUMOFPAGES);
    assert(page_indices != NULL);
    for (int i = 0; i < NUMOFPAGES; i++) {
        page_indices[i] = i;
    }
    srand(time(NULL));
    for (int i = NUMOFPAGES - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = page_indices[i];
        page_indices[i] = page_indices[j];
        page_indices[j] = temp;
    }

    int PAGESIZE = getpagesize();
    int stride = PAGESIZE / sizeof(int);
    int max_length = NUMOFPAGES * stride;
    int *arr = (int *)malloc(sizeof(int) * max_length);
    assert(arr != NULL);
    memset(arr, 0, sizeof(int) * max_length);

    for (int p = 1; p <= NUMOFPAGES; p *= 2) {
        printf("%d pages:\t%lf ns\n", p, iter(p, page_indices, arr));
    }

    free(page_indices);
    free(arr);

    return 0;
}

(空闲空间管理: 内存分配)

相邻合并的空闲链表+各种匹配机制 Slab / Buddy / TLSF

并发

多线程: 线程作为操作系统调度的单位, 但同一进程容器内的线程共享一片地址空间, 不过有自己独立的栈

共享数据导致了什么

从高级语言层面上看来是一个操作的很多操作实际上是分为多步实现的, 例如赋值包含了访存, 写入内存; 甚至对于 CISC, 很多指令也是分为多步实现的 (在 FDEMW 中的 D 阶段可能会拆分指令).

由于这样的行动分为多个步骤, 因此被打断时可能出现中间状态.

我们称”一次执行完毕, 即使被打断也不会出现中间状态, 要么是未执行要么是执行完毕”的操作为”原子操作”, 自然, 上述的操作都不是原子操作.

那么这个和多线程有什么关系呢? 同一进程内的所有线程共享进程的地址空间, 如果 A 线程的某操作被打断, 产生了中间状态, 而这个中间状态对 B 线程也是可见的, 很可能会影响到 B 线程的决策导致错误的语义. 调度是不可控的, 我们不能指望操作系统的调度程序本身拥有足够的智能来防止这样的情况出现. (硬要说原因的话, 一是性能不允许, reschedule 的次数还是比较多的, 要尽可能高性能; 二是这本身也不是调度程序的职责, 而是程序本身语义应该提供的保证)

总结一下就是: 访问共享资源时(最经典的情境就是多线程), 可能因为非原子化的操作执行错误的语义. 我们称这种情况为竞态条件, 称访问共享资源的这一段代码为临界区.

一个很自然的想法就是, 在执行非原子操作时, 让临界区中的共享资源暂时对其他线程不可见. 这就是”互斥锁”的概念, 在临界区开头加锁(获取锁), 令本线程独占这一资源(怎么有种”本小姐要独占你…“的感觉?), 其他线程暂时不可见, 在临界区结束后解锁(释放锁), 这样其他线程也可以获取锁并使得资源对自己可见.

pthread 库的互斥锁用起来比较麻烦, 需要手动初始化, 在代码块的前后调用 lock 和 unlock, 评价为没有 RAII 导致的, std::mutex 和 Mutex<T> 显然用起来更方便些. (尤其是后者加上生命周期, 对于某些临时变量的生命周期管理使得”忘了解锁”的现象更少, 参考 Rust Temporary Lifetimes and “Super Let” - Mara’s Blog 的开头部分)

  • 互斥锁的实现
    • 关闭中断的自旋锁
    • 常见CAS原子操作指令
    • 具体实现例子: Linux futex)
  • 并发数据结构:
    • 加锁(加锁的临界区范围尽可能小)
    • 无锁数据结构(依靠原子操作原语)
  • 生产者-消费者问题
  • 条件变量及其实现, 解决生产者-消费者问题
  • 信号量
    • 信号量实现互斥锁(二值信号量)
    • 信号量实现条件变量
    • 信号量解决生产者-消费者问题
    • 信号量实现读写锁(读写锁与 Rust 引用规则: 可变性与别名问题)
    • 信号量实现哲学家就餐问题
  • 并发问题:
    • 未锁定执行顺序
    • 未保证原子语义
    • 死锁, 避免死锁的原则(顺序一致性)
  • 基于实现的并发:
    • I/O 多路复用 (select/poll/epoll)
    • 异步 I/O (Linux 的 io_uring)
  • 总结: 生产者消费者模型 -> 环形缓冲区 -> 异步 I/O -> 实例: io_uring 或 VirtIO 虚拟队列的可用环/已用环