$20
Homework II
This assignment introduces the definition of classes, and their use in the implementation and use of a simple linked list. These will then be used to implement some simple scheduling policies.
PROBLEM DESCRIPTION
This assignment will simulate a job scheduler by defining a collection or processes and then choosing which will execute next. There are several possible policies that may be applied to choose what gets to use the CPU, so that problem will be factored out into a separate part of the program.
Here is a very rough sketch of the simulation:
1) There are many different scheduling policies, but this assignment will simply run the processes in the order in which they appear which is very easy to do with a linked list.
2) No Operating System can accurately predict just how much time any process will need to use the CPU. It might have very little work to do, and finishes quickly. Or it may get stuck in an infinite loop and try to run indefinitely. To guard against the latter, one can just put a limit on one process, after which the CPU is taken away and passed to another.
3) If a process is done, it is removed from the system (and we will put a 'Q' at the end of its history). If it still wants to run some more, we will just put it back into the set of processes that wish to use the CPU.
SPECIFICATION DETAILS:
Most of the simulation details above will be handled by these objects and methods:
Allows the specified process to run for a little while. One parameter gives an upper limit on the time allowed. One parameter represents the simulation clock, which increases to show the passage
of time (depending on how much CPU time this processor uses). And a return parameter indicates what the process wishes to do after it runs run
some more ('X') or finish ('Q').
Represents the overall simulation, as hinted at by the rough pseudocode above. Its parameter list
includes a description of all the processes in the system and when they arrived. One parameter specifies the upper time limit for each call to , to see the effect that has on overall behavior.
There are also several listrelated functions defined to assist with this and later assignments. The contents of each list element would be good to know:
Each list includes a process ID (just a small integer in this project), a time index, and a process state
(such as 'X' or '').
This list will serve three very different purposes in this project:
will record the complete history of each process during the simulation, i.e. the data to
be displayed by the code from Homework 1. A sensible simulation should record this information
in chronological order.
will record the collection of processes currently wishing to use the CPU. The
only essential information here is the process ID, which is nothing more than a subscript to an
array of Processes.
will record events that will occur in the simulation's future. For example, not all
processes are ready to run at time 0; in later assignments, they will also not be ready to run until
certain other operations complete. This list must be kept in chronological order.
HEADER FILES
Header files (.h) will now begin to declare classes and their methods, and source files (.cpp) will
implement many of those methods.
Taking a closer look at the class declarations:
This file declares a singlelinked
list along with an iterator. The ProcList class implements some very
simple accessor methods to assist with the simulation. Since this List will often only be used as a queue,
the only peeks at the list are at the time values for the timeordered
list of future events. Looking at any
other within the list would require use of a ProcIterator.
This describes a single process that wishes to use the computer system. Every process is assigned an
identifier for easy reference for
this project, this will be nothing more than its assigned subscript in an
array.
The process behavior is represented as a series of alternating usages of the CPU, which may be separated
by other devices (in the next assignment). Later, the project will compare various scheduling policies on
the same set of processes, so one set of variables will be assigned at process creation time and left
unchanged, and some others will record how far it has executed. A log is included to record its complete
history. Some simple functions are defined to maintain this log history, and then to provide that history to
the function.
This declares the scheduler object, along with some very simple functions regarding the subset of
processes that currently wish to use the CPU. These three functions have been isolated, because their
behavior will differ for other scheduling policies later in the course. It is strongly recommended to make
use of these methods, so that the implementation will work equally well with all policies
later.
Usually only the accessor methods for a class appear in a header file, but often I will put any very short
function in there as well. A function that is implemented within a class definition in C++ becomes an
function, meaning that when the compiler encounters a function call, it simply expands the function
code in place. This does yield code duplication in the executable file (so should not be done for large
functions) but
it avoids the need to call and return, which would dominate the execution time of a
simple accessor method.
Conversely, there are several occasions this semester where a constructor method does NOT appear in
the header file, because it is doing considerable work, such as filling arrays.
COMPONENT FILES
Here is a summary of all the files for this assignment:
Declares the description of a process
DO NOT CHANGE
Initializes a process and simulates its CPU usage
Complete method
Declares the process scheduler object
DO NOT CHANGE
Implements the scheduler simulation
Complete method
Declares the list elements, the list, and an iterator
DO NOT CHANGE
Implements the list and its iterator
Complete and
Declaration of display function
DO NOT CHANGE, but notice the change in interface
Implementation of display function
Some editing is required, since the parameter list now includes an array of processes
containing linked lists instead of two parallel arrays. Complete and submit.
Some code to test the scheduling simulation
Feel free to edit as desired, but do not submit.
A very different version of this file will be used for grading.
The files to be submitted for this assignment are and
. Include them all within a single dropbox submission.
EXTRA CREDIT OPTION
An important part of the simulation above is to record information for each process about its history. A
simple straightforward
implementation may actually insert a few list elements that actually do not
contain useful information.
If a process is not given enough allowance to use all the CPU time it desires, then it may have wait and
resume later. It is very simple to just make that assumption and insert a list element with the ''
indicating
that it will wait.
But on some occasions, no waiting actually occurs (such as if there is no other process in the system).
The resulting job history would then have two consecutive elements with the same time index, indicating
that the first has no actual duration.
Furthermore, removing these zerotime
elements may lead to two consecutive elements describing the
same state implying
a state change when there is none (the second would add no information).
The extra credit assignment then is to remove these unnecessary list elements. A method has been
declared () for this purpose. Complete it to remove and deallocated unwanted list
nodes.
Be sure to place a notice in the ANGEL Message Box to the grader that you have attempted this feature.
