Programming05

在Cache类中实现fetch方法将数据从内存读到Cache(如果还没有加载到Cache)并返回被更新的Cache行的行号(需要调用不同的映射策略和替换策略)

实现三种映射策略(直接映射、全关联映射、组关联映射)和三种替换策略(先进先出、最少使用、最近使用)

简单来说就是模拟一个Cache. README.md只提供了这么一些内容，具体看了看代码的TODO，两个抽象类分别是MappingStrategy.java和ReplacementStrategy.java，我们需要完成继承了他们的几个策略并在Cache.java中完成调用。

映射策略需要完成3种映射，部分方法需要调用父类中的替换策略。

getTag()方法是根据内存的块号，取出高12位tag并将后10位置为0，转换成字符数组返回.
map()方法则是访问Cache类的静态成员，读出对应行的tag与getTag()的结果进行比对，数据有效且tag相等则返回块号的低10位（这里可以不用对总行数取模），否则返回-1.
对于writeCache()方法，由于是直接映射，没有后续调用策略，因此这里从memory读入数据后写进Cache，再返回块号的低10位转成的整数即可。

关联映射的tag就是块号，getTag()直接返回即可。
关联映射的查找范围是整个cache，因此map()需要从0到N-1行调用替换策略的isHit()方法。
同样的，writeCache()方法要先从memory的静态成员中读取data，read()方法的参数应该为以块号作为高位，低位补充10个0的eip，读取长度为cache一行的大小，即一个块的大小Cache.LINE_SIZE_B，然后再调用策略里的writeCache()方法，把读取到的data写入0到N-1行范围内。

这里的组关联映射是4路组关联，一共是1024/4=258=2⁸个组，即组号占8位，标记占22-8=14位

getTag()方法取出高14位tag并将后8位置为0，转换成字符数组返回。
由于是组关联映射，map()需要根据中间的8位组号确认查找的起始点，8位组号为高位，补充低位2个0作为起始行，补充低位两个1作为结束行，调用策略中的isHit()方法。
类似地，组关联中的writeCache()方法需要在memory的静态成员中读取对应的data，处理方式和关联映射是一样的（因为对于同一个块号，读取的块开头地址与结尾地址都一样），然后调用策略的writeCache()方法，把data写入第二点提到的起始行与结束行之间的范围。

需要完成三种策略。

维护一个内容为Integer的队列，从0到N-1个元素是从新到旧的访问顺序。

isHit()方法直接根据起始点访问Cache里的静态成员进行比对即可。
writeCache()方法需要遍历队列，如果队列中的元素在区间内且有效，更新命中指针并把计数器addup加1，注意这里需要维护一个invalid指针，如果队列中的元素在区间内但无效则更新invalid，遍历完成后判断：
- 如果指针未被更新或计数器小于区间长度，说明这个区间没有被填满，需要寻找在区间内序号最小的有效位为false的行，如果invalid被更新了，说明有失效的空行，那么最小的空行号应该是min(start+addup,invalid)，没被更新则说明只是单纯地区间没有被填满，这时候需要把数据写入找到的行并把这个行号写入队列开头。
- 否则说明区间已经被填满了，由于顺序是从新到旧，顺序遍历最后更新的指针即最老访问的行。因此在指针的行处写入数据并在队列中删除原行，重新写入开头。

维护一个时间戳。

isHit()需要在返回前更新时间戳，直接设成++timeStamp.
类似FIFO，writeCache()需要判断区间是否被填满，同样用指针记录最小时间戳，用计数器记录数量，如果没满则找到序号最小的有效位为false的行，如果满了则更新指针行，更新的时候需要多更新一个时间戳。

由于传入参数确保了数据一定在同一个数据块内，所以我们只需要从地址取出高22位的块号，调用映射策略的map()方法，如果为-1说明未命中，需要写入，此时返回调用的writeCache()方法即可，否则说明命中，直接返回map().

修改了一些小bug之后，通过测试。

代码见github.