[Day 3] Atomic Operation

前言

昨天简单猜测了非同步框架所应具备的基本功能 ( 某种资料模式, thread schedule ), 可以发现 Multi-threading data structure 在非同步框架中是必须的存在, 所以为了之後可以看懂原始码, 会花几天简单说说一些常见的 concurrency 观念 , 帮助我们了解之後遇到的 Multi-threading data structure 。

atomic operation 可以说是用来理解底层同步机制的基石, 就现实面来说在之後阅读原始码的过程会大量的遇到基於原子操作的 CAS 演算法, 而且就我目前的观察, 大多数同步机制的实践会使用 lock-free 演算法, 基於上述原因, 我会用尽可能地把之後可能会用到的 atomic 操作相关观念阐述於这几天的文章。 因为这部分的教学网路上蛮多的, 但不提一下我又怕没人要看我写的文, 所以我会尽可能简单带过。

定义 atomic operation 原子操作

指不会被执行绪调度机制打断的操作,这种操作一旦开始,就一直运行到结束,中间过程可以假设为没有其它 thread 会与其交互

因此利用原子操作可以回避掉,race condition , transaction 等资料错误顺序存取的问题

同步(asynchronous)与并行(concurrency)

关於 thread 的意义可以参考我以前文章中提到的举例

C# Task 十分钟轻松学同步非同步 - iT 邦帮忙::一起帮忙解决难题,拯救 IT 人的一天

实际上有许多定义, 但基於篇幅以下仅阐述其中一种

  1. concurrency ⇒ 探讨多执行绪彼此如何互动, 才能在保有正确性, 稳定性, 与速度的条件下提高软件 throughput
  2. asynchronous ⇒ 当占用 processor 的 thread 闲置(正在I/O) 时切换到另一条 thread , 藉由不使 processor 闲置来达到提高 throughput 的目的

藉由上面的定义我们可以了解到, asynchronous 是实践 concurrency 的方法之一, 也因此在探讨 asynchronous 的过程没有办法回避去了解 concurrency 相关议题。

Race condition

Race condition - Wikipedia

Race condition 是 concurrency programming 一定会遇到的问题, 主要问题点在於, 当有多条 thread 在面对同一个 storage 交叉运作时, 有可能因为错误的资料取用顺序导致错误结果。

以下用图片简略说明 :

当两条 thread 同时取用了变数且其值为 0 , 两条 thread 各自对 0 加一後存回, 使用者以为变数应该是2, 但其实因为做了两次 0 加 1 , 所以最终的结果是 1。

https://ithelp.ithome.com.tw/upload/images/20210903/20131164XIGXC7RCOX.png

以下程序码为两条 thread 各把一个变数加 5000 , 最终结果应该是 10000 , 但会因为 Race condition 导致得不到 10000 这个结果。

#include <iostream>
#include <thread>

using namespace std;

void plusOne(int* count) {
	for (int i = 0; i < 5000; i++) {
		int newCount = *count;
		newCount++;
		*count = newCount;
	}
}

int main() {
	int count = 0;
	thread ThreadA = thread(plusOne, &count);
	thread ThreadB = thread(plusOne, &count);
	ThreadA.join();
	ThreadB.join();

	cout << &count << " : " << count << endl;
}

lock and atomic

为了解决 Race condition 所以必须由 OS 或 hardware 提供某种机制来限制 thread 切换的自由度。

而用来限制 thread 自由度的方法被称作 "同步机制" , 因为其目的是强迫 processor 在某些段落或某句指令仅能同步运行( 不可以切换成别的 thread ) , 同步机制的模型被广泛的使用在应用端的语言, 例如 JS 中就是利用 await 来限制 thread 停下来等待 IO 回传, 不要创建新的 thread 且切换过去继续走。

同步机制分成以下两种 :

  1. 阻塞式 : 代表是 mutex lock , 要求 thread 在执行某一段程序码 ( critical section ) 时, 别的 thread 不能进入该段。非系列文重点, 此处不详述。
  2. 非处塞式 : atomic operation , 有意思的是, 阻塞式同步机制都可以被 atomic 实践, 以下详述其原理。

atomic operation 的本质是由 CPU 提供的 atomic instruction, 以下这篇文章提到了 ARM CPU 在 atomic operation 的实践方法。

The ARM processor (Thumb-2), part 11: Atomic access and barriers

CPU 提供指令在锁定特定记忆体的同时进行操作, 锁定的作用是检测该记忆体是否被该指令以外的指令操作, 如果有就放弃操作, 如果没有就完成操作。

所以若是用以下流程操作, CPU 可以实践最基本的 atomic operation 。

  1. 锁定特定记忆体且决定操作
  2. 进行操作 ( 过程中发生发生外部指令操作就放弃操作)
  3. 若成功操作就结束, 若放弃操作就返回步骤 1

而前人透过包装上述指令完成了许多 atomic operation , 以下叙述常用的3种 :

  1. atomic_load 取得记忆体且不会被中断
  2. atomic_store 存入记忆体且不会被中断
  3. compare_and_swap 比较两个标的後进行交换且中间不会中断

可以发现即便是现今广泛被使用的原子操作, 其功能都很少, 这是受限於 CPU 提供的 instruction 功能单一, 所以包装出这种层级的 atomic operation 已是极限。

但是单单靠这几句 atomic operation 要写出 concurrency 的 program 是困难的。

所以前人发展了名为 CAS 的 pattern 来使後人可以无脑的利用上面三句 atomic operation 来实践多数"同步机制"所需功能。

明日进度

明天会继续跟大家聊聊 CAS 以及 Lock-Free , 後天应该会利用 CAS 实做简单的 Lock-Free Data structure 来帮助大家厘清概念

明天见 !


<<:  [Day 3] 资料产品第一层 - 原始资料的类型

>>:  Transactions (3-1) - Weak Isolation Levels - Read Committed

JavaScript学习日记 : Day6 - 函数(一)

1.函数的重要性 因为函数是Javascript世界的第一等公民,指的是函数与其他数据类型一样,处於...

Vue.js 从零开始:v-model

表单类型是网页很常见的呈现方式,表单元素有文字框<input>、<textarea...

【Day 30】- 结语 : 从 0 开始的网路爬虫

结语   完成了连续一个月的铁人赛了!当初觉得每天发一篇应该不会太难,甚至还在开赛前屯了四篇,结果事...

第29篇:结合

package com.example.touth; public class listdata ...

#21数据中的机率(2)

tags: tags: 2021IT 对事物运动这种不确定性(随机性)的肚量就是机率论。 假设我的的...