29 内存模型

内存一致性模型（或称 内存模型）规定了共享数据块事件的可能排序，这些事件通过访问由 SharedArrayBuffer 支持的 TypedArray 实例以及调用 Atomics 对象的方法产生。当程序无数据竞争（定义见下）时，事件的排序表现为顺序一致，即各代理动作的交错。当程序存在数据竞争时，共享内存操作可能表现为非顺序一致。例如，程序可能出现因果违反行为和其他令人惊讶的现象。这些惊讶源于编译器变换和 CPU 设计（例如乱序执行与推测执行）。内存模型定义了程序表现顺序一致行为的精确条件，以及数据竞争中可能读取的值。换言之，不存在未定义行为。

内存模型以关系约束形式定义，这些约束作用于在求值过程中由对 SharedArrayBuffer 的抽象操作或 Atomics 对象的方法引入的事件。

Note

本节提供了对 SharedArrayBuffer 抽象操作引入事件的公理化模型。需强调该模型不同于规范其余部分，并非可算法表达。抽象操作非确定性引入事件，是 ECMAScript 求值的操作语义与内存模型公理语义之间的接口。事件语义通过考虑一次求值中所有事件组成的图来定义。它们既非静态语义，也非运行时语义。目前没有演示的算法实现，而是一组约束，用来判定某事件图是否被允许。

29.1 内存模型基础

共享内存访问（读与写）分为两类：原子访问和数据访问（下文定义）。原子访问是顺序一致的，即存在一个所有代理都同意的严格全序。非原子访问在所有代理之间没有严格全序，即无序。

Note 1

不支持比顺序一致更弱、比无序更强的次序（如 release-acquire）。

共享数据块事件 是 ReadSharedMemory、WriteSharedMemory 或 ReadModifyWriteSharedMemory Record。

Table 94: ReadSharedMemory 事件字段
字段名 取值 含义
[[Order]] seq-cst 或 unordered 内存模型对该事件保证的最弱次序。
[[NoTear]] 一个 Boolean 该事件是否允许从多个范围与其相等的写事件读取。
[[Block]] 一个共享数据块 事件操作的块。
[[ByteIndex]] 一个非负整数 在 [[Block]] 中读取的字节地址。
[[ElementSize]] 一个非负整数 读取的大小。
Table 95: WriteSharedMemory 事件字段
字段名 取值 含义
[[Order]] seq-cst、unordered 或 init 内存模型对该事件保证的最弱次序。
[[NoTear]] 一个 Boolean 该事件是否允许被多个范围与其相等的读事件读取。
[[Block]] 一个共享数据块 事件操作的块。
[[ByteIndex]] 一个非负整数 在 [[Block]] 中写入的字节地址。
[[ElementSize]] 一个非负整数 写入的大小。
[[Payload]] 一个字节值的 List 供其他事件读取的字节值列表。
Table 96: ReadModifyWriteSharedMemory 事件字段
字段名 取值 含义
[[Order]] seq-cst 读-改-写事件始终顺序一致。
[[NoTear]] true 读-改-写事件不可撕裂。
[[Block]] 一个共享数据块 事件操作的块。
[[ByteIndex]] 一个非负整数 在 [[Block]] 中读改写的字节地址。
[[ElementSize]] 一个非负整数 读改写的大小。
[[Payload]] 一个字节值的 List 传递给 [[ModifyOp]] 的字节值列表。
[[ModifyOp]] 一个读-改-写修改函数 从读取的字节值 List 与 [[Payload]] 返回修改后字节值 List 的抽象闭包。

这些事件由抽象操作或 Atomics 对象的方法引入。

某些操作还可能引入 Synchronize 事件。一个 Synchronize 事件 没有字段，仅用于直接约束其他事件的允许顺序。

除共享数据块事件与 Synchronize 事件外，还存在宿主特定事件。

令 ReadSharedMemory、WriteSharedMemory 或 ReadModifyWriteSharedMemory 事件的范围为从其 [[ByteIndex]] 到 [[ByteIndex]] + [[ElementSize]] - 1 的连续整数集合。两个事件的范围相等当且仅当它们具有相同 [[Block]] 且范围逐元素相等。若两个事件有相同 [[Block]]、范围不等且交集非空则范围重叠。若两个事件没有相同 [[Block]] 或其范围既不相等也不重叠则范围不相交。

Note 2

应考虑的宿主特定同步事件示例：将一个 SharedArrayBuffer 从一代理发送至另一代理（例如浏览器中的 postMessage），代理的启动与停止，以及通过共享内存之外的通道在代理集群内通信。对于某次执行 execution，这些事件由宿主通过 host-synchronizes-with 严格偏序提供。此外，宿主可以将宿主特定同步事件加入 execution.[[EventList]] 以参与 is-agent-order-before 关系。

候选执行中的事件由下列定义的关系排序。

29.2 代理事件记录

Agent Events Record 是具有以下字段的 Record。

Table 97: Agent Events Record 字段
字段名 取值 含义
[[AgentSignifier]] 一个代理标识符 其求值导致此排序的代理。
[[EventList]] 一个事件的 List 求值过程中事件被追加到该列表。
[[AgentSynchronizesWith]] 一对 Synchronize 事件的 List 由操作语义引入的同步关系。

29.3 选定值记录

Chosen Value Record 是具有以下字段的 Record。

Table 98: Chosen Value Record 字段
字段名 取值 含义
[[Event]] 一个共享数据块事件 为该选定值引入的 ReadSharedMemory 或 ReadModifyWriteSharedMemory 事件。
[[ChosenValue]] 一个字节值的 List 求值过程中非确定性选出的字节。

29.4 候选执行

代理集群求值的一个 candidate execution 是具有以下字段的 Record。

Table 99: Candidate Execution Record 字段
字段名 取值 含义
[[EventsRecords]] Agent Events Record 的 List 映射一个代理到求值过程中追加的事件列表。
[[ChosenValues]] Chosen Value Record 的 List 将 ReadSharedMemory 或 ReadModifyWriteSharedMemory 事件映射为求值过程中选定的字节值列表。

empty candidate execution 是各字段为空 List 的候选执行 Record。

29.5 内存模型的抽象操作

29.5.1 EventSet ( execution )

The abstract operation EventSet takes argument execution (a candidate execution) and returns a Set of events. It performs the following steps when called:

  1. 令 events 为一个空 Set。
  2. 对于 execution.[[EventsRecords]] 中的每个 Agent Events Record aer，执行
    1. 对 aer.[[EventList]] 中的每个事件 E，执行
      1. 将 E 加入 events。
  3. 返回 events。

29.5.2 SharedDataBlockEventSet ( execution )

The abstract operation SharedDataBlockEventSet takes argument execution (a candidate execution) and returns a Set of events. It performs the following steps when called:

  1. 令 events 为一个空 Set。
  2. 对 EventSet(execution) 中的每个事件 E，执行
    1. 如果 E 是 ReadSharedMemory、WriteSharedMemory 或 ReadModifyWriteSharedMemory 事件，将 E 加入 events。
  3. 返回 events。

29.5.3 HostEventSet ( execution )

The abstract operation HostEventSet takes argument execution (a candidate execution) and returns a Set of events. It performs the following steps when called:

  1. 令 events 为一个空 Set。
  2. 对 EventSet(execution) 中的每个事件 E，执行
    1. 如果 E 不在 SharedDataBlockEventSet(execution) 中，将 E 加入 events。
  3. 返回 events。

29.5.4 ComposeWriteEventBytes ( execution, byteIndex, Ws )

The abstract operation ComposeWriteEventBytes takes arguments execution (a candidate execution), byteIndex (a non-negative integer), and Ws (a List of either WriteSharedMemory or ReadModifyWriteSharedMemory events) and returns a List of byte values. It performs the following steps when called:

  1. 令 byteLocation 为 byteIndex。
  2. 令 bytesRead 为一个新的空 List。
  3. 对 Ws 中每个元素 W，执行
    1. 断言：W 的范围包含 byteLocation。
    2. 令 payloadIndex 为 byteLocation - W.[[ByteIndex]]。
    3. 如果 W 是 WriteSharedMemory 事件，则
      1. 令 byte 为 W.[[Payload]][payloadIndex]。
    4. 否则，
      1. 断言：W 是 ReadModifyWriteSharedMemory 事件。
      2. 令 bytes 为 ValueOfReadEvent(execution, W)。
      3. 令 bytesModified 为 W.[[ModifyOp]](bytes, W.[[Payload]])。
      4. 令 byte 为 bytesModified[payloadIndex]。
    5. 将 byte 追加到 bytesRead。
    6. 将 byteLocation 设为 byteLocation + 1。
  4. 返回 bytesRead。
 Note 1

读-改-写修改 [[ModifyOp]] 由 Atomics 对象上引入 ReadModifyWriteSharedMemory 事件的函数属性给出。

 Note 2

此抽象操作将写事件的 List 组合为字节值的 List。用于 ReadSharedMemory 和 ReadModifyWriteSharedMemory 事件的事件语义。

29.5.5 ValueOfReadEvent ( execution, R )

The abstract operation ValueOfReadEvent takes arguments execution (a candidate execution) and R (a ReadSharedMemory or ReadModifyWriteSharedMemory event) and returns a List of byte values. It performs the following steps when called:

  1. 令 Ws 为 reads-bytes-from(R) in execution。
  2. 断言：Ws 是长度等于 R.[[ElementSize]] 的 WriteSharedMemory 或 ReadModifyWriteSharedMemory 事件 List。
  3. 返回 ComposeWriteEventBytes(execution, R.[[ByteIndex]], Ws)。

29.6 候选执行的关系

以下关系与数学函数以特定候选执行为参数，对其事件排序。

29.6.1 is-agent-order-before

对候选执行 execution，其 is-agent-order-before 关系是满足以下条件的事件上的最小关系。

  • 对事件 E 与 D，若存在 execution.[[EventsRecords]] 中的某个 Agent Events Record aer，使得 aer.[[EventList]] 同时包含 E 与 D 且 E 在该 List 顺序上位于 D 之前，则 E 在 execution 中 is-agent-order-before D。
Note

每个代理在求值期间按代理内严格全序引入事件。这些严格全序的并集即本关系。

29.6.2 reads-bytes-from

对候选执行 execution，其 reads-bytes-from 函数是一个数学函数，将 SharedDataBlockEventSet(execution) 中的事件映射到该集合中事件的 List，满足下列条件。

一个候选执行总能容纳一个 reads-bytes-from 函数。

29.6.3 reads-from

对候选执行 execution，其 reads-from 关系是满足以下条件的事件上的最小关系。

29.6.4 host-synchronizes-with

对候选执行 execution，其 host-synchronizes-with 关系是宿主提供的、在宿主特定事件上的严格偏序，至少满足：

Note 1

对候选执行 execution 中两个宿主特定事件 E 与 D，若 E host-synchronizes-with D，则 E happens-before D。

 Note 2

该关系允许宿主提供额外同步机制，如在 HTML workers 间使用 postMessage。

29.6.5 synchronizes-with

对候选执行 execution，其 synchronizes-with 关系是满足以下条件的事件上的最小关系：

  • 对事件 R 与 W，若 R reads-from W in execution、R.[[Order]] 为 seq-cst、W.[[Order]] 为 seq-cst 且 R 与 W 范围相等，则 W synchronizes-with R。
  • 对 execution.[[EventsRecords]] 的每个元素 eventsRecord，以下成立：
    • 若 eventsRecord.[[AgentSynchronizesWith]] 包含 (S, Sw)，则 S synchronizes-with Sw。
  • 对事件 E 与 D，若 execution.[[HostSynchronizesWith]] 包含 (E, D)，则 E synchronizes-with D。
Note 1

按内存模型文献惯例，写事件 synchronizes-with 读事件，而不是反之。

 Note 2

init 事件不参与该关系，而由 happens-before 直接约束。

 Note 3

并非所有通过 reads-from 关联的 seq-cst 事件都由 synchronizes-with 关联，只有范围相等者才关联。

 Note 4

若共享数据块事件 W synchronizes-with R，R 仍可 reads-from 除 W 之外的写。

29.6.6 happens-before

对候选执行 execution，其 happens-before 关系是满足以下条件的事件上的最小关系。

Note

因 happens-before 是 agent-order 的超集，候选执行与 ECMAScript 的单线程求值语义一致。

29.7 合法执行的性质

29.7.1 有效选定读取

候选执行 execution 具有有效选定读取当且仅当以下算法返回 true。

  1. 对 SharedDataBlockEventSet(execution) 中每个 ReadSharedMemory 或 ReadModifyWriteSharedMemory 事件 R，执行
    1. 令 chosenValueRecord 为 execution.[[ChosenValues]] 中 [[Event]] 字段为 R 的元素。
    2. 令 chosenValue 为 chosenValueRecord.[[ChosenValue]]。
    3. 令 readValue 为 ValueOfReadEvent(execution, R)。
    4. 令 chosenLen 为 chosenValue 的元素个数。
    5. 令 readLen 为 readValue 的元素个数。
    6. 如果 chosenLen ≠ readLen，则
      1. 返回 false。
    7. 如果 存在整数 i 属于 [0, chosenLen) 使 chosenValue[i] ≠ readValue[i]，则
      1. 返回 false。
  2. 返回 true。

29.7.2 相干读取

候选执行 execution 具有相干读取当且仅当以下算法返回 true。

  1. 对 SharedDataBlockEventSet(execution) 中每个 ReadSharedMemory 或 ReadModifyWriteSharedMemory 事件 R，执行
    1. 令 Ws 为 reads-bytes-from(R) in execution。
    2. 令 byteLocation 为 R.[[ByteIndex]]。
    3. 对 Ws 中每个元素 W，执行
      1. 如果 R happens-before W，则
        1. 返回 false。
      2. 如果 存在 WriteSharedMemory 或 ReadModifyWriteSharedMemory 事件 V，其范围包含 byteLocation，且 W happens-before V 且 V happens-before R，则
        1. 返回 false。
      3. 将 byteLocation 设为 byteLocation + 1。
  2. 返回 true。

29.7.3 无撕裂读取

候选执行 execution 具有无撕裂读取当且仅当以下算法返回 true。

  1. 对 SharedDataBlockEventSet(execution) 中每个 ReadSharedMemory 或 ReadModifyWriteSharedMemory 事件 R，执行
    1. 如果 R.[[NoTear]] 为 true，则
      1. 断言：R.[[ByteIndex]] 除以 R.[[ElementSize]] 的余数为 0。
      2. 对每个事件 W（满足 R reads-from W 且 W.[[NoTear]] 为 true），执行
        1. 如果 R 与 W 范围相等且存在事件 V 使得 V 与 W 范围相等、V.[[NoTear]] 为 true、W 与 V 非同一共享数据块事件且 R reads-from V，则
          1. 返回 false。
  2. 返回 true。
 Note

事件的 [[NoTear]] 字段为 true 表示该事件通过访问整数 TypedArray 引入；为 false 则表示通过访问浮点 TypedArray 或 DataView 引入。

直观地，该要求表示当内存范围以整数 TypedArray 对齐方式访问时，在与其他范围相等写事件的数据竞争中，必须由“单个”写事件“胜出”。更精确地：对齐的读事件不能读取由多个范围相等写事件的字节混合组成的值。然而对齐读事件仍可能读取来自范围重叠写事件的字节。

29.7.4 顺序一致原子

对候选执行 execution，is-memory-order-before 是 EventSet(execution) 所有事件的严格全序，且满足：

若候选执行存在一个 is-memory-order-before 关系，则其具有顺序一致原子。

Note 3

虽然 is-memory-order-before 包含 EventSet(execution) 的所有事件，但未被 happens-before 或 synchronizes-with 约束的事件可在该顺序中任意位置出现。

29.7.5 合法执行

候选执行 execution 是合法执行（或简称执行）当且仅当以下各项均为真：

  • 宿主为 execution 提供 host-synchronizes-with 关系。
  • execution 存在一个为严格偏序的 happens-before 关系。
  • execution 具有有效选定读取。
  • execution 具有相干读取。
  • execution 具有无撕裂读取。
  • execution 具有顺序一致原子。

所有程序至少有一个合法执行。

29.8 竞争

对执行 execution 及其中 SharedDataBlockEventSet(execution) 的事件 E 与 D，若以下算法返回 true，则 E 与 D 处于一个 race 中。

  1. 如果 E 与 D 不是同一共享数据块事件，则
    1. 如果并非 E happens-before D 且 D happens-before E 同时成立，则
      1. 如果 E 与 D 均为 WriteSharedMemory 或 ReadModifyWriteSharedMemory 事件且范围不相交为假，则
        1. 返回 true。
      2. 如果 E reads-from D 或 D reads-from E，则
        1. 返回 true。
  2. 返回 false。

29.9 数据竞争

对执行 execution 及其中 SharedDataBlockEventSet(execution) 的事件 E 与 D，若以下算法返回 true，则 E 与 D 处于一个 data race 中。

  1. 如果 E 与 D 在 execution 中处于 race，则
    1. 如果 E.[[Order]] 不是 seq-cst 或 D.[[Order]] 不是 seq-cst，则
      1. 返回 true。
    2. 如果 E 与 D 范围重叠，则
      1. 返回 true。
  2. 返回 false。

29.10 数据竞争自由

执行 execution 是 data race free 当且仅当 SharedDataBlockEventSet(execution) 中不存在两事件处于数据竞争。

若程序所有执行均数据竞争自由，则该程序为数据竞争自由程序。

内存模型保证数据竞争自由程序所有事件的顺序一致性。

29.11 共享内存指南

Note 1

以下是面向使用共享内存的 ECMAScript 程序员的指南。

推荐保持程序数据竞争自由，即使同一内存位置不可能同时发生并发非原子操作。数据竞争自由程序具有交错语义：每个代理的每一步求值语义互相交错。此时无需理解内存模型细节，细节对编写 ECMAScript 的直觉帮助有限。

更一般地，即便程序非数据竞争自由，也可能具可预测行为，只要原子操作不参与任何数据竞争，且竞争操作的访问大小一致。最简单方式是保证原子与非原子操作使用不同内存单元，且不同大小的原子访问不同时访问相同单元。实质上，程序应尽量将共享内存视为强类型。仍不可依赖竞争的非原子访问的顺序与时序，但若内存被强类型对待，竞争访问不会“撕裂”（其值的位不会混合）。

 Note 2

以下是面向为使用共享内存程序编写编译器变换的 ECMAScript 实现者的指南。

希望在多代理环境中允许大多数在单代理环境有效的程序变换，以确保多代理程序中每个代理的性能与单代理时一样。此类变换往往难以判定。我们概述若干应视为规范性的规则（由内存模型蕴含或比其更强），但不一定穷尽。规则适用于在组成 is-agent-order-before 关系的事件引入之前的程序变换。

令 agent-order slice 为 is-agent-order-before 关系中属于单一代理的子集。

令读取事件的 possible read values 为该事件在所有合法执行中 ValueOfReadEvent 的所有值集合。

在无共享内存时有效的任意 agent-order slice 变换在存在共享内存时亦有效，以下例外：

  • 原子操作不可动摇：程序变换不得使 agent-order slice 中的 seq-cst 事件与其 unordered 操作重排，亦不得重排其 seq-cst 操作之间的顺序，也不得移除 seq-cst 操作。

    （实践中，该限制迫使编译器假设每个 seq-cst 操作均为同步点并被包含在最终 is-memory-order-before 关系中。）

  • 读取必须稳定：任一共享内存读取在一次执行中只能观察到单一值。

    （例如，若语义上单次读取被多次执行，则程序只能观察其中一个值；某些再物化变换可违反此规则。）

  • 写入必须稳定：所有可观察写入必须源于该次执行的程序语义。

    （例如，变换不能引入程序本不可能的写，如对更大位置的读改写来写较小数据，写入程序原本不可写的值，或将刚读取的值写回其位置且期间可能被他代理覆盖。）

  • 可能读取值不得为空：程序变换不能使某共享内存读取的可能读取值集合为空。

    （反直觉地，该规则实际限制对写的变换，因为写的作用仅在被读事件读取。例如写可移动、合并，有时在两个 seq-cst 操作间重排，但不可删掉所有更新某位置的写，必须保留一个。）

仍然有效的变换示例：合并多个对同一位置的非原子读；重排非原子读；引入推测非原子读；合并多个对同一位置的非原子写；对不同位置的非原子写重排；将非原子读外提出循环（即使影响终止性）。注意别名 TypedArrays 使证明位置不同变得困难。

 Note 3

以下是面向为共享内存访问生成机器码的 ECMAScript 实现者的指南。

对内存模型不弱于 ARM 或 Power 的架构，非原子存取可编译为裸存取。原子存取可编译为保证顺序一致的指令。若不存在此类指令，则使用内存屏障（如在裸存/取两侧放置）。读改写操作可编译为目标架构的读改写指令，如 x86 上的 LOCK 前缀指令，ARM 的 load-exclusive/store-exclusive，Power 的 load-link/store-conditional。

具体而言，内存模型旨在允许如下代码生成：

  • 程序中的每个原子操作都被视为必要。
  • 原子操作不与其他原子或非原子操作重排。
  • 函数被假定执行原子操作。
  • 原子操作不以更大数据的读改写实现，而在不支持相应大小原子时使用非锁自由原子（假定平台具备所有必要尺寸的普通内存访问）。

朴素代码生成模式：

  • 常规加载与存储 -> 单条加载/存储指令。
  • 锁自由原子加载与存储 -> 全栅栏，常规加载/存储，再全栅栏。
  • 锁自由原子读改写 -> 全栅栏，原子读改写指令序列，全栅栏。
  • 非锁自由原子 -> 自旋锁获取，全栅栏，一系列非原子读写，全栅栏，自旋锁释放。

该映射在原子操作与非原子写或不同大小原子不竞争下正确；若竞争，内存模型将相关原子操作降级为非原子。但此朴素映射很强：允许原子操作充当顺序一致栅栏，这超出模型实际保证。

局部优化在模型约束下也是允许的，例如：

  • 平台相关的消除冗余栅栏（例如 x86 上锁自由原子读写的栅栏多可省略，除写后的栅栏）。
  • 多数现代平台支持所需数据大小的锁自由原子；若需非锁自由原子，可将原子操作体周围栅栏折叠进锁操作；最简单是每个 SharedArrayBuffer 一个锁字。
  • 更复杂的局部优化，如合并背靠背栅栏；x86 上分隔原子写的栅栏可省，因写后所需栅栏仅用于分隔与后续读。