Operating Systems Lecture Notes

2014 September 11 • Threads

---

Outline

• Threads and the thread abstraction.
• Threads and processes.
• Thread resources.
• Thread management.
• The Thread-Process Split.

Executing Programs

• A program

  int find(a, x)
    i = a.length
    while --i > -1
      if a[i] == x, break
    return i
  

• in execution is a sequence of instructions.

  	     i = a.length; --i > -1; a[i] == x; ...
  

Threads

• A thread is responsible for executing a program statement sequence.
• A thread
  • is an OS resource.
  • is an abstract or virtual CPU.
  • multiplexes the CPU.
• A thread is a sequence of executed statements from a program.

The Thread Abstraction

• A computation has active and passive parts.
• A process is a resource set; it’s passive.

  A thread is the active part of a computation. A computation is one or more threads in a process. At least one thread, the main() thread.

Threads and Processes

• A thead executes, a process doesn’t. Why the split?
• A thread is a handy abstraction of the CPU.
  • Decouple actual and the conceptual processing power.
• A process is an expensive, complex, inflexible abstraction.
• But, in some (threadless) OS abstractions, processes execute too.

Thread Resources

• What resources does a thread need to execute?
  • The CPU.
• What else?
  • Execution state: program counter, registers, run-time stack.
  • Process information: the host process, other threads in the host process.

Single- and Multi-Threading

Thread Descriptors

• Thread resources are stored in a thread descriptor.
  • Similar to a process descriptor.
• Each thread gets its own thread descriptor.
  • Thread resources aren’t usually shared among threads.
• Thread descriptors are stored in the computation’s process.
  • Similar to a process table.

Process Resources

• A thread executing in a process has access to the process’s resources.
  • The resources are shared among all threads executing in the process.
  • Raising the specter of contentious access to shared resources.
• A thread usually doesn’t have access to another thread’s resources.

Sharing Example

	Shared resources are usually declared as global variables in the program.
	buffer b p() {... b.put() ...} c() {... b.get() ...} main {... fork(p) fork(c) ...}

Thread Management

• Thread management consists of
  • Creating and deleting threads.
  • Managing thread resources and descriptors.
  • Coordinating thread access to shared resources.
  • Moving threads into and out of the CPU.
    • This is mainly the scheduler’s job.

Thread Create and Delete

• Traditionally called fork (or spawn) and join.

  int pthread_create(
    thread id,         out to caller
    thread attributes, stack, priority, ...
    thread function,   statements
    thread arguments)  to the function
  
  void pthread_exit(result)
  
  int pthread_join(
    thread id,
    result)

• See the code.

Fork-Join Example

Java Threads

• Java threads have two parts:
  • The JavaApiRef(lang, Runnable) interface gives the code.
  • The JavaApiRef(lang, Thread) class executes the Runnable code.

  class P implements Runnable { ... }
  class C implements Runnable { ... }
  main()
    Queue q = new Queue()
    Thread p = new Thread(new P(q))
    Thread c = new Thread(new C(q))
    p.run() ; c.run()
    p.join() ; c.join()
  

• See the code.

The Thread-Process Split

• Managing processes is much harder than managing threads.
  • The complexity of the data involved.
  • The complexity of the operations involved.
  • The amount of state to wrangle.
• Avoid managing process in favor of threads.
  • The origin of heavyweight vs. lightweight processes.

Some Process Code

switch pid = fork()

  case 0
    execve("null-process")

  case -1
    // fork() failed

  default
    const pid_t p = wait()
    if (p == -1)
      // wait() failed

    if (p != pid)
      // unexpected pid from wait() 

Some Thread Code

s = pthread_create(&tid, NULL, null_thread, NULL);
if (s != 0)
  // pthread_create() failed

s = pthread_join(tid, NULL)
if (s != 0)
  // pthread_join() failed

void * null_thread(void *)
  pthread_exit(NULL)

Some Data

• Repeatedly fork threads and processes that do nothing but return.

  	avg, std dev
  		threads		processes
  n = 100		123, 158		1730, 180
  n = 1000		77, 41		1590, 321

• Times in \(\mu\)secs.
• The average of n runs.
• Unoptimized complilation with g++ v. 3.4.6.
• Execution on rockhopper.
• See the code.

Implementing Threads

• Threads have far fewer resources than do processes.
  • Registers, stack space, thread-local data.
    • There may be other state.
• Thread resources are small.
  • Cheap to create, cheap to hold.
• CPU \(\leftrightarrow\) thread resource transfer is small and fast.

Threads Outside the OS

• Every thread implementation keeps some resources outside the OS.
  • Why there can be so many threads.
• Some thread implementations are all outside the OS.
  • A fun problem, but not too practical.
• Most other implementations are split between in and out of the OS.

User-Space Threads

• User-space threads are implemented completely outside the OS.
  • Access to registers via assembly or libraries.

    #include <setjmp.h>
    
    int setjmp(jmp_buf env)
    void longjmp(jmp_buf env, int val)
    

  • setjmp() takes a location snapshot.
  • longjmp() jumps to a location snapshot.

OS-Based Threads

• Most modern OSs have kernel threads implemented entirely the OS.
• Similar to, to simpler than user-space-based threads.
  • No protection boundaries, fewer resources to wrangle.
• The OS can use kernel threads.
• And kernel threads can be used to implement user-space threads.

User and Kernel Threads

• User threads are mapped to kernel threads.
  • Kernel threads can be mapped to CPUs or cores.
• A kernel thread manages user threads.
  • User-thread create and delete.
  • User-thread context switches.
  • Scheduling

One-to-One Mappings

• Responsive user threads. Higher (user + kernel) overhead. Kernel restrictions dominate.

Many-to-One Mappings

• Sharing kernel resources among user threads. Lower overhead. Kernel restrictions less important. Kernel-thread effects dominate. Blocking in particular.

Many-to-Many Mappings

• Great on multiprocessors and multicore systems. Lower overhead, but complex mapping. Kernel restrictions less important. Kernel-thread effects can be circumvented. At increased complexity.

Summary

• Threads abstract (or virtualize, or multiplex) the CPU.
  • And represent statement sequence executions from a program.
• All threads share a host process’s resources.
  • And each thread has unsharable resources of its own.
• Threads vs processes: performance vs protection.

References

• Why Threads Are A Bad Idea (for most purposes) by John Ousterhout, Usenix Annual Technical Conference, January 1996.
• SEDA: An Architecture for Well-Conditioned, Scalable Internet Services by Matt Welsh, David Culler, and Eric Brewer, Eighteenth Annual Symposium on Operating System Principles, 2001.
• Why Events Are A Bad Idea (for high-concurrency servers) by Rob von Behren, Jeremy Condit and Eric Brewer, 9th Workshop on Hot Topics in Operating Systems, May, 2003.

---

This page last modified on 2012 February 6.