Почему мои данные в связанном списке изменяются / портятся во вложенных функциях? - PullRequest
Новая
       10

Почему мои данные в связанном списке изменяются / портятся во вложенных функциях?

0 голосов
/ 28 марта 2019

Я пишу код для имитатора расписания с дискретным временем.Он просто генерирует процессы и планирует их соответственно.В настоящее время я реализую график FCFS.Я понимаю природу симулятора дискретного времени, но мне трудно реализовать его на C ++.

Проблема возникает при переходе между handleNextEvent() и generateProcessDeparture().В какой-то момент данные в моей очереди событий связанного списка будут повреждены.(Строка 267 в eventQueue.cpp)

Идея состоит в том, что handleNextEvent() извлекает следующее событие из очереди событий, приход (тип 1), и, таким образом, генерирует отправку (тип 2) для того же процесса.(PID 1).Все хорошо до этого момента.

Как только элемент управления отпускается generateProcessDeparture() и возвращается к handleNextEvent(), исходное событие прибытия удаляется, что СЛЕДУЕТ оставлять только событие отправления.

Вместо этого у меня сумасшедший обман - плюс дополнительная копия события прибытия как-то.Я исследовал область и указатели, но я новичок в 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)

Из того, что я понимаю о сбоях сегментации, это часто связано с обращением к массиву или списку изграниц?

1 Ответ

2 голосов
/ 28 марта 2019

Код вопроса в этой строке: 

newPtr = &dep;

Вы должны изменить его на 

*newPtr = dep;

Поскольку dep определено в буфере стека, после выполнения функции generateProcessDeparture,буфер стека будет перезаписан.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...