Content

1. Threads and Processes
2. Thread Scheduling

Threads and Processes

• When a program runs, it is called a process
• OS maintains states for each abstraction:
  • Thread(CPU) state
    • Registers, PC, SP, ...
  • Address Space (memory) state
    • Program instructions, static & dynamic data, ...
  • Device & other state
    • Open files, network connection state, ...

Threads

• Abstraction of virtualizing CPU
  • Each thread thinks it has its own set of CPU registers

• of threads arbitrary; # of CPUs fixed

• Enables concurrency

  • Running multiple programs concurrently
  • Running multiple tasks concurrently
    • Hiding I/O latency
      • Can use non-blocking file I/O (event-driven), but harder to get right because need to build a state machine
      • ~ interrupts
    • Run truly in parallel with multiple CPUs via multiplexing

• Threads v.s. Functions

  | Threads | Functions | |:--------|:----------| | Independent streams of execution, one thread no need to run to the end before switching | LIFO policy, functions runs untill the end | | Thread scheduler multiplexes the threads on CPU | One function calls another function | | Each thread has its own stack, calling its own set of functions | Running on a single stack | | Runs in parallel with multiprocessors | Cannot run in parallel with multiprocessors because functions stack together |

Address Space

• Abstraction of virtualizing memory
  • A set of virtual memory regions accessible to a program
    • Text: program code
    • Data, Heap: static, dynamic variables
    • Stack: for function & system calls
• Provides memory protection

• Address space (order may vary with different H/W & compiler environment)

            +++++++++++++++   ----
            |    param    |     |
            +++++++++++++++     |
            |   ret val   |     |
            +++++++++++++++     |
            |   ret addr  |     |    activation frame
            +++++++++++++++     |    for current function
      fp -> |   prev fp   |     |
            +++++++++++++++     |
            |  other regs |     |
            +++++++++++++++     |
      sp -> |  local var  |     |      # function call:
            +++++++++++++++   ----       # push %rbp; save old fp
            |      ↓      |              # mov %rbp %rsp; init sp to fp
            |             |              # retq; call *sp
            |      ↑      |
            +++++++++++++++            # return:
            |    data     |              # add $24 %rsp; pop off stack
            +++++++++++++++              # pop %rbp; fp=*sp (or *fp), sp++
            |    text     |              # retq; call *sp
            +++++++++++++++
  

Processes

• A running program consistes of >= 1 processes
  • Traditionally:
    • process = addr space + thread
    • Threads communicate using system calls
  • Today:
    • process = addr space + >= 1 threads
    • Threads share addr space (but not stack)
    • Threads communicate with reading/writing memory

• Speed up cases analysis:

    # Vector operation
    for (k = 0; k < n; k++)
        a[k] = b[k]*c[k] + d[k]*e[k];
  

  • Multiple processes?
    • Communicate with system call...
  • Multiple threads?
    • Must make it global to share data
  • On single processor?
    • Threads go one after another

  • On multiprocessor?

    • O

    # Web server
    Loop:
      1. get network message from client -> I/O
      2. get URL data form disk, cache in memory -> I/O
      3. compose response
      4. send response -> I/O
    

  • Multiple processes?

    • Cannot share the cache (stored in global resource area of that process)
  • Multiple threads?
    • O
  • On single processor?
    • O
  • On multiprocessor?
    • O

• Threads v.s. Processes

  | | Threads | Processes | |:--|:--------|:----------| | Memory needed| Shared, less | Not shared, more | | Communication & Synchronization | Via shared vars, faster | Via system calls, slower | | Switching | Save & restore regs, faster | Change MMU's regs (e.g. base & limit), slower | | Robustness | Memory sharing -> bugs | Communication explicit -> robust |

• Program v.s. Process

  • Program: a set of instructions & data
  • Process: a program loaded in memory and executing

OS-Level Process State

• OS keeps state for each process: process state, process control block (PCB)
  • Thread state
    • Processor regs for resuming/suspending thread
    • Thread id
    • Various parameters e.g. scheduling parameters
  • Address space state
    • Location of text, data, stack
    • MMU virtual memory state i.e. virtual -> physical mapping
  • Device related state
    • Open files, network connections
  • Other states
    • Terminal state, pending signals, timers, swap, ...

Thread Scheduling

• Thread: an independent stream of instructions
  • Which to choose?
  • When to switch?
  • How to switch?
• Thread scheduling: running threads in some order
  • Thread state
    • Running
    • Ready
    • Blocked
    • Exited (not yet destroyed)
  • Scheduling policies to change states
• Thread scheduling functions
  • thread_yield
    • Running -> Ready
  • thread_sleep
    • Running -> Blocked
  • thread_wakeup
    • Blocked -> Ready
• Preemptive scheduling
  • Scheduler uses timer interrupt to control threads
  • Interrupt handler calls yield on behalf of running thread
    • Normally interrupt handler returns to original call; here, it calls thread_yield() instead
• Scheduler implementation
  • Thread structures maintained in queues
    • Ready queue
      • Generally 1 per CPU
    • Wait queue
      • Separate wait queues for each type of event e.g. disk, console, timer, network, ...
      • Generally shared by CPUs
    • Exited queue
      • Generally shared by CPUs
  • Scheduling functions move threads between queues

Thread & Context Switch

• context switch (process switch) = thread switch + address space switch

  • Address space switch
    • Updating MMU's registers
    • More expensive than thread switch
  • Context switch v.s. Mode switch
    • Unrelated; the former switch threads, the latter switch CPU modes

• Functions

  • thread_yield

      thread_yield() {
          enqueue_ready_queue(current)
          next = choose_next_thread()
          thread_switch(current, next)
      }
      thread_switch(current, next) {
          save_processor_state(current->cpu_regs)
          ...
          restore_processor_state(next->cpu_regs)
      }
    

  • thread_init
    • Create the first (main) thread
  • thread_create
    • Allocate thread struct, stack memory, init PC, SP
    • Add to ready queue

Thread Creation & Termination

• Functions
  • thread_exit
    • Does not destroy itself; switch to another thread and it will destroy this thread
  • thread_destroy
    • Actually destroy thread structure & stack of exited threads

Kernel Threads v.s. User Threads

• Kernel level scheduler doesn't know about user threads

Quick Questions

1. Is the OS code run in a separate process? A separate thread? Does it need a process structure?
   • OS code runs when a process makes a system call or when an interrupt occurs. In either case, the OS generally runs in the thread and address space context of the user process, and hence it does not require its own process or thread state.
2. What is the address space of an OS?
   • The entire physical memory

Related Articles

• Thread Switching v.s. Process Switching