Due: Tuesday, May 16 at 11:59pm
The goals of the second project are to implement a core set of system calls and support multiprogramming of user-level programs. As in the first project, we provide some of the code you need and your task is to complete the system and enhance it. Until now, all the code you have written for Nachos has been part of the operating system 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. You will enable user-level programs to invoke Nachos routines that you implement in the Nachos kernel.
The changes you make to Nachos will be in these two files in the userprog directory:
as well as a couple of classes in the machine directory:
Nachos emulates user programs executing on a real CPU (a MIPS R3000 chip). By emulating execution, Nachos has complete control over how many instructions are executed at a time, how the address translation works, and how interrupts and exceptions (including system calls) are handled. The emulator can run normal programs compiled from C to the MIPS instruction set. The only caveat is that floating point operations are not supported.
Nachos initially is only able to run a single user-level MIPS program at a time, and supports only one system call fully: halt. All halt does is ask the operating system to shut the machine down. This test program is found in test/halt.c and represents the simplest supported MIPS program.
Nachos provides several other example MIPS programs in the test directory. You can use these programs to test your implementation, and you will be writing new test programs of your own. Of course, you will not be able to run the programs which make use of features such as I/O until you implement the appropriate kernel support. That will be your task in this project.
To compile the test programs, you need a MIPS cross-compiler. This cross-compiler is already installed on the instructional machines as mips-gcc (see the Makefile in the test directory for details). When logged into an instructional machine, prep will initialize two environment variables (ARCHDIR and PATH) to enable you to use the cross-compiler. If you would like to use the cross-compiler on your own Linux machine (or Linux virtual machine), you can download the distribution to your system. Alternatively, you can compile your test programs on ieng6 and copy them over to your own machine.
The test directory includes C source files (.c files) and Nachos user program binaries (.coff files). The binaries can be created while in the test directory by running make, or from the proj2 directory by running make test.
You can run test programs by running
program.coff where program.coff is the name of the
MIPS program binary in the test directory. You will be
creating many test programs both for this project and project 3, and
you will place them all in the test directory. To compile
your test programs, add them to the Makefile in
the test directory in the line:
TARGETS = halt sh matmalt sort echo cat cp mv rm
Regarding project dependencies, project 2 requires the essentials of Alarm.waitUntil (AlarmGrader1-4) and KThread.join to work (JoinGrader1-5). Usually nearly every group passes those tests. If your group didn't, though, follow up with us either in lab or office hours so that we can troubleshoot your implementation. Note that project 2 does not depend on Rendezvous, sleepFor, or Condition2 (you can always use Condition).
That said, some groups are often interested in improving their project 1 code (e.g., Rendezvous). We will configure gradescope so that you can run against the project 1 tests again. However, we strongly encourage you to first work on project 2, and then go back to tinker with project 1.
% prep cs120sp23b
Go to the proj2 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
After typing 'q' at the prompt, 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
Note that the baseline Nachos implementation has code in UserKernel.selfTest() that tests the console device. Nachos executes this code every time it runs. When you start testing your implementation, you can comment out this code so that you do not have to type 'q' every time you run Nachos.
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 UserProcess.readVirtualMemory and UserProcess.writeVirtualMemory, which copy data between the kernel and the user's virtual address space, so that they work with multiple user processes. Note that these methods 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().
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).
Implement named pipes as an interprocess communication mechanism between processes. A pipe has an internal kernel buffer one page in size that follows the producer-consumer pattern (note that, although it has a name, it is not a file in the file system). A process can write into a pipe until the pipe fills up, at which point it blocks until the pipe is no longer full. Write will not return until all bytes from the write buffer have been written into the pipe. A process can read from a pipe as long as the pipe is not empty, at which point it blocks until the buffer is no longer empty. Specifically, if the pipe is not empty when read is called, read will return the bytes that are available in the pipe (even if the read buffer is much larger), up to the size of the read buffer. If the pipe is empty when read is called, read will block until the writer writes more bytes in the pipe (it will not return 0 in this case). Implement the Pipe class as a private inner class of UserProcess.
You need only support one writer and one reader process, where one process creates the pipe and writes to it while another process opens it and reads from it. Use synchronization primitives (not interrupts) to synchronize the writer and reader. A process creates a pipe using the creat system call with a special pipe name argument of the form "/pipe/name", where name is a valid filename string. If a pipe of the same name already exists, creat returns -1. Otherwise, creat creates a new pipe and returns a new file descriptor for it. A system-wide maximum of 16 named pipes can be created at once, and creat returns -1 when 16 pipes are in use.
A process opens a pipe using the open system call with a pipe name as the name argument. If the named pipe has not been created, open returns -1. Otherwise, open returns a new file descriptor for the named pipe. Creating and opening pipes count towards the per-process file descriptor limit. To write or read from a pipe, a process simply calls the write and read system calls on the pipe file descriptor. A process closes a pipe using the close system call on the pipe file descriptor. After being created, a pipe exists as long as at least one process has a file descriptor referring to it.
Here are some guidelines and tips for project 2 from previous CSE 120 TAs:
As with all of the projects, it is your responsibility to implement your own tests to thoroughly exercise your code to ensure that it meets the requirements specified for each part of the project. Testing is an important skill to develop, and the Nachos projects will help you to continue to develop that skill. In this project, you will implement tests as user-level programs written in C. See the discussion at the top of this page on creating test programs in the test directory, compiling them, and running them with Nachos.
The following pages provide testing strategies and example test programs for the project:
As a final step, create a file named README in the proj2 directory. The README file should list the members of your group and provide a short description of what code you wrote, how well it worked, how you tested your code, and how each group member contributed to the project. The goal is to make it easier for us to understand what you did as we grade your project in case there is a problem with your code, not to burden you with a lot more work. Do not agonize over wording. It does not have to be poetic, but it should be informative.
For grading, as with project 1 we will use a snapshot of your Nachos implementation in your github repository as it exists at the deadline, and grade that version. (Even if you have made changes to your repo after the deadline, that's ok, we will use a snapshot of your code at the deadline.) Important: Before the deadline, you must submit your code to Gradescope at least once. See the instructions in the Testing section above.
If you encounter problems with your account (command not found, disk quota exceeded, class file has wrong version, etc.), see these troubleshooting tips.
You can discuss concepts with students in other groups, but do not cheat when implementing your project. Cheating includes copying code from someone else's implementation, or copying code from an implementation found on the Internet. See the main project page for more information.
We will manually check and also run code plagiarism tools on submissions and multiple Internet distributions (if you can find it, so can we).