高并发之CAS自顶向下

操作系统内核 Comments

高并发之CAS自顶向下

Wirte by 021.

机器级代码

计算机系统使用了多种不同形式的抽象，可以通过一个简单的抽象模型来隐藏实现细节。对于机器级别的程序来说，有两点非常重要。

首先第一点，定义机器级别程序的格式和行为被称为 指令集体系结构或指令集架构(instruction set architecture)， ISA。ISA 定义了进程状态、指令的格式和每一个指令对状态的影响。大部分的指令集架构包括 ISA 用来描述进程的行为就好像是顺序执行的，一条指令执行结束后，另外一条指令再开始。处理器硬件的描述要更复杂，它可以同时并行执行许多指令，但是它采用了安全措施来确保整体行为与 ISA 规定的顺序一致。

第二点，机器级别对内存地址的描述就是 虚拟地址(virtual address)，它提供了一个内存模型来表示一个巨大的字节数组。

编译器在整个编译的过程中起到了至关重要的作用，把 C 语言转换为处理器执行的基本指令。汇编代码非常接近于机器代码，只不过与二进制机器代码相比，汇编代码的可读性更强，所以理解汇编是理解机器工作的第一步。

一些进程状态对机器可见，但是 C 语言程序员却看不到这些，包括

  • 程序计数器(Program counter)，它存储下一条指令的地址，在 x86-64 架构中用 %rip 来表示。

程序执行时，PC 的初始值为程序第一条指令的地址，在顺序执行程序时， CPU 首先按程序计数器所指出的指令地址从内存中取出一条指令，然后分析和执行该指令，同时将 PC 的值加 1 并指向下一条要执行的指令。

比如下面一个例子。

这是一段数值进行相加的操作，程序启动，在经过编译解析后会由操作系统把硬盘中的程序复制到内存中，示例中的程序是将 123 和 456 执行相加操作，并将结果输出到显示器上。由于使用机器语言难以描述，所以这是经过翻译后的结果，实际上每个指令和数据都可能分布在不同的地址上，但为了方便说明，把组成一条指令的内存和数据放在了一个内存地址上。

image-20211110162521277

  • 整数寄存器文件(register file)包含 16 个命名的位置，用来存储 64 位的值。这些寄存器可以存储地址和整型数据。有些寄存器用于跟踪程序状态，而另一些寄存器用于保存临时数据，例如过程的参数和局部变量，以及函数要返回的值。这个 文件 是和磁盘文件无关的，它只是 CPU 内部的一块高速存储单元。有专用的寄存器，也有通用的寄存器用来存储操作数。

  • 条件码寄存器 用来保存有关最近执行的算术或逻辑指令的状态信息。这些用于实现控件或数据流中的条件更改，例如实现 if 和 while 语句所需的条件更改。我们都学过高级语言，高级语言中的条件控制流程主要分为三种：顺序执行、条件分支、循环判断三种，顺序执行是按照地址的内容顺序的执行指令。条件分支是根据条件执行任意地址的指令。循环是重复执行同一地址的指令。

    • 顺序执行的情况比较简单，每执行一条指令程序计数器的值就是 + 1。
    • 条件和循环分支会使程序计数器的值指向任意的地址，这样一来，程序便可以返回到上一个地址来重复执行同一个指令，或者跳转到任意指令。

下面以条件分支为例来说明程序的执行过程（循环也很相似）

程序的开始过程和顺序流程是一样的，CPU 从 0100 处开始执行命令，在 0100 和 0101 都是顺序执行，PC 的值顺序+1，执行到 0102 地址的指令时，判断 0106 寄存器的数值大于 0，跳转（jump）到 0104 地址的指令，将数值输出到显示器中，然后结束程序，0103 的指令被跳过了，这就和我们程序中的 if() 判断是一样的，在不满足条件的情况下，指令会直接跳过。所以 PC 的执行过程也就没有直接+1，而是下一条指令的地址。

image-20211110162801553

  • 一组 向量寄存器用来存储一个或者多个整数或者浮点数值，向量寄存器是对一维数据上进行操作。

机器指令只会执行非常简单的操作，例如将存放在寄存器的两个数进行相加，把数据从内存转移到寄存器中或者是条件分支转移到新的指令地址。编译器必须生成此类指令的序列，以实现程序构造，例如算术表达式求值，循环或过程调用和返回

认识汇编

我相信各位应该都知道汇编语言的出现背景吧，那就是二进制表示数据，太复杂太庞大了，为了解决这个问题，出现了汇编语言，汇编语言和机器指令的区别就在于表示方法上，汇编使用操作数来表示，机器指令使用二进制来表示，我之前多次提到机器码就是汇编，你也不能说我错，但是不准确。

但是汇编适合二进制代码存在转换关系的。

汇编代码需要经过 汇编器 编译后才产生二进制代码，这个二进制代码就是目标代码，然后由链接器将其连接起来运行。

汇编语言主要分为以下三类

  • 汇编指令：它是一种机器码的助记符，它有对应的机器码
  • 伪指令：没有对应的机器码，由编译器执行，计算机并不执行
  • 其他符号，比如 +、-、*、/ 等，由编译器识别，没有对应的机器码

汇编语言的核心是汇编指令，而我们对汇编的探讨也是基于汇编指令展开的。

与汇编有关的硬件和概念

CPU

CPU 是计算机的大脑，它也是整个计算机的核心，它也是执行汇编语言的硬件，CPU 的内部包含有寄存器，而寄存器是用于存储指令和数据的，汇编语言的本质也就是 CPU 内部操作数所执行的一系列计算。

内存

没有内存，计算机就像是一个没有记忆的人类，只会永无休止的重复性劳动。CPU 所需的指令和数据都由内存来提供，CPU 指令经由内存提供，经过一系列计算后再输出到内存。

磁盘

磁盘也是一种存储设备，它和内存的最大区别在于永久存储，程序需要在内存装载后才能运行，而提供给内存的程序都是由磁盘存储的。

总线

一般来说，内存内部会划分多个存储单元，存储单元用来存储指令和数据，就像是房子一样，存储单元就是房子的门牌号。而 CPU 与内存之间的交互是通过地址总线来进行的，总线从逻辑上分为三种

  • 地址线
  • 数据线
  • 控制线

image-20211110162824440

CPU 与存储器之间的读写主要经过以下几步

读操作步骤

  • CPU 通过地址线发出需要读取指令的位置
  • CPU 通过控制线发出读指令
  • 内存把数据放在数据线上返回给 CPU

写操作步骤

  • CPU 通过地址线发出需要写出指令的位置
  • CPU 通过控制线发出写指令
  • CPU 把数据通过数据线写入内存

下面我们就来具体了解一下这三类总线

地址总线

通过我们上面的探讨，我们知道 CPU 通过地址总线来指定存储位置的，地址总线上能传送多少不同的信息，CPU 就可以对多少个存储单元进行寻址。

image-20211110162852156

上图中 CPU 和内存中间信息交换通过了 10 条地址总线，每一条线能够传递的数据都是 0 或 1 ，所以上图一次 CPU 和内存传递的数据是 2 的十次方。

所以，如果 CPU 有 N 条地址总线，那么可以说这个地址总线的宽度是 N 。这样 CPU 可以寻找 2 的 N 次方个内存单元。

数据总线

CPU 与内存或其他部件之间的数据传送是由数据总线来完成的。数据总线的宽度决定了 CPU 和外界的数据传输速度。8 根数据总线可以一次传送一个 8 位二进制数据（即一个字节）。16 根数据总线一次可以传输两个字节，32 根数据总线可以一次传输四个字节。。。。。。

控制总线

CPU 与其他部件之间的控制是通过 控制总线 来完成的。有多少根控制总线，就意味着 CPU 提供了对外部器件的多少种控制。所以，控制总线的宽度决定了 CPU 对外部部件的控制能力。

一次内存的读取过程

内存结构

image-20211110162906306

内存 IC 是一个完整的结构，它内部也有电源、地址信号、数据信号、控制信号和用于寻址的 IC 引脚来进行数据的读写。下面是一个虚拟的 IC 引脚示意图

图中 VCC 和 GND 表示电源，A0 - A9 是地址信号的引脚，D0 - D7 表示的是控制信号、RD 和 WR 都是好控制信号，我用不同的颜色进行了区分，将电源连接到 VCC 和 GND 后，就可以对其他引脚传递 0 和 1 的信号，大多数情况下，**+5V** 表示1，****0V 表示 0。

我们都知道内存是用来存储数据，那么这个内存 IC 中能存储多少数据呢？D0 - D7 表示的是数据信号，也就是说，一次可以输入输出 8 bit = 1 byte 的数据。A0 - A9 是地址信号共十个，表示可以指定 00000 00000 - 11111 11111 共 2 的 10次方 = 1024个地址。每个地址都会存放 1 byte 的数据，因此我们可以得出内存 IC 的容量就是 1 KB。

如果我们使用的是 512 MB 的内存，这就相当于是 512000（512 * 1000） 个内存 IC。当然，一台计算机不太可能有这么多个内存 IC ，然而，通常情况下，一个内存 IC 会有更多的引脚，也就能存储更多数据。

内存读取过程

下面是一次内存的读取过程。

image-20211110162922419

来详细描述一下这个过程，假设我们要向内存 IC 中写入 1byte 的数据的话，它的过程是这样的：

  • 首先给 VCC 接通 +5V 的电源，给 GND 接通 0V 的电源，使用 A0 - A9 来指定数据的存储场所，然后再把数据的值输入给 D0 - D7 的数据信号，并把 WR（write）的值置为 1，执行完这些操作后，即可以向内存 IC 写入数据

  • 读出数据时，只需要通过 A0 - A9 的地址信号指定数据的存储场所，然后再将 RD 的值置为 1 即可。

  • 图中的 RD 和 WR 又被称为控制信号。其中当WR 和 RD 都为 0 时，无法进行写入和读取操作。

CAS原子性操作之汇编

自旋锁本质

  • 模拟临界区

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //设置全局变量
    flag = 0;

    Lab:
    	mov eax,1; 
    	lock xadd [flag],eax;   //先交换 ，flag = 1,eax =0; 再相加 - flag = flag+eax = 1; eax =0; 
    	cmp eax,0;   // 对比eax 是否为0
    	jz endLab    // cmp指令会影响 标志寄存器， jz根据标志寄存的值进行指令跳转.
    	dec [flag]   // eax不为0，证明有未能拿到临界区令牌;
    	//线程等待
    endLab:				
    	ret


  • 自旋锁源码

    image-20211116201638291

  • 伪代码模拟自旋锁

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //取锁
    tryLock(){

    	boolean flag = lock getLock(); //原子操作, 检查锁，并设置标志位；
    	if(!flag){
    		waitiLock();
    	}
    	return flag;
    }

    //自旋等待
    waitiLock(){
    	boolean flag = checkLock(); //检查锁状态 
    	if(flag){
    		tryLock();
    	}
    	sleep(...);
    	waitiLock();
    }

最常见的原子操作有Compare and Exchange,Self Increase/Decrease等等

8086汇编相关指令

  • LOCK:这是一个指令前缀，在所对应的指令操作期间使此指令的目标操作数指定的存储区域锁定，以得到保护。

  • XADD:先交换两个操作数的值，再进行算术加法操作。多处理器安全，在80486及以上CPU中支持。

  • CMPXCHG:比较交换指令，第一操作数先和AL/AX/EAX比较，如果相等ZF置1，第二操作数赋给第一操作数，否则ZF清0，第一操作数赋给AL/AX/EAX。多处理器安全，在80486及以上CPU中支持。

  • XCHG:交换两个操作数,其中至少有一个是寄存器寻址.其他寄存器和标志位不受影响.

原子操作函数

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
long __stdcall **CompareExchange**(long volatile***Destination**,long **Exchange**,long **Comperand**)

{

  __asm

  **{**

   **mov   ecx**, **Destination**;

   **mov   edx**, **Exchange**;

   **mov   eax**, **Comperand**;

   **lock cmpxchg [ecx**], **edx**;

  **}**

}

交换

long __stdcall **Exchange**(long volatile* **Target**,long **Value**)

{

  __asm

  **{**

   **mov   ecx**, **Target**;

   **mov   edx**, **Value**;

**label**:

   **lock cmpxchg [ecx**], **edx**;//加

   **jnz**   short **label**;

  **}**

}

自减

long __stdcall **Decrement**(long volatile* **Addend**)

{

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov   eax**, 0FFFFFFFFh;//-1

   **lock xadd [ecx**], **eax**; //加-1

   **dec   eax**;

  **}**

}

自增

long __stdcall **Increment**(long volatile* **Addend**)

{

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov   eax**, 1;

   **lock xadd [ecx**], **eax**; //加

   **inc   eax**;

  **}**

}

相加后交换

long __stdcall **ExchangeAdd**(long volatile* **Addend**,long **Value**)

{

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov   eax**, **Value**;

   **lock xadd [ecx**], **eax**;

  **}**

}



 

原子操作(2) - 泛型后的原子操作

32位的数据类型有4种,但是上面的只支持long,怎么办?手工hack?太土了,当然是C++的大规模杀伤性武器template了.

同时把几个不跨平台的地方抽出来用macro表示.

目前模板还没有得到concept的支持,所以只能用boost.type_traits低级的手动判断,要求只有32位的整数类型才能实例化这些函数.







\#include

\#include



\#define **CALL_METHOD** __stdcall

\#define **VOLATILE** volatile



template<typename **T**>

**T CALL_METHOD compare_exchange32**(**T VOLATILE*****Destination**,**T exchange32**,**T Comperand**)

{

  **BOOST_STATIC_ASSERT**(sizeof(**T**) == 4 && **boost**::**is_integral**<**T**>::**value**);

  __asm

  **{**

   **mov   ecx**, **Destination**;

   **mov   edx**, **exchange32**;

   **mov   eax**, **Comperand**;

   **lock cmpxchg [ecx**], **edx**;

  **}**

}









template<typename **T**>

**T CALL_METHOD exchange32**(**T VOLATILE*** **Target**,**T Value**)

{

  **BOOST_STATIC_ASSERT**(sizeof(**T**) == 4 && **boost**::**is_integral**<**T**>::**value**);

  __asm

  **{**

   //   mov  ecx, Target;

   //   mov  edx, Value;   

   //label:

   //   lock  cmpxchg [ecx], edx;//加

   //   jnz  short label;

   **mov   ecx**, **Target**;

   **mov   eax**, **Value**;

   **xchg [ecx**],**eax**;

  **}**

}







template<typename **T**>

**T CALL_METHOD decrement32**(**T VOLATILE*** **Addend**)

{

  **BOOST_STATIC_ASSERT**(sizeof(**T**) == 4 && **boost**::**is_integral**<**T**>::**value**);

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov  eax**, 0FFFFFFFFh;//-1

   **lock xadd [ecx**], **eax**; //加-1

   **dec   eax**;

  **}**

}









template<typename **T**>

**T CALL_METHOD increment32**(**T VOLATILE*** **Addend**)

{

  **BOOST_STATIC_ASSERT**(sizeof(**T**) == 4 && **boost**::**is_integral**<**T**>::**value**);

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov   eax**, 1;

   **lock xadd [ecx**], **eax**; //加

   **inc   eax**;

  **}**

}





template<typename **T**>

**T CALL_METHOD exchange_add32**(**T VOLATILE*** **Addend**,**T Value**)

{

  **BOOST_STATIC_ASSERT**(sizeof(**T**) == 4 && **boost**::**is_integral**<**T**>::**value**);

  __asm

  **{**

   **mov   ecx**, **Addend**;

   **mov   eax**, **Value**;

   **lock xadd [ecx**], **eax**;

  **}**

}

010101 Decimal is 21, so call me 021(zero to one)Web Developer

记录点滴生活。