Formal Documentation

#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; // The current simulation time. Cpu cpu; // The current CPU state. // 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; // Tracks the cumulative turnaround time for average turnaround time calculation. double cumulativeTimeDiff = 0; // Tracks the number of terminated processes for average turnaround time calculation. int numTerminatedProcesses = 0; // Sadly, C++ has no built-in way to trim strings. This function does the job for us. 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; } // This function takes a filename of a simulated process program. The file is opened // and parsed. The parsed instructions are then added to the passed-in program // vector. You do not need to do anything with this function, it is already complete. bool createProgram(const string &filename, vector<Instruction> &program) { ifstream file; int lineNum = 0; program.clear(); file.open(filename.c_str()); if (!file.is_open()) { char* curDir = getcwd(NULL, 0); cout << "Error opening file \"" << filename << "\" in \"" << curDir << "\"" << endl; free(curDir); 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) { // TODO: If runningState != -1 AND the cpu.timeSliceUsed equals or exceeds // cpu.timeSlice: // 1. Get the PCB entry for runningState. // 2. Lower the process priority (remember since the highest priority is zero, // you actually have to increment the priority to lower it). Also make sure to // not increment the priority past its maximum value. // 3. Push runningState on to the end of the correct readyStates queue (hint: use // pcbEntry.priority to select the correct queue. // 4. Update the pcbEntry: // a. Set state to STATE_READY. // b. Set the programCounter to cpu.programCounter. // c. Set the value to cpu.value. // d. Increment timeUsed by cpu.timeSliceUsed. // 5. Set runningState to -1. if (runningState != -1) { return; } // TODO: Get a new process to run, if possible, from the ready queue in // priority order. Remember that the highest priority is zero! The code below // needs to be updated/replaced since right now it only uses the highest priority // queue. // Get a new process to run, if possible, from the ready queue. if ( !readyStates[0].empty() ) { runningState = readyStates[0].front(); readyStates[0].pop_front(); } // 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; // TODO: Set cpu.timeSlice to the correct value (hint: use the // global PRIORITY_TIME_SLICES array and pcbEntry->priority) // TODO: Set cpu->timeSliceUsed to zero. cout << "Process running, pid = " << pcbEntry->processId << endl; } } // Implements the B operation. void block(void) { 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. 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(void) { 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(void) { 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. schedule(); } // Implements the U command. void unblock(void) { 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(void) { #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)) { delete pcbEntry; return 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 }