Chapter 5: Threads

Overview

• Lightweight process (LWP, thread)

• heavyweight process

  ch5_1.png

Motivation

​ ch5_n1.png

• Benefits of of multithreaded programming
  • Responsiveness
    • program run even if part of it is bloked.
    • useful in designing user interfaces.
  • Resource Sharing
  • Economy
    • economical to create and context-switch threads (than process)
  • Scalability
    • Utilization of MP (microprocessor) architectures

Multicore Programming

• parallelism : can perform more than one task simultaneously

• concurrency : supports more than one task by allowing all the tasks to make progress

Programming Challenges

• Identifying tasks : find areas that can be divided into seperate concurrency tasks
• Balance : ensure that the tasks perform equal work of equal values; may not be worth the cost
• Data splitting : the data accessed and manipulated by the tasks must to run on seperate cores.
• Data dependency : ensure that the execution of the tasks is synchronized to accommodate the data dependency.
• Testing and debugging : difficult

Types of Parallelism

• Data Parallelism : distribute subsets of the same data across multiple computing cores and perform the same operation on each core.
• Task Parallelism : distribute not data but tasks (threads) across multiple computing cores. Each thread is performing a unique operation. Different threads may be operating on the same data, or they be operating on different data.

Few applications strictly follow either the data parallelism or task parallelism. In most instances, applications use a hybrid of these two strategies.

Multithreading Models

• Many-to-one model
• One-to-one model
• Many-to-many model

User and Kernel Threads

• User Threads
  • Provided at the user level
  • Are supported above the kernel, and are managed without kernel support.
  • Fast/Blocking
  • POSIX Pthreads, Mach C-threads, Solaris UIthreads
• Kernel Threads
  • Provided by the kernel.
  • Are supported and managed directly by the oprating system.
  • Fast/Nonblocking
  • Linux Solaris2, Windows, BeOS

Many-to-one model

• Maps many user threads to single kernel thread.

• Thread management is done by the thread library in user space.

• Used on systems that do not surport kernel thread.

• Drawback : the entile process will be block if a thread makes a blocking system call.

• Example: Green threads for Solaris2.

  ch5_2.png

One-to-one model

====

• Maps each user-level thread to a kernel thread.

• Provides more concurrency

  • allow another thread to run when a thread makes a blocking system call.
  • allow multiple threads to run in parallel on multiprocessor.

• Drawback :

  • create a user thread requires creating the corresponding kernel thread.
  • restrict the number of threads surpported by system.

• Example: Windows 95/98/NT/2000, OS/2

  ch5_3.png

​

​

Many-to-many model

• Multiplexes many user-level threads to a smaller or equal number of kernel threads.

• Allows the operating system to create a sufficient number of kernel threads.

• Example: Solaris 2, IRX, HP-UX.

  ch5_4.png

• two-level model:

ch5_n2.png

Thread Libraries

• A thread library provides programmers with an API for creating and managing threads.
• Two priamry ways of implementing a thread library:
  • provide a library entirely in user space with no kernel support.
    • All code and data structures for the library exist in user space.
    • Invoking a function in the library results in a local function call in user space and not a system call.
  • implement a kernel-level library supported directly by the operating system.
    • Code and data structures for the library exist in kernel space.
    • Invoking a function in the API for the library typically results in a system call to the kernel.
• Three main thread libraries are in use today:
  • POSIX Pthreads
  • Windows
  • Java
• Pthreads
  • The threads extension of the POSIX standard. (IEEE 1003.1c)
  • May be provided as a user-level or a kernel-level library.
• Windows thread library
  • A kernel-level library available on Windows system.

• Java thread API

  • Allows threads to be created and managed directly in java programs.
  • Because in most instances the JVM is running on the top of the host operating system, the Java thread API is generally implemented using a thread library available on the host system.
  • Java threads are typically implemented using:
    • Windows system : the Windows API
    • Unix and Linux : Pthreads

• POSIX and Windows threads : any data declared globally (declared outside of any function) are shared among all threads belonging to the same process.

• Java (has no notion of global) : access to shared data must be explicitly arranded between threads.

• Data declared local to a function are typically stored on the stack. Since each thread has its own strict, each thread has its own copy of local data.

• Two strategies of creating multiple threads:

  • asynchronous threading
  • synchronous threading

• Asynchronous threading : little data sharing between threads.

  
  ch5_n3.png ch5_n1.png

• Synchronous threading : involves significant data sharing among threads.

  • The parent thread creates one or more children and then must wait for all of its children to terminate before it resumes — the so-called fork-join strategy.

    ch5_n4.png

Pthreads

• Referred to the POSIX standard (IEEE 1003.1c)

• Defined an API for thread creation and synchronization.

• A specification of thread behavior, not an implementation.

• Common in UNIX operating systems.

• A C program used the Pthread API.

  #include  <stdio.h>
  #include  <pthread.h>
  
  #define   NUM 5
  
  main()
  {
      pthread_t t1, t2;     /* two threads */
  
      void  *print_msg(void *);
  
      pthread_create(&t1, NULL, print_msg, (void *)"hello");
      pthread_create(&t2, NULL, print_msg, (void *)"world\n");
      pthread_join(t1, NULL);
      pthread_join(t2, NULL);
  }
  void *print_msg(void *m)
  {
      char *cp = (char *) m;
      int i;
      for(i=0 ; i<NUM ; i++){
          printf("%s", m);  
          fflush(stdout);
          sleep(1);
      }
      return NULL;
  }
  

  ​

• A C program demonstrates the basic Pthread API for constructing a multithreaded program that calculates the summation of a nonnegative integer in a separate thread

  #include <pthread.h>
  #include <stdio.h>
  
  int sum; /* this data is shared by the thread(s) */
  
  void *runner(void *param); /* threads call this function */
  
  int main(int argc, char *argv[]) {
      pthread_t tid; /* the thread identifier */
      pthread_attr_t attr; /* set of thread attributes */
  
      if (argc != 2) {
          fprintf(stderr, "usage: a.out <integer value>\n");
          return -1;
      }
  
      if (atoi(argv[1]) < 0) {
          fprintf(stderr, "%d must be >= 0\n", atoi(argv[1]));
          return -1;
      }
  
      /* get the default attributes */
      pthread_attr_init(&attr);
      /* create the thread */
      pthread_create(&tid, &attr, runner, argv[1]);
      /* wait for the thread to exit */
      pthread_join(tid, NULL);
  
      printf("sum = %d\n", sum);
  }
  
  /* The thread will begin control in this function */
  void *runner(void *param) {
      int i, upper = atoi(param);
      sum = 0;
  
      for (i = 1; i <= upper; i++)
          sum += i;
  
      pthread_exit(0);
  }
  

• Pthread code for joinning ten threads

  #define NUM_THREADS 10
  /* an array of the threads to be joined upon */
  pthread_t workers[NUM_THREADS];
  
  for (int = 0; i < NUM_THREADS; i++)
      pthread_join(workers[i], NULL);
  

Summary

A thread is a flow of control within a process. A multithreaded process contains several different flows of control within the same address space. The benefits of multithreading include increased responsiveness to the user, resource sharing within the process, economy, and scalability factors, such as more efficient use of multiple processing cores.
User-level threads are threads that are visible to the programmer and are unknown to the kernel. The operating-system kernel supports and manages kernel-level threads. In general, user-level threads are faster to create and manage than are kernel threads, because no intervention from the kernel is required.
Three different types of models relate user and kernel threads. The many- to-one model maps many user threads to a single kernel thread. The one-to-one model maps each user thread to a corresponding kernel thread. The many-to- many model multiplexes many user threads to a smaller or equal number of kernel threads.
Most modern operating systems provide kernel support for threads. These include Windows, Mac OS X, Linux, and Solaris.
Thread libraries provide the application programmer with an API for creating and managing threads. Three primary thread libraries are in common use: POSIX Pthreads, Windows threads, and Java threads.
In addition to explicitly creating threads using the API provided by a library, we can use implicit threading, in which the creation and management of threading is transferred to compilers and run-time libraries. Strategies for implicit threading include thread pools, OpenMP, and Grand Central Dispatch.
Multithreaded programs introduce many challenges for programmers, including the semantics of the fork() and exec() system calls. Other issues include signal handling, thread cancellation, thread-local storage, and scheduler activations.

Practice Exercises

1. What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

   User-level threads are threads that are visible to the programmer and are unknown to the kernel.

   user-level threads are faster to create and manage than are kernel threads

2. Describe the actions taken by a kernel to context-switch between kernel-level threads.

   ​

3. What resources are used when a thread is created? How do they differ from those used when a process is created?

   ​