并发编程基本概念

• 并发：多个逻辑控制流的生命周期有重叠，即称为并发现象(concurrency)
• 并行：发生在多核/多计算机上的并发现象（在一个时刻上存在多个逻辑控制流），称为并行现象（parallel），是并发现象的真子集；

并发程序的三种构造方式：

• 进程：每个逻辑控制流实现为一个进程
  • 特点：独立的虚拟地址空间
  • 优点：独立则不易混淆
  • 缺点：
    • 独立则难以共享数据
    • 进程context切换和IPC开销高，所以往往比较慢（ 进程间通信机制）
• I/O多路复用：状态机化，逻辑控制流的切换实现为状态机的状态切换。具体原理看这个
  • 优点：共享数据容易，并且没有进程context切换的开销
  • 缺点：编码复杂，不能充分利用多核处理器
• 线程：重点，下面展开讲。

线程基本概念：

• 主线程：进程中第一个运行的线程
• 对等线程：进程中后来运行的线程
• 与进程的区别：
  • 上下文内容少，切换更快，开销更少，具体包括：线程ID、栈和栈指针、PC、条件码、register value
  • 一个进程的所有线程（对等线程池）彼此之间没有层次结构，都是对等的；
  • 对等线程之间共享进程的虚拟地址空间，可以等待另外一个对等线程终止或主动杀死它
• 共享变量：一个变量的一个实例被不止一个线程引用，那么这个变量称为共享变量
• 线程安全的函数：被多个并发线程反复调用时能够一直产生正确结果的函数称为线程安全函数
• 可重入函数：线程安全函数的一个真子集，指不会引入任何共享数据的函数
  • 显式可重入：传参均为值传递（且非指针值传递），而且所有数据引用的都是本地自动栈变量
  • 隐式可重入：在显式的基础上取消“值传递（且非指针值传递）”的限制，允许指针值传递和引用传递，但是传递的变量都是非共享变量时，该函数是隐式可重入的
• 竞争：程序的正确性依赖于某条/某些特定的轨迹线，或者说不是全部的轨迹线都能让程序正确执行，哪怕是那些绕过了互斥锁禁止区的全部轨迹线也不行。（具体例子见CSAPP P719）

Posix线程模型：

管理Linux线程的C语言接口包，包含大约60个函数。

• 线程例程概念：接受和返回一个void指针的函数类型，其内容为线程真正要做的事。若输入输出的参数较多，应封装为一个结构体。
• 常用的pthread函数：

  /*创建线程*/
  int pthread_creat(&tid, NULL, thread, NULL)
  //(返回线程ID，设置线程属性(高阶内容)，线程例程函数名，线程例程函数的传参)，成功返回0，否则非0
  
  /*终止线程*/
  //方式1：某个对等线程的例程函数执行完毕，该线程会隐式终止
  //方式2：某个对等线程调用pthread_exit函数，线程会显式终止，而且如果是主线程调用，它会等待所有其他对等线程终止后再终止（进程也被终止了）
  void pthread_exit(void *thread_return) //函数不返回（因为逻辑控制流都结束了啊），会将一些信息写到thread_return中
  //方式3：某个对等线程调用系统exit函数，终止其所属进程及该进程所有的线程
  //方式4：某个对等线程调用pthread_cancel函数，终止另一个对等线程
  int pthread_cancel(pthread_t tid)  //终止线程ID为tid的对等线程，成功返回0，否则非0
  
  /*回收已终止线程的资源*/
  int pthread_join(pthread_t tid, void**thread_return) //调用该函数的对等线程阻塞，等待线程ID为tid的对等线程结束，然后回收其资源后返回
  
  /*分离线程*/
  //一个线程的状态要么是detached要么是joinable，处于后者时意味着可以被其他线程杀死和回收资源，前者不可（自行终止，系统回收资源）
  int pthread_detach(pthread_t tid)  //调用该函数的对等线程将线程ID为tid的线程分离
  
  /*获取自身ID*/
  pthread_t pthread_self();

线程的内存模型（两个关键问题）

• 线程的内存模型是怎样的？——不是整齐清楚的。。。
• 变量的实例如何映射到线程的内存模型中？
  • 全局变量+局部的静态变量：一个进程中只有一个实例，任何线程均可引用；
  • 局部的自动变量：多个实例，由各个线程栈自行管理。

线程共享变量的冲突问题

关键字：进度图->信号量->PV操作->互斥锁->互斥锁加/解锁->死锁

• 进度图：注意把P/V操作放到线段上，状态放到端点上，这样端点的状态即可解释为执行P/V操作前或者P/V操作后
• 信号量s：一个非负整数全局变量
• PV操作（原子操作）：
  • P(s)操作：检查s是否为0；
    • 是，则调用该函数的线程在此处阻塞；
    • 否，则将s减1后继续向下执行；
  • V(s)操作：先将s加1，然后检查有么有因为P(s)阻塞的线程，如有则将完成其P操作，然后置为就绪状态（等待调度），若没有那就没有。。若有不止一个，就随机选择一个，反正只能一个（因为要完成P操作啊）
• 互斥锁：二元的信号量
• 互斥锁加/解锁：针对二元信号量的P/V操作
• 死锁：
  禁止区外存在这样一些状态点，既不能向右，也不能向上，因为向上会进入线程A的禁止区，向右会进入线程B的禁止区。
  
  通过以下原则来防止死锁：
  给定所有互斥操作的一个全序( 全序概念)，如果每个线程都是以该全序获得互斥锁并以相反的顺序（不是说全序的逆序，而是线程A和线程B释放的顺序相反）释放，那么这个程序就不会出现死锁。（但是该原则现在看下来只适用于两个线程，更多的线程就要用到更复杂的银行家算法了）
  
  例如：
  
  • 线程1： P(s) -> P(t) -> V(t) -> V(s);
  • 线程2： P(s) -> P(t) -> V(s) -> V(t);

并行程序的性能量化（暂时略过）

信号量用于共享资源调度（暂时略过）