课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一部分回顾Lecture 23至Lecture 24，介绍了并发编程。

备注：图片和总结内容均来自于课件。

说明：

大部分内容已经整理过，这里仅仅进行补充。

Lecture 23

并发编程很困难

  • 并发编程的经典问题类：
    • 竞争：结果取决于系统中其他地方的任意调度决策。
      • 示例：谁获得了飞机上的最后一个座位？
    • 死锁：资源分配不当阻碍前进。
      • 例子：交通拥堵。
    • 活锁/饥饿/公平：外部事件和/或系统调度决策可以阻止子任务的进展。
      • 例子：人们总是在你前面排队。

迭代服务器的基本流

迭代服务器一次处理一个请求：

解决方法是使用并发服务器，并发服务器使用多个并发流同时为多个客户端提供服务：

基于进程

优缺点

优点：

  • 并发处理多个连接；
  • 清晰的共享模型；
    • 描述符（否）
    • 文件表（是）
    • 全局变量（否）
  • 简单明了；

缺点：

  • 进程控制的额外开销；
  • 在进程之间共享数据非常重要
    • 需要 IPC（进程间通信）机制
      • FIFO（即管道）、System V 共享内存和信号量；

基于事件

优缺点

优点：

  • 一个逻辑控制流和地址空间；
  • 可以使用调试器单步执行；
  • 没有进程或线程控制开销；
  • 高性能Web服务器和搜索引擎的首选设计，例如，Node.js、nginx、Tornado；

缺点

  • 与基于进程或线程的设计相比，代码要复杂得多；
  • 难以提供细粒度的并发；
    • 例如，如何处理部分HTTP请求头；
  • 无法利用多核；
    • 单线程控制；

基于进程

进程的传统视角：

  • 进程 = 进程上下文 + 代码、数据和堆栈；

进程的另一个视角：

  • 进程 = 线程 + 代码、数据和内核上下文；

多进程示例：

线程的逻辑视角

  • 与进程关联的线程形成对等线程池，与形成树层次结构的进程不同；

线程 VS 进程

  • 线程和进程的相同点
    • 都有自己的逻辑控制流；
    • 都可以与其他人同时运行（可能在不同的内核上）；
    • 都能进行上下文切换 ；
  • 线程和进程的不同点
    • 线程共享所有代码和数据（本地堆栈除外） ；
      • 进程（通常） 不能共享；
    • 线程比进程开销小
      • 进程控制（创建和收割）是线程控制的两倍；
      • Linux上时间开销：
        • 创建和回收进程约20K周期；
        • 创建和收割线程约10K周期；

优缺点

优点：

  • 易于在线程之间共享数据结构，例如日志信息、文件缓存；
  • 线程比进程更高效；

缺点：

  • 无意共享可能会引入微妙且难以重现的错误！
    • 可以轻松共享数据是线程的最大优势也是最大的弱点；
    • 很难知道哪些数据是共享的，哪些是私有的；
    • 很难通过测试来检测；
      • 出现不好的竞争结果的概率非常低，但不是零！

Lecture 24

略过。

Lecture 25

略过。

Lecture 26

这部分介绍快排的并行版本。

串行快排

串行快排伪代码

对$N$个随机数构成的数组$X$进行排序：

  • 从$X$中选择“主元”$p$
  • 将$X$重新排列成
    • $L$：值$\le p$
    • $R$：值$\ge p$
  • 递归排序$L$，得到$L’$
  • 递归排序$R$，得到$R’$
  • 返回$L’ : p : R’$

串行快排可视化

并行快排

并行快排伪代码

  • 如果$N\le \mathrm{Nthresh}$，进行串行快排；
  • 其他情况：
    • 从$X$中选择“主元”$p$
    • 将X重新排列成
      • $L$：值$\le p$
      • $R$：值$\ge p$
    • 递归产生单独的线程
      • 递归排序$L$，得到$L’$
      • 递归排序$R$，得到$R’$
    • 返回$L’ : p : R’$

并行快排可视化

  • 任务：对数据的子范围进行排序
    • 指定为：
      • base：起始地址；
      • nele：子范围中的元素数；
  • 作为单独的线程运行

  • 使用串行快速排序对子范围进行排序

代码：

void tqsort(data_t *base, size_t nele) {
    init_task(nele);
    global_base = base;
    global_end = global_base + nele - 1;
    task_queue_ptr tq = new_task_queue();
    tqsort_helper(base, nele, tq);
    join_tasks(tq);
    free_task_queue(tq);
}

/* Multi-threaded quicksort */
static void tqsort_helper(data_t *base, size_t nele,
                          task_queue_ptr tq) {
    if (nele <= nele_max_sort_serial) {
        /* Use sequential sort */
        qsort_serial(base, nele);
        return;
    }
    sort_task_t *t = new_task(base, nele, tq);
    spawn_task(tq, sort_thread, (void *) t);
}

/* Thread routine for many-threaded quicksort */
static void *sort_thread(void *vargp) {
    sort_task_t *t = (sort_task_t *) vargp;
    data_t *base = t->base;
    size_t nele = t->nele;
    task_queue_ptr tq = t->tq;
    free(vargp);
    size_t m = partition(base, nele);
    if (m > 1)
        tqsort_helper(base, m, tq);
    if (nele-1 > m+1)
        tqsort_helper(base+m+1, nele-m-1, tq);
    return NULL;
}

小结

  • 必须有并行化策略
    • 分成$K$个独立的部分；
    • 分而治之；
  • 内循环必须是无同步的
    • 同步操作非常昂贵；
  • 当心阿姆达尔定律
    • 串行代码可能成为瓶颈；
  • 你可以做到！
    • 实现适度的并行性并不困难；
    • 建立实验框架并测试多种策略；

存储一致性

不可能的结果：

  • 1, 100; 100, 1

用状态标记每个缓存块

  • 无效（Invalid）：不能使用值；
  • 共享（Shared）：可读副本；
  • 独占（Exclusive）：可写副本；

示例：