自写仿真器的cache算法的实现规范

发表于 | 阅读次数:

代码实现的规范:
首先创建自己对应的PUD-LRU的C文件和头文件(clion自动提示生成),在initFlash函数段中添加自己的初始化函数,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//    选择相应的缓冲区算法
    switch(cache_type){
//        LRU
        case 1: cache_op=LRU_op_setup();break;
//        CFLRU
        case 2: cache_op=CFLRU_op_setup();break;
//        AD-LRU
        case 3: cache_op=ADLRU_op_setup();break;
//        CASA
        case 4: cache_op=CASA_op_setup();break;
//        LRU-WSR
        case 5: cache_op=LRUWSR_op_setup();break;
//         CCF-LRU
        case 6:cache_op=CCFLRU_op_setup();break;
//            块级的FAB算法
        case 7:cache_op=FAB_op_setup();break;
//            BPLRU算法
        case 8:cache_op=BPLRU_op_setup();break;
        
//      case 9:cache_op=PUD_op_setup(); break;
    }

之后关于每个缓冲算法的接口标准;

1
2
3
4
5
6
7
8
9
//加入自己的cache_type类型的函数指针结构
struct cache_operation{
    int  (*init) (int size,int blk_num);
    int (*SearchCache)(int LPN,int operation);
    int (*HitCache)(int LPN, int operation,int index);
    double (*AddCacheEntry)(int LPN,int operation);
    double (*DelCacheEntry)(int LPN,int operation);
    void (*end) ();
};

以LRU算法的实现,做代码实现的参考标准,在对应的头文件生命如下的函数:

1
struct cache_operation * LRU_op_setup();

在对应的LRU.c文件的底部定义

1
2
3
4
struct cache_operation * LRU_op_setup()
{
    return &LRU_Operation;
}

再针对这个全局变量的函数指针结构体进行赋值操作(也就是指定对应的函数)

1
2
3
4
5
6
7
8
struct cache_operation LRU_Operation={
        init:   LRU_init,
        SearchCache:    LRU_Search,
        HitCache:   LRU_HitCache,
        AddCacheEntry:  LRU_AddCacheEntry,
        DelCacheEntry:  LRU_DelCacheEntry,
        end:    LRU_end
};

之后在这个结构体之前定义上述的几个函数

1
2
3
4
5
6
7
8
9
10

int LRU_init(int size, int DataBlk_Num);
//释放对应的内存
void LRU_end();
//返回匹配的命中请求在数组中的位置
int LRU_Search(int LPN,int operation);
int LRU_HitCache(int LPN,int operation,int Hit_kindex);
double LRU_AddCacheEntry(int LPN,int operation);
//不管缓冲区是否满都调用该函数（满）
double LRU_DelCacheEntry(int ReqLPN,int ReqOperation);

注意这些函数外部可调用的函数,自己的内部函数可在对应的文件中定义,例如LRU.c中定义了自己使用的函数

1
2
3
//找到数组中索引对应的LPN的age最大或最小,同时添加返回数组最值的索引
int my_find_cache_min(int *arr,int arrMaxSize,int * index);
int my_find_cache_max(int *arr,int arrMaxSize,int *index);

关于双链表的使用实现,已经封装在List.c中,可直接调用以下函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//创建双向链表
pNode CreateList();
//删除整个链表，释放内存（这里有点小问题)
void FreeList(pNode pHead);
//判断链表是否为空
int IsEmptyList(pNode pHead);
//返回链表的长度
int GetListLength(pNode pHead);
//从链表中找到特定的LPN值，并返回节点的指针位置,如果不存在返回NULL
pNode FindLPNinList(pNode pHead,int LPN);
//该函数完成指定节点的指针返回,根据指定的位置返回节点的指针
pNode FindIndexNode(pNode pHead,int index);
//向链表中删除节点，删除位置的节点
int DeleteEleList(pNode pHead,int pos);
//将命中的节点移动到指定队列pHead的第一个位置（MRU）
int MoveToMRU(pNode pHead,pNode Hit);
//这个函数返回的是删除页的状态（是否为脏页），关于删除的页编号通过传值参数DelLPN改变
int DeleteLRU(pNode pHead,int *DelLPN);
//将一个全新的节点添加到队列的MRU位置
int AddNewToMRU(pNode pHead,pNode New);
//查看链表中的节点是否存在干净页节点,如果不存在干净页则返回NULL
pNode IsCleanNodeInList(pNode pHead);
//基于二次机会的冷探测机制,找到节点中isCold的节点,并返回该节点
pNode FindColdNodeInList(pNode pHead);
//删除链表中指定Victim的节点,函数返回的是删除节点对应的LPN号
int DelVictimNodeInList(pNode pHead,pNode Victim);
//无论热区还是冷区,选择剔除的时候都是优先置换干净页,之后基于二次机会遍历选择脏页
//函数返回的是需要剔除页的节点指针
pNode FindVictimNode_CleanFirst(pNode pHead);

上述的双链表的节点表示的是数据页(用以实现纯页级的缓冲区算法),其节点的定义

1
2
3
4
5
6
7
8
9
//定义节点,双链表需要复用的节点定义
typedef struct Node
{
    int LPN;
    struct Node *Pre;
    struct Node *Next;
    int isD;
    int isCold;
}Node ,*pNode;

实现块级的缓冲区算法,则需要用到双链表的部分操作也封装在BlkList的文件中,其操作的节点类型结构:

1
2
3
4
5
6
7
8
9
//定义节点,节点是块的节点
typedef struct BlkNode
{
    int BlkNum;
    struct BlkNode *Pre;
    struct BlkNode *Next;
    int BlkSize;
    int list[PAGE_NUM_PER_BLK];
}BlkNode ,*pBlkNode;

相应可使用的函数操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/创建块索引的双向链表
pBlkNode CreateBlkList();
//删除整个链表，释放内存
void FreeBlkList(pBlkNode pHead);
//判断链表是否为空
int IsEmptyBlkList(pBlkNode pHead);
//计算链表长度
int GetBlkListLength(pBlkNode pHead);
//遍历链表，寻找链表中对应的数据，若存在则返回该节点的指针
pBlkNode  SearchBlkList(pBlkNode pHead,int BlkNum);
//返回以块节点组织的cache大小-->当前的缓冲区的大小
int BlkGetCacheSize(pBlkNode pHead);
//将新的节点加到MRU位置
int BlkAddNewToMRU(pBlkNode pHead,pBlkNode p_new);
//将命中的数据块移动队列的头部
int BlkMoveToMRU(pBlkNode pHead,pBlkNode pHit);
//LRU补偿机制,将判断为连续请求的块移动到LRU
int BlkMoveToLRU(pBlkNode pHead,pBlkNode pHit);
//根据请求的LPNz找到对应的块节点的指针
//函数也可以通过Hit查看对应的LPN是否存在缓冲区中
pBlkNode FindHitBlkNode(pBlkNode pHead,int LPN,int *Hit);
//删除块链表中指定的节点,放回删除节点的包含的页的个数
int BlkDeleteNode(pBlkNode pHead,pBlkNode Victim);

最后需要注意的是,代码实现的过程中的参数命名规范,一般以对应的算法命名其全局变量或外部变量:
_”XXX_CACHE_SIZE”_ 以LRU为例看其变量命名:

1
2
3
4
5
6
7
8
9
10
11
12
struct LRU_Cache_entry *LRUPage;
unsigned int LRUPage_Num;//只表示总的数据页
//定义当前的cache的age最小的索引
int LRU_min_age_index;
int LRU_max_age_index;

//缓冲区最大的大小设置
int LRU_Cache_Max_Entry;
//当前缓冲区的个数
int LRU_Cache_Num_Entry;
//下面表示存储LPN的数组
int *lru_cache_arr;

针对额外的外部函数需要实现公用的直接创建issue讨论,在代码实现前,先提交一份iusse伪代码方便代码交流,变量命名需要规范.

热评文章