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:
- Real-Time processes that must be run immediately on a First
Come First Served (FCFS) basis, pre-empting any other processes
running with lower priority. These processes are run till
completion.
- Normal user processes are run on a three level feedback dispatcher
(see "Operating Systems", William Stallings, Prentice Hall).
The basic timing quantum of the dispatcher is 1 second. This is also
the value for the time quantum of the feedback scheduler.

Figure 1. Three Level
Feedback Dispatcher
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.

Figure 2. Round Robin
Dispatcher
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):

Figure 3. Dispatcher
Logic Flow
Resource
Constraints
The HOST has the following resources:
- 2 Printers
- 1 Scanner
- 1 Modem
- 2 CD Drives
- 1024 Mbyte Memory available for processes
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
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
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:
- A message displaying the process ID when the process starts;
- A regular message every second the process is executed;
and
- A message when the process is Suspended, Continued, or
Terminated.
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 process is submitted to the dispatcher input queues
via an initial process list which designates the arrival time,
priority, processor time required (in seconds), memory block
size and other resources requested.
- A process is "ready-to-run" when it has "arrived"
and all required resources are available.
- Any pending Real-Time jobs are submitted for execution
on a First Come First Served basis.
- If enough resources and memory are available for a lower
priority User process, the process is transferred to the appropriate
priority queue within the feedback dispatcher unit, and the
remaining resource indicators (memory list and i/o devices)
updated.
- When a job is started (fork and
exec("process",...)),
the dispatcher will display the job parameters (Process ID,
priority, processor time remaining (in seconds), memory location
and block size, and resources requested) before performing
the exec.
- A Real-Time process is allowed to run until its time has
expired when the dispatcher kills it by sending a SIGINT
signal to it.
- A low priority User job is allowed to run for one dispatcher
tick (one second) before it is suspended (SIGTSTP)
or terminated (SIGINT) if its time
has expired. If suspended, its priority level is lowered (if
possible) and it is re-queued on the appropriate priority
queue as shown in Figures 1 & 3 above. To retain synchronisation
of output between your dispatcher and the child process, your
dispatcher should wait for the process to respond to a SIGTSTP
or SIGINT signal before continuing
( waitpid(p->pid, &status, WUNTRACED)).
To match the performance sequence indicated in Stallings'
comparison of scheduling policies (ibid Figure 9.5
p.405) the User job should not be suspended and moved to a
lower priority level unless another process is waiting to
be (re)started.
- Provided no higher priority Real Time jobs are pending
in the submission queue, the highest priority pending process
in the feedback queues is started or restarted (SIGCONT).
- When a process is terminated, the resources it used are
returned to the dispatcher for reallocation to further processes.
- When there are no more processes in the dispatch list,
the input queues and the feedback queues, the dispatcher exits.
Dispatch
List
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.
>hostd dispatchlist
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>
Thus,
12, 0, 1, 64, 0, 0, 0, 0
12, 1, 2, 128, 1, 0, 0, 1
13, 3, 6, 128, 1, 0, 1, 2
would indicate:
1st Job: |
Arrival at time 12, priority 0 (Real-Time), requiring
1 second of c.p.u. time and 64 Mbytes memory - no i/o resources
required. |
2nd Job: |
Arrival at time 12, priority 1 (high priority User job),
requiring 2 seconds of c.p.u. time, 128 Mbytes of memory,
1 printer and 1 CD drive. |
3rd Job: |
Arrival at time 13, priority 3 (lowest priority User job),
requiring 6 seconds of c.p.u., 128 Mbytes of memory, 1 printer,
1 modem, and 2 CD drives. |
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.
Project
Requirements
- Design a dispatcher that satisfies the above criteria.
In a formal design document:
- Describe and discuss what memory allocation
algorithms you could have used and justify your final
design choice.
- Describe and discuss the structures used
by the dispatcher for queuing, dispatching and allocating
memory and other resources.
- Describe and justify the overall structure
of your program, describing the various modules and major
functions (descriptions of the function 'interfaces' are
expected).
- Discuss why such a multilevel dispatching scheme would
be used, comparing it with schemes used by "real" operating
sytems. Outline shortcomings in such a scheme, suggesting
possible improvements. Include the memory and resource
allocation schemes in your discussions.
The formal design document is expected to have in-depth
discussions, descriptions and arguments. The design document
is to be submitted separately as a physical paper document.
The design document should NOT include any source
code.
- Implement the dispatcher using the C language.
- The source code MUST be extensively commented and appropriately
structured to allow your peers to understand and easily maintain
the code. Properly commented and laid out code is much easier
to interpret and it is in your interests to ensure that the
person marking your project is able to understand your
coding without having to perform mental gymnastics!
- Details of submission procedures will be supplied well before
the deadline.
- The submission should contain only source code file(s),
include file(s), and a makefile.
No executable program should be included. The marker will
be automatically rebuilding your program from the source code
provided. If the submitted code does not compile it can not
be marked!
- The makefile should generate the binary
executable file hostd (all lower case please).
A sample makefile would be:
# Joe Citizen, s1234567
- Operating Systems Project 2
# CompLab1/01 tutor: Fred Bloggs
hostd: hostd.c utility.c hostd.h
gcc hostd.c utility.c
-o hostd
The program hostd is then generated by
just typing make at the command line prompt.
Note: the fourth line in the above makefile
MUST begin with a tab
Deliverables
- Source code file(s), include file(s), and a makefile;
- The design document as outlined in Project Requirements
section 1 above.
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.
Marking
Criteria
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:
- Description, discussion and justification of choice of memory
allocation algorithms - 20 marks
- Description and discussion of the structures used by the
dispatcher - 5 marks
- Description and justification of the program structure
and individual modules - 15 marks
- Discussion of dispatching scheme (including memory and resource
allocation), shortcomings, and possible improvements - 30 marks.
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:
- Operation of FCFS high priority scheduler - 10 marks
- Operation of User Feedback scheduler - 10 marks
- Operation of User Feedback scheduler in Round Robin mode
- 10 marks
- Mixed scheduler operation - 10 marks
- Resource allocation - 10 marks
- Memory management - 10 marks
- Combination of all requirements - 10 marks
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.
|