1. 线程

<aside> 📖 Definition

Concurrent: existing, happening, or done at the same time.

In computer science, concurrency refers to the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome. (Wikipedia)

操作系统是最早的并发程序之一

</aside>

并发的基本单位，是共享内存的多个执行流

简单理解：“同时执行”的函数

<aside> 📖 线程间共享

完整的地址空间 (所有数据，包括代码) 所有指令取指、执行都作用在同一个地址空间

</aside>

<aside> 📖 线程独立拥有

寄存器 (为什么？) 堆栈 (地址空间都共享了，堆栈如何独立？)

</aside>

2. 原子性的丧失

“程序 (甚至是一条指令) 独占处理器执行” 的基本假设在现代多处理器系统上不再成立。

<aside> 📖 原子性

一段代码执行 (例如 pay()) 独占整个计算机系统

• 单处理器多线程
  • 线程在运行时可能被中断，切换到另一个线程执行
• 多处理器多线程
  • 线程根本就是并行执行的 </aside>

实现原子性

lock(&lk)
unlock(&lk)

• 实现临界区 (critical section) 之间的绝对串行化
• 程序的其他部分依然可以并行执行

<aside> 📖 99% 的并发问题都可以用一个队列解决

$$ Tn<T_{\infty}+\frac{T_1}{n} $$

• 把大任务切分成可以并行的小任务
• worker thread 去锁保护的队列里取任务
• 除去不可并行的部分，剩下的部分可以获得线性的加速 </aside>

3. 顺序的丧失

编译器对内存访问 “eventually consistent” 的处理导致共享内存作为线程同步工具的失效。

// Before being optimized
extern int done

void join() {
	while (!done) ;
}

// After being optimized
extern int done

while (!done)
	if (!done) while(1)

<aside> 📖 实现源代码的按顺序翻译

• 加入Compiler-barrier: asm volatile("":::"memory");
• 设置volatile变量 </aside>

4. 可预见性的丧失

满足单处理器 eventual memory consistency 的执行，在多处理器上可能无法序列化！