CS330 Phase Three
Process State and CPU Scheduling
In this phase, you will implement the operations shown in the process state diagram, which is the pictorial representation of the possible states for a process and the transitions between these states. Use these numeric ids for the processes: Ready = 0, Running = 1, and Waiting = 2. Thus, you will provide a means of executing programs as processes and a scheduler to choose which process to run next.
The new instructions for this phase are: PTexecute, PTshowprocesses, PTshowscheduler, and PTsetquantum. You should also add the ability to SOS to print a message indicating that it is idle, when at least one Waiting process exists and no other process is available to execute at the current time.
A major part of this phase is simulating the scheduling of processes. CPU scheduling (or short-term scheduling) is the repeated choosing of how to allocate processor time to ready processes, i.e., processes that could run if given the CPU. Whenever the CPU scheduler is run, it chooses one of the ready processes to become the running process.
In this phase, we will make use of the
first two items on each line in an input file, such as in3-01.txt. The first
item gives the time when the instruction is available to be executed. The
time must be greater than or equal to the time of the most recent
instruction with a valid time field previous instruction in the input
file; i.e., the most recent line that did not cause a time travel error.
If not, give a “Time travel not supported” error message and ignore the
instruction. The second item tells the user id of the user executing
the instruction.
You will write a scheduler to supervise the execution of commands. Any existing instruction from Phase 1 or 2, such as FSmount, FSdump, FScopy etc., will be run by the scheduler at the time given for the command or later. It is assumed that any instruction, other than the PTexecute command, requires one unit of time. Only processes created by the PTexecute command are assigned process ids, starting with 0, 1, 2, 3, ….
The PTexecute command causes SOS to load and execute an .xex minifile. If the given file name does not end in “.xex”, give a “Invalid name for executable minifile” error message. The PTexecute instruction itself requires one unit of time, but it loads the minifile into simulated memory and puts an entry for it in the Ready queue. In more detail, for an PTexecute instruction, SOS first checks that the specified .xex minifile exists. If it does not, give a “Specified executable minifile is not available” error message. If the user does not have the appropriate execute (x) permission, give an “Insufficient permission to execute minifile” error message. If insufficient simulated memory remains to load the complete executable minifile (.xex minifile), give an “Insufficient memory available to load executable” error message. In case of this error, also remove the executable minifile from the simulated memory (by resetting the NextAvailableMemoryLocation variable indicating the next location to be allocated to its value before this PTexecute statement was encountered). Otherwise, an entry in the process table should be created/updated to show the process id, the .xex minifile name, the user id, the start time (time that the PTexecute instruction was executed), the elapsed time for the process (including one time unit for the original PTexecute instruction), the state at the end of this time unit (Ready), the starting address, the limit (i.e., the number of instructions in the .xex minifile), and the current relative address (PC). The user id can be obtained from the line containing the execute instruction. The starting time is the time when the PTexecute instruction began execution. The code (r, s, x) from the .xex minifile should be copied to the next available area in the simulated memory, which is described below. The PC gives the offset past the starting address where the next instruction for the process should be executed from; PC should initially be set to 0. In an .xex minifile, every line says ‘s’ for sleep, ‘r’ for run, or ‘x’ for exit. If any other instruction is present, give an “Invalid command in executable file” error message, and ignore the command. If any non-newline characters follow the ‘r’ or ‘x’, give an “Invalid command in executable file” error message, and ignore the command. An ‘s’ is followed by an integer indicating the number of units of time to sleep (the length of the time to be spent in the Waiting state). If ‘s’ is not followed by an integer, give an “Invalid command in executable file” error message, and ignore the command. If the integer in the sleep command is zero or negative, give an “Invalid sleep time” error message and ignore the command.
Example fast.xex:
r
r
r
s 6
r
r
r
s 4
r
r
r
r
r
x
When a sleep (s) command is executed, the process is placed in the Waiting state and the time that it should be awoken is specified as the current time plus the sleep time plus one. For example, if a process executes a sleep instruction at time 29 and the specified amount of time to sleep is 5, the time to awaken should be set as 35 (so it sleeps during the five time intervals [30,31], [31,32], [32,33], [33,34], and [34,35]). A separate queue containing all Waiting processes should be maintained. In each entry of the queue, you need to store the wakeup time and the process id for a sleeping process.
To implement scheduling, execute most instructions immediately and execute .xex files using the round robin (RR) algorithm. This algorithm is based on a single queue called the Ready queue. You should provide a PTsetquantum command for changing the quantum size for the Ready queue. The PTsetquantum command causes a change in the quantum size for all subsequent CPU bursts after its execution.
The PTshowprocesses command causes all ready, running, and waiting processes to be shown in order of process id.
Actions to be performed to simulate the scheduler:
To initialize, set the Ready queue and the Waiting queue to empty and the time to 0.
Then repeatedly perform the following two steps.
1. First for every process that is Waiting: If the time it was Waiting for is less than or equal to the current time, remove it from the Waiting queue, change the state of the process to Ready, and place it at the back of the Ready queue.
2. (a) If the next instruction in the input file is for a time that is less than or equal to the current time (but not before the previous instruction in the file!), execute it immediately.
(b) Otherwise if at least one process is in the Ready queue:
o remove the first process from the front of the Ready queue;
o change its state to Running;
o execute up to one quantum’s worth of instructions for the process:
§ if the current command is ‘x’,
· print a message
<time> <userid> Process <processid> exited
· delete the process from the process table
§ if current command is ‘s’, change the state of the process to Waiting, move it to the Waiting queue, print the message below, and advance the current relative address (PC) for the process by one:
<time> <userid> Process <processid> will sleep until <new time>
§ if current command is ‘r’, print the message below, and then advance the current relative address (PC) for the process by one:
<time> <userid> Process <processid> runs, PC <PC>, qr = <int>
The value given after qr is the time remaining in the quantum. If the quantum size is q then qr will count down q – 1, q – 2, …, 0 for the series of instructions executed by a process if it completes its quantum.
o if the process has not exited and is still in the Running state at the end of the quantum, change its state to Ready and add it at the end of the Ready queue.
(c) Otherwise (if no processes are in the Ready queue but either input remains in the input file or processes remain in the Waiting queue), print an Idle message:
o <time> 0 Idle
THE FOLLOWING MORE DETAILED ALGORITHM IS INTENDED TO BE EQUIVALENT TO THE ABOVE DESCRIPTION. IF YOU FIND ANY EXAMPLE WHERE IT IS NOT, PLEASE LET ME KNOW.
time = 0
read first instruction from input file
repeat forever:
repeat while the time of the next item in the Waiting queue is less than or equal to the current time,
remove it from the Waiting queue,
change the state of the process to Ready, and
place it at the back of the Ready queue.
end repeat while
if the next time in the input file is less than or equal to the current time
execute it immediately
increment time
read the next instruction from the input file.
else if at least one process is in the Ready queue:
remove the first process from the front of the Ready queue;
change its state to Running;
repeat for up to one quantum’s worth of instructions for the process:
execute instruction
§ if the current command is ‘x’,
· print a message
<time> <userid> Process <processid> exited
· delete the process from the process table
· increment time
· exit loop
§ if current command is ‘s’,
· change the state of the process to Waiting,
· move the process to the Waiting queue,
· print the message below
<time> <userid> Process <processid> will sleep until <new time>
· advance the current relative address (PC) for the process by one
· increment time
· exit the loop
§ if current command is ‘r’,
· print the message below
<time> <userid> Process <processid> runs, PC <PC>, qr = <int>
Note: The value given after qr is the time remaining in the quantum. If the quantum size is q then qr will count down q – 1, q – 2, …, 0 for the series of instructions executed by a process if it completes its quantum.
· advance the current relative address (PC) for the process by one
· increment time
end repeat
if the process has not exited and is still in the Running state at the end of the quantum, change its state to Ready and add it at the end of the Ready queue.
else if input remains in the input file or processes remain in the Waiting queue,
print an Idle message:
<time> 0 Idle
increment time
else DONE
end repeat forever
\
If no processes exist, the simulator should stop. The overall effect is to execute instructions from the input file whenever they are specified to occur, except for small delays as .xex minifiles finish their quanta.
Simulated memory:
The simulated memory for the computer should be an array 1000 entries long. Each element in the array should be able to hold a single character (‘r’, ‘s’, or ‘x’) plus an integer. In your implementation, you can use a struct or a class in C++ for a memory element. Your program should have one integer variable called something like NextAvailableMemoryLocation, which is initially 0 and advances as memory is used up. To simplify programming of SOS, memory is never reused. If you reach the end of memory and have not finished loading the .xex file, give an error message (“Insufficient memory available to load executable”) and remove the partially loaded minifile. When loading an .xex minifile, store the starting memory location and the number of memory locations used for the .xex minifile (same as the number of lines) in the process table.
Ready queue:
You will need a data structure for this algorithm to represent the Ready queue; you may use an array, a queue, a linked list, a vector, etc. for the Ready queue. Only the process id (or a pointer to an entry in the process table) needs to be stored in an entry in the Ready queue, since all other information about the process is available in the process table.
The PTshowprocesses instruction displays the process table, in order of process id. For each entry in the process table, it shows the process id, the .xex minifile name, the user id, the start time, the elapsed time, the state of the process at this time, the starting address, the limit, and the current relative address (PC).
The PTshowscheduler instruction displays the quantum size, the Ready queue, and the Waiting queue. The Ready queue is shown as a series of process ids, such as:
-->[3]-->[2]-->[5]-->[]
which indicates that process 3 is first in the Ready queue and process 5 is last. The entries in the Ready queue should be shown in the same order in which they would be removed. The Waiting queue is shown as a series of time - process id combinations, such as:
-->[100 | 3]-->[110 | 2]-->[112 | 5]-->[]
which indicates that process 3 will be ready at time 100, process 2 will be ready at time 110, etc. The entries in the Waiting queue should be shown in the same order in which they would be removed.
Unlike the normal Round Robin algorithm discussed in class, your scheduler should insert a process that finishes its quantum back in the Ready queue before any newly ready process, such as one that is beginning execution or leaving the Waiting state. The method for the scheduler described above performs the insertions in this way.
The PTsetquantum system call changes the quantum size to the specified value. If the value is not an integer between 1 and 9 inclusive, an error message is printed (Invalid parameter). Initially, the quantum should be set to 1. If a process does not run to the end of its quantum, it is either finished (in which case it should be deleted) or it should be placed in the Waiting queue (see below).
Another data structure required for Phase Three is the Waiting queue, which in this project is the list of processes in the Waiting state. These processes are also called suspended processes because they have nothing to do until they become ready again. Each entry in the Waiting queue gives a time when an event will occur and a process id. When a process is removed from the Waiting queue, the one with the lowest execution time should be selected (ties should be broken by selecting the one that has been in the Waiting queue longest). In your implementation, it is recommended that the entries in the event list should be kept sorted in order of the time of occurrence of the events.
A process can be suspended before completing its quantum. If two processes happen to be suspended until the same time, then at that time, the one that was suspended first should be made ready first.
Design Suggestions: It is recommended that you begin by implementing the scheduling of Ready processes (all ‘r’s and final ‘x’) and postpone the implementation of the Waiting processes until the scheduler is working.
0 0 FScreate disk01 SFFS 1 0 100000 50
1 0 FSmount disk01 fs1
2 0 FSchange fs1
4 1 FSimport fast.xex
5 1 FSpermission fast.xex e+x
6 2 FSimport spinning.xex
7 2 FSpermission spinning.xex e+x
8 0 FSdir
9 1 PTexecute spinning.xex
13 1 PTshowprocesses
14 2 PTshowscheduler
19 2 PTexecute fast.xex
20 3 PTshowprocesses
20 2 PTshowscheduler
29 3 PTshowprocesses
29 2 PTshowscheduler
SOS started on Tue Sep 07 14:04:40 2010 0 0 FScreate disk31 SFFS 1 0 100000 50 1 0 FSmount disk31 fs1 2 0 FSchange fs1 3 0 Idle 4 1 FSimport fast.xex 5 1 FSpermission fast.xex e+x 6 2 FSimport spinning.xex 7 2 FSpermission spinning.xex e+x 8 0 FSdir++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Filename Size Owner Properties Time ++ passwords.dat 6 0 |drwx| | | 0 ++ fast.xex 38 1 |drwx| | x| 4 ++ spinning.xex 52 2 |drwx| | x| 6 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 9 1 PTexecute spinning.xex 10 1 Process 0 runs, PC 1 qr = 0 11 1 Process 0 runs, PC 2 qr = 0 12 1 Process 0 runs, PC 3 qr = 0 13 1 PTshowprocesses++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ProcId Minifile Name UserId S_Time E_Time State Address Limit PC ++ 0 spinning.xex 1 9 4 READY 0 26 3 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 14 2 PTshowscheduler+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Quantum: 1+ Ready Queue: -->[0]-->[]+ Waiting Queue: -->[]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 15 1 Process 0 runs, PC 4 qr = 0 16 1 Process 0 runs, PC 5 qr = 0 17 1 Process 0 runs, PC 6 qr = 0 18 1 Process 0 runs, PC 7 qr = 0 19 2 PTexecute fast.xex 20 3 PTshowprocesses++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ProcId Minifile Name UserId S_Time E_Time State Address Limit PC ++ 0 spinning.xex 1 9 8 READY 0 26 7 ++ 1 fast.xex 2 19 1 READY 26 17 0 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 21 2 PTshowscheduler+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Quantum: 1+ Ready Queue: -->[0]-->[1]-->[]+ Waiting Queue: -->[]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 22 1 Process 0 runs, PC 8 qr = 0 23 2 Process 1 runs, PC 1 qr = 0 24 1 Process 0 runs, PC 9 qr = 0 25 2 Process 1 runs, PC 2 qr = 0 26 1 Process 0 runs, PC 10 qr = 0 27 2 Process 1 runs, PC 3 qr = 0 28 1 Process 0 runs, PC 11 qr = 0 29 3 PTshowprocesses++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ProcId Minifile Name UserId S_Time E_Time State Address Limit PC ++ 0 spinning.xex 1 9 12 READY 0 26 11 ++ 1 fast.xex 2 19 4 READY 26 17 3 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 30 2 PTshowscheduler+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Quantum: 1+ Ready Queue: -->[1]-->[0]-->[]+ Waiting Queue: -->[]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 31 2 Process 1 runs, PC 4 qr = 0 32 1 Process 0 runs, PC 12 qr = 0 33 2 Process 1 runs, PC 5 qr = 0 34 1 Process 0 runs, PC 13 qr = 0 35 2 Process 1 runs, PC 6 qr = 0 36 1 Process 0 runs, PC 14 qr = 0 37 2 Process 1 will sleep until 44 38 1 Process 0 runs, PC 15 qr = 0 39 1 Process 0 runs, PC 16 qr = 0 40 1 Process 0 runs, PC 17 qr = 0 41 1 Process 0 runs, PC 18 qr = 0 42 1 Process 0 runs, PC 19 qr = 0 43 1 Process 0 runs, PC 20 qr = 0 44 1 Process 0 runs, PC 21 qr = 0 45 2 Process 1 runs, PC 8 qr = 0 46 1 Process 0 runs, PC 22 qr = 0 47 2 Process 1 runs, PC 9 qr = 0 48 1 Process 0 runs, PC 23 qr = 0 49 2 Process 1 runs, PC 10 qr = 0 50 1 Process 0 runs, PC 24 qr = 0 51 2 Process 1 will sleep until 56 52 1 Process 0 runs, PC 25 qr = 0 53 1 Process 0 exited 54 0 Idle 55 0 Idle 56 2 Process 1 runs, PC 12 qr = 0 57 2 Process 1 runs, PC 13 qr = 0 58 2 Process 1 runs, PC 14 qr = 0 59 2 Process 1 runs, PC 15 qr = 0 60 2 Process 1 runs, PC 16 qr = 0 61 2 Process 1 exited SOS stopped on Tue Sep 07 14:04:40 2010
What to Submit for Phase Three:
· Cover page with your name, student number, course number, phase number, lab section, and nothing else.
· Test cases: Explain in a general way how invalid input is handled. Give at least two examples of valid uses and two examples of invalid uses for each command. Assign each of these examples a “test case number”.
· Design of your software: Identify the OS platform and compiler used to create your software. Give an updated pictorial overview of the organization of your software into modules/functions/objects, explain the main or novel aspects of design (typed, with machine-produced pictures), with emphasis on parts that are new for Phase Three.
· Extra Feature (15% of grade for the phase): Describe an extra feature (or several extra features) that you added to your file system manager above and beyond the stated requirements. Your extra feature should extend the design of Phase Three in a reasonable way (reading the textbook may give you ideas). Your extra feature should be made optional, such that it does not invalidate SOS’s behavior on the testing data. Explain why the feature is useful and how you tested it.
· Testing results: Test your SOS thoroughly on valid and invalid input. Design at least three of your own input files, called in2-11.txt, in2-12.txt, in2-13.txt, etc. Make a separate run with each input file. The test files should cover all your test cases and include at least 60 lines in total. For Phase Three emphasize the testing of the scheduler in unusual situations. A single test case may involve several lines of input. Draw up a table with the following columns: (1) Test case number, (2) Expected result, (3) Log file number, (4) Lines, and (5) Worked? (YES or NO). The Lines column identifies the relevant lines in the log file where the test case is shown.
· Source Code for SOS: Provide neatly formatted code for your version of SOS, in the programming language of your choice (check with the instructor if this is not C, C++, or Java). You are required to include:
o boxed comments for every file of code and for every class and for every function/procedure/method more than 10 lines long,
o functions/procedures/methods no more than one page (66 lines) long,
o adequate white space,
o symbolic constants (e.g., MAX_PROCESSES) rather than numbers,
o at most 80 characters in each line,
o indenting of contents of conditional (if) and repetition (for, while) statements; if you are following published style guidelines, cite a reference for the style guidelines.
Electronic submission: you will submit all code and test files electronically by deadline date and time. Your program will be evaluated on a set of ten input files, five of which will be revealed to you before the deadline. Your own testing is needed to supplement the revealed test files.