你想要了解的线程知识都在这里(一)

900 阅读13分钟

写在前面

由于本篇文章是线程开篇的第一篇文章,因此会着重介绍一些线程的基础,与一些概念性的内容。部分内容引用参考资料,可能存在过于官方的情况。不过系统性的学习也应当如此,希望大家可以耐着性子看完。

在阅读本文章时,希望大家暂且抛弃掉语言的固有认知,不同语言对于某些问题的处理可能会产生较大的不同,因此本篇文章的代码也是基于伪代码,意在抛弃语言的干扰后,为大家讲解各知识点。

你会发现有些情况在你的语言中并不会出现,这也许是因为你的编译器优化策略有所改进等原因。尽信书不如无书,希望大家多多实践,实践是检验真理的唯一标准

什么是线程

线程与进程

线程(Thread) 也被称作 轻量级进程(Lightweight Process, LWP),是程序执行流的最小单元。标准线程由 线程ID、当前指令指针(PC)、寄存器集合、堆栈组成。一个经典的线程与进程的关系图如下所示:


图片来自《程序员的自我修养——链接、装载与库》

发展史

多道程序

在计算机发展早期,CPU 资源十分昂贵,如果一个 CPU 只运行一个程序,那么碰到例如程序读写磁盘(可能是磁带)时,CPU就空闲下来了,这简直是暴殄天物。

于是人们很快编写了一个监控程序,当 程序A 暂时无需使用 CPU 时,监控程序就将正在等待 CPU 资源的程序启动。使 CPU 充分被利用。

这种方法被称作 多道程序(Multiprogramming),虽然原始,但大大提高了 CPU 利用率。

当然这种方法存在很大的弊端,即调度策略太粗糙,也许有些程序急需 cpu 来完成一些任务(例如用户交互),有可能很长时间后才被分配到 cpu。

分时系统

稍加改进后,程序运行模式变为了协作模式,即每个程序运行一段时间后,主动让出 cpu 给其他程序,这种程序协作模式叫做 分时系统(Time-Sharing System) 尤其是对于交互式的任务,这一点非常重要。

Windosw 早期版本(Windows 95 和 Windows NT之前),Mac OS X 之前的版本都是采用这种分时系统来调度程序。

当然,这里面也存在很大的问题,例如一个郑旭正在进行一个非常耗时的计算,一直霸占着 cpu 不放,那么操作系统也没办法,其他程序只能等待,就好像系统死机了一样。比如一个 while(1) 死循环会导致整个系统停止。在今天看来其实这是非常荒唐的。

多任务系统

多任务系统我们几天已经非常熟悉了。操作系统接管了所有硬件资源,并且本身运行在一个受硬件保护的级别。

所有的应用程序以 进程(Process) 的方式运行在比操作系统权限低的级别,有自己的独立地址空间。cpu 由操作系统统一进行分配,根据进程优先级,都会有机会得到 cpu,如果运行时间超过了一定的时间,操作系统会暂停该进程,将 cpu 分配给其他等待运行的进程。

这种 cpu 分配方式,我们称为 抢占式(Preemptive),操作系统可以强制剥夺 cpu 资源并且分配给他认为目前最需要的进程。

一些基本概念

并发

我们所说的并发,往往指的就是多线程或多进程之间的协作调度,这种方式可以很好的解决耗时操作将操作系统卡住的问题。

事实上,cpu 的核心数量代表着真正的并发线程的数量,而单核 cpu 仅仅是在多线程间快速切换,使得看起来像是同时进行一样。

线程的 3 种状态

线程通常至少拥有三种状态,分别是:

  • 运行(Running):线程正在执行
  • 就绪(Ready):线程可以执行,但 cpu 被占用
  • 等待(Waiting):线程等待某一事件(通常是 I/O 或 同步)

线程在 3 种状态间来回切换,如下图所示:


图片来自《程序员的自我修养——链接、装载与库》

轮转法 和 优先级调度

线程调度从多任务操作系统开始就不断被提出不同的方案和算法。主流方式尽管各不相同,但都有两种经典算法的痕迹,一种是论转法,另一种是优先级调度。

轮转法顾名思义,各个线程轮流执行一小段时间。特点是线程之间交错执行。
优先级调度法则是按照线程优先级来进行调度,线程拥有各自的 线程优先级(Thread Priority),高优先级线程更早执行。

在优先级调度下,有一种 饿死(Starvation) 的现象,即 cpu 总被高优先级线程抢占,导致某个低优先级线程永远无法执行。这里有个很好的例子就是 OSSpinLock(自旋锁)

当然,为了避免饿死现象的存在,一个线程若是等待了足够长的时间,那么它的优先级也会被提升上来。

I/O 密集型 与 cpu 密集型

我们一般把线程频繁等待的线程称之为IO 密集型线程(IO Bound Thread),而把很少等待的线程称之为 CPU 密集型线程IO 密集型线程 总是比 CPU 密集型 线程容易得到优先级的提升。

走进多线程

前面介绍了一些线程的概念与发展史,尽管只是冰山一角,但笔者已经感觉到乏味了,因此直接带来一个有趣的案例,以此案例引出后续。

见如下伪代码段

int x = 0;
thread1: {
	lock();
    x++;
    unlock();
};

thread2: {
	lock();
    x++;
    unlock();
};

after thread1 & thread 2: {
	print(x);
}

我们分析代码,认为对了 x 进行了加锁操作后,再进行自增操作,保证了自增操作的完整性。 但是在老的编译器中,或者老的系统版本中,这种操作经常会输出 x = 1。

这是为什么呢? 接下来我们就来谈谈线程安全。

线程安全

竞争与原子操作

我们先来看一个著名例子,两个线程分别执行表中代码

线程1线程2
i = 1;
++i;
--i;

在很多体系结构中,++i 的实现方法分为如下三步:

  1. 读取 i 到某寄存器 X
  2. X++
  3. 将 X 的内容存储回 i

由于 线程1 和 线程2 并发执行,因此他们的执行序列可能如下表所示

序号指令执行后的变量值线程
1i=1i=1, X[1]=未知线程1
2X[1]=ii=1, X[1]=1线程1
3X[2]=Ii=1, X[2]=1线程2
4X[1]++i=1, X[1]=2线程1
5X[2]--i=1, X[2]=0线程2
6X[2]--i=2, X[1]=2线程1
7X[2]--i=0, X[2]=0线程2

可以看出来,这里错的非常离谱,i 的结果可能是 0、1、2,原因就是自增操作被编译为汇编代码后不止一条,很有可能执行到一半被调度系统打断,去执行了其他代码。

我们把单指令的操作称为原子操作(Atomic),无论如何,单指令操作都不会被打断。 事实上,如果你去看 libdispatch 源码,会发现它定义了大量的原子性操作,例如:

  • __sync_add_and_fetch((p), 1) 先自加1,再返回
  • __sync_sub_and_fetch((p), 1) 先自减1,再返回
  • __sync_add_and_fetch((p), (v)) 先自加v,再返回
  • __sync_sub_and_fetch((p), (v)) 先自减v,再返回
  • __sync_fetch_and_or((p), (v)) 先返回,再进行或运算
  • __sync_fetch_and_and((p), (v))先返回,再进行与运算

同步与锁

但随着逻辑越来越复杂,原子性操作显然不能满足我们的需求,这个时候我们就要引入一个新的概念,

锁是一种很常见的同步方式,每一个线程在访问某个资源时先试图 获取(Aquire) 锁,并在结束后释放(Release) 该锁。在锁被占用时试图获取锁时,线程会等待,直到锁重新可用。

锁的种类有很多,这里列举一些,不作过多说明:

  • 二元信号量(Binary Semaphore)
  • 信号量(Semaphore)
  • 互斥量(Mutex)
  • 临界区(Critical Section)
  • 读写锁(Read-Write Lock)(Shared / Exclusive)
  • 条件变量(Condition Variable)

是不是觉得很多都非常眼熟?我们平时用到的 pthread_mutex、NSLock、NSCondition、dispatch_semaphore、@synchronized 等都在上面。

这里还要提及一个概念即可重入(Reentrant),一个函数可以被重入,表示这个函数没有执行完成,由于外部因素或内部调用,又一次进入该函数执行。一个函数被称为可重入的,表示该函数被重入后没有任何不良后果,是并发安全的强力保证。一个可重入的函数可以在多线程环境下放心使用。

过度优化

我们重新看到上面的代码段,按照前文的说明,我们对于 x++ 这样的非原子操作进行了加锁处理,并且也保证了输出 x 在两次自增之后,为什么说 x 的值有可能为 1 呢?

这里就要提到一个编译器优化,为了提高 x 的访问速度,会把 x 放入某个寄存器中,而我们知道不同线程的寄存器是独立的,因此产生了问题,程序顺序如下所示:

  1. [threa1] 读取寄存器到 R[1]=0
  2. [thread1] R[1]++(暂时不将 R[1]写回)
  3. [thread2] 读取 x 的值到某个寄存器 R[2]=0
  4. [thread2] R[2]++ 5.[thread2] 将 R[2]写回 6.[thread1] (很久以后) 将R[1] 写回 x

由此,我们引出引出一个关键字:volatile

volatile 在各个语言环境中的意思并不相同,在 c 和 c++ 中,volatile 确保本条指令不会因编译器的优化而省略,且要求每次直接读值。

volatile 修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这样在任何时刻,两个不同的线程总是看到某个成员变量的同一个值。

volatile 关键字可以用来阻止过度优化,基本上可以做到两件事情:

  • 阻止编译器为了提高速度将一个变量缓存到寄存器内而不写回
  • 阻止编译器调整操作 volatile 变量的指令顺序

显然,在上面一个问题中,第一点是可以被优化的,但是第二点是无法满足的,因为我们即使可以阻止编译器的过度优化,也无法阻止 cpu 动态调换执行顺序。

我们来看一段貌似没有问题的代码,下面这段代码是一段看似没问题的单例代码,注意这里的 double-checked lock,旨在降低锁粒度,具体妙用请读者自己体会。

volatile T *pInstance = 0;
T * GetInstance() {
	if (pInstance == NULL) {
    	lock();
        if (pInstance == NULL) {
        	pInstance = new T;
        }
        unlock();
    }
    return pInstance;
}

乍看之下,这样的代码是没问题的,lock() 和 unlock() 防止了多线程竞争导致的错误。但实际上会出现另一个问题,问题的来源仍是 cpu 的乱序执行。

C++中的new实际上包含了两个步骤:

  1. 分配内存
  2. 调用构造函数

所以 pInstance = new T; 实际上包含了三个步骤:

  1. 分配内存
  2. 在内存的位置上调用构造函数
  3. 将内存地址赋值给 pInstance

在这三个步骤中,2 和 3 的位置实际上是可以任意调换的。也就是说可能会发生一种情况:pInstance已经不为空了,但构造函数还没有调用完成。因此当其他线程访问时,拿到了一个还没有被初始化的 pInstance,此时程序会如何表现就取决于这个类如何设计了。

由此我们引出一个新的概念:内存屏障
内存屏障 也叫做 内存栅障,增加 barrier 指令会阻止cpu将该指令之前的指令交换到 barrier 之后,反之亦然。大家可以思考以下,我们的 barrier 指令应该加到哪一行?

我们以 Objective-C 中最常用的构建单例的代码来看:

static T *_tInstance_ = nil;
+ (instancetype) shareInstance
{
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        _tInstance_ = [[T alloc] init];
    });
    return _tInstance_;
}

如果你熟悉 gcd 源码的话,就会知道,在 dispatch_once 的实现中,增加了内存屏障,节选代码如下:

dispatch_once_f(dispatch_once_t *val, void *ctxt, void (*func)(void *))
{
	volatile long *vval = val;
    
    if (dispatch_atomic_cmpxchg)(val, 0L, 1L) {
    	// 执行方法
    	func(ctxt);
        // 增加内存屏障
        dispatch_atomic_barrier();
        *val = ~0L;
    } else {
    	// 等待锁
    	do {
        	_dispatch_hardware_pause();
        } while (*vval != ~0L);
        dispatch_atomic_barrier();
    }
}

在这段代码中,我们可以保证对象的构造与赋值过程一定在 dispatch_atomic_barrier() 前完成。当然,这里不会出上述情况的原因是 ,这一点读者可以自行体会。
高级语言提供的一些 api 中经常会帮我们处理这些事情,导致我们忽视其中的细节,而这些细节往往需要我们格外关心。

写在后面

本篇文章大部分表现已经过时,但知识永远不会过时,我们学习到的底层知识、原理,都是帮我们更好的认识计算机的世界,让我们可以解决奇形怪状的各种问题。

在学习知识时应该抱着严谨的态度,将理论与应用相结合。上文中提到的非常多的优化在实际开发中都已经没有了。例如我们上文中提到的 多线程中 x++ 的问题,实际上经过测试,即使不增加 volatile关键字 也不会出问题。(Objective-C & Apple clang version 11.0.3 (clang-1103.0.32.59))

我们可以写个小 demo 来测试一下,环境同上:

{
	int i = 1;
    i++;
    
    int j = i;
    j++;
    
    int k = j;
    i++;
    k = i;
}

我们将编译出来的 .app 文件丢到 hopper 中,查看对应的汇编代码,如下图所示:


Objective-C & Apple clang version 11.0.3 (clang-1103.0.32.59)

我们可以看到,每次需要使用到之前的变量时,都会从内存重新读取入寄存器,而每次操作完寄存器,都会重新写入内存,并没有将变量的值存放在寄存器不回写的情况。(若将编译器优化开至 Fast / Fastest, Smallest 等,会发现更有意思的事情,请大家自己尝试)
所以我们不管是看书还是看文章,对于看到的知识都应该抱有一个怀疑态度,多去尝试,多去探究才能真正的进步。

文章中如有错误,欢迎指出。