多极缓存
- 每个核心有自己的私有高 速缓存（L1 Cache）
- 多个核心共享一个二级高 速缓存（L2 Cache）
- 所有核心共享一个最末级 高速缓存（LLC）
由于不同核心均拥有私有的高速缓存（如一级缓存），某一地址上的数据可能同时存在于多个核心的一级缓存中。当这些核心同时使用写回策略修改该地址的数据时，会导致不同核心上一级缓存中该地址数据不一致，违反了共享内存的抽象。为了保证私有缓存之间也能就某一地址的值达成共识，多核硬件提供了缓存一致性协议（Cache Coherence Protocol）。
缓存一致性是由硬件保证的
属于目录式缓存一致性协议
状态
-
独占修改
当前缓存行在全局只有本地高速缓存中这一份拷贝
可以直接进行读/写操作，不会触发缓存行的状态变化
-
共享
当前缓存行在全局可能存在多份拷贝，且本地的拷贝是有效的
因此当前核心可以直接读该缓存行
如果需要写该缓存行：
1. 则当前核心需要<u>查找全局共享目录</u>
2. 找到所有拥有该缓存行拷贝的核心，并通知这些核心将缓存行状态转换为<u>失效</u>
3. 再设置目录中该项的<u>Dirty Bit</u> 为1，更新拥有者的Bit Vector
4. 最后，将本地的缓存行状态转换为独占修改，方能对缓存行进行写操作
- 失效
这个状态代表当前缓存行本地的拷贝失效
当前核心不能直接读/写该缓存行。
如果需要读缓存行：
- 则应当在目录找到拥有该缓存行的核心，向其索要该缓存行的数据
- 同时通知该核心将该缓存行状态改为共享
- 之后更新目录中的Dirty Bit 为0，并更新拥有者的Bit Vector
- 在本核心中将拿到的缓存行设置为共享之后，方能读取该缓存行
如果需要写该缓存行：
- 则需要通过目录找到所有拥有缓存行的核心，通知它们将该缓存行状态都改为失效，之后才能拿到该缓存行的数据
- 更新目录中的状态
- 最后，将本地的缓存行状态设置为独占修改后，方能写该缓存行
例子
void back_off(int time) {
for (volatile int i=0; i<time; i++)
cpu_relax();
}
void lock(int *lock) {
while(atomic_CAS(lock, 0, 1) != 0)
back_off(DEFAULT_TIME);
}治标不治本
核心思路：在关键路径上避免对单一缓存行的高度竞争
1 void *XCHG(void **addr, void *new_value)
2 {
3 void *tmp = *addr;
4 *addr = new_value;
5 return tmp;
6 }将addr地址上的值修改为新值new_value 并返回该地址上原来的值。
struct MCS_node {
2 volatile int flag;
3 volatile struct MCS_node *next;
4 } __attribute__((aligned(CACHELINE_SZ)));
5
6struct MCS_lock {
7 struct MCS_node *tail;
8 };
9
10 void lock(struct MCS_lock *lock, struct MCS_node *me)
11 {
12 struct MCS_node *tail = 0;
13 me->next = NULL;
14 me->flag = WAITING;
15 tail = atomic_XCHG(&lock->tail, me);
16 if (tail) {
17 tail->next = me;
18 while (me->flag != GRANTED)
19 ;
20 }
21 }
22
23 void unlock(struct MCS_lock *lock,
24 struct MCS_node *me)
25 {
26 if (!me->next) {
27 if (atomic_CAS(&lock->tail, me, 0) == me)
28 return;
29 while (!me->next)
30 ;
31 }
32 me->next->flag = GRANTED;
33 }拿锁
- 当一个线程调用lock尝试获取MCS 锁时，其先初始化自己的等待队列节点
- 其后，该线程利用atomic_XCHG操作将队尾指针lock-tail交换为指向自己的指针
- 并将原来的队尾指针的值存入tail
- 若原来的指针为空，代表该锁为空闲状态，此时该线程可以直接进入临界区执行
- 否则，该线程将链入自己的节点，并等待在自己的MCS节点上
放锁
- 先检查等待队列中是否还有其他线程等待在该锁上
- 如果有其他线程等待，则依照链表顺序，通过修改后序等待者节点中的标记位为GRANTED来通知该节点进入临界区
- 若当前线程已经是等待队列里的最后一个，该线程则需要原子地将等待队列的队尾指针置为空，表示该锁已经释放
- 如果原子操作失败，说明此时有新的线程已经交换了队尾指针，该线程需要等待新竞争者链入 并将锁传递给新的线程
例子
为何这样设计能够为MCS 锁带来更好的可扩展性
如果一个锁要具有良好的可扩展性，锁竞争的开销（如缓存行失效的次数）不应随着同一 时刻竞争者数量增多而加大。
在自旋锁中，随着竞争者数量增多，单一缓存行的竞争加剧，最终导致关键路径上平均每次获取锁造成的缓存失效数量急剧上升。
而对MCS 锁而言，当同一时刻竞争者数量增多时，理想情况下关键路径上锁传递都只涉及两次缓存失效：分别为被继任者修改的me->next所在缓存行与继任者初始化的me->next->flag所在缓存行。
自旋锁获取锁与释放锁所需的操作均非常精简，在只有少数核心竞争时，其性能较MCS 锁更好。因此这两个锁并不存在好坏之分，需要依据具体场景下的竞争程度来判断到底选用哪一种锁
-
多个核心对于同一缓存行的高频修改将会导致严重的性能开销
- 当多个核心需要修改同一缓存行时，需要缓存一致性协议来保证一致性。由于 缓存一致性协议同一时刻只允许一个核心独占修改该缓存行，会造成多核执行流串行化，无法充分发挥出多核的性能优势
- 多个核心对于同一缓存行的高频修改还会导致高速互联总线中产生大量缓存一致性流量，从而造成性能瓶颈
-
伪共享
伪共享是指本身无需在多核之间共享的内容被错误地划分到同一个缓存行中，并引 起了多核环境下对于单一缓存行的竞争，从而导致无谓的性能开销
如在软件中直接使用整型数组（如int cnt[CORE_NUM]）为每个核心提供一个独占的计数器，线程按照所在核心更新这些计数器。由于不同核心将更新不同的计数器，这些计数器本身不是共享的。但如果直接分配一个整型数组，这些计数器很可能落入到同一个缓存行中
-
多核环境下局部性同样重要
处理器中核心数量增多以及多处理器系统的出现 -> 单一的内存控制器逐渐成为了性能瓶颈 -> 多个内存控制器分布在不同的核心或处理器上 -> 不同的核心有可以快速访问的本地内存，其也可以访问其他处理器上的远程内存
- 一个节点中的任意核心能够快速地访问本地的内存。一旦其需要访问远端其他节点的内存时，其需要通过互联总线（Interconnect）与远端节点通讯
- NUMA 架构有多种组成方式，一个NUMA 节点可以是一个物理处理器，也可以是处理器中一部分核心
- 由于节点数量众多，有些节点之间没有直接相连，请求需要通过两跳才能到达目标节点
- 如果应用所用内存随机分布在不同节点上，与只访问本地内存的应用相比，该应用将面临严重的远程内存访问开销
- NUMA 架构对于操作系统不是透明的
测试：临界区将访问并修改10个共享缓存行中的数据，而非之前的1 个。另外，测试使用的核心数进一步从32 核扩展至64
现的性能下降主要是由于线程临界区访问了更多的缓存行。当核心数超过16 个核心时，锁的竞争者就可能出现在不同的NUMA 节点。当锁持有者在不同节点上时，临界区内访问的缓存行也需要在不同的NUMA 节点之间迁移，导致巨大的开销。
问题核心：用于增强访存操作的局部性，减少发生跨NUMA 节点的缓存一致性。在保证正确性的同时尽可能保证一段时间内访问都能在本地命中（包括本地的缓存行和内存），从而避免在关键路径上出现太多远程内存访问（包括通过缓存一致性访问在其他节点高速缓存中的缓存行）****
cohort锁核心：在一段时间内限制互斥锁在单个NUMA 节点内部传递，从而在关键路径上剔除耗时的跨节点缓存一致性
设计：采取了两层锁的设计，第一层是唯一的全局锁，第二层是对应每个NUMA 节点的本地锁
当某一个NUMA 节点上的核心持有Cohort 锁时，其需要同时持有全局锁以及本地锁。而当该核心执行解锁操作时，如果本地节点有其他竞争者，则该核心不会释放全局锁，而是释放本地锁并将全局锁的拥有权转给下一个本节点的竞争者，从而保证Cohort 锁在一段时间内在本地的线程之间传递。
- Cohort 锁牺牲了一定的公平性
从操作系统的角度出发，我们如何提供NUMA 感知的能力
首先我们需要为上层应用提供NUMA 感知的内存分配接口，让上层应用显式地指定分配内存所在位置。
其次，对于没有使用这些接口的应用，操作系统需要尽可能地将内存分配在本地，避免远程内存访问。
最后，操作系统调度时需要尽可能避免跨NUMA 节点的线程迁移。
- 只保证了互斥访问，不保证有限等待和空闲让进
- 如果两个线程同时希望进入临界区，且在互相读对方的标记位之前，都已经设置了自己的标记位。此时，两个线程都不能进入临界区，陷入了无限等待。
- 在现代处理器上，由于会出现访存乱序的情况，因此LockOne算法的互斥访问无法保证。
- 假设在线程0 与线程1 中，第2 行的写操作与第3 行的读操作发生了乱序
- 导致检查标记位的操作在自己的写标记全局可见（即对方的读操作可以读到其结果）之前发生
- 此时如果线程0 与线程1 同时申请进入临界区，它们乱序后的读操作可能读到对方的标记位均为false，导致两个线程同时进入临界区，打破了LockOne的互斥访问的保证。
内存一致性模型明确定义了不同核心对于共享内存操作需要遵循的顺序。读写操作之间共有四类先后顺序需要保证，即读操作与读操作的顺序、读操作与写操作的顺序、写操作与读操作的顺序、写操作与写操作的顺序
🔺 有核心对一个地址的任意读操作都能读到这个地址最近一次写的数据
- 有访存操作都是严格按照程序编写的顺序可见
- 所有的线程看到的访存操作顺序都与其发生的时间顺序完全一致
- 在这种模型下实现的LockOne算法一定能保证互斥访问
问题：要求使用全局一致的时钟5 以判定不同核心上执行的访存指令的时间先后顺序，增加了系统的实现难度
例子
🔺 不要求操作按照真实发生的时间顺序（全局时钟）全局可见。首先，不同核心看到的访存操作顺序完全一致，这个顺序称为全局顺序；其次，在这个全局顺序中，每个核心自己的读写操作可见顺序必须与其程序顺序保持一致。
- 此其中的读操作不一定能读到其他核上最新的修改
- 序一致性模型能够保证LockOne算法的互斥访问
例子
🔺 针对不同地址且无依赖的读-读、读-写、写-写顺序都能得到保证，只有写-读的顺序不能够得到保证
- TSO 一致性模型通过加入一个写缓冲区达成优化性能的目的
- 该写缓冲区能够保证写操作按照顺序全局可见
-
现代处理器允许访存操作乱序执行，单核可以通过ROB保证顺序
-
让指令按照程序顺序退役
-
退役对应顺序执行中的执行结束，其意味着该条指令对系统的影响终将全局可见
-
有的指令由于分支预测得到提前执行，但最终分支预测错误时，由于分支判断语句还未退役，这些指令不会提前退役，处理器就可以通过ROB 追踪到这些被错误执行的指令，舍弃
-
只在单核上运行的应用程序并不会受到影响，这些程序展现出的行为与严格按照程序顺序执行的行为相同
但是在多核环境下，由于该系统中其它核心也可以观测到当前核心的运行结果，上述这些措施无法保证被其他核心观测的结果与严格按照程序顺序执行一致。其次，访存指令要完成缓存一致性流程后，才能顺利地被其它核心观测到。因此，如果访存指令等待缓存一致性流程结束后再退役，则会阻塞后续指令进入重排序缓冲区，导致性能受损。
- 处理器在每个核心的存取单元（Load/Store Unit，简称为LSU）中预留了读缓冲区与写缓冲区，这个缓冲区用于暂存还没有满足缓存一致性的访存指令
- 访存指令不再需要等待耗时的缓存一致性流程结束后再退役，而是放入对应的读缓冲区或写缓冲区后，就可以认为该指令已经完成
- 退役只代表该指令一定可以执行，并一定在未来可以被其他核心观测到
- 将一个访存操作完成缓存一致性流程、真正变得全局可见的过程称为提交（Commit）。提交与退役并不相等，一个访存操作需要等到其从重排序缓冲区退役后才会提交
- 写缓冲区用于缓存已经执行结束，但还没有变得全局可见的写操作（包括刚刚将指令提交到LSU，还未通过重排序缓冲区退役的指令；以及已经退役但是还未能变得全局可见的写操作）
- 规定：如果一个写操作满足了缓存一致性条件，真正离开写缓冲区到达L1 cache，则代表该写操作的结果全局可见，称该写操作成功提交
写操作离开写缓冲区需要满足以下几个前提条件：
- 写操作必须要退役。一旦退役，当前核心将会认为这个写指令已经完成，该指令不可撤销
- 所需的缓存一致性流程必须结束
- 架构的写缓冲区按照先入先出的顺序提交写操作。也即一个写操作必须等到前序写操作离开写缓冲区之后才能离开。因此，x86 架构使用的TSO 模型中写写操作之间的顺序能够得到保证
读操作并不存在提交的概念，但仍需要按照先入先出的顺序离开读缓冲区（即退役）
但是，如果某个在读缓冲区中的读操作还未退役，且此时该操作目标缓存行被其他核心修改，其会受到缓存一致性中的“失效”命令影响，舍弃当前读操作读到的结果，重新执行该读操作。所以在TSO 架构中不会出现读读乱序（乱序执行的读操作读到的结果与顺序执行一致，否则会被要求重做）
读操作离开写缓冲区需要满足以下几个前提条件：
- 首先，该读操作需要读取的值必须已经被读取到该核心
- 其次，程序顺序中该操作之前的所有操作必须已经退役
- 最后，读操作从读到值开始到退役之间没有收到目标缓存行“失效”的命令。若在此之间收到了目标缓存行“失效”的命令，则需要重新执行读操作
写写：
正如在介绍写缓冲区时讨论，由于写缓冲区保证了写操作会按照程序顺序提交，因此它们会按程序顺序全局可见，从而保证了写写顺序，即图中STR0与STR1将依照顺序全局可见。 读读：
以代码片段12.1为例，假设乱序执行使得proc_B的读data操作（第13 行，图中LD1）在读flag操作（第11 行，图中LD0）之前发生，且读到的是初始数据0而非proc_A修改的666。而此时如果roc_B读flag操作读到了proc_A修改的READY，那么由于proc_A可以保证写data到写READY的提交顺序（即保证写写的可见顺序），因此此时对data的写操作一定也已经提交完成。而根据缓存一致性协议，此时对于data缓存行的缓存失效通知一定已经到达了proc_B所在核心。由于读缓冲区按程序顺序退役，此时proc_B读flag操作刚刚完成，还未退役，因此读data缓存行操作也没有完成退役。所以，对于data缓存行的缓存失效通知会使得proc_B重做该读操作（图中T2 时刻）， 并读到修改值666。通过以上策略，x86 处理器就实现了对于读读操作的顺序保证。 读写：
在x86 处理器中，保证读写操作的顺序较为简单。由于重排序缓冲区已经保证了所有指令会按照程序顺序退役，而写操作的提交操作一定发生在退役之后，因此当一个写操作全局可见时（即提交），它之前的读操作一定已经完成并退役了（通过ROB 保证，图中T2 时刻）。所以，TSO 架构能保证对于读写操作之间的顺序 写读：
最后对于写读操作，由于当写操作退役时，其值可能还没有变得全局可见（图中T1 时刻，STR0退役但还在写缓冲区中），但若其后续的读操作已经满足了退役的条件，造成读操作在写操作真正变得全局可见之前退役（图中T2 时刻），最终破坏了写读之间的顺序。如果此时有使得读操作目标缓存行失效的命令到达，写读乱序将会被其他核心所观测到。
为了避免写读乱序，x86 处理器提供了mfence指令用于避免写读乱序。在我们上述的这种实现中，可以简单认为mfence指令会阻塞后续指令发送到LSU，直到前序所有访存操作完成。以图12.5中的LockOne算法为例，如果在两个线程的第2-3 行之间添加了mfence指令，读对方flag的操作必须 要等到写自己的flag操作提交之后才能发送到LSU 并执行。因此能够保证LockOne算法的互斥访问。
🔺 弱序一致性模型不保证任何无依赖且针对不同地址的读写操作之间的顺序
写写
在ARM 架构中，写缓冲区中的写操作可以不按照“先入先出”的顺序离开写缓冲区，当对应的写指令退役且目标缓存行缓存一致性流程结束后，该写操作便可以离开写缓冲区，变得全局可见。因此，对于任意的无依赖且针对不同地址的两个写操作，其全局可见的顺序不再受到约束。
读读
ARM 架构下的读操作的退役机制与x86 架构也存在很大差异。
x86 架构下必须等到真正的值读入处理器内部（寄存器）且前序指令退役后才能退役。如果在等待过程中被缓存一致性协议标记为失效，则需要重新执行。因此，x86架构能保证读读的顺序。
在ARM 架构下，处理器可以在确保该读操作一定会发生（如分支预测成功）且前序指令退役时，就将该读操作退役。此时，这个读操作所需要读到的值可能还没有被读到处理器中。所以读操作虽然还是会按照程序顺序退役，但读操作发生的时机可能会违背程序顺序，造成读读乱序。
读写和写读
由于读操作与写操作退役之后都不要求其真正执行完毕（需要读的值到达处理器或写的值全 局可见），因此它们之间真实发生的顺序均没有严格要求，很可能会发生乱序
内存屏障指令
最常用的一类内存屏障指令是dmb，其全称为Data Memory Barrier。dmb指令能够保证其之前的访存指令与其之后的访存指令之间的顺序
请说明为什么自旋锁不适用于单核系统，但在多核系统下可以正常工作？ 对该问题有何种解决方案？
(1).因为等待自旋锁的线程会不断自旋，通常需要其他线程来释放锁。如果只有一个处理器，则该处理器在等待线程耗尽其时间片前无法调度等待线程（如果调度程序不支持抢占式调度，则等待线程将陷入死循环并且永远不会停止）。 在多处理器中时，其他线程可以释放对其他处理器的锁定。
(2).使用条件变量，一旦线程等待锁，它将进入休眠状态，直到锁被其他线程释放为止。
假设有一个包含四个处理器和五个相同资源的系统。 每个处理器在有限的持续时间内最多使用两个资源。 请说明为什么该系统没有死锁（所有处理器最终都将使用两个资源）
(1).我们可以通过矛盾证明。
(2).假设系统死锁。 唯一的情况是，每个进程都持有一个资源，正在等待另一个资源。
(3).由于有四个进程和五个资源，一个进程必须有两个资源。
(4). (2)和(3)有矛盾。(5)Q.E.D.
排号锁可能会导致在高竞争情况下性能降低。下图描述了使用排号锁和MCS锁的open()系统调用的性能。请指出使得排号锁的吞吐量下降的代码行。 另外，MCS锁是如何达到高可扩展性的呢？ （左图为排号锁代码）
(1).while(lock-> owner!=my_ticket)使多个处理器在lock->owner的缓存行上竞争。
(2).MCS锁具有更好的可扩展性，因为使用MCS锁的处理器不需要在同一高速缓存行上争用。
在课程中，我们学习了
NUMA-aware cohort lock。 尽管它可以提高锁在NUMA架构中的性能，但它会引入了公平性问题。请给出对此问题的问题的合理解决方案
每个NUMA节点获得锁后，为其设置一个最大的本地锁转移次数。
假设小明在ARM 处理器上实现自旋锁，并且发现关键部分没有通过锁定得到很好的保护。 在了解了弱顺序一致性后，他知道要在代码中添加内存屏障。 请在适当的位置帮助小明添加barrier()。
void lock(struct spinlock* lock) {
/* locking */
barrier();
}
void unlock(struct spinlock* lock) {
barrier();
/* unlocking */
}