Formal Documentation

#define ENABLE_COMMANDER #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; // For iLab 3, unused for iLab 2 unsigned int timeUsed; // For iLab 3, unused for iLab 2 }; 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. deque<int> readyState; // A queue of PCB indices for ready processes. deque<int> blockedState; // A queue of 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) { // TODO: Implement // 1. Set the CPU value to the passed-in value. } // Implements the A operation. void add(int value) { // TODO: Implement // 1. Add the passed-in value to the CPU value. } // Implements the D operation. void decrement(int value) { // TODO: Implement // 1. Subtract the integer value from the CPU value. } // Performs scheduling. void schedule(void) { // TODO: Implement // 1. Return if there is still a processing running (runningState != -1). // There is no need to schedule if a process is already running (until iLab // 3) // 2. Get a new process to run, if possible, from the ready queue. // 3. If we were able to get a new process to run: // a. Mark the processing as running (update new process's PCB state) // b. Update the CPU structure with the PCB entry details (program, // program counter, value, etc.) } // Implements the B operation. void block(void) { // TODO: Implement // 1. Add the PCB index of the running process (stored in runningState) to // the blocked queue. // 2. Update the process's PCB entry // a. Change the PCB's state to blocked. // b. Store the CPU program counter in the PCB's program counter. // c. Store the CPU's value in the PCB's value. // 3. Update the running state to -1 (basically mark no process as running). // Note that a new process will be chosen to run later (via the Q command // code calling the schedule() function). } // Implements the E operation. void end(void) { // TODO: Implement // 1. Get the PCB entry of the running process. // 2. Update the cumulative time difference (increment it by // timestamp + 1 - start time of the process). // 3. Increment the number of terminated processes. // 4. Update the running state to -1 (basically mark no process as running). // Note that a new process will be chosen to run later (via the Q command // code calling the schedule function). // 5. You can choose to free the memory for the PCB entry here if you want. // Otherwise it will get freed when the simulation terminates. } // Implements the F operation. void fork(int value) { // TODO: Implement // 1. Create a new PCB entry. // 2. Get the PCB entry for the current running process. // 3. Ensure the passed-in value is not out of bounds. // 4. Populate the PCB entry created in #1 // a. Set the process ID to the PCB index to add (pcbTable.size()). // b. Set the parent process ID to the process ID of the running process // (use the running process's PCB entry to get this). // c. Set the program counter to the cpu program counter. // d. Set the value to the cpu value. // e. Set the priority to the same as the parent process's priority. // f. Set the state to the ready state. // g. Set the start time to the current timestamp // 5. Add the new PCB entry to the PCB table. // 6. Add the new pcb index (the process ID on the new PCB entry) to the // ready queue. // 7. Increment the cpu's program counter by the value read in #3 } // Implements the R operation. void replace(string &argument) { // TODO: Implement // 1. Clear the CPU's program (cpu.pProgram->clear()). // 2. Use createProgram() to read in the filename specified by argument into // the CPU (*cpu.pProgram) // a. Consider what to do if createProgram fails. I printed an error, // incremented the cpu program counter and then returned. Note that // createProgram can fail if the file could not be opened or did not // exist. // 3. Set the program counter to 0. } // 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++; schedule(); } // Implements the U command. void unblock(void) { // TODO: Implement // 1. If the blocked queue contains any processes: // a. Remove a process form the front of the blocked queue. // b. Add the process to the ready queue. // c. Change the state of the process to ready (update its PCB entry). // 2. Call the schedule() function to give an unblocked process a chance to // run (if possible). } // Implements the P command. void print() { cout << "Print command is not implemented until iLab 3" << endl; } // 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 = 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 }