-2

作为练习（主要是尝试使用指针编写内容的练习），我正在编写缓存模拟，特别是旧 486 中最近使用最少的伪系统。我收到“访问冲突读取位置”错误该行：

int min = treeArray[set]->root->findPLRU();

最初，treeArray 似乎已正确初始化（如果我在开始时暂停程序并查看，一切都应该如此），但是当程序中断并且我深入研究有问题的树的根时t 定义。

我觉得我很可能犯了某种非常基本的指针错误，这导致指向节点的指针在某处“丢失”，但我不知道它可能是什么。我需要做些什么来“坚持”指针值吗？

#include "stdafx.h"
#include "stdlib.h"
#include <conio.h>
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <io.h>

#include "main.h"

//char fn[80];                              // trace filename
int tf;                                     // trace file
trace buf[BUFSZ / sizeof(trace)];           // buffer SIZE
int LRUHits = 0;
int pLRUHits = 0;
int randomHits = 0;
int height;

int cachelinenumber;



//log2 helper function
int log2(int n)
{
int i = 0;
while (n)
{
    n = n >> 1;
    i++;
}
return i - 1;
}

class CacheLine{
public:
int tag;
int access;
CacheLine();
};

class Cache;

class Node{
public:
bool goRight;
Node* left;
Node* right;
int leftCacheLine;
int rightCacheLine;

Node(int depth) // constructor
{
    goRight = false;
    if (depth < height - 1)
    {
        left = new Node(depth + 1);
        right = new Node(depth + 1);
        leftCacheLine = -1;
        rightCacheLine = -1;
    }
    else
    {
        leftCacheLine = cachelinenumber;
        cachelinenumber++;
        rightCacheLine = cachelinenumber;
        cachelinenumber++;
    }
    //printf("Depth: %d, Height: %d, Left: %d, Right: %d\n", depth, height, leftCacheLine, rightCacheLine);
}

~Node()
{
    delete left;
    delete right;
}

int findPLRU()
{
    if (leftCacheLine < 0 || rightCacheLine < 0)
    {
        if (goRight)
        {
            goRight = false;
            return right->findPLRU();
        }
        else
        {
            goRight = true;
            return left->findPLRU();
        }
    }
    else
    {
        if (goRight)
        {
            goRight = false;
            return rightCacheLine;
        }
        else
        {
            goRight = true;
            return leftCacheLine;
        }
    }
}
};

class Tree{
public:
Node* root;
Tree()
{
    root = new Node(0);
}

~Tree()
{
    delete root;
}

};

//cache class
class Cache
{
public:
CacheLine *cache;

int l, k, n, replacementPolicy;
int log2l, log2n;
int access;
Tree** treeArray;
//constructor
Cache(int ll, int kk, int nn, int _replacementPolicy)
{
    l = ll;
    k = kk;
    n = nn;
    replacementPolicy = _replacementPolicy;
    log2l = log2(l);
    log2n = log2(n);

    cache = (CacheLine*)malloc(sizeof(CacheLine)*k*n);

    for (int i = 0; i < k*n; i++)
    {
        cache[i].tag = 0x80000000;
        cache[i].access = 0;
    }

    if (replacementPolicy == 1)
    {
        cachelinenumber = 0;
        treeArray = new Tree*[n];
        for (int i = 0; i < n; i++)
        {
            treeArray[i] = new Tree();
        }
    }
    access = -1;
}

//destructor
~Cache()
{
    free(cache);
}



//test for hit
void hit(int a) 
{
    access++;

    int set = (a >> log2l) & (n - 1);
    int tag = a >> (log2n + log2l);

    CacheLine* c = &cache[set*k];

    for (int i = 0; i < k; i++)
    {
        if (c[i].tag == tag)
        {
            c[i].access = access;
            if (replacementPolicy == 0)
                LRUHits++;
            else if (replacementPolicy == 1)
                pLRUHits++;
            else if (replacementPolicy == 2)
                randomHits++;
            break;
        }
    }

    if (replacementPolicy == 0) //LRU
    {
        int min = 0; 
        int minv = c[0].access;
        for (int i = 1; i < k; i++)
        {
            if (c[i].access < minv)
            {
                minv = c[i].access;
                min = i;
            }
        }
        c[min].tag = tag;
        c[min].access = access;
    }
    else if(replacementPolicy == 1) // pseudoLRU
    {
        int min = treeArray[set]->root->findPLRU();
        c[min].tag = tag;
        c[min].access = access;
    }
    else // random
    {
        srand(clock());
        int randomNumber = rand()%k;
        c[randomNumber].tag = tag;
        c[randomNumber].access = access;
    }
    return;
}
};

void analyse (int l, int k, int n)
{
height = log2(k) + 1;
char fn[] = "ico0.trace";
if ((tf = open(fn, _O_RDONLY | _O_BINARY )) == -1) {
    printf("unable to open file %s\n", fn);
    exit(0);
}

LRUHits = 0;
pLRUHits = 0;
randomHits = 0;
Cache *cache0 = new Cache(l, k, n, 0); // LRU
Cache *cache1 = new Cache(l, k, n, 1); // pseudoLRU
Cache *cache2 = new Cache(l, k, n, 2); // random

int bytes, word0, a, type, burstcount;
int hits = 0;
int tcount = 0;

while (bytes = read(tf, buf, sizeof(buf)))
{
    for (int i = 0; i <  bytes / (int) sizeof(trace); i++, tcount++) 
    {
        word0 = buf[i].word0;
        a = (word0 & ADDRESSMASK) << 2;
        type = (word0 >> TYPESHIFT) & TYPEMASK;
        burstcount = ((word0 >> BURSTSHIFT) & BURSTMASK) + 1;
        cache0->hit(a);
        cache1->hit(a);
        cache2->hit(a);
    }
}
printf("Hits: %d  Total: %d\n", LRUHits, tcount);
printf("Hits: %d  Total: %d\n", pLRUHits, tcount);
printf("Hits: %d  Total: %d\n\n\n", randomHits, tcount);
delete cache0;
delete cache1;
delete cache2;
}


int _tmain(int argc, _TCHAR* argv[])
{
//analyse(16, 1, 8);
analyse(16, 2, 512);
//analyse(16, 4, 256);
//analyse(16, 8, 128);
//analyse(16, 1024, 1);
_getch();
return 0;
}
4

1 回答 1

6

您的问题尚未被提出，可能是因为您的代码仍然无法编译，因为您没有提供main.h.

即使那样，它也会惹恼大多数试图帮助您的人，因为您没有提及ico0.trace防止代码立即退出所需的文件。

你说int min = treeArray[set]->root->findPLRU();访问违反了。

1) 的值set永远不能超过你的大小n，treeArray因为你& n-1输入值的范围。

2）因为你的~Tree()析构函数永远不会被调用，所以总会有一个treeArray[set]->root

3）因为你*总是在任何时候创建新的left&right节点leftCacheLine = -1，或者rightCacheLine = -1它不能是由于递归findPLRUs

因此，指向节点的指针不会在某处“丢失”；它正在被踩踏。

尝试更换：

    int min = treeArray[set]->root->findPLRU();
    c[min].tag = tag;
    c[min].access = access;

和：

    int min = treeArray[set]->root->findPLRU();
    if (min >= k*n)
    {
        printf("ook\n");
    }
    else
    {
        c[min].tag = tag;
        c[min].access = access;
    }

我想你会发现是什么在跺脚。;)

于 2012-04-10T21:23:38.313 回答