术语表

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

ACID

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

  • 原子性:执行或不执行块的所有语句。

  • 一致性:系统始终处于一致的状态,所有事务构建顺序一致。

  • 独立性:每个事务在完全隔离的情况下运行。

  • 会对事务的持久性进行记录。

CAS

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

可调用单元

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

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

并发性

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

临界区

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

立即求值

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

Executor

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

函数对象

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

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

struct Square{
    void operator()(int& i){i= i*i;}
};

std::vector<int> myVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

std::for_each(myVec.begin(), myVec.end(), Square());

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函数可以通过值或引用来接收它们的参数,还可以通过值或引用捕获已定义的变量。

std::vector<int> myVec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::for_each(myVec.begin(), myVec.end(), [](int& i){ i= i*i; });
// 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. 所有线程上的所有操作都遵循全局顺序。

序列点

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

伪唤醒

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

线程

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

全序关系

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

  • 反对称性:如果a <= b并且b <= a,则a == b

  • 传递性:如果a <= b, b <= c,则a <= c

  • 完全性:a <= b或b <= a

volatile

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

无等待

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

Last updated