C++ Formal Documentation
debmouti190c
lab3_scheduler2.docxECET360 Week 3 Lab Robert Weymouth
// ECET360 Lab 3
// Comment out the two lines below to disable the pipe() and fork() behavior of
// the program. This may make debugging much easier since there is only one
// process to debug.
// #define ENABLE_COMMANDER
// #define ENABLE_REPORTER
#include <cctype> // for toupper()
#include <cstdlib> // for EXIT_SUCCESS and EXIT_FAILURE
#include <cstring> // for strerror()
#include <cerrno> // for errno
#include <deque> // for deque (used for ready and blocked queues)
#include <fstream> // for ifstream (used for reading simulated process programs)
#include <iostream> // for cout, endl, and cin
#include <sstream> // for stringstream (for parsing simulated process programs)
#include <sys/wait.h> // for wait()
#include <unistd.h> // for pipe(), read(), write(), close(), fork(), and _exit()
#include <vector> // for vector (used for PCB table)
using namespace std;
class Instruction {
public:
char operation;
int intArg;
string stringArg;
};
class Cpu {
public:
vector<Instruction> *pProgram;
int programCounter;
int value;
int timeSlice;
int timeSliceUsed;
};
enum State {
STATE_READY,
STATE_RUNNING,
STATE_BLOCKED
};
class PcbEntry {
public:
int processId;
int parentProcessId;
vector<Instruction> program;
unsigned int programCounter;
int value;
unsigned int priority;
State state;
unsigned int startTime;
unsigned int timeUsed;
};
// The number of valid priorities.
#define NUM_PRIORITIES 4
// An array that maps priorities to their allotted time slices.
static const unsigned int PRIORITY_TIME_SLICES[NUM_PRIORITIES] = {
1,
2,
4,
8
};
unsigned int timestamp = 0;
Cpu cpu;
// For the states below, -1 indicates empty (since it is an invalid index).
int runningState = -1; // The index of the running process in the PCB table.
// readyStates is an array of queues. Each queue holds PCB indices for ready processes
// of a particular priority.
deque<int> readyStates[NUM_PRIORITIES];
deque<int> blockedState; // A queue fo PCB indices for blocked processes.
// In this implementation, we'll never explicitly clear PCB entries and the
// index in the table will always be the process ID. These choices waste memory,
// but since this program is just a simulation it the easiest approach.
// Additionally, debugging is simpler since table slots and process IDs are
// never re-used.
vector<PcbEntry *> pcbTable;
double cumulativeTimeDiff = 0;
int numTerminatedProcesses = 0;
// Sadly, C++ has no built-in way to trim strings:
string &trim(string &argument) {
string whitespace(" \t\n\v\f\r");
size_t found = argument.find_last_not_of(whitespace);
if (found != string::npos) {
argument.erase(found + 1);
argument.erase(0, argument.find_first_not_of(whitespace));
} else {
argument.clear(); // all whitespace
}
return argument;
}
bool createProgram(const string &filename, vector<Instruction> &program) {
ifstream file;
int lineNum = 0;
program.clear();
file.open(filename.c_str());
if (!file.is_open()) {
cout << "Error opening file " << filename << endl;
return false;
}
while (file.good()) {
string line;
getline(file, line);
trim(line);
if (line.size() > 0) {
Instruction instruction;
instruction.operation = toupper(line[0]);
instruction.stringArg = trim(line.erase(0, 1));
stringstream argStream(instruction.stringArg);
switch (instruction.operation) {
case 'S': // Integer argument.
case 'A': // Integer argument.
case 'D': // Integer argument.
case 'F': // Integer argument.
if (!(argStream >> instruction.intArg)) {
cout << filename << ":" << lineNum
<< " - Invalid integer argument "
<< instruction.stringArg << " for "
<< instruction.operation << " operation" << endl;
file.close();
return false;
}
break;
case 'B': // No argument.
case 'E': // No argument.
break;
case 'R': // String argument.
// Note that since the string is trimmed on both ends,
// filenames with leading or trailing whitespace (unlikely)
// will not work.
if (instruction.stringArg.size() == 0) {
cout << filename << ":" << lineNum
<< " - Missing string argument" << endl;
file.close();
return false;
}
break;
default:
cout << filename << ":" << lineNum
<< " - Invalid operation, " << instruction.operation
<< endl;
file.close();
return false;
}
program.push_back(instruction);
}
lineNum++;
}
file.close();
return true;
}
// Implements the S operation.
void set(int value) {
cpu.value = value;
cout << "Set CPU value to " << value << endl;
}
// Implements the A operation.
void add(int value) {
cpu.value += value;
cout << "Incremented CPU value by " << value << endl;
}
// Implements the D operation.
void decrement(int value) {
cpu.value -= value;
cout << "Decremented CPU value by " << value << endl;
}
// Performs scheduling.
void schedule(void)
{
cout <<"cpu timeslice used " <<cpu.timeSliceUsed<<endl;
cout <<"cpu timeslice " <<cpu.timeSlice<<endl;
if ((runningState != -1) && (cpu.timeSliceUsed >= cpu.timeSlice)) {
// The currently running process consumed its entire time slice.
PcbEntry *pcbEntry = pcbTable[runningState];
// Lower the process priority.
if (pcbEntry->priority >= 0 && pcbEntry->priority < (NUM_PRIORITIES - 1)) {
pcbEntry->priority++;
}
readyStates[pcbEntry->priority].push_back(runningState);
cout << "Process exceeded time slice, pid = " << pcbEntry->processId <<
endl;
pcbEntry->state = STATE_READY;
pcbEntry->programCounter = cpu.programCounter;
pcbEntry->value = cpu.value;
pcbEntry->timeUsed += cpu.timeSliceUsed;
runningState = -1;
}
if (runningState != -1) {
return;
}
// Get a new process to run, if possible, from the ready queue in priority
// order.
for (int index = 0; index < NUM_PRIORITIES; index++) {
if (!readyStates[index].empty()) {
runningState = readyStates[index].front();
readyStates[index].pop_front();
break;
}
}
// Make sure there is a process to run.
if (runningState != -1) {
// Mark the process as running.
PcbEntry *pcbEntry = pcbTable[runningState];
pcbEntry->state = STATE_RUNNING;
// Update the CPU with new PCB entry details.
cpu.pProgram = &pcbEntry->program;
cpu.programCounter = pcbEntry->programCounter;
cpu.value = pcbEntry->value;
cpu.timeSlice = PRIORITY_TIME_SLICES[pcbEntry->priority];
cpu.timeSliceUsed = 0;
cout << "Process running, pid = " << pcbEntry->processId << endl;
}
// Implements the B operation.
void block() {
PcbEntry *pcbEntry = pcbTable[runningState];
// TODO: Raise the process priority (remember since the highest priority is zero,
// you actually have to decrement the priority to raise it). Also make sure to
// not decrement the priority below zero.
if (pcbEntry->priority > 0 && pcbEntry->priority <= (NUM_PRIORITIES - 1)) {
pcbEntry->priority--;
}
blockedState.push_back(runningState);
pcbEntry->state = STATE_BLOCKED;
pcbEntry->programCounter = cpu.programCounter;
pcbEntry->value = cpu.value;
runningState = -1;
cout << "Blocked process, pid = " << pcbEntry->processId << endl;
}
// Implements the E operation.
void end() {
PcbEntry *pcbEntry = pcbTable[runningState];
// Add 1 to account for the time to execute the E operation.
cumulativeTimeDiff += (double) (timestamp + 1 - pcbEntry->startTime);
numTerminatedProcesses++;
cout << "Ended process, pid = " << pcbEntry->processId << endl;
runningState = -1;
}
// Implements the F operation.
void fork(int value) {
int pcbIndex = (int) pcbTable.size();
PcbEntry *runningPcbEntry = pcbTable[runningState];
PcbEntry *pcbEntry = new PcbEntry();
pcbEntry->processId = pcbIndex;
pcbEntry->parentProcessId = runningPcbEntry->processId;
pcbEntry->program = runningPcbEntry->program;
pcbEntry->programCounter = cpu.programCounter;
pcbEntry->value = cpu.value;
pcbEntry->priority = runningPcbEntry->priority;
pcbEntry->state = STATE_READY;
pcbEntry->startTime = timestamp + 1;
pcbEntry->timeUsed = 0;
pcbTable.push_back(pcbEntry);
// TODO: Update the line below to use the correct readyStates queue.
readyStates[0].push_back(pcbIndex);
cout << "Forked new process, pid = " << pcbEntry->processId << endl;
if ((value < 0) ||
(cpu.programCounter + value >= cpu.pProgram->size())) {
cout << "Error executing F operation, ending parent process" << endl;
end();
}
cpu.programCounter += value;
}
// Implements the R operation.
void replace(string &argument) {
if (!createProgram(argument, *cpu.pProgram)) {
cout << "Error executing R operation, ending process" << endl;
end();
return;
}
cpu.programCounter = 0;
cout << "Replaced process with " << argument << ", pid = "
<< pcbTable[runningState]->processId << endl;
}
// Implements the Q command.
void quantum() {
Instruction instruction;
if (runningState == -1) {
cout << "No processes are running" << endl;
++timestamp;
return;
}
if (cpu.programCounter < cpu.pProgram->size()) {
instruction = (*cpu.pProgram)[cpu.programCounter];
cpu.programCounter++;
} else {
cout << "End of program reached without E operation" << endl;
instruction.operation = 'E';
}
switch (instruction.operation) {
case 'S':
set(instruction.intArg);
break;
case 'A':
add(instruction.intArg);
break;
case 'D':
decrement(instruction.intArg);
break;
case 'B':
block();
break;
case 'E':
end();
break;
case 'F':
fork(instruction.intArg);
break;
case 'R':
replace(instruction.stringArg);
break;
}
timestamp++;
// TODO: Increment cpu.timeSliceUsed.
cpu.timeSliceUsed = cpu.timeSliceUsed + 1;
schedule();
}
// Implements the U command.
void unblock() {
if (!blockedState.empty()) {
int pcbIndex = blockedState.front();
PcbEntry *pcbEntry = pcbTable[pcbIndex];
blockedState.pop_front();
// TODO: Update the line below to use the correct readyStates queue.
readyStates[0].push_back(pcbIndex);
pcbEntry->state = STATE_READY;
cout << "Unblocked process, pid = " << pcbEntry->processId << endl;
}
schedule();
}
// Implements the P command.
void print() {
#ifdef ENABLE_REPORTER
pid_t pid;
pid = fork();
if (pid == -1) {
cout << "fork:" << strerror(errno) << endl;
return;
}
if (pid != 0) {
// Wait for the reporter process to exit.
wait(NULL);
return;
}
#endif
// TODO: Implement all of the printing logic.
#ifdef ENABLE_REPORTER
_exit(EXIT_SUCCESS);
#endif
}
// Function that implements the process manager.
int runProcessManager(int fileDescriptor) {
PcbEntry *pcbEntry = new PcbEntry();
// Attempt to create the init process.
if (!createProgram("init", pcbEntry->program)) {
return (int) EXIT_FAILURE;
}
pcbEntry->processId = (int) pcbTable.size();
pcbEntry->parentProcessId = -1;
pcbEntry->programCounter = 0;
pcbEntry->value = 0;
pcbEntry->priority = 0;
pcbEntry->state = STATE_RUNNING;
pcbEntry->startTime = 0;
pcbEntry->timeUsed = 0;
pcbTable.push_back(pcbEntry);
runningState = pcbEntry->processId;
cout << "Running init process, pid = " << pcbEntry->processId << endl;
cpu.pProgram = &(pcbEntry->program);
cpu.programCounter = pcbEntry->programCounter;
cpu.value = pcbEntry->value;
timestamp = 0;
double avgTurnaroundTime = 0;
// Loop until a 'T' is read, then terminate.
char ch;
do {
// Read a command character from the pipe.
if (read(fileDescriptor, &ch, sizeof (ch)) != sizeof (ch)) {
// Assume the parent process exited, breaking the pipe.
break;
}
// Ignore whitespace characters.
if (isspace(ch)) {
continue;
}
// Convert commands to a common case so both lower and uppercase
// commands can be used.
ch = toupper(ch);
switch (ch) {
case 'Q':
quantum();
break;
case 'U':
unblock();
break;
case 'P':
print();
break;
case 'T':
if (numTerminatedProcesses != 0) {
avgTurnaroundTime = cumulativeTimeDiff
/ (double) numTerminatedProcesses;
}
cout << "The average turnaround time is " << avgTurnaroundTime
<< "." << endl;
break;
default:
cout << "Unknown command, " << ch << endl;
}
} while (ch != 'T');
// Cleanup any remaining PCB entries.
for (vector<PcbEntry *>::iterator it = pcbTable.begin();
it != pcbTable.end(); it++) {
delete *it;
}
pcbTable.clear();
return EXIT_SUCCESS;
}
// Main function that implements the commander.
int main(int argc, char *argv[]) {
#ifdef ENABLE_COMMANDER
int pipeDescriptors[2];
pid_t processMgrPid;
char ch;
int result;
// Create a pipe.
if (pipe(pipeDescriptors) == -1) {
// Print an error message to help debugging.
cout << "pipe: " << strerror(errno) << endl;
return EXIT_FAILURE;
}
// Create the process manager process.
processMgrPid = fork();
if (processMgrPid == -1) {
// Print an error message to help debugging.
cout << "fork: " << strerror(errno) << endl;
return EXIT_FAILURE;
}
if (processMgrPid == 0) {
// The process manager process is running.
// Close the unused write end of the pipe for the process manager
// process.
close(pipeDescriptors[1]);
// Run the process manager.
result = runProcessManager(pipeDescriptors[0]);
// Close the read end of the pipe for the process manager process (for
// cleanup purposes).
close(pipeDescriptors[0]);
_exit(result);
} else {
// The commander process is running.
// Close the unused read end of the pipe for the commander process.
close(pipeDescriptors[0]);
// Loop until a 'T' is written or until the pipe is broken.
do {
// Read a command character from the standard input.
cin >> ch;
// Pass commands to the process manager process via the pipe.
if (write(pipeDescriptors[1], &ch, sizeof (ch)) != sizeof (ch)) {
// Assume the child process exited, breaking the pipe.
break;
}
} while (ch != 'T');
// Wait for the process manager to exit.
wait(&result);
// Close the write end of the pipe for the commander process (for
// cleanup purposes).
close(pipeDescriptors[1]);
}
return result;
#else
// Run the Process Manager directly.
return runProcessManager(fileno(stdin));
#endif
}
Operator Instructions
Once the program is running the operator can enter one of four characters described below.
1. Q: Executes a line of instruction. 2. U: Unblock the first simulated process in blocked queue. 3. P: Print the current state of the system. 4. T: Print the average turnaround time, and terminate the system.
The program will prompt the user/operator and wait for input.
On receiving a Q command, the process manager executes the next instruction of the currently running simulated process, increments program counter value (except for F or R instructions), increments Time, and then performs scheduling. Note that scheduling may involve performing context switching.
On receiving a U command, the process manager moves the first simulated process in the blocked queue to the ready state queue array.
On receiving a P command, the process manager spawns a new reporter process.
On receiving a T command, the process manager first spawns a reporter process and then terminates after termination of the reporter process.
The simulated process program consists of a sequence of instructions will initiate the program . There are seven types of instructions as follows:
1. S n: Set the value of the integer variable to n, where n is an integer.
2. A n: Add n to the value of the integer variable, where n is an integer.
3. D n: Subtract n from the value of the integer variable, where n is an integer.
4. B: Block this simulated process.
5. E: Terminate this simulated process.
6. F n: Create a new (simulated) process. The new (simulated) process is an exact copy of the parent (simulated) process. The new (simulated) process executes from the instruction immediately after this (F) instruction, while the parent (simulated) process continues its execution n instructions after the next instruction.
7. R filename: Replace the program of the simulated process with the program in the file filename, and set program counter to the first instruction of this new program.
Page 8 of 25
