#include "LRU.h"
LRU::LRU()
{
for (int i = 0; i < DEFBUFSIZE; i++)
{
ftop[i] = -1;
ptob[i] = NULL;
memset(buf[i].field,'\0',FRAMESIZE);
}
lru = NULL;
mru = lru;
hit = 0;
total = 0;
flashreadcount = 0;
flashwritecount = 0;
}
LRU::~LRU()
{
//释放lru链表
LRUElement * p = mru;
while (p != NULL)
{
mru = mru->LessRecent;
delete p;
p = mru;
}
lru = mru = NULL;
//释放控制块节点
LRUBCB * pb= NULL;
LRUBCB * head = NULL;;
for (int i = 0; i<DEFBUFSIZE; i++)
{
head = ptob[i];
pb = head;
while (pb != NULL)
{
head = head->next;
delete pb;
pb = head;
}
}
pb = head = NULL;
maplist.clear();
}
void LRU::Init()
{
//释放lru链表
LRUElement * p = mru;
while (p != NULL)
{
mru = mru->LessRecent;
delete p;
p = mru;
}
lru = mru = NULL;
//释放控制块节点
LRUBCB * pb= NULL;
LRUBCB * head = NULL;;
for (int i = 0; i<DEFBUFSIZE; i++)
{
head = ptob[i];
pb = head;
while (pb != NULL)
{
head = head->next;
delete pb;
pb = head;
}
}
pb = head = NULL;
/*初始化缓冲区*/
for (int i = 0; i < DEFBUFSIZE; i++)
{
ftop[i] = -1;
ptob[i] = NULL;
memset(buf[i].field,'\0',FRAMESIZE);
}
hit = 0;
total = 0;
flashreadcount = 0;
flashwritecount = 0;
}
int LRU::FixPage(int page_id)
{
ASSERT(page_id >= 0);
int frid = -1;
int rv = -1;
int hk = hash(page_id);
LRUBCB* pb = NULL;
pb = PageToLRUBCB(page_id);
/*读计数加1*/
total++;
/*若该页在缓冲区中已存在*/
if (pb != NULL)
{
frid = pb->frame_id;
AdjustLRUList(frid);
/*命中次数加1*/
hit++;
return frid;
}
else // 若该页不在缓冲区中
{
frid = SelectVictim();
/*正常情形下,此时应该从二级存储器读入需要加载的数据*/
rv = f_read_page(page_id,(BYTE *)(buf[frid].field),0,FRAMESIZE);
if(rv == RV_ERROR_INVALID_PAGE_STATE)
{
printf("page readed is invalid\n");
}
if (rv == RV_ERROR_FLASH_BLOCK_BROKEN)
{
printf("the block contained this page is broken \n");
}
flashreadcount++;
ftop[frid] = page_id;
pb = ptob[hk];
/*将新的LRUBCB链接到桶的尾部*/
if ( pb != NULL)
{
while( pb->next != NULL)
{
pb = pb->next;
}
pb->next = new LRUBCB();
pb = pb->next;
}
else //桶为空
{
pb = new LRUBCB();
ptob[hk] = pb;
}
pb->dirty = 0;
pb->frame_id = frid;
pb->page_id = page_id;
pb->next = NULL;
InsertLRUEle(frid);
return frid;
}
}
NewPage LRU::FixNewPage(LBA lba)
{
NewPage np;
np.frame_id = -1;
np.page_id = -1;
int pid = -1;
int frid = -1;
LRUBCB* pb = NULL;
/* 申请分配新数据页 */
f_alloc_page(1,&pid);
if (pid == -1)
printf("there is no free page in the flash memory");
ASSERT(pid >= 0);
/*注册映射项*/
RegistEntry(lba,pid);
/* 在缓冲区中寻找空闲块,用于存储新数据页中的数据*/
frid = SelectVictim();
ftop[frid] = pid;
pb = ptob[hash(pid)];
/*将新的LRUBCB链接到桶的尾部*/
if ( pb != NULL)
{
while( pb->next != NULL)
{
pb = pb->next;
}
pb->next = new LRUBCB();
pb = pb->next;
}
else //桶为空
{
pb = new LRUBCB();
ptob[hash(pid)] = pb;
}
pb->dirty = 0;
pb->frame_id = frid;
pb->page_id = pid;
pb->next = NULL;
InsertLRUEle(frid);
np.frame_id = frid;
np.page_id = pid;
return np;
}
int LRU::UnFixPage(int page_id)
{
ASSERT(page_id >= 0);
LRUBCB *pb = NULL;
pb = PageToLRUBCB(page_id);
int rv = -1;
if(pb->dirty == 1)
{
pb->dirty = 0;
}
rv = f_release_page(page_id);
if (rv == RV_ERROR_INVALID_LBA)
{
printf("Invalid LBA\n");
return rv;
}
return 0;
}
void LRU::ReadFrame(int frame_id,char* buffer)
{
ASSERT(frame_id >= 0 );
ASSERT(buffer != NULL);
memcpy(buffer,buf[frame_id].field,FRAMESIZE);
return;
}
void LRU::WriteFrame(int frame_id,const char* buffer)
{
ASSERT(frame_id >= 0);
ASSERT(buffer != NULL);
memcpy(buf[frame_id].field,buffer,FRAMESIZE);
SetDirty(frame_id);
return;
}
int LRU::WriteDirty()
{
LRUBCB* pb = NULL;
int rv = -1;
for (int i = 0; i < DEFBUFSIZE; i++)
{
pb = ptob[i];
while ( pb != NULL)
{
if (pb->dirty == 1)
{
//程序结束时,我们应该将脏页写回二级存储器
rv = f_write_page(pb->page_id,(BYTE *)(buf[pb->frame_id].field),0,FRAMESIZE);
if (rv == RV_ERROR_FLASH_NO_MEMORY)
{
printf("no more flash memory \n");
return rv;
}
flashwritecount++;
}
pb = pb->next;
}
}
return 0;
}
double LRU::HitRatio()
{
return ((double)(hit)/(double)(total)*100);
}
void LRU::RWInfo()
{
printf("hit is: %d\n",hit);
printf("total is: %d\n",total);
printf("flash read count is: %d\n",flashreadcount);
printf("flash write count is: %d\n",flashwritecount);
return;
}
int LRU::IsLBAValid(LBA lba)
{
ASSERT(lba >= 0);
if(maplist.count(lba))
{
return LBA_IS_VALID;
}
else
{
return LBA_IS_INVALID;
}
}
int LRU::LBAToPID(LBA lba)
{
ASSERT(lba >= 0);
return maplist[lba];
}
void LRU::SetDirty(int frame_id)
{
ASSERT(frame_id >= 0);
int pid = -1;
LRUBCB* pb = NULL;
pid = ftop[frame_id];
pb = PageToLRUBCB(pid);
if (pb->dirty == 0)
{
pb->dirty = 1;
}
return;
}
int LRU::hash(int page_id)
{
ASSERT(page_id >= 0 );
int hk = -1;
hk = page_id % DEFBUFSIZE;
return hk;
}
LRUBCB* LRU::PageToLRUBCB(int page_id)
{
ASSERT(page_id >= 0);
LRUBCB* pb = NULL;
int hk = -1;
hk = hash(page_id);
pb = ptob[hk];
while ( pb != NULL && pb->page_id != page_id)
{
pb = pb->next;
}
return pb;
}
void LRU::RemoveLRUBCB(LRUBCB* pb)
{
ASSERT(pb != NULL);
LRUBCB* head = NULL;
head = ptob[hash(pb->page_id)];
/* 若该LRUBCB正好在桶的首部 */
if (pb == head)
{
/* 如果桶的长度大于1,则需要维护桶的其它部分*/
if ( head->next != NULL)
{
head = head->next;
ptob[hash(pb->page_id)] = head;
ftop[pb->frame_id] = -1;
memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
delete pb;
pb = NULL;
head = NULL;
}
else //若桶中只有一个元素
{
ptob[hash(pb->page_id)] = NULL;
ftop[pb->frame_id] = -1;
memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
delete pb;
pb = NULL;
}
}
else //在桶内需找LRUBCB的正确位置
{
while ( head->next != pb)
{
head = head->next;
}
head->next = pb->next;
ftop[pb->frame_id] = -1;
memset(&(buf[pb->frame_id].field),'\0',FRAMESIZE);
delete pb;
pb = NULL;
head = NULL;
}
return;
}
/* 在LRU置换策略中,每次只需删除lru指向的元素,这里做一般化处理*/
void LRU::RemoveLRUEle(int frame_id)
{
ASSERT(frame_id >= 0);
LRUElement* elem = NULL;
elem = lru;
if (elem == NULL)
{
return;
}
while( (elem != NULL)&&(elem->frame_id != frame_id))
{
elem = elem->MoreRecent;
}
if (elem == NULL)
{
return; //找不到相应的元素
}
else
{
if ( elem == lru) //lru指向要删除的元素
{
if ( elem == mru) //mru也指向要删除的元素
{
lru = mru = NULL;
delete elem;
}
else
{
lru = lru->MoreRecent;
lru->LessRecent = NULL;
delete elem;
}
}
else //在lru策略中能删除除链尾以外的元素,只出现在多线程访问同一元素时(数据锁)
{
if ( elem == mru ) //mru指向要删除的元素
{
mru = mru->LessRecent;
mru->MoreRecent = NULL;
delete elem;
}
else //删除除链头和链尾的元素
{
elem->MoreRecent->LessRecent = elem->LessRecent;
elem->LessRecent->MoreRecent = elem->MoreRecent;
delete elem;
}
}//end elem == lru
return;
}//end elem == NULL
}
void LRU::InsertLRUEle(int frame_id)
{
ASSERT(frame_id >= 0);
LRUElement* elem = NULL;
elem = new LRUElement();
elem->frame_id = frame_id;
elem->LessRecent = NULL;
elem->MoreRecent = NULL;
/* 若链表为空 */
if ( mru == NULL)
{
mru = elem;
lru = mru;
}
else
{
elem->LessRecent = mru;
mru->MoreRecent = el
LRU.rar_LRU缓冲
版权申诉
118 浏览量
2022-09-21
06:48:32
上传
评论
收藏 3KB RAR 举报
邓凌佳
- 粉丝: 65
- 资源: 1万+