c++ - 为什么链表中的数据在嵌套函数中发生更改/损坏？

Question

我正在为离散时间 CPU 调度模拟器编写代码。它只是生成流程并相应地安排它们。我目前正在实现 FCFS 计划。我理解离散时间模拟器的本质，但我在用 C++ 实现时遇到了麻烦。

问题出现在handleNextEvent()和generateProcessDeparture()之间的跳转。在某些时候，我的链表事件队列中的数据被破坏了。 (eventQueue.cpp 中的第 267 行)

想法是 handleNextEvent() 从事件队列中提取下一个事件，即到达(类型 1)，从而为同一进程(PID 1)生成离开(类型 2) .到目前为止一切都很好。

一旦 generateProcessDeparture() 释放控制并返回到 handleNextEvent()，原始到达事件将被删除，应该只留下出发事件。

相反，我得到了 gobbly gook - 以某种方式加上了到达事件的额外拷贝。我研究了作用域和指针，但我是 C++ 的新手，找不到我做错了什么。

任何见解表示赞赏。谢谢。

eventQueue.cpp

/*
    EVENT TYPES
        -1  HEAD: There can be only one head in the linked list of events.
        0 NEW: If 0 the event is new and blank.  For error checking.
        1 arrival:  Indicates arrival of a single process.
        2 departure:  Indicates completion of process.  If the event exists within
            the event queue, then the simulator has NOT YET accounted for it in 
            system state or metric report.
*/

#include "eventQueue.h"
#include <iostream>

eventQueue::eventQueue(int dac, int aar, float ast, float q){

    // Initiatialize head of event linked list.
    eHeadPtr = new event;
    eHeadPtr->type = -1;
    eHeadPtr->time = -1;
    eHeadPtr->next = NULL;

    rqHeadPtr = new event;
    rqHeadPtr->type = -1;
    rqHeadPtr->time = -1;
    rqHeadPtr->next = NULL;

    defaultArrivalCount = dac;
    averageArrivalRate = aar;
    averageServiceTime = ast;
    averageServiceRate = 1 / ast;
    quantum = q;
}

void eventQueue::runFCFS(){
    std::cout << "\n\nrunFCFS()...";

/*  generateProcessArrival();
    generateProcessArrival();
    generateProcessArrival();
    generateProcessArrival();
    generateProcessArrival();
    generateProcessDeparture(*eHeadPtr->next);*/

    while(handledProcessCount < defaultArrivalCount){
        std::cout << "\n\nCurrent event queue: ";
        printEventQueue();
        std::cout << "\nCurrent ready queue: ";
        printReadyQueue();
        std::cout << "\nLatestArrivalTime: " << latestArrivalTime;
        std::cout << "\nNextDepartureTime: " << nextDepartureTime;


        if(eventQueueEmpty()){
            generateProcessArrival();
        }

        handleNextEvent();
        //std::cout << "\n\nEvent queue after handleNextEvent:";
        //printEventQueue();

        while(latestArrivalTime <= nextDepartureTime){
            std::cout << "\nLatestArrivalTime( " << latestArrivalTime << " ) <= nextDepartureTime( " << nextDepartureTime << " )";
            generateProcessArrival();
        }
    }
}

bool eventQueue::eventQueueEmpty(){
    if (eHeadPtr->next == NULL){
        return true;
    }
    return false;
}

bool eventQueue::readyQueueEmpty(){
    if (rqHeadPtr->next == NULL){
        return true;
    }
    return false;
}

void eventQueue::printEvent(event e){
    std::cout << "\n  [ TYPE: " << e.type << ", TIME: " << e.time << ", PID: "
        << e.proc.id << ", BURST: " << e.proc.cpuBurst << ", A_TIME: " << 
        e.proc.arrTime << ", S_TIME: "  << e.proc.servTime << ", R_TIME: " << 
        e.proc.remTime << ", NEXT: " << e.next << " ] ";
    return;
}

void eventQueue::printEventQueue(){

    if (eventQueueEmpty()){
        std::cout << "\n  [ ]";
    }
    else{
        event* tmpPtr = eHeadPtr;

        do{
            tmpPtr = tmpPtr->next;
            printEvent(*tmpPtr);
        }while(tmpPtr->next != NULL);

        tmpPtr = NULL;
        return;
    }
}

void eventQueue::printReadyQueue(){

    if (readyQueueEmpty()){
        std::cout << "\n  [ ]";
    }
    else{
        event* tmpPtr = eHeadPtr;

        do{
            tmpPtr = tmpPtr->next;
            printEvent(*tmpPtr);
        }while(tmpPtr->next != NULL);

        tmpPtr = NULL;
        return;
    }
}

double eventQueue::generateBurst(){

    int intRand = rand() % 100;
    float realRand = intRand / 100.0;
    double burst = ((-log(1 - realRand))/averageServiceRate);
    return burst;
}

double eventQueue::generateArrivalDiff(){

    double diffTime;
    int intRand = rand() % 100; 
    double realRand = intRand / 100.0;
    double dTime = ((-log(1 - realRand)/averageArrivalRate));
    return dTime;
}

void eventQueue::generateProcessArrival(){
    std::cout << "\n\ngenerateProcessArrival()...";

    // Establish pointers.
    event* frontPtr = new event;
    event* backPtr = new event;
    event* newPtr = new event;

    double burst = generateBurst();
    double arrivalDiff = generateArrivalDiff();
    latestArrivalTime += arrivalDiff;
    newProcessID++;

    newPtr->type = 1;
    newPtr->time = latestArrivalTime;
    newPtr->proc.id = newProcessID;
    newPtr->proc.arrTime = latestArrivalTime;
    newPtr->proc.cpuBurst = burst;
    newPtr->proc.servTime = 0;
    newPtr->proc.remTime = burst;

    std::cout << "\nCreated new arrival event:";
    printEvent(*newPtr);

    if(eventQueueEmpty()){
        eHeadPtr->next = newPtr;
        std::cout << "\nEvent queue was empty.  Added new arrival event to queue:";
        printEventQueue();
    }
    else{
        backPtr = eHeadPtr;
        frontPtr = eHeadPtr->next;

        while((newPtr->time > frontPtr->time) && (frontPtr->next != NULL)){
            backPtr = frontPtr;
            frontPtr = frontPtr->next;
        }

        if ((frontPtr->next == NULL)&&(newPtr->time > frontPtr->time)){
            frontPtr->next = newPtr;
            std::cout << "\nAdded new arrival to end of event queue:";
            printEventQueue();      
        }
        else{
            backPtr->next = newPtr;
            newPtr->next = frontPtr;
            std::cout << "\nAdded new arrival to (center/front) of event queue.";
            printEventQueue();  
        }
    }
    frontPtr = NULL;
    backPtr = NULL;
    newPtr = NULL;
    return;
}

void eventQueue::generateProcessDeparture(event arr){
    std::cout << "\n\ngenerateProcessDeparture()...";

    // Establish pointers.
    event* frontPtr = new event;
    event* backPtr = new event;
    event* newPtr = new event;

    // Generate departure based on arrival event.
    event dep;
    dep.type = 2;
    dep.proc = arr.proc;
    dep.time = arr.proc.arrTime + arr.proc.cpuBurst;
    newPtr = &dep;

    std::cout << "\nCreated new departure event:";
    printEvent(*newPtr);

    if(eventQueueEmpty()){
        eHeadPtr->next = newPtr;
        std::cout << "\nEvent queue was empty.  Added new arrival event to queue:";
        printEventQueue();
    }
    else{
        backPtr = eHeadPtr;
        frontPtr = eHeadPtr->next;

        while((newPtr->time > frontPtr->time) && (frontPtr->next != NULL)){
            backPtr = frontPtr;
            frontPtr = frontPtr->next;
        }

        if ((frontPtr->next == NULL)&&(newPtr->time > frontPtr->time)){
            frontPtr->next = newPtr;
            std::cout << "\nAdded new arrival to end of event queue:";
            printEventQueue();      
        }
        else{
            backPtr->next = newPtr;
            newPtr->next = frontPtr;
            std::cout << "\nAdded new arrival to (center/front) of event queue.";
            printEventQueue();  
        }
    }
    std::cout << "\ngenerateProcessDeparture final check:";
    printEventQueue();  
    frontPtr = NULL;
    backPtr = NULL;
    newPtr = NULL;

    return;
}

void eventQueue::handleNextEvent(){
    std::cout << "\n\nhandleNextEvent()...";

    // Establish pointers.
    event* frontPtr = new event;
    event* backPtr = new event; 
    frontPtr = eHeadPtr->next;
    backPtr = eHeadPtr;
    systemClock = frontPtr->time;

    if (frontPtr->type == 1){
        std::cout << "\nArrival event next.";
        printEventQueue();
        //printEvent(*frontPtr);

        if (readyQueueEmpty() && cpuIdle){
            std::cout << "\nReady queue empty and cpu idle.";
            generateProcessDeparture(*frontPtr);

            printEventQueue();      
            backPtr->next = frontPtr->next;     // Remove event from event queue.
            std::cout << "\n\nreturn to handleNextEvent()...";
            cpuIdle = false;
            std::cout << "\ncpuIdle: " << cpuIdle;
            std::cout << "\nCurrent event queue:";
            printEventQueue();          
        }
        else{
            std::cout << "\nReady queue not empty and/or cpu not idle.";
            pushReadyQueue(*frontPtr);
            backPtr->next = frontPtr->next;
        }
    }
    else if (frontPtr->type == 2){
        std::cout << "\nDeparture event next.";
        printEvent(*frontPtr);

        if (!readyQueueEmpty()){
            std::cout << "\nReady not empty.  Loading next event to CPU.";
            event* tmpPtr = rqHeadPtr->next;    //Set tmpPtr to first item in readyQueue.
            generateProcessDeparture(*tmpPtr);  //Creature departure event.
            rqHeadPtr->next = tmpPtr->next;     //Delete old event.
            tmpPtr = NULL;                      
        }
        else{
            std::cout << "\nReady queue empty and cpu idle.";
            cpuIdle = true;
            backPtr->next = frontPtr->next;
        }
    }
    else{
        std::cout << "\nERROR: bad event type in event queue.";
    }

    handledProcessCount++;
    frontPtr = NULL;
    backPtr = NULL; 
    return;
}

void eventQueue::pushReadyQueue(event e){

    // Establish pointers.
    event* frontPtr = new event;
    event* backPtr = new event; 

    while((e.time > frontPtr->time) && (frontPtr->next != NULL)){
        backPtr = frontPtr;
        frontPtr = frontPtr->next;
    }

    if ((frontPtr->next == NULL) && (e.time > frontPtr->time)){
        frontPtr->next = &e;
        std::cout << "\n\nAdded new arrival to end of ready queue:";
        printReadyQueue();      
    }
    else{
        backPtr->next = &e;
        e.next = frontPtr;
        std::cout << "\n\nAdded new arrival to (center/front) of ready queue.";
        printReadyQueue();  
    }

    frontPtr = NULL;
    backPtr = NULL; 
    return; 
}

eventQueue.h

/*
    EVENT TYPES
        -1  INVALID: if 0 the event is new and blank.  For error checking.
        0 head: There can be only one head in the linked list of events.
        1 arrival:  Indicates arrival of a single process.
        2 departure:  Indicates completion of process.  If the event exists within
            the event queue, then the simulator has NOT YET accounted for it in 
            system state or metric report.
*/

#ifndef EVENTQUEUE_H
#define EVENTQUEUE_H
# include <cstddef>
# include <tgmath.h>
# include <ctime>

struct process{
    int id = -1;
    double arrTime = -1;
    double cpuBurst = -1;
    double servTime = -1;
    double remTime = -1;
};

struct event{
    int type = -1;
    double time = -1;
    process proc;
    event* next = NULL;
};

class eventQueue{
    private:
        event* eHeadPtr;
        event* rqHeadPtr;
        int defaultArrivalCount;
        int handledProcessCount = 0;
        int newProcessID = 0;
        int averageArrivalRate;  // lambda
        float averageServiceTime;   // Ts
        float averageServiceRate;   // mu
        float quantum;  //q
        double latestArrivalTime = 0;
        double nextDepartureTime = 0;
        bool cpuIdle = true;
        double systemClock = 0;

    public:
        eventQueue(const int, int, float, float);
        void runFCFS();
        bool eventQueueEmpty();
        bool readyQueueEmpty();
        void printEvent(event);
        void printEventQueue();
        void printReadyQueue();
        void generateProcessArrival();
        double generateBurst();
        double generateArrivalDiff();
        void generateProcessDeparture(event);
        void handleNextEvent();
        void pushReadyQueue(event);
};

#endif // EVENTQUEUE_H

main.cpp

/*
    EVENT TYPES
        0  INVALID: if -1 the event is new and blank.  For error checking.
        1 head: There can be only one head in the linked list of events.
        2 arrival:  Indicates arrival of a single process.
        3 departure:  Indicates completion of process.  If the event exists within
            the event queue, then the simulator has NOT YET accounted for it in 
            system state or metric report.
*/
#include <iostream>
#include <tgmath.h>
#include "eventQueue.h"

void testInput(int, char*);

int main(int argc, char *argv[]){
    srand(time(NULL));
    char divider[] = "----------------------------------------------------------------------------------------------------------------";
    const int DEF_ARR_COUNT= 10;

    std::cout << "\n" << divider;
    std::cout << "\nWelcome to the Simulator";

    //TEST CMD LINE INPUT
    testInput(argc, *argv);

    // Setup environment and first default events (arrivals).
    //int lambda = std::stoi(argv[2]);
    //float Ts = std::stof(argv[3]);
    //eventQueue eq(TOTAL_PR, lambda, Ts);
    //eq.initDefaultArr();

    //eq.printQueue(15);

    eventQueue eq(DEF_ARR_COUNT, std::stoi(argv[2]), std::stof(argv[3]), std::stof(argv[4]));
    eq.runFCFS();
    //eq.printWithoutCount();



    std::cout << "\n" << divider;
    std::cout << "\n\n";
    return 0;
}

void testInput(int argc, char* argv){
    if ((argc < 5) || ((argv[1] > 4) && (argv[1] < 1))){
        std::cout << "\n\nERROR: invalid commandline input";
        std::cout << "\n\tCommand line: <scheduler> <lambda> <Ts> <quantum>";
        std::cout << "\n\tScheduler: [1,FCFS], [2, SRTF], [3, HRRN], [4, RR]";
        std::cout << "\n\tExample: ./main 2 15 0.06 0.01";
    }
}

这是我得到的一些示例输出:

anne@laptop:~/Dropbox/College/Current/Opsy/ROUND_4$ g++ main.cpp eventQueue.cpp -o main
anne@laptop:~/Dropbox/College/Current/Opsy/ROUND_4$ ./main 1 10 0.05 0.01

----------------------------------------------------------------------------------------------------------------
Welcome to the Simulator

runFCFS()...

Current event queue: 
  [ ]
Current ready queue: 
  [ ]
LatestArrivalTime: 0
NextDepartureTime: 0

generateProcessArrival()...
Created new arrival event:
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 
Event queue was empty.  Added new arrival event to queue:
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 

handleNextEvent()...
Arrival event next.
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 
Ready queue empty and cpu idle.

generateProcessDeparture()...
Created new departure event:
  [ TYPE: 2, TIME: 0.359373, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 
Added new arrival to end of event queue:
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0x7fff5cc50520 ] 
  [ TYPE: 2, TIME: 0.359373, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 
generateProcessDeparture final check:
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0x7fff5cc50520 ] 
  [ TYPE: 2, TIME: 0.359373, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0 ] 
  [ TYPE: 1, TIME: 0.350656, PID: 1, BURST: 0.00871767, A_TIME: 0.350656, S_TIME: 0, R_TIME: 0.00871767, NEXT: 0x7fff5cc50520 ] 
  [ TYPE: 1556416656, TIME: 4.6627e-310, PID: 1556415824, BURST: 0.00871767, A_TIME: 4.6627e-310, S_TIME: 6.95322e-310, R_TIME: 6.95322e-310, NEXT: 0x55d52b320ec1 ] 
Segmentation fault (core dumped)

根据我对段错误的理解，它通常是由于引用数组或列表越界造成的？

Answer 1

这一行的问题代码:

newPtr = &dep;

你应该把它改成

*newPtr = dep;

因为dep定义在栈缓冲区上，执行函数generateProcessDeparture后，栈缓冲区会被覆盖。