29 内存模型

内存一致性模型,或称 内存模型,用于指定共享数据块事件可以出现的顺序,这些事件是通过访问以 SharedArrayBuffer 为后端的 TypedArray 实例以及通过 Atomics 对象的方法产生的。当程序不存在数据竞争(定义见下文)时,事件的顺序表现为顺序一致性,即表现为来自每个 agent 的动作按某种交织出现。当程序存在数据竞争时,内存操作可能不再表现为顺序一致。例如,程序可能会出现违反因果律的行为或其他令人惊讶的现象。这些现象源于编译器变换和 CPU 的设计(如乱序执行与推测执行)。内存模型既定义了程序表现为顺序一致行为的准确条件,也定义了数据竞争时可能读取的值。换言之,没有未定义行为。

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

Note

本节基于抽象操作引入的 SharedArrayBuffer 上的 Memory 事件提供了一个公理化模型。需要强调的是,这种模型不能像本规范其它部分一样用算法表述。抽象操作非确定性地引入事件,这成为 ECMAScript 求值的操作语义与内存模型的公理化语义之间的接口。这些事件的语义是通过考察一次求值中所有事件所组成的图来定义的。这既不是静态语义,也不是运行时语义。这里没有已证明的算法实现,而是一组约束,用于决定一个特定事件图是否被允许。

29.1 内存模型基础

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

Note 1

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

共享数据块事件是指 ReadSharedMemoryWriteSharedMemoryReadModifyWriteSharedMemory 记录之一。读事件是指 ReadSharedMemory 或 ReadModifyWriteSharedMemory。写事件是指 WriteSharedMemory 或 ReadModifyWriteSharedMemory。

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

共享数据块事件是通过抽象操作或者 Atomics 对象的方法引入到候选执行的代理事件记录中的。一些操作还会引入同步事件,同步事件没有任何字段,仅用于直接约束其他事件被允许的排序。最后,还存在特定于宿主的事件。内存事件指的是共享数据块事件、同步事件或此类宿主特定事件。

令共享数据块事件 e内存区间为从 e.[[ByteIndex]](包含)到 e.[[ByteIndex]] + e.[[ElementSize]](不包含)之间所有整数的集合。当两个事件拥有相同的 [[Block]][[ByteIndex]][[ElementSize]] 时,它们的内存区间相等。若两个事件拥有相同的 [[Block]]区间不等且它们的交集非空,则称它们的内存区间重叠。若两个事件没有相同的 [[Block]],或它们的区间既不相等也不重叠,则称它们的内存区间不相交。

Note 2

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

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

29.2 代理事件记录

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

Table 97: 代理事件记录字段
字段名 取值 含义
[[AgentSignifier]] 一个代理标识符 产生此排序结果的代理。
[[EventList]] 一个内存事件的列表 事件在求值过程中按顺序追加到此列表。
[[AgentSynchronizesWith]] 同步事件对的列表 由操作语义引入的同步关系。

29.3 选定值记录

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

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

29.4 候选执行

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

Table 99: 候选执行记录字段
字段名 取值 含义
[[EventsRecords]] 代理事件记录的列表 将代理映射到求值过程中追加的内存事件列表。
[[ChosenValues]] 已选值记录的列表 ReadSharedMemoryReadModifyWriteSharedMemory 事件映射为求值过程中选定的字节值列表。

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

29.5 内存模型的抽象操作

29.5.1 EventSet ( execution )

The abstract operation EventSet takes argument execution (一个候选执行) and returns 一个 Memory 事件的集合. It performs the following steps when called:

  1. events 为一个空集合。
  2. 对于 execution.[[EventsRecords]] 的每个代理事件记录 aer,执行
    1. 对于 aer.[[EventList]] 的每个 Memory 事件 E,执行
      1. E 加入 events
  3. 返回 events

29.5.2 SharedDataBlockEventSet ( execution )

The abstract operation SharedDataBlockEventSet takes argument execution (一个候选执行) and returns 一个共享数据块事件的集合. It performs the following steps when called:

  1. events 为一个空集合。
  2. 对于 EventSet(execution) 的每个 Memory 事件 E,执行
    1. 如果 E 是一个共享数据块事件,则将 E 加入 events
  3. 返回 events

29.5.3 HostEventSet ( execution )

The abstract operation HostEventSet takes argument execution (一个候选执行) and returns 一个 Memory 事件的集合. It performs the following steps when called:

  1. 返回一个包含 EventSet(execution) 中所有不在 SharedDataBlockEventSet(execution) 中元素的新集合。

29.5.4 ComposeWriteEventBytes ( execution, byteIndex, Ws )

The abstract operation ComposeWriteEventBytes takes arguments execution (一个候选执行), byteIndex (一个非负整数), and Ws (WriteSharedMemoryReadModifyWriteSharedMemory 事件的列表) and returns 一个字节值列表. It performs the following steps when called:

  1. byteLocationbyteIndex
  2. bytesRead 为一个新的空列表。
  3. 对于 Ws 中的每个元素 W,执行
    1. 断言:W内存区间包含 byteLocation
    2. payloadIndexbyteLocation - W.[[ByteIndex]]
    3. 如果 WWriteSharedMemory 事件,则
      1. byteW.[[Payload]][payloadIndex]。
    4. 否则,
      1. 断言:WReadModifyWriteSharedMemory 事件。
      2. bytesValueOfReadEvent(execution, W)。
      3. bytesModifiedW.[[ModifyOp]](bytes, W.[[Payload]])。
      4. bytebytesModified[payloadIndex]。
    5. byte 添加到 bytesRead
    6. byteLocation 加 1。
  4. 返回 bytesRead
Note 1

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

Note 2

抽象操作将一组写事件组合为一个字节值列表。它用于 ReadSharedMemoryReadModifyWriteSharedMemory 事件的事件语义中。

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. Wsreads-bytes-from(R) in execution
  2. 断言:Ws 是长度等于 R.[[ElementSize]]WriteSharedMemoryReadModifyWriteSharedMemory 事件 List
  3. 返回 ComposeWriteEventBytes(execution, R.[[ByteIndex]], Ws)。

29.6 候选执行的关系

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

以下关系和数学函数是以特定的候选执行为参数,对其 Memory 事件进行排序。

29.6.1 is-agent-order-before

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

  • 对于事件 ED,如果存在 execution.[[EventsRecords]] 中的 Agent Events Record aer,使得 aer.[[EventList]] 同时包含 ED,且 Eaer.[[EventList]] 的列表顺序中位于 D 之前,则 E is-agent-order-before D
Note

每个 agent 在求值过程中按每 agent 的严格全序引入事件。这是那些严格全序的并集。

29.6.2 reads-bytes-from

对于候选执行 execution,其 reads-bytes-from 函数是一个数学函数,将 SharedDataBlockEventSet(execution) 中的 Memory 事件映射到 SharedDataBlockEventSet(execution) 中事件的列表,满足以下条件。

一个候选执行总是允许一个 reads-bytes-from 函数存在。

29.6.3 reads-from

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

29.6.4 host-synchronizes-with

对于候选执行 execution,其 host-synchronizes-with 关系是在宿主特定的 Memory 事件上的宿主提供的严格偏序,至少满足以下条件。

  • 如果 E host-synchronizes-with Dexecution 中,HostEventSet(execution) 包含 ED
  • host-synchronizes-with 与 is-agent-order-before 的并集在 execution 中不存在环。
Note 1

对于候选执行 execution 中的两个宿主特定事件 EDE host-synchronizes-with D 意味着 E happens-before D

Note 2

该关系允许宿主提供额外的同步机制,例如 HTML worker 之间的 postMessage

29.6.5 synchronizes-with

对于候选执行 execution,其 synchronizes-with 关系是在 Memory 事件上的最小关系,满足以下条件。

  • 对于事件 RW,若 R reads-from W in execution,且 R.[[Order]]seq-cstW.[[Order]]seq-cst,且 RW内存区间相等,则 W synchronizes-with R in execution
  • 对于 execution.[[EventsRecords]] 的每个元素 eventsRecord,如下成立。
    • 对于事件 SSw,如果 eventsRecord.[[AgentSynchronizesWith]] 包含 (S, Sw),则 S synchronizes-with Sw in execution
  • 对于事件 ED,若 execution.[[HostSynchronizesWith]] 包含 (E, D),则 E synchronizes-with D in execution
Note 1

根据内存模型文献的惯例,在候选执行 execution 中,写事件 synchronizes-with 读事件,而不是读事件 synchronizes-with 写事件

Note 2

在候选执行 execution 中,init 事件不参与该关系,而是直接被 happens-before 约束。

Note 3

在候选执行 execution 中,并非所有通过 reads-from 相关的 seq-cst 事件都通过 synchronizes-with 相关。只有内存区间也相等的事件才通过 synchronizes-with 相关。

Note 4

对于候选执行 execution 中的共享数据块事件 RW,若 W synchronizes-with R,则 R 仍有可能 reads-fromW 之外的其他写事件

29.6.6 happens-before

对于候选执行 execution,其 happens-before 关系是在 Memory 事件上的最小关系,满足下列条件。

  • 对于事件 ED,只要下列任何条件成立,则 E happens-before D in execution

Note

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

29.7 有效执行的性质

29.7.1 有效选定读取

若下述算法返回 true,则候选执行 execution 具有有效选定读取。

  1. 对于 SharedDataBlockEventSet(execution) 中的每个 ReadSharedMemoryReadModifyWriteSharedMemory 事件 R,执行
    1. chosenValueRecordexecution.[[ChosenValues]][[Event]] 字段为 R 的元素。
    2. chosenValuechosenValueRecord.[[ChosenValue]]
    3. readValueValueOfReadEvent(execution, R)。
    4. chosenLenchosenValue 的元素数量。
    5. readLenreadValue 的元素数量。
    6. 如果 chosenLenreadLen,则
      1. 返回 false
    7. 如果存在某个整数 i,范围从 0(包含)到 chosenLen(不包含),满足 chosenValue[i] ≠ readValue[i],则
      1. 返回 false
  2. 返回 true

29.7.2 一致性读取

若下述算法返回 true,则候选执行 execution 具有一致性读取。

  1. 对于 SharedDataBlockEventSet(execution) 中的每个 ReadSharedMemoryReadModifyWriteSharedMemory 事件 R,执行
    1. Wsreads-bytes-from(R) in execution
    2. byteLocationR.[[ByteIndex]]
    3. 对于 Ws 中的每个元素 W,执行
      1. 如果 R happens-before W in execution,则
        1. 返回 false
      2. 如果存在 WriteSharedMemoryReadModifyWriteSharedMemory 事件 V,它的内存区间包含 byteLocation,且 W happens-before V in execution 并且 V happens-before R in execution,则
        1. 返回 false
      3. byteLocation 加 1。
  2. 返回 true

29.7.3 无撕裂读取

若下述算法返回 true,则候选执行 execution 具有无撕裂读取。

  1. 对于 SharedDataBlockEventSet(execution) 中的每个 ReadSharedMemoryReadModifyWriteSharedMemory 事件 R,执行
    1. 如果 R.[[NoTear]]true,则
      1. 断言:R.[[ByteIndex]] 除以 R.[[ElementSize]] 的余数为 0。
      2. 对于满足 R reads-from W in executionW.[[NoTear]]true 的 Memory 事件 W,执行
        1. 如果 RW内存区间相等,且存在 Memory 事件 V,满足 VW内存区间相等,V.[[NoTear]]trueWV 不是同一个 Shared Data Block 事件,并且 R reads-from V in execution,则
          1. 返回 false
  2. 返回 true
Note

通过访问整型 TypedArray 引入事件时,共享数据块事件[[NoTear]] 字段为 true;通过访问浮点型 TypedArray 或 DataView 引入则为 false

直观来说,这一要求意味着:当通过整型 TypedArray 以对齐方式访问内存区间时,在和其他写事件产生数据竞争时,该区间上的单个写事件必须“获胜”。更准确地说,就是对齐读取不能从多个、区间相等但事件不同的写事件的字节组合值中读取。然而,对齐读仍然可以从多个区间重叠的写事件中读取。

29.7.4 顺序一致的原子操作

对于候选执行 executionis-memory-order-before 是对 EventSet(execution) 所有 Memory 事件的严格全序,满足如下条件。

候选执行有顺序一致原子操作,当且仅当它允许存在 is-memory-order-before 关系。

Note 3

虽然 is-memory-order-before 包含 EventSet(execution) 中所有事件,但那些不受 happens-beforesynchronizes-with 约束的事件可以在顺序中的任意位置。

29.7.5 有效执行

若候选执行 execution 满足如下所有条件,则称其为有效执行(或简称执行)。

  • 宿主execution 提供了 host-synchronizes-with 关系。
  • execution 允许存在严格偏序happens-before 关系。
  • execution 具有有效选定读取。
  • execution 具有一致性读取。
  • execution 具有无撕裂读取。
  • execution 具有顺序一致的原子操作。

所有程序至少有一个有效执行。

29.8 竞争(Races)

对于 execution execution 和已包含在 SharedDataBlockEventSet(execution) 内的事件 ED,若下述算法返回 true,则 ED 存在 竞争

  1. 如果 ED 不是同一个 Shared Data Block 事件,则
    1. 如果不存在 E happens-before D in executionD happens-before E in execution,则
      1. 如果 ED 均为 WriteSharedMemoryReadModifyWriteSharedMemory 事件,且 ED内存区间不相交,则
        1. 返回 true
      2. 如果 E reads-from D in executionD reads-from E in execution,则
        1. 返回 true
  2. 返回 false

29.9 数据竞争(Data Races)

对于 execution executionSharedDataBlockEventSet(execution) 内的事件 ED,若下述算法返回 true,则它们存在 数据竞争

  1. 如果 EDexecution 中存在 竞争,则
    1. 如果 E.[[Order]] 不是 seq-cstD.[[Order]] 不是 seq-cst,则
      1. 返回 true
    2. 如果 ED内存区间重叠,则
      1. 返回 true
  2. 返回 false

29.10 无数据竞争(Data Race Freedom)

SharedDataBlockEventSet(execution) 中不存在任何处于数据竞争的事件对,则执行 execution无数据竞争的。

若某程序的所有执行都无数据竞争,则该程序是无数据竞争的。

内存模型保证无数据竞争程序的全部事件都具有顺序一致性。

29.11 共享内存编程指南

Note 1

以下是 ECMAScript 程序员在使用共享内存时的相关建议。

我们建议程序保持无数据竞争(即确保不存在对同一内存地址的并发非原子操作)。无数据竞争的程序具有交织语义,每个 agent 的求值语义中的每一步都可以与其他 agent 交织。在无数据竞争程序下,不必理解内存模型的细节。细节并不会真正帮助你更好地编写 ECMAScript 代码。

更一般来说,即使程序不是无数据竞争的,只要所有涉及原子操作的数据竞争都不存在,且发生竞争的操作具有相同的访问大小,程序可能依然是可预测的。让原子操作不参与竞争最简单的方式是确保原子和非原子操作访问不同的内存单元,并且不同大小的原子访问不会同时访问同一单元。实质上,程序应尽量把共享内存视为强类型内存。你仍不能依赖于参与竞争的非原子访问的顺序和时机,但如果内存视为强类型,则访问不会“撕裂”(即值的各位不会出现混杂)。

Note 2

以下是 ECMAScript 实现者针对使用共享内存的程序编译器转换的建议。

在多 agent 环境下,允许大多数在单 agent 环境中有效的程序变换是很有必要的,这样可以确保多 agent 程序中每个 agent 的性能不会低于其在单 agent 情境下的表现。然而,这些变换通常难以评判。我们在此概述了一些关于程序变换的规范性规则(即这些规则要么隐含于内存模型,要么比内存模型更严格),但这些规则很可能不是完全穷尽的。这些规则旨在适用于那些发生在组成 is-agent-order-before 关系的 Memory 事件被引入之前的程序变换。

定义 agent-order 切片is-agent-order-before 关系中,属于单个 agent 的子集。

定义某次读事件可能读取值(possible read values)为所有有效执行中 ValueOfReadEvent 的所有可能值之集合。

任何在无共享内存场景下有效的 agent-order 切片转换,在有共享内存下同样有效,但需遵循以下例外:

  • 原子操作不可改变:程序变换不得导致 is-agent-order-before 关系中 [[Order]]seq-cst共享数据块事件被移除、互相重排序,或与 [[Order]]unordered 的事件重排序。

    (实际上,对重排序的禁止迫使编译器假定每个 seq-cst 操作都是一次同步,并会出现在最终的 is-memory-order-before 关系中,实际在无跨 agent 程序分析下也必须这样处理。同时编译器还假定所有调用、其中被调函数对 memory-order 影响未知时,也可能含有 seq-cst 操作。)

  • 读取需稳定:每个共享内存读取在一次执行中只能见到唯一值。

    (例如,若语义上是一次读取而程序实际执行了多次,那么之后程序只允许观察到其中一个读取结果。rematerialization 等变换会破坏这个规则。)

  • 写入需稳定:所有可观察到的对共享内存的写都必须基于执行过程产生。

    (如:某些变换不得引入新的可观察写入,比如用对更大内存的读改写操作写入小数据,在程序无法写出的值被写入、或者读取后又立即写回,而该地址可能已被其它 agent 覆盖。)

  • 读取的可能值不能为空:程序变换不得导致某次共享内存读取的"可能读取值"集合为空。

    (直观上,这一规则实则限制了对写的变换,因为写只有能被读到才有模型效力。例如,允许合并/重排序写,但不得移除全部写入,否则可能会让某次读取无值可读。)

例如:合并同一地址的多次非原子读取、重排序非原子读取、引入投机性非原子读取,合并同一地址的多次非原子写、重排序写到不同地址的非原子写,以及将非原子读取提出循环体外甚至影响终止性等,都是有效的变换。但需要注意别名 TypedArray 情况下难以证明地址不同。

Note 3

以下是 ECMAScript 实现者在为共享内存访问生成机器码时的建议。

对于内存模型不弱于 ARM 或 Power 的体系结构,非原子读写可直接编译为普通的存取指令。原子读写可编译为保证顺序一致性的指令,如无则应组合内存屏障:在普通存取指令前后分别插入屏障。读改写操作可编译为对应的读改写指令,例如 x86 的 LOCK 前缀、ARM 的 load-exclusive/store-exclusive、Power 的 load-link/store-conditional。

内存模型的本意容许如下代码生成:

  • 程序中的每个原子操作都视为必需。
  • 原子操作之间,及与非原子操作之间,都不得重排序。
  • 所有函数都假定可能执行原子操作。
  • 原子操作不得通过在更大数据上做读改写实现(不能偷懒为非 lock-free 的原子操作),如目标平台无相应原子操作,则应退化为非 lock-free 原子(假定任意有用数据尺寸的常规内存存取操作总是有)。

朴素代码生成模式如下:

  • 普通读写编译为单条指令。
  • lock-free 的原子读写生成:完整(顺序一致性)屏障、常规指令、完整屏障。
  • lock-free 的原子读改写:完整屏障、原子读改写指令序列、完整屏障。
  • 非 lock-free 原子需加自旋锁 acquire、完整屏障、非原子读写指令序列、完整屏障、自旋锁 release。

只要原子操作的内存区间不与非原子写或不同大小的原子操作竞争,这种方式就是正确的。内存模型实际上会把参与竞争的原子操作降级为非原子。而该映射方式比规范还强:它允许原子操作用来实现顺序一致的全局屏障,这是内存模型本身未实际保证的。

对上述模式的局部优化也是允许的,只要遵循内存模型约束。例如:

  • 可以根据平台移除冗余屏障。如 x86 上 lock-free 原子读写前后的屏障一般都可以省略,仅存储后需要,lock-free 原子读改写则完全无需屏障(因皆用 LOCK 前缀)。多数平台有不同强度的屏障,根据场景可用更弱屏障而不破坏顺序一致性。
  • 大多数现代平台都支持 ECMAScript 所需尺寸的 lock-free 原子,如需非 lock-free 的原子,原子的屏障通常能融合进锁的 acquire/release。最简单的方案是为每个 SharedArrayBuffer 配一个锁字。
  • 还可进行更复杂的平台依赖本地优化,需一些代码分析。例如两条屏障连续出现时效果等同于一条,只须按需插入。如 x86 上,甚至原子写之后的屏障就可省略,因为仅需将写与随后的读隔开。