For full credit on problem set 5, you must complete Part A (threads). For extra credit, complete Part B (a student-chosen project).
Due Wednesday, May 6
Before submitting, fill out
psets/pset5collab.md with collaboration
information; if you do an extra-credit project, also fill out
psets/pset5project.md with a brief project writeup.
Implement multithreaded processes: processes that can have multiple
independent threads of control, but that share the same virtual memory space
and file descriptor table. Use kernel threads, the design where
every user-visible “thread” corresponds to a
You’ll add three system calls:
- The new
sys_clonesystem call starts a new thread in the current process. See below for more on
- The new
sys_gettidsystem call returns the current thread’s thread ID. Different threads in a process have different
sys_gettids, but the same
sys_getpid. Note that the process ID returned by
sys_getpidneed not equal any of the
sys_gettids for that process’s threads!
- The new
sys_texitsystem call exits the current thread. When the last thread in a process exits,
sys_exit; otherwise, the process just continues with one fewer thread.
And change some existing ones:
sys_exitexits all threads in the current process.
sys_waitpidwaits for processes, not threads (in other words,
sys_waitpid(p)waits for all the threads of
sys_forkshould clone only the calling thread.
- You may assume that
sys_execvis called only by single-threaded processes.
make run-testthread to check your work.
Process IDs and thread IDs
Kernel threading introduces a distinction between process and thread IDs:
every user task has one of each, and they may not be equal.
allocate one of each.
We recommend storing the thread ID in
proc::id_. This may feel backwards
but it’s just easier to keep
ptable indexed by
id_. Add a new member, such
proc::pid_, to store the true process ID; and add a table, such as
pidtable[NPROC], to store processes by true PID.
(For what it’s worth, Linux does the same thing. Its
is a thread ID, while the true process ID is called a “thread group ID” and
getpid system call returns
Your goal is for
sys_clone(function, arg, stack_top) to set up a new thread
function(arg) on the given stack, where when that function returns,
the thread exits via
sys_texit. This means the initial thread stack frame
should contain a return address pointing to
packages typically divide responsibility for this between the kernel’s system
call and user-level code in the system call wrapper; most typically the stack
setup is left to wrapper code.
Some examples from real operating systems:
In Linux, the
clonesystem call takes several arguments, but none of those arguments correspond to
arg, and the
stack_topargument doesn’t actually change the active stack pointer (it is recorded in the kernel for later use). Linux
clone’s return value resembles that of
fork: it is 0 in the new thread and the new thread’s ID in the original thread. User-level wrapper code examines the return value and modifies the stack as appropriate. In a Linux-like Chickadee design, the
sys_clonesystem call would take no arguments.
clonemanual page; uClibc’s
cloneimplementation (documented); musl libc’s
cloneimplementation (undocumented, but more compact).
In FreeBSD, the
thr_newsystem call does take arguments resembling
stack_top. However, when used in a threading library, the wrapper code still adds a layer of indirection so that the
sys_texitequivalent is called when the thread function returns.
The key hurdles with implementing the
sys_clonewrapper function are saving the arguments until they can be used—which is generally after the clone system call returns—and wrangling assembly.
One way forward is to write the
sys_clonewrapper function entirely in assembly. Create a new
u-clone.Sfile and add
PROCESS_LIB_OBJS. You’ll want to use the C++ mangled name for
sys_clone, which is likely
sys_clone, taking arguments with types
char*”). Your assembly file might look like this:
#include "obj/u-asm.h" .text .globl _Z9sys_clonePFiPvES_Pc _Z9sys_clonePFiPvES_Pc: # ... your code here ...
Another way is to use GCC inline assembly (reference, useful overview), the GCC extension that lets you integrate assembly with C++ code. This is how the existing wrappers are written. Some tips on wrangling inline assembly:
- Use syntax like
callq *%%raxto call a function whose address is stored in
%rax. (In inline assembly, as in
printf, the double
%means a literal percent character.)
- An input register constraint like
"i" (SYSCALL_TEXIT)may be required to pass a numeric constant as a parameter, since the normal constraints like
"r"do not always work for constants.
Either method will need to store arguments across the
syscallinstruction. It’s possible to store the arguments in places including the calling thread’s stack and the system’s callee-saved registers (
%r12-%r15). If you choose registers and inline assembly, you’ll likely need this style of declaration to force the compiler to use specific registers:
register uintptr_t x asm("r12") = reinterpret_cast<uintptr_t>(arg); // i.e., C++ variable `x` is stored in register `%r12`
Explain your synchronization plan for parts of process state that can now be
shared by multiple tasks, especially
pagetable_ and your file descriptor
Process exit is a special issue for multithreaded processes. The
system call should exit all of the process’s threads, not just the calling
thread. But the process’s other threads might be blocked in the kernel or
running on other CPUs! The threads’ memory and
struct procs cannot be
deleted until they have all stopped running. You’ll want to mark the threads
as “exiting,” wait for them to stop running, and only then tear down the
process as a whole. This will use some of the same techniques you used in
problem set 2, part G (system call
interruption). The later parts of
p-testthread.cc check interactions between
B. Project (Optional)
For extra credit, design and implement a project of your choice which adds a new feature to your operating system! Check with the course staff to make sure that your project ideas are in scope. Extra credit will be assigned as a number of additional percentage points to add to your total percentage points in the class. The maximum number of extra credit percentage points will be 7. For example, at the end of the class, if your final percentage points total (when considering midterms, projects, and participation) was 83%, your final total could be boosted to a maximum of 90%.
Describe your project in a file
psets/pset5project.md that you add to your
repository. Your writeup should answer these questions:
- What was your goal?
- What’s your design?
- What code did you write (what files and functions)?
- What challenges did you encounter?
- How can we test your work?
The writeup need not be very long; 300 words can do it if you use the words well.
The course staff believe that the following project ideas are very doable by the due date for the project:
More visualizations. Can you create console visualizations for other aspects of the problem sets than virtual memory? For example, can you create a visualization for the disk or VFS?
Performance optimization and stress tests. Create a thorough and comprehensive test suite, a stress test plan, and/or a performance benchmark, then improve your operating system until it is amazing.
Support for kernel introspection via a
/proc-like file system.
File system symbolic link support, device support (e.g., /dev/null, /dev/zero), mount support, etc.
More ambitious ideas include:
Networking support. Implement device support for networking, then link that device to a networking stack, such as lwIP or picoTCP.
You may be interested in a networking project from MIT’s 6.828 class; though that class uses 32-bit x86 rather than 64-bit x86-64, network device handling support should be similar.
Graphics support. Implement a fancier graphics mode. Maybe port a game!
Debugging support. Can you make DWARF debugging information, or some other kind of debugging information, available in the kernel? This might let you print line numbers in backtraces!
Dynamic linking support.
psets/pset5collab.md and push to
GitHub. Then submit on the grading server.
Checkin: All work is due by 11:59pm Wednesday 5/6.