@www.csse.monash.edu.au |
| Assessment | Contacts | Laboratories | Lectures | Resources | Timetables | Tutorials | Unit Outline |
| Last modified: 20100915:114002/add Marc Cheong's HTML Gantt chart generator | FIT2022 AJH-2010-38 |
Objectives and Outcomes | The Literate Program | The Story So Far | Processes | Events | Outputs of the Simulations | Shortest Remaining Time First (Preemptive) | Round Robin | Main | Exercises | Indices
At the end of this lab session, you should:
Your demonstrator may ask you questions about these points, and will only give you a "satisfactory" for the lab if you can respond correctly.
Don't forget to enter your experiences into your lab journal, and save it back to the svn repository!
There are no new ideas introduced to the literate programming model in Lab 4.
The program below has already been tangled. There are eight files:
This simulation is about modelling processes, the events that occur to them, and the process (or job) scheduling algorithm. We model the execution of several processes, and try out the various algorithms discussed in lectures to see the effect on throughput, or the number of processes completed within a given time. We expect that some algorithms will perform better than others, but we also expect to see a variation in the comparison depending upon the actual behaviour of the processes, and the flow of events as they execute.
The heart of the simulation is this focus upon the key events that happen during a process's life cycle. We are interested in the effect of these events, and we seek to discover something about the real operating system environment by abstracting the events from that real world system. So we are not building an operating system itself, but rather a model in which the events, the time at which they happen and their effect upon the system, exactly parallel the real system, but all other unnecessary detail is removed.
Remember in Lab 2 how we modeled processes by means of a set of threads? Since we are not actually running any processes per se in this lab exercise, we no longer need to use threads, but instead restrict ourselves to just the salient abstractions of a process, such as the fact that it has a unique process number, that it has a predicted run time, that it spends some time doing IO (and hence in the wait queue), and so on. All of these attributes are abstracted into a new class Process, defined in a separate module.
The Process definitions appear in a separate module.
We use the event model developed in Lab2 to drive the simulation. Events are things like process completion, IO start and finish, resource requests, and so on. Anything which moves a process around the process state diagram, in fact. Each simulation is driven by a sequence of events, an encoding of which is read in from standard input, and used to define the process state transitions. It is the timing of these transitions that interests us in this lab.
Shown below for each event is the format of the event record, read in as part of the initial file. Some events (create and admit) are identified in the initial event list. Other events, such as dispatch, are generated by the simulation, and added to the event list as the simulation proceeds.
The Events definitions appear in a separate module.
[event time] create [process no] [run time] [I/O time]
[event time] admit [process no] 0 0 0
Each simulation is designed to generate similar outputs, so that you can compare them easily. There are three main outputs:
Here is the process state transition diagram, augmented to include the pre-emptive edge of interruption. This is now the full state diagram, as given in the text (and should be committed to memory).
Unlike the First-Come First-Served algorithm, processes are not scheduled in order of arrival, but rather which one has the shortest time to run. Two strategies are possible:
SRTF and RR are both pre-emptive schedulers, which means that a process may be removed from the running state before we expect it to be. This means that the approach we used in lab 4 of working out how long a process will run for before dispatching it, and scheduling an event for either io waiting or termination, will no longer work, since these events will not happen at the appointed time if the process is pre-empted.
Instead, we have to check the event clock at each cycle, to see whether pre-emption is taking place, and if so, update the process data accordingly. The main thrust of the changes is to refine the process data to include a variable to count how much time to the next io wait, and to the event module to explicitly cycle the clock, and see if an event is due at the current time. The process variable timetoio is initialized to the value of iotime, and counts down the time to the next io wait event. It is preserved over pre-emption, and thus captures the semantics that we seek.
In the new model, rather than computing the process time values at the event times, we recompute them on each clock tick. If the time to run time, or time to next io wait timeio reaches zero, we schedule the appropriate event then.
Again, we use the initial set of events developed in Lab2 to start the simulation off.
We write the SRTF algorithm as a Python module. This means that it is constructed as a separate file, which is imported into our main program. The file just contains all the definitions we are going to use.
<SRTF definitions 7.2> =The running variable defines which process currently is running. A value of -1 indicates that no process is currently running. The ReadyQ is implemented as a Python list, initialized to empty. As suggested above, we use a simple model of IO activity, and assume that all IO takes a fixed amount of time to complete, given by the variable IOWaitTime. This variable may be altered by specification on the command line (see below).
As each clock tick passes, we check the currently running process to see if it has any activity to note. Two counters count down to indicate this: the time variable, which indicates the remaining time for the process, and the timetoio variable, which indicates when the next io event for the process will happen. If either of these reach zero, then the process will exit or iowait. Note that we test for exit (termination) first, since if both counters hit zero simultaneously, the process is regarded as terminated.
This defines the method of adding a process to the ready queue. Recall that we decided in the Introduction above to maintain the ready queue in shortest time first order, rather than just using the default append-to-end employed in FCFS. The method takes a process number as argument, and inserts that process (number) into the ready queue ordered in shortest time first order.
We scan the ready queue from first to last, looking for a process time that is larger than the incoming one. If we find one, the new entry is inserted just before that one. Two endcases arise: the list is initially empty (the for loop body is not executed), or the new value is larger than any in the list (the for loop falls through the end). In both cases, the else branch of the for loop is taken, and we just append the new value to the (possibly empty) list. Neat huh?
What distinguishes SRTF from other algorithms is the way in which it responds to the events that occur at the process management level. The structure of the outer part of the algorithm is similar to FCFS, however.
<define the SRTF HandleEvent method 7.5> =This is the main event handler for the algorithm. Each of the event types is handled within this method. Some events will cause other events to be added to the event list.
A create event simply creates the corresponding process. We call statechange to indicate that the process now is created, which fact is recorded in the history data. Note that if no io is to be simulated, indicated by a zero value for iotime, then set the time to the next io event to one unit greater than the time to run. This means the io event will never happen, since the process will terminate first.
When a process is admitted to the ready queue, we set its state to ready, and call the AddReady routine to insert it in the right position to maintain shortest remaining time first.
Since the arriving job may be shorter than the currently executing job, pre-emption may occur, and we have to check for that.
A 'dispatch' event causes a process to start running. Its state is therefore set to 'running', and we record the new running process. Since this is a preemptive environment, we rely upon the tick algorithm to check for completion/io/interruption events, and need not test for them here.
A 'interrupt' event causes a process to stop running. Its state is therefore set to 'ready'. Set the running flag to indicate no process is running. We must therefore call the scheduler to reschedule the shortest remaining time process next.
A 'iowait' event causes a process to stop running, and its state is set to 'waiting'. Work out how long to wait for, and schedule an iocomplete event at that time.
A 'iocomplete' event causes a process to stop waiting for io, and its state to become 'ready' again. Update its waiting time, and reset the time to the next io event from the iotime value. If there is no io, set the time to io to be greater than the time to run, so that no io wait will take place. The process is returned to the ready queue.
Because the algorithm is pre-emptive, we must check if the current process should be pre-empted. This is handled in a separate piece of code.
An 'exit' event causes a process to stop all demands for CPU time. Its state is set to 'terminated'.
An event (admit or iocomplete) has occurred that could cause preemption. Because there may be more than one event that could cause pre-emption, we first check the time of last pre-emption. If it is the same as now, we don't need to recompute this calculation (nor should we, since we might create a redundant interrupt event).
Check the time to run of the current process and see whether it is longer than the new process. Note that if the current process has a zero time or timetoio, then do nothing, since the current process will quit the running state this clock tick anyway.
After handling an event, we check the running flag. If it is set to -1, it means that there is no process running, and we pop the ready queue to determine which process should be dispatched.
<SRTF dispatch a process 7.15> =Dispatch a process by removing it from the ready queue, and scheduling a dispatch event for it for the current time.
This is a convenient logging function to record on standard output the events that have been processed.
We continue on from the Shortest Time First Scheduler, using the code developed there to develop the Round Robin scheduler.
The Round Robin scheduler maintains the ready queue as for the First-Come First-Served algorithm, so we can revert to the simpler AddReady algorithm.
In the new model, rather than updating the process time values at each event time, we update them on each clock tick. If the time to run time, or time to next io wait timeio reaches zero, we schedule the appropriate event then.
Again, we use the initial set of events developed in Lab2 to start the simulation off.
We write the RR algorithm as a Python module. This means that it is constructed as a separate file, which is imported into our main program. The file just contains all the definitions we are going to use.
<RR definitions 8.2> =The running variable defines which process currently is running. A value of -1 indicates that no process is currently running. The ReadyQ is implemented as a Python list, initialized to empty.
As suggested above, we use a simple model of IO activity, and assume that all IO takes a fixed amount of time to complete, given by the variable IOWaitTime. This may be modified by command line parameters.
The Round Robin algorithm requires that we allocate a maximum time slice to each process when it is dispatched. This is defined by the (fixed) value of TimeSlice, which also may be modified by command line parameters.
As each clock tick passes, we check the currently running process to see if it has any activity to note. Three counters count down to indicate this: the time variable, which indicates the remaining time for the process, the timetoio variable, which indicates when the next io event for the process will happen, and the slice variable, added to the Process data to indicate how much time is left in the current time slice. If any of these reach zero, then the process will exit, iowait, or interrupt, as appropriate. Note the order in which we test these, since if exit (termination) occurs first, the others do not matter. Similarly, if the process iowaits, it does not need to be interrupted.
This defines the method of adding a process to the ready queue. For Round Robin, we revert to first in first out order, so simply appending to the queue suffices.
What distinguishes RR from other algorithms is the way in which it responds to the events that occur at the process management level. The structure of the outer part of the algorithm is similar to FCFS and SRTF, as before.
<define the RR HandleEvent method 8.5> =This is the main event handler for the algorithm. Each of the event types is handled within this method. Some events will cause other events to be added to the event list.
A create event simply creates the corresponding process, and we set its state to 'created'. Note that if no io is to be simulated, indicated by a zero value for iotime, then set the time to the next io event to one unit greater than the time to run. This means the io event will never happen, since the process will terminate first.
When a process is admitted to the ready queue, we set its state to ready, and call the AddReady routine to insert it in the right position to maintain shortest remaining time first.
Unlike SRTF, the arrival of a process does not cause pre-emption, since we wait until the end of the current slice for the new process to get a turn in the running slot.
A 'dispatch' event causes a process to start running. Its state is therefore set to 'running'. We must allocate a fixed unit of time to run, so the slice counter is reset to the slice value.
A 'interrupt' event causes a process to stop running. Its state is therefore set to 'ready'. We must therefore call the scheduler to reschedule the shortest remaining time process next.
A 'iowait' event causes a process to stop running, and enter the 'waiting' state. Work out how long to wait for, and schedule an iocomplete event at that time.
A 'iocomplete' event causes a process to stop waiting for io, and its state to become 'ready' again. Update its waiting time, and reset the time to the next io event from the iotime value. If there is no io, set the time to io to be greater than the time to run, so that no io wait will take place. The process is returned to the ready queue.
An 'exit' event causes a process to stop all demands for CPU time. Its state is set to 'terminated'.
The only pre-emption that occurs in Round Robin is at the end of a time slice, which is handled by the tick method, and a separate interrupt event. Hence there is no need to check for pre-emption here.
After handling an event, we check the running flag. If it is set to -1, it means that there is no process running, and we pop the ready queue to determine which process should be dispatched.
<RR dispatch a process 8.14> =Dispatch a process by removing it from the ready queue, and scheduling a dispatch event for it for the current time.
This is a convenient logging function to record on standard output the events that have been processed.
The main process of this simulation reads in the simulation file, builds the event queue, and then starts the simulation running.
"srtfsim.py" 9.1 =The main program for Shortest Remaining Time First. The call on the Gantt chart generator should display charts like this:
The main program for Round Robin.
The common set of import statements.
<define subroutines 9.4> =This code reads lines from the initial file, which defines the initial set of events, and builds the initial event queue.
<define subroutines 9.5> =This code performs the simulation itself. Its main loop counts the clock along, updates process data, and then calls the scheduling algorithm to see if any action needs to be taken. The simulation ends when the clock reaches the end of the epoch. "Epoch" means "a particular period of time marked by distinguishing events" (Macquarie), and here the distinguishing events are the start and end of simulation.
<compute simulation results 9.6> =Add up all the wait times for each process to find the average waiting time.
<run the SRTF simulation 9.7> =The main program consists of loading the initial events and running the simulation.
"initial" 9.10 =You asked for the exercises to be separate. You got it!
Two of the processes in the above simulations have no waiting time under SRTF(*). Is this simply fortuitous ("good luck"), or is it because the algorithm is intrinsically better ("good management")? Devise an experiment to test your theory.
Hint: "Testing will never show the absence of bugs, only their presence" is a famous statement by the eminent computer scientist Edsgar Dijkstra. You should bear this maxim in mind as you test your theory.
* Careful here! Distinguish between "waiting time" and "time in the (io) waiting state". Remember that process waiting time is defined as time in the ready state, NOT time in the waiting state.
Warning:This exercise should be completed
only after all other basic sections have been completed, and
are working satisfactorily.
Warning:This exercise should be completed
only after all other basic sections have been completed, and
are working satisfactorily.
| File Name | Defined in |
|---|---|
| RR.py | 8.1 |
| SRTF.py | 7.1 |
| initial | 9.10 |
| rrsim.py | 9.2 |
| srtfsim.py | 9.1 |
| Chunk Name | Defined in | Used in |
|---|---|---|
| RR definitions | 8.2, 8.15 | 8.1 |
| RR definitions | 8.2, 8.15 | 8.1 |
| RR dispatch a process | 8.14 | 8.13 |
| RR handle admit event | 8.7 | 8.5 |
| RR handle create event | 8.6 | 8.5 |
| RR handle dispatch event | 8.8 | 8.5 |
| RR handle exit event | 8.12 | 8.5 |
| RR handle interrupt event | 8.9 | 8.5 |
| RR handle iocomplete event | 8.11 | 8.5 |
| RR handle iowait event | 8.10 | 8.5 |
| RR schedule process | 8.13 | 8.5 |
| SRTF check if current process should be preempted | 7.13 | 7.7, 7.11 |
| SRTF definitions | 7.2, 7.16 | 7.1 |
| SRTF definitions | 7.2, 7.16 | 7.1 |
| SRTF dispatch a process | 7.15 | 7.14 |
| SRTF handle admit event | 7.7 | 7.5 |
| SRTF handle create event | 7.6 | 7.5 |
| SRTF handle dispatch event | 7.8 | 7.5 |
| SRTF handle exit event | 7.12 | 7.5 |
| SRTF handle interrupt event | 7.9 | 7.5 |
| SRTF handle iocomplete event | 7.11 | 7.5 |
| SRTF handle iowait event | 7.10 | 7.5 |
| SRTF schedule process | 7.14 | 7.5 |
| collect CLI values | 9.9 | 9.1, 9.2 |
| compute simulation results | 9.6 | 9.5 |
| define subroutines | 9.4, 9.5 | 9.1, 9.2 |
| define the RR AddReady method | 8.4 | 8.2 |
| define the RR HandleEvent method | 8.5 | 8.2 |
| define the RR tick method | 8.3 | 8.2 |
| define the SRTF AddReady method | 7.4 | 7.2 |
| define the SRTF HandleEvent method | 7.5 | 7.2 |
| define the SRTF tick method | 7.3 | 7.2 |
| imports | 9.3 | 9.1, 9.2 |
| run the RR simulation | 9.8 | 9.2 |
| run the SRTF simulation | 9.7 | 9.1 |
| Identifier | Defined in | Used in |
|---|---|---|
| AddReady | 7.4 | |
| HandleEvent | 7.5 | |
| HandleEvent | 8.5 | |
| IOWaitTime | 7.2 | |
| LogEvent | 7.16 | |
| ReadyQ | 7.2 | |
| SRTF | 7.2 | |
| preemptTime | 7.2 | |
| read_simulation | 9.4 | |
| run_simulation | 9.5 | |
| running | 7.2 | |
| tick | 7.3 |
| 20100915:114002 | 3.1.0 | ajh and mc | add Marc Cheong's HTML Gantt chart generator |
| 20100909:164701 | 3.0.0 | ajh | initial version for 2010 |
| This page maintained by John Hurst. Copyright Monash University Copyright Policy |
|
  
|
|
Generated at
20120524:0257
from an XML file modified on
20101004:0840 | |||