Your Task:

Implement a simulated Operating System Scheduler Since we are simulating the scheduler in this assignment, its OK to use C++ to compile your program. If you curious to why, its because this allows a little bit more higher-level functionality (abstraction from the hardware) to complete the program. The sample code is written in C++ using the g++ compiler. The program is very similar to C, but with a couple C++ libraries to make it easier to read from the file and print to the screen. The simulated scheduler should implement Round Robin Scheduling Assume there is only 1 CPU No process should be able to run concurrently for more than one quantum If a process runs for more than one quantum and didnt complete, it is put at the end of the ready queue When a process returns from a block state, it is also added to the back of the queue. To make it a bit easier, if a process blocks or terminates, assume that it happened at the end of a quantum. In other words, no process will ever be preempted in the middle of a quantum.

Sample Code: A significant amount of sample code is provided: feeder.cpp reads the input file, simulates the clock interrupts (clock ticks) representing each quantum). Calls the scheduler at each clock tick queues.cpp contains very helpful functions for managing queues push: add to the end (tail) of the queue pop: remove from head of the queue remove: for this assignment, there is a situation in which you would want to move from the middle of te queue (its like cutting in line). A function is provided to assist you. scheduler.cpp this is where most of your effort is needed. Keep track of the state of each process Output changes in process state Force only one process to be running on the CPU at any one time.

~Scheduler~

##ifndef SCHEDULER_H

define SCHEDULER_H

#include "queues.h"

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int INT_MAX = 2147483647;

extern int cpuTimer;

extern int maxWait;

#define TRUE 1

#define FALSE 0

#define READY 0

#define RUNNING 1

#define HALTED 2

#define BLOCKED 3

#define SUSPENDED 4

#define TERMINATED 5

double getAvgWait();

int scheduler();

void dispatch(my_queue**);

void updateState(my_queue*);

void process();

#endif

#include "scheduler.h"

bool cpuBusy = false;

int totalWait = 0;

int processesStarted = 0; //if a job is blocked, it counts twice.

int maxWait = 0;

//Simply used for statistics reporting

double getAvgWait()

{

return (double) totalWait / processesStarted;

}

//Routine triggered once per quantum (on simulated clock interrupt) to determine which

//process gets CPU time and maintains queues

int scheduler()

{

int i;

//cpu needs to be free to dispatch.....

if(cpuBusy == false && readyq != NULL)

{

my_queue* head = popQ(&readyq, &ready_tail);

dispatch(&head);

}

}

// This routine adds the specified task to the Processing queue.

// Maintaining FCFS philosophy, it is added to end

void dispatch(my_queue** t) {

my_queue* task = *t;

//update Statistics

int waitTime = cpuTimer - task->this_task.arrival_time;

totalWait+=waitTime;

processesStarted++;

if (waitTime > maxWait)

maxWait = waitTime;

*t = task;

}

//This routine updates the process states in the PCB (Process Control Block)

//Queues are updated maintaining FCFS philosophy

void updateState(my_queue* task)

{ }

~Queues~

#include "scheduler.h"

//Jobs that have not READY yet (hence, not loaded into memory, etc...)

my_queue* jobq;

my_queue* job_tail;

//Jobs that are READY to run, but need access to the CPU

my_queue* readyq;

my_queue* ready_tail;

//Jobs running on a CPU. This does not need to be a Queue, since we only have one CPU in this scenerio

my_queue* processing_head;

my_queue* processing_tail;

//Used for debugging. Print the contents of queue

void printQ(my_queue* temp)

{

while(temp!=NULL)

{

cout this_task.taskid this_task.arrival_time this_task.state

temp=temp->next;

}

}

void pushQ(my_queue** head, my_queue** node, my_queue** tail)

{

my_queue* h = *head;

my_queue* n = *node;

my_queue* t = *tail;

n->next = NULL;

n->prev = NULL;

//if queue is empty

if (t == NULL && h == NULL)

h = n;

if (t != NULL)

{

t->next = n;

n->prev = t;

}

t = n;

*head = h;

*tail = t;

*node = n;

}

my_queue* popQ(my_queue** head, my_queue** tail)

{

my_queue* h = *head;

my_queue* t = *tail;

my_queue* old_head = h;

if (h != NULL)

{

h = h->next;

//don't point to the rest of the queue

old_head->next = NULL;

old_head->prev = NULL;

if (h != NULL)

h->prev = NULL;

else

t = NULL;

}

else

return NULL;

*head = h;

*tail = t;

return old_head;

}

void removeQ(my_queue** head, my_queue** removeNode, my_queue** tail)

{

my_queue* h = *head;

my_queue* t = *tail;

my_queue* n = *removeNode;

my_queue* left = n->prev;

my_queue* right = n->next;

if(left != NULL)

left->next = right;

if (right != NULL)

right->prev = left;

if(n->prev == NULL)

h = right;

if(n->next == NULL)

t = left;

*head = h;

*tail = t;

}

#ifndef QUEUES_H

#define QUEUES_H

struct task_PCB {

int taskid;

int userno;

int state;

int cpu;

int est_runtime;

int time_run;

// Special for this assignment

int arrival_time;

int block_startTime;

int block_waitTime;

};

struct my_queue {

task_PCB this_task;

my_queue* next;

my_queue* prev;

};

extern my_queue* jobq;

extern my_queue* job_tail;

extern my_queue* readyq;

extern my_queue* ready_tail;

extern my_queue* processing_head;

extern my_queue* processing_tail;

void printQ(my_queue*);

void pushQ(my_queue**, my_queue**, my_queue**);

my_queue* popQ(my_queue**, my_queue**);

void removeQ(my_queue**, my_queue**, my_queue**);

#endif

~Feeder~

// - Feeder : Created initial processes, placed them on ready queue, established Linux timer, and started scheduler

#include "scheduler.h"

#include

#include

#include

int taskID = 0;

int cpuTimer = 0;

//Takes line from file and initializes PCB node

my_queue* constructTask(string s)

{

struct my_queue *new_task = (struct my_queue*) malloc(sizeof(struct my_queue));

new_task->this_task.taskid = taskID++;

new_task->this_task.state = READY;

new_task->this_task.est_runtime = INT_MAX;

new_task->this_task.time_run = 0;

new_task->this_task.arrival_time = INT_MAX;

new_task->this_task.block_startTime = INT_MAX;

new_task->this_task.block_waitTime = INT_MAX;

char buffer[256];

istringstream iss(s);

int count = 0;

do

{

string sub;

iss >> sub;

switch(count)

{

case 1:

new_task->this_task.taskid = atoi(sub.c_str());

case 3:

new_task->this_task.arrival_time = atoi(sub.c_str());

case 5:

new_task->this_task.est_runtime = atoi(sub.c_str());

case 7:

new_task->this_task.block_startTime = atoi(sub.c_str());

case 8:

new_task->this_task.block_waitTime = atoi(sub.c_str());

}

count++;

} while (iss);

return new_task;

}

int main(void)

{

//Read input file and load process jobs in jobs Queue

string t;

while(getline(cin, t))

{

cout

my_queue* new_task = constructTask(t);

pushQ(&jobq, &new_task, &job_tail);

}

cout

printQ(jobq);

//RUN SIMULATION

cpuTimer=0; //each increment represents one quantum.

while(jobq != NULL || readyq != NULL || processing_head != NULL && cpuTimer

{

cpuTimer++;

my_queue* current = jobq;

while(current!=NULL)

{

//task has arrived and is can be moved to readyQ

if (current->this_task.arrival_time

{

cout this_task.taskid

removeQ(&jobq, ¤t, &job_tail);

pushQ(&readyq, ¤t, &ready_tail);

current = jobq;

}

else

current = current->next;

}

scheduler();

}

cout

cout

cout

cout

return 0;

}

~MakeFile~

all:

g++ scheduler.cpp queues.cpp feeder.cpp -o hw4

clean: rm hw4

Test/Input Data: Non-Blocking Processes: The input data depicts processes arriving and requesting CPU time. For instance, in line #1, we see a process #1 is ready to run at quantum #1 (arrive1). It will require two quantums of CPU time to be able to complete (estTime- nputFile bd 1 process 1 arrive 1 estTime 2 Blocking Processes: Imagine some processes will make a system call and therefore block. For instance, in line #2, we see an example. Process #2 arrives at (quantum : 2). It requires 2 guantums of CPU time to complete (estTime 2) and will block after the first running for one quantum (block 1 2). Since the kernel-level request takes time to complete (e.g. access data on disk), the system needs to block for a minimal amount of time. In this example, it must block for two guantums (block 1 2) scheduler.cpp.M EinputFilebt process 2 arrive 2 estTime 2 block 1 2