Operating Systems - Projects and Exercises

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:

1. 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.
    
2. 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:

1. A message displaying the process ID when the process starts;
2. A regular message every second the process is executed; and
3. 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:

1. 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.
2. A process is "ready-to-run" when it has "arrived" and all required resources are available.
3. Any pending Real-Time jobs are submitted for execution on a First Come First Served basis.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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).
9. When a process is terminated, the resources it used are returned to the dispatcher for reallocation to further processes.
10. 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:

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

1. Design a dispatcher that satisfies the above criteria. In a formal design document:
    
   1. Describe and discuss what memory allocation algorithms you could have used and justify your final design choice.
   2. Describe and discuss the structures used by the dispatcher for queuing, dispatching and allocating memory and other resources.
   3. Describe and justify the overall structure of your program, describing the various modules and major functions (descriptions of the function 'interfaces' are expected).
   4. 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.

2. Implement the dispatcher using the C language.
    
3. 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!
    
4. Details of submission procedures will be supplied well before the deadline.
    
5. 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!
    
6. 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

1. Source code file(s), include file(s), and a makefile;
    
2. 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.