28[VB]同步
28[VB]同步

视频地址:
课件地址:
本章对应于书中的12.4, 12.5和12.7。

  • 只有资源共享才会产生同步问题,如果线程没有共享任何资源,就没有同步问题。判断一个变量是否是共享的,首先判断该变量在内存的实例个数,然后看该变量的一个实例是否被多个线程引用。对共享变量进行操作时要进行同步。
  • 多线程程序要画出进度图来分析
  • 互斥锁主要是用来保护共享变量的,只要有多个线程访问共享变量,就加上互斥锁。如果要对资源进行调度,就使用计数信息量。
  • 多线程代码:首先判断哪些变量是共享变量,加上互斥锁。如果有多个互斥锁,画出进度图,避免出现死锁。
  • 由于同步的开销很大,所以尽量写成可重入的形式。
  • 多进程程序中,需要注意对信号进行阻塞;多线程程序中,需要注意对共享变量进行同步。
  • 多线程程序要注意:共享变量,竞争,死锁,线程安全。

1 多线程程序的共享变量

我们以下面的程序为例来说明多线程共享变量的问题
notion image
一组并发的线程运行在一个进程上下文中,每个线程具有自己的线程上下文,包括TID、栈、栈指针、程序计数器、条件码和通用目的寄存器值,这就说明每个进程可以通过自己的程序计数器运行自己的代码,而通过栈可以保存自己的局部变量,这些栈是保存在虚拟地址空间中的栈区域。而进程的其余部分在所有线程中是共享的,包括整个用户虚拟地址空间,其中有代码、读写数据、堆、共享代码库代码数据区域、打开的文件描述符和信号处理程序等等
但是并不会完全遵守以上的线程内存模型,比如我们这里要求每个线程有自己独立的栈,但是这里并不会对其他线程的访问进行限制,比如上面代码在线程例程中通过全局变量ptr来访问主线程中栈的局部变量msgs,所以要十分小心这个线程内存模型。
根据链接这一章可知,未初始化静态变量、以及初始化为0的全局变量或静态变量的符号.bss节中,初始化过的全局变量或静态变量的符号在.data节中,这两个数据节在生成可执行目标文件时,都被分配到了数据段中,所以全局变量和静态变量的实例是保存在进程的虚拟地址空间中的数据段中的,所有线程都能访问到,且虚拟内存空间值包含一个实例。而局部非静态变量是保存在栈或寄存器中的,每个线程都有自己的栈和寄存器值,所以局部非静态变量的实例是保存在线程的栈或寄存器中的,通常只有自己能访问到
而判断一个变量是否是共享的,就看该变量的一个实例是否被多个线程引用
  • ptr:它是未初始化全局变量,实例保存在.bss节中,所有线程都可以访问。在主线程和两个对等线程中都有引用过,所以是共享的。
  • cnt:它是初始化了的静态变量,实例保存在.data节中,所有线程都可以访问。在两个对等线程中都有引用过,所以是共享的。
  • i.m:主线程中的变量i是局部变量,保存在主线程中的栈,没有被其他线程引用过,所以是不共享的。
  • msgs.m:主线程中的变量msgs是局部变量,保存在主线程中的栈。由于全局变量ptr指向了msgs,而两个对等线程通过ptr间接地引用了msgs的数据,所以是共享的。
  • myid.0myid.1:在两个对等线程中的局部变量myid,它们各自保存在对等线程自己的栈中,也不存在间接引用,所以它们是不共享的。
notion image

2 用信号量同步线程

由于共享变量的存在,可能会引入同步错误(Synchronization Error)
notion image
注意:由于我们这里在线程例程中不会对niters进行修改,所以可以直接将niters的地址传入pthread_create函数而不用担心竞争。
我们运行该程序时,希望cnt的值为2*niters,但是运行出来的结果却是
notion image
我们观察在线程例程中的汇编
notion image
其中,%rcx保存niters的值,%rax保存i的值,%rdx保存cnt的值。我们知道,在单核线程并发时,是由内核调度这两个线程的逻辑流进行交替运行的,而上图的中间部分是两个逻辑流对共享变量cnt的操作,所以当其中一个线程运行到中间部分又被内核调度到另一个线程时,就可能会出错。这两个线程的逻辑流具有一些能得到正确结果的执行顺序,也有一些会得到错误结果的执行顺序,比如
notion image
我们可以通过进度图(Process Graph)来探讨指令执行的顺序。首先有n个并发线程就创建n维笛卡尔积空间,每个维度对应一个线程的进度,根据线程的指令顺序对每一维进行划分,则在该笛卡尔积空间中的某一条轨迹就是并发线程的指令执行顺序。注意:
  • 图的原点是所有并发线程还未开始执行的初始状态
  • 两条指令不能同时执行,所以不存在斜线
  • 程序不允许反向运行,所以轨迹总是向右上方增长的
notion image
如上图所示就是根据汇编指令得到的一条指令执行顺序的轨迹。其中我们将操作共享变量cnt的指令 当做临界区(Critical Section),我们希望临界区不和其他线程的临界区交替执行,来使得线程拥有对共享变量的互斥访问(Mutually Exclusive Access)。我们可以将两个线程的临界区围起来构成一个不安全区(Unsafe Region),只要有一条轨迹穿过不安全区,说明两个线程对共享变量cnt的操作是交替执行的,可能就会出现错误。我们将穿过不安全区的轨迹称为不安全轨迹(Unsafe Trajectory),而其他的轨迹就是安全轨迹(Safe Trajectory)
notion image
为了保证可以获得安全轨迹,可以通过信号量的方法同步线程来获得安全轨迹。

2.1 信号量

为了同步线程,提出了一种特殊类型变量信号量(Semaphore)s,它是具有非负整数的全局变量,只能通过两个系统调用函数进行操作:
  • P(s)
    • 如果s是非零的,就对其减1并立即返回(原子操作)
    • 如果s是0,则将当前线程挂起,直到被V(s)函数加1且重启线程,P(s)才会再对s减1并返回。
  • V(s)s加1(原子操作),如果有任何线程被P挂起,该函数会重启其中任意一个线程,此时控制权又回到了那个线程的P中
P和V这样的定义是为了保证了信号量s不会变成负值,才能够对线程进行同步,这种属性称为信号量不变性(Semaphore Invariant)。这里有一些信号量的函数
#include <semaphore.h>

int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s);  //P
int sem_post(sem_t *s);  //V
其中,每个信号量都要通过sem_init函数进行初始化,且初始化值为value,然后通过sem_waitsem_post函数来调用P和V。我们这里提供这两个的封装
#include "csapp.h"
int P(sem_t *s);
int V(sem_t *s);
使用信号量来确保对共享变量的互斥访问,基本思想将共享变量和一个信号量联系起来,然后使用P和V将对应的临界区包围起来。比如我们将原来的代码改为
sem_t mutex;  //信号量
//主线程中初始化信号量
sem_init(&mutex, 0, 1);
//对等线程例程中
for(i=0; i<niters; i++){
  P(&mutex);
  cnt++;
  V(&mutex);
}
这里我们声明了一个信号量mutex,然后在线程例程中用P和V将cnt++围住了。首先,当还没有线程执行线程例程时,mutex被初始化为1,当有一个线程A在执行线程例程时,会首先执行P(&mutex),此时由于mutex不是0,所以会将其减1,然后执行cnt++,此时mutex就为0,如果在执行cnt++指令的中间有另一个线程B也要执行线程例程时,在P(&mutex)中由于当前mutex为0,则P会将线程B挂起,直到线程A执行到V(&mutex)时,会将mutex加1,然后重启线程B,此时线程B又会执行P(&mutex),此时由于mutex为1,所以也会顺利执行。
更形式化来说,我们将这种用来保护共享变量的信号称为二元信号量(Binary Semaphore),因为它的值总是0或1。以提供互斥为目的的二元信号量也称为互斥锁(Mutex),则执行P操作就称为上锁,执行V操作就称为解锁,一个线程对互斥锁上锁了还未解锁,就称该线程占用这个互斥锁。我们通过互斥锁将线程的临界区包围起来,则会构成一个禁止区(Forbidden Region),在禁止区内由于信号量都为-1,想要操作共享变量就要通过P对信号量减1,此时就会将当前线程挂起,直到占用的线程解锁
notion image
图中每个点的值为信号量的值

2.2 利用信息量来调度共享资源

除了用二元信息量来提供互斥锁以外,还能用来作为一组可用资源的计数器,称为计数信号量,用来调度对共享资源的访问,经典的模型有生产者-消费者问题(Producer-Consumer Problem)读者-写者问题(Reader-Writer Problem)

2.2.1 生产者-消费者问题

我们考虑这样一类问题,假设目前我们去一个商场购买口罩,我们作为消费者可以自己去购买,如果口罩不够了,则消费者就等待生产者生产出更多的口罩放在商场供我们购买,如果生产者一不小心生产了太多口罩,则商场放不下了,就要等商场有空的区域时再生产。这就是一个生产者-消费者问题。
在这里,我们将生产者和消费者看成是生产者线程和消费者线程,而商场看成是一个具有有限空间的缓冲区,生产者线程会不断生成新的项目(Item),然后将其插入缓冲区中,而消费者线程会不断从缓冲区中取出这些项目去消费。
notion image
由于缓冲区在这两个线程中是共享变量,从中取出项目和插入项目都要更新共享变量,所以要对缓冲区设置一个互斥锁,保证只有一个线程能访问缓冲区。其次,我们还需要通过计数信号量对缓冲区的访问进行调度,当缓冲区有空间来插入项目时,生产者线程才尝试插入项目,当缓冲区中有项目时,消费者线程才尝试从中取出项目。我们可以首先定义缓冲区的数据结构
notion image
其中,buf是一个动态分配的缓冲区,n是缓冲区的大小,frontrear是第一个项目和最后一个项目的索引,这里将buf实现为循环的数组。mutex是访问缓冲区的互斥锁,slots是用来调度生产者线程的计数信息量,items是用来调度消费者线程的计数信息量。
注意:计数信息量slotitems是用来判断能否执行生产者线程或消费者线程,如果可以,则会对buf进行访问,由于buf是共享变量,所以它的访问需要mutex互斥锁,所以这里会有三个信息量。
notion image
首先,我们需要初始化该缓冲区,其中sp->mutex要初始化为二院信息量,sp->slots要初始化为n,表示有n个空间供生产者线程使用,sp->items要初始化为0,表示现在还没有项目供消费者线程消费。
notion image
生产者线程可以调用sbuf_insert函数来将将项目插入到缓冲区中。首先需要通过sp->slots查看是否有空闲的区域,如果sp->slots为0,说明没有空闲的区域,则P会将生产者线程挂起,直到sp->slots大于0且该线程被V重启。然后需要通过sp->mutex来获得缓冲区的互斥锁,然后才能将item插入缓冲区中。随后通过Vsp->mutex解锁,然后用Vsp->items加1,如果刚好有消费者由于sp->items为0而挂起,则该V会随机重启一个消费者线程。
notion image
消费者线程可以调用sbuf_remove函数来从缓冲区中获得项目。首先通过sp->items查看缓冲区中是否存在项目,如果sp->items为0表示没有项目供消费者线程消费,此时消费者线程会挂起,直到被生产者线程的P(&sp->items)重启。然后通过sp->mutex来获得缓冲区的互斥锁,然后才能从缓冲区中获得项目item。随后通过Vsp->mutex解锁,然后用Vsp->slots加1,如果刚好有生产者线程由于sp->slots为0而挂起,则该V会随机重启一个生产者线程。
最终我们可以通过以下函数来释放缓冲区
notion image

2.2.2 读者-写者问题

当一组并发的线程要访问一个共享对象时,有些线程只读对象称为读者线程,而其他对象只写对象称为写者线程,写者线程必须有对对象的独占访问,而读者线程可以和其他读者线程共享对象。根据读者和写者的优先级,可以分成两类问题:
  • 第一类:读者优先级高于写者,除非写者已占用互斥锁,否则读者都不会一直等待,在等待的写者之后到达的读者具有更高的优先级。
  • 第二类:写者优先级高于读者,一旦写者准备好写时,它会尽快执行写操作,在写者之后到达的读者必须等待。
这两种情况都会出现饥饿问题。这里提供一个第一类读者-写者问题的代码
notion image
这里定义了一个全局共享变量readcnt来统计读者线程的数目,由于不同读线程要对其进行访问,所以需要一个互斥锁mutex来控制对readcnt的访问,然后还有一个w互斥锁来控制对对象的访问。
notion image
在写者线程中,会通过用P(&w)V(&w)将临界区包围住,从而根据互斥锁w的状态来访问对象,此时保证了一次只能有一个写者线程能访问对象。
notion image
在读者线程中,首先要通过readcnt来统计其中有多少个读者线程,因为是读者优先的,所以只有进入的读者数目readcnt为0时,才能让写者线程去访问对象,所以这里每个读者线程进来和出去时都要修改readcnt,而readcnt是共享变量,所以需要通过mutex来对其上锁。其次,我们只有当readcnt为1时才执行P(&w)w进行上锁,当有写者线程尝试访问对象时,会被挂起,而当有其他读者线程进入时,由于readcnt被修改了,所以不会访问到P(&w),也就不会被挂起,此时后续的读者线程就能不断进入临界区访问对象。而只有当readcnt为0时才执行V(&w)w解锁,此时挂起的写者线程就能被重启。

2.3 基于预线程化的并发服务器

我们之前实现的基于线程的并发服务器,为每个客户端都生成一个线程进行处理,其实十分耗费资源。我们可以基于生产者-消费者问题来构建一个预线程化(Prethreading)的并发服务器,它将主线程看成是生产者,不断接收客户端发送的连接请求,并将已连接描述符放在缓冲区中,而提前创建的一系列线程就是消费者,不断从缓冲区中取出已连接描述符与客户端通信
notion image
notion image
第24行首先对缓冲区进行初始化,然后生成了NTHREADS个消费者线程,在线程例程中,会通过pthread_detach函数来分离消费者线程,然后死循环通过sbuf_remove函数来从缓冲区中获得已连接描述符connfd,当pthread_create函数返回时,这些消费者线程就开始运行了,此时由于sbuf->items为0,所以这些消费者线程会被P(&sbuf->items)挂起。然后在生产者线程中通过accept函数来获得已连接描述符connfd,并通过sbuf_insert函数将其插入到缓冲区中,此时sbuf->items就不为0了,那些被挂起的消费者线程就会一个个被V(&sbuf->items)重启,然后将获得的connfd传入echo_cnt函数来与客户端通信。这里的对等线程的数目是我们一开始创建的那些线程,而不是等到获得connfd时才创建,所以称为预线程化,可以自己控制对等线程的数目。
notion image
这个echo_cnt函数会通过全局变量byte_cnt来统计服务器总共从客户端获得的字节数,由于不同的消费者线程都会调用echo_cnt函数,所以会有多个线程来访问byte_cnt共享变量,所以我们对byte_cnt的访问需要使用互斥锁。而我们这里将互斥锁和byte_cnt的初始化过程放在了子线程中,通过pthread_once函数来保证该初始化函数init_echo_cnt函数只被执行一次。

3 其他并发问题

可以发现,线程由于会对共享变量进行操作,所以我们尝试使用同步技术来解决操作共享资源时出现的问题,接下来会介绍几个典型问题。

3.1 线程安全

当且仅当一个函数被多个并发线程反复调用还会一直产生正确结果时,才称为线程安全的(Thread-Safe),我们可以根据线程不安全的原因分成以下几个类:
  • 第一类:不保护共享变量的函数:当我们没有对共享变量进行保护,而它的操作也是非原子的时,就可能会造成错误。
    • 💡
      解决方法:引入互斥锁,使用PV将对共享变量访问的部分围起来,但程序速度会变慢。
  • 第二类:跨多个函数调用依赖于持久状态:比如以下伪随机数生成器,在单个线程程序中,我们可以通过srand函数定义相同的随机种子来得到可重复的随机数序列,但是在多个线程中调用rand函数时,由于rand函数中依赖于共享的前一个状态next_seed,此时next_seed可能会被其他线程修改而无法获得相同的随机数序列。
    • 💡
      解决方法:重写函数,将状态作为参数的一部分传递,避免被其他线程修改。
      notion image
  • 第三类:返回指向静态变量的指针的函数:静态变量保存在数据区,在进程中只有一个实例,是所有线程共享的,当你返回一个静态变量的指针时,是指向一个内存地址,而在别的线程中可能也会通过该静态变量对该内存地址的内容进行修改。
    • 💡
      解决方法:
    • 重写函数,让调用者传递保存结果的地址
    • 使用加锁-复制(Lock-and-Copy)技术,将线程不安全函数与一个互斥锁联系起来,用PV函数将该不安全函数的调用部分包围起来,并将其结果保存在一个局部变量中。问题:需要引入额外的同步操作,会降低程序的速度,其次是有一些函数会返回十分复杂的数据结构,比如getaddrinfo,此时就需要深拷贝才能复制整个结构数据。
    • notion image
  • 第四类:调用线程不安全函数的函数:如果该线程不安全函数属于第二类,就要修改函数的源码,如果是第一类或第三类,可以直接通过互斥锁的方式保证函数时线程安全的。
Linux系统提供的大多数线程不安全函数都有对应的线程安全版本,一般是以_r结尾的。
notion image
我们可以更进一步得到线程安全函数中的一类可重入函数(Reentrant Function),当他们被多个线程引用时,不会引用任何共享数据。可将其分成两类:
  • 显示可重入的(Explicitly Reentrant):函数参数全都是值传递,且函数内的数据应用都是局部变量,不含有全局变量或静态变量。
  • 隐式可重入的(Implicitly Reentrant):函数参数可以是引用传递的,如果调用线程传递一个非共享数据的指针,它就是可重入的。
可重入函数包括显示可重入和隐式可重入,说明可重入函数可能也依赖于调用线程的属性,比如传递一个非共享数据的指针到隐式可重入函数,保证其是可重入的,这类函数就不需要任何同步技术来保证多线程结果的正确。由于同步的开销很大,所以尽量写成可重入的形式。
上面第二类线程不安全函数,只能通过修改函数使其是线程安全的,并且由于无法使用互斥锁,所以只能将其改为可重入的
notion image
注意:可重入函数是线程安全函数的真子集,所以可重入函数一定是线程安全函数,而线程安全函数不一定是可重入函数,可能是用互斥锁来实现线程安全的。可重入函数由于不用同步操作,所以通常速度会更快。

3.2 竞争

多线程程序要求对进度图中任何可行的轨迹都正确工作,而程序员可能会下意识假设了某种特殊的轨迹,比如一个程序的正确性依赖于线程A要在线程B执行到y之前先执行到x,此时就会出现竞争(Race)
这个例子之前也说过
notion image
该程序中,第13行创建线程时传入的参数为&i,而在线程例程中通过*((int*)vargp)将其转化为int,此时就会出现竞争。因为主线程中的局部变量i保存在主线程的栈中,而传入的线程例程的参数是i的地址,在前一个线程在第22行读取该地址中的i之前,第12行修改了该地址内的数据,就会造成竞争。这里假设了第22行在第12行之前执行。
notion image
正确的方法是申请一个独立的空间
notion image

3.3 死锁

死锁(Deadlock)就是一组线程被阻塞,等待一个永远不会为真的条件。比如下图是一个使用了两个互斥锁的进度图
notion image
我们可以发现,当轨迹进入图中所示的死锁区(Deadlock)时,线程1占用互斥锁s,线程2占用互斥锁t,而轨迹要从死锁区出来,要么线程1占用互斥锁s,要么线程2占用互斥锁t,这两个都是不可能为真的条件,所以就陷入了死锁状态。所以轨迹可以进入死锁区,但是无法从死锁区出来。
可以发现是由于P和V的操作顺序不当,使得两个互斥锁的禁止区出现了重叠,导致死锁区的出现,这种原因导致的死锁常用的解决方法是定义一个互斥锁加锁顺序规则,给定所有互斥操作的一个全序,如果每个线程都是以一种顺序获得互斥锁并以相反的顺序释放锁,则该程序时无死锁的。也就是对于有多个互斥锁的情况,我们在所有线程中按照相同顺序来上锁,在解锁时用相反顺序。
notion image
注意:要注意互斥锁的初始状态。