Problem set 5: Threads and a Student-chosen Project

A. Threads

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 struct proc.

You’ll add three system calls:

You'll need to update some existing system calls:

Run 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. fork must 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 as proc::pid_, to store the true process ID; and add a table, such as proc* pidtable[NPROC], to store processes by true PID.

[For what it’s worth, Linux does the same thing. Its task_struct::pid member is a thread ID, while the true process ID is called a “thread group ID” and stored in task_struct::tgid; Linux’s getpid system call returns tgid and its gettid returns pid. ¯\_(ツ)_/¯]

sys_clone interface

Your goal is for sys_clone(function, arg, stack_top) to set up a new thread running 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 sys_texit. Multithreading 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:

Synchronization

In psets/pset5answers.md, explain your synchronization plan for the parts of a process's state that can now be shared by multiple tasks. Pay special attention to pagetable_ and the file descriptor table.

Exiting

Process exit is a special issue for multithreaded processes. The sys_exit 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 sys_exit and sys_texit.

B. Student-chosen Project

For this part, you should design and implement a project of your choice which adds a new feature to your operating system! Once you have an initial idea, check with the course staff to make sure that your idea is in scope and isn't too hard or too easy.

Describe your project in a file psets/pset5project.md that you add to your repository. Your writeup should answer these questions:

  1. What was your goal?
  2. What’s your design?
  3. What code did you write (what files and functions)?
  4. What challenges did you encounter?
  5. 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 ambitious ideas include:

Turnin

Fill out psets/pset5collab.md and psets/pset5answers.md. Also place an overview of your student-chosen project in psets/pset5project.md. Push to GitHub and then submit on the grading server.

Checkin: All work is due by 11:59pm Wednesday 5/5.