Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <map>
- #include <stdlib.h>
- #include <cstdlib>
- #include <algorithm>
- #include <iomanip>
- #define SJFNP 0
- #define SJFP 1
- #define RR 2
- #define PP 3
- int n = 12; //num processes
- class Process {
- public:
- Process() : id(0), cpu(false), burstTime(0), cpuBursts(0), t(0), b(0), userMode(false), turnaround(0), wait(0), priority(0), totalTurnaround(0), totalWait(0) {
- }
- //constant
- int id; //process id
- bool cpu; //false for interactive process, true for cpu process
- int burstTime; //burst time needed from the cpu
- int userTime; //time needed from i/o
- int cpuBursts; //num bursts before terminating (for cpu processes)
- int initialPriority;
- //varying
- int t; //time (starting at 0)
- int b; //count of cpu bursts
- bool userMode; //if waiting for i/o
- int turnaround; //turnaround time counter
- int wait; //wait time counter
- int priority;
- int totalTurnaround;
- int totalWait;
- //increment time
- void timeInc(bool active) {
- if (active){
- t++;
- turnaround++;
- } else {
- t++;
- wait++;
- }
- }
- void reset(){
- t = 0;
- b = 0;
- userMode = false;
- turnaround = 0;
- wait = 0;
- priority = initialPriority;
- totalTurnaround = 0;
- totalWait = 0;
- }
- };
- class CPU {
- public:
- CPU() : process(NULL), processOut(NULL), useTime(0), notUseTime(0), contextSwitchTime(0), inContextSwitch(false) {
- }
- Process* process;
- Process* processOut; //process leaving during a context switch
- int useTime;
- int notUseTime;
- int contextSwitchTime;
- bool inContextSwitch;
- std::map<int, int> processesTime;
- void reset() {
- process = NULL;
- processOut = NULL;
- useTime = 0;
- notUseTime = 0;
- contextSwitchTime = 0;
- inContextSwitch = false;
- for (int i=0; i<n; i++){
- processesTime[i+1] = 0;
- }
- }
- };
- std::vector<CPU*> cpus;
- std::vector<Process*> readyQueue;
- std::vector<Process*> terminatedProcesses;
- double pInt = .8; //percent of interactive processes
- int iBMin = 20; //min burst time for interactive processes
- int iBMax = 200; //max burst time for interactive processes
- int uMin = 1000; //min user time
- int uMax = 4500; //max user time
- int cBMin = 200; //min burst time for cpu processes
- int cBMax = 3000; //max burst time for cpu processes
- int b = 8; //num burst for cpu processes before terminating
- int ioMin = 1200; //min i/o block time
- int ioMax = 3200; //max i/o block time
- int m = 4; //num cpu's
- int tSlice = 100; //time slice for RR
- int tAging = 1200; //aging will cause lower-priority processes to increment after this time passes
- int tCS = 2; //overhead time for completing a context switch
- int t = 0; //time
- int algorithm = SJFNP; //the algorithm currently simulated
- int rrTimer = 0; //time counter for RR
- int minTurnaround = 99999999;
- int maxTurnaround = 0;
- int totalTurnaround = 0;
- int minWait = 99999999;
- int maxWait = 0;
- int totalWait = 0;
- int randomVal(int low, int high) {
- return low + (high - low) * (rand() * 1.0 / RAND_MAX);
- }
- void addToReadyQueue(Process* proc, bool canPreempt = false);
- void contextSwitch(Process* proc, CPU* cpu);
- void makeProcesses() {
- for (int i=0; i<n; i++){
- Process* proc = new Process();
- proc->id = i+1;
- if (i < pInt*n){
- //interactive process
- proc->cpu = false;
- proc->burstTime = randomVal(iBMin, iBMax);
- proc->userTime = randomVal(uMin, uMax);
- } else {
- //cpu process
- proc->cpu = true;
- proc->burstTime = randomVal(cBMin, cBMax);
- proc->cpuBursts = b;
- proc->userTime = randomVal(ioMin, ioMax);
- }
- proc->initialPriority = rand() % 5;
- proc->priority = proc->initialPriority;
- addToReadyQueue(proc);
- for (int j=0; j<int(cpus.size()); j++){
- cpus[j]->processesTime[proc->id] = 0;
- }
- }
- }
- bool shorterProcess(Process* p1, Process* p2) { return p1->burstTime - p1->t < p2->burstTime - p2->t; }
- int indexOfShortestProcess(std::vector<Process*> queue){
- int ret = 0;
- if (queue.empty()) return -1;
- Process* proc = queue[0];
- for (int i=1; i<int(queue.size()); i++){
- if (shorterProcess(queue[i], proc)){
- ret = i;
- proc = queue[i];
- }
- }
- return ret;
- }
- int indexOfHighestPriority(std::vector<Process*> queue){
- int ret = 0;
- if (queue.empty()) return -1;
- Process* proc = queue[0];
- for (int i=1; i<int(queue.size()); i++){
- if (queue[i]->priority < proc->priority){
- ret = i;
- proc = queue[i];
- }
- }
- return ret;
- }
- void resetCPUs(){
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- cpu->process = NULL;
- cpu->useTime = 0;
- cpu->notUseTime = 0;
- }
- }
- void addToReadyQueue(Process* proc, bool canPreempt){
- readyQueue.push_back(proc);
- std::cout << "[time " << int(t) << "ms] ";
- if (proc->cpu){
- std::cout << "CPU-bound";
- } else {
- std::cout << "Interactive";
- }
- std::cout << " process ID " << proc->id;
- std::cout << " entered ready queue (";
- std::cout << "requires " << int(proc->burstTime) << "ms CPU time; ";
- std::cout << "priority " << proc->priority << ")";
- std::cout << std::endl;
- //if can preempt, check if other job should be interrupted
- if (canPreempt &&
- algorithm == SJFP){
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process != NULL && !cpu->inContextSwitch
- && !cpu->process->userMode){
- if (proc->burstTime < cpu->process->burstTime - cpu->process->t){
- contextSwitch(proc, cpu);
- break;
- }
- }
- }
- }
- if (canPreempt &&
- algorithm == PP){
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process != NULL && !cpu->inContextSwitch
- && !cpu->process->userMode){
- if (proc->priority < cpu->process->priority){
- contextSwitch(proc, cpu);
- break;
- }
- }
- }
- }
- }
- void removeFromReadyQueue(Process* proc) {
- int index = -1;
- for (int i=0; i<int(readyQueue.size()); i++){
- if (readyQueue[i] == proc){
- index = i;
- break;
- }
- }
- if (index == -1) return;
- readyQueue.erase(readyQueue.begin()+index);
- }
- void contextSwitch(Process* proc, CPU* cpu) {
- Process* cpuProc = cpu->process;
- if (proc != NULL){
- removeFromReadyQueue(proc);
- }
- std::cout << "[time " << t << "ms] Context switch (";
- if (cpuProc == NULL){
- } else {
- std::cout << "swapping out process ID " << cpuProc->id;
- if (proc == NULL){
- std::cout << ")";
- } else {
- std::cout << " for ";
- }
- cpu->processOut = cpuProc;
- }
- if (proc != NULL){
- std::cout << "process ID " << proc->id << ")";
- }
- std::cout << std::endl;
- cpu->process = proc;
- cpu->inContextSwitch = true;
- cpu->contextSwitchTime = 0;
- }
- void increasePriority(Process* proc) {
- if (proc->priority <= 0)
- return;
- proc->priority--;
- std::cout << "[time " << t << "ms] Increased priority of ";
- if (proc->cpu) std::cout << "CPU-bound ";
- else std::cout << "Interactive ";
- std::cout << "process ID " << proc->id << " to " << proc->priority << " due to aging";
- std::cout << std::endl;
- }
- void terminateProcess(Process* proc) {
- std::cout << "[time " << t << "ms] CPU-bound process ID " << proc->id << " terminated ";
- std::cout << "(avg turnaround time " << (proc->totalTurnaround / proc->cpuBursts);
- std::cout << ", avg total wait time " << (proc->totalWait / proc->cpuBursts) << ")";
- std::cout << std::endl;
- terminatedProcesses.push_back(proc);
- }
- //does all actions that takes place in 1 ms
- void step() {
- //finish context switches
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->inContextSwitch && cpu->contextSwitchTime >= tCS){
- if (cpu->processOut != NULL){
- addToReadyQueue(cpu->processOut, true);
- }
- cpu->processOut = NULL;
- cpu->inContextSwitch = false;
- }
- }
- //processes completing
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process == NULL || cpu->inContextSwitch) continue;
- Process* proc = cpu->process;
- if (proc->userMode){ //i/o completed
- if (proc->t >= proc->userTime){
- //user i/o completed, go back to ready queue
- proc->turnaround = 0;
- proc->wait = 0;
- proc->priority = proc->initialPriority;
- proc->userMode = false;
- proc->t = 0;
- contextSwitch(NULL, cpu);
- }
- } else { //cpu burst completed
- std::cout << "[time " << t << "ms] ";
- if (proc->cpu) std::cout << "CPU-bound";
- else std::cout << "Interactive";
- std::cout << " process ID " << proc->id << " CPU burst done (turnaround time ";
- std::cout << proc->turnaround << "ms, total wait time ";
- std::cout << proc->wait << "ms)";
- std::cout << std::endl;
- if (proc->turnaround < minTurnaround) minTurnaround = proc->turnaround;
- if (proc->turnaround > maxTurnaround) maxTurnaround = proc->turnaround;
- totalTurnaround += proc->turnaround;
- if (proc->wait < minWait) minWait = proc->wait;
- if (proc->wait > maxWait) maxWait = proc->wait;
- totalWait += proc->wait;
- proc->totalTurnaround += proc->turnaround;
- proc->totalWait += proc->wait;
- if (proc->t >= proc->burstTime){
- if (proc->cpu){ //cpu-bound, keep track of cpu bursts
- proc->b++;
- if (proc->b >= proc->cpuBursts){
- //process done, should be terminated
- cpu->process = NULL;
- terminateProcess(proc);
- } else {
- //enter user mode
- proc->userMode = true;
- proc->t = 0;
- }
- } else { //interactive process
- //enter user mode
- proc->userMode = true;
- proc->t = 0;
- }
- }
- }
- }
- int index;
- Process* proc;
- switch (algorithm){
- case SJFNP:
- case SJFP:
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process == NULL && !cpu->inContextSwitch){
- //process with shortest job enters CPU
- if (!readyQueue.empty()){
- index = indexOfShortestProcess(readyQueue);
- proc = readyQueue[index];
- contextSwitch(proc, cpu);
- }
- }
- }
- break;
- case RR:
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- //fill all cpus' with a process
- if (cpu->process == NULL && !cpu->inContextSwitch){
- if (!readyQueue.empty()){
- index = 0; //since processes are pushed to the back of the readyQueue
- proc = readyQueue[index];
- contextSwitch(proc, cpu);
- }
- }
- }
- rrTimer++;
- if (rrTimer >= tSlice){
- //preform round robin
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->inContextSwitch) continue; //would prevent cpu from RR, not sure how to fix
- if (readyQueue.empty()) break;
- proc = readyQueue[0];
- contextSwitch(proc, cpu);
- }
- rrTimer = 0;
- }
- break;
- case PP:
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process == NULL && !cpu->inContextSwitch){
- //process with highest priority enters CPU
- if (!readyQueue.empty()){
- index = indexOfHighestPriority(readyQueue);
- proc = readyQueue[index];
- contextSwitch(proc, cpu);
- }
- }
- }
- break;
- }
- //increment time values
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->inContextSwitch){
- cpu->contextSwitchTime++;
- cpu->useTime++;
- if (cpu->process != NULL){
- cpu->process->timeInc(true);
- }
- if (cpu->processOut != NULL){
- cpu->processOut->timeInc(true);
- }
- } else if (cpu->process != NULL){
- cpu->useTime++;
- if (cpu->process != NULL){
- cpu->processesTime[cpu->process->id]++;
- cpu->process->timeInc(true);
- }
- } else {
- cpu->notUseTime++;
- }
- }
- for (int i=0; i<int(readyQueue.size()); i++){
- Process* proc = readyQueue[i];
- proc->timeInc(false);
- if (algorithm == PP){ //detect changing priority
- if (proc->wait % tAging == 0){
- increasePriority(proc);
- }
- }
- }
- t++;
- }
- //prints data after simulation
- void analysis(){
- int cpuUseTime = 0;
- int cpuTotalTime = 0;
- std::vector<int> cpuProcessesTime(n);
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- cpuUseTime += cpu->useTime;
- cpuTotalTime += cpu->useTime + cpu->notUseTime;// + cpu->contextSwitchTime;
- for (int j=0; j<n; j++){
- cpuProcessesTime[j] += cpu->processesTime[j+1];
- }
- }
- std::cout << std::endl;
- std::cout << "Turnaround time: min " << minTurnaround << " ms; ";
- std::cout << "avg " << std::setprecision(12) << (totalTurnaround*1.0 / n) << " ms; ";
- std::cout << "max " << maxTurnaround << " ms\n";
- std::cout << "Total wait time: min " << minWait << " ms; ";
- std::cout << "avg " << std::setprecision(12) << (totalWait*1.0 / n) << " ms; ";
- std::cout << "max " << maxWait << " ms\n";
- std::cout << "Average CPU utilization: " << std::setprecision(12) << (100.0*cpuUseTime / cpuTotalTime) << "%\n\n";
- std::cout << "Average CPU utilization per process: \n";
- for (int i=0; i<int(cpuProcessesTime.size()); i++){
- std::cout << (i+1) << ": " << std::setprecision(12) << (100.0*cpuProcessesTime[i] / cpuTotalTime) << "%\n";
- }
- }
- void reset() {
- t = 0;
- rrTimer = 0;
- minTurnaround = 99999999;
- maxTurnaround = 0;
- totalTurnaround = 0;
- minWait = 99999999;
- maxWait = 0;
- totalWait = 0;
- for (int i=0; i<int(cpus.size()); i++){
- CPU* cpu = cpus[i];
- if (cpu->process != NULL)
- terminatedProcesses.push_back(cpu->process);
- if (cpu->processOut != NULL)
- terminatedProcesses.push_back(cpu->processOut);
- cpu->reset();
- }
- for(int i=0; i<int(readyQueue.size()); i++){
- terminatedProcesses.push_back(readyQueue[i]);
- }
- readyQueue.clear();
- for(int i=0; i<int(terminatedProcesses.size()); i++){
- terminatedProcesses[i]->reset();
- addToReadyQueue(terminatedProcesses[i]);
- }
- terminatedProcesses.clear();
- }
- void run(){
- while (int(terminatedProcesses.size()) < int((1-pInt) * n)){
- step();
- }
- }
- int main(int argc, const char* argv[]) {
- //parse argv
- for (int i=1; i<argc; i++) {
- //example: pInt=.7 (variable = value)
- std::string arg(argv[i]);
- int index = (int) arg.find('=');
- if (index == -1) continue;
- std::string varStr = arg.substr(0, index);
- const char* c = arg.substr(index+1).c_str();
- if (varStr == "n") n = atoi(c);
- else if (varStr == "pInt") pInt = atof(c);
- else if (varStr == "iBMin") iBMin = atoi(c);
- else if (varStr == "iBMax") iBMax = atoi(c);
- else if (varStr == "uMin") uMin = atoi(c);
- else if (varStr == "uMax") uMax = atoi(c);
- else if (varStr == "cBMin") cBMin = atoi(c);
- else if (varStr == "cBMax") cBMax = atoi(c);
- else if (varStr == "b") b = atoi(c);
- else if (varStr == "ioMin") ioMin = atoi(c);
- else if (varStr == "ioMax") ioMax = atoi(c);
- else if (varStr == "m") m = atoi(c);
- else if (varStr == "tSlice") tSlice = atoi(c);
- else if (varStr == "tAging") tAging = atoi(c);
- else if (varStr == "tCS") tCS = atoi(c);
- }
- //make cpu's
- for (int i=0; i<m; i++){
- CPU* cpu = new CPU();
- cpus.push_back(cpu);
- }
- //run
- algorithm = SJFNP;
- std::cout << "Shortest-Job-First with no preemption:\n\n";
- makeProcesses();
- run();
- analysis();
- algorithm = SJFP;
- std::cout << "\n\nShortest-Job-First with preemption:\n\n";
- reset();
- run();
- analysis();
- algorithm = RR;
- std::cout << "\n\nRound-Robin:\n\n";
- reset();
- run();
- analysis();
- algorithm = PP;
- std::cout << "\n\nPreemptive Priority:\n\n";
- reset();
- run();
- analysis();
- //cleanup
- for (int i=0; i<(int) cpus.size(); i++){
- delete cpus[i];
- }
- cpus.clear();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement