Lab 2: Multiprocessing

Important deadlines

• Design docuement due 1/20 (Thursday) at 9:00pm (post to your design pod channel on Slack)
• Peer feedback due 1/25 (Tuesday) at 9:00pm (also post your design pod Slack channel)
• Lab implementation due 1/28 (Friday) at 9:00pm (submit on Gradescope).

Introduction

This lab adds process management to osv. You will add support for the following UNIX system calls:

• fork: creates a copy of the current process, returning from the system call in each context (but with different return values).
• wait: allows a process to pause until a child process finishes executing.
• exit: terminates the current process and releases kernel resources given to the process.

Pull the latest changes to the baseline code by running

$ git pull upstream master

and merge.

After the merge, double check that your code still passes the lab 1 tests.

Writing design docs

Starting with this lab, I will ask you to write a small design document. Lab 2 will be time consuming and difficult, and there are many design decisions to be made.

• You have been assigned to a design pod channel on the course Slack. This is where you will post your design document.
• The design doc for lab 2 is due on 1/20 at 9pm.
• You have been grouped with another group for a round of peer review on your design documents. These students will share your design pod Slack channel.
  • Your feedback for your peer review group members is due 1/25.
  • Substantive participation in peer review will be part of your grade for the course.

If you are working with a partner, you only need to create one design document. You should collaborate with your partner on both your design document and giving peer review feedback.

Follow the guidelines on how to write a design document (these guidelines also cover peer review). I have provided a design doc template for lab 2 (raw markdown—GitHub will nicely render Markdown documents in the repo). However, you are free to write your design document in whatever format you wish.

The reference solution for this lab made changes to

• include/kernel/proc.h
• kernel/proc.c
• kernel/syscall.c

Implement the fork, wait, and exit system calls

These system calls work together as a unit to support multiprocessing. You can start by implementing fork, but one of the first tests will have the new process call process exit.

osv fork duplicates the state of the user-level application. The system call fork returns twice: 1. Once in the parent, with the return value of the process ID (pid) of the child 2. Once in the child, with a return value of 0

The open files should be shared between both the parent and the child, e.g. calling read in the parent should advance the offset in both the parent and the child. In short, a child process inherits a parent’s open file table. The child process should have its own address space, meaning

• any changes in the child’s memory after fork is not visible to the parent
• any changes in the parent’s memory after fork is not visible to the child

Keeping track of processes

osv provides a process table (ptable) which tracks all processes and a lock (ptable_lock) to protect this process table. Both are defined in kernel/proc.c. If a process needs to find child processes, it can loop through the process table (see ptable_dump for an example).

ptable_dump (in proc.c) is a debugging function that iterates over the process table and prints every process’s name and pid. Feel free to modify this function to dump more information if you extend the process struct.

Implementation

Implement proc_fork in kernel/proc.c. Once a new process is created, osv will run it concurrently via the process scheduler. A hardware device generates a timer interrupt on fixed intervals. If another process/thread is READY, the scheduler will switch to it, essentially causing the current process to yield the CPU.

The implementation of sys_fork in kernel/syscall.c is provided to you.

Synchronization between parent and child process

exit takes in a status, which is the exit status of the process. This needs to be saved somewhere, since its parent might ask for it in wait. Note that STATUS_ALIVE (kernel/proc.h) is a reserved exit status value that will not be used by any process, so you can safely use STATUS_ALIVE as an initial value for exit status.

exit also needs to release kernel resources given to the process. On process creation, the kernel gives each process

• an address space
• a kernel thread
• a process struct

All of these need to be cleaned up, plus any information tracked by the process struct (e.g., open file table).

osv takes care of cleaning up the process’s address space (proc_exit) and its thread for you (thread_exit, thread_cleanup), but you still need to clean up the rest and communicate your exit status back to the parent process. This communication is tricky. Let’s say you decide to store the exit status in struct A (can be process struct or something else)—you cannot free this struct until the parent process has seen it (or exited). One way to handle this problem is by relying on another process (e.g., the parent) to free it after it has seen the exit status.

The wait system call interacts with fork and exit. It is called by the parent process to wait for a child. Note that a parent can

• create multiple child processes
• wait on a specific child or any child to exit, and get its exit status.

You need to be careful with synchronization here. The parent may call wait before any child calls exit. In that case, the wait should block (e.g., use a condition variable) until the child being waiting on exits. Note that the parent need not call wait; it can exit without waiting for the child. The child’s data structures must still be reclaimed in this case when the child does eventually exit.

There are various ways that you can implement all of this, so you should think through the various cases and design an implementation before you start to code. If you choose to let the parent clean up its exited children. you will need some way to reclaim the children’s data when the parent exits first. (Note that in osv as in UNIX, the initial(user/init.c) process never exits, meaning an exiting process could “hand off” its children to this process.)

In short, cases you need to think through are:

• parent waits before child exits
• parent waits after child exits
• parent exits without waiting for child

Implementation

Implement exit and wait. This should include the system calls (sys_exit and sys_wait in kernel/syscall.c), and the underlying functions in kernel/proc.c, proc_exit and proc_wait.

/*
 * Corresponds to void exit(int status);
 * 
 * Halts program and reclaims resources consumed by program.
 * The process will exit with the given status.
 * Should never return.
 */
sysret_t
sys_exit(void *arg);

/*
 * Corresponds to int wait(int pid, int *wstatus);
 * 
 * Suspend execution until a child process terminates. 
 * Wait for child with pid `pid` to terminate, if pid is -1, wait for any child process.
 * If wstatus is not NULL, store the exit status of the child in wstatus.
 * A parent can only wait for the same child once.
 * 
 * Return:
 * PID of the child process that terminated.
 * ERR_FAULT - Address of wstatus is invalid.
 * ERR_CHILD - The caller does not have a child with the specified pid, or have already waited
 *             for the child.
 */
sysret_t
sys_wait(void *arg);

/* Exit a process with a status */
void proc_exit(int);

/*
 * Wait for a process to change state. If pid is ANY_CHILD, wait for any child process.
 * If wstatus is not NULL, store the the exit status of the child in wstatus.
 *
 * Return:
 * pid of the child process that changes state.
 * ERR_CHILD - The caller does not have a child with the specified pid.
 */
int proc_wait(pid_t, int* status);

Testing

After you implement the system calls described above, test lab 2 code by either running individual tests in osv shell (i.e., make qemu and then enter the name of the test file in user/lab2 without the .c), or run python3 test.py 2 to run all the tests.

Some of the tests depend on open, close, and read. If you were not able to get these working in lab 1, please see me.

When debugging, I would recommend running individual tests in osv. test.py depends on observing TEST-NAME passed in the output from osv, and the presence of debugging print statements can interfere with this (as output from various processes can get mixed together). It’s also important, therefore, that you disable any print statements before submission to Gradescope.

Things to keep in mind:

• Access memory after deallocation can read garbage values or cause a kernel panic. In particular, be careful about accessing fields of a struct proc after proc_free might have been called on it.
• Make sure you release any held locks before a function returns (otherwise the system could deadlock as one thread holds the lock forever).
  • A thread trying to acquire a lock it already holds will result in a kernel panic.
• It may be useful to include the pid as part of any debugging prints, so you can follow which processes are calling various functions.
• Leave fork-tree and race-test for last, as these tests are the most complex (many concurrent processes).

What to turn in

You will submit your work for this project via Gradescope.

Gradescope lets you submit via GitHub, which is probably the easiest method. All you’ll need to do is connect your GitHub account (the Gradescope submission page has a button for this) and select the repository and branch you wish to submit. Alternatively, you can create a zip file of the osv-w22 directory and upload that. The the arch, include and kernel directories from your submission will be used.

When you submit, the autograder will compile your code and run the test cases. The Gradescope autograder will run each test multiple times.

Although you are allowed submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their projects near the deadline, and thus it will Gradescope take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This lab will be graded out of 90 points, as shown in the table below. Comments explaining your approach can help earn partial credit if there are tests that don’t pass. Poor coding style can lose points, so make sure to submit clean, well-organized code.