前段时间我在研究怎么在 linux 环境下用 C++ 写一些东西，刚好就拿这个作业练练手。

老师要求用 C++ 实现一种基于 WB 策略的一致性维护的 Cache 模拟器，该模拟器仅考虑4核的 CPU，且每个核只有一级 Cache，Cache 行长度为 64 字节，观察 CPU读、写数据后各个核上 Cache 中数据状态的变化情况。

我思考了一下，准备分三步来完成这个任务：原理学习、程序设计、程序编写。

一些原理

首先要了解 Cache 一致性维护相关的知识。

其实本科学计组时讲过单机系统中的 Cache 一致性问题，但是单机系统中只考虑单个 Cache 与主存之间的数据不一致，通过直写法或回写法就可以简单地解决。而并行计算机体系结构中要考虑多处理机系统中的 Cache 一致性问题，需要考虑不同 Cache 之间、Cache 与主存之间的数据一致性，单纯的直写法或回写法并不能保证多处理机的多数据副本一致。

由于要求实现三状态的 Cache 一致性模拟，所以我先学了一下 MSI 协议。

MSI

MSI 协议将 Cache 中的数据块分为三种状态：

  1. S (Shared) 表示该数据块被共享，正确数据块分别在 Cache 和 Memory 中，或者在不同的 Cache 中。
  2. M (Modified) 表示该数据块在系统中唯一正确。
  3. I (Invalid) 表示该数据块无效。

这三种状态之间的转换由四种操作来决定：

  • 本地读：本地处理机对该数据块读。

    • M：不变
    • S：不变
    • I：变 S

  • 本地写：本地处理机对该数据块写。

    • M：不变
    • S：变 M
    • I：变 M

  • 远程读：远程处理机对该数据块读。

    • M：变 S
    • S：不变
    • I：不变

  • 远程写：远程处理机对该数据块写。

    • M：变 I
    • S：变 I
    • I：不变

大概就长下面这样：

MSI 状态转移图

WB

在单机系统中，回写策略指被修改的 Cache 行只有在被替换时才将修改的内容写回内存中。而多机系统中的回写策略还要考虑 Cache 行与主存块的状态变化。这种变化在两种情形下发生，一种是 Cache 未命中时与主存替换，另一种是当无效的数据块被读取时，唯一正确数据写回主存并传递给无效数据块所在的 Cache。

当 Cache 未命中并发生替换时，写回对应主存块的状态变化如下：

  1. 若 Cache 行的状态为 I，则无需写回。
  2. 若 Cache 行的状态为 M，则写回并将主存中对应块状态置为 M。
  3. 若 Cache 行的状态为 S，无需写回（共享状态下，主存中的数据也一定是正确的）。判断当前共享数量是否为1，若为1则将主存对应块状态置为 M。

对于替换进 Cache 的数据块，考虑 Cache 行的状态：

  1. 内存块为 M，则一起置 S。
  2. 内存块为 S，Cache 行置 S。
  3. 内存块为 I，Cache 行置 I。

实现

了解 Cache 一致性的原理之后，我就开始了程序的设计。因为重点是对协议的模拟，只需要模拟出状态的变化，无需实现数据的真实传输，同时我不想去实现复杂的替换策略，也不希望模拟太大的主存空间，于是我就大胆做出了如下假设：

  1. 4个 Cache 都只包含 1 个 Cache 行。
  2. 主存地址范围 0~9。

这样以来，我只需要实现一个 Cache 类、一个 Memory 类以及一个控制全局的 Controll 类即可。

遇到的一些问题

继承中的构造函数

我发现 Cache 类与 Memory 类有很多相似的地方，所以就写了一个 Device 父类做继承。但是在实现的过程中，发现子类的构造函数总是报错，上网搜了一圈才发现原因。

大致来说是因为父类的构造函数是不能被子类继承的，构造原则如下：

  1. 如果子类没有定义构造方法，则调用父类的无参数构造方法。
  2. 如果子类定义了构造方法，在创建子类对象时，首先执行父类的无参数构造方法，然后再执行自己的构造方法。
  3. 如果父类只定义了有参数构造函数，子类的构造函数没有显示调用父类构造函数，则出错。也就是说如果父类只有有参数的构造方法，子类必须显示调用此带参构造方法。

所以解决问题方法就是，父类同时定义带参构造方法以及空的无参构造方法，然后子类就可以定义自己的构造方法了。

静态成员数组的访问

最开始的时候，我写了一个表示状态的 Status 类，并在其中用 constexpr static 关键字定义了一个 char 类型的静态数组 mp[]，但是在后续使用的时候发现报错。

后来发现常量表达式(constexpr)在编译期就可以计算出结果，所以不能在数组中用变量下标，只能用常量下标。于是我就大笔一挥，把constexpr给去掉了。

整体设计思路

写一个控制器Controll，控制器通过run()方法运行，在run()方法中会要求用户输入要访问的 Cache 的 id、要进行的读或写操作op以及数据块的地址address，然后根据操作的不同调用read()或write()。上述被调用的两个方法在访问数据块时先通过visit()判断 Cache 是否命中，如果未命中则需要替换change()，然后再根据是本地读写或是远程读写来进行相应的状态变化。run()在最后会打印出各个 Cache 以及主存中的状态。

Status

1
2
3
4
5
6
7
8
9
10
11
12
#ifndef STATUS_H
#define STATUS_H

class Status{
    public:
        constexpr static int M=1;
        constexpr static int S=2;
        constexpr static int I=3;
        char mp[4]={' ','M','S','I'};
};

#endif

Device

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef DEVICE_H
#define DEVICE_H

class Device{
    public:
        int id;
        int address;
        int status;

        Device();
        Device(int id,int address,int status);
        int get_id();
        int get_address();
        char get_status();
        void toS();
        void toI();
        void toM();
        virtual void print();
};

#endif

Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef CACHE_H
#define CACHE_H

#include"Device.h"

class Cache:public Device{
    public:
        Cache();
        Cache(int id,int address,int status);
        void print();
        void l_r();
        void l_w();
        void r_r();
        void r_w();
        void set_address(int address);
        bool visit(int address);
};

#endif

Memory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef MEMORY_H
#define MEMORY_H

#include"Device.h"

class Memory:public Device{
    public:
        Memory();
        Memory(int id,int address,int status);
        void print();
        bool visit(int address);
};

#endif

Controll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef CONTROLL_H
#define CONTROLL_H

#include"Status.h"
#include"Cache.h"
#include"Memory.h"
#include<queue>

class Controll{
    public:
        Cache c[4];
        Memory m[10];
        int share[10];

        Controll();
        void run();
        void read(int id,int address);
        void write(int id,int address);
        void change(int id,int cache_adr,int mem_adr);
};
#endif

test

1
2
3
4
5
6
7
#include"Controll.h"

int main(){
    Controll ice;
    while(true) ice.run();
    return 0;
}

结果

开源仓库

系统：Linux ubuntu-20.04.6

需要安装 gcc cmake

运行:

到项目目录下：

1
2
3
cmake .
make
./test

随便敲了几个样例，感觉没什么问题。

w 1 1

1
2
3
4
5
6
7
8
not hit!
Cache 0: the status is I,the address is -1.
Cache 1: the status is M,the address is 1.
Cache 2: the status is I,the address is -1.
Cache 3: the status is I,the address is -1.
Memory 0  1  2  3  4  5  6  7  8  9  
Status I  I  I  I  I  I  I  I  I  I  
Share  0  1  0  0  0  0  0  0  0  0

w 1 2

1
2
3
4
5
6
7
8
not hit!
Cache 0: the status is I,the address is -1.
Cache 1: the status is M,the address is 2.
Cache 2: the status is I,the address is -1.
Cache 3: the status is I,the address is -1.
Memory 0  1  2  3  4  5  6  7  8  9  
Status I  M  I  I  I  I  I  I  I  I  
Share  0  1  1  0  0  0  0  0  0  0

w 0 1

1
2
3
4
5
6
7
8
not hit!
Cache 0: the status is M,the address is 1.
Cache 1: the status is M,the address is 2.
Cache 2: the status is I,the address is -1.
Cache 3: the status is I,the address is -1.
Memory 0  1  2  3  4  5  6  7  8  9  
Status I  I  I  I  I  I  I  I  I  I  
Share  0  1  1  0  0  0  0  0  0  0

r 3 2

1
2
3
4
5
6
7
8
not hit!
Cache 0: the status is M,the address is 1.
Cache 1: the status is S,the address is 2.
Cache 2: the status is I,the address is -1.
Cache 3: the status is S,the address is 2.
Memory 0  1  2  3  4  5  6  7  8  9  
Status I  I  S  I  I  I  I  I  I  I  
Share  0  1  3  0  0  0  0  0  0  0

写在最后

这个作业还是比较好做的，其实可以不用C++多文件，整个项目下来可能有点繁琐，但是就是想试一试所以就这么写了。要求用文件读写的方式来做控制，但是还没实现，离 deadline 还有一个多月，到时候可以再补上。

其实一直以来我都是用 c++ 比较多，但是因为以前都在用 devc++ 写算法题，大三以后的课程作业基本都用 python 写了，所以对怎么用 C++ 写小实验还是比较陌生。算是弥补了一直以来的遗憾吧。