课程主页: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):可写副本;

示例: