The Hypothetical Operating System Testbed (HOST) is a multiprogramming system with a four level priority process dispatcher operating within the constraints of finite available resources.
Four-Level Priority Dispatcher
The dispatcher operates at four priority levels:
The dispatcher needs to maintain two submission queues - Real-Time and User priority - fed from the job dispatch list. The dispatch list is examined at every dispatcher tick and jobs that "have arrived" are transferred to the appropriate submission queue. The submission queues are then examined; any Real-Time jobs are run to completion, pre-empting any other jobs currently running.
The Real-Time priority job queue must be empty before the lower priority feedback dispatcher is reactivated. Any User priority jobs in the User job queue that can run within available resources (memory and i/o devices) are transferred to the appropriate priority queue. Normal operation of a feedback queue will accept all jobs at the highest priority level and degrade the priority after each completed time quantum. However, this dispatcher has the ability to accept jobs at a lower priority, inserting them in the appropriate queue. This enables the dispatcher to emulate a simple Round Robin dispatcher if all jobs are accepted at the lowest priority.
When all "ready" higher priority jobs have been completed, the feedback dispatcher resumes by starting or resuming the process at the head of the highest priority non-empty queue. At the next tick the current job is suspended (or terminated and its resources released) if there are any other jobs "ready" of an equal or higher priority.
The logic flow should be as shown below (and as discussed in the exercises):
The HOST has the following resources:
Low priority processes can use any or all of these resources, but the HOST dispatcher is notified of which resources the process will use when the process is submitted. The dispatcher ensures that each requested resource is solely available to that process throughout its lifetime in the "ready-to-run" dispatch queues: from the initial transfer from the job queue to the Priority 1-3 queues through to process completion, including intervening idle time quanta.
Real-Time processes will not need any i/o resources (Printer / Scanner / Modem / CD), but will obviously require memory allocation - this memory requirement will always be 64 Mbytes or less for Real-Time jobs.
Memory allocation must be as a contiguous block of memory for each process that remains assigned to the process for the lifetime of that process.
Enough contiguous spare memory must be left so that the Real Time processes are not blocked from execution - 64 Mbytes for a running Real-Time job leaving 960 Mbytes to be shared amongst "active" User jobs.
The HOST hardware MMU can not support virtual memory so no swapping of memory to disk is possible. Neither is it a paged system.
Within these constraints, any suitable varible partition memory allocation scheme (First Fit, Next Fit, Best Fit, Worst Fit, Buddy, etc) may be used.
Processes on HOST are simulated by the dispatcher creating a new process for each dispatched process. This process is a generic process (supplied as "process" - source: sigtrap.c) that can be used for any priority process. It actually runs itself at very low priority, sleeping for one second periods and displaying:
The process will terminate of its own accord after 20 seconds if it is not terminated by your dispatcher. The process prints out using a randomly generated colour scheme for each unique process, so that individual "slices" of processes can be easily distinguishable. Use this process rather than your own.
The life-cycle of a process is:
The Dispatch List is the list of processes to be processed by the dispatcher. The list is contained in a text file that is specified on the command line. i.e.
Each line of the list describes one process with the following data as a "comma-space" delimited list:
<arrival time>, <priority>, <processor time>, <Mbytes>, <#printers>, <#scanners>, <#modems>, <#CDs>
The submission text file can be of any length, containing up to 1000 jobs. It will be terminated with an end-of-line followed by an end-of-file marker.
Dispatcher input lists to test the operation of the individual features of the dispatcher are described in the exercises. It should be noted that these lists will almost certainly form the basis of tests that will be applied to your dispatcher during marking. Operation as described in the exercises will be expected.
Obviously, your submitted dispatcher will be tested with more complex combinations as well!
A fully functional working example of the dispatcher will be presented during the course. If in any doubt as to the manner of operation or format of output, you should refer to this program to observe how your dispatcher is expected to operate.
Submission of code
A makefile is required. All files will be copied to the same directory, therefore do not include any paths in your makefile. The makefile should include all dependencies that build your program. If a library is included, your makefile should also build the library.
To make this clear: do not submit any binary or object code files. All that is required is your source code and a makefile. Test your project by copying the source code only into an empty directory and then compile it with your makefile.
The marker will be using a shell script that copies your files to a test directory, performs a make, and then exercises your dispatcher with a standard set of test files. If this sequence fails due to wrong names, wrong case for names, wrong version of source code that fails to compile, non-existence of files etc. then the marking sequence will also stop. In this instance, the only further marks that can be awarded will be for the source code and design document.
The project will be marked out of 170.
70 marks will be allocated for the submitted documentation, which will be judged on depth of discussion, readability, maintainability, completeness, and demonstration of an understanding of the problems and your solution:
30 marks will be allocated for the source code which will be judged on presentation (incl. complying with requirements), readability, suitability & maintainability of source code and the makefile.
The balance of the marks (70) will be based on the operation and functionality of your dispatcher and how well it performs against the supplied benchmarks:
Part marks will be awarded for incomplete projects or programs only providing a subset of the above requirements. Where only part of the project has been attempted a statement to that effect should be included in the submission.
For use only by students and instructors using the supplementary material available with the text book: "Operating Systems - Internals and Design Principles", William Stallings, Prentice Hall, 5th Edition, 2004. Not to be printed out or copied by any other persons or used for any other purpose without written permission of the author(s).