Lab: Multithreading

Uthread: switching between threads (moderate)

This task is very similar to scheduling different processes in xv6 kernel:

1. User thread yield the CPU ↔ One process yield CPU in its kernel thread: yield()
2. User threads and xv6 processes all have to store their own running context: proc->context, cpu->context
3. Switching threads and processes both require storing and loading registers: kernel/swtch.S

Note:

• When the process creates a thread, it will store its starting address to ra in context. During the (fake) switch, a ret instruction will jump to the beginning of thread functions.
• Every thread has its own stack. We need to save sp in context in advance and change it to the right address after switching.
• User stacks grow downwards!
• code

Using threads (moderate)

We have to add locks to preserve concurrent reading and writing to a simple hash table.

• Add a single lock to the hash table. Every operation need to acquire and release the lock. → Each thread have to wait other threads to finish visiting the hash table. They seems to run sequentially, so there’s no performance benefit by using multiple threads.
• Assign one lock to each bucket. Every operation only reads or modifies the linked list in one bucket. We can only locks one element in the table entries. → Threads visiting different entries can actually run in parallel.
• code

Barrier (moderate)

A point in an application at which all participating threads must wait until all other participating threads reach that point too. Here are my thoughts:

1. bstate.round represents which barrier the farthest thread is on or will be on. Besides, every thread will know the number of its own current barrier.
2. bstate.nthread represents the number threads blocked on the bstate.round, not the number threads being blocked.