What Is Threads ?

Cooperating Processes

1. Last time we discussed how processes can be independent or work cooperatively

2. Cooperating processes can be used :
  • To gain speedup by overlapping activities or working in parallel
  • To better structure an application as set of cooperating processes
  • To share information between jobs
3. Sometimes processes are structured as a pipeline
  • Each produces work for the next stage that consumes it
Case for Parallelism

Consider the following code fragment on a dual core CPU :

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

Instead :

CreateProcess(fn, 0, n/2);
CreateProcess(fn, n/2, n);
fn(l, m)
for(k = l; k < m; k++)
a[k] = b[k] * c[k] + d[k] * e[k];

1. Consider a web server :
  • Get network message from socket
  • Get URL data from disk
  • Compose response
  • Write compose.
2. Server connections are fast, but client connections may not be (grandma’s modem connection) 
  • Takes server a loooong time to feed the response to grandma
  • While it’s doing that it can’t service any more requests
Parallel Programs

1. To build parallel programs, such as :
  • Parallel execution on a multiprocessor
  • Web server to handle multiple simultaneous web requests
2. We will need to :
  • Create several processes that can execute in parallel
  • Cause each to map to the same address space. Because they’re part of the same computation
  • Give each its starting address and initial parameters
  • The OS will then schedule these processes in parallel
Process Overheads

1. A full process includes numerous things :
  • An address space (defining all the code and data pages)
  • OS resources and accounting information
  • A “thread of control”, defines where the process is currently executing. That is the PC and registers
2. Creating a new process is costly. 
  • All of the structures (e.g., page tables) that must be allocated
3. Context switching is costly. 
  • Implict and explicit costs as we talked about
Need something more lightweight

1. What’s similar in these processes ?
  • They all share the same code and data (address space)
  • They all share the same privileges
  • They share almost everything in the process
2. What don’t they share ?
  • Each has its own PC, registers, and stack pointer
3. Idea :  Why don’t we separate the idea of process (address space, accounting, etc.) from that of the minimal “thread of control” (PC, SP, registers) ?

Threads and Processes

1. Most operating systems therefore support two entities :
  • The process, which defines the address space and general process attributes
  • The thread, which defines a sequential execution stream within a process
2. A thread is bound to a single process.  
  • For each process, however, there may be many threads.
3. Threads are the unit of scheduling

4. Processes are containers in which threads execute

Multithreaded Processes

Threads vs Processes

  • A thread has no data segment or heap
  • A thread cannot live on its own, it must live within a process
  • Inexpensive creation
  • Inexpensive context switching
  • If a thread dies, its stack is reclaimed
  • A process has code/data/heap & other segments
  • There must be at least one thread in a process
  • Expensive creation
  • Expensive context switching
  • If a process dies, its resources are reclaimed & all threads die

Can you achieve parallelism within a process without using threads ?

Thread scheduling

A cooperative thread gets to runs until it decides to give up the CPU

tid t1 = CreateThread(fn, arg);
fn(int arg)

Cooperative Threads
  • Cooperative threads use non pre-emptive scheduling
  • Advantages :
  • Simple. Scientific apps
  • Disadvantages : For badly written code
  • Scheduler gets invoked only when Yield is called
  • A thread could yield the processor when it blocks for I/O
Non-Cooperative Threads
  • No explicit control passing among threads
  • Rely on a scheduler to decide which thread to run
  • A thread can be pre-empted at any point
  • Often called pre-emptive threads
  • Most modern thread packages use this approach
Multithreading models

1. There are actually 2 level of threads :

2. Kernel threads :
  • Supported and managed directly by the kernel.
3. User threads :
  • Supported above the kernel, and without kernel knowledge
Kernel Threads

Kernel threads may not be as heavy weight as processes, but they still suffer from performance problems :

1. Any thread operation still requires a system call.

2. Kernel threads may be overly general 
  • To support needs of different users, languages, etc.
3. The kernel doesn’t trust the user
  • There must be lots of checking on kernel calls
User-Level Threads

1. The thread scheduler is part of a user-level library

2. Each thread is represented simply by:
  • PC
  • Registers
  • Stack
  • Small control block
3. All thread operations are at the user-level:
  • Creating a new thread
  • Switching between threads
  • Synchronizing between threads
Multiplexing User-Level Threads

1. The user-level thread package sees a “virtual” processor(s)
  • It schedules user-level threads on these virtual processors
  • Each “virtual” processor is implemented by a kernel thread (LWP)
2. The big picture :
  • Create as many kernel threads as there are processors
  • Create as many user-level threads as the application needs
  • Multiplex user-level threads on top of the kernel-level threads
3. Why not just create as many kernel-level threads as app needs ?
  • Context switching
  • Resources
Many-to-One Model

Thread creation, scheduling, synchronization done in user space. Mainly used in language systems, portable libraries.
  • Fast - no system calls required
  • Few system dependencies, portable
  • No parallel execution of threads - can’t exploit multiple CPUs
  • All threads block when one uses synchronous I/O
One-to-one Model

Thread creation, scheduling, synchronization require system calls. Used in Linux Threads, Windows NT, Windows 2000, OS/2
  • More concurrency
  • Better multiprocessor performance
  • Each user thread requires creation of kernel thread
  • Each thread requires kernel resources; limits number of total threads
Many-to-Many Model

If U < L? No benefits of multithreading. If U > L, some threads may have to wait for an LWP to run
  • Active thread - executing on an LWP
  • Runnable thread - waiting for an LWP
A thread gives up control of LWP under the following :
  • Synchronization, lower priority, yielding, time slicing
Two-level Model

1. Combination of one-to-one + “strict” many-to-many models

2. Supports both bound and unbound threads
  • Bound threads - permanently mapped to a single, dedicated LWP
  • Unbound threads - may move among LWPs in set
3. Thread creation, scheduling, synchronization done in user space

4. Flexible approach, “best of both worlds”

5. Used in Solaris implementation of P threads and several other Unix implementations (IRIX, HP-UX)

User-Level vs. Kernel Threads

User-Level :
  • Managed by application
  • Kernel not aware of thread
  • Context switching cheap
  • Create as many as needed
  • Must be used with care
Kernel-Level :
  • Managed by kernel
  • Consumes kernel resources
  • Context switching expensive 
  • Number limited by kernel resources
  • Simpler to use
Key issue : Kernel threads provide virtual processors to user-level threads, but if all of kernel threads block, then all user-level threads will block even if the program logic allows them to proceed.

Example User Thread Interface

t = thread_fork(initial context)
create a new thread of control
stop the calling thread, sometimes called thread_block

start the named thread
voluntarily give up the processor
terminate th calling thread, sometimes called thread_destroy

Key Data Structures

Multithreading Issues

Semantics of fork() and exec() system calls
1. Thread cancellation
  • Asynchronous vs. Deferred Cancellation
2. Signal handling
  • Which thread to deliver it to?
3. Thread pools
  • Creating new threads, unlimited number of threads
4. Thread specific data

5. Scheduler activations
  • Maintaining the correct number of scheduler threads
Thread Hazards

int a = 1, b = 2, w = 2;
main() {
CreateThread(fn, 4);
CreateThread(fn, 4);
while(w)  ;
fn() {
int v = a + b;

Concurrency Problems

A statement like w-- in C (or C++) is implemented by several machine instructions :
load reg, #w
add reg, reg, -1
store reg, #w
Now, imagine the following sequence, what is the value of w ?
load reg, #w        
add reg, reg, -1
store reg, #w
load reg, #w
add reg, reg, -1
store reg, #w
Next Post »