Threads & Concurrency#

Overview#

A Thread is the smallest unit of CPU utilization

Thread 就是 CPU 能夠安排運行的最小單位，擁有

• thread ID
• Program Counter (PC): 可能會是一個或多個
• Register Set
• Stack

Overview

跟 Process 最大不同就是會 share resource, code, file

Thread 可以來平行的進行各種計算，Process 是一個 time consuming 的東西，而 Thread 比較少成本，平行計算 multi-threading 可以節省很多時間跟成本

• Responsiveness: 反應會比較即時，因為可以平行運行
• Resource sharing: 效率高，但會出現 Synchronize 的問題
• Economy
• Scalability

Multicore Programming#

• Concurrency: 不同的 task 各自都有 progress
• Parallelism: 完全獨立的運行

Single core 也可以有 Concurrency，但無法 Parallelism

Multicore Programming 1

下面這張則是同時有 Concurrency 跟 Parallelism

Multicore Programming 2

Challenge#

• Identifying tasks
• Balance: 分工問題
• Data splitting: 資料同一份無法切割
• Data dependency: 執行順序問題，可能導致最後根本沒有 Concurrency
• Testing and debugging

Parallelism#

• Data parallelism 從資料下手，把資料分成四段，執行一樣的 code 四個 core 執行完畢再由統一一個 core 做整合

Parallelism 1

• Task parallelism 共用一個 data，但四個 core 在做不同的 task

Parallelism 2

兩種 parallelism 可以混用，只是概念而已

Amdahl’s Law#

把每個 Task 切割成可以平行以及不能平行計算的部分，就可以得到

• $S$: 必須得 serial 執行的部分
• $N$: Processing Core

雖然有平行化，但通常都會多一些 overhead，所以現實情況都會差一點

無法平行化的部分越多，multi-core 的效果就越差

Multithreading Models#

User thread / Kernel thread#

看是誰負責處理這個 thread 決定他是 kernel/user

Many-to-One Model (user-level threading)#

有很多 user thread，但全都由同一個 kernel thread 管理，等於實際上只有一個真正的 thread

• 同時只有一個 thread 可以 access kernel
• 當有一個 user thread 被 block 住就會讓整個 kernel 卡住
• 站在 kernel 角度其實沒辦法真正 implement multi-thread
• efficient 但是無法真正發揮 parallelism

Many-to-One Model

One-to-One Model (kernel-level threading)#

每個 user thread 都有對應的 kernel thread

• 當有 blocking system call 只會讓對應的 kernel thread 被 block 住
• 高成本

One-to-One Model

Many-to-Many Model (hybrid threading)#

混合版模型，把 M 個 application 丟給 N 個 thread entities (Virtual Processor)

• 比較彈性，可以根據 task 的複雜度，來決定到底要多少 thread

Many-to-Many Model 2

Two-level model 也是一種 Many-to-Many Model 的變形

現今大部分 OS 都是 one-to-one model 因為效能足夠

Thread Libraries#

Thread Libraries 就是用 api 來實現各種 Thread 的管理，有可能是 user-level，也可以是 kernel-level

• Asynchronous threading independent 的執行下去 parent 可以繼續執行

• Synchronous threading 需要先 block 住，等 child thread 執行再繼續

Pthreads#

POSIX standard 只是一個 spec，而不是一個 implementation

#include <pthread.h>
#include <stdio.h>
#include <stdlib.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 */
    /* set the default attributes of the thread */
    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 execute 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);
}

• Process Creation

#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
int main() {
    pid_t pid;
    /* fork a child process */
    pid = fork();
    if (pid < 0) { /* error occurred */
        fprintf(stderr, "Fork Failed");
        return 1;
    }
    else if (pid == 0) { /* child process */
        execlp("/bin/ls","ls",NULL);
    }
    else { /* parent process */
    /* parent will wait for the child to complete */
        wait(NULL);
        printf("Child Complete");
    }
    return 0; 
}

• function call

#include <stdio.h>
#include <stdlib.h>
int sum;
void runner(void *param);
int main(int argc, char *argv[]) {
    runner(argv[1]);
    printf("sum = %d\n",sum);
}
void runner(void *param) {
    int i, upper = atoi(param);
    sum = 0;
    for (i = 1; i <= upper; i++)
        sum += i;
}

join 10 個 pthread

#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);

參考 System Programming 系統程式設計 筆記

Windows Threads#

#include <windows.h>
#include <stdio.h>
DWORD Sum; /* data is shared by the thread(s) */
/* The thread will execute in this function */
DWORD WINAPI Summation(LPVOID Param) {
    DWORD Upper = *(DWORD*)Param;
    for (DWORD i = 1; i <= Upper; i++)
        Sum += i;
    return 0;
}
int main(int argc, char *argv[]) {
DWORD ThreadId;
    HANDLE ThreadHandle;
    int Param;
    Param = atoi(argv[1]);
    /* create the thread */
    ThreadHandle = CreateThread(NULL, 0, Summation, &Param, 0, &ThreadId);
    /* now wait for the thread to finish */
    WaitForSingleObject(ThreadHandle,INFINITE);
    /* close the thread handle */
    CloseHandle(ThreadHandle);
    printf("sum = %d\n",Sum);
}

• 透過 CreateThread 設定參數
• WaitForMultipleObjects(N, THandles, TRUE, INFINITE); 可以等多個 thread

Java Threads#

Java 是 run 在 Java virtual machine (JVM) 上的，而 JVM 又會跟底層 OS 做 communication，但在這個地方我們只討論最上層（Java thread）

• Create a new class derived from the Thread 然後要 override its run() method
• 用 Runnable 去 call run()，直接 call run() 是不會跑的

class Task implements Runnable {
    public void run() {
        System.out.println("I am a thread.");
    }
}

Creation: 不要直接 call run() 而要用 start() 去啟動

Thread worker = new Thread(new Task());
worker.start();

Wait:

try {
    worker.join();
}
catch (InterruptedException ie) { }

Implicit Threading#

Threading problem 其實是一個非常困難的問題，Thread 之間的交互影響以及順序問題，是非常複雜的

Implicit Threading 就是把 creation, management 都交給 compiler 或是 runtime library，User face 來看，是完全沒有 Thread 的概念，而是 Task

Thread Pool#

在一群 Thread 裡面抓人出來做 task，省略了 Thread creation 的步驟，一直使用同一組 Thread pool 裡的 Thread，沒有 creation 跟 termination

• Create 這件事是有很大的 overhead
• Thread Pool 可以限定所有 Thread 都在同一個 Management 底下（因為是同一組），可以控制數量，但限定了效能
• Thread Pool 可以讓我們對 Thread Management 有更大的 flexibility

Fork join#

跟 Process 很像，只是我們這次是用在 Thread 上

• 站在使用者的角度是分成兩個 Task，但是實際上的 implementation 也有可能是 Thread Pool

Fork join 1

通常會有 library 來處理，會使用 synchronous thread，也就是全部執行完畢才會回到 main thread

OpenMP#

是一種 compiler directives，可以讓 compiler 知道哪段要做平行計算

#pragma omp parallel
{
    printf("I am a parallel region.");
}
#pragma omp parallel for
for (i = 0; i < N; i++) {
    c[i] = a[i] + b[i];
}

使用者一樣不用處理 Threading 的部分

Grand Central Dispatch (GCD)#

MacOS 或是 iOS 使用的，Run-time API

GCD schedules tasks 可以把他們分成

• Serial (private) dispatch queue
• Concurrent (global) dispatch queue

可以告訴 compiler 這個大括號內是一個 block

^{ printf("I am a block"); }

dispatch_async(queue,{ print("A closure.") })

Intel Threading Building Blocks (TBB)#

可以把

for (int i = 0; i < n; i++) {
    apply(v[i]);
}

變成

parallel_for(size_t(0), n, [=](size_t i) {apply(v[i]);});

就可以讓 library 去處理 task 的 parrellel

Threading Issues#

fork() and exec() System Call#

在 Multi-thread 的情況下可能會有問題

• 有一個 Thread call fork() 的話出來的 process 需要繼承所有 thread 嗎
  • Duplicate all thread
  • Duplicate only the caller thread
• exec() 的 call 如果在 fork() 後，就沒必要 Duplicate 了

Signal Handling#

signal 在 Unix 中是用來 notify 的，通常 signal 被發出就必須 handle（但可以用 ignore 來 handle）

• Synchronous signal
  • 會送給 perform operation 的 process
• Asynchronous signal
  • 外部的操作（Ctrl+C）

每個 Signal 都有 default signal handler 也可以用 user-defined signal handler 來 overwrite，可能是 terminate 也可能是 ignore

允許的操作有

• Deliver 給專門處理 signal 的 Thread
• Deliver 給所有 Thread
• Deliver 給一部分 Thread
• Deliver 給做出操作的 Thread

Thread Cancellation#

Cancellation 不同於 Termination，是在沒結束的時候就先砍，因為時間不固定，所以要特別處理 Cancelation Point

• Deferred cancellation
• Asynchronous cancellation

要被 Cancel 的 Thread 通常叫做 target thread

Pthread Cancellation#

有三種 cancellation modes:

• disabled
• deferred
• asynchronous

pthread_t tid;
/* create the thread */
pthread_create(&tid, 0, worker, NULL);
/* cancel the thread */
pthread_cancel(tid);
/* wait for the thread to terminate */
pthread_join(tid,NULL);

pthread_testcancel() 可以設定 cancellation point

while (1) {
    /* do some work for awhile */
    ...
    /* is there a cancellation request? */
    pthread_testcancel();
}

到了 Cancelation point 才會檢查自己有沒有被 Cancel，Cancel 後會呼叫 cleanup handler

Java#

跟 Pthread 一樣是 deferred

Thread worker;
...
/* set the interruption status of the thread */
worker.interrupt()

while(!Thread.currentThread().isInterrupted()){
    ...
}

Thread-Local Storage (TLS)#

可以讓 Thread 計算的 variable 不會直接消失，有點像 static data

Scheduler Activations#

Lightweight Process (LWP)#

Two level model 我們通常都會把 kernel thread 當成一個 virtual processor，而 LWP 就是一種 virtual processor

有時候的 communication 是 bottom up 的，我們會叫他 upcall

LWP 在知道 下面發生的情況後就可以對 User Thread 做適當的處理

Operating System Examples#

Thread 角度的 Context

• A thread ID uniquely identifying the thread
• A register set representing the status of the processor
• A program counter
• User and kernel stacks, employed when the thread is running in user and kernel modes, respectively
• A private storage area used by run-time and dynamic link libraries

都應該記錄下來當作 Context