术语表

本术语表只为基本术语提供参考。

ACID

事务具有原子性、一致性、隔离性和持久性(ACID)属性的操作。在C++中，除了持久性之外，事务性内存的所有属性都保持不变。

  • 原子性：执行或不执行块的所有语句。
  • 一致性：系统始终处于一致的状态，所有事务构建顺序一致。
  • 独立性：每个事务在完全隔离的情况下运行。
  • 会对事务的持久性进行记录。

CAS

CAS表示compare-and-swap，是一个原子操作。它将内存位置与给定值进行比较，如果内存位置与给定值相同，则修改内存位置的值。在C++中，CAS操作有std::compare_exchange_strong和std::compare_exchange_weak。

可调用单元

可调用单元的行为类似于函数。不仅是函数，还有函数对象和Lambda函数。如果一个可调用单元接受一个参数，它就被称为一元可调用单元；如果有两个参数，就是二元可调用单元。

谓词是返回布尔值的特殊可调用项。

并发性

并发性意味着多个任务的重叠执行。而且，并发是并行的超集。

临界区

临界区是一段代码，最多只有一个线程可以访问。

立即求值

如果立即求值，则立即求出表达式的值，则该策略与延迟求值正交。立即求值通常也称为贪婪求值。

Executor

执行者是与特定执行上下文相关联的对象。它提供一个或多个执行函数，用于为可调用的函数对象创建执行代理。

函数对象

首先，不要叫它们函子。这是一个明确的数学术语，叫做范畴理论。

函数对象是行为类似于函数，通过实现函数调用操作符来实现这一点。由于函数对象是对象，因此可以有属性和状态。

  1. struct Square{
  2.     void operator()(int& i){i= i*i;}
  3. };
  5. std::vector<int> myVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  7. std::for_each(myVec.begin(), myVec.end(), Square());
  9. for (auto v: myVec) std::cout << v << " "; // 1 4 9 16 25 36 49 64 81 100

实例化函数对象

常见的错误是在算法中使用函数对象(Square)的名称，而不是函数对象(Square())本身的实例，比如：std::for_each(myVec.begin()， myVec.end()， Square)，应该使用：std::for_each(myVec.begin()， myVec.end()， Square())。

Lambda函数

Lambda函数可以就地提供需要的功能，编译器当场就能得到相应的信息，因此具有极佳的优化潜力。Lambda函数可以通过值或引用来接收它们的参数，还可以通过值或引用捕获已定义的变量。

  1. std::vector<int> myVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  2. std::for_each(myVec.begin(), myVec.end(), [](int& i){ i= i*i; });
  3. // 1 4 9 16 25 36 49 64 81 100

应该首选Lambda函数

如果可调用的功能是简短和可以自解释的，使用Lambda函数最好不过。Lambda函数通常比函数或函数对象更快，而且更容易理解。

延迟求值

延迟求值的情况下，仅在需要时才对表达式求值。该策略与立即求值策略正交。延迟求值通常称为按需调用。

无锁

如果保证了系统范围内的进程无影响，那么非阻塞算法就是无锁的。

未唤醒

未唤醒是指，线程由于竞争条件而丢失唤醒通知的情况。

如果使用没有使用谓词，可能会发生这种情况。

数学规律

某个集合X上的一个二进制操作(*)：

  • 结合律，满足x, y, z中的所有x, y, z的结合律：(x y) z = x (y z)
  • 交换律，满足所有x和y的交换律x y = y x

内存位置

内存位置的详解可以参考cppreference.com

  • 标量类型的对象(算术类型、指针类型、枚举类型或std::nullptr_t。
  • 非零长度的最大连续序列。

内存模型

内存模型定义了对象和内存位置之间的关系，特别是处理了以下问题：如果两个线程访问相同的内存位置，会发生什么情况。

修改顺序

对特定原子对象M的所有修改，都以特定的顺序进行，这个顺序称为M的修改顺序。因此，线程读取原子对象时，不会看到比线程已经观察到的值更“旧”的值。

Monad(单子)

Haskell作为一种纯函数语言，只有纯函数。这些纯函数的一个关键特性，当给定相同的参数时，总是返回相同的结果。有了这个透明参照的属性，Haskell函数才不会有副作用。因此，Haskell有一个概念上的问题。到处都是有副作用的计算，这些计算可能会失败，可能返回未知数量的结果，或者依赖于环境。为了解决这个概念上的问题，Haskell使用单子并将它们嵌入到纯函数语言中。

经典的单子封装：

  • I/O单子：计算输入和输出的结果。
  • 可能性单子：可能会返回计算结果的单子。
  • 错误单子：计算可能失败。
  • 列表单子：计算可以有任意数量的结果。
  • 状态单子：基于状态的计算。
  • 读者单子：基于环境的计算。

单子的概念来自数学中的范畴理论，其处理对象之间的映射。单子是抽象的数据类型，将简单的类型转换为丰富的类型。这些丰富类型的值称为一元值。当进入单子，一个值只能由一个函数组合转换成另一个一元值。

这种组合尊重了单子的独特结构。因此，当发生错误，错误单子中断它的计算，或重新构建状态单子的状态。

一个单子包括三个部分:

  • 类型构造函数：定义简单数据类型，如何成为一元数据类型。
  • 函数:
    • 恒等函数：在单子中引入一个简单的值。
    • 绑定操作符：定义如何将函数应用于一元值，以获得新的一元值。
  • 功能规则:
    • 恒等函数的左右必须是恒等元素。
    • 函数的复合必须遵循结合律。

要使错误单子成为类型类单子的实例，错误单子必须支持恒等函数和绑定操作符，这两个函数定义了错误单子应该如何处理计算中的错误。如果使用错误单子，错误处理会在后台完成。

单子由两个控制流组成：用于计算结果的显式控制和用于处理特定副作用的隐式控制流。

当然，也可以用更少的词来定义单子：“单子只是内函子类中的一个独异点(monoid)。”

单子在C++中变得越来越重要。在C++ 17中，添加了std::optional ，这是一种可能性单子。在C++20/23中，可能会从Eric Niebler那里得到扩展future和范围库，二者也都是单子。

无阻塞

如果任何线程的失败或挂起，不会导致另一个线程的失败或挂起，则称为非阻塞。这个定义来自于《Java并发实践》。

并行性

并行性意味着同时执行多个任务。并行性是并发性的一个子集。

谓词

谓词是返回布尔值的可调用单元。如果一个谓词有一个参数，它就称为一元谓词。如果一个谓词有两个参数，就称为二元谓词。

模式

“每个模式规则都是一个由三部分组成，表明了特定上下文、问题和解决方案之间的关系。“ —— Christopher Alexander

RAII

资源获取是初始化(RAII)，代表C++中的一种流行技术，在这种技术中，资源的获取和释放与对象的生命周期绑定在一起。这意味着对于锁，互斥锁将被锁定在构造函数中，并在析构函数中解锁。这种RAII实现，也称为范围锁定。

C++中的典型用例有：管理互斥锁生命周期的锁、管理资源(内存)生命周期的智能指针，或者管理元素生命周期的标准模板库容器。

释放序列

原子对象M的释放序列，以释放操作A为首，是M修改顺序中最大的连续子序列，其中第一个操作为A，每个后续操作为:

  • 由执行A操作的线程进行的操作
  • 原子的读-改-写操作。

顺序一致的存储模型

顺序一致有两个基本特征:

  1. 程序的指令是按源代码顺序执行的。
  2. 所有线程上的所有操作都遵循全局顺序。

序列点

序列点定义了程序执行过程中的任何一个结点。在这个点上，可以保证先前评估的所有执行效果，而不影响后续评估的 执行效果。

伪唤醒

伪唤醒是一种条件变量的现象。可能发生的情况是，条件变量的等待组件错误地获取了一个通知。

线程

计算机科学中，执行线程是可由调度器独立管理的最小程序指令序列，调度器通常是操作系统的一部分。线程和进程的实现在不同的操作系统之间是不同的，但是在大多数情况下，线程是进程的一个组件。多个线程可以存放在于一个进程中，并发执行并共享内存等资源，而不同的进程不共享这些资源。特别是，进程中的线程在任何给定时间，共享其可执行代码和变量。想要了解更多信息，可以阅读维基百科关于线程)的文章。

全序关系

总序是一个二元关系(<=)在某个集合X上表现，其有反对称性、传递性，完全性。

  • 反对称性：如果a <= b并且b <= a，则a == b
  • 传递性：如果a <= b, b <= c，则a <= c
  • 完全性：a <= b或b <= a

volatile

volatile通常用于表示可以独立于常规程序流进行更改的对象。例如，这些对象在嵌入式编程中表示一个外部设备(内存映射I/O)。由于这些对象可以独立于常规程序流进行更改，并且其值可以直接写入主内存，因此不会在缓存中进行优化存储。

无等待

当有每个线程都有进程保证不会互相影响时，那么一个非阻塞算法是无等待的。