1 of 27

CSE 451

Operating Systems

L7 - Concurrency: Processes and Threads - 2

​

​

Slides by: Tom Anderson

Baris Kasikci

2 of 27

Concurrency: Threads

  • Can multiple executions share the same address space?
    • Yes! The operating system kernel runs multiple processes on different cores
    • Yes! The operating system kernel can multiplex processes on one core
    • In each case, multiple system calls can be active at the same time
    • Also: interrupts, background tasks, system maintenance
  • Applications can also benefit from concurrency
    • Thread to handle user input
    • Thread to do operation user requested
  • Humans are not very good at keeping track of multiple things happening simultaneously

3 of 27

Definitions

  • A thread is a single execution sequence that represents a separately schedulable task
    • Single execution sequence: familiar programming model
    • Separately schedulable: OS can run or suspend a thread at any time
  • Protection is an orthogonal concept
    • Can have one or many threads per protection domain
    • Kernel itself has many threads

4 of 27

Multithreaded OS Kernel

5 of 27

Multithreaded User Processes

6 of 27

Process Thread Lifetime

7 of 27

Thread Operations

  • thread_create(thread, func, args)
    • Create a new thread to run func(args)
  • thread_yield()
    • Relinquish processor voluntarily
  • thread_join(thread)
    • In parent, wait for child thread to exit, then return
  • thread_exit
    • Quit thread and clean up, wake up joiner if any

8 of 27

Déjà vu?

  • Didn’t we learn all about concurrency in CSE 332/333?
    • More practice
      • Realistic examples, especially in the project
    • Design patterns and pitfalls
      • Methodology for writing correct concurrent code
    • Implementation
      • How do threads work at the machine level?
    • CPU scheduling
      • If multiple threads to run, which do we do first?

9 of 27

Thread Abstraction

  • Infinite number of processors
  • Threads execute with variable speed
  • Programs must be designed to work with any schedule

10 of 27

Question

Why do threads execute at variable speed?

11 of 27

Programmer vs. Processor View

12 of 27

Possible Executions

13 of 27

Example: threadHello

#define NTHREADS 10 thread_t threads[NTHREADS]; main() {

for (i = 0; i < NTHREADS; i++) thread_create(&threads[i], &go, i); for (i = 0; i < NTHREADS; i++) {

exitValue = thread_join(threads[i]);

printf("Thread %d returned with %ld\n", i, exitValue);

}

printf("Main thread done.\n");

}

void go (int n) {

printf("Hello from thread %d\n", n); thread_exit(100 + n);

// REACHED?

}

14 of 27

Implementing threads

  • thread_create(func, args)
    • Allocate thread control block
    • Allocate stack
    • Build stack frame for base of stack (stub)
    • Put func, args on stack
    • Put thread on ready list
    • Will run sometime later (maybe right away!)
  • stub(func, args):
    • Call (*func)(args)
    • If func returns, call thread_exit()

15 of 27

Thread Stack

  • What if a thread puts too many procedures on its stack?
    • What happens in Java?
    • What happens in the Linux kernel?
    • What happens in xk?
    • What should happen?

16 of 27

xk swtch (swtch.S)

swtch:

// callee saved registers already saved

// ptr to old PCB is in rdi push %rbp

push %rbx

push %r11

push %r12

push %r13

push %r14

push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

17 of 27

xk swtch (swtch.S): Switch from A -> B

swtch:

// callee saved registers already saved

// ptr to old PCB is in rdi

push %rbp

push %rbx

push %r11

push %r12

push %r13

push %r14

push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

Step 1: Save old thread’s preserved state (A)

18 of 27

xk swtch (swtch.S): Switch from A -> B

swtch:

// callee saved registers already saved

// ptr to old PCB is in rdi

push %rbp

push %rbx

push %r11

push %r12

push %r13

push %r14

push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

Step 2: Record A’s execution point

current stack pointer

destination register (memory field inside the TCB)

19 of 27

xk swtch (swtch.S): Switch from A -> B

swtch:

// callee saved registers already saved

// ptr to old PCB is in rdi

push %rbp

push %rbx

push %r11

push %r12

push %r13

push %r14

push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

Step 3: Switch to the new thread’s (B) stack

20 of 27

xk swtch (swtch.S): Switch from A -> B

swtch:

// callee saved registers already saved

// ptr to old PCB is in rdi

push %rbp

push %rbx

push %r11

push %r12

push %r13

push %r14

push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

Step 4: Restore B’s state and resume it

21 of 27

A Subtlety

  • Thread_create puts new thread on ready list
  • When it first runs, some thread calls swtch
    • Saves old thread state to stack
    • Restores new thread state from stack

=> Set up newly created thread so that swtch will ”resume” at start of

thread

22 of 27

Stack Progression

23 of 27

Why is there a stub at all?

  • F is an ordinary function that might return normally
    • No where sensible to go in that case!
  • With the stub, once F returns, stub calls thread_exit to cleanup

24 of 27

Why is there a stub at all?

  • When the scheduler switches to B:
    • swtch loads this thread’s saved stack pointer into %rsp
    • pops registers, executes ret.
  • ret uses the saved return address on this stack, which points to the stub.

25 of 27

What Happens After Switch?

26 of 27

Timer Interrupt -> swtch

27 of 27

Two Threads Call Yield