Design (20 points) and Implementation (60 points) - (80 points total) Before you begin this assignment, tag your repository as asst2-begin. System calls and exceptions Implement system calls and exception handling. The full range of system calls that we think you might want over the course of the semester is listed in kern/include/kern/callno.h. For this assignment you should implement: • getpid • fork • execv • waitpid, • _exit It's crucial that your syscalls handle all error conditions gracefully (i.e., without crashing OS/161.) You should consult the OS/161 man pages included in the distribution( in ~os161/os161-1.11/man/syscall directory) and understand fully the system calls that you must implement. You must return the error codes as described in those man pages. Additionally, your syscalls must return the correct value (in case of success) or error code (in case of failure) as specified in the man pages. Some of the grading scripts rely on the return of appropriate error codes; adherence to the guidelines is as important as the correctness of the implementation. The file include/unistd.h contains the user-level interface definition of the system calls that you will be writing for OS/161 (including ones that are relevant for another potential assignment). This interface is different from that of the kernel functions that you will define to implement these calls. You need to design this interface and put it in kern/include/syscall.h. As you may have discovered in OS 161/Asst0, the integer codes for the calls are defined in kern/include/kern/callno.h. You need to think about a variety of issues associated with implementing system calls. Perhaps the most obvious one is: can two different user-level processes (or user-level threads, if you choose to implement them) find themselves running a system call at the same time? Be sure to argue for or against this, and explain your final decision in the design document. For any given process, the first file descriptors (0, 1, and 2) are considered to be standard input (stdin), standard output (stdout), and standard error (stderr). These file descriptors should start out attached to the console device ("con:"). Although these system calls may seem to be tied to the filesystem, in fact, these system calls are really about manipulation of file descriptors, or process-specific filesystem state. A large part of this assignment is designing and implementing asystem to track this state. Some of this information (such as the current working directory) is specific only to the process, but others (such as file offset) is specific to the process and file descriptor. Don't rush this design. Think carefully about the state you need to maintain, how to organize it, and when and how it has to change. Note that there is a system call __getcwd() and then a library routine getcwd(). Once you've written the system call, the library routine should function correctly. getpid() A pid, or process ID, is a unique number that identifies a process. The implementation of getpid() is not terribly challenging, but pid allocation and reclamation are the important concepts that you must implement. It is not OK for your system to crash because over the lifetime of its execution you've used up all the pids. Design your pid system; implement all the tasks associated with pid maintenance, and only then, implement getpid(). fork(), execv(), waitpid(), _exit() These system calls are probably the most challenging part of the assignment, but also the most rewarding. They enable multiprogramming and make OS/161 a much more useful entity. fork() is the mechanism for creating new processes. It should make a copy of the invoking process and make sure that the parent and child processes each observe the correct return value (that is, 0 for the child and the newly created pid for the parent). You will want to think carefully through the design of fork() and consider it together with execv() to make sure that each system call is performing the correct functionality. execv(), although "only" a system call, is really the heart of this assignment. It is responsible for taking newly created processes and make them execute something useful (i.e., something different than what the parent is executing). Essentially, it must replace the existing address space with a brand new one for the new executable (created by calling as_create in the current dumbvm system) and then run it. While this is similar to starting a process straight out of the kernel (as runprogram() does), it's not quite that simple. Remember that this call is coming out of userspace, into the kernel, and then returning back to userspace. You must manage the memory that travels across these boundaries very carefully. (Also, notice that runprogram() doesn't take an argument vector -- but this must of course be handled correctly in execv()). Although it may seem simple at first, waitpid() requires a fair bit of design. Read the specification in the OS 161 waitpid() man page carefully to understand the semantics, and consider these semantics from the ground up in your design. Youmay also wish to consult the general UNIX man page, though keep in mind that you are not required to implement all the things UNIX waitpid() supports, nor is the UNIX parent/child model of waiting the only valid or viable possibility. The implementation of _exit() is intimately connected to the implementation of waitpid(). They are essentially two halves of the same mechanism. Most of the time, the code for _exit() will be simple and the code for waitpid() more complicated, but it's perfectly viable to design it the other way around as well. If you find both are becoming extremely complicated, it may be a sign that you should rethink your design. kill_curthread() As part of this project, you may need to write the code for kill_curthread(). Feel free to write it in as simple a manner as possible. Just keep in mind that essentially nothing about the current thread's userspace state can be trusted if it has suffered a fatal exception -- it must be taken off the processor in as judicious a manner as possible, but without returning execution to the user level. A note on errors and error handling of system calls: The man pages in the OS/161 distribution contain a description of the error return values that you must return. If there are conditions that can happen that are not listed in the man page, return the most appropriate error code from kern/errno.h. If none seem particularly appropriate, consider adding a new one. If you're adding an error code for a condition for which Unix has a standard error code symbol, use the same symbol if possible. If not, feel free to make up your own, but note that error codes should always begin with E, should not be EOF, etc. Consult Unix man pages to learn about Unix error codes; on Linux systems "man errno" will do the trick. Note that if you add an error code to kern/include/kern/errno.h, you need to add a corresponding error message to the file lib/libc/strerror.c. Design Considerations Here are some additional questions and thoughts to aid in writing your design document. They are not, by any means, meant to be a comprehensive list of all the issues you will want to consider. You do not need to explicit answer or discuss these questions in your design document, but you should at least think about them. Your system must allow user programs to receive arguments from the command line. For example, you should be able to run the following program: char *filename = "/bin/cp"; char *args[4];pid_t pid; args[0] = "cp"; args[1] = "file1"; args[2] = "file2"; args[3] = NULL; pid = fork(); if (pid == 0) execv(filename, argv); which will load the executable file cp, install it as a new process, and execute it. The new process will then find file1 on the disk and copy it to file2. Some questions to think about: Passing arguments from one user program, through the kernel, into another user program, is a bit of a chore. What form does this take in C? This is rather tricky, and there are many ways to be led astray. You will probably need several iterations to get this right. What primitive operations exist to support the transfer of data to and from kernel space? Do you want to implement more on top of these? How will you determine: (a) the stack pointer initial value; (b) the initial register contents; (c) the return value; (d) whether you can exec the program at all? You will need to "bullet-proof" the OS/161 kernel from user program errors. There should be nothing a user program can do to crash the operating system (with the exception of explicitly asking the system to halt). What new data structures will you need to manage multiple processes? What relationships do these new structures have with the rest of the system? Testing your system call implementations To test your system call implementations, the best way would be to write small programs that make use of those system calls (fork, exec, waitpid, etc.), compile with cs161-gcc compiler, and run it under os161. Specifically, when you build and invoke your kernel, on the sys161 menu, choose first the "Operations Menu", and then use the "[p]" option to invoke the executable. For example, typing: p testbin/forktestwould invoke the forktest executable which is already provided in the "testbin" directory. The "testbin" directory has other executables; and some of them may be useful for debugging. By reading the first few lines of C programs there, you may be able to see whether the test program is suitable for this project or not. But more importantly, do not restrict your tests with the programs in the testbin directory. In fact it may be wiser to first use very small programs (like the program with fork() and exec() whose code is given on the previous page). For example you can store that program in a separate directory under testbin and compile (by preparing and running a Makefile similar to that available for "forktest" in testbin). Those makefiles call cs161-gcc compiler with proper flags. And then you can again use p testbin/myprogram if the name of your new executable is myprogram. In your submission, include in your asst2 directory the scripts for the tests that you designed so that we can evaluate them as well. In this project, it is NOT necessary to implement the file-system related system calls (such as read() and write()). You can certainly do that if you wish; but it is not required. However, you will still need a "shortcut" in order to execute library calls like putchar(), printf() to print to the screen; because those calls issue a call to "write()". If you don't want to implement "write()" separately, you can do the following: Go to the kern/arch/mips/mips directory, and open for editing the file syscall.s. Within the mips_syscall() function, you will see a switch statement. To handle the calls to "write()", add the following to the switch statement: case SYS_write: for (i = 0; i < (size_t) tf->tf_a2; ++i) { kprintf("%c", ((char *) tf->tf_a1)[i]); } Save syscall.s, build your kernel again, and this should be sufficient for simply printing to the screen. In fact, even the "forktest" program will need this "patch" in addition to the correct implementation of fork(), and exec(), for proper printing. But as we mentioned, it is best to test your implementations first with very short programs, before moving to "forktest" which is more complicated. You may also find some of the programs from the bin directory useful, such as false,and true.Scheduling Right now, the OS/161 scheduler implements a simple Round-Robin queue. As we learned in class, this is typically not the best method for achieving optimal processor performance. For this assignment, you will extend this scheduling algorithm, by adding another queue, converting it into a multi-level (2) feedback queuing system. Both queues will use Round-Robin, and the quantum of the second queue should be two times the quantum of the first. You want the scheduler to be configurable by making it possible to specify the quantum of the first queue. It is OK to have to recompile to change these settings, as with the HZ parameter of the default scheduler. And it is OK to require a recompile to switch schedulers. But it shouldn't require editing more than a couple #defines or the kernel config file to make these changes. In any event, OS/161 should display at boot time which scheduler is in use. Test your scheduler by running several of the test programs from testbin (e.g., add.c, hog.c, farm.c, sink.c, kitchen.c, ps.c) using the default time slice and scheduling algorithm. Experiment with it. Write down what you expect to happen. Then compare what actually happened to what you predicted and explain the difference. It is critical that you plan, run, and report the experiments for the scheduling component in your report, to get credit for this part. Suggestions In this project, you can continue to work with your partner from Assignment 3. If you worked alone in Assignment 3, you can pair up with another CS 571 student who also worked alone in Assignment 3. You will need to (again) put significant time in reading the existing OS 161 kernel code. Make sure to allocate sufficient time to debugging and extensive testing; consider also testing your partner's code extensively! On the assignment due date: 1. Commit all your final changes to the system. Make sure your partner has committed everything as well. Make sure you have the most up-to-date version of everything. Re-run make on both the kernel and userland to make sure all the last-minute changes get incorporated. 2. Run the tests and generate scripts. If anything breaks, repeat step 1. 3. Tag your CVS repository; prepare the diff and submission source tree. 4. Make your submission to the Blackboard by following the guidelines below.