一、实验目的
1.掌握4路组相联Cache的组成结构
2.掌握通过物理地址访问Cache的算法
3.掌握Cache替换算法的运用
二、实验要求
按照实验题目的要求，编写程序并上机调试
三、实验设备、环境
计算机、Linux
四、实验步骤及内容
（1）在main中定义char binary[10]，从屏幕上输入10位地址，调用Cache函数查找数据，将数据和Cache输出到屏幕上;定义16行的4路组相联Cache数据结构，假设与内存传输块大小为4B；编写函数char * Cache(char binary[])
（2）参数为10位物理地址，根据参数访问Cache，并返回读取结果。返回值为4字节的二进制数，读取Cache的替换算法为LRU算法。
（3）Cache的算法：1.划分地址；2.根据索引查找哪一组;3.比对CacheTag;4.如果比对成功则需要判定Valid，判定成功返回CacheData，否则未查找到;6.未查找到应当从内存中读取数据到Cache中并返回数据，如果Cache已满需要根据LRU算法替换出一块，具体方法是将count最大的项替换出去，建议单独写一个函数刷新count值。
提示：
1.Cache可以定义为全局变量。
2.注意返回结果应当为32位大小的字符数组，使用malloc函数生成char数组并返回。
3.注意Cache使用了替换算法，因此Cache的结构中需要加入计数器，注意Cache应该为结构体数组，结构体定义为char Valid ; char CacheTag[6];char CacheData[32];int count。
4.测试需要模拟替换，但是实际上并没有内存来进行读取，所以本题目使用固定的值10001000100010001111111111111111来进行替换。即当发生替换时，直接将以上32位数据存入Cache的块中。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NUM 16
#define GROUPNUM 4 //一组个数

struct S_Cache
{
    char Valid;
    char CacheTag[7];
    char CacheData[33];
    int count;
} Caches[NUM];

char *Cache(char binary[]);
void data_input();

int main()
{
    data_input();
    char binary[10];
    char *rnum;
    int i;
    for ( i = 0; i < 3; i++)
    {
        gets(binary);
        rnum = Cache(binary);
        printf("返回应为%s\n", rnum);
    }
    for ( i = 0; i < 8; i++)
    {
        printf("%c %s %s %d\n", Caches[i].Valid, Caches[i].CacheTag, Caches[i].CacheData, Caches[i].count);
    }

    return 0;
}

void data_input() // 输入测试用Cache数据
{
    int i;
    for ( i = 0; i < NUM; i++)
    {
        scanf("%c %s %s %d", &Caches[i].Valid, Caches[i].CacheTag, Caches[i].CacheData, &Caches[i].count);
        getchar();
    }
}

char *Cache(char binary[])
{
    int i;
    int num = 0;
    int n = 0, m = 0;
    char *str = (char *)malloc(sizeof(char) * 32);
    n = ((binary[6] - '0') << 1) + binary[7] - '0'; //组号
    m = ((binary[8] - '0') << 1) + binary[9] - '0'; //块内地址
    for ( i = 0; i < NUM; i++)                   //找到cacheTag
    {
        if (n == i / GROUPNUM && m == i % GROUPNUM)
        {
            num = i;
            break;
        }
    }
    printf("n = %d, m = %d, num = %d\n", n, m, num);
    if (strncmp(binary, Caches[num].CacheTag, 6) == 0 && Caches[num].Valid == '1') //对比cacheTag,中标
    {
        for (i = num + 3; i >= 0; i--) //替换算法最近最少用（LRU） 一组四个，所以这组最大不大于num+3
        {
            if (n == i / 4)
            {
                if (Caches[i].count < Caches[num].count)
                    Caches[i].count++;
            }
            else if (n > i / 4)
                break;
        }
        Caches[num].count = 0;
        strcpy(str, Caches[num].CacheData);
    }
    else
    {
        for ( i = num + 3; i >= 0; i--)
        {
            if (n == i / 4)
            {
                if (Caches[i].count == 3)
                    num = i;
                Caches[i].count++;
            }
            else if (n > i / 4)
                break;
        }
        Caches[num].count = 0;
        strcpy(str, "10001000100010001111111111111111");
        strcpy(Caches[num].CacheData, str);
    }
    return str;
}

实验结果


测试用例

1 000000 00000000000000000000000000000001 1
1 000001 00000000000000000000000000000010 2
1 000010 00000000000000000000000000000011 0
1 000011 00000000000000000000000000000100 3
0 000000 00000000000000000000000000000101 3
1 000001 00000000000000000000000000000110 0
1 000010 00000000000000000000000000000111 1
1 000011 00000000000000000000000000001000 2
0 000000 00000000000000000000000000001001 3
1 000001 00000000000000000000000000001010 1
1 000010 00000000000000000000000000001011 2
1 000011 00000000000000000000000000001100 0
0 000000 00000000000000000000000000001101 3
1 000001 00000000000000000000000000001110 2
1 000010 00000000000000000000000000001111 1
1 000011 00000000000000000000000000000000 0
测试用例：
1:0000000000
2:0000000100
3:1000000000
返回应为0000 0000 0000 0000 0000 0000 0000 0001    //测试命中
返回应为1000 1000 1000 1000 1111 1111 1111 1111	   //测试未命中，有空闲行
返回应为1000 1000 1000 1000 1111 1111 1111 1111	   //测试未命中，无空闲行
1 000000 00000000000000000000000000000001 1
1 000001 00000000000000000000000000000010 2
1 000010 00000000000000000000000000000011 0
1 000011 00000000000000000000000000000100 3
0 000000 00000000000000000000000000000101 3
1 000001 00000000000000000000000000000110 0
1 000010 00000000000000000000000000000111 1
1 000011 00000000000000000000000000001000 2
0 000000 00000000000000000000000000001001 3
1 000001 00000000000000000000000000001010 1
1 000010 00000000000000000000000000001011 2
1 000011 00000000000000000000000000001100 0
0 000000 00000000000000000000000000001101 3
1 000001 00000000000000000000000000001110 2
1 000010 00000000000000000000000000001111 1
1 000011 00000000000000000000000000000000 0