程序员经验分享-hwhale

memory-ordering-at-compile-time

2023-11-03

浅谈Memory Reordering

 

 

Memory ordering

在我们编写的 C/C++代码和它被在 CPU 上运行,按照一些规则,代码的内存交互会被乱序.内存乱序同时由编译器(编译时候)和处理器(运行时)造成,都为了使代码运行的更快.

被编译开发者和处理器制造商遵循的中心内存排序准则是:

不能改变单线程程序的行为.

因为这条规则,在写单线程代码时内存乱序被普遍忽略.即使在多线程程序中,它也被时常忽略,因为有 mutexes,semaphores 等来防止它们调用中的内存乱序.仅当 lock-free 技术被使用时,内存在不受任何互斥保护下被多个线程共享,内存乱序的影响能被看到.

下面先比较 Weak 和 Strong 的内存模型,然后分两部分,实际内存乱序如何在编译和运行时发生,并如何防止它们.

Weak VS strong Memory Models

Jeff Preshing 在 Weak vs. Strong Memory Models 中很好的总结了从 Weak 到 Strong 的类型:

非常弱 数据依赖性的弱 强制 顺序一致
DEC Alpha ARM X86/64 dual 386
C/C++11 low-level atomics PowerPC SPARC TSO Java volatile/C/C++11 atomics

弱内存模型

在最弱的内存模型中,可能经历所有四种内存乱序 (LoadLoad, StoreStore, LoadStore and StoreLoad).任何 load 或 store 的操作能与任何的其他的 load 或 store 操作乱序,只要它不改变一个独立进程的行为.实际中,这样的乱序由于编译器引起的指令乱序或处理器本身处理指令的乱序.

当处理器是弱硬件内存模式,通常称它为 weakly-ordered 或 weak ordering.或说它有 relaxed memory model. DEC Alpha 是 最具代表 的弱排序的处理器.

C/C++的底层原子操作也呈现弱内存模型,无论代码的平台是如 x86/64 的强序处理器.下面章节 Memory ordering at compile time 会演示其弱内存模型,并说明如何强制内存顺序来保护编译器乱序.

数据依赖性的弱

ARM 和 PowerPC 系列的处理器内存模型和 Alpha 同样弱,除了它们保持 data dependency ordering.它意味两个相依赖的load(load A, load B<-A)被保证顺序load B<-A总能在 load A之后.(A data dependency barrier is a partial ordering on interdependent loads only; it is not required to have any effect on stores, independent loads or overlapping loads.)

强内存模型

弱和强内存模型区别存在分歧.Preshing 总结的定义是:

一个强硬件内存模型是在这样的硬件上每条机器指令隐性的保证 acquire and release
semantics 的执行.因此,当一个 CPU 核进行了一串写操作,每个其他的 CPU 核看到这些值的改变顺序与其顺序一致.

所以也就是保证了四种内存乱序 (LoadLoad, StoreStore, LoadStore and StoreLoad) 中的 3 种,除了不保证 StoreLoad 的顺序.基于以上的定义,x86/64 系列处理器基本就是强顺序的.之后 Memory ordering at processor time 可以看到 StoreLoad 在 X86/64 的乱序实验.

顺序一致

在顺序一致 (Sequential consistency) 的内存模型中,没有内存乱序存在.

如今,很难找到一个现代多核设备保证在硬件层 Sequential consistency.也就早期的 386 没有强大到能在运行时进行任何内存的乱序.

当用上层语言编程时,Sequential consistency 成为一个重要的软件内存模型.Java5 和之后版本,用volatile声明共享变量.在 C+11 中,可以使用默认的顺序约束memory_order_seq_cst在做原子操作时.当使用这些术语后,编译器会限制编译乱序和插入特定 CPU 的指令来指定合适的 memory barrier 类型.

Memory ordering at compile time

看如下代码:

test.c

1
2
3
4
5

int A, B;
void test() {
  A = B + 1;
  B = 0;
}

不打开编译器的优化,把它编译成汇编,我们可以看到,B的赋值在A的后面,和原程序的顺序一样.

  

1
2
3
4
5
6

$ gcc -S -masm=intel test.c

	mov	eax, DWORD PTR B
	add	eax, 1
	mov	DWORD PTR A, eax
	mov	DWORD PTR B, 0

用O2打开优化:

  

1
2
3
4
5
6

$ gcc -S -O2  -masm=intel test.c

	mov	eax, DWORD PTR B
	mov	DWORD PTR B, 0
	add	eax, 1
	mov	DWORD PTR A, eax

这次编译器把B的赋值提到A的前面.为什么它可以这么做呢?内存顺序的中心没有破坏.这样的改变并不影响单线程程序,单线程程序不能知道这样的区别.

但是当编写 lock-free 代码时,这样的编译器乱序就会引起问题.看如下例子,一个共享的标识来表明其他共享数据是否更新:

  

1
2
3
4
5
6

int value;
int updated = 0;
void UpdateValue(int x) {
    value = x;
    update = 1;
}

如果编译器把update的赋值提到value赋值的前面.即使在单核处理器系统中,会有问题:在两个参数赋值的中间这个线程被中断,使得另外的程序通过update判断以为value的值已经得到更新,实际上却没有.

显性的 Compiler Barriers

一种方法是用一个特殊的被称为 Compiler Barrier 的指令来防止编译器优化的乱序.以下 asm volative 是 GCC 中的方法.

test_barrier.c

1
2
3
4
5
6

int A, B;
void test() {
  A = B + 1;
  asm volatile("" ::: "memory");
  B = 0;
}

经过这样的修改,打开优化,B的存储将保持在要求的顺序上.

  

1
2
3
4
5
6

$ gcc -S -O2  -masm=intel test.c

	mov	eax, DWORD PTR B
	add	eax, 1
	mov	DWORD PTR A, eax
	mov	DWORD PTR B, 0

隐性的 Compiler Barriers

在 C++11 中原子库中,每个不是 relaxed 的原子操作同时是一个 compiler barrier.

  

1
2
3
4
5
6
7

int value;
std::atomic<int> updated(0);
void UpdateValue(int x) {
    value = x;
    // reordering is prevented here
    update.store(1, std::memory_order_release);
}

每一个拥有 compiler barrier 的函数本身也是一个 compiler barrier,即使它是 inline 的.

  

1
2
3
4
5
6
7

int a;
int b;
void DoSomething() {
    a = 1;
    UpdateValue(1);
    b = a + 1;
}

进一步推知,大多数被调用的函数是一个 compiler barrier.无论它们是否包含 memory barrier.排除 inline 函数,被声明为pure attribution 或当 link-time code generation 使用时.因为编译器在编译时,并不知道UpdateValue的运行是否依赖于a或会改变a的值从而影响b,所以编译器不会乱序它们之间的顺序.

可以看到,有许多隐藏的规则禁止编译指令的乱序,也防止了编译器多进一步的代码优化,所以在某些场景 Why the “volatile” type class should not be used, 来让编译器进一步优化.

无缘由的存储

有隐形的 Compiler Barriers,同样 GCC 编译器也有无缘由的存储.来自这里的实例:

  

1
2
3
4
5
6
7
8

extern int v;

    void
    f(int set_v)
    {
      if (set_v)
        v = 1;
    }

在 i686,GCC 3.3.4–4.3.0 用O1编译得到:

  

1
2
3
4
5
6
7
8

        pushl   %ebp
        movl    %esp, %ebp
        cmpl    $0, 8(%ebp)
        movl    $1, %eax
        cmove   v, %eax        ; load (maybe)
        movl    %eax, v        ; store (always)
        popl    %ebp
        ret

在单线程中,没有问题,但多线程中调用f(0)仅仅只是读取 v 的值,但中断后回去覆盖其他线程修改的值.引起 data rate.在新的 C++11 标准中明确禁止了这样的行为,看最近 C+11 标准进行的 draft§1.10.22 节:

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard.

Memory ordering at processor time

看一个简单的 CPU 乱序的简单例子,即使在强内存模型的 X86/64 也能看到.有两个整数X和Y初始是 0,另外两个变量 r1 和 r2 读取它们的值,两个线程并行运行,执行如下的机器代码:

每个线程存储 1 到一个共享变量,然后把对方变量读取到一个变量或一个寄存器中.无论哪个线程先写 1 到内存,另外个线程读回那个值,意味着最后 r1=1 或 r2=1 或两者都是.但是 X86/64 是强内存模型,它还是允许乱序机器指令.特别,每个线程允许延迟存储到读回之后.以致最后 r1 和 r2 能同时等于 0–违反直觉的一个结果.因为指令可能如下顺序执行:

写一个实例程序,实际看一下 CPU 的确乱序了指令.源码可以 Github 下载.两个读写的线程代码如下:

  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

sem_t begin_sem1;
sem_t begin_sem2;
sem_t end_sem;

int X, Y;
int r1, r2;

void *ThreadFunc1(void *param) {
  MersenneTwister random(1);
  for (;;) {
    sem_wait(&begin_sem1);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    X = 1;
    asm volatile("" ::: "memory");  // prevent compiler ordering
    r1 = Y;
    sem_post(&end_sem);
  }
  return NULL;
}

void *ThreadFunc2(void *param) {
  MersenneTwister random(2);
  for (;;) {
    sem_wait(&begin_sem2);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    Y = 1;
    asm volatile("" ::: "memory");  // prevent compiler ordering
    r2 = X;
    sem_post(&end_sem);
  }
  return NULL;
}

随机的延迟被插入在存储的开始处,为了交错线程的开始时间,以来达到重叠两个线程的指令的目的.随机延迟使用线程安全的MersenneTwister类.汇编代码asm volatile("" ::: "memory");如上节所述只是用来 防止编译器的乱序, 因为这里是要看 CPU 的乱序,排除编译器的乱序影响.

主线程如下,利用 POSIX 的 semaphore 同步它与两个子线程的同步.先让两个子线程等待,直到主线程初始化X=0和 Y=0.然后主线程等待,直到两个子线程完成操作,然后主线程检查r1和r2的值.所以 semaphore 防止线程见的不同步引起的内存乱序,主线程代码如下:

  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int main(int argc, char *argv[]) {
  sem_init(&begin_sem1, 0, 0);
  sem_init(&begin_sem2, 0, 0);
  sem_init(&end_sem, 0, 0);

  pthread_t thread[2];
  pthread_create(&thread[0], NULL, ThreadFunc1, NULL);
  pthread_create(&thread[1], NULL, ThreadFunc2, NULL);

  int detected = 0;
  for (int i = 1; ; ++i) {
    X = 0;
    Y = 0;
    sem_post(&begin_sem1);
    sem_post(&begin_sem2);
    sem_wait(&end_sem);
    sem_wait(&end_sem);
    if (r1 == 0 && r2 == 0) {
      detected++;
      printf("%d reorders detected after %d iterations\n", detected, i);
    }
  }
  return 0;
}

在 Intel i5-2435M X64 的 ubuntu 下运行一下程序:

  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1 reorders detected after 2181 iterations
2 reorders detected after 4575 iterations
3 reorders detected after 7689 iterations
4 reorders detected after 22215 iterations
5 reorders detected after 60023 iterations
6 reorders detected after 60499 iterations
7 reorders detected after 61639 iterations
8 reorders detected after 62243 iterations
9 reorders detected after 67998 iterations
10 reorders detected after 68098 iterations
11 reorders detected after 71179 iterations
12 reorders detected after 71668 iterations
13 reorders detected after 72417 iterations
14 reorders detected after 73970 iterations
15 reorders detected after 78227 iterations
16 reorders detected after 81897 iterations
17 reorders detected after 82722 iterations
18 reorders detected after 85377 iterations
...

差不多每 4000 次的迭代才发现一次 CPU 内存乱序.所以多线程的 bug 是多么难发现.那么如何消除这些乱序.至少有如下两种方法:

  1. 让两个子线程在同一个 CPU 核下运行.(没有可移植性方法,如下是 linux 平台的).
  2. 使用 CPU 的 memory barrier 防止它的乱序.

Lock to one processor

让两个子线程在同一个 CPU 核下运行,代码如下:

  

1
2
3
4
5

  cpu_set_t cpus;
  CPU_ZERO(&cpus);
  CPU_SET(0, &cpus);
  pthread_setaffinity_np(thread[0], sizeof(cpu_set_t), &cpus);
  pthread_setaffinity_np(thread[1], sizeof(cpu_set_t), &cpus);

Place a memory barrier

防止一个 Store 在 Load 之后的乱序,需要一个 StoreLoad 的 barrier.这里使用 mfence的一个全部 memory barrier,防止任何类型的内存乱序.代码如下:

  

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void *ThreadFunc1(void *param) {
  MersenneTwister random(1);
  for (;;) {
    sem_wait(&begin_sem1);
    // random delay
    while (random.Integer() % 8 != 0) {
    }
    X = 1;
    asm volatile("mfence" ::: "memory");  // prevent CPU ordering
    r1 = Y;
    sem_post(&end_sem);
  }
  return NULL;
  }

More

  1. University of Cambridge 整理的文档和论文
  2. Paul McKenney 概括他们做的一些工作和工具
  3. The Art of Multiprocessor Programming
  4. C++ Concurrency in Action: Practical Multithreading
  5. Is Parallel Programming Hard, And, If So, What Can You Do About It?
  6. The C++11 Memory Model and GCC

Summarization

  1. 有两种内存乱序存在:编译器乱序和 CPU 乱序.
  2. 如何防止编译器乱序.
  3. 如何防止 CPU 乱序.

Posted by DreamRunner Jun 28th, 2014  Multithreading

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

memory barrier

memory-ordering-at-compile-time 的相关文章

  • 实现数据字典的缓存、加载、刷新和映射的集成框架

    前言 在业务开发的过程中 总是会遇到字典打交道 比如说 性别 类型 状态等字段 都可以归纳为字典的范围 字典的组成分成 字典类型 字典数据 其中 字典数据 归属于一类的 字典类型 可以通过 字典类型 获取 字典数据 例如开头提到的 性别就为

  • 蓝桥杯python基础练习报时助手

    这道题比较简单我们可以直接用字典和if语句来完成 按照题目意思创建一个字典1 20和30 40 50 因为创建全部的字典太麻烦 我们可以将不存在字典的建转化为字典中的建 第二步可以运用if语句进行判断 m 0时直接 输出即可 m h gt

  • centos mail报错：550 Mailbox not found or access denied

    运行了几年的发邮件脚本 最近体发邮件都发生了报错 无法发出 smtp server 550 Mailbox not found or access denied 报错信息提示邮箱找不到 但是接收人邮箱确定没有错误 因为一直正常运行 网上说5

  • 【Unity XR】Unity开发OpenXR

    Unity开发OpenXR 介绍OpenXR相关依赖插件 OpenXR OpenXR Plugin XR Interaction Toolkit XR Plugin Management 安装OpenXR相关依赖插件 Package Man

  • qt MVD 框架入门教学归纳实例：QListView + QAbstractItemModel + QStyledItemDelegate 实现自定义进度条（同时显示文件名 + 实时跟新进度）

    前置理论基础 关于QT的MVD框架这里就不做赘述 通篇介绍的话得占不少版面 其实作为qt开发者 基本上只要有个能跑起来的demo 相关的技术点不难理解 新手学习mvd的难点在于没有一个小型的 直观的demo能直接梳理出三者的关系 关于MVD

  • Ubuntu显示美化 优化 常用插件

    本文不再更新 已迁移到MD文档 参见 Ubuntu显示美化 优化 常用插件 神奏的博客 CSDN博客 1 安装 Extension Manager ubuntu snap商店或者deb商店打开 搜索 Extension Manager 安装

  • vue实现穿梭框功能

  • 路由器的几种模式

    1 AP 无线热点模式 路由器的WAN口接入网线 在其他设备通过路由器的无线连接上网 2 Client 客户端的模式 将无线路由器作为无线网卡来使用 通过无线的方式连接到其他路由上 然后设备通过网线连接上路由器 3 Router 无线路由模

  • Linux的cat命令

    1 cat 显示文件连接文件内容的工具 cat 是一个文本文件查看和连接工具 查看一个文件的内容 用cat比较简单 就是cat 后面直接接文件名 比如 de gt root localhost cat etc fstab de gt 为了便

  • Linux下SVN的安装及SVN常用命令

    SVN的介绍 SVN是一个开源的版本控制系統 svn版本管理工具管理随时间改变的各种数据 这些数据放置在一个中央资料档案库 repository 中 这个档案库很像一个普通的文件服务器 它能记住你每次的修改 查看所有的修改记录 恢复到任何历

  • vue前端项目的结构以及组成部分

    本文结构 在初入前端的时候 一个项目中的文件夹会非常多 与Vue官网的简单demo相差非常大 这也是对前端项目文件组成和几个大的模块的一些介绍 文末还有一些不成文的代码规范 本文目录 项目代码组成 前端项目组成 前端的几大模块 项目编写规范

  • RPC框架的网络线程模型

    一 RPC的网络IO模型 1 连接独占线程或进程 在这个模型中 线程 进程处理来自绑定连接的消息 在连接断开前不退也不做其他事情 当连接数逐渐增多时 线程 进程占用的资源和上下文切换成本会越来越大 性能很差 这就是C10K问题的来源 这种方

  • FOTA升级差分包编译服务器搭建

    奈何公司测试组电脑没有Linux系统 每次测试FOTA升级用的差分包都需要找我来制作 实在麻烦 本想搞个QT界面弄得专业点 后面有时间再去搞吧 现在打算先临时写一个应急 一 Ubuntu端先搭建FTP服务器 参考之前搭建的记录 Ubuntu

  • 【网络】https单向认证和双向认证

    前言 之前面试的时候 面试官问我了解过https的双向认证吗 当时 的确不理解 不过没关系 现在就来补上 正文 1 单向认证 还是有必要先说下单向认证 单向认证是我刚开始接触https的时候就了解到的 下面看一下执行流程图 图是网上找的 再

  • 什么网站适合使用cdn？

    高防cdn的主要功能就是加速和防御 通过建设多个cdn节点来防御各种ddos cc等网络攻击 保证网站的稳定运行 那么高防cdn是如何进行防御的呢 1 高防cdn的防御机制是智能多样的 不是单打独斗类型 起内部的智能机制可以应对各种类型的攻

随机推荐

  • 高阶数据结构之图论

    文章目录 图是什么 图的存储 邻接矩阵 邻接表 无向图邻接表存储 有向图邻接表存储 图的遍历 广度优先遍历 BFS 深度优先遍历 DFS 最小生成树 Prim算法 Kruskal算法 最短路径问题 Dijkstra算法 求单源最短路径 Be

  • C++基础：继承，子类继承父类有规范和要求

    文章目录 1 语法 2 成员的访问权限 3 继承关系的构造顺序 4 同名隐藏 5 多种情况 6 派生对象给基类对象的传递 7 多重继承 8 菱形继承 9 对象构造顺序总结 1 语法 继承关系 A is a B 父类 子类 基类 派生类 继承

  • 【C进阶】指针（二）

    六 函数指针数组 数组是一个存放相同类型数据的存储空间 我们已经学习了指针数组 eg int arr 10 整形指针数组 数组 存放的是整形指针 char arr 5 字符指针数组 数组 存放的是字符指针 那么把函数的地址存到一个数组中 那

  • Laravel 使用数组条件查询时 in和or 的用法

    laravel给出了whereIn的用法 users DB table users gt whereIn id 1 2 3 gt get 或者在闭包中使用whereIn ids 1 2 list User where function qu

  • Kalman滤波——初阶入门

    概要 kalman滤波在机器人控制 数字图像等领域应用非常广泛的一种方法 很多人对其名字不能理解 因为kalman滤波在大多数时候表现出来都是将多个数据进行融合 为什么不叫kalman融合呢 如果你有这个疑问 那就说明你对kalman滤波理

  • matlab变量全局化,matlab全局变量global

    matlab global定义全局变量的问题 我写了matlab的一个主函数 放在一个M文件中 然后在这个主函数中调用其可以 前提是两个函数共用变量均需用global声明 例子 保存f m内容如下 function f a b global

  • Python探索Raspberry Pi机器人平台

    随机轨迹 第一代机器人吸尘器在一个无限循环中使用了一种非常简单的算法 直行直到撞到障碍物 转一个随机角度 如果您担心这种行为的清洁质量 那可能是对的 但是从数学角度来看 如果给定无限的时间 只要机器人可以物理上到达 该算法将覆盖整个清洁区域

  • 安装php7+nginx所遇到的一些问题及解决办法

    1 关于nginx启动出现403 forbidden 403表示请求资源的访问被拒绝 那么有可能你的访问地址就没有这个资源 因此解决办法 缺少索引文件index html inde php 比如下面的配置 server listen 80

  • 冒泡排序和快速排序的效率比较

    快速排序 快速排序是通过一趟排序将要排序的数据分割成独立的两部分 其中一部分的所有数都比另外一部分的所有数都要小 然后再按这个方法对这两部分数据分别进行排序 这里初始化i 1 p 0 r 7 j从0至7 这里有一个循环过程 就是拿序列里面的

  • 携手共进，聚力共赢

    2021年3月17日海伯利安宣布与 香港 国金集团 下称国金集团 有限公司达成全面战略合作协议 进一步深化双方在去中心化地图服务和商业地产行业等领域的战略合作 以引领行业发展为导向 海伯利安致力于深耕区块链底层技术 提供优质的去中心化地理空

  • python进阶（异常处理，文件操作）

    python进阶 异常处理机制 try except try except else 结构 发生异常的执行情况 执行 except 块 没有执行 else try except finally 结构 finally 块无论是否发生异常都会被

  • 顺序栈的初始化、构建、入栈，出栈和取栈顶元素

    一 顺序栈的定义 include

  • LENOVO联想笔记本电脑 拯救者Y520-15IKBN(80Y5)原装Win10系统文件，恢复出厂OEM系统

    lenovo联想笔记本电脑 拯救者Y520 15IKBN 1050 1050Ti 80Y5 出厂状态Windows10系统 原装OEM系统镜像 系统自带所有驱动 出厂主题壁纸LOGO Office办公软件 联想电脑管家等预装程序 所需要工具

  • 安装deepin V20 （1002）时如何添加根分区？

    安装deepin V20 1002 时 选择安装分区时提 发现1个错误 修复后既可以继续安装 需要添加1个根分区才那进行安装 请问 如何添加根分区 把这个ext4作为根分区 鼠标挪到这一行点一下 右侧会出现编辑的图标 可以点击进入编辑分区

  • Linux 信号学习

    Linux 信号学习 信号量的基本概念 信号产生的条件 信号如何被处理 信号的异步特质 信号的分类 可靠信号 不可靠信号 实时信号 非实时信号 常见信号与默认行为 信号处理 signal 函数 sigaction 函数 向进程发送信号 ki

  • 检验IP地址有效性

    使用inet aton函数

  • linux系统转换window系统,Window系统改装为linux系统

    以下以安装Centos6 5为例 1 下载资料 1 1 准备一个U盘 大于8G 1 2 下载U盘启动盘制作工具 UltraISO http qunying jb51 net 81 201311 tools UltraISOPortable

  • 运维笔记-nginx详解

    目录 1 简介 2 正向代理与反向代理 3 nginx的安装部署 基于Centos stream操作系统 4 nginx配置文件详解 5 高效的Web服务器 nginx 5 1nginx服务器基本配置 5 2nginx 基于IP的访问控制

  • springboot常用语法库

    今天与大家分享springboot常用语法库的基本语法 如果有问题 望大家指教 目录 1 freemarker是什么 1 1 优点 2 springboot整合freemarker 2 1 pom xml 2 2 项目配置文件 2 3 Co

  • memory-ordering-at-compile-time

    浅谈Memory Reordering Memory ordering 在我们编写的 C C 代码和它被在 CPU 上运行 按照一些规则 代码的内存交互会被乱序 内存乱序同时由编译器 编译时候 和处理器 运行时 造成 都为了使代码运行的更快

热门标签