Overview

• A thread is a basic unit of CPU utilization, consisting of a program counter, a stack, and a set or registers, ( and a thread ID). A thread control block (TCB) is a data structure that hold a separate copy of the information needed to execute a thread independently
• Traditional processes have a single thread of control - There is one program counter, and one sequence of instructions that can be carried out at any given time
• Multi-threaded applications have multiple threads with a single process, each having their own program counter, stack and set of registers, but sharing common code, data, and certain structures such as open files.

Motivation

• Threads are very useful in modern programming whenever a process has multiple tasks to perform independently of the others.
• This is particularly true when one of the tasks may block, and it is desired to allow the other tasks to proceed without blocking.

Benefits

There are four major categories of benefits to multi-threading:

1. Responsiveness - One thread may provide rapid response while other threads are blocked or slowed down doing intensive calculations.
2. Resource sharing - By default threads share common code, data, and other resources, which allows multiple tasks to be performed simultaneously in a single address space.
3. Economy - Creating and managing threads ( and context switches between them ) is much faster than performing the same tasks for processes.
4. Scalability, i.e. Utilization of multiprocessor architectures - A single threaded process can only run on one CPU, no matter how many may be available, whereas the execution of a multi-threaded application may be split amongst available processors. ( Note that single threaded processes can still benefit from multi-processor architectures when there are multiple processes contending for the CPU, i.e. when the load average is above some certain threshold. )

Multi-core Programming

• CPUs are being built with multiple cores.
• A multi-threaded application running on a traditional single-core chip would have to interleave the threads. On a multi-core chip, however, the threads could be spread across the available cores, allowing true parallel processing.

Programming Challenges

1. Identifying tasks - Examining applications to find activities that can be performed concurrently.
2. Balance - Finding tasks to run concurrently that provide equal value. Don't waste a thread on trivial tasks.
3. Data splitting - To prevent the threads from interfering with one another
4. Testing and debugging - Inherently more difficult in parallel processing situations, as the race conditions become much more complex and difficult to identifying

Types of Parallelism

1. Data parallelism divides the data up amongst multiple cores ( threads ), and performs the same task on each subset of the data. For example dividing a large image up into pieces and performing the same digital image processing on each piece on different cores
2. Task parallelism divides the different tasks to be performed among the different cores and performs them simultaneously.

In practice, a program is divided using a hybrid combination of the two.

Multi-threading models

Two types of threads, user threads and kernel threads.

• User threads are supported above the kernel, without kernel support. These are the threads that application programmers would put into their programs.
• Kernel threads are supported within the kernel of the OS itself. All modern OSes support kernel level threads, allowing the kernel to perform multiple tasks simultaneously and/or service multiple kernel system calls simultaneously.

In a specific implementation, the user threads must be mapped to kernel threads, using one of the following strategies.

Many-To-One Model

In the many-to-one model, many user-level threads are all mapped to a single kernel thread. Thread management is handled by the thread library which is very efficient. However, if a blocking system call is made, then the entire process blocks, even if the other user threads would be able to continue.

Because a single kernel thread can operate only on a single CPU, the many-to-one model does not allow individual processes to be split across multiple CPUs.

One-To-One Model

The one-to-one model creates a separate kernel thread for each user thread. This model overcomes the problems listed above such as blocking system calls and the splitting of processes across multiple CPUs.

However the overhead associated is greater and slows down the system.

Most implementations of this model limits the number of threads that can be created.

Many-To-Many Model

The many-to-many model is when several user threads are connected to an equal or smaller number of kernel threads. This combines the best features of many-to-one and one-to-one models.

Users have no restrictions on the number of threads created. Blocking system calls do not block the entire process. Processes can be split across multiple processors.

Individual processes may be allocated variable number of kernel threads, depending on the number of CPUs present and other factors.

A popular variation of the many-to-many model is the two-tier model, which allows either many-to-many or one-to-one operation.

Thread Libraries

Thread libraries provide programmers with an API for creating and managing threads. They may be implemented either in user space or kernel space.

User space involves API functions implemented solely within user space, with no kernel support. Kernel space involves system calls and requires a kernel with thread library support.

Pthreads

Provided as either a user or kernel library, as an extension to the POSIX standard. The POSIX standard defines the specification for pThreads, not the implementation.

Global variables are shared amongst all threads. One thread can wait for the others to rejoin before continuing.

pThreads begin execution in a specified function, in this example the runner() function:

#include <pthread.h>
#include <stdio.h>
int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* the thread */
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);
}

Here's Pthread code for joining ten threads:

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

Windows Threads

They are provided as a kernel-level library on Windows systems.

#include <windows.h>
#include <stdio.h>
DWORD Sum; /* data is shared by the thread(s) */
/* the thread runs in this separate function */
DWORD WINAPI Summation(LPVOID Param)
{
    DWORD Upper = *(DWORD*)Param;
    for (DWORD i = 0; i <= Upper; i++)
    Sum += i;
    return 0;
}
int main(int argc, char *argv[])
{
    DWORD ThreadId;
    HANDLE ThreadHandle;
    int Param;
    /* perform some basic error checking */
    if (argc != 2) {
    fprintf(stderr,"An integer parameter is required\n");
    return -1;
    }
    Param = atoi(argv[1]);
    if (Param < 0) {
    fprintf(stderr,"An integer >= 0 is required\n");
    return -1;
    }
    // create the thread
    ThreadHandle = CreateThread(
    NULL, // default security attributes
    0, // default stack size
    Summation, // thread function
    &Param, // parameter to thread function
    0, // default creation flags
    &ThreadId); // returns the thread identifier
    if (ThreadHandle != NULL) {
    // now wait for the thread to finish
    WaitForSingleObject(ThreadHandle,INFINITE);
    // close the thread handle
    CloseHandle(ThreadHandle);
    printf("sum = %d\n",Sum);
}

Java Threads

All java programs use threads. The creation of new threads requires Objects that implement the Runnable Interface, which means they contain the method public void run(). Any descendant of the Thread class will naturally contain such a method. In practice the run() method must be overridden / provided for the thread to have any practical functionality.

Creating a Thread Object does not start the thread running - to do that the program must call the Thread's start() method. Start() allocates and initializes memory for the Thread, and then calls the run() method. Usually programmers don't call the run() method directly.

Because Java does not support global variables, Threads must be passed a reference to a shared Object in order to share data, in this example the "Sum" Object.

Note that the JVM runs on top of a native OS, and that the JVM specification does not specify what model to use for mapping Java threads to kernel threads. This decision is JVM implementation dependant, and may be one-to-one, many-to-many, or many-to-one. On a UNIX system JVM uses Pthreads and on Windows it uses windows threads.

class Sum
{
    private int sum;
    public int getSum() {
        return sum;
    }
    public void setSum(int sum) {
        this.sum = sum;
    }
}
class Summation implements Runnable
{
    private int upper;
    private Sum sumValue;
    public Summation(int upper, Sum sumValue) {
        this.upper = upper;
        this.sumValue = sumValue;
    }
    public void run() {
        int sum = 0;
        for (int i = 0; i <= upper; i++)
            sum += i;
        sumValue.setSum(sum);
    }
}
public class Driver
{
    public static void main(String[] args) {
    if (args.length > 0) {
        if (Integer.parseInt(args[0]) < 0)
            System.err.println(args[0] + " must be >= 0.");
        else {
            // create the object to be shared
            Sum sumObject = new Sum();
            int upper = Integer.parseInt(args[0]);
            Thread thrd = new Thread(new Summation(upper, sumObject));
            thrd.start();
            try {
                thrd.join();
                System.out.println("The sum of "+upper+" is "+sumObject.getSum());
            } catch (InterruptedException ie) { }
        }
    }
    else
        System.err.println("Usage: Summation <integer value>"); }
}