内存栅栏：软件黑客眼中的硬件视角

需积分: 1 186 浏览量更新于2024-07-20 1 收藏 288KB PDF 举报

"本文是Paul E. McKenney在2009年发表的一篇关于内存栅栏的文章，主要探讨了内存屏障在并发同步中的重要性以及硬件层面的理解。" 在现代计算机系统中，尤其是多处理器（SMP，Symmetric Multi-Processing）环境中，内存屏障（Memory Barriers）是确保并发程序正确同步的关键机制。内存屏障，也称为内存栅栏，是为了对抗处理器对内存操作的重排序优化而引入的。处理器为了提高性能，会重新安排指令的执行顺序，这可能导致内存访问的顺序发生改变。然而，对于依赖于特定内存访问顺序的同步原语（如锁、信号量等）来说，这种重排序可能会破坏其正确性。文章首先介绍了缓存的基本结构。缓存是处理器与主内存之间的高速缓冲，用于存储频繁访问的数据，以减少访问主内存的延迟。缓存的工作原理是基于局部性原理，即程序倾向于连续访问同一块内存区域。接着，文章详细描述了缓存一致性协议的作用。当多个处理器共享同一内存时，缓存一致性协议确保每个处理器对内存位置的修改都能被其他处理器及时感知到，从而保持各处理器间的一致视图。这通常通过诸如MESI（Modified, Exclusive, Shared, Invalidated）这样的协议来实现。最后，文章探讨了存储缓冲区（Store Buffers）和无效队列（Invalidate Queues）如何帮助缓存和缓存一致性协议实现高性能。存储缓冲区暂时存储写操作，允许处理器继续执行后续指令，而无效队列则管理着在不同处理器之间传播的缓存状态更新信息。这些机制虽然提高了性能，但也为内存屏障的存在提供了理由，因为它们可能导致写入操作的实际完成顺序与程序顺序不一致。内存屏障的使用确保了在特定点强制执行内存访问顺序，这对于构建正确同步的并发程序至关重要。尽管内存屏障增加了编程复杂性和可能的性能开销，但它们是现代处理器体系结构中不可或缺的一部分，以确保在追求高性能和可扩展性的同时，维持软件的正确性。理解和合理利用内存屏障是软件开发者在面对多核、多处理器环境时必须掌握的重要技能。

Transition (d): The CPU does an atomic read-

modify-write operation on a data item that was

not present in its cache. It transmits a “read

invalidate”, receiving the data via a “read re-

sponse”. The CPU can complete the transition

once it has also received a full set of “invalidate

acknowledge” responses.

Transition (e): The CPU does an atomic read-

modify-write operation on a data item that was

previously read-only in its cache. It must trans-

mit “invalidate” messages, and must wait for a

full set of “invalidate acknowledge” responses be-

fore completing the transition.

Transition (f): Some other CPU reads the cache

line, and it is supplied from this CPU’s cache,

which retains a read-only copy. This transition

is initiated by the reception of a “read” message,

and this CPU responds with a “read response”

message containing the requested data.

Transition (g): Some other CPU reads a data item

in this cache line, and it is supplied either from

this CPU’s cache or from memory. In either case,

this CPU retains a read-only copy. This tran-

sition is initiated by the reception of a “read”

message, and this CPU responds with a “read re-

sponse” message containing the requested data.

Transition (h): This CPU realizes that it will soon

need to write to some data item in this cache

line, and thus transmits an “invalidate” message.

The CPU cannot complete the transition until

it receives a full set of “invalidate acknowledge”

responses. Alternatively, all other CPUs eject

this cache line from their caches via “writeback”

messages (presumably to make room for other

cache lines), so that this CPU is the last CPU

caching it.

Transition (i): Some other CPU does an atomic

read-modify-write operation on a data item in a

cache line held only in this CPU’s cache, so this

CPU invalidates it from its cache. This transi-

tion is initiated by the reception of a “read in-

validate” message, and this CPU responds with

both a “read response” and an “invalidate ac-

knowledge” message.

Transition (j): This CPU does a store to a data

item in a cache line that was not in its cache,

and thus transmits a “read invalidate” message.

The CPU cannot complete the transition until it

receives the “read response” and a full set of “in-

validate acknowledge” messages. The cache line

will presumably transition to “modiﬁed” state

via transition (b) as soon as the actual store com-

pletes.

Transition (k): This CPU loads a data item in

a cache line that was not in its cache. The

CPU transmits a “read” message, and completes

the transition upon receiving the corresponding

“read response”.

Transition (l): Some other CPU does a store to a

data item in this cache line, but holds this cache

line in read-only state due to its being held in

other CPUs’ caches (such as the current CPU’s

cache). This transition is initiated by the recep-

tion of an “invalidate” message, and this CPU

responds with an “invalidate acknowledge” mes-

sage.

Quick Quiz 4: How does the hardware handle the

delayed transitions described above?

2.4 MESI Protocol Example

Let’s now look at this from the perspective of a cache

line’s worth of data, initially residing in memory at

address 0, as it travels through the various single-line

direct-mapped caches in a four-CPU system. Table 1

shows this ﬂow of data, with the ﬁrst column show-

ing the sequence of operations, the second the CPU

performing the operation, the third the operation be-

ing performed, the next four the state of each CPU’s

cache line (memory address followed by MESI state),

and the ﬁnal two columns whether the corresponding

memory contents are up to date (“V”) or not (“I”).

Initially, the CPU cache lines in which the data

would reside are in the “invalid” state, and the data

is valid in memory. When CPU 0 loads the data at

address 0, it enters the “shared” state in CPU 0’s

cache, and is still valid in memory. CPU 3 also loads

the data at address 0, so that it is in the “shared”

state in both CPUs’ caches, and is still valid in mem-

ory. Next CPU 3 loads some other cache line (at

address 8), which forces the data at address 0 out of

its cache via a writeback, replacing it with the data

at address 8. CPU 2 now does a load from address 0,

but this CPU realizes that it will soon need to store

to it, and so it uses a “read invalidate” message in

order to gain an exclusive copy, invalidating it from

CPU 3’s cache (though the copy in memory remains

up to date). Next CPU 2 does its anticipated store,

changing the state to “modiﬁed”. The copy of the

data in memory is now out of date. CPU 1 does an

atomic increment, using a “read invalidate” to snoop

the data from CPU 2’s cache and invalidate it, so that

the copy in CPU 1’s cache is in the “modiﬁed” state

(and the copy in memory remains out of date). Fi-

nally, CPU 1 reads the cache line at address 8, which

uses a “writeback” message to push address 0’s data

back out to memory.

Note that we end with data in some of the CPU’s

caches.

Quick Quiz 5: What sequence of operations

would put the CPUs’ caches all back into the “in-

valid” state?

3 Stores Result in Unnecessary

Stalls

Although the cache structure shown in Figure 1 pro-

vides good performance for repeated reads and writes

from a given CPU to a given item of data, its perfor-

mance for the ﬁrst write to a given cache line is quite

poor. To see this, consider Figure 4, which shows a

timeline of a write by CPU 0 to a cacheline held in

CPU 1’s cache. Since CPU 0 must wait for the cache

line to arrive before it can write to it, CPU 0 must

stall for an extended period of time.

The time required to transfer a cache line from one CPU’s

cache to another’s is typically a few orders of magnitude more

than that required to execute a simple register-to-register in-

struction.

CPU 0 CPU 1

Write

Acknowledgement

Invalidate

Stall

Figure 4: Writes See Unnecessary Stalls

But there is no real reason to force CPU 0 to stall

for so long — after all, regardless of what data hap-

pens to be in the cache line that CPU 1 sends it, CPU

0 is going to unconditionally overwrite it.

3.1 Store Buﬀers

One way to prevent this unnecessary stalling of writes

is to add “store buﬀers” between each CPU and its

cache, as shown in Figure 5. With the addition of

these store buﬀers, CPU 0 can simply record its write

in its store buﬀer and continue executing. When the

cache line does ﬁnally make its way from CPU 1 to

CPU 0, the data will be moved from the store buﬀer

to the cache line.

However, there are complications that must be ad-

dressed, which are covered in the next two sections.

3.2 Store Forwarding

To see the ﬁrst complication, a violation of self-

consistency, consider the following code with vari-

ables “a” and “b” both initially zero, and with the

cache line containing variable “a” initially owned by

CPU 1 and that containing “b” initially owned by

CPU 0:

剩余25页未读，继续阅读

ProgramResearch

粉丝: 0
资源: 18

内存栅栏：软件黑客眼中的硬件视角

Memory Barriers: a Hardware View for Software Hackers 讲解内存屏障的好论文，推荐！

Memory_Barriers_a_Hardware_View_for_Software_Hacke.pdf

memory-barriers.pdf

Memory-barriers.pdf

Developing a framework to identify barriers of Green technology adoption for ent

hackathon-for-a-world-without-barriers

Adolphus, Stephen H. (Ed.) (1984), Equality postponed: Continuing barriers to higher education in the 1980s (Report from a Policy Conference on Postsecondary Programs for the Disadvantaged, held at Wingspread, Racine, Wisconsin, in June 1982). New York: C

Unified characteristic numbers and solutions of equations for birth and death processes with barriers

Memory-access-ordering-part-2---barriers-and-the-_Windows编程_Unix_Linux_

Bowe, F. Handicapping America: Barriers to disabled people. New York: Harper & Row, 1978, 254 pp., [dollar]10.95

最新资源