Chapter 4 Threads and Concurrency

• Thread runs within program.
• Process creation is heavy-weight, thread creation is light-weight.
• Simplify code, increase efficiency

Multi-threaded server architecture:

Benefits

• Responsiveness: Even if a part of program is slow or blocked, other parts of the program can continue to run.
• Resource sharing: Threads shares memory and resources within process by default.
• Economy: Cheaper to create than process.
• Scalability: Runs in parallel in different cores.

Context switch VS thread switch

• Context switch will have to reload everything currently in memory space.
• Threads in the process shares the same code, data section and OS resources.

Multicore programming

Parallel

• Perform more than one task simultaneously.

Types of parallelism

• Data parallelism: Same data and operation on multiple core.
• Task parallelism: Distribute threads across cores, each performing an unique operation.

Amdahl's law

• S is serial portion of program.
• N processing cores

• As N approaches infinite, speedup approaches 1/S.

Concurrency

• Supports more than one task making progress.
• Single core multitask. Use a scheduler.

Multi-threading Models

• User threads: Management done by user-level thread library.
  • POSIX thread
  • Windows thread
  • Java thread
• Kernel threads: Supported by the Kernel

Models

• Many-to-one
  • Many user-level threads mapped to single kernel thread
  • One thread blocking causes all to block
  • May not run in parallel on multi-core system because only one thread can be in the kernel at a time.
• One-to-One
  • Each user-level thread maps to kernel thread
  • More concurrency than many-to-one
  • Number of threads per process sometimes restricted due to overhead
• Many-to-many
  • Allows many user level threads to be mapped to many kernel threads
  • Allows the operating system to create a sufficient number of kernel threads
• Two level model
  • Hybrid One-to-One and Many-to-many. Allows a user thread to be bound to kernel thread.

Thread Libraries

• Use thread libraries to create and and manage threads.

Pthreads

• Provided either as user-level or kernel-level.
• A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
• Is a spec. not implementation.
• API specifies behavior, implementation is up to library.
• Common in UNIX.

Example

Windows multi-thread C program

• Similar to POSIX

Example

JAVA Threads

• Managed by the JVM
• JVM is available on any OSs, including Windows, Linux, MacOS.
• JAVA thread is created by:
  • Extending the thread class
  • implementing the runnable interface(Used most of the time)

public interface Runnable
{
    public abstract void run();
}

Codes

• Implement runnable interface

• Create thread

• waiting on a thread

Java executor framework

• Java also allows thread creation around the Executor interface:

• The Executor is used as follows:

Implicit threading

• Growing in popularity as number of thread increase.

• Creation and management of threads done by compilers and run-time libraries rather than programmers

• Five methods explored

  • Thread Pools
  • Fork-Join
  • OpenMP
  • Grand Central Dispatch
  • Intel Threading Building Blocks

Thread pool

• Creates threads in a pool waiting for work.

Advantages

• Usually slightly faster than creating thread on request.
• Number to threads is bound to the size of pool
• task can start run by mechanics rather than create thread.

Windows API supports thread pool

Three methods to create thread pool for JAVA

Fork Join

• Threads are forked, and then joined.
  • 
• General algorithm for fork-join strategy
  • 

Fork join parallelism in JAVA

• The ForkJoinTask as an abstract task.
• RecursiveTask and RecursiveAction classes extend ForkJoinTask.
• RecursiveTask returns a result (via the return value from the compute() method)
• RecursiveAction does not return a result

OpenMP

• Identifies parallel regions as code blocks by #pragma omp parallel .
  
  
  
  

Grand Central Dispatch

• For MacOS and IOS.
• Extensions to C, C++ and Objective-C languages, API, and run-time library
• Allows identification of parallel sections by ^{} .
• Blocks placed in dispatch queue. After task is removed from queue, assign the task to empty thread in thread pool.
• Two types of dispatch queues:
  • Serial: Blocks removed in FIFO order. Queue is per process, called main queue.
  • concurrent: Removed in FIFO order, several may be removed at a time.

Intel Threading Building Blocks (TBB)

• Template library for designing parallel C++ programs
• For loop written using TBB with parallel_for statement
  • parallel_for(size_t(0),n, [=] (size_t i){apply(v[i])})

Threading Issues

The fork() and exec() System Calls

• Two versions of fork()
  • Only duplicate the called thread
  • Duplicate all threads
• Exec(). Replace all threads in process.

Signal handling

• Signal is used to notify an event has occurred.
• A signal handler is used to process signals.
  • Signal is created by particular event.
  • Signal is delivered to a process.
  • Signal handlers can be default or user-defined.
• Every signal has default handler that kernel runs. User-defined signal handler can override default.
• Four types of signal deliver:
  • Deliver the signal to the thread to which the signal applies
  • Deliver the signal to every thread in the process
  • Deliver the signal to certain threads in the process
  • Assign a specific thread to receive all signals for the process

Thread Cancellation

• Terminate a thread before it has finished.
• Thread to be canceled is called the target thread.

Two general approaches

• Asynchronous cancellation: Terminates the target thread immediately.
• Deferred cancellation: Target thread periodically check if it should be cancelled.

Pthread example to create and cancel a thread.

• pthraed_cancel(tid) sends a request to terminate only. Actual cancellation depends on thread state.
• If thread has cancellation disabled, cancellation remains pending.
• Default type is deferred.
• Cancel only occurs when pthread_testcancel() is called, the cleanup handler is invoked.

JAVA

• Deferred cancellation uses the interrupt() method.

• A thread checks if it is interrupted.

Thread-Local Storage(TLS)

• TLS allows each thread to have its own data.
• Useful when using thread pool.

Scheduler Activations

• Many-to-many and two-level models require communication to maintain the appropriate number of kernel threads allocated to the application.
• Lightweight process (LWP) is an intermediate data structure between kernel and user thread.
  • Appears to be a virtual processor user thread could be scheduled to run on.
  • Each LWP is attached to kernel thread.
• The kernel informs an application about current event using upcalls provided by upcall handler in thread library.
• This communication allows an application to maintain the correct number kernel threads

Operating System Examples

Windows Threads

• Provided by windows API.

• Implements the one-to-one mapping.

• Context of thread:

  • thread id
  • Register set representing state of processor
  • Separate user and kernel stacks for when thread runs in user mode or kernel mode
  • Private data storage area used by run-time libraries and dynamic link libraries (DLLs)

• Primary data structures of a thread :

  • ETHREAD (executive thread block) – includes pointer to process to which thread belongs and toKTHREAD, in kernel space
  • KTHREAD (kernel thread block) – scheduling and synchronization info, kernel-mode stack, pointer to TEB, in kernel space
  • TEB (thread environment block) – thread id, user-mode stack, thread-local storage, in user space

Linux Threads

• Refers to as tasks not threads.
• Thread creation is done by clone().
• clone() allows a task to share address space with process controlled by flags.
  
  
• struct task_struct points to process data structures (shared or unique)

Review Questions

• 1. What resources are used when a thread is created and a process is created?
     How do they differ from those used when a process is created? Difference
• 2. How does a multi-threaded web server work?
• 3. What are the benefits of multi-threaded programming? Explain each item. Benefits
• 4. What are the differences between the three multithreading models? Models
• 5. Implement creating a thread by the following thread library,
     including the critical functions, parameters, and related procedures.
     a. Pthread b. Windows thread c. Java Thread
• 6. How does implicit threading work?
     Describe the three types of implementations.Thread pool, openMP and Grand Central Dispatch
• 7. How a signal can be delivered in a multi-threaded program.
     Describe the four options.Signal handling
• 8. How do the two types of thread cancellation work? Thread Cancellation
• 9. How does the scheduler of kernel thread work, including the upcall procedure? Scheduler
• 10. What is the data structure of Windows thread?
      Describe the content of each block of data structure. Window Thread

tags: Operating System CSnote