er> 书中对于并发问题的引入举了一个比较有意思的例子: 当多个人共享同一个桃子的时候,所有人首先在视觉上看到了桃子,但是当多个人伸手去拿桃子的时候却会惊奇的发现桃子不见了

并发引入

  • 还是通过经典的线程同步的例子引出并发中线程安全的问题,和csapp中一样,把对于共享数据的处理拆分为指令级别的,之后说明在一个线程执行这些指令的过程中,可恶的中断调度其他线程导致线程安全问题,最后提出了各种解决线程安全问题的方式: 提供原子操作指令或者停止屏蔽中断

锁

锁的定义

  • 根据上面的讨论自然而然引出了锁的概念,一个锁其实就是一个变量,这一个变量中可以记录各种各样的信息,比如对于锁的标识,锁的状态甚至可以记录阻塞在锁上面的线程队列等信息

评价锁的指标

  • 正确性: 是否可以正确的完成互斥的任务
  • 公平性: 所有线程都可以拿到锁,放置某些线程因为拿不到产生的饥饿问题
  • 性能

实现一个锁

  • 一般而言,对于操作系统中某一个功能的支持或者某一个操作性能的提升一般都需要操作系统的支持和硬件的支持,硬件的支持主要用于提供各种可以使用的指令,操作系统的支持则是利用硬件提供的各种指令来操作数据结构完成对于操作的优化

硬件支持

  • 硬件支持主要是为操作系统各种操作的原子指令(这些指令的实现依赖于底层的数字逻辑结构),如下总结书中提到的几种可以用于实现锁的原子指令
测试并且设置指令
  • 测试并且设置指令运行把设置一个内存空间处的值为新的值并且返回旧的值这一个操作作为一个原子指令,相似的原子指令比如x86中的xchg指令,实现的功能如下:
int TestAndSet(int* old_ptr , int new) {
	int old = *old_ptr;
	*old_ptr = new;
	return old;
}
  • 所以依赖于这一个指令,可以利用如下操作实现互斥锁: Pasted image 20241102150859.png
  • 上面的锁,当线程被阻塞的时候就会不断判断条件并且阻塞等待,这一个过程成为自旋,所以这一个锁被称为自旋锁
  • 对于自旋锁的评价:
    • 正确性: 可以保证互斥性
    • 公平性: 自旋的线程会在阻塞处不断自旋占用CPU,没有公平性,会导致自旋操作不断占用CPU,执行其他任务的线程占用CPU的时间减少或者拿不到锁而饿死
    • 性能: 单CPU上性能不好,多CPU上由于执行任务的线程和自旋的线程可以在不同的CPU上面执行所以性能不错
比较并且交换指令
  • 指令的伪C代码实现:
int CompareAndSwap(int* ptr , int expected , int new) {
	int actual = *ptr;
	if(actual == expected) 
		*ptr = new;
	return actual;
}
  • 利用这一条指令实现锁: Pasted image 20241102151552.png
  • 但是以上实现的还是自旋锁,还是会导致以上的问题
链接的加载和条件式存储指令
  • 原子指令的伪C代码实现: Pasted image 20241102151753.png
  • 利用这一条指令实现锁: Pasted image 20241102151950.png
获取并且添加指令
  • 获取并且添加指令的实现方式如下:
int FetchAndAdd(int* ptr) {
	int old = *ptr;
	*ptr = old + 1;
	return old;
}
  • 利用这一条指令可以实现tickets锁: Pasted image 20241102152323.png
  • 以上实现锁的过程保证了每一个尝试的线程都可以获取到锁,保证了公平性
  • 最后可以发现如何仅仅依靠硬件层面实现的原子指令来实现锁,那么难以保证自旋过多的问题,所以此时就需要软件(操作系统)支持了

操作系统支持

  • 通过操作系统支持,可以提供各种数据结构或者系统调用来控制进程的调度
自旋的时候让出CPU
  • 最简单的一种方法: 自旋的时候让出CPU: Pasted image 20241102152810.png
  • 但是利用这一种方式当很多线程同时竞争一把锁的时候就会导致很多线程不断处理礼让-自旋的这一种的状态中,也就是不可以让自旋的进程处于就绪状态
使用队列: 休眠替代自旋
  • 一种比较巧妙的方法就是让自旋的线程进入休眠状态,同时所有休眠状态中的线程被放入到队列中,实现方法如下: Pasted image 20241102153342.png
  • 这一种方法就使得自旋的线程在经过一次条件判断之后都处于休眠状态了,减少了自旋线程对于CPU的占用
两阶段锁
  • 核心思想: 如果第一个自旋阶段没有获取到锁,第二个阶段调用者就会休眠知道锁可以使用,比如Linux中就是使用这一种方式,并且Linux中设置自旋次数为1: Pasted image 20241102154851.png
  • 不太明白这一段代码

并发的数据结构

  • 有了互斥锁之后就可以利用互斥锁构建各种并发安全的数据结构,并且构建这一些数据的结构的时候都可以使用一个非常简单粗暴的方法(对于每一个操作都使用加锁的方式进行互斥),同时注意拓展性,拓展性也就是指在进行某一个操作的时候是否可以并发的操作数据结构的另外的部分,拓展性能的实现方式就是控制更小的锁的力度,比如对于链表,给链表的每一个节点上锁,对于队列,给队列头和队列尾上锁
  • 注意锁的语义: 就是保护相应的共享变量,比如对于队列头上的锁就是保护队列头部,里面就是操作头部的代码
  • 书中主要介绍了并发的计数器,链表,队列和散列表的数据结构 , 参考书中实现代码即可(也就是注意加锁的粒度即可),另外注意并发计数器的实现方式即可(惊为人天的一种操作)

条件变量

  • 条件变量的作用: 可以让线程阻塞在某一个条件的位置
  • 和锁这样的并发原语一样,条件变量其实也是一个结构,它其实是一个显示队列
  • 相关的操作:
pthread_cond_t cond;  // 声明条件变量
int pthread_cond_init(pthread_cond_t *restrict cond,
           const pthread_condattr_t *restrict attr);  // 初始化条件变量
int pthread_cond_destroy(pthread_cond_t *cond);  // 销毁条件变量
int pthread_cond_wait(pthread_cond_t *restrict cond,
           pthread_mutex_t *restrict mutex); // 根据条件阻塞线程
int pthread_cond_signal(pthread_cond_t *cond); // 随机唤醒一个阻塞在条件变量上的一个线程
int pthread_cond_broadcast(pthread_cond_t *cond); // 唤醒阻塞在条件变量上的所有线程
  • 特别注意,pthread_cond_signal的作用如下:
    • 首先会释放互斥锁
    • 阻塞等待条件满足(也就是pthread_cond_signal唤醒)
    • 重新获取锁
  • 本节中的引入方式就是通过不断完善生产者消费者模型从而引出条件变量的各种特性的,所以这里直接阐述利用条件变量实现生产者消费者模型的注意事项 代码: pro_con_cond.c
  • 注意事项如下:
    • 为了保护共享变量(count)和队列,需要加上互斥锁
    • 这里需要使用while判断条件的原因在与,pthread_cond_wait中释放了锁,所以接下来的过程中,当一个线程被唤醒的时候,另外的一个线程可能已经越过锁了(此时条件被满足了,判断结束),所以一旦这一个线程此时获取变量就会发生线程安全问题
    • 注意互斥锁的位置,如果互斥锁出现在条件变量的前面就会导致生产者和消费者同时获取锁时候的线程安全问题
    • 另外一个小的注意事项就是就算子线程中利用pthread_detach一旦主线程结束,所有子线程都会跟着结束,所以最好还是使用phtread_join回收子线程

信号量

  • 信号量也可以叫做PV信号量,可以参考csapp ,信号量是一个整数值的对象,通常信号量的操作方式如下:
#include <semaphore.h>  // 头文件
int sem_init(sem_t *sem, int pshared, unsigned int value);  // 初始化信号量
int sem_wait(sem_t *sem);  // P 操作,使得sem_t - 1 
int sem_post(sem_t *sem);  // V 操作,使得sem_t + 1
  • 利用信号量可以构建互斥锁: 互斥锁就是一个二值的信号量
  • 利用信号量可以构建条件变量: 但是比较复杂(需要很多锁来支持ptread_cond_wait中的几个步骤)
  • 利用信号量可以构建消费者生产者模型,此时可以利用空格数量锁住生产者,利用物品的数量锁住消费者 代码实现: pro_con_sem.c
  • 另外可以利用信号量实现读者-写者模型 但是树上的代码没有保证在写者和读者都被阻塞的时候写者的优先级别,它的思路就是让第一个读者获取到互斥锁,之后的读者都可以读取数据,但是写者必须在读者读完之后才可以写入数据
  • 可以解决各种有趣的并发问题,比如哲学家进餐问题
  • 注意可以利用条件变量和互斥锁来实现信号量,信号量也就是一个整数和互斥锁的集合(但是实际的信号量的实现比较复杂) 实现方式: sem.c (注意这里sem_wait要做的事情就是把value--并且阻塞,sem_post要做的事情就是把value++然后唤醒即可)

并发问题

  • 一般来说并发问题分为死锁问题和非死锁问题
  • 非死锁问题的种类和解决方式:
    • 违反原子性,也就是在操作共享数据的时候没有加上锁,导致多个线程操作同一个共享数据时产生的线程安全问题,解决方式就是加上锁即可
    • 违反顺序缺陷,类似于循环应用问题,这里的一种解决方案就是利用条件变量,只有条件满足的时候才会执行相应的操作
  • 死锁问题的预防策略:
    • 死锁问题的出现条件: 互斥
    • 持有并且等待
    • 非抢占
    • 循环等待
  • 预防方式:
    • 循环等待: 也就是两个线程使用反序或者不适当的方式获取到锁,解决方式就是偏序,也就是规定不同锁之间上锁的顺序,比如Linux内核中一组代码规定了十中不同的加锁方式
    • 持有并且等待: 把抢锁的代码在使用一层锁来保卫,保证原子性
    • 非抢占: 利用trylock,一次尝试之后就不可以在尝试了,这里可以规定重试的时间,但是可能出现活锁问题
    • 互斥: 不要使用锁,而是通过各种策略构建无锁的数据结构
  • 最后比如可以通过调度避免死锁定,银行家算法就是一种可能的策略,可以参考银行家算法 算法的实现逻辑还是比较简单的,注意搞清楚每一个矩阵的用法即可(特别是使用work矩阵模拟剩余容量的过程), 这里我就不想写了

基于事件的并发

  • 并发程序的三种实现方式: 进程,线程,IO多路复用
  • 核心思想就是事件循环,也就是同时监听不同的事件,当监听到某一个事件发生的时候就会采取相应的操作来处理对应的事件,相关的实现函数比如select,poll,epoll等
  • 基于事件的并发实际上是单线程的,但是如果在基于事件的并发中使用阻塞的系统调用(比如read和write等IO操作),可能会导致程序阻塞导致资源被大量占用,一种可能的解决方案就是异步的IO,许多系统中提供了一种异步的IO,允许在后台进行IO操作并且在IO操作完成的时候通知进程(信号或者相应的函数返回值)
  • 但是编写基于事件的并发程序比较困难,需要处理事件集合之间的关系