Part I. Implementation of a Multilevel Feedback Scheduling: (40%)
Implement and test multilevel feedback queue scheduling to reduce average response time for workloads consisting of CPU-bound and I/O-bound jobs on your system. Demonstrate that your new scheduler reduces response time relative to the original Nachos scheduler for at least one workload.
Implement your multilevel feedback scheduler with three ready queues: RQ0, RQ1, and RQ2. When a process P first enters the system, it is put in RQ0. When P is eventually placed in the Running State, if it executes until the end of its assigned time slice, it is placed in RQ1 (back in the Ready State). P is demoted to RQ2 if once again it executes for the duration of the next time slice assigned to it. A process that is blocked OR that yields before it consumes its entire time slice is NOT demoted, i.e., it is returned to the same ready queue.
Scheduling is done on a preemptive basis. RQ0 is the highest priority queue; RQ1 is the next highest; RQ2 is the lowest priority queue. Within each priority queue, preemptive round-robin scheduling is used.
The time slice for RQ0 should last several timer interrupts (see TimerInterruptHandler in system.cc). Design your system such that the time slice for RQ1 is twice as long as the time slice for RQ0, and the time slice for RQ2 is twice as long as the time slice for RQ1.
Finally, extend your multilevel feedback scheduler to support aging. The goal is to promote a process to a higher-priority queue if it spends a certain amount of time waiting in its current queue for service. Aging is an effective technique for dealing with possible starvation associated with multilevel priority queues.
Testing Your Scheduler:
To test your implementation of a multilevel feedback scheduler, you need to create multiple threads in the Nachos kernel. You must simulate CPU-bound as well as I/O-bound threads in your tests. Simulating CPU-bound threads is relatively easy. This can be accomplished by having threads execute long-running loops. Simulating I/O-bound threads is slightly more difficult. We suggest that you insert yield statements and GoToSleepFor alarm clock calls (from Programming Assignment #1) in your test code. Make sure that your test cases also demonstrate that the "aging" mechanism works. (Note: You may wish to disable random yielding so that CPU-bound threads are not preempted prematurely.)
Part II. Implementation of Multiprogramming: (60%)
In Part II of this assignment, you are to modify Nachos to support multiprogramming. The Nachos code we have given you is restricted to running one user program at a time. You will need to: (a) come up with a way of allocating physical memory frames so that multiple programs can be loaded into memory at once; and (b) Implement the following system calls to use the multiprogramming features: Exec, Join, and Exit.(These system calls are discussed later in this document.)Up until now, all the code that you have written for Nachos has been part of the operating system. You have been creating threads that executed within (as part of) the Nachos kernel. In a real operating system, the kernel not only uses its procedures internally, but allows user-level programs to access some of its routines via system calls. In this assignment, you are to modify Nachos to fully support multiple user programs (or processes), using system calls to access services provided by the kernel and the ability to run multiple user programs simultaneously.
In the machine directory, we are giving you a simulated CPU that models a real CPU (a MIPS chip). The simulated CPU simulates each MIPS instruction, including memory operations, register operations, address translation, system calls, etc. The machine can also raise exceptions (also called traps ), which are simply errors in user code such as divide by zero, illegal address, etc. These traps are passed to an exception handler in userprog/exception.cc .
Most of the new files that you will be using are in the nachos/code/userprog directory. By running make depend in userprog directory, followed by make , you should be able to create a nachos executable within the userprog directory that supports running of user programs in a limited manner. By ``limited manner'' we mean that there is no exception handling ( exception handler is called, but it doesn't check for all exceptions), only a small subset of the system calls are implemented, and only one user-level program can run at a time.
By the end of Part II in this assignment you will have implemented some additional system calls (as defined by userprog/syscall.h), and support for running multiple user programs concurrently.
The existing Nachos implementation can run a single user-level "C" program at a time. As a simple working example, we have provided you with a trivial user program, test/halt.c; all halt does is to turn around and ask the operating system to shut the machine down. Run the halt program by the command ../userprog/nachos -x halt (after making the new version of nachos and compiling the halt program). Tracing what happens during the execution of the halt program (using the debug flag) may help you understand what is happening.
The halt program is compiled using a gcc cross-compiler that runs on the SUN SPARC workstation but generates code for the MIPS processor. The path for the cross compiler (on CAEN) is
The three executables that are of concern to us are: decstation-ultrix-gcc, decstation-ultrix-ld, and decstation-ultrix-as. The TAs will post to the newsgroup a new makefile which can be used to compile Nachos user programs.
Please do *not* modify GCCDIR in other directories; you only want to cross-compile user programs that run on Nachos, and not Nachos itself. Nachos itself is compiled to Sparc code as usual. Also, comment out the line with "ASFLAGS = -mips" in that makefile.
Note the halt executable will not run directly on the workstation except by being interpreted by Nachos. Before that can happen, the compiled programs must be converted into Nachos format, using the program ``coff2noff'' (supplied). The Makefile in the test directory, after the above change to the GCCDIR, should take care of producing the Nachos user program executables.
System Call Implementations in Part II:Current nachos only gives the implementation of one system call Halt . You have to implement several additional system calls. See the Nachos Roadmap for more information on Halt is implemented. Basically, all the system calls are defined in start.s, an assembly language routine, that is loaded along with the user program. The assembly language routine places an integer (SC_Halt for Halt()) identifying the system call in register r2 and then invoke a hardware trap instruction syscall. The syscall instruction generates a trap (just like divide by zero), causing control to be transferred to the Nachos exception handler. The nachos exception handler can then do usual OS functions, such as terminating the thread, putting it to sleep, creating a new thread, doing I/O on its behalf, etc.
(Note that UNIX has a similar facility as syscall for generating a trap for making a system call. Try doing `man syscall' and looking at /usr/include/sys/syscall.h. You wouldn't be using the Unix stuff, but it is useful to know that what Nachos does is not all that different from techniques used in real operating systems!)
The system calls you have to implement for this part are:
SpaceId Exec(char *executable_file_name):
Creates a user process by creating a new address space, reading the executable file into it, and creating a new internal thread (via Thread::Fork) in which to run it. Set up the MIPS processor state for the new process and then calling machine::Run() starts execution of the instructions in the MIPS machine simulator. The call returns the address space id identifying the child user process to its parent process. Note that this call is different from Unix execv() system call. It is more equivalent to a fork() followed by an execv() system call in Unix.
The routine ``StartProcess'' in progtest.cc may be worth looking at in implementing the ``exec'' system call.
int Join (SpaceId id)
This is called by one process to wait for the termination of another, referred to by its address space id. When the process id exits, this call returns to allow the caller to progress. The exit status of the id is returned.
Void Exit(int status)
The user process calling this is done. The thread running this user program can finish and be destroyed. The status value should printed before the thread is destroyed. Note that the parameter status is placed in register r4 by the normal procedure call mechanism --- you don't have to modify start.s. You can retrieve it within the exception handler routine by examining the register r4.
Important Note: Make sure that the user programs that you write for Part II always end with the "Exit" system call. This allows a proper clean up of kernel data structures and memory allocated to the thread. Also, test your implementation with random yield enabled.Part III. Extra Credit: Multithreaded User Programs(25%)
void Fork(void (*func)()) and void Yield()
Implement the thread fork and yield systemcalls to allow a user program to fork a thread to call a routine in the same address space. The Fork() and Yield() are used to provide user-level threads within a single user-level program. Implementing these will require you to allocate a stack per thread within the user program's address space, figure out what to do with various threads if the user program invokes "Exit(status)" system call (delete address space?, delete all threads or just the thread invoking Exit", etc.).
In the userprog directory, most of your changes will probably go into exception.cc.
In the machine directory all of the files are relevant except for disk.h, disk.cc, network.h, and network.cc. The files in the machine directory should not need to be modified, except to increase as amount of physical memory on the simulated MIPS machine, so that you can load Sufficient number of user programs to test multiprogramming features. To increase the physical memory available, increase the value of NumPhyPages in machine.h. You should not need to change anything else in the machine directory. Files of particular interest in the machine directory include: