Project Description: Background: The job of the CPU is to fetch, decode, execute an instruction and continue these steps. Imagine we have one processor and many processes such as email, word, C compiler and so on. The Operation System (OS) divides time in small portions (quantum of time) and assigns CPU to each process (email, word, or the compiler). To make this work, a queue is needed to make all the processes wait for their turn. A timer and interrupt system needed to interrupt the CPU after the quantum time for a process is over. Structures are needed to save all the register values of the CPU and let the registers to be used by the other process. Then after the first process gets the CPU for another time, the saved CPU values will be placed in CPU registers one more time. It looks like as if each process has its own CPU. We want to simulate what is explained. For example, a structure or class is defined which will play the role of CPU registers. Part of the code you will write will do the function of the CPU. In other words, CPU will be a simulation of the CPU. An integer field is designated for PC (program counter) and another field for the accumulator. Also, to simplify this simulation, the project has defined a simple set of instruction set. For example, your code reads the next instruction from the array or a file (i.e. this is the simulation of CPU fetching the next instruction). Then using a switch structure, your code decides if the instruction is a S 20 or A 20 and so on (i.e. this is the simulation of decoding the instruction by the CPU). If the instruction is S 20 then the value 20 is stored in a variable (i.e. this is the simulation of the execution cycle of the CPU where the value 20 is placed in the accumulator). To make this simulation realistic, two processes will be created that will communicate to each other using a pipe. Rather than having a timer and an interrupt system to interrupt CPU after a quantum amount of time, we will use the keyboard and type characters such as Q, U, P and T. When the user types character Q, it means one time unit has passed. So, CPU can fetch and execute the next instruction. Note that the CPU is also a simulation. In other words, your code will read the next instruction from an array or a file and execute that instruction. The set of instructions defined in the project are simple. For example, the instruction S 20 means to set the value of an integer variable to 20. While this program (process) is performing these tasks another process reads the keyboard for characters such as Q, U, P and T. These two processes communicate with each other using a pipe. Pipe is like a queue that is shared by the two processes. The first process writes the character to the pipe (to the queue) and the other process gets it from the other end of the pipe. Your program should output a prompt such as $ and wait for the user input. The user can input one of these four characters (Q, U, P or T) as described below: 1. Q: End of one unit of time. 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 must end when the user enters T. This part of the code is called the commander process. Process Management Simulation Part Process management simulation manages the execution of simulated processes. Each simulated process is comprised of a program that manipulates (sets/updates) the value of a single integer variable. Thus the state of a simulated process at any instant is comprised of the value of its integer variable and the value of its program counter. A simulated process' program consists of a sequence of instructions. There are seven types of instructions as follows: ● Sn: Set the value of the integer variable to n, where n is an integer. • An: Add n to the value of the integer variable, where n is an integer. ● Dn: Subtract n from the value of the integer variable, where n is an integer. • B: Block this simulated process. E: Terminate this simulated process. ● ● 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. 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. An example of a program for a simulated is as follows: S 1000 A 19 A 20 D 53 A 55 F1 R file a F 1 R file b F 1 R file_c F 1 R file d F 1 R file_e E You may store the program of a simulated process in an array, with one array entry for each instruction. Process Manager Process The process manager process simulates five process management functions: creation of new (simulated) processes, replacing the current process image of a simulated process with a new process image, management of process state transitions, process scheduling, and context switching. In addition, it spawns a reporter process whenever it needs to print out the state of the system. The process manager creates the first simulated process (process id = 0). Program for this process is read from a file (filename: init). This is the only simulated process created by the process manager on its own. All other simulated processes are created in response to the execution of the F instruction. Process manager: Data structures The process manager maintains six data structures: Time, Cpu, PcbTable, ReadyState, BlockedState, and RunningState. Time is an integer variable initialized to zero. Cpu is used to simulate the execution of a simulated process that is in running state. It should include data members to store a pointer to the program array, current program counter value, integer value, and time slice of that simulated process. In addition, it should store the number of time units used so far in the current time slice. PcbTable is an array with one entry for every simulated process that hasn't finished its execution yet. Each entry should include data members to store process id, parent process id, a pointer to program counter value (initially 0), integer value, priority, state, start time, and CPU time used so far. ReadyState stores all simulated processes (PcbTable indices) that are ready to run. This can be implemented using a queue or priority queue data structure. BlockedState stores all processes (PcbTable indices) that are currently blocked. This can be implemented using a queue data structure. Finally, RunningState stores the PcbTable index of the currently running simulated process. Process manager: Processing input commands After creating the first process and initializing all its data structures, the process manager repeatedly receives and processes one command at a time from the commander process (read via the pipe). On receiving a Q command, the process manager executes the next instruction of the currently running simulated process, increments program counter value (except for For 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 process manager ensures that no more than one reporter process is running at any moment. Process manager: Executing simulated processes The process manager executes the next instruction of the currently running simulated process on receiving a Q command from the commander process. Note that this execution is completely confined to the Cpu data structure, i.e. PcbTable is not accessed. Instructions S, A and D update the integer value stored in Cpu. Instruction B moves the currently running simulated process to the blocked state and moves a process from the ready state to the running state. This will result in a context switch. Instruction E terminates the currently running simulated process, frees up all memory (e.g. program array) associated with that process and updates the PcbTable. A simulated process from the ready state is moved to running state. This also results in a context switch. Instruction F results in the creation of a new simulated process. A new entry is created in the PcbTable for this new simulated process. A new (unique) process id is assigned and the parent process id is process id of the parent simulated process. Start time is set to the current Time value and CPU time used so far is set to 0. The program array and integer value of the new simulated process are a copy of the program array and integer value of the parent simulated process. The new simulated process has the same priority as the parent simulated process. The program counter value of the new simulated process is set to the instruction immediately after the F instruction, while the program counter value of the of the parent simulated process is set to n instructions after the next instruction (instruction immediately after F. The new simulated process is created in the ready state. Finally, the R instruction results in replacing the process image of the currently running simulated process. Its program array is overwritten by the code in file filename, program counter value is set to 0, and integer value is undefined. Note that all these changes are made only in the Cpu data structure. Process id, parent process id, start time, CPU time used so far, state, and priority remain unchanged. Process manager: Scheduling The process manager also implements a scheduling policy. You may experiment with a scheduling policy of multiple queues with priority classes. In this policy, the first simulated process (created by the process manager) starts with priority 0 (highest priority). There are a maximum of four priority classes. Time slice (quantum size) for priority class 0 is 1 unit of time; time slice for priority class 1 is 2 units of time; time slice for priority class 2 is 4 units of time; and time slice for priority class 3 is 8 units of time. If a running process uses its time slice completely, it is preempted and its priority is lowered. If a running process blocks before its allocated quantum expires, its priority is raised. Process manager: Context Switching Context switching involves copying the state of the currently running simulated process from Cpu to PcbTable (unless this process has completed its execution), and copying the state of the newly scheduled simulated process from PcbTable to Cpu. Reporter Process The reporter process prints the current state of the system on the standard output and then terminates. The output from the reporter process appears as follows: