一道关于算法应用考研题，讲思路就行了

Question

题目描述
硬盘Cache是用于缓解内存和外存之间速度差的一种机制，Cache硬件通常位于硬盘上，由一个专门的处理器来管理。处理器要读取的数据，如果保存在Cache中，则称为Cache命中，否则就称为Cache未命中，现在提供给你如下信息：
有一个硬盘，Cache大小为16MBytes，以4KBytes为一簇，硬盘上的数据也以4KBytes为一个簇，硬盘和Cache中的数据每次读写都以1个簇为单位，写Cache的函数是write(intaddr,unsignedchar*buf);表示将buf内的数据写到地址为addr的Cache内，所以addr一定是4096的倍数；
处理器读硬盘数据的指令表示为函数为voidread(unsignedintcid,unsignedchar*buf);其功能为读簇号为cid的簇，读取的数据存放在buf中；在这个函数中，需要考虑Cache命中；
Cache中的数据有一定的淘汰机制，目前最多使用的是最久未访问淘汰机制，即Cache中的一个簇，如果未被使用的时间最长，在一次Cache未命中时，将其淘汰出Cache，而用未命中的数据来代替；所以read函数中，需要考虑Cache未命中。现在，本题需要你实现这个read函数，你需要回答如下问题：
给出数据结构，能够用于管理Cache；
结合(1)，请你实现read函数，注意：如果未命中，真正从硬盘中读取数据，请直接使用函数readhd，声明如下：voidreadhd(unsignedintcid,unsignedchar*buf);该函数不需要你实现。
提示：你可以先写出你的程序思路，然后根据这个思路来写你的程序：例如：如果读cache命中，那么…，否则…；如果cache满，那么…，否则…readhd和write的使用方式示例代码如下；
voidread(unsignedintcid,unsignedchar*buf)
{
…
readhd(cid,buf);//读硬盘数据
…
write(addr,buf);//写入cache指定地址
…
}
题目来源及自己的思路
浙江理工2018考研，大家讲下思路就行了，实在想不出什么好的办法，只能用C语言。

Answer 1

16M的硬盘cache且每簇4K，也就是说有4096个簇。为了保证“最久未访问淘汰机制”应使用时间排序，其次为了方便调整簇的顺序可以使用链表。确定完cache的数据结构后，开始设计read函数：首先请求进来，先遍历链表上的簇，然后比对cid，匹配成功（cache命中）就返回buf，若cache没有匹配（cache未命中）就调用readhd函数读取硬盘的数据。并判断cache是否已满。分2种情况（可以直接按情况1处理，分2种是优化，反正题目要求未命中就替换，也没管cache满不满）：1.cache已满将硬盘读取的簇替换到链表开头，初始化时间，并删除链表的最后一个节点。2.cache未满将命中的簇移动到链表开头，并更新时间。

Answer 2

在cache里面分一部分出来进行标识硬盘的哪些数据在cache里面，以及存放时间（也就是一个计数器）；每次查找的时候看看是否有指定的簇，有的话，直接取；否则读硬盘，并做相应的添加或替换