Доступ к элементу std :: list сбрасывает ядро

Question

#include <iostream>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <iomanip>
using namespace std;

void runSimulation(int frameNum, fstream &fs);
void handleMemory(string address);
void handleAddress(int frameNum, string address);
void insertValue(string index);
void replaceValue(string index);
void updateOrder(list<string>::iterator orderPos);

int hit_num = 0, miss_num = 0;
const int INDEX_BITS = 5;
typedef map< string, list<string>::iterator > Memory;
typedef pair< string, list<string>::iterator > MemPair;
Memory memory;
list<string> order;

int main(){

    fstream fs;
    fs.open("trace.txt", fstream::in);

    cout <<  "LRU---"  << endl;
    cout << left << setw(10) << "size";
    cout << left << setw(15) << "miss";
    cout << left << setw(20) << "hit";
    cout << "page fault ratio" << endl;
    for(int i=256; i<=512; i*=2){
        runSimulation(i, fs);
        fs.clear();
        fs.seekg(0, ios::beg);
    }

    fs.close();

    return 0;
}

void runSimulation(int frameNum, fstream &fs){
    memory.clear();
    order.clear();
    hit_num = 0;
    miss_num = 0;

    string str;
    while(getline(fs, str)){
        handleAddress(frameNum, str);
    }

    cout << left << setw(10) << frameNum;
    cout << left << setw(15) << miss_num;
    cout << left << setw(20) << hit_num;
    cout << fixed << setprecision(9) <<  (double)miss_num/(miss_num + hit_num) << endl;
}

void handleAddress(int frameNum, string address){
    string index;
    Memory::iterator found;

    index = address.substr(0, INDEX_BITS);
    found = memory.find(index);
    if(found == memory.end()){ // miss
        miss_num++;
        if(memory.size() < frameNum){ // there are empty spaces
            insertValue(index);
        }
        else{
            replaceValue(index);
        }
    }
    else{ // hit
        hit_num++;
        //cout << "hit: " << found->first << endl;
        updateOrder(found->second);
    }
}

void insertValue(string index){
    //cout << "insert: " << index << endl;
    string *newIndex = new string;
    order.push_back(index);
    list<string>::iterator it = order.end();
    it--;
    memory.insert(MemPair(index, it));
}

void replaceValue(string index){
    //cout << "replace: " << index << endl;
    memory.erase(order.front());
    order.pop_front();
    insertValue(index);
}

void updateOrder(list<string>::iterator orderPos){
    string value = *orderPos;
    order.erase(orderPos);
    order.push_back(value);
}

Я пытаюсь смоделировать механизм наименее недавно использованного в ОС.Но я думаю, что вы все равно могли бы понять проблему, если не знаете об этом.

Ввод будет представлять собой серию воображаемых адресов памяти, и ими манипулируют в виде string по всей программе.(Я не говорю об адресе или указателе переменной или чего-то еще.) Каждая строка содержит один адрес, и я читаю их построчно, используя getline.

И мне нужны два контейнераподдерживать все время.
Первая - это карта, тип которой <string, list<string::iterator>>.Здесь записывается, существует ли один адрес в настоящее время в мнимой памяти, и положение адреса в списке (второй контейнер).
Второй - это список, тип которого list<string>.Это отслеживает «актуальность» каждого адреса.Самый последний из них находится сзади, а наименее последний - спереди.

После получения одного адреса, если адрес не существует на карте (и в воображаемом виде все еще существуют пустые места)память), это было бы первым push_back в списке.Затем я записал бы положение этого элемента в списке, сделал бы pair<string, list<string::iterator>> (first это адрес, second это позиция) и insert это на карту.

Есливоображаемая память заполнена, затем вытолкните наименее последний и вставьте новый.Оба контейнера должны быть сохранены.Я знаю, какой из них является наименьшим последним по доступу к началу списка.

Если адрес уже существует на карте (хит), соответствующие данные в списке будут erase d и * 1024.* снова попал в список, сделав его самым последним.

И вот в чем проблема.

При запуске ввода иногда я получаю дамп ядра.GDB говорит мне, что проблема всегда в updateOrder (я пробовал несколько разных способов перестановки кодов).Я полагаю, что я не очень хорошо справился с итератором.

И что более интересно, если я сделаю runSimulation(64, fs), то будет нормально, если frameNum будет 64, а ядро ​​сброшено на 128. Однако, если я сначала сделаю runSimulation(128, fs), все будет в порядке на 128, но будет сброшено на 256.

Что-то не так во время инициализации в начале runSimulation?Или итератор указывает на неправильную позицию?

Answer 1

Проблема в updateOrder.Вы удаляете существующий узел и создаете новый, но у memory все еще есть итератор для стертого узла.Вы можете обновить memory с новым местоположением, но лучшим решением будет использование splice:

void updateOrder(list<string>::iterator orderPos){
    order.splice(order.back(), order, orderpos);
}

. Это позволит переместить существующий узел в конец списка без аннулирования существующих итераторов.

Кстати, вы теряете память в insertValue при выделении строки (которую вы не используете).