CS350: Operating Systems

Lecture 3: Threads

Ali Mashtizadeh

University of Waterloo

1 / 26
 Today: Threads

emacs

Process Threads Locks File I/O

Operating System

Hardware: CPU, Memory and Devices

2 / 26
 Outline

1 Threads

2 Case Study: Go Language and Runtime

3 How to implement threads in OS/161

3 / 26
 Threads

• A thread is a schedulable execution context

I Program counter, registers, stack (local variables) …
• Multi-threaded programs share the address space (global variables, heap, …)
4 / 26
 Why threads?

• Most popular abstraction for concurrency

I Lighter-weight abstraction than processes
I All threads in one process share memory, file descriptors, etc.
• Allows one process to use multiple CPUs or cores
• Allows program to overlap I/O and computation
I Same benefit as OS running emacs & gcc simultaneously
I E.g., threaded web server services clients simultaneously:
for (;;) {
fd = accept_client ();
thread_create (service_client, &fd);
}
• Most kernels have threads, too
I Typically at least one kernel thread for every process
5 / 26
 POSIX thread API

• int pthread_create (pthread_t *thr, pthread_attr_t *attr,

void *(*fn)(void *), void *arg);
I Create a new thread identified by thr with optional attributes, run fn with arg
• void pthread_exit(void *return_value);
I Destroy current thread and return a pointer
• int pthread_join(pthread_t thread, void **return_value);
I Wait for thread thread to exit and receive the return value
• void pthread_yield();
I Tell the OS scheduler to run another thread or process
• Plus lots of support for synchronization (next Lecture and see [Birell])

6 / 26
 Kernel threads

• Can implement pthread_create as a system call

• To add pthread_create to an OS:
I Start with process abstraction in kernel
I pthread_create like process creation with features stripped out
. Keep same address space, file table, etc., in new process
. rfork/clone syscalls actually allow individual control

• Faster than a process, but still very heavy weight

7 / 26
 Limitations of kernel-level threads

• Every thread operation must go through kernel

I create, exit, join, synchronize, or switch for any reason
I Syscall takes 100 cycles, function call 2 cycles
I Result: threads 10×–30× slower when implemented in kernel
I Worse today because of SPECTRE/Meltdown mitigations
• One-size fits all thread implementation
I Kernel threads must please all people
I Maybe pay for fancy features (priority, etc.) you don’t need
• General heavy-weight memory requirements
I E.g., requires a fixed-size stack within kernel
I Other data structures designed for heavier-weight processes

8 / 26
 User threads

• An alternative: implement in user-level library

I One kernel thread per process
I pthread_create, pthread_exit, etc., just library functions

9 / 26
 Implementing user-level threads

• Allocate a new stack for each pthread_create

• Keep a queue of runnable threads
• Replace blocking system calls (read/write/etc.)
I If operation would block, switch and run different thread
• Schedule periodic timer signal (setitimer)
I Switch to another thread on timer signals (preemption)
• Multi-threaded web server example
I Thread calls read to get data from remote web browser
I “Fake” read function makes read syscall in non-blocking mode
I No data? schedule another thread
I On timer or when idle check which connections have new data

10 / 26
 Limitations of user-level threads

• Can’t take advantage of multiple CPUs or cores

• A blocking system call blocks all threads
I Can replace read to handle network connections
I But usually OSes don’t let you do this for disk
I So one uncached disk read blocks all threads
• A page fault blocks all threads
• Possible deadlock if one thread blocks on another
I May block entire process and make no progress
I [More on deadlock in future lectures.]

11 / 26
 User threads on kernel threads

• User threads implemented on kernel threads

I Multiple kernel-level threads per process
I thread_create, thread_exit still library functions as before
• Sometimes called n : m threading
I Have n user threads per m kernel threads
(Simple user-level threads are n : 1, kernel threads 1 : 1)
12 / 26
 Limitations of n : m threading
• Many of same problems as n : 1 threads
I Blocked threads, deadlock, …

• Hard to keep same # ktrheads as available CPUs

I Kernel knows how many CPUs available
I Kernel knows which kernel-level threads are blocked
I Tries to hide these things from applications for
transparency
I User-level thread scheduler might think a thread is
running while underlying kernel thread is blocked

• Kernel doesn’t know relative importance of threads

I Might preempt kthread in which library holds
important lock
13 / 26
 Lessons

• Threads best implemented as a library

I But kernel threads not best interface on which to do this
• Better kernel interfaces have been suggested
I See Scheduler Activations [Anderson et al.]
I Maybe too complex to implement on existing OSes (some have added then
removed such features, now Windows is trying it)
• Today shouldn’t dissuade you from using threads
I Standard user or kernel threads are fine for most purposes
I Use kernel threads if I/O concurrency main goal
I Use n : m threads for highly concurrent (e.g,. scientific applications) with many
thread switches
• …though concurrency/synchronization lectures may
I Concurrency greatly increases the complexity of a program!
I Leads to all kinds of nasty race conditions
14 / 26
 Outline

1 Threads

2 Case Study: Go Language and Runtime

3 How to implement threads in OS/161

15 / 26
 Go Routines

• Go routines are very light-weight

I Running 100k go routines is practical
I Custom compiler enables stack segmentation, preemption, and garbage collection
I Runs on segmented stack – stack allocated on demand to avoid memory use
I OS thread typically allocate 2 MiB fixed stacks

• Go routines on top of Kernel threads (n:m Model)

I Multi-core scalability and efficient user-level threads
I One pthread (kernel-level thread) per CPU core
I Supports many user-level threads as you like

16 / 26
 Go Routine Continued

• Each kernel-level thread finds and runs a go routine (user-level thread)

• Every logical core is owned by a kernel thread when running

• Convert blocking system calls (when possible):

I Converted to non-blocking by in the runtime yielding the CPU to another core
I Cores poll using kernel event API poll, epoll, or kqueue
• Blocking system calls:
I Release the ”CPU” to another kernel-level thread before the call
I Let the kernel thread sleep
I Regain the ”CPU” thread when done

17 / 26
 Go Channels

• Go routine communicate and synchronize through channels

func worker(done chan bool) {
// Notify the main routine
done <- true
}

func main() {
// Create a channel to notify us
done := make(chan bool, 1)

// Create go routine
go worker(done)

// Block until we receive a message

<-done
}
18 / 26
 Outline

1 Threads

2 Case Study: Go Language and Runtime

3 How to implement threads in OS/161

19 / 26
 Background: MIPS calling conventions
• Registers divided into 2 groups
I Functions free to clobber caller-saved regs Call
(%t0–%t9 on MIPS) arguments
I But must restore callee-saved ones to original value
return addr
upon return (%s0–%s7, %fp)
old frame ptr
• %sp register always base of stack fp
callee-saved
I Frame pointer (%fp) is old %sp
registers
• Local variables stored in registers and on stack
Local vars
• Function arguments go in caller-saved regs and and temps
on stack sp
I First four arguments in %a0–%a3
I Remaining arguments on stack
• Return value %v0 and %v1
20 / 26
 Background: procedure calls

• Some state saved on stack

I Return address, caller-saved registers
• Some state not saved
I Callee-saved regs, global variables, stack pointer
21 / 26
 Threads vs. procedures

• Threads may resume out of order:

I Cannot use LIFO stack to save state
I General solution: one stack per thread
• Threads switch less often:
I Don’t partition registers (why?)
• Threads can be involuntarily interrupted:
I Synchronous: procedure call can use compiler to save state
I Asynchronous: thread switch code saves all registers
• More than one than one thread can run at a time:
I Procedure call scheduling obvious: Run called procedure
I Thread scheduling: What to run next and on which CPU?

22 / 26
 OS/161 Kernel Threads

• OS/161 supports fork, exec, exit, and wait

I You will implement these functions in Assignments 2a/2b
• One thread per process
int thread_fork(const char *name,
struct proc *proc,
void (*entrypoint)(void *data1, unsigned long data2),
void *data1, unsigned long data2);
• OS/161 supports kernel threads (no user-level threading)
• Create a kernel thread with: thread_fork()
• Bad nameing: Not fork() this is actually pthread_create!

23 / 26
 Switching Threads

• All thread switches go through thread_yield() and thread_switch()

• thread_switch() calls switchframe_switch generates switchframe
• switchframe_switch switches from one stack to other

General (from Kernel) Hardware Interrupt (typically Timer)

...

struct trapframe
...
trap()
thread_yield()
interrupt handler
thread_switch()
thread_yield()
switchframe
thread_switch()
...
struct switchframe

...

24 / 26
 OS/161 switchframe_switch – save old thread

From OS/161 kern/arch/mips/thread/switch.S

1 switchframe_switch:
2 /* a0: switchframe pointer to old thread */
3 /* a1: switchframe pointer to new thread */
4 /* Allocate space for saving 10 registers. 10*4 = 40 */
5 addi sp, sp, -40
6
7 sw ra, 36(sp) /* Save callee save registers */
8 sw gp, 32(sp) /* Caller saved registers saved by thread_switch() */
9 sw s8, 28(sp)
10 sw s6, 24(sp)
11 sw s5, 20(sp)
12 sw s4, 16(sp)
13 sw s3, 12(sp)
14 sw s2, 8(sp)
15 sw s1, 4(sp)
16 sw s0, 0(sp)
17
18 /* Store the old stack pointer in the old thread */
19 sw sp, 0(a0) 25 / 26
 OS/161 switchframe_switch – restore new thread

1 /* Get the new stack pointer from the new thread */

2 lw sp, 0(a1)
3 nop /* Delay slot for load */
4
5 lw s0, 0(sp) /* Now, restore callee saved registers */
6 lw s1, 4(sp) /* Caller saved registers restored by thread_switch() */
7 lw s2, 8(sp)
8 lw s3, 12(sp)
9 lw s4, 16(sp)
10 lw s5, 20(sp)
11 lw s6, 24(sp)
12 lw s8, 28(sp)
13 lw gp, 32(sp)
14 lw ra, 36(sp)
15 nop /* Delay slot for load */
16
17 j ra /* jump register to return address. */
18 addi sp, sp, 40 /* Fix sp in delay slot for j */

26 / 26