4.1 Overview

So far, we assumed that a process was an executing porgram with a single thread of control.

However, a process is able to contain multiple threads of control.

A thread is a lightweight process. (= a basic unit of CPU utilization)

A thread
: a thread ID + a program counter + a register set + a stack

Motivation for multithreading

Let us condisder the case of client-server system, e.g. a web server.

The benefits of multithreaded programming

1. Responsiveness: may allow continued execution

• if part of process is blocked, especially important for user interfaces.

2. Resource Sharing: thread share resources of process

• they share code and data section

• eaiser than shared-memory or message-passing.

3. Economy: cheaper than process creation

• thread switching lower overhead than context switching.

4. Scalability: process can take advantage of multiprocessor architectures.

4.4 Thread Library

Threads in Java

In a Java program, threads are the fundamental model of program execution.

Java provides a rich set of features for the creation and management of threads.

Three techniques for explicitly creating threads in Java.
1. Inheritance from the Thread class

• create a new class that is derived from the Thread class.
• and override its public void run() method.

2. Implementing the Runnable interface.

• define a new class that implements the Runnable interface.
• and override its public void run() method.

3. (New!) Using the Lambda expression (beginning with Java Version 1.8)

• rather than defining a new class
• use a lambda expression of Runnable instead.

1. Inheritance from the Thread class

class MyThread1 extends Thread {
	public void run() {
    	try {
        	while (true) {
            	System.out.println("Hello, Thread!");
                Thread.sleep(500);
			}
		}
        catch (InterruptedException ie) {
        	System.out.println("I'm interrupted");
		}
	}
}

public class ThreadExample1 { // fork()와 유사
	public static final void main(String[] args) {
    	MyThread1 thread = new MyThread1();
        thread.start(); // thread.run() (X)
        System.out.println("Hello, My Child!");
	}
}

Output

Hello, My Child!
Hello, Thread!
Hello, Thread!
Hello, Thread!
...

2. Implementing the Runnable interface

class MyThread2 implements Runnable {
	public void run() {
    	try {
        	while (true) {
            	System.out.println("Hello, Runnable!");
                Thread.sleep(500);
			}
		}
        catch (InterruptedException ie) {
        	System.out.println("I'm interrupted");
		}
	}
}

public class ThreadExample2 {
	public static final void main(String[] args) {
    	Thread thread = new Thread(new MyThread2());
        thread.start();
        System.out.println("Hello, My Runnable Child!");
	}
}

3. (New!) Using Runnable Lambda expression

public class ThreadExample3 {
	public static final void main(String[] args) {
    	Runnable task = () -> { // Lambda expression
        	try {
            	while (true) {
                	System.out.println("Hello, Lambda Runnable!");
                    Thread.sleep(500);
				}
			}
            catch (InterruptedException ie) {
            	System.out.println("I'm interrupted");
			}
		}
		Thread thread = new Thread(task);
        thread.start();
        System.out.println("Hello, My Lambda Child!");
	}
}

Parent Thread: Wait(X) vs Join(O)

public class ThreadExample4 {
	public static final void main(String[] args) {
    	Runnable task = () -> {
        	for (int i = 0; i < 5; i++) {
            	System.out.println("Hello, Lambda Runnable!");
			}
		};
        Thread thread = new Thread(task);
        thread.start();
        try {
        	thread.join(); // wait
		}
        catch (InterruptedException ie) {
			System.out.println("Parent thread is interrupted");
        }
        System.out.println("Hello, My Joined Child!);
	}
}

Output

Hello, Lambda Runnable!
Hello, Lambda Runnable!
Hello, Lambda Runnable!
Hello, Lambda Runnable!
Hello, Lambda Runnable!
Hello, My Joined Child!

Thread: Stop(X) vs Interrupt(O)

public class ThreadExample5 {
	public static final void main(String[] args) throws InterruptedException {
    	Runnable task = () -> {
        	try {
            	while (true) {
                	System.out.println("Hello, Lambda Runnalbe!");
                    Thread.sleep(100);
				}
			}
            catch (InterruptedException ie) {
            	System.out.println("I'm interrupted");
			}
            Thread thread = new Thread(task);
            thread.start();
            Thread.sleep(500);
            thread.interrupt();
            System.out.println("Hello, My Interrupted Child!");
		}
	}
}

Output

Hello, Lambda Runnalbe!
Hello, Lambda Runnalbe!
Hello, Lambda Runnalbe!
Hello, Lambda Runnalbe!
Hello, Lambda Runnalbe!
I'm interrupted
Hello, My Interrupted Child!

4.2 Multicore Programming

Multithreading in a Multicore system.

Consider an application with four threads

• Single-core: thread will be interleaved over time.

• Concurrent execution

• Mulitple-core: some threads can run in parallel.

• Parallel execution

Programming Challenges in Multicore systems

1. Identifying tasks: find areas can be divided into separate tasks.
2. Balance: ensure the tasks to perform equal work of euqal value.
3. Data splitting: data slao must be divided to run on separate cores.
4. Data dependency: ensure that the execution of tasks is synchronized to accommodate the data dependency
5. Testing and debuggin: more difficult than single-thread.

Types of parallelism

These days, distributed parallelism by MapReduce widely used

Amdahl's Law

Question: CPU core is 'The more, the better?'

$speedup$ $≤$ $1\over S+\frac{(1-S)}{N}$, where
$S$: the portion that must be performed serially on a system
$N$: the number of processing cores

Example
$S$=0.25, $N$=2, $speedup$=1.6
$S$=0.25, $N$=4, $speedup$=2.28

4.3 Multithreading Models

Two types of thread

1. User threads

supported above the kernel, and are managed without kernel supprot.

2. Kernel threads

supported and managed directly by the operating system.

Three relationships between user and kernel threads

Many-to-One Model	One-to-One Model	Many-to-Many Model

4.4 Thread Libraries

A thread library provides an API for creating and managing threads.

Three main thread libraries are in use today

1. $POSIX$ Pthreads

2. $Windows$ thread

3. $Java$ thread

$Pthreads$

• refers to the $POSIX$ standard (IEEE 1003.1c)

• just a specification for thread behavior, not an implementation.

Multithreaded C program using the Pthread API

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

/* the data shared by the threads */
int sum;
/* thread call this function */
void * runner(void *param); // public void run

int main(int argc, char *argv[])
{
	pthread_t tid; // pthread identifier
    pthread_attr_t attr // pthread attributes
    
    pthread_attr_init(&attr);
    pthread_create(&tid, &attr, runner, argv[1]); // new Thread();
    pthread_join(tid, NULL)l
    
    printf("sum = %d\n", sum);
}
void *runner(void *param)
{
	int i, upper = atoi(param);
    sum = 0;
    for (i = 1; i <== upper; i++)
    	sum += i;
	pthread_exit(0);
}

Compile

$ gcc -pthread 4.11_pthread.c
$ ./a.out
> Segemenataion falut
$ ./a.out 10
> sum = 55
$ ./a.out 100
> sum = 5050

Excercise 4.17 (p.910)

pid_t pid;

pid = fork();
if (pid == 0) { /* child process */
	fork();
    thread_create( . . .);
}
fork();

a. How many unique processes are created? : 6
b. How many unique threads are created? : 2 + 6 = 8

4.5 Implicit Threading

The Strategy of Implicitly Thread

The design of concurrent and parallel applications

• i.e., the design of multithreading in multicore systems, is too difficult for application developers.

So, transfer the difficulty to compiler and run-time libraries.

Four alternative approaches using implicit threading

1. Thread Pools

• create a number of threads in a pool where they await work.

2. Fork & Join

• explicit threading, but an excellent candidate for implicit threading.

3. OpenMP

• a set of compiler directives and an API for programs written in C/C++.

4. Grand Central Dispatch(GCD)

• developed by Apple for its macOS and iOS operating system.

OpenMP

• identified parallel regions as blocks of code that may run in parallel.

• insert compiler directives into source code at parallel regions.

• these directives instruct OpenMP runtime library to execute the region in parallel.

#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[])
{
	#pragma omp parallel // compiler directive
    {
    	printf("I am a parallel region.\n");
    }
    return 0;
}

Compile

$ gcc 4.20_OpenMP1.c
$ ./a.out
> I am a parallel region.
$ gcc -fopenmp 4.20_OpenMP1.c
$ ./a.out
> I am a parallel region.
> I am a parallel region.
> I am a parallel region.
> I am a parallel region.
> I am a parallel region.
> I am a parallel region.
...
> I am a parallel region.

#include <stdio.h>
#include <omp.h>

int main(int argc, char *argv[])
{
	omp_set_num_threads(4); // controll the count of threads
    
    #pragma omp parallel
    {
    	printf("OpenMP thread: %d\n", omp_get_thread_num());
    }
    return 0;
}

Compile

$ gcc -fopenmp 4.20_OpenMP2.c
$ ./a.out
> OpenMP thread: 0
> OpenMP thread: 3
> OpenMP thread: 1
> OpenMP thread: 2

#include <stdio.h>
#include <omp.h>

#define SIZE 10000000

int a[SIZE], b[SIZE], c[SIZE];

int main(int argc, char *argv[])
{
	int i;
    for (i = 0; i < SIZE; i++)
    	a[i] = b[i] = i;

	#pragma omp parallel for
    for (i = 0; i < SIZE; i++) {
    	c[i] = a[i] + b[i];
	}
    return 0;
}