Deadlines

• Tell me partners: due Wednesday, January 17th, at 10:00pm

• Design document: due Friday, January 19th, at 10:00pm (post on a “design pod” channel on Slack)

• Peer feedback: due Monday, January 22nd, at 10:00pm (again as a post on Slack)

• Code implementation: due Monday, January 29th, at 10:00pm (on Gradescope)

Introduction

In this assignment, you will add to osv some more system calls, this time for process management.

Goals

Your task is to implement the UNIX-based system calls for fork, wait, and exit:

• 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 that process

Collaboration policy

For this and most other assignments, you are encouraged to talk at a high level with your classmates. However, any low-level discussions (e.g., that involve actual code instead of ideas) should be with at most one other student in the class.

See our class collaboration policy for more information.

Getting started

Pull any changes to the baseline code by running

git pull upstream main

and merging. If you have any issues with this, please let me know!

After the merge, double check that your code still passes the Lab Assignment #1 tests.

Writing design documents

Starting with this lab, I will ask you to write a small design document. Note that Lab Assignment #2 will have many design decisions to be made, and planning now will help prevent time-consuming issues from arising later.

• You will be 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 Friday 1/19 at 10pm.

• You have been grouped with other students 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 is due Monday 1/22 at 10pm.

  • 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.

Below are two Markdown files, one that was used for Lab Assignment #1, and a template for one for this lab. (Note that GitHub nicely renders Markdown documents in your repo.) However, you are free to write your design document in whatever format you wish, as long as you can post it nicely to Slack.

• Lab Assignment #1 design document: raw Markdown file

• Lab Assignment #2 design document: rendered template and raw Markdown file

Background

The fork, wait, and exit system calls

These system calls work together as a unit to support multiprocessing. In osv, calling fork should duplicate the state of the user-level application. As in UNIX, the system call fork returns twice:

1. once in the parent, with the return value of the process ID (pid) of the child, and
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 are not visible to the parent, and
• any changes in the parent’s memory after fork are not visible to the child.

The exit system call takes in a status, which is the exit status of the process. This value may be provided to its parent in wait. The exit call also releases any kernel resources given to the process and performs other cleanup (e.g., the open file table).

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

Process scheduling

Once a new process is created, it will be run concurrently via the process scheduler. A hardware device generates a timer interrupt on fixed intervals.

If another process/thread is READY (for osv, look up the enum threadstate_t), the scheduler will switch to it, essentially causing the current process to yield to the CPU.

In osv

I have added an osv overview page that you may find helpful in your planning.

Design guidance

As you think through your design, keep the following in mind.

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).

The function ptable_dump (in proc.c) can be used for debugging; it 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.

Where to start

The actual system call sys_fork is already implemented; it just calls into a function proc_fork in kernel/proc.c. You’ll need to start here. Keep in mind, though, that one of the first tests will have the process process call exit.

You’ll also need to implement the system calls for exit and wait, as described below.

The reference solution for this lab assignment made changes to:

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

Synchronization between a parent and child process

The exit status provided to exit needs to be saved somewhere (even though the resources for the exiting process are being released), as its parent may 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.

On process creation, the kernel gives each process:

• an address space,
• a kernel thread, and
• a process struct.

All of these need to be cleaned up, plus any other information tracked by the process struct (like your file-descriptor table).

Note that osv will take 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 communication your exit status back to the parent process. This communication can be tricky. Let’s say that you decide to store the exit status in a struct A (this can be the 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 parent may call wait to block until a child exits. Note that a parent can:

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

You’ll again need to be careful with synchronization. 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 waited-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 (you can’t just rely on wait to trigger this).

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 relcima the childrens’ data when the parent exits first. (Note that in osv as in UNIX, the initial (user/init.c) process never exits, meaning that an exiting process could “hand off” its children to this process.)

In short, you need to think through these cases:

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

Implementation

Implement exit and wait, in addition to the functionality needed for fork.

You’ll need to complete proc_fork in kernel/proc.c:

/* Fork a new process identical to current process */
struct proc* proc_fork();

For exit and wait, you’ll need to complete the system calls (sys_exit and sys_wait in kernel/syscall.c) and the underlying functions proc_exit and proc_wait in kernel/proc.c:

/*
 * Corresponds to void exit(int status);
 * 
 * Terminate the calling process (e.g., halt it and reclaim its resources).
 * 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 changes state (e.g., terminates).
 *
 * 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:
 * On success, the PID of the child process that changed state.
 * On failure:
 *   ERR_FAULT - Address of wstatus is invalid.
 *   ERR_CHILD - The caller does not have a child with the specified pid.
 */
sysret_t
sys_wait(void *arg);

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

/*
 * Wait for a process to change state (e.g., terminate).
 * 
 * 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:
 * On success, the pid of the child process that changed state.
 * On failure:
 *   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 your Lab Assignment #2 code by either running individual tests in the 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 of 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.

Debugging

When debugging, I would recommend running individual tests in osv. Note that 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.

Hints

Here are some things to keep in mind:

• Accessing memory after deallocation can result in reading 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).

  • Note: 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 print statements, so you can follow which processes are calling various functions.

• Leave the fork-tree and race-test tests for last, as these are the most complex with many concurrent processes.

• FAQ

What to turn in

You will submit your work for this assignment via Gradescope.

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

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 to submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their assignments near the deadline, and thus Gradescope will take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This assignment will be graded out of 100 points, with 90 points coming from the tests shown in the table below. Comments explaining your approach can help earn partial credit if there are tests that don’t pass. The remaining 10 points are based on coding style, so make sure to submit clean, well-organized code.