Styjun

I am writing code for a discrete time CPU schedule simulator. It simply generates processes and schedules them accordingly. I am currently implementing the FCFS schedule. I understand the nature of a discrete time simulator, but I am have trouble implementing in C++.

The problem occurs in the jump between handleNextEvent() and generateProcessDeparture(). At some point the data in my linked-list event queue gets corrupted. (Line 267 in eventQueue.cpp)

The idea is that handleNextEvent() pulls the next event from the event queue, an arrival (type 1), and thus generates a departure (type 2) for the same process (PID 1). Everything is good up to this point.

Once control is release by generateProcessDeparture() and returns to handleNextEvent(), the original arrival event is deleted, which SHOULD leave only the departure event.

Instead I've got gobbly gook - plus a extra copy of the arrival event somehow. I've researched scope and pointers, but I am a novice to C++, and can't find what I'm doing wrong.

Any insight appreciated. Thank you.

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 << "nnrunFCFS()...";

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

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


 if(eventQueueEmpty())
 generateProcessArrival();
 

 handleNextEvent();
 //std::cout << "nnEvent 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 << "nngenerateProcessArrival()...";

 // 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 << "nngenerateProcessDeparture()...";

 // 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 << "nnhandleNextEvent()...";

 // 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 << "nnreturn 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 << "nnAdded new arrival to end of ready queue:";
 printReadyQueue(); 
 
 else
 backPtr->next = &e;
 e.next = frontPtr;
 std::cout << "nnAdded 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 << "nn";
 return 0;


void testInput(int argc, char* argv)
 if ((argc < 5) 

Here is some example output that I am getting:

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)

From what I understand of segmentation faults, its often due to referencing an array or list out of bounds?

Question code in this line:

newPtr = &dep;

You should change it to

*newPtr = dep;

Because dep is defined on the stack buffer, after execute function generateProcessDeparture, the stack buffer will be overwritten.