wngtk
commented
1 year ago Chapter 26
关键问题：如何实现同步 为了构建有用的同步原语，需要从硬件中获得哪些支持？需要从操作系统中获得什么支持？如何正确有效地构建这些原语？程序如何使用它们来获得期望的结果？
常见的线程之间的交互：
- 访问共享变量
- 一个线程在继续之前必须等待另一个线程完成某些操作
我们不仅要研究如何构建对同步原语的支持来支持原子性，还要研究支持在多线程程序中常见的睡眠/唤醒交互的机制。
操作系统是第一个并发程序。
Chapter 28 锁
锁在代码里面就是一个变量。这个锁变量（简称锁）保存了锁在某一时刻的状态。它要么是可用的（available，或unlocked，或free），要么是被占用的（acquired，或 locked，或 held），表示有一个线程持有锁，正处于临界区。
锁为程序员提供了最小程度的调度控制。我们把线程视为程序员创建的实体，但是被操作系统调度，具体方式由操作系统选择。锁让程序员获得一些控制权。通过给临界区加 锁，可以保证临界区内只有一个线程活跃。锁将原本由操作系统调度的混乱状态变得更为可控。
POSIX 库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。
关键问题：怎样实现一个锁 如何构建一个高效的锁？高效的锁能够以低成本提供互斥，同时能够实现一些特性，我们下面会讨论。需要什么硬件支持？什么操作系统支持？
PETERSON 算法，是实现互斥的一种算法。
- 假设 load 和 store 是原子的
下面是 OSTEP 书上的 Peterson 算法示例，思路很清晰但是这不是一个在今天的计算机上可以正确运行的 C 语言实现的 Peterson 算法。
int flag[2]; int turn;
void init() { flag[0] = flag[1] = 0; // 1->thread wants to grab lock turn = 0; // whose turn? (thread 0 or 1?) }
void lock() { flag[self] = 1; // self: thread ID of caller turn = 1 - self; // make it other thread's turn while ((flag[1-self] == 1) && (turn == 1 - self)) ; // spin-wait }
void unlock() { flag[self] = 0; // simply undo your intent }
假设有两个线程，用 Peterson 算法（基本假设是 load 和 store 是原子的）实现两个线程之间的互斥。flag[self] 表示当前线程是否想要获得锁。0 表示线程 0，1 表示线程 1。首先两个线程都企图获得锁，也就是把旗子举起来，两个线程都把旗子举起来，然后尝试改变共享的变量 turn。谁抢先改变 turn，谁就获得锁。因为后改变 turn 的会使得 turn 是对方，所以谁快谁有。
对方的:triangular_flag_on_post:是举起来的，并且是轮到对方了，lock()就会自旋等待。当对方的旗子放下来了，就不自旋了。
一段时间以来，出于某种原因，大家都热衷于研究不依赖硬件支持的锁机制。后来这些工作都没有太多意义，因为只需要很少的硬件支持，实现锁就会容易很多（实际在多处理器的早期，就有这些硬件支持）。而且上面提到的方法无法运行在现代硬件（因为松散内存一致性模型），导致它们更加没有用处。 更多的相关研究也湮没在历史中……
松散内存一致性模型，导致的问题是当前 CPU 的写内存操作对于其他 CPU 来说不一定是同时可见的，x86 是写回内存后其他 CPU 同时可见的。ARM 是松散内存一致性模型。
- Compiler Barrier 保障指令访存的读写不能跨过这个屏障
- Memory Barrier 保证屏障之前的写操作对于屏障后面的读操作都是可见的
> A memory barrier is implemented in hardware, and stops the CPU itself from reordering the instructions. However, a compiler-only fence stops the compiler's optimizer from reordering instructions, but the CPU can still reorder them.
编译器提供的 `__sync_synchronize()`函数可以用来添加非常强的 Memory Barrier，是硬件级别的 memory barrier[^1]。
相当于:
```c
asm volatile ("mfence":::"memory")而普通的 memory barrier/compiler barrier 就只是
tell the compiler not to move loads or stores beyond this point (in any direction) as part of its optimizations. These barriers prevent a compiler from reordering instructions, they do not prevent reordering by CPU.
锁的实现需要 CPU 提供一点点的支持。
OSTEP^ostep是一本免费的操作系统教材，围绕着操作系统三个基础的概念展开：虚拟化，并发和持久性。
Thanks CSAPP, jyy OS, OSTEP for providing good information. I am not an experter just a beginner.