CSE 220 Project 2: Multiprogramming

Tasks

0. (0%) Run your first Nachos user-level program. Prep as you did for task 1 in project 0. Then go to the proj2 build directory, run make test to compile the test programs, run make to compile Nachos, and then run nachos -x halt.coff.

       % cd nachos/proj2
       % make test
       % make
       % nachos -x halt.coff
   

   Nachos will shutdown ("Machine halting!"). To give you more insight into what happens as the user program gets loaded, runs, and invokes a system call, next run nachos -d a -x halt.coff. The 'a' debug flag prints process loading information.

       % nachos -d a -x halt.coff
   

1. (35%) Implement the file system calls creat, open, read, write, close, and unlink. Their semantics and specifications are documented in test/syscall.h, and the calling conventions are documented in the comments to UserProcess.handleSyscall. You will see the code for halt and skeleton code for exit in UserProcess.java. Implement the other system calls following the same pattern. Note that you are not implementing a file system. Rather, you are simply giving user processes the ability to access a file system that Nachos already implements. For further suggestions and tips, see the Tips section below. For examples and strategies for testing, see the Testing section below.

   • First implement the core functionality for each system call assuming correct parameters. Wait until you have the core functionality working before worrying about error conditions, incorrect parameters, and other corner cases.

   • Since the memory addresses passed as arguments to the system calls are virtual addresses, you need to use readVirtualMemory (rVM) and writeVirtualMemory (wVM) to transfer data between the user process and the kernel. In your handleRead and handleWrite methods, use a simple byte buffer to stage the data between the process virtual address space and calling into rVM and wVM.

   • User processes store filenames and other string arguments as null-terminated strings in their virtual address space. The maximum length for strings passed as arguments to system calls is 256 bytes (including the terminating null).

   • A stub file system interface to the UNIX file system is already provided for you, and the interface is implemented by the class machine/FileSystem.java. You can access the stub filesystem through the static field ThreadedKernel.fileSystem. (Note that since UserKernel extends ThreadedKernel, you can still access this field.) This filesystem is capable of accessing the test directory in Nachos, which is going to be useful when you implement the exec system call described below. You do not need to implement any file system functionality, but you should examine carefully the specifications for FileSystem and StubFileSystem to determine what functionality you need to implement, and what is handled by the file system.

   • Each file that a process opens should have a unique file descriptor associated with it (see syscall.h for details). The file descriptor should be a non-negative integer that is simply used to index into a table of currently-open files by that process. Your implementation should have a file table size of 16, supporting up to 16 concurrently open files per process. Note that a given file descriptor can be reused if the file associated with it is closed, and that different processes can use the same file descriptor value to refer to different files.

   • When any process is started, its file descriptors 0 and 1 must refer to standard input and standard output. Use UserKernel.console.openForReading() and UserKernel.console.openForWriting() to implement these semantics. A user process is allowed to close these descriptors, just like descriptors returned by open.

   • System calls should return the appropriate value as documented in test/syscall.h. When a system call needs to indicate an error condition to the user, it should return -1. In particular, it should not assert or otherwise throw an exception.

   • Do not implement any file locking, the file system is responsible for it. If ThreadedKernel.fileSystem.open() returns a non-null OpenFile, then the user process is allowed to access the given file; otherwise, you should return an error. Likewise, you do not need to worry about the details of what happens if multiple processes attempt to access the same file at once; the stub filesystem handles these details for you.

   • As the final step, once you have the core functionality for the system calls working, "bullet-proof" the Nachos kernel from user program errors. There should be nothing a user program can do to crash the operating system (with the exception of explicitly invoking the halt syscall). In other words, you must ensure that if a user program passes bad arguments to the kernel (e.g., a NULL pointer value of 0x0, or an invalid address), it will not cause the kernel to crash, or corrupt its internal state or that of other processes.

2. (30%) Implement support for multiprogramming. The initial Nachos code is restricted to running only one user process, and your task is to make it work for multiple user processes. For further suggestions, see the Tips section below. For examples and strategies for testing, see the Testing section below.

   • You will need to manage the allocation of pages of physical memory so that different processes do not overlap in their memory usage. You can use whatever data structure you like to manage physical pages, but we suggest maintaining a static linked list of free physical pages (perhaps as part of the UserKernel class). Be sure to use synchronization where necessary when accessing this list to prevent race conditions.

     Your solution must make efficient use of memory by allocating pages for a new process wherever possible. This means that it is not acceptable to only allocate pages in a contiguous block; your implementation must be able to make use of "gaps" in the free memory pool.

   • You will create and initialize the pageTable data structure for each user process, which maps the process's virtual addresses to physical addresses. The TranslationEntry class represents a single virtual-to-physical page translation. The field TranslationEntry.readOnly should be set to true if the page is coming from a COFF section which is marked as read-only. You can determine this status using the method CoffSection.isReadOnly().

     Modify UserProcess.loadSections() so that it allocates the pageTable and the number of physical pages based on the size of the address space required to load and run the user program (and no larger). This method is the one that should set up the pageTable structure for the process so that the program is loaded into the physical memory pages it has allocated for the address space. Note that user programs do not make use of malloc or free, meaning that user programs effectively have no dynamic memory allocation (and therefore no heap). The stack is fixed size as well. As a result, Nachos knows how many virtual pages a new process needs for its address space when it is created. If the new user process cannot allocate sufficient physical pages for its address space, exec should return an error.

     All of a process's memory should be freed on exit (whether it exits normally, via the syscall exit, or abnormally, due to an illegal operation). As a result, its physical pages can be subsequently reused by future processes.

   • Modify readVirtualMemory (rVM) and writeVirtualMemory (wVM), which copy data between the kernel and the user's virtual address space, so that they work with multiple user processes. When implementing rVM and wVM, make sure that you fully implement the rVM and wVM functionality as specified in their method comments. In particular, the buffer passed in could be of arbitrary size and span many pages. Note that these methods also should not throw exceptions if they encounter an error when copying data; instead, they must always return the number of bytes transferred (even if that number is zero).

     The physical memory of the MIPS machine is accessed through the method Machine.processor().getMemory(), and the total number of physical pages is Machine.processor().getNumPhysPages().

   • The user threads (see the UThread class) already save and restore user machine state, as well as process state, on context switches. So you are not responsible for these details.

3. (35%) Implement the system calls exec, join, and exit, also documented in syscall.h. For further suggestions, see the Tips section below. For examples and strategies for testing, see the Testing section below.
   • Note that, although Nachos chose the name exec for its system call, it is not the same as the Unix exec system call. As described in syscall.h, the Nachos exec system call both creates a new process and loads a new program into that process. (As a result, it essentially combines fork/exec on Unix and is similar to CreateProcess on Windows.)

   • As with the other system calls, the addresses passed in registers as arguments to exec and join are virtual addresses. Use the methods readVirtualMemory and readVirtualMemoryString to transfer data between kernel memory and the memory of the user process.

   • Note that the memory of the child process is entirely private to this process. This means that the parent and child do not directly share memory or file descriptors. Note that two processes can open the same file; for example, all processes should have file descriptors 0 and 1 mapped to the system console, as described above.

   • Use KThread.join to implement the join system call (you have implemented the functionality once, no need to implement it again). Unlike threads using KThread.join in project 1, though, for this project enforce the rule that only a process's parent can join to it. For instance, if A execs B and B execs C, A is not allowed to join to C, but B is allowed to join to C.

   • join takes a process ID as an argument, which is used to uniquely identify the child process which the parent wishes to join with. The process ID should be a globally unique positive integer, assigned to each process when it is created. Set the process ID of the first process to 0. (Although for this project the only use of the process ID is in join, for project 3 it is important that the process ID is unique across all running processes in the system.) The easiest way of accomplishing this is to maintain a static counter which indicates the next process ID to assign. Since the process ID is an int, then it may be possible for this value to overflow if there are many processes in the system. For this project you are not expected to deal with this case; that is, assume that the process ID counter will not overflow.

   • Extend the implementation of the halt system call so that it can only be invoked by the "root" process — that is, the initial process in the system. If another process attempts to invoke halt, the system should not halt and the handler should return immediately with -1 to indicate an error.

   • When a process calls exit, its thread should be terminated and the process should clean up any state associated with it (i.e., free up memory, close open files, etc.). Modify handleException to perform the same cleanup if a process exits abnormally (e.g., executes an illegal instruction).

   • If a parent process has called join on a child process, and the child process exits normally, then join needs to transfer the child's exit status value to the parent (see methods in the Lib class for converting between bytes and integers). A child process exits normally when it calls the exit system call and provides a status value as an argument. If the status parameter is NULL, then join behaves normally and simply does not return the status from the child. If the status parameter is invalid (e.g., beyond the end of the address space), then join immediately returns with -1 to indicate an error.

     If a child process terminates abnormally (e.g., due to an unhandled exception), it will not have an exit status. In this case, join will return 0 to the parent and the value of the status parameter does not need to be set (see test/syscall.h for the complete specification).

   • The last process to call exit should cause the machine to halt by calling Kernel.kernel.terminate(). (Note that only the root process should be allowed to invoke the halt system call, but the last exiting process should call Kernel.kernel.terminate() directly.)

   • As a last step, bullet-proof these syscalls (e.g., handle cases such as the program passing a NULL pointer value of 0x0, or an invalid address, as the file name to exec).