Description
Background on operating system scheduling
An operating system (OS) is a program that manages all running programs (aka processes) on a
computer. The OS decides which process gets to execute, and for how long. This is called process
scheduling.
A batch operating system is one which runs one whole program, then runs another whole program, etc.
Batch operation is an older, simpler approach to scheduling in an operating system. A non-batch
operating system is one like Windows or Linux, where multiple processes all seem to run at the same
time (really they just use small amounts of time and switch back and forth).
An operating system is real-time if it makes guarantees about when processes will be executed (e.g.
when it will start, or when it will finish).
Operating systems use different methods for scheduling which processes are run, and when. One simple
method for a batch operating system is first-come-first serve, in which the processes are ordered by their
start times, and run in order, where each process is run to completion. Another popular method is
shortest-first, where processes are ordered by the amount of time they will require (from least to greatest),
and run in that order.
For a real-time operating system, it is often important when a process will finish. For example, if we know
that a prediction program for tomorrow’s weather will take 12 hours to run, then it will be useless to start it
any later than noon today because the answer will be irrelevant. Therefore, processes could be ordered
by their deadlines, and the first process run is the one which must finish earliest, thereby guaranteeing it
will finish. For example, if the operating system has 3 processes that must finish at 25 ticks, 80 ticks, and
15 ticks (respectively), the first process run will be the one that must finish at 15 ticks. Note that 25, 80,
and 15 are not the amounts of time the processes will run, they are the actual times when the
corresponding processes must finish.
Project description
You will write an program that uses a priority queue (heap) to simulate a real-time batch operating
system, as described in the previous section. Your simulator will start new processes running when they
are ready, and update the clock when they have finished. The next process to run will always be one that
has the earliest deadline.
Sometimes a process may have a finishing time that is impossible to achieve. For example, if the clock is
currently at 30 ticks, the next process to run must finish by 50 ticks, and it will require 40 ticks to run, then
the process cannot finish on time. In such a case, the process will simply be skipped.
You will use two abstract data types for this project: ArrayHeap and Process. Each Process has several
attributes:
• id — a unique numeric identifier assigned by the operating system, which never changes. The
first process has id 0, the next has id 1, etc.
• deadline — the time by which the process must finish (on or before that time)
• requiredTime — the amount of time required to run the process
• information — a string that will be printed when the process is run (simulates actually doing
something in the process)
The ArrayHeap is used to store Process objects, ordered by deadline. In the case where two Process
objects have the same deadline, they should be ordered by amount of time required to run (ordered least
to greatest). If they are still the same, then they should be ordered by their process id (ordered least to
greatest).
Your simulator should read the description of the simulation from standard input (cin). The first line of
input will be the number of processes that will be run, called n. The remaining n lines will each describe
one process. Each line describing a process will have three integers and a text description. The first
integer will be the submission time of the process (when the user submitted the program to be run) in
absolute time. The second integer will be the deadline of the program (in absolute time). The third integer
will be the amount of time (number of ticks) required to execute the process. The remainder of the line will
be a textual description of the process (its “information” that should be printed when it is run).
At the beginning of the simulation, the system clock starts at 0 ticks. The simulator always places in the
heap all processes that have already started (i.e. their start time is less than or equal to the system clock).
However, processes that haven’t started yet shouldn’t be on the heap! The simulator then runs processes
that can run, in the order discussed above. If a process is next to be run but cannot finish in time, it is
skipped. This continues until there are no processes left to run. The system clock increments by the
required run time of a process when that process is run, or by 1 tick when any process is skipped.
Sample simulation
Here is a demonstration of the simulator. The sample input is:
5
10 20 5 hello there
11 20 5 how are you
12 20 5 i am fine
13 20 5 i’m glad to hear that
14 30 5 goodbye
Note that the input has a single space between the fields required time and information, and this space
should be skipped. The single space is not a part of the information field. Only one space should be
skipped, any further spaces should be considered part of the information field.
Here is a description of the simulator as it processes this input:
• The system clock starts at 0 ticks. The simulator reads from the first line of input that there will be
5 processes to run.
• There are no processes that start at 0 ticks, so the system clock advances to the starting time of
the next process, which is 10 ticks.
• The system clock is now 10 ticks, and the first process can be read from the file, given process id
0, and inserted into the heap. No other processes can start when the system clock is 10, so they
are not yet read in.
• Process id 0 is on the top of the heap, and it should finish by 15 ticks (clock is currently at 10
ticks, plus 5 required ticks). Its deadline is 20 ticks, so it can run. It is run, and removed from the
heap. Each time a process is run or skipped, it is removed from the heap.
• After running process id 0, the system clock is 15 ticks. Four more processes have started (they
all have starting times of less than or equal to 15 ticks), so they are all read in, given process ids
1-4, and inserted into the heap.
• The next process to run is id 1, with deadline of 20 ticks. Currently at 15, requiring 5 ticks, the
process can finish at 20 ticks, so it is allowed to run, and the system clock is now at 20 ticks.
• The next process to run is id 2, with deadline of 20 ticks. It requires 5 ticks and cannot finish in
time, so it is skipped. The system clock is incremented by one tick. The same thing happens for
process id 3.
• The system clock is now at 22 ticks. Process id 4 will run since it can complete before 30 ticks,
and the final system clock is 27 ticks.
The sample output is:
running process id 0 at 10
hello there
running process id 1 at 15
how are you
skipping process id 2 at 20
skipping process id 3 at 21
running process id 4 at 22
goodbye
final clock is 27
number of processes run is 3
number of processes skipped is 2
If a process is run, its output has two lines:
• the simulator tells that it is being run, giving the process’ id and the system clock when the
process starts
• the Process’s run() method prints the information that the Process object contains
If a process is skipped, it has just one line of output: the simulator tells that it is being skipped, giving the
process’ id and the system clock when the process is skipped
After simulation of all processes completes, the simulator tells the final system clock, the number of run
processes, and the number of skipped processes.
Some additional notes
Here are some tips that should help you along the way. Read these after you have read the rest of the
document.
• Always run (or skip) the process that is at the top of the process heap. Don’t make special cases
for any processes.
• Very important: whenever the system clock changes, new processes may have started! These
processes should be on the heap as soon as possible, because they may have earlier deadlines
than processes on the heap.
• The system clock should only jump to the next starting time only if there are no processes on the
heap. Otherwise, if there are items on the heap, the system clock advances by the required time
(if the process runs), or 1 (if the process is skipped). Additionally, the system clock should never
move backwards.
Sample input and output
The inputs will always be ordered by start time, so you can read them in one at a time, without sorting by
start time. They should be read in the given order. Some processes may have the same starting time.
Here are several sample inputs and outputs.
• input 1
• input 2
• input 3
Sample executables
When you design test cases, you can judge your output against the output from my correct solution.
• DOS executable
• Linux executable
• OSX executable
As in previous projects, if you give a command-line argument to these executables, they will print extra
information about how they are running.
Provided code
You must use the .h files provided here. As before, you should put your code for the ArrayHeap in the
student file, and do not put your code in the prof file. However, you might put code in the prof file for
debugging purposes (but it will not be submitted).
• arrayheap-prof-proj5.h
• arrayheap-student-proj5.h
• process-proj5.h
Remember that when using templates, all of the code you write goes in the .h file. So you will turn in 3
files for this project: arrayheap-student-proj5.h, process-proj5.cpp, and your driver (a .cpp file). Your driver
should #include arrayheap-student-proj5.h, and it should #include the corresponding prof file (which it
already does).
Structuring the project
Since this is a large project, it helps to have a plan of attack. The following milestones should be turned in
via the upload site.
Step Finish by Milestone
1 Monday, October
30 at noon
WRITE and thoroughly TEST test the Process class, and the following
methods for the ArrayHeap: default constructor, copy constructor, destructor,
getMin, getNumItems, bubbleUp, and bubbleDown.
2 Friday, November
3 at noon
WRITE and thoroughly TEST the insert, removeMin, doubleCapacity, and
operator= methods for the ArrayHeap.
3 Monday,
November 6 at
noon
WRITE and thoroughly TEST the main driver. Write and solve by hand
several test case inputs and outputs. Check your driver against the inputs
and outputs you have developed. Finish early so that you have time to solve
any remaining bugs.
Writing a test driver for a data structure means writing a small, self-contained program that tests the
different methods of the data structure and verifies that they are correct. For each milestone you should
develop and turn in a driver that illustrates testing your code.
Final notes
Remember when writing this program to adhere to the coding style guidelines. No credit will be given for
a solution which does not pass all the hidden tests I create, or does not pass in the allowed time. For
more detailed instructions, read the project submission guidelines.
Copyright © 2016 Greg Hamerly.
Computer Science Department
Baylor University
