privot函数（prev_permutation函数）

Book开源处,感觉翻译很烂

关于异常：

出现异常并不意味着程序本身出了问题，而是程序外部的输入无法让正常业务继续执行，这时应该执行的是异常业务，而异常就是这两种业务转接的桥梁——它提供一种机制，使得程序员在遵守一定规则之下，这个异常业务能够正确完成。

异常安全的三个级别：noexcept, basic, strong

ref

ref

spin：自旋转

unary predicate：一元谓词s

binary predicate：二元谓词

predicate：谓词

snapshot：快照

nice-to-have：可有可无

parallelism: 并行

serialization：串形

RAII: Resource Acqusition Is Initialization，资源获取即初始化

Abstraction penalty：抽象代价

daemon thread: 守护线程

invariants:不变量

race condition：条件竞争

grammar：语法

semantics：语义

malicious_function：恶意函数

hierarchical: 分层的

granularity: 粒度

idiom：惯用法

nest: 嵌套

recursive：互斥

synchronization：同步

condition variable：条件变量

future：期望

spurious wakeup：伪唤醒

asynchronization：异步

pivot：枢纽

chrono：时间

contest switch

save cpu state and instruction pointer, calculate which task should we switched, and load new cpu state. then, cpu will load the instruction and data in cache

hardware concurrency

truly concurrency

the way of concurrency

Multiprocessing concurrency: need to IPC, so more complex and more slowly, but it has good isolation and more safety

Multithreading concurrency: need to solve concurrency problem carefully

Warning: this book base on multiply thread concurrency

why need to concurrency: only one for code ioslation and other for prefomance

test code:

2.1.1 generalize

create and run a new thread

join or detain thread

unique identify of thread

2.1.2 start thread

thread run when you create a object of

can create a object by , like this example:

But, if you want to pass a tempate object to , in this way:

You will found this run with error:

This is because C++’s most vexing parse, in that declaration, my_t will be parsed in a funtion but a object, you can solve this by following way:

use of an extra parenthesis:
use C++11 initialization:
use C++11 lambda:

If you doesn’t decide join or detain your thread, then it will call dtor().

2.1.2 join thread

If you detach a thread like this way:

In , we pass by value of and access local object in , if funtion exit before thread exit, then will access local value which is destoryed, and the behaviour when it happened is UB.

so it is important to choose a valid way to wait you thread.

and a programming habit is do not create a thread which can access local object

A easy and rude way to wait a thread until exit is

if you call , the resoures about thread will clean automatilly, and you cant call double times and more.

you can call to get if you can join, it return false if you haved joined

2.1.3 join in special condition

Look the next code:

In function , if throw exception, and not catched, then wiil exit and skiped

A solution is followings:

But, a better way is in RAII

In this way, although will throw exception and skip , the object will call to the thread he managed

2.1.4 detach thread

Whaterver the parameters type you set(reference or value), thread will copy always! Just copy all arguments in the memory space itself.

In the following code, function receive a int pass by value and a string pass by reference

And because we detach the thread , so we would can't receiver it’s output.

在下面的代码中，函数 f 打印的 s 可能会乱码，这是因为函数 buf 实际上是一个指针变量，它指向局部变量。

并且它的类型是，当我们把它传递给时，会执行一个隐式类型转换。

但是，我们无法确保隐式类型转换与 thread 传递参数时进行 copy 的执行顺序问题，也就是说，有可能传递给 string 的事转换前的变量（buf 只想的指针）

So, the solution is easy, explicit call type convention

But, sometimes, we actually want to pass by refernece, the solution is use

Also, you can pass class funtion and it’s this object

But, for some type, the operator assignment or operator copy is deleted, like , so should but copy.

It would CE If you not use .

Thread cant copt too.

2.3.1 preface

你不能通过赋新值操作来“丢弃”一个线程，即：你不能将一个线程 move 到一个已经分配了任务的线程。

你也不可以将一个线程 copy 到另一个线程，但是你可以将一个线程 move 到另一个空线程。

对于下面的形式（1）是合法的，因为是一个临时对象 – 移动操作会隐式的调用，如果是一个，就需要显示的调用，如 (2) 所示。

但是对于 (3) 所示就会 CE：

2.3.2 scoped_thread

疑问？

为啥不把 ctor 里的 t 设置为右值引用呢？

2.3.3 jpthread

疑问？

为啥不把 ctor 中的改为呢？

：返回并发线程的数量。

并行版的

因为数据范围并不大，因此得出的时间消耗意义不大！

：如果线程没有执行，会打印：

：返回当前线程的 id

线程标识符可以用来比较，排序，哈希等。

通过线程标识符可以实现不同的线程执行不同的任务。

的输出是依赖于实现的，但是C++ 标准规定相同 ID 的线程必须有相同的输出。

3.1.1 race condition

条件竞争分为恶性条件竞争和良性条件竞争，良性条件竞争不会对系统有什么影响。

避免恶性条件竞争的方法：

对数据结构采用某种保护机制，例如：mutex
无锁数据结构
事务

3.1.2 use mutex to avoid RC

C++ 为我们提供了互斥量用来避免恶性条件竞争，我们可以通过实例化创建互斥量，并通过和进行上锁和解锁，但并不推荐你这么做，认为人总会犯错 😭

所以，类似智能指针，C++ 标准库为互斥量提供了一个 RAII 语法的模板类，其会在构造的时候自动上锁，并在析构的时候自动解锁。

他们都在头文件当中。

示例程序：

但互斥量也不总是安全的，例如我们在一个类中返回了被保护数据的指针或引用时，会破坏对数据的保护，并且不会被互斥锁限制。

因此，对接口的设计需要相当谨慎，要确保互斥量能锁住任何对保护数据的访问，并且“不留后门”。

例如，在下面的程序当中，我们通过引用把被保护数据传递到互斥锁作用于之外，从而造成一个潜在的陷阱：

3.2.1 RC between interface

使用互斥量对数据进行保护并不能万事大吉。

例一：删除双链表中的一个节点

当我们要删除双链表中的节点时，仅仅对 P 添加互斥量是不行的，还需要对 , 同时添加互斥锁。

例二：堆栈

在上面的代码中，当堆栈非空时，我们希望从中取出栈顶素，再调用，但其实 (1) 和 (2) 之间是有竞争条件的，也就是说，可能存在一个线程在 (1) 与 (2) 之间也掉用了。

另一个潜在的竞争条件发正在 (2) 和 (3) 之间，可能有两个线程先后执行了，但没有执行，此时两个线程处理后的值可能是相同的，这种错误很难定位，因为程序没有出错，出错的是你的逻辑。

这就需要接口设计上有较大的改动，提议之一就是使用同一互斥量来保护 top()和 pop()。Tom Cargill[1]指出当一个对象的拷贝构造函数在栈中抛出一个异常，这样的处理方式就会有问题。在 Herb Sutter[2]看来，这个问题可以从“异常安全”的角度完美解决，不过潜在的条件竞争，可能会组成一些新的组合。

一个很有意思的事情是，我们可能不得不面临例二中的竞争条件。在堆栈的 pop 操作中（有返回值），如果我们直接把容器元素 ”移动“ 到目标位置，可能会因为异常，也就是内存不足而导致数据没有拷贝出去，并且栈中的数据也杯破坏了。

因此，设计人员通常把这个操作操作分为两部分：

top()
pop()

由此来确保数据不会在内存不足时出错，但我们之前讨论过了，在 1 和 2 之间，有竞争条件。

但幸好，我们还有其它选项，尽管他们也不是完美的。

solution1：将变量的引用作为参数，传入 pop() 函数中取得想要的”弹出值“

这种方法有明显的缺点：

需要构造出一个栈中类型的实例用于接受目标值，这会导致空间和空间的额外开销等

要求类型必须支持赋值操作，很多类型即使支持移动构造和拷贝构造，可能也不支持赋值

solution2：无异常抛出的拷贝构造函数或移动构造函数

solution3：返回指向弹出值的指针

solution4：“选项1 + 选项2”或 “选项1 + 选项3”

Example： thread safe stack

其实本质上就是将原本的两个函数（top 和 pop）实现的操作集成到一个函数（pop）当中，这样就可以通过互斥量完成数据的保护。

通过一个函数修改我们的参数，很自然的有两种方式，一是返回值，而是传引用。

在返回值这种方式中，return 一个引用是危险的，这我们前面提到过。直接 return 值的话开销可能很大，因此我们考虑传出一个动态对象，而手动 new/delete 不安全，因此使用智能指针。

3.2.2 deadlock

避免死锁的方法：

指定获得锁的顺序
一次性加全部锁
…

C++ 标准库的可以一次性锁住多个互斥量并且没有死锁风险。

虽然规定一个获得锁的顺序可以避免死锁，但他不是万能的，甚至说，会起到适得其反的效果，例如：

在上面的例子中，我们虽然在中规定了获得锁的顺序，但是如果我们交换了的参数顺序，那么结果就很可怕了！

std::defer_lock, std::try_to_lock, std::adopt_lock

不获得互斥的所有权 try_to_lock_t 尝试获得互斥的所有权而不阻塞 adopt_lock_t 假设调用方线程已拥有互斥的所有权

Advise to avoid deadlock：

避免嵌套锁，尽量只使用一个锁
避免在持有锁时调用用户提供的代码
使用固定顺序获取锁
使用层级锁

3.2.3 hierarchical_mutex

reference

层级锁的意义在于：在运行时约定是否进行检查，这个建议需要对应用层进行分层，并且识别在给定层上所有互斥量。

层级锁的核心就是：每个互斥量有一个层级值，线程只能以层级值递减的顺序获取锁，由此实现顺序性。

Sample complement:

初始化 static 成员时不能加 static，避免与 class 之外的 static 变量混淆

为什么将 this_thread_hierarchy_value 设置为 thread_local static ? 只有这样才能实现动态更新层级，当我们更新了 this_thread_hierarchy_value 的值之后，下一个创建的 hierarchical_mutex 对象使用的是更新之后的值。例如：

3.2.4 std::uniqie_lock

对 swap 函数的改写：

3.2.5 Passing of mutex ownership in different domains

实例没有与自身相关的互斥量，互斥量的所有权可以通过移动操作，在不同的实例间传递。

… 看不懂在干啥 😭

3.2.5 Lock Granularity

锁的粒度用来描述通过一个锁保护着的数据量大小。一个细粒度锁(a fine-grained lock) 能够保护较小的数据量，一个粗粒度锁(a coarse-grained lock)能保护较多的数据量。

3.3.1 protect initialization process of data

假设我们有一个共享源，构建代价很昂贵，他可能会打开一个数据库连接或分配出很多的资源。

Lazy Initialization 在单线程代码中很常见 —— 没一个操作都需要对源进行检查，了解数据是否被初始化，然后在其使用前决定，数据是否需要初始化：

在多线程中，一种大粒度锁方法：

声名狼藉的“双重检查锁模式”:

这个模式声名狼藉的原因在于，存在潜在的条件竞争。

具体的可以参考这里

论文太长，我粗略的看了一下，我们知道，new 是分为两步的：

operator new(size_of_object)
ctor
assign

文章给出代码如下所示：

文章的意思应该是，在 ctor 之前，对象还没被构建，此时指向它的指针为空，即使 ctor 完成了，我们还需要将其地址赋值给指向它的指针，而在ctor与assign之间，指针依然为空。

指针为空就意味着，第二次检查不一定是有效的，也即，仍然可能有多个线程进入 (1) 从而破坏数据，并且行为是未定义的！

为了解决这种条件竞争，C++ 标准库提供了和，并且使用比使用互斥量消耗的资源更少。

: 顾名思义，可以准确执行一次 callable object，其通过来判断是否被执行过，如果多次调用，会抛出异常。

call_one 分为:

active call：第一次调用

passive call：后序调用

exceptional call：抛出异常的调用，不会修改 once_flag

例如：

由此，可以将上面的例子修改为：

一个例子：

输出结果为:

局部 static 变量的线程安全的初始化方式（的替代方案）

初始化和定义完全在一个线程中发生，并且没有其他线程可在初始化完成前对其进行处理。

其实这个就是例子设计模式(Singleton)的思路，让 static 变量在函数内部完成初始化，从而使得调用该对象时，该对象一定被初始化。

但是为什么呢？

其实主要是因为“C++只能保证在同一个文件中声明的static变量的初始化顺序与其变量声明的顺序一致。但是不能保证不同的文件中的static变量的初始化顺序。”

然后对于单例模式而言，不同的单例对象之间进行调用也是常见的场景。比如我有一个单例，存储了程序启动时加载的配置文件的内容。另外有一个单例，掌管着一个全局的日志管理器。在日志管理初始化的时候，要通过配置文件的单例对象来获取到某个配置项，实现日志打印。

这时候两个单例在不同文件中各自实现，很有可能在日志管理器的单例使用配置文件单例的时候，配置文件的单例对象是没有被初始化的。这个未初始化可能产生的风险指的是C++变量的未初始化，而不是说配置文件未加载的之类业务逻辑上的未初始化导致的问题。

而写法中，单例对象是次访问的时候（也就是次调用函数的时候）才初始化的，但也是恰恰因为如此，因而能保证如果没有初始化，在该函数调用的时候，是能完成初始化的。所以先再访问这种形式的单例其关键并不是在于这个形式。而是在于其内容，局部static变量能保证通过函数来获取static变量的时候，该函数返回的对象是肯定完成了初始化的！

另外，该写法需要 C++11 的支持，因为在 C++11 之后，static 变量的初始化是线程安全的。

「详细信息参考这里—reference」

3.3.2 protect data struct which updatelessly

对于更新比较少，读取频繁的数据结构，使用显得有些反应过激了，因为在没有修改时，它将削弱并发读取数据的可能性，因此，这里需要一种不同的互斥量 – 读写锁：一个“写”线程独立访问，多个 “读” 线程并发访问。

C++ 标准库暂时没有提供“读者-写者锁”，但是 Boost 库提供了支持 (读写锁)，通常用于读操作比较频繁的，而写操作比较少的情况。

读写锁比起mutex具有更高的适用性，具有更高的并行性，可以有多个线程同时占用读模式的读写锁，但是只能有一个线程占用写模式的读写锁，读写锁的基本规则可以总结为“write first，read shared，cross mutex(交叉互斥)”，具体表现为读写锁的三种状态：

当读写锁是写加锁状态时，在这个锁被解锁之前，所有试图对这个锁加锁的线程都会被阻塞。（交叉互斥）
当读写锁在读加锁状态时，所有试图以读模式对它进行加锁的线程都可以得到访问权，但是以写模式对它进行加锁的线程将会被阻塞。（读共享，交叉互斥）
当读写锁在读模式的锁状态时，如果有另外的线程试图以写模式加锁，读写锁通常会阻塞随后的读模式锁的请求，这样可以避免读模式锁长期占用，而等待的写模式锁请求则长期阻塞。（写优先）

注：其实在读者-写者问题中，有读者优先和写者优先两种模式，只是在 shared_mutex which in boost library default complement in writing first，这其实也是有道理的，because we always want to read the least data，这就得保证写者优先。

例子：模拟 dns 缓存的修改和查询

3.3.3 nested lock

单单将数据保护起来并不能满足我们的需求。通常情况下，我们还想对单独的线程进行同步。例如，某个线程作为另一个线程的输入。

通过条件变量(condition variables)和期望(futures)实现线程之间的同步。

4.1.1 introduce

情景：我们需要等待一个事件。

最笨的方法是一直加锁，然后时间来临之后，处理事件，解锁。但是这种方法是很低效的，因为等待事件时我们持有锁但什么也不做。

进步的方法是下面这种（），每隔一段时间就进行一次检查，但是这种方法的问题是，很难确定中间间隔的时间，太短或者太长了都不好！

最好的办法就是使用条件变量，当时间发生时，广播“条件达成”的信息，由此出发等待该事件的线程。

4.1.2 condition variable

C++标准库对条件变量有两套实现：和。这两个实现都包含在头文件的声明中。两者都需要与一个互斥量一起才能工作(互斥量是为了同步)；前者仅限于与一起工作，而后者可以和任何满足最低标准的互斥量一起工作，从而加上了_any的后缀。因为更加通用，这就可能从体积、性能，以及系统资源的使用方面产生额外的开销，所以一般作为首选的类型，当对灵活性有硬性要求时，我们才会去考虑。

下面是使用处理等待数据

在 (1) 中，如果条件不满足( 返回 )，函数将解锁互斥量，并将这个线程置于阻塞或等待状态。

当在中调用通知条件变量之后，处理数据的线程从睡眠状态中苏醒，重新获得互斥锁，并且对条件再次检查，当条件不满足时，线程将对互斥量解锁，并且重新开始等待，当条件满足时，从返回并继续持有锁。

注意在唤醒之后需要再次检查条件，因为可能还有其他线程也被唤醒，此时会有竞争。这就是所谓的伪唤醒(spurious wakeup)，

这也是为甚么要使用而不是的原因 —— 等待中的线程必须在等待期间解锁互斥量，并在这之后对互斥量再次上锁，而没有这么灵活。

其实这也说明了的主要用途 —— 和配合使用，做到多次和。

4.1.3 thread safety queue

接口

线程安全的队列

同之前提到的一样，当我们执行时，会有接口之间的条件竞争，因此我们需要将这两个函数放到同一个函数中。

4.2.1 introdece

C++ 标准库模型将这种一次性事件成为期望(future)。当事件发生时，这个“期望”就不能被重置。

在C++标准库中，有两种“期望”，使用两种类型模板实现，声明在头文件中: 唯一期望(unique futures)()和共享期望(shared futures)()。这是仿照和。的实例只能与一个指定事件相关联，而的实例就能关联多个事件。后者的实现中，所有实例会在同时变为就绪状态，并且他们可以访问与事件相关的任何数据。这种数据关联与模板有关，比如和的模板参数就是相关联的数据类型。在与数据无关的地方，可以使用与的特化模板。虽然，我希望用于线程间的通讯，但是“期望”对象本身并不提供同步访问。当多个线程需要访问一个独立“期望”对象时，他们必须使用互斥量或类似同步机制对访问进行保护，如在第3章提到的那样。不过，在你将要阅读到的4.2.5节中，多个线程会对一个实例的副本进行访问，而不需要期望同步，即使他们是同一个异步结果。

最基本的一次性事件，就是一个后台运行出的计算结果。在第2章中，你已经了解了执行的任务不能有返回值，并且我能保证，这个问题将在使用“期望”后解决——现在就来看看是怎么解决的。

4.2.2 background task with return value — async

假设，你现在有一个需要长时间的运算，你需要能计算出一个有效的值，但是你现在并不迫切需要这个值。因为并不提供接受返回值的机制，这里就需要函数模板（也就是在中声明）

当不着急得到任务的结果时，你可以使用启动一个异步任务，与对象等待的方式不同，会返回一个对象，这个对象持有最终计算出来的结果，你只需要调用这个对象的成员函数；并且会阻塞线程直到“期望”状态未就绪为止。例如：

与方式一样，允许通过添加额外的调用参数，想函数传递额外的参数。

例如，第一个参数是指向成员函数的指针，第二个参数是提供这个函数成员类的具体对象。

和一样，当参数是右值时，拷贝操作将使用移动的方式转移原始数据。

我们还可以在调用之前向传递一个额外参数，这个参数的类型是，它提供了两种策略可供选择：

：在调用之后就开始创建线程
：延迟加载方式创建线程。调用不创建线程，直到调用了的或者时才创建线程。（lazy calculate）

默认策略是

例如：

有三种状态：

：异步操作还未完成
：异步操作已经完成
：异步操作超时，主要用于

reference

4.2.3 task and future

会将与函数或可调用对象进行绑定。当调用时，就会调用相关函数或可调用对象，当状态未就绪时，会存储返回值。

的模板参数是一个函数签名。我们传入对象的签名可以与模板参数中指定的签名不一致，但是必须能隐式转换到目标类型。

例如，一种便特化的的意义如下：

是一个可调用对象，可以封装在对象中，从而作为汉城函数传递到对象中，或作为可调用物对象传递到另一个函数中或直接调用。

例子1：

c++ reference 上的例子 2：

解释一下：这条语句并不会导致封装的可调用对象的执行，它仅仅是将的返回值存储到这个对象当中。

参考：

Zhihu

Cpp-reference

4.2.4 std::promises

cppreference 例1:

例2: 线程等待另一个线程的数据

[TODO]

在这里我发现了一个神奇的事情，如果是按照上面的形式（例2）即，lambda 表达式的形式创建线程，如果不 set_value() 的话，future::wait() 会一直等待，而使用显式的函数则不会（例1），为什么呢？

参考：

JianShu

Cpp-reference

4.2.5 exception and future

如果我们抛出一个异常，那么这个异常会存储到中，然后的状态设置为，之后调用会抛出已存储的异常。

注意！标准并未规定重新抛出的这个异常是原对象还是一份拷贝，这取决于山西i安

4.2.6 waiting of multiple thread

如果并行代码没办法让多个线程等待同一个事件，可以帮你解决这个问题。因为是只 move 的，所以其所有权可以在不同的实例中互相传递，但只有一个实例可以获得特定的同步结果，而实例是可 copy 的，所以多个对象可以引用同一关联期望值的结果。

例: std::shared_future

顾名思义，就是多个线程共享一个。可用在一个线程传递数据给多个线程的时候，多个线程在自身的线程空间内通过共享一个，这是线程安全的。

可以无限次调用，而仅能调用一次。

返回的一定是引用（模板参数是的除外）

在每一个的独立对象上成员函数调用返回的结果还是不同步的，所以为了在多个线程访问一个独立对象时，避免数据竞争，必须使用锁来对访问进行保护。优先使用的办法：为了替代只有一个拷贝对象的情况，可以让每个线程都拥有自己对应的拷贝对象。这样，当每个线程都通过自己拥有的对象获取结果，那么多个线程访问共享同步结果就是安全的。

4.3.1 introduce

Sometimes, it is needed to limited the wating time of the wait thread.

There are two ways to signated if timeout:

time duration(relative): you are expected to signated a duration of time like: 30s
time point(absolute): you are expected to signated a concrete time like: ,

The variable which used for relative time suffixed by , and other used for absolute time suffixed by

Before observe the usage of timeout funtion, let’s check the way to signated the time in C++

4.3.2 clock

对于 C++ 来说，时钟就是时间信息源。并且，时钟是一个，提供了四种不同的信息：

当前时间：会返回系统的当前时间，它属于 .
时间类型
时钟节拍：可能是标准库中提供的具有最小节拍周期（因此具有最高的精度）的时钟。
稳定时钟：

4.3.3 ratio

先介绍一下，他定义在头文件当中。

具体的可以参考 cppreference

4.3.4 literal

在 C++14 中的中预定义了许多后缀操作符用来表示时长中的常用单位来简化代码。同样，还用用于表示字符串的等。

例如：

4.3.5 time duration

例如：

例如：等待状态变为就绪需要 35ms

4.3.4 time point

例如：

例2: 等待条件变量满足条件 —— 有超时功能

4.3.5 use timeout

使用超时机制的函数

类型/命名空间函数返回值 std::this_thread[namespace] sleep_for(duration) N/A sleep_until(time_point) std::condition_variable 或 std::condition_variable_any wait_for(lock, duration) std::cv_status::time_out 或 std::cv_status::no_timeout wait_until(lock, time_point) wait_for(lock, duration, predicate) bool —— 当唤醒时，返回谓词的结果 wait_until(lock, duration, predicate) std::timed_mutex 或 std::recursive_timed_mutex try_lock_for(duration) bool —— 获取锁时返回true，否则返回fasle try_lock_until(time_point) std::unique_lock unique_lock(lockable, duration) N/A —— 对新构建的对象调用owns_lock(); unique_lock(lockable, time_point) 当获取锁时返回true，否则返回false try_lock_for(duration) bool —— 当获取锁时返回true，否则返回false try_lock_until(time_point) std::future 或std::shared_future wait_for(duration) 当等待超时，返回std::future_status::timeout wait_until(time_point) 当“期望”准备就绪时，返回std::future_status::ready 当“期望”持有一个为启动的延迟函数，返回std::future_status::deferred

现在，我们讨论的机制有：condition variable、“future”、“promise”还有 packaged_task。是时候从更高的角度去看待这些机制，怎么样使用这些机制，简化线程的同步操作。

同步工具在本章成为“构建块”。

比起在多个线程间共享数据，每个任务最好拥有自己的数据，并且其他线程可以通过使用获取运行结果。

4.4.1 funtional programming by future

functional programming(FP) is a programming way which the function_return_value only depend on the arguments and you will get the same result always if you pass the same arguments

串形版针对的：

qsort —— FP pattern with thread strongthen（并行版本）

在上面的代码中，每调用一次，我们便创建一个新的线程，由于递归执行的缘故，线程的创建是指数级别的，也就是说，如果递归执行 10 次，那么就会创建 1024 个线程！但创建太多线程显然是不好的，因此会自动执行某些操作，避免创建太多线程。这也符合的策略（既可立马创建新线程，也可以以延迟加载的方式创建线程）。

其实，如果以延迟加载的方式执行，也就是直到在返回的对象调用或者时才执行。

然鹅，当调用时，函数会同步执行，即调用者会阻塞直到函数运行结束，如果没有被调用，函数就绝对不会执行。

ref here

比起使用，你可以写一个spawn_task()函数对和做简单的包装，如下面代码所示；你需要为函数结果创建一个对象，可以从这个对象中获取“期望”，或在线程中执行它，返回“期望”。

其本身并不提供太多的好处(并且事实上会造成大规模的超额任务)，但是它会为转型成一个更复杂的实现铺平道路，将会实现向一个队列添加任务，而后使用线程池的方式来运行它们。我们将在第9章再讨论线程池。使用更适合于当你知道你在干什么，并且要完全控制在线程池中构建或执行过任务的线程。

4.4.2 synchronization by message passing

MPI：Message Passing Interface，消息传递接口

CSP：Communicating Sequentiasl Processer，通讯顺序进程

??????? THIS SECTION AND NEXT SECTION TODO

TODO …

同步操作对于使用并发编写一款多线程应用来说，是很重要的一部分：如果没有同步，线程基本上就是独立的，也可写成单独的应用，因其任务之间的相关性，它们可作为一个群体直接执行。

本章，我们讨论了各式各样的同步操作，从基本的条件变量，到“期望”、“承诺”，再到打包任务。

我们也讨论了替代同步的解决方案：函数化模式编程，完全独立执行的函数，不会受到外部环境的影响；还有，消息传递模式，以消息子系统为中介，向线程异步的发送消息。

本章主要内容：

设计并发数据结构
如何设计
实现数据结构

设计并发数据结构时，可以使用多线程中的构建块，比如：和。当然也要保证并发块在并发环境下的线程安全。

设计并发数据结构是为了让多线程并发访问，并且线程可对数据结构做相同或不同的操作。

多线程环境下，无数据丢失和损坏，苏哟偶的数据都维持原样，且无竞争条件的数据结构，称之为“线程安全”的数据结构。

实际上，我们要通过设计线程安全的数据结构为线程提供并发访问数据结构的机会。因为就本质来说，互斥量为了保护数据，会显示阻止线程对数据的并发访问。

6.1.1 guideline of desiging the concurrency DB

设计并发数据结构时，需要两方面的考量：

确保访问安全
真正并发访问

第三章已经对如何保证数据安全做过简单的描述：

确保无线程能够看到“不变量”变化时的状态
小心会引起条件竞争的接口，提供完整操作的函数，而非操作步骤（top-pop）
注意数据结构的行为是否会产生异常，从而确保“不变量”的状态
将死锁的概率降到最低。限制锁的范围，避免嵌套锁等

还需要考虑数据结构对于使用者有什么限制，当线程通过特殊的函数对数据结构进行访问时，其他的线程还有哪些函数能安全调用?

这是一个很重要的问题，普通的构造函数和析构函数需要独立访问数据结构，所以用户使用时，就不能在构造函数完成前或析构函数完成后对数据结构进行访问。当数据结构支持赋值操作swap()或拷贝构造时，作为数据结构的设计者，即使线程操纵数据结构中有大量的函数，也需要保证这些操作在并发下是安全的(或确保这些操作能够独立访问)，以保证并发访问时不会出错。

第二个方面是确保真正的并发，需要考虑一下问题：

操作在锁的范围中进行，是否允许在锁外执行？
数据结构中不同的互斥能否保护不同的区域？
所有操作都需要同级互斥量的保护吗？
能否对数据结构进行简单的修改，增加并发访问的概率？

这些问题都源于一个指导思想:如何让序列化访问最小化，让真实并发最大化?😊？？😭

允许线程并发读取的数据结构并不少见，但修改必须是单线程的，这种结构类似于。同样，这种数据结构也很常见—— 支持多线程的不同操作时，也能串行执行相同的操作。

最简单的线程安全结构通常会对数据使用互斥量或锁。虽然，这么做还有问题，不过这样做相对简单，并且能保证只有一个线程在同一时间对数据结构进行独立访问。为了更轻松的设计线程安全的数据结构，接下来了解一下基于锁的数据结构。

基于锁的并发数据结构确保访问线程持有锁的时间最短；对于只有一个互斥量的数据结构，需要锁之外的操作不能访问数据；使用多个互斥量保护数据结构不同的区域时要避免死锁。

6.2.1 threadsafe stack

在 push() 操作中，无论如何都无法避免新数据的创建，除非你直接 move 原来的数据（右值引用 + move），但是直接 move 原来的数据有一个问题，那就是如果内存不足，move 一半异常了，那么原来的数据就会被破坏，因此，使用传值的方式拷贝初始数据，在 move 到容器中，更为稳妥。

这里的 “异常 - 安全” 好恶心😭

另外，这里的代码是可能发生死锁的;

用户要对栈负责，当栈未对一个数据进行拷贝或分配时，用户就不能想当然的将其添加到栈中。

所有成员函数都使用 std::lock_guard<> 保护数据，所以栈成员函数才是“线程安全”的。当然，构造与析构函数不是“线程安全”的，但构造与析构只有一次。调用不完全构造对象或是已销毁对象的成员函数，无论在哪种编程方式下都不可取。所以，用户就要保证在栈对象完成构造前，其他线程无法对其进行访问。并且，要保证在栈对象销毁后，停止所有线程的访问操作。

串形化的线程会隐性的限制程序性能。例如我们需要 pop 一个元素，那么当栈为空时我们只能等待，但这种等待时无意义的，我们希望它不这么闲着等，而是去做一些其他事，因此，这需要用户编写等待和提示的代码（例如：条件变量）。下面的队列就是如此。

6.2.2 threadsafe queue – mutex && condition_variable

这里的代码在有一个问题，就是当 push() 执行 notice_one() 之后，如果唤醒的那个线程发生了异常死了，例如构造新的 shared_ptr 对象时发生异常，那么所有线程都将永眠，因为此时没有其它条件能将他们唤醒，解放方案有如下几种：

notice_all()，但是这么做的开销太大了，因为往往只有一个线程最终唤醒，而其他线程仍然需要沉睡
当唤醒的线程异常时，调用 notice_one() 去唤醒另一个线程
将的初始化过程移到push()中，并且存储实例，而非直接使用数据的值。将拷贝到内部中，就不会抛出异常了，这样wait_and_pop()又是安全的了。

下面是使用第三种方案修改后的代码：

6.2.3 threadsaft queue - small granularity && condition_variable

下面是一个单线程环境下简单队列的实现，它是一个有头尾节点的单链表，当链表为空时，头尾指针为空。

头节点 != 头指针

这段代码在单线程下没问题，但是在多线程下问题就太多了！

因为在给定的实现中有两个数据项(head①和tail②)；即使，使用两个互斥量，来保护头指针和尾指针，也会出现问题。

显而易见的问题就是push()可以同时修改头指针⑤和尾指针⑥，所以push()函数会同时获取两个互斥量。虽然会将两个互斥量都上锁，但这还不是太糟糕的问题。糟糕的问题是push()和pop()都能访问next指针指向的节点：push()可更新tail->next④，而后try_pop()读取head->next③。当队列中只有一个元素时，head==tail，所以head->next和tail->next是同一个对象，并且这个对象需要保护。不过，“在同一个对象在未被head和tail同时访问时，push()和try_pop()锁住的是同一个锁”，就不对了。所以，你就没有比之间实现更好的选择了。这里会“柳暗花明又一村”吗？

可以通过分离数据实现并发。

通过“预分配虚拟节点（无数据）”，确保这个节点永远在队列的最后，用来分离头尾指针能访问的节点。

经过修改之后，push 便只需要访问 tail，而原来还需要访问 head，try_pop 需要访问 head 和 tail，但是 head 只在开始时用了一下，所以存在的时间很短。

不过，最重大的提升在于，try_pop 和 push 不能对同一节点进行操作，也就不需要互斥了。因此，现在只需要一个互斥量来保护 head 和 tail 就行了。

那么，该如何加锁呢？

多线程环境下，节点及数据的分配时“并发安全”的。

下面是可上锁和等待的线程安全队列

栈和队列的设计太 easy 啦（然而我也招架不住😭），下面来点大的。😠😠😠

6.3.1 threadsafe dictionary

和栈和队列一样，标准容器的接口不适合多线程进行并发访问，因为这些接口都存在固有的条件竞争，所以这些接口需要砍掉或者重新修订。

并发访问时，最大的问题在于 —— 迭代器。例如当迭代器引用的元素被其它线程删除时，迭代器就会失效，但我们不知道。

查询表（字典）基本操作：

（增）添加 key-value
（删）删除 key-value
（改）修改指定 key 所对应的 value
（查）查询指定 key 所对应的 value
so on…

如果你坚持之前的线程安全指导意见，例如：不要返回一个引用，并且用一个简单的互斥锁对每一个成员函数进行上锁，以确保每一个函数线程安全。最有可能的条件竞争在于，当一对“键值-数据”加入时；当两个线程都添加一个数据，那么肯定一个先一个后。一种方式是合并“添加”和“修改”操作为一个成员函数，就像清单3.13对域名系统缓存所做的那样。

区别多线程环境下一下容器的并发能力：

二叉树，比如：红黑树
有序数组
哈希表

其中哈希表并发性能最好，因为哈希表可以设计为同 bucket+list(或有序数组)，而每一个 bucket 可以独立加锁，bucket 与 bucket 之间独立

下面是基于哈希表，使用读写锁，线程安全的，字典：

⚠️⚠️⚠️ [BUG] ⚠️⚠️⚠️

在上面的代码中出现了很恶心的 bug（也可能是我太蠢了），导致我排查了好长好长时间，其实错误原因很简单。

在成员函数中，如果我们添加了 const 函数修饰符，那么如果我们返回一个迭代器的话，其实返回的是 const_iterator 而不是 iterator，const_iterator 有底层修饰，不能修改指向的对象。

例如下面的代码会报错：

报错信息主要内容如下：

很明显的发现，编译器提示我们，我们的返回值是一个类型，而不是。

那你可能会说，如果我们不希望返回 const_ierator 的话，把 (1) 处的 const 去掉不久行了？

那你就得好好看了，下面的错误更隐蔽和恶心，去掉 (1) 处的 const 之后，

上面的报错信息不认真看，理解着看的话，有可能不知道他说的是什么意思！其实这种错误在《Effective C++》系列都是强调过的！由此可见，光理论，不实践，掌握的知识不牢固，容易忘！

其实人话来说，就是 get_val() 是一个 const 成员函数，所以，在这个函数中， this 指针是 this *const(底层 const)，想必如果你很敏感的话，那么你应该知道错在哪了！我们把一个 this *const 传入到一个非 const 的成员函数 get() 当中，那么在 get() 当中就可能修改我们的 this，从而间接的破坏了 get_val() 的 const 属性！

实际上，上面的 bug 正是《effective STL》的一条 item:

“const_iterator fist!”

那么，作者为什么会写出如此不严谨的代码呢？是选，有意思的一点是，如果不进行测试，上面的代码是没有问题的！那么，到底是作者写这本时的 C++ 和编译器的版本问题，还是作者偷懒没有进行测试呢？大概是前者吧！😊

最终在这篇博客找到了 bug 的解决方案，感恩！

最后，给出使用 iterator 的版本，只需要把所有 const 成员函数修饰去掉就行了。

解决问题的方法就是不让问题产生 😭

6.3.2 threadsafe list

同上面谈到的，容器中的迭代器在并发时会产生麻烦，除非让迭代器持有锁，但这是个很槽糕的做法。因此这意味着迭代器受限于锁，而不是容器。

替代方案是使用迭代函数，例如：将 for_each 作为容器本身的一部分。这就能让容器对迭代的部分进行负责和锁定。

。。。

链表应该提供的操作：（增删改查）

向列表添加一个元素
当某个条件满足时，就从链表中删除某个元素
当某个条件满足时，从链表中查找某个元素
当某个条件满足时，更新链表中的某个元素
（more）将当前容器中链表中的每个元素，复制到另一个容器中
（more）插入元素到某个指定的位置

使用细粒度锁最初的想法，是为了让链表每个节点都拥有一个互斥量。当链表很长时，那么就会有很多的互斥量!这样的好处是对于链表中每一个独立的部分，都能实现真实的并发：其真正感兴趣的是对持有的节点群进行上锁，并且在移动到下一个节点的时，对当前节点进行释放。下面的清单中将展示这样的一个链表实现。

学到了个新东西

可以在 while 的条件判断里面声名一个局部变量，并且可以在 while body 里面使用，但是有个限制，就是只能使用默认比价方式（0，nullptr），如果你想使用特殊的比较方式，例如：，那么局部变量 y 的作用域实际上是这个括号里面，除了括号就死了，因此在 while body 里面也就无法使用，这时候，就得在 while 外面声明这个变量了。

TODO

文章主要内容包括：

线程间划分数据的技术
影响并发代码性能的因素
性能因素是如何影响数据结构的设计
多线程代码中的异常安全
可拓展性
并行算法的实现

最直白的，对于一个线程，是让他充当一个“全能”线程来完成所有工作，还是充当一个“专业”线程完成一件事情，还是两者混合。等等。诸如此类的选择至关重要。

8.1.1 prepare divide

思想很简单，就是在创建线程之前，把多个任务分为一组，一个线程处理一组任务。

但是这样做仍然有一个不太好的地方，如代码2.8 所示，最后一步仍然是串行的：

不过，accumulate 实际上是一个递减操作（即任务的个数是逐渐减少的），因此当线程数量大于一个线程上最小处理项时，可以对函数递归调用，这样就可以最大化并行的程度。

原本递归是等一个子函数执行完，再执行另一个子函数。但是通过线程，我们可以同时递归执行多个子函数，自函数再递归执行多个自函数，每个子函数占用一个线程。

可以发现，这对线程数量的要求比较高！

8.1.2 recursion divide

快速排序就用到了递归！

下面是 list 的快速排序算法的实现：

8.1.3 work divide

多线程下有两个危险需要分离。

第一个是对错误的担忧（主要表现为线程间共享着很多的数据）
第二个是不同的线程需要相互等待。

这两种情况都是因为线程间很密切的交互。如果这种情况发生，就需要看一下为什么发生这么多交互。当所有交互都有相同的问题，就应该使用但线程来解决，并将引用同一源的线程提取出来。或者当有两个线程需要频繁的交流，在没有其它线程时，就可以将这两个线程合为一个线程。

当任务会应用到相同的任务序列，去处理独立的数据项时，就可以使用 pipeline 系统进行并发。

使用这种方式划分工作，可以为流水线中的每一阶段操作创建一个独立线程。

关于cpu的核和芯

原生多核，封装多芯

作者说，四核两芯的cpu可以有16个线程，是因为超线程吗？

8.2.1 cpu count

为了拓展线程的数量，且与硬件所支持的并发线程数一致，C++ 标准库提供了，使用这个函数可以知道在给定硬件上可以拓展的线程数量。

我的 MacBook M1 Air 才是 8

使用的线程个数不是越多越好，太多线程进行切换会导致 oversubscription(超额请求)

8.2.2 race data and cache ping-pong

当多个线程在不同的处理器上时，对数据的读取通常不会有问题，因为数据会拷贝到每个线程的缓存中，并让多个处理器同时处理。然鹅，当有线程对数据进行修改，并且需要同步到其它核心的缓存时，需要浪费一定的时间。这样的修改可能会让其它处理情停下来，等待硬件内存更新缓存的数据。并且，根据 cpu 指令，这是一个特别慢的操作。

high contention：处理器之间经常需要等待数据的更改

low contention：处理器之间很少需要相互等待

cache ping-pong：在多个处理器的缓存之间来回传递的数据

避免 cache ping-pong 的方法就是减少两个线程对同一个内存为止的竞争

cache line sharing

其实就是减少缓存的刷新次数，降低数据伪共享缓存的概率。

….

当为多线程设计数据结构时，需要考虑：contention, false sharing, data proximity(数据临近)，这些对性能都有重大影响。

[TODO]

ref1

ref2

ref3

原子类型()是封装了一个值的类型，它的访问保证不会导致数据的竞争，并且可以用于在不同的线程之间同步内存访问。

原子类型主要用于避免加锁解锁时的程序开销，从而提高性能。(互斥量加锁一般针对的是一个代码段，而原子操作针对的一般是一个变量)。

原子类型是“指令”层面上的支持，因此它的性能相比锁和消息传递会好很多。

std::atomic 内部使用了 CAS(compare and swap) 自旋锁：

是原子布尔类型，它保证是免锁（lock-free）的。只支持两种操作：和

自旋锁

自旋锁是计算机科学用于多线程同步的一种锁，线程反复检查锁变量是否可用。由于线程在这一过程中保持执行，因此是一种忙等待。一旦获取了自旋锁，线程会一直保持该锁，直至显式释放自旋锁。自旋锁避免了进程上下文的调度开销，因此对于线程只会阻塞很短时间的场合是有效的。

C++ 是系统级别的编程语言，标准委员会的目标是不需要比C++还要底层的高级语言。C++ 应该向程序员提供足够的灵活性，无障碍的去做他们想要做的事情。需要时，也可以“接触硬件”。原子类型和原子操作就可以“接触硬件”，并提供底层同步操作，通常会将指令数缩减到 1～2 个CPU指令。

TODO ⌛️⌛️⌛️

一个简单的示例：

document

multiple thread document

thread pool in C

可以通过sleep稍微控制线程的执行顺序。。。

一个线程就是一个“任务”，当我们创建一个线程时，它就开始执行这个任务。

我们创建的线程一般称为子线程，为啥不是主线程呢？因为主线程一般是默认存在的！当我们在一个进程中创建线程时，主进程会变成主线程。

因此，当主线程退出时，也就意味着主进程结束了，也就意味着分配的虚拟内存空间要释放，因此其余线程也要销毁。

但是，我们可以通过调用相关API，使得主线程退出后，子线程也可以正常运行。

在上面提到，如果主线程退出，子线程没执行完也会结束。我们也提到，只需要使用（线程退出函数）就可以让当前线程“马上退出”，并且不会影响其他线程的正常运行。

如果所有线程都使用了线程退出函数，那么当所有线程执行结束之后，系统资源（虚拟地址空间）会被操作系统回收。

当线程退出时，还可以通过该函数传出一些数据（其实是这些数据的地址）。注意不能传出栈中的数据。

可以通过下面三种方式：

heap
全局/static
接受主线程（调用线程）中的数据，并传出接受的数据。

子线程是不能访问主线程的栈空间的，但是主线程可以主动传入。

主线程回收子线程资源。

回收什么资源呢？

我们知道，线程独占stack等，当线程结束时，stack资源会自动释放，heap，data和text等共享资源由操作系统自动回收。

主线程回收的主要是“内核资源”。这件事子线程自己干不了。

为什么第二个参数接受一个二级指针呢？

因为我们如果要接受返回的数据，就要使用一个指针（）接受。因为返回的数据类型就是。

如果我们要修改一个指针（注意不是指针指向的数据），就要传入一个指针的地址，所以我们就要用指向指针的指针。

注意 join 是一个阻塞函数。

detach：分离

默认情况下，主线程和子线程是有联系的，即，主线程需要释放子线程拥有的资源。

调用这个函数之后，指定的子线程和主线程分离。当子线程推出的时候，其占用的内核资源就被系统的其他进程接管并回收了。（这意味着无法回收子线程资源）

可能你会问，我们已经有了了啊，他已经可以完成线程内核资源回收的任务了，为什么还有有呢，这是因为是阻塞性函数，也就是说，当子线程不时，主线程就会一直处于阻塞状态。

就是给主线程减负的，当子线程结束时，其资源不需要主线程来回收。

但是当主线程结束时，子线程仍然会结束，即使子线程处于状态。如果我们希望主线程结束时不影响子线程的执行，应该调用函数。

上面代码希望通过两个线程实现对 sum 的累加，并希望结果为50，但是却不是。

如其名，互斥锁只能被一个线程使用。

通过互斥锁，让线程线性执行，这样就不会有并发问题。

锁的个数取决于临界资源而不是线程个数。

另外，可以发现使用互斥锁的函数都是用的mutex指针，这就说明我们的mutex不能分配在局部内存。

key :strict

用来修饰指针，只有这个关键字修饰的指针才能访问指向的内存地址，其他指针都是不行的（类型匹配也不行）。

TODO: 但是我测试不行？？

读写锁是互斥锁的升级版。在做读操作的时候可以提高程序的执行效率，如果所有的线程都是读操作，那么都是并行的。而使用互斥锁，读操作是串行的。

其与互斥锁的区别主要在于读操作可以并行，因此，当线程涉及到大量读操作，读写锁的效率比互斥锁高。

读写锁虽然有读锁和写锁，但他是「一把锁」。

写锁的优先级比读锁高。

API:

Example：下面是，5个线程执行读操作，3个线程执行写操作。

运行之后，我们可以发现，所有打印出来的 sum 是升序的，这说明我们的读写锁没有问题，另外，我们可以发现，有大量读操作在最后才执行，这是因为前面说的，当一个读操作和一个写操作同时访问同一个临界资源时，写操作的优先级更高。

严格意义上来说，条件变量的主要作用不是处理线程同步，而是进行线程的阻塞。

如果多线程下只使用条件变量无法完成线程的同步，必须要配合互斥锁来使用。

那既然有了互斥锁，为什么还要用条件变量呢？主要是为了处理「生产者和消费者模型」。（常规的临界资源只有一份，只允许一个线程访问，而有时候临界资源可能有多份，可以分给多个线程，这就是条件变量的用处）

APIs

为什么 pthread_cond_wait() 的参数有一个 mutex？

首先，我们需要知道 wait 做了什么？

释放自己占据的 mutex（作为参数传入）

阻塞，等待被别的线程唤醒

被唤醒后，再次获取 mutex（作为参数传入）

现在明白了吧，一般来说，我们执行 cond_wait 的时候，都是已经 mutex_lock 的，如果我们不 unlock 的话，其他线程就无法进入临界区，也就无法 cond_signal，那么被阻塞的线程也就不会被唤醒。也就发生了死锁。

example1：生产者消费者模型 - 链表

在这个生产者消费者模型中，我们使用链表储存产品，因为理论上可以存储无限个产品，所以只需要使用一个条件变量判断产品队列是否为空。

如果使用数组，即产品是有限的，那么我们还需要一个新的条件变量来判断产品是否满了。

注意我们不能同时使用同一个条件变量判断是否为满和是否为空。

example2：生产者消费者模型 - 数组

同条件变量一样，信号量主要用于阻塞线程，不能完全保证线程安全，如果要保证线程安全，需要信号量和互斥锁一起使用。

另外，需要注意信号量的wait和条件变量的wait是不同的，这从参数列表就可以发现，信号量的wait参数列表中并没有 mutex 参数，因此，当线程阻塞时，他不会释放获取的 mutex 资源，因此，我们必须通过手工的方式控制信号量和锁的获取顺序：先获取信号量，再获取锁，以避免死锁。

example：生产者和消费者模型

为什么要有线程池

同内存池的设计需求一样，线程池也是用来避免线程的大量创建和销毁所带来的巨大开销。

线程池的组成部分

任务队列：线程就是用来处理任务的，但是可能任务的个数要远大于线程的个数，因此无法一次性处理完所有的任务，因此我们就需要用一个 data struct（一般为数组 or 链表）将任务存起来。
工作的线程：处理任务队列的任务的消费者，通常有多个。
管理者线程：不处理任务队列的任务，负责管理工作的线程（增加或者销毁线程），只有一个。

任务队列的存在也意味着，线程池就差不多是一个生产者消费者模型。线程池负责为负消费者线程和任务队列，而使用者负责维护生产者线程（通过线程池提供的 API 接口）。

任务队列存储的是任务，而任务通常是一个个（回调）函数，因此任务队列需要存储函数的地址。