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