附录B：硬件基础

CPU访问内存takes a long time，要尽可能消除

cycle: the time it takes a processor to fetch and execute a single instruction. 不同年代、不同平台，cycle 相差大。当用cycle 表达时，相对指令代价变化缓慢

when a thread is descheduled, it may resume execution on another processor

interconnect 指CPU与内存间的连接，不管是SMP, 还是NUMA，不能让一个处理器大量占用interconnect 带宽，否则其它处理器get delayed

word 的大小与平台相关，一般 32b or 64b

L1 1-2 cycle L2,L3 tens of cycle memory hundreds of cycles 当replacement policy 允许替换任何cache line时，称为fully associative；只能换一对一的那个line时，为direct-mapped 从大小 K 的set 中选一个替换为 k-way set associative

cache coherence

一个处理器在写了另一个处理器cached 的数据，造成另一个处理器的cache 失效，这种问题叫做cache coherence . 有很多复杂聪明的cache coherence protocol 解决这问题。一个常用的是 MESI protocol (Fig B.5 ， PPT好图）

避免false sharing 的方法

独立访问的objects, fields 应该对齐，padded，这样它们能放在不同的cache line里
让只读的数据与频繁修改的数据分开存放在单独的cache line
如果可能的话，把object 拆成 thread-local
如果锁保护被频繁修改的数据，让锁和数据在不同的cache line，这样尝试获取锁的线程不会干扰持有者对数据的访问 ?? (thread A 在访问数据，thread B 申请锁，如果锁和数据在同一cache line，则thread B 把数据也加载进去了，但是这很可能是失效的数据，也就相当于B 做了无用功，能这么理解吗？）
竞争不太大的数据，可以让数据和锁在一个cache line，这样获取锁的同时就可加载数据到cache

different architecures provide different guarantees about the extent to which memory reads and writes can be reordered memory barrier 经常由原子方法自动插入，在非 CS 区时要显式地使用；代价高，几百cycle 要显式地用，不能依赖于平台相关的保证

baiwfg2 commented 2 years ago

3.8 progress conditions

wait-free: if every call finishes its execution in a finite number of steps. 如果一个对象的所有方法都是wait-free，则称此对象是wait-free

lock-free : wait-free 会很不高效，有时候我们只需要一个 weaker progress guarantee. 执行此方法可以保证某个调用可以在有限步内完成

lock-free 保证了最小的progress，因为执行lock-free method可以保证系统作为整体是在前进的（但不保证所有线程都在前进），但wait-free 就保证所有线程都在前进。因为在lock-free 算法中有些线程可能会 starve，但是可能性很小，所以一个快的lock-free算法比一个慢的wait-free 要好。

不依赖于底层OS提供的能力，这样的progress conditions称为 independent prorgress condition

starvation-free, deadlock-free 是属于 blocking progress condition，因为它们允许阻塞式实现

如果抢占(preemption) 关键区很少见，则blocking progress conditions 可能和nonblocking counterparts 难以区分的，但是抢占若很常见，考虑使用nonblocking progress conditions

为并发对象实现挑选progress condition 依赖于应用需要和底层平台的特点。

第3章总结：选择什么样的correctness condition 和progress condition都依赖于应用需要。一个对象的不同方法可以有不同的progress guarantees. 程序员都希望有linearizable 硬件和软件和良好性能，但是没有完美的技术

baiwfg2 commented 2 years ago

7 spin locks

在这么多处理器上，写共享内存会放在write buffer(store buffer）,当需要时才写到内存

barrier 和fence 是一回事，在哪里放置barrier 是程序员的责任 memory barriers are expensive

rule of thumb: 被并发访问的成员，如果不在CS中，得用volatile 声明。否则reads可能读到 stale 值，writes可能被推迟

test-and-set locks

乍眼看，test-and-set lock非常适合用来做spin lock

fig 7.4 中，为何TASLock, 与 TTASLock 性能相差那么大？

Moden multiprocessors have a variety of architectures, so we must be careful about overgeneralizing

when accessing a memory location, a processor first checks whether its cache has a copy of that location. If it is writing the location, the copy must be exclusive. If the cache has the location's current data, then we say that processor hits in its cache. In this case, the processor may read or write the copy in its cache immediately. Otherwiese, the processor has a cache miss, and its requests a copy by broadcasting the address of the location on the bus. The other processors (and the memory controllers) snoop on the bus.

因为getAndSet 会写地址，因此会申请exclusive，导致其它core cached copy失效，几乎所有的getAndSet 都会cache miss 而TTASLock 算法刚开始只是在 while (read lock); ，并没有bus traffic

local spinning，线程在本地不断spin，而不是占用bus，这是一个对spinlock 设计非常重要的原则

exponential back-off

即使是TTASLock，在一线程释放锁后，一瞬间会有大量waiting threads 争抢锁，导致storm of bus traffic 怎样挑选back off time ? 经验法则是：不成功的次数越多，竞争越大，需要back off的时间就越长。因此每个线程在获取锁失败后，将back-off time翻倍，直到一个固定最大值

经验表明，MIN_DELAY, MAX_DELAY 不太好设置，依赖于arch(处理器个数，速度），所以backoff 方式难以跨平台使用另外，BackoffLock 可能是不公平的，使得某个线程不断地获取锁（好处是它cache 一直hit)