simulation.cpp

/*
    Operating Systems Fall 2013, Lab 2. 15 October 2013
    Lior Galanti lior.galanti@nyu.edu N14314920
*/

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include <fstream>
#include <iostream>
#include <sstream> 
#include <string>
#include <list>

// Header 

using namespace std;

enum SchedulingAlgorithm {
    UNKNOWN = 0,
    FCFS = 1,
    RoundRobin = 2,
    LCFS = 3,
    SJF = 4
};

enum EventType {
    PROCESS_BLOCKS_FOR_INPUT = 1,
    SCHEDULER_PICKS_ANOTHER_PROCESS = 2,
    SCHEDULER_PICKS_THIS_PROCESS = 3,
    INPUT_BECOMES_AVAILABLE = 4,
    PROCESS_ARIVES = 5,
    PROCESS_TERMINATES = 6
};

class Process {
public:
    int Pid;
    int ArrivalTime;
    int TotalCpuTime;
    int CpuBurst;
    int IoBurst;
    int FinishTime;
    int AccumulatedRunTime;
    int AccumulatedIoTime;
    int AccumulatedReadyTime;
    int LastSwitch;
    int RemainingCpuBurst;
    
    Process &operator=(const Process &rhs);
    int operator==(const Process &rhs) const;
    int operator<(const Process &rhs) const;
    
	Process() {
        Pid = -1;
        ArrivalTime = -1;
        TotalCpuTime = -1;
        CpuBurst = -1;
        IoBurst = -1;
        FinishTime = -1;
        AccumulatedRunTime = 0;
        AccumulatedIoTime = 0;
        AccumulatedReadyTime = 0;
        LastSwitch = -1;
        RemainingCpuBurst = 0;
    }
    void PrintSummary() {
        printf("%.04d:%5d%5d%5d%5d |%5d%5d%5d%5d\n",
            Pid,
            ArrivalTime,
            TotalCpuTime,
            CpuBurst,
            IoBurst,
            FinishTime,
            TurnaroundTime(),
            AccumulatedIoTime,
            AccumulatedReadyTime
        );
    }
    int TurnaroundTime() const{
        return FinishTime - ArrivalTime;
    }
    int RemainingTime() const{
        return TotalCpuTime - AccumulatedRunTime;
    }
};

class Event {
public:
    enum EventType Type;
    int Eid;
    int Time;
    int Created;
    Process* Subject;
    
    Event &operator=(const Event &rhs);
    int operator==(const Event &rhs) const;
    int operator<(const Event &rhs) const;
    int operator>(const Event &rhs) const;

    Event(Process* process, int created);
};

class Priority {
public:
    Process* Subject;
    int Prid;
    
    Priority &operator=(const Priority &rhs);
    int operator==(const Priority &rhs) const;
    int operator<(const Priority &rhs) const;
    int operator>(const Priority &rhs) const;
    
    int Score() const {
        return Subject->RemainingTime();
    }
    Priority(Process* process){
        Subject = process;
    }
};

class Simulation {
public:
    int Valid;
    int Verbose;
    string Information;
    char* InputFilePath;
    char* RandFilePath;
    enum SchedulingAlgorithm Policy;
    int Preemptive;
    int Quantum;
    
    int FinishTime;
    int TotalCpuTime;
    int TotalIoTime;
    int ActiveIos;
    int LastIoStart;
    
    // Processes
    list<Process*> Processes;
    list<Process*> Ready;
    Process* Running;
    
    // Events
    list<Event*> Pending;
    list<Event*> Done;
    
    void StepForward();
    virtual void PushToReady(Process* process){};
    virtual Process* PickNextProcess(){return NULL;};
    
    Simulation(int verbose, char* inputFilePath, char* randFilePath){
        Valid = 1;
        Verbose = verbose;
        InputFilePath = inputFilePath;
        RandFilePath = randFilePath;
        Policy = UNKNOWN;
        Preemptive = 0;
        Quantum = 0;
        FinishTime = 0;
        TotalCpuTime = 0;
        TotalIoTime = 0;
        ActiveIos = 0;
        LastIoStart = 0;
        TotalRandom = 0;
        RandomOffset = 0;
        EventCounter = -1;
        PriorityCounter = -1;
        Load();
    };
    ~Simulation(){
        if (RandomSet != NULL) { delete RandomSet;}
    };
    void Load();
    void Run(){
        while(!Pending.empty())
            StepForward();
    }
    int NextEventId(){
        EventCounter++;
        return EventCounter;
    }
    int NextPriorityId(){
        PriorityCounter++;
        return PriorityCounter;
    }
    void PlaceEvent(Event* event);
    void PrintSum() {
        double cpuUtilization = 0.0, ioUtilization = 0.0, cpuWaitingTime = 0.0, turnaroundTime = 0.0, throughput = 0.0;
        for(list<Process*>::iterator p = Processes.begin();p != Processes.end(); p++) {
            TotalCpuTime += (*p)->AccumulatedRunTime;
            cpuWaitingTime += (*p)->AccumulatedReadyTime;
            turnaroundTime += (*p)->TurnaroundTime();
        }

        cpuUtilization = 100.0 * (((double)TotalCpuTime) / ((double)FinishTime));
        ioUtilization = 100.0 * (((double)TotalIoTime) / ((double)FinishTime));
        cpuWaitingTime /= (double)Processes.size();
        turnaroundTime /= (double)Processes.size();
        throughput = ((double)Processes.size() / ((double)FinishTime)) * 100.0;
        
        printf("SUM: %d %.2lf %.2lf %.2lf %.2lf %.3lf\n",
            FinishTime,
            cpuUtilization,
            ioUtilization,
            turnaroundTime,
            cpuWaitingTime,
            throughput
        );
    }
    void PrintSummary(){
        printf("%s\n", Information.c_str());
        //printf("PID:    AT   TC   CB   IO |   FT   TT   IT   CW\n");
        for(list<Process*>::iterator p = Processes.begin();p != Processes.end(); p++) {
            (*p)->PrintSummary();
        }
        PrintSum();
    }
protected:
    int TotalRandom;
    int RandomOffset;
    int EventCounter;
    int PriorityCounter;
    int* RandomSet;
    void LoadRandom();
    void LoadProcesses();
    void ScheduleProcesses();
    void ScheduleProcessBlocksForInputEvent(Process* p, int now, int time);
    void ScheduleSchedulerPicksAnotherProcessEvent(Process* p, int now, int time);
    void ScheduleSchedulerPicksThisProcessEvent(Process* p, int now, int time);
    void ScheduleInputBecomesAvailableEvent(Process* p, int now, int time);
    void ScheduleProcessTerminatesEvent(Process* p, int now, int time);
    int RandomBurst(int burst){
        int random = 1 + (int)(RandomSet[RandomOffset] % burst);
        RandomOffset++;
        RandomOffset %= TotalRandom;
        return random;
    }
};

class FCFSSimulation: public Simulation {
public:
    void PushToReady(Process* process){
        Ready.push_back(process);
    };
    Process* PickNextProcess(){
        Process* result = NULL;
        if(!Ready.empty()) {
            result = Ready.front();
            Ready.pop_front();
        }
        return result;
    }
    
    FCFSSimulation(int verbose, char* inputFilePath, char* randFilePath)
    :Simulation(verbose, inputFilePath, randFilePath) {
        Policy = FCFS;
        Information = "FCFS";
    };
};

class LCFSSimulation: public Simulation {
public:
    void PushToReady(Process* process){
        Ready.push_back(process);
    };
    Process* PickNextProcess(){
        Process* result = NULL;
        if(!Ready.empty()) {
            result = Ready.back();
            Ready.pop_back();
        }
        return result;
    }
    
    LCFSSimulation(int verbose, char* inputFilePath, char* randFilePath)
    :Simulation(verbose, inputFilePath, randFilePath) {
        Policy = LCFS;
        Information = "LCFS";
    }
};

class SJFSimulation: public Simulation {
public:
    list<Priority*> ReadyQueue;
    
    void PushToReady(Process* process){
        Priority* priority = new Priority(process);
        priority->Prid = NextPriorityId();
    
        if(ReadyQueue.empty()) {
            ReadyQueue.push_front(priority);
        
        } else {
            int placed = 0;
            for(list<Priority*>::iterator p = ReadyQueue.begin();p != ReadyQueue.end(); p++) {
                if (*priority < *(*p)) {
                    ReadyQueue.insert(p, priority);
                    placed = 1;
                    break;
                }
            }
            if (placed == 0) ReadyQueue.push_back(priority);
        }
    }
    Process* PickNextProcess(){
        Process* result = NULL;
        if(!ReadyQueue.empty()) {
            Priority* p = ReadyQueue.front();
            result = p->Subject;
        
            ReadyQueue.pop_front();
            delete p;
        }
        return result;
    }

    SJFSimulation(int verbose, char* inputFilePath, char* randFilePath)
    :Simulation(verbose, inputFilePath, randFilePath) {
        Policy = SJF;
        Information = "SJF";
    }
};

class RoundRobinSimulation: public Simulation {
public:
    void PushToReady(Process* process){
        Ready.push_back(process);
    };
    Process* PickNextProcess(){
        Process* result = NULL;
        if(!Ready.empty()) {
            result = Ready.front();
            Ready.pop_front();
        }
        return result;
    }
    RoundRobinSimulation(int verbose, char* inputFilePath, char* randFilePath, int quantum)
    :Simulation(verbose, inputFilePath, randFilePath) {
        Policy = RoundRobin;
        Quantum = quantum;
        Preemptive = 1;
        
        stringstream s;
        s << "RR " << quantum;
        Information = s.str();
    }
};

// Implementation

// Simulation
void Simulation::PlaceEvent(Event* event){
    // The initial event list is sorted by time because it is assumed process input is sorted
    // Every time we want to add an event we will scan the list until we find its correct place.
    if(Pending.empty()) {
        Pending.push_front(event);
        
    } else {
        int placed = 0;
        for(list<Event*>::iterator e = Pending.begin();e != Pending.end(); e++) {
            if (*event < *(*e)) {
                Pending.insert(e, event);
                placed = 1;
                break;
            }
        }
        if (placed == 0) Pending.push_back(event);
    }
}
void Simulation::StepForward(){
    Event* e = Pending.front();
    int now = e->Time;
    int schedule = 0;

    while(e!= NULL && e->Time == now) {
        Process* p = e->Subject;
        int duration = now - p->LastSwitch;
    
        switch (e->Type) {
            case PROCESS_BLOCKS_FOR_INPUT: {
                // update the run time counter
                p->AccumulatedRunTime += duration;
                p->RemainingCpuBurst -= duration;

                // Set the Running to NULL
                Running = NULL;
                schedule = 1;
    
                // Schedule a new event for the input to become available
                int ioBurst = RandomBurst(p->IoBurst);
                ScheduleInputBecomesAvailableEvent(p, now, now + ioBurst);
                
                if (ActiveIos == 0) LastIoStart = now;
                ActiveIos++;
        
                if(Verbose){
                    printf("\n==> %d %d ts=%d BLOCK  dur=%d\n", now, p->Pid, e->Created, now - e->Created);
                    printf("T(%d:%d): RUNNG -> BLOCK  ib=%d rem=%d\n", p->Pid, now, ioBurst, p->RemainingTime());
                }
            } break;
    
            case SCHEDULER_PICKS_ANOTHER_PROCESS: {
                // update the run time counter
                p->AccumulatedRunTime += duration;
                p->RemainingCpuBurst -= duration;
                
                PushToReady(p);
                
                // Set the Running to NULL and flag that a new process needs to be scheduled
                Running = NULL;
                schedule = 1;
            
                if(Verbose){
                    printf("\n==> %d %d ts=%d PREEMPT  dur=%d\n", now, p->Pid, e->Created, now - e->Created);
                    printf("T(%d:%d): RUNNG -> READY  cb=%d rem=%d\n", p->Pid, now, p->RemainingCpuBurst, p->RemainingTime());
                }
            } break;
            
            case SCHEDULER_PICKS_THIS_PROCESS: {
                // update the ready time counter
                p->AccumulatedReadyTime += duration;
        
                // set process to running
                Running = p;
        
                // Schedule a new event for the process to block for input
                int remaining = p->RemainingTime();
                
                if (p->RemainingCpuBurst <= 0) {
                    p->RemainingCpuBurst = RandomBurst(p->CpuBurst);
                }
                
                if(p->RemainingCpuBurst >= p->RemainingTime()) {
                    // shorted the burst to the remaining
                    p->RemainingCpuBurst = p->RemainingTime();
                }
                
                if(Preemptive) {
                    if(p->RemainingCpuBurst == p->RemainingTime() && p->RemainingCpuBurst <= Quantum) {
                        // Termination takes precedence
                        ScheduleProcessTerminatesEvent(p, now, now + p->RemainingCpuBurst);
                    } else {
                        // IO Burst takes precedence over preemption
                        if(p->RemainingCpuBurst<= Quantum) {
                            ScheduleProcessBlocksForInputEvent(p, now, now + p->RemainingCpuBurst);
                        } else {
                            ScheduleSchedulerPicksAnotherProcessEvent(p, now, now + Quantum);
                        }
                    }
                } else {
                    if(p->RemainingCpuBurst == p->RemainingTime()) {
                        // Termination takes precedence
                        ScheduleProcessTerminatesEvent(p, now, now + p->RemainingCpuBurst);
                    } else {
                        ScheduleProcessBlocksForInputEvent(p, now, now + p->RemainingCpuBurst);
                    }
                }
                
                if(Verbose) {
                    printf("\n==> %d %d ts=%d RUNNG  dur=%d\n", now, p->Pid, e->Created, now - e->Created);
                    printf("T(%d:%d): READY -> RUNNG  cb=%d rem=%d\n", p->Pid, now, p->RemainingCpuBurst, remaining);
                }
            } break;
    
            case INPUT_BECOMES_AVAILABLE: {
                // update the IO time counter
                p->AccumulatedIoTime += duration;
                
                ActiveIos--;
                if(ActiveIos == 0) TotalIoTime += (now - LastIoStart);
        
                // App process to the end of the Ready queue
                PushToReady(p);
                if (Running == NULL) schedule = 1;
        
                if(Verbose) {
                    printf("\n==> %d %d ts=%d READY  dur=%d\n", now, p->Pid, e->Created, now - e->Created);
                    printf("T(%d:%d): BLOCK -> READY\n", p->Pid, now);
                }
            } break;
    
            case PROCESS_ARIVES: {
                // App process to the end of the Ready queue
                PushToReady(p);
                
                if (Running == NULL) schedule = 1;
        
                if(Verbose) {
                    printf("\n==> %d %d ts=%d READY  dur=%d\n", now, p->Pid, now, 0);
                    printf("T(%d:%d): READY -> READY\n", p->Pid, now);
                }
            } break;
    
            case PROCESS_TERMINATES:{
                p->AccumulatedRunTime += duration;
                p->RemainingCpuBurst -= duration;
                Running = NULL;
                schedule = 1;
                p->FinishTime = now;
                
                // Global
                FinishTime = now;
                
                if(Verbose) {
                    printf("\n==> %d %d ts=%d BLOCK  dur=%d\n", now, p->Pid, e->Created, now - e->Created);
                    printf("==> T(%d): Done\n", p->Pid);
                }
            } break;
    
            default: break;
        }
    
        p->LastSwitch = now;
        Pending.pop_front();
        Done.push_back(e);
        e = Pending.front();
    }

    if(schedule and Running == NULL) {
        Process* next = PickNextProcess();
        if (next != NULL) {
            ScheduleSchedulerPicksThisProcessEvent(next, now, now);
        }
    }
}
void Simulation::ScheduleProcessBlocksForInputEvent(Process* p, int now, int time){
    Event* event = new Event(p, now);
    event->Eid = NextEventId();
    event->Type = PROCESS_BLOCKS_FOR_INPUT;
    event->Time = time;
    PlaceEvent(event);
}
void Simulation::ScheduleSchedulerPicksAnotherProcessEvent(Process* p, int now, int time){
    Event* event = new Event(p, now);
    event->Eid = NextEventId();
    event->Type = SCHEDULER_PICKS_ANOTHER_PROCESS;
    event->Time = time;
    PlaceEvent(event);
}
void Simulation::ScheduleSchedulerPicksThisProcessEvent(Process* p, int now, int time){
    Event* event = new Event(p, now);
    event->Eid = NextEventId();
    event->Type = SCHEDULER_PICKS_THIS_PROCESS;
    event->Time = now; //context switching overhead is zero
    PlaceEvent(event);
}
void Simulation::ScheduleInputBecomesAvailableEvent(Process* p, int now, int time){
    Event* event = new Event(p, now);
    event->Eid = NextEventId();
    event->Type = INPUT_BECOMES_AVAILABLE;
    event->Time = time;
    PlaceEvent(event);
}
void Simulation::ScheduleProcessTerminatesEvent(Process* p, int now, int time){
    Event* event = new Event(p, now);
    event->Eid = NextEventId();
    event->Type = PROCESS_TERMINATES;
    event->Time = time;
    PlaceEvent(event);
}
void Simulation::ScheduleProcesses() {
    for(list<Process*>::iterator p = Processes.begin();p != Processes.end(); p++) {
        Event* event = new Event(*p, 0);
        event->Eid = NextEventId();
        event->Type = PROCESS_ARIVES;
        event->Time = (*p)->ArrivalTime;
        
        // Arrival events are predetermined and provided in order 
        Pending.push_back(event);
    }
}
void Simulation::LoadRandom(){
    if (RandFilePath != NULL) {
        int length, value, index;
        string line;
        ifstream randomFile( RandFilePath );
        if (randomFile) {
            // Get the size of the array
            getline( randomFile, line );
            istringstream iss(line);
            if (iss >> TotalRandom) {
                // allocate an array for random numbers
                RandomSet = (int*)malloc(sizeof(int) * TotalRandom);
            
                index = 0;
                while (getline( randomFile, line )) {
                    istringstream iss(line);
                    iss >> value;
                    RandomSet[index] = value;
                    index++;
                }
            } else {
                cerr << "Input file format error\n";
            }
            randomFile.close();
        } else {
            cerr << "Error opening random file\n";
            Valid = 0;
        }
    }
};
void Simulation::LoadProcesses(){
    if (InputFilePath != NULL) {
        string line;
        int index;
        
        ifstream randomFile( InputFilePath );
        if (InputFilePath) {
            index = 0;
            while (getline( randomFile, line )) {
                Process* process = new Process();
                istringstream iss(line);
                
                process->Pid = index;
                iss >> process->ArrivalTime >> process->TotalCpuTime >> process->CpuBurst >> process->IoBurst;
                Processes.push_back(process);
                index++;
            }
            randomFile.close();
        } else {
            cerr << "Error opening process file\n";
            Valid = 0;
        }
    }
};
void Simulation::Load(){
    LoadRandom();
    LoadProcesses();
    ScheduleProcesses();
};

// Priority
Priority& Priority::operator=(const Priority &rhs){
    this->Subject = rhs.Subject;
    return *this;
}
int Priority::operator==(const Priority &rhs) const {
    if(this->Prid == rhs.Prid) return 1;
    return 0;
}
int Priority::operator<(const Priority &rhs) const {
    int result = 0;
    if( this->Score() < rhs.Score() ) result = 1;
    else if ((this->Score() == rhs.Score()) && (this->Prid < rhs.Prid)) result = 1;
    return result;
}

// Process
Process& Process::operator=(const Process &rhs){
    this->Pid = rhs.Pid;
    this->ArrivalTime = rhs.ArrivalTime;
    this->TotalCpuTime = rhs.TotalCpuTime;
    this->CpuBurst = rhs.CpuBurst;
    this->IoBurst = rhs.IoBurst;
    this->FinishTime = rhs.FinishTime;
    this->AccumulatedRunTime = rhs.AccumulatedRunTime;
    this->AccumulatedIoTime = rhs.AccumulatedIoTime;
    this->AccumulatedReadyTime = rhs.AccumulatedReadyTime;
    this->LastSwitch = rhs.LastSwitch;
    this->RemainingCpuBurst = rhs.RemainingCpuBurst;
    return *this;
}
int Process::operator==(const Process &rhs) const {
    if(this->Pid == rhs.Pid) return 1;
    return 0;
}
int Process::operator<(const Process &rhs) const {
    if( this->Pid < rhs.Pid ) return 1;
    return 0;
}

// Event
Event::Event(Process* process, int created) {
    Subject = process;
    Created = created;
    Eid = -1;
    Time = -1;
}
Event& Event::operator=(const Event &rhs){
    this->Eid = rhs.Eid;
    this->Time = rhs.Time;
    this->Subject = rhs.Subject;
    this->Created = rhs.Created;
    return *this;
}
int Event::operator==(const Event &rhs) const {
    if(this->Eid == rhs.Eid) return 1;
    return 0;
}
int Event::operator<(const Event &rhs) const {
    int result = 0;
    if( this->Time < rhs.Time) result = 1;
    else if ((this->Time == rhs.Time) && (this->Eid < rhs.Eid)) result = 1;
    return result;
}
int Event::operator>(const Event &rhs) const {
    int result = 0;
    if( this->Time > rhs.Time) result = 1;
    else if ((this->Time == rhs.Time) && (this->Eid > rhs.Eid)) result = 1;
    return result;
}

// Command Line
Simulation* ParseCommandLine(int argc, char **argv) {
    Simulation* simulation = NULL;
    int verbose = 0;
    int index, c, quantum;
    enum SchedulingAlgorithm policy = UNKNOWN;
    char *inputFilePath, *randFilePath;
    opterr = 0;
    while ((c = getopt (argc, argv, "vs:")) != -1) {
        switch (c) {
            case 'v':
                verbose = 1;
                break;
            case 's':
                if (strcmp(optarg, "F") == 0) {
                    policy = FCFS;
                
                } else if (strcmp(optarg, "L") == 0) {
                    policy = LCFS;
            
                } else if (strcmp(optarg, "S") == 0) {
                    policy = SJF;
                    
                } else if (optarg[0] == 'R') {
                    policy = RoundRobin;
                    quantum = atoi(optarg+1);
                }
                break;
            case '?':
                if (optopt == 's')
                    fprintf (stderr, "Option -%c requires an argument.\n", optopt);
                
                else if (isprint (optopt))
                    fprintf (stderr, "Unknown option `-%c'.\n", optopt);
                else
                    fprintf (stderr, "Unknown option character `\\x%x'.\n", optopt);
            default: abort ();
        }
    }
    
    if ((argc - optind) == 2) {
        inputFilePath = argv[optind];
        randFilePath = argv[optind+1];
    } else {
        fprintf (stderr, "Simulation expects 2 positional arguments.\n");
    }

    if (policy > 0){
        if(policy == FCFS) {
            simulation = new FCFSSimulation(verbose, inputFilePath, randFilePath);
        } else if(policy == LCFS) {
            simulation = new LCFSSimulation(verbose, inputFilePath, randFilePath);
        } else if(policy == SJF) {
            simulation = new SJFSimulation(verbose, inputFilePath, randFilePath);
        } else if(policy == RoundRobin) {
            simulation = new RoundRobinSimulation(verbose, inputFilePath, randFilePath, quantum);
        }
    }
    
    return simulation;
}

// Main
int main (int argc, char **argv) {
    Simulation* simulation = ParseCommandLine(argc, argv);
    if(simulation->Valid) {
        simulation->Run();
        simulation->PrintSummary();
    }
}