2023-02-03

Computer System

mesi与伪共享

随着现代CPU设计技术的不断发展，CPU的性能和内存性能差距逐步拉大，程序执行时需要不断通过总线访问内存读写数据，与内存之间的数据传输成为了计算机性能的巨大瓶颈。

cache

局部性

计算机程序中的指令一般情况下是按顺序执行，但也存在着诸如循环等结构，循环会不断执行相同的指令，而执行函数时，也会访问存储在函数栈帧中的局部变量。因此程序执行通常具有局部性，局部性有两种不同的表现形式：

时间局部性：被引用过的内存位置很可能在不久的将来再次引用，如循环结构中访问的变量以及循环结构本身的指令
空间局部性：被引用过的内存位置，其附近的数据项很可能在不久的将来被引用，如遍历数组、访问结构体等

memory hierarchy

一般来说，处于更高层的存储结构价格较高，容量较小，但访问速度快，CPU访问频率也越高，而处于低层次的存储结构价格较低，容量较大，但访问速度慢CPU，访问频率越低。

可见，相对于访问cache，直接从内存中存取数据消耗的时间是前者的几十倍之大。因此，现代计算机系统一般提供使用层次化方法设计存储器系统，将程序经常访问的以及更倾向于访问的数据存放在离CPU较近的存储层中，提升数据存取的速度，进而缩短程序执行的时间。根据局部性，提供的存储系统具备近乎较高层次的快速和较低层次的大容量特点。

cache一致性问题

在一个多核处理器系统中，不同的处理器可能对同一物理地址进行操作，cache共享数据引入的一个新的问题是，由于两个不同的处理器保存的存储器视图都是通过各自的cache获得的，如果没有任何额外的保护措施，那么处理器可能看到两个不同的值。例如，在一个多线程的程序中，两个不同的线程分别在两个不同的处理器上运行，并且访问同一全局变量，这个全局变量分别存放在两个处理器的cache中，当一个线程更新全局变量时，由于cache采用的是write back、write allocate策略，因此该线程所处的处理器会在cache中更新该变量，而不会立即写回内存，另一个处理器cache中的该全局变量的值就是旧的。
简单来说，如果对任何数据项的读取都能返回该数据项的最新值，则该存储系统是一致的。一致包含了存储系统行为的两个方面：第一是coherence，即一致性，定义了读取操作会返回什么值；第二是consistency，即连续性，定义了写入的值什么时候会被读取操作返回。

监听协议

一个常用的cache一致性协议是监听。cache中既包含物理存储器数据的副本，也含有该数据块的共享状态，但并不集中保留状态。这些cache都可以通过一些广播媒体（总线或网络）访问，而且所有的cache控制器都可以监听媒介，以确定它们是否有总线访问所需的数据块的副本。

MESI

introduce

缓存一致性协议MESI(Modified Exclusive Shared Invalid)，四个字母缩写代表了缓存行的四种状态：

M：modified，表示当前cache行中的副本数据已经被修改，和主存中的数据不一致，若其他处理器想读取主存中的数据，必须等待当前行的副本写回主存。可以理解为，当前CPU更改了副本的值，主存中的数据是旧的，若其他CPU需要读取，必须等当前cache行先写回新的值
E：exclusive，当前cache行中的数据的副本是独占中，别的处理器cache还未包含该数据的副本，当前cache行中的副本和主存中的数据值是一致的
S：shared，即多个CPU的cache都缓存了主存中数据的副本，处于共享状态，且均和主存中数据一致。可以理解为当前cache行中的副本数据在其他CPU的cache中也存在，且均是“干净”的
I：invalid，即无效状态，表示当前cache行中的数据副本已经失效，需要重新从内存中读取

状态迁移图

考虑多核处理器系统中，多个core对相关的（即缓存的副本是内存中的统一数据）cache行进行操作时，会影响自身或其他core中cache行的状态，大致状态转移图如下，共存在4种event：

local read：当前core读取cache行中的数据副本
local write：当前core修改cache行中的数据副本
remote read：其他core读取自己的cache行中的数据副本
remote write：其他core修改自己的cache行中的数据副本

我们通过一个简单的例子帮助理解状态以及其转移的含义。假设在多核处理器系统中，有三个线程分别运行在core A、core B和core C（下文简称A、B、C）上，对同一变量进行访问。初始状态3个core中的cache行均是Invalid。cache采用write back + write allocate策略。

A读取变量，触发local read事件，将其缓存在自身的cache中，状态设为Exclusive（当前仅一份副本）。B和C中cache行仍是Invalid
A修改变量，触发local write事件，直接修改其缓存的cache中的副本，状态设为Modified。B和C中cache行仍是Invalid
B读取变量，本地触发local read事件，对于A出发remote read事件。首先A将其自身的相关cache行写回，状态设为Shared（与B共享）。B从主存中读取变量并缓存到cache行中，状态也设为Shared。C中cache行仍是Invalid
A读取变量，触发local read事件，直接从自身cache中获取最新数据副本
B修改变量，触发local write事件，对于A触发remote write事件。B直接修改自身的cache行，状态设为Modified。A中cache行缓存的已是旧值，设为Invalid，下次使用需要重新读取。C中cache行仍是Invalid
C修改变量，触发local write事件，对于B触发remote write事件。B中cache行的状态为Modified，首先写回cache行，并且状态设为Invalid（因为C将进行修改操作，B中的数据将会是旧值）。C从内存读取最新的数据（B刚写回的），并缓存在自身cache中，然后修改该副本，状态变为Modified。

多个core在进行操作时，会通过总线进行通信，此处略过通信的具体过程，有兴趣的朋友可以上网搜索。

状态迁移表

State	Event	Action
Modified	local read	从cache中读取，状态不变
	local write	修改cache中的副本，状态不变
	remote read	cache中的副本写回主存，remote core再访问主存获取最新数据，remote core中的cache行和当前cache行状态变为Shared
	remote write	cache中的副本写回主存，其他core再访问主存获取最新数据并修改，状态变为Modified，当前cache行的状态Invalid
Exclusive	local read	从cache中读取，状态不变
	local write	修改cache中的副本，状态变为Modified
	remote read	与其他core共享数据，相应的cache行状态均变为Shared
	remote write	其他core访问主存获取数据并修改，状态变为Modified，当前cache行的状态变为Invalid
Shared	local read	从cache中读取，状态不变
	local write	修改cache中的副本，状态变为Modified，其他core中共享数据的cache行状态变为Invalid
	remote read	其他core访问主存获取数据，状态变为Shared，当前cache行状态不变
	remote write	其他core访问主存获取最新数据并修改，状态变为Modified，当前core状态变为Invalid
Invalid	local read	如果其他core的cache中有这份数据的副本并且已经修改过（状态为Modified），则需要先写回；当前core从主存中读取，如果有其他core共享数据，则相关的core的cahce行的状态均设为Shared，反之当前core的cache行状态设为Exclusive
	local write	如果其他core的cache中有这份数据的副本并且已经修改过（状态为Modified），则需要先写回；当前core从主存中读取，如果有其他core共享数据，则其他的core的cache行状态均设为Invalid，当前core的cache行状态设为Modified
	remote read	状态不变
	remote write	状态不变

注意，所提及的cache行状态是指包含相应数据副本的cache行，例如，如果cache行有64bytes，修改了其中的某些bytes后，该cache行的状态就变为Modified，状态是属于cache行的，而非整个cache。写回操作也是以cache行为进行操作。

通过上述对MESI的描述，可以得知，多个core的状态并非独立的，例如，不可能同时存在两个core的状态是Modified或Exclusive，Shared状态的core的数量不能少于2。

	M	E	S	I
M	×	×	×	√
E	×	×	×	√
S	×	×	√	√
I	√	√	√	√

simulation

通过C语言实现一个简单的MESI模拟。
定义枚举类型，包含4种状态。定义cache行的结构体。每个cache行结构体包含一个变量用于缓存数据，并包含一个枚举类型的状态变量。

typedef enum
{
    MODIFIED,
    EXCLUSIVE,
    SHARED,
    INVALID
} state_t;


typedef struct 
{
    state_t state;
    uint32_t data;
} line_t;

为确保不引入cache自身工作原理相关的复杂性，我们用line_t的数组替代整个多核系统的cache，NUM_CORE是系统的核心数，每个核心编号为0~NUM_CORE - 1，核心i的cache为cache[i]，即一个line_t，程序中我们只会操作每个core对应的line_t。
state_count用于跟踪当前系统中各core的cache行的状态的数量。state_ch是用于debug的数组，根据cache行的状态简单地标识一个输出信号。全局变量mem_data用于表示内存中的一个数据，结构体line_t中的变量就是用来缓存该全局变量的。程序中模拟访问内存中的数据只会使用该变量。同时，定义两个全局静态变量，modified_idx和exclusive_idx，分别跟踪当前系统中状态为Modified或Exclusive的cache行所在的core的编号。

typedef line_t cache_t[NUM_CORE]; // cache lines
uint32_t state_count[4];            // cache line state count
char state_ch[4] = 
{'M', 'E', 'S', 'I'};               // cache line state character
cache_t cache;                      // cache
uint32_t mem_data = 6828;           // memory data

static uint32_t modified_idx, exclusive_idx;

定义一个检查当前多核系统中各core的cache行状态是否合法的函数，防止系统cache行经过多次改变后进入了一个不可能存在的情况（例如多个Modified和Exclusive）。一个打印函数，输出当前系统中各个core的cache行的状态和数据副本、state_count的值以及全局变量的值。

int check_cache_state()
{
    // 需要满足：1. M或E的状态数不能超过1，且S状态数大于1，剩余状态均是I，或均是I
    if (((state_count[MODIFIED] == 1 || state_count[EXCLUSIVE] == 1) && state_count[INVALID] == NUM_CORE - 1) 
        || (state_count[SHARED] > 1 && state_count[INVALID] == NUM_CORE - state_count[SHARED])
        || state_count[INVALID] == NUM_CORE)
        return 0;
    return 1;
}


void print_cache()
{
    for (int i = 0; i < NUM_CORE; ++i)
        printf("[%d] %c %d\n", i, state_ch[cache[i].state], cache[i].data);
    for (int i = 0; i < 4; ++i)
        printf("%c %d\t", state_ch[i], state_count[i]);
    printf("\nmemory: %d\n", mem_data);
}

定义读取函数，给定一个core编号，表示该core读取数据。我们每次操作均需要根据当前情况，该边当前core甚至其他core的cache行的状态，以及更新state_count数组和两个static变量。

void read_line(uint32_t idx, uint32_t * pd)
{
    // 如果当前cache行的状态为无效
    if (cache[idx].state == INVALID)
    {
        // 1.如果其他core没有这份数据，当前core的数据从内存获得，cache行状态变为E
        if (state_count[INVALID] == NUM_CORE)
        {
            cache[idx].state = EXCLUSIVE;
            cache[idx].data = mem_data;

            // update state to EXCLUSIVE
            --state_count[INVALID];
            ++state_count[EXCLUSIVE];
            exclusive_idx = idx;

            #ifdef DEBUG
            printf("[%d] read miss; read from memory data %d\n", idx, cache[idx].data);
            #endif
        }
        // 2.如果其他core有这份数据，且状态为M
        else if (state_count[INVALID] == NUM_CORE - 1 && state_count[MODIFIED] == 1)
        {
            // write back
            #ifdef DEBUG
            printf("[%d] read miss; [%d] write back; update memory from %d to %d; read from other line data %d\n", 
                idx, modified_idx, mem_data, cache[modified_idx].data, mem_data);
            #endif
            mem_data = cache[modified_idx].data;

            // read from M cache line
            cache[idx].data = cache[modified_idx].data;

            // update state to SHARED
            cache[modified_idx].state = cache[idx].state = SHARED;
            --state_count[MODIFIED];
            --state_count[INVALID];
            state_count[SHARED] = 2;
        }
        // 3. 如果其他core有这份数据，且状态为S或者为E
        else
        {
            #ifdef DEBUG
            printf("[%d] read miss; broadcast shared; read from other line; data %d\n", idx, cache[idx].data);
            #endif
            // update state
            cache[idx].state = SHARED;
            --state_count[INVALID];
            ++state_count[SHARED];
            if (state_count[EXCLUSIVE] == 1) // 存在一个E状态的core
            {       
                cache[exclusive_idx].state = SHARED;
                --state_count[EXCLUSIVE];
                ++state_count[SHARED];
                // read from E line
                cache[idx].data = cache[exclusive_idx].data;
            }
            else
            {
                for (int i = 0; i < NUM_CORE; ++i)
                {
                    // read from S line
                    if (i != idx && cache[i].state == SHARED)
                    {
                        cache[idx].data = cache[i].data;
                        break;
                    }
                }
            }
        }
    }
    else
    {
        #ifdef DEBUG
        printf("[%d] read hit;  data %d\n", idx, cache[idx].data);
        #endif
    }

    *pd = cache[idx].data;
}

接下来是写操作，给定core的编号和一个数据，表示该core进行了一个写操作。

void write_line(uint32_t idx, uint32_t * pd)
{
    if (cache[idx].state == MODIFIED)
    {
        #ifdef DEBUG
        printf("[%d] write hit; update data from %d to %d\n", idx, cache[idx].data, *pd);
        #endif
        cache[idx].data = *pd;
    }
    else if (cache[idx].state == EXCLUSIVE)
    {
        #ifdef DEBUG
        printf("[%d] write hit; write data %d\n", idx, *pd);
        #endif
        // update state
        cache[idx].state = MODIFIED;
        --state_count[EXCLUSIVE];
        ++state_count[MODIFIED];
        cache[idx].data = *pd;   
        modified_idx = idx;
    }
    else if (cache[idx].state == SHARED)
    {
        #ifdef DEBUG
        printf("[%d] write hit; broadcast invalid; write %d\n", idx, *pd);
        #endif
        // update state
        cache[idx].state = MODIFIED;
         --state_count[SHARED];
        ++state_count[MODIFIED];
        cache[idx].data = *pd;
        modified_idx = idx;

        // update other shared core to invalid
        for (int i = 0; i < NUM_CORE && state_count[SHARED]; ++i)
        {
            if (cache[i].state == SHARED)
            {
                cache[i].state = INVALID;
                ++state_count[INVALID];
                --state_count[SHARED];
            }
        }
    }
    else
    {
        #ifdef DEBUG
        printf("[%d] write miss\n", idx);
        #endif
        // 如果其他core中保存有data且状态为M，则先写回其他core
        if (state_count[MODIFIED] == 1)
        {
            #ifdef DEBUG
            printf("[%d] write back %d\n", modified_idx, cache[modified_idx].data);
            #endif
            mem_data = cache[modified_idx].data;
            cache[modified_idx].state = INVALID;
            --state_count[MODIFIED];
            ++state_count[INVALID];
        }
        // read from memory and write
        #ifdef DEBUG
        printf("[%d] read from memory %d; update to %d\n", idx, mem_data, *pd);
        #endif
        cache[idx].data = mem_data;
        cache[idx].data = *pd;

        // update state
        cache[idx].state = MODIFIED;
        --state_count[INVALID];
        ++state_count[MODIFIED];
        modified_idx = idx;
        // update other core state  
        if (state_count[EXCLUSIVE] == 1)
        {
            cache[exclusive_idx].state = INVALID;
            --state_count[EXCLUSIVE];
            ++state_count[INVALID];
        }
        else if (state_count[SHARED] > 0)
        {
            for (int i = 0; i < NUM_CORE && state_count[SHARED]; ++i)
            {
                if (cache[i].state == SHARED)
                {
                    cache[i].state = INVALID;
                    ++state_count[INVALID];
                    --state_count[SHARED];
                }
            }
        }
    }
}

再定义了一个evict操作，表示当前cache行被替换了，可能进行写回操作

void evict_line(uint32_t idx, uint32_t * pd)
{
    #ifdef DEBUG
    printf("[%d] evict", idx);
    #endif
    // if modified, write back
    if (cache[idx].state == MODIFIED)
    {
        #ifdef DEBUG
        printf("; write back %d", cache[idx].data);
        #endif
        mem_data = cache[idx].data;
        *pd = cache[idx].data;
    }
    #ifdef DEBUG
    printf("\n");
    #endif
    --state_count[cache[idx].state];
    cache[idx].state = INVALID;
    ++state_count[INVALID];

    // if S state count is 1, update it to E
    if (state_count[SHARED] == 1)
    {
        for (int i = 0; i < NUM_CORE; ++i)
            if (cache[i].state == SHARED)
            {
                cache[i].state = EXCLUSIVE;
                --state_count[SHARED];
                ++state_count[EXCLUSIVE];
                exclusive_idx = i;
                break;
            }
    }
}

最后通过main函数进行模拟和测试。使用随机数选择每次需要进行的操作和相应的core编号，每次操作后，检查当前多核系统是否处于一个合法的状态，若进入了一个不合法状态，则打印一个state error信息，并退出；反之打印pass。

int main(int argc, char **argv)
{
    if (argc != 2)
    {
        printf("usage: ./mesi <times>\n");
        exit(0);
    }
    int times = atoi(argv[1]);
    void (*op_arr[3])(uint32_t, uint32_t *) = {read_line, write_line, evict_line};
    uint32_t idx, op, data;

    srand(15213);

    // 初始化cache
    for (int i = 0; i < NUM_CORE; ++i)
    {
        cache[i].state = INVALID;
        cache[i].data = 0;
    }
    state_count[INVALID] = NUM_CORE;

    for (int i = 0; i < times; ++ i)
    {
        #ifdef DEBUG
        printf("========================================\n");
        #endif
        idx = rand() % NUM_CORE;
        op = rand() % 3;

        #ifdef DEBUG
        switch (op)
        {
            case 0:
                printf("read line <%d>\n", idx);
                break;
            case 1:
                printf("write line <%d>\n", idx);
                break;
            case 2:
                printf("evict line <%d>\n", idx);
                break;
            default:
                exit(1);
        }
        #endif
        if (op == 1)
            data = rand() % 10009;
        op_arr[op](idx, &data);

        if (check_cache_state())
        {
            fprintf(stderr, "state error\n");
            exit(1);
        }
        #ifdef DEBUG
        printf("\n");
        print_cache();
        #endif
    }

    printf("pass\n");

    return 0;
}

编译程序，可以通过定义DEBUG宏定义变量，输出详细的操作过程信息。

1	> gcc -DDEBUG mesi.c -g -o mesi

执行时给出需要执行的次数，查看输出结果

> ./mesi 5
========================================
evict line <1>
[1] evict

[0] I 0
[1] I 0
[2] I 0
[3] I 0
M 0     E 0     S 0     I 4
memory: 6828
========================================
evict line <1>
[1] evict

[0] I 0
[1] I 0
[2] I 0
[3] I 0
M 0     E 0     S 0     I 4
memory: 6828
========================================
read line <3>
[3] read miss; read from memory data 6828

[0] I 0
[1] I 0
[2] I 0
[3] E 6828
M 0     E 1     S 0     I 3
memory: 6828
========================================
write line <3>
[3] write hit; write data 7815

[0] I 0
[1] I 0
[2] I 0
[3] M 7815
M 1     E 0     S 0     I 3
memory: 6828
========================================
write line <1>
[1] write miss
[3] write back 7815
[1] read from memory 7815; update to 5828

[0] I 0
[1] M 5828
[2] I 0
[3] I 7815
M 1     E 0     S 0     I 3
memory: 7815
pass

默认core的数量是4，调整到64，以及更多的操作次数，取消DEBUG的编译标识，查看运行结果

1
2
3

> gcc mesi.c -g -o mesi
> ./mesi 123456789
pass

伪共享

伪共享就是多线程操作位于同一缓存行的不同变量时，由于缓存失效而引发性能下降的问题。例如，假设有2个线程运行在不同core上，cache行大小为64bytes，线程访问两个相邻的int变量a和b，因此两个core的cache中会分别缓存这两个变量。由于每次cache会直接读入64bytes，因此这两个相邻的变量可能同时被读入了cache行。当前两个core中均缓存了a和b且在同一行上，根据MESI，当两个线程操作这两个看似无关的变量时，会不断触发remote write，反复写回一个core的cache行，而另一个core重新访问内存，造成了性能的降低。“真”共享就是两个core访问内存区的同一变量。
通过一个示例程序，查看伪共享、“真”共享和“无”共享的情况下的性能对比。程序中，通过创建两个线程，执行同一函数，对两个变量进行自增操作，这两个变量是相邻的（伪共享）、相同的（“真”共享）或相隔较远的（保证不再同一cache行）。线程执行自增任务之前，根据传入的参数，将自己绑定到指定的core上执行。
查看cache的行大小

> getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  524288
LEVEL2_CACHE_ASSOC                 8
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  16777216
LEVEL3_CACHE_ASSOC                 0
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  
LEVEL4_CACHE_ASSOC                 
LEVEL4_CACHE_LINESIZE

查看页大小

1 2	> getconf PAGE_SIZE 4096

在程序中预定义常量CACHELINE_SIZE为64，设置数组占64bytes

#define TIMES (1e8)
#define CACHELINE_SIZE (64)

// 线程执行需要传入的参数
typedef struct
{
    uint64_t * ptr;      // 访问的内存地址
    uint32_t cpu_id;     // 需要绑定的core
    uint32_t times;      // 自增操作次数
} param_t;

// 线程访问的变量
uint64_t val1[CACHELINE_SIZE / sizeof(uint64_t)];
uint64_t val2[CACHELINE_SIZE / sizeof(uint64_t)];
uint64_t val3[CACHELINE_SIZE / sizeof(uint64_t)];
uint64_t val4[CACHELINE_SIZE / sizeof(uint64_t)];

定义worker函数，即线程执行的函数，会输出tid、所在的core、访问的内存地址和操作后的数值。

void * worker(void * param)
{
    param_t * p = (param_t *)param;
    cpu_set_t mask;

    // bind to core[core_id]
    CPU_ZERO(&mask);
    CPU_SET(p->cpu_id, &mask);
    if (pthread_setaffinity_np(pthread_self(), sizeof(mask), &mask) == -1)
        exit(1);
    while (p->times--)
        ++(*(p->ptr));
    printf("T[%d] run on core <%d> result %#x: %ld\n", pthread_self(), sched_getcpu(), p->ptr, *p->ptr);
    return NULL;
}

模拟无共享，两个线程分别访问&val1[0]和&val2[0]，理论上这两个地址相隔64bytes，存放在不同的cache行中

void no_sharing()
{
    pthread_t t1, t2;

    param_t param1 = 
    {
        .ptr = &val1[0],
        .cpu_id = 0,
        .times = TIMES
    };

    param_t param2 = 
    {
        .ptr = &val2[0],
        .cpu_id = 1,
        .times = TIMES
    };

    clock_t start = clock();

    pthread_create(&t1, NULL, worker, &param1);
    pthread_create(&t2, NULL, worker, &param2);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("======================[NO]\tcost %ld\n", clock() - start);
}

模拟伪共享，两个线程访问的内存地址分别为&val3[0]和&val3[1]，很可能处于同一cache行中（也可能刚好处于不同行中），运行后可以通过查看虚拟地址判断。

void false_sharing()
{
    pthread_t t1, t2;

    param_t param1 = 
    {
        .ptr = &val3[0],
        .cpu_id = 0,
        .times = TIMES
    };

    param_t param2 = 
    {
        .ptr = &val3[1],
        .cpu_id = 1,
        .times = TIMES
    };

    clock_t start = clock();

    pthread_create(&t1, NULL, worker, &param1);
    pthread_create(&t2, NULL, worker, &param2);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("======================[FALSE]\tcost %ld\n", clock() - start);
}

模拟真共享，两个线程访问同一内存地址，即&val4[0]。

void true_sharing()
{
    pthread_t t1, t2;

    param_t param1 = 
    {
        .ptr = &val4[0],
        .cpu_id = 0,
        .times = TIMES
    };

    param_t param2 = 
    {
        .ptr = &val4[0],
        .cpu_id = 1,
        .times = TIMES
    };

    clock_t start = clock();

    pthread_create(&t1, NULL, worker, &param1);
    pthread_create(&t2, NULL, worker, &param2);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("======================[TRUE]\tcost %ld\n", clock() - start);
}

main函数运行三个测试函数

int main()
{
    no_sharing();
    false_sharing();
    true_sharing();
}

运行，查看结果

> ./false_sharing
T[140737351505472] run on core <0> result 0x55558040: 100000000
T[140737343112768] run on core <1> result 0x55558080: 100000000
======================[NO]      cost 1646328
T[140737343112768] run on core <0> result 0x555580c0: 100000000
T[140737351505472] run on core <1> result 0x555580c8: 100000000
======================[FALSE]   cost 2323293
T[140737343112768] run on core <1> result 0x55558100: 124568282
T[140737351505472] run on core <0> result 0x55558100: 142349628
======================[TRUE]    cost 3019775

可见，no sharing执行的时间最短，两个线程访问的内存地址（虚拟地址）分别为0x55558040和0x55558080，页大小为4KB，两个地址的页偏移为0x40和0x80，虽然我们不知道访问的具体物理地址是多少，但是可以确定这两个地址位于同一物理页框，因为它们的虚拟页号是相同的。0x40和0x80读入的cache行是不同的，因此符合no sharing，执行时间最短。
同理，false sharing访问的地址为0x555580c0和0x555580c8，虚拟页号相同，物理页框也相同，cache行大小为64bytes，0xc0和0xc8确定的cache索引号是相同的，块内偏移不同，因此这两个内存区域的数据会读入同一行。
true sharing的执行时间最长。