CS 305b - Assignment 3 - 1998
			-----------------------------

Due:	Monday, April 6, 1998 at 5:00 p.m. in the locker
Weight: 15% (Part I - 13%, Part II - 2%)

*****************************************************************************
NOTE: This is a two-part assignment. Both parts MUST be handed in together,
      in the same envelope.
******************************************************************************

PART I : Modify the MINIX Scheduler
-----------------------------------

Your assignment is to modify the MINIX scheduler so that user processes have
different priorities. The scheduler will have multiple queues for user
processes, with one queue for each priority value. It will use round-robin
within each priority queue.

The priority value of a process will be greater than or equal to zero,
and a higher priority value will mean a "lower priority" for purposes of
scheduling. The priority value for a process will change during the lifetime
of the process, based on the amount of CPU time that the process has used
"recently". The following method (similar to UNIX) will be used:
   - at every clock tick, a CPU usage counter in the process table entry for
     the running process is incremented by 1
   - process priorities are recalculated once a second, for all processes:
	- the CPU usage counter is divided by 2 (so that a process is not
	  punished forever for past CPU usage)
	- the process priority value is calculated by
 	  new priority = base priority + (new) CPU usage counter
	  (you may assume the base priority is 0)

The operation of the scheduler will be such that it finds the "highest
priority" queue (i.e. the one with the lowest priority value) that is not
empty, and then chooses the first process on that queue.

A process runs for a maximum of 1 quantum, or until it blocks. (Note that a
blocked process is not in any priority queue.) If a process uses up its
quantum, it is put back on the end of its queue.

Note that the MINIX scheduler should still pick tasks and servers to run before
it picks a user process.

Implementation:
~~~~~~~~~~~~~~
How you choose to implement the priority queues and scheduling algorithm
is up to you. Here is an idea from UNIX: each queue is organized as a
doubly-linked list, with the head of each list kept in an array.

What to hand in:
~~~~~~~~~~~~~~~
*****************************************************************************
NOTE: You are encouraged to use a laser printer for your output, source code,
      and documentation, but ONLY if there is no line wrap or other format
      impediments to easy reading.
      Use of the line printer for your output and source code is acceptable,
      IF the printing is dark enough so that it can be read clearly. The line
      printer is NOT acceptable for documentation.
*****************************************************************************

Hand in the following:

1. Listings of the source files in the kernel that you changed

2. Technical Documentation: (laser printed)
	Introduction
	Design Documentation
	Implementation Documentation (includes data structures,
		detailed algorithms, design decisions)
	Testing Documentation

3. Script files for your testing runs.

Testing:
~~~~~~~
You must show the marker that your new MINIX scheduler does indeed
assign priority values to user processes, and uses those in picking the
next user process to run. Idea:  modify the ps command to show the
CPU usage field and priority value field for each process (check out
ps -l on GAUL).


Thank you:
~~~~~~~~~
to Doug Williams for his work on setting up the script file.


PART II : Concepts
------------------

****************************************************************************
NOTE: The answers to PART II must be typed; hand-written submissions will
      not be accepted.

      Explanations must be given for all of your answers.
****************************************************************************

1. Tanenbaum Chapter 3 #22

2. Tanenbaum Chapter 4 #7
	
3. Tanenbaum Chapter 4 #9

4. Tanenbaum Chapter 4 #10

5. Tanenbaum Chapter 4 #11

6. Tanenbaum Chapter 4 #15

7. Assuming a page size of 4 Kbytes and that a page table entry takes
   4 bytes, how many levels of page tables would be required to map the
   address space for a 64-bit address, if the "top" level page table
   fits into a single page?