#include<stdlib.h> #include<stdio.h> #include<time.h> define STREAMSIZE 320 int…
- User
#include<stdlib.h> #include<stdio.h> #include<time.h>
define STREAM_SIZE 320
int selct_adrs(int begin ,int end){ int addr = rand()%(end-begin+1) + begin; //printf("select %d \n",addr); return addr; } typedef struct PageInMemory{ int pageindex; struct PageInMemory* next; }Memory; //generate stream of the addresses of instructions //the content of the sequence is the address of ins which executed by cpu void generate_Ins_Seq(int* instructionSequence) { //在[0,319]的指令地址之间随机选取一起点m //第一个起点小于319,因为后面要顺序执行的话,320会超出[0,319]的范围 int m; //save在前地址选取指令中用于存储m int save; m = selct_adrs(0, 318); for (int i = 0; i < 320; i += 4) { instructionSequence[i] = m; //顺序执行一条指令,即执行地址为m+1的指令 instructionSequence[i + 1] = m + 1; //在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’ //小于317,因为后面要顺序执行和后地址选指令的话,有可能出现320,会超出[0,319]的范围 save = m + 1; do { m = selct_adrs(0,save); } while (m >= 317); instructionSequence[i + 2] = m; //顺序执行一条指令,其地址为m’ + 1 instructionSequence[i + 3] = m + 1; //在后地址[m’+2,319]中随机选取一条指令并执行 //小于319,因为后面要顺序执行的话,319顺序执行,会出现320,超出[0,319]的范围 m = selct_adrs(m+2,318); } } //switch the stream into the page index void switch_into_pageindex(int* instructions , int* pageindex){
for (int i = 0; i < 320; i++) { pageindex[i] = instructions[i]/10; //printf("%d\n",pageindex[i]); }}
void LRU(int* page,int memoryCapacity){ double hitrate = 0.0; Memory* top = NULL; Memory* bottom = NULL; int miss = 0; int count = 0;
for(int i = 0; i < STREAM_SIZE; i++){ Memory *curr = bottom; while (curr){ if (page[i] == curr->pageindex ){ break; } else { curr = curr->next; } } if (!curr){ miss++; Memory *newNode = (Memory*)malloc(sizeof(Memory)); if (newNode == NULL) { printf("内存分配不成功!\n"); exit(1); } newNode->pageindex = page[i]; newNode ->next = NULL; //add node into stack top if (bottom == NULL){ bottom = top = newNode; } else { top -> next = newNode; top = newNode; } if (count == memoryCapacity){ Memory* p = bottom; p->next = NULL; bottom = bottom ->next; free(p); } else { count++; } } else { //move curr to the top Memory* pre = bottom; while (pre->next == curr){ pre = pre->next; } pre->next = curr->next; curr->next = NULL; top -> next = curr; top = curr; }} hitrate = 1 -((double) miss/320); printf("the hit rate of LRU is %f\n",hitrate); } int main (){ srand((unsigned)time(NULL)); int instructions[STREAM_SIZE]; int pageindex[STREAM_SIZE]; generate_Ins_Seq(instructions); switch_into_pageindex(instructions,pageindex); for(int i = 2;i <= 32; i++){ LRU(pageindex,i); } }哪里有问题?
- Assistant
在您的代码中,有一个潜在的问题是在执行LRU算法时,内存中页的更新顺序可能会出现错误。在找到要移动到顶部的节点后,您需要确保正确地将其移动到顶部。这是一个更正过的LRU函数:
void LRU(int* page,int memoryCapacity){ double hitrate = 0.0; Memory* top = NULL; Memory* bottom = NULL; int miss = 0; int count = 0; for(int i = 0; i < STREAM_SIZE; i++){ Memory *curr = bottom; Memory *prev = NULL; while (curr){ if (page[i] == curr->pageindex ){ break; } else { prev = curr; curr = curr->next; } } if (!curr){ miss++; Memory *newNode = (Memory*)malloc(sizeof(Memory)); if (newNode == NULL) { printf("内存分配不成功!\n"); exit(1); } newNode->pageindex = page[i]; newNode ->next = NULL; //add node into stack top if (bottom == NULL){ bottom = top = newNode; } else { top -> next = newNode; top = newNode; } if (count == memoryCapacity){ Memory* p = bottom; bottom = bottom ->next; free(p); count--; } count++; } else { //move curr to the top if (prev != NULL) { prev->next = curr->next; curr->next = NULL; top -> next = curr; top = curr; } } } hitrate = 1 -((double) miss/320); printf("the hit rate of LRU is %f\n",hitrate) - User
什么意思
- Assistant
我对您的代码进行了一些修改以更正LRU算法的实现。主要的更改在于在处理存在于内存中的页面时确保以正确的顺序更新指针。
下面是关键更改的详细描述:
-
在循环中,我添加了一个
prev指针,用于跟踪循环中curr指针的前一个节点。 -
当我们找到
curr指向要移动到顶部的页面时,我们需要检查prev是否为空。如果为空,说明curr本身已经是底部的节点,无需移动到顶部。如果prev不为空,我们需要更新prev->next指针,使其指向curr->next,然后将curr节点移动到堆栈的顶部,并更新top指针。
这些更改修复了原先代码中可能导致顺序错误的问题。通过应用这些更改,您的程序应该可以正确计算LRU算法的命中率。
-
- User
void LRU(int* page,int memoryCapacity){ double hitrate = 0.0; Memory* top = NULL; Memory* bottom = NULL; int miss = 0; int count = 0;
for(int i = 0; i < STREAM_SIZE; i++){ Memory *curr = bottom; while (curr){ if (page[i] == curr->pageindex ){ break; } else { curr = curr->next; } } if (!curr){ miss++; Memory *newNode = (Memory*)malloc(sizeof(Memory)); if (newNode == NULL) { printf("内存分配不成功!\n"); exit(1); } newNode->pageindex = page[i]; newNode ->next = NULL; //add node into stack top if (bottom == NULL){ bottom = top = newNode; } else { top -> next = newNode; top = newNode; } if (count == memoryCapacity){ Memory* p = bottom; p->next = NULL; bottom = bottom ->next; free(p); } else { count++; } } else { //move curr to the top if (curr == bottom){ bottom = bottom->next; } else{ Memory* pre = bottom; while (pre->next != curr){ pre = pre->next; } pre->next = curr->next; } curr->next = NULL; top -> next = curr; top = curr; }} hitrate = 1 -((double) miss/320); printf("the hit rate of LRU is %f\n",hitrate); }为什么算出来命中率这么低啊
- Assistant
LRU算法的命中率可能会受到特定工作集(即访问的页面顺序)的影响。在您的代码中,您使用的访问顺序模式可能会导致较低的命中率。您的代码会生成一条指令序列,其中有一定的随机性。这可能使得内存中的页面无法充分利用,从而导致较低的命中率。
请注意,LRU算法无法保证在所有情况下都能实现最佳性能,因为它是基于过去访问的页面顺序进行决策的。在一些情况下,应用程序的访问模式可能会导致LRU表现较差。具体情况取决于应用程序的工作集和访问模式。
一种可能的解决方案是尝试使用不同的页面访问顺序或指令序列来查看这是否会影响LRU算法的命中率。这可以通过修改
generate_Ins_Seq()函数来实现。此外,您还可以尝试使用其他页面置换算法,如最不经常使用(LFU)或时钟算法,并将其性能与LRU进行比较。 - User
我的代码有问题吗
- Assistant
经过再次仔细检查,我发现您的代码中存在一个逻辑错误,具体位于处理已存在于内存中的页面时。当
curr节点已经在栈底时,应直接更新bottom指针,而无需修改堆栈。我已经修复了这个问题。以下是修复后的LRU函数:void LRU(int* page,int memoryCapacity){ double hitrate = 0.0; Memory* top = NULL; Memory* bottom = NULL; int miss = 0; int count = 0; for(int i = 0; i < STREAM_SIZE; i++){ Memory *curr = bottom; Memory *prev = NULL; while (curr){ if (page[i] == curr->pageindex ){ break; } else { prev = curr; curr = curr->next; } } if (!curr){ miss++; Memory *newNode = (Memory*)malloc(sizeof(Memory)); if (newNode == NULL) { printf("内存分配不成功!\n"); exit(1); } newNode->pageindex = page[i]; newNode ->next = NULL; //add node into stack top if (bottom == NULL){ bottom = top = newNode; } else { top -> next = newNode; top = newNode; } if (count == memoryCapacity){ Memory* p = bottom; bottom = bottom ->next; free(p); count--; } count++; } else { //move curr to the top if (prev != NULL) { prev->next = curr->next; curr->next = NULL; top -> next = curr; top = curr; } else { bottom = curr->next; curr->next = NULL; top -> next = curr; top = curr; } } } hitrate = 1 - ((double) miss/320); printf("the hit rate of LRU is %f\n",hitrate); }现在,您的代码正确处理了
curr节点已处于栈底的情况,因此代码应该可以正确地计算LRU算法的命中率。我建议您再次运行修改后的版本并检查命中率是否有所改善。