首頁

# Thread Introduction

  • Motivation
  • Benefits of Multithreading
    • Responsiveness：允許程式中的某部份被中斷或是執行得非常久時，該程式仍然可以繼續執行
    • Resource Sharing：分享 code、data 和 OS 資源
    • Economy：輕量化的 process。
      (context switch 一個 thread 比 process 快約 5 倍，建立一個 thread 比 process 快約 13 倍)
    • Utilization of MP arch：多個 thread 能在多個處理器平行處理

# Multicore Programming

Multithreaded programming 提供一種更有效率使用多核心的機制，改善 concurrency

concurrency : 快速切換來同時運行多個 task，但實際上同時只執行一個
多核心 / 多處理器 (multicore/multiprocessor)：無論多個運算核心是在單一或多個 CPU 晶片上，都稱為多核心 / 多處理器

  • parallelism：執行在多核心系統
    • Data Parallelism：資料分成不同 core 來執行，某段只由一個 core 執行
    • Task Parallelism：同一段資料可能有多個 core 來執行，執行不同的任務
  • concurrency：執行在單處理器或核心，支持多個任務執行

# User vs. Kernel Threads

  • User threads
    • 在 user mode 下進行，OS 不知道有這些 thread 存在也不需要 OS 介入管理
    • 即所謂 user-level threads library，支援 creation、deletion、scheduling
    • 每個 user thread 屬一個 process
    • 優點：不由 kernel 直接控制，通常在創建及管理上會比較快
    • 缺點：若 process 的 user thread 發出鎖定的 system call 且 kernel 是 single thread 則整個 process 被鎖住
    • Example：POSIX Pthreads、Win32 threads、Java threads
  • Kernel threads
    • 在 kernel mode 下進行，OS 知道有這些 thread 存在，由 OS 介入管理
    • 由 OS（kernel）直接支援 creation、deletion、scheduling，由 TCB 控制的 thread
    • kernel thread 與 process 無關
    • 優點：多個 thread 可同時發出 system call，若某個 thread 被 block 仍可由 kernel 安排其他 threads 執行工作
    • 缺點：由 kernel 進行創建及管理，速度較慢
    • Example：Windows 2000 （NT）、Solaris、Linux、Tru64 UNIX

# 挑戰

  • Dividing activities：將 program 拆成多個可以同時處理的任務
  • Data splitting：除了計算任務要拆，資料也要能夠拆開給不同任務處理。有時候 data 很複雜，不一定是平分給所有任務處理
  • Data dependency：shared data 的同步，是平行程式中最複雜且重要的部份
  • Balance：各個任務的執行時間要差不多，否則會受限於執行最久的任務
  • Testing and debugging：不知誰先誰後，而且可能會有 10 幾個 thread 同時跑

# Multi-threading models

# Many-to-One

  • 優點：mapping，user thread library（user space）決定，有效率
  • 缺點：
    • 整個 process 可能被 block
    • 無法利用多核心，因為只有一個 kernel thread

# One-to-One

  • 優點：More concurrency
  • 缺點：
    • 成本較高
    • Overhead，每創一個 user thread 就要創一個 kernel thread
    • 要限制執行緒產生的個數，產生一個 user thread 時需連帶產生一個 kernel thread，而 kernel thread 會對程式的執行產生一些額外的負擔

# Many-to-Many

  • 允許 developer create 他想要的 thread 數量
  • 優點：
    • 系統不會被 single thread 執行鎖死
    • 比 one-to-one 經濟
    • 可以多個 thread 平行跑在多個處理器
    • 當一個 thread 執行到 blocking call，kernel 能排程另一個 thread 進來執行

# Two-level model

  • 類似多對多，但允許使用者執行緒被綁到一個核心執行緒

# Threaded Case Study

# Shared-Memory Programming

  • 定義
    • process 互相溝通透過一塊共享的記憶體
    • 比 message passing 更快，有效率
  • 議題
    • Synchronization
    • Deadlock
    • Cache coherence
  • Programming techniques
    • Parallelizing compiler
    • Unix processes
    • Threads (Pthread, Java)

# Thread libraries

# Pthreads

POSIX standard for thread Operating 的實作

  • pthread_create (thread, attr, routine, arg)：創一個新的 thread
    • thread：回傳的 thread id
    • attr：thread attributes (NULL 為預設)
    • routine：thread 要執行的 function
    • arg：傳給 routine 的參數
  • pthread_join (threadId, status)：block 住直到特定的 thread terminate，完成 thread 之間的同步化
  • pthread_detach(threadId)：
    • 當一個 thread 被分離，之後就不能被 join
    • 分離一個 thread，會 free 掉一些系統資源

# Java threads

  • thread creation
    • Extending Thread class
    • Implementing the Runnable interface
  • Java threads 用 thread library on the host system 實作
  • Thread mapping 依據 JVM 的實作

# Linux Threads

  • 不支援 multithreading
  • Pthreads 實作 are available for user-level
  • fork system call – 創一個新的 process 和一份父行程的相關 data 的 copy
  • clone system call – 創一個新的 process 和一個 link 指到父行程的相關 data
    • 一組 flag 表 sharing 的程度
    • 沒有 flag 升起 –> 等同 fork ()
    • 全部 flag 升起

# Threading Issues

  1. Semantics of fork() and exec() ，fork 呼叫一個 thread 或 all thread?
    Undefined. maybe the following
    • 只 fork 該 thread : 當 child 做工作與 parent 不同
    • fork 整個 process : 當 child 所做的工作與 parent 相同
  2. Signal handling
    • default 由編輯器自動載入預設的訊號處理
    • user-defined 自行定義訊號的處理

    [補充] process 或裝置通知 kernel -> interrupt；kernel 通知 process -> signal

  3. Thread cancellation
    • asynchronous cancellation : 立刻取消
    • deferred cancellation : 一個時間周期到才會取消
    • actual cancellation : 根據 thread 狀態取消
  4. Thread pools
    • 產生多個 thread 並等待執行，因為使用現有 thread 比新產生一個 thread 快
    • 此法等待執行的 thread 數目前依目前 thread pool 大小決定
  5. TLS (thread-local storage)
    • TLS 要解決的問題，並不是 Thread 之間資源共享的問題，而是 Thread 本身資源共享的問題
    • TLS 是在 thread 中佈置一塊空間，並讓 thread 外面可以觀測
  6. Light weight process (LWP)
    • 介於 user-level thread 和 kernel-level thread 的資料結構，用來提供一個 virtual process 讓應用程式 thread 做排程
    • 支援多個 User-level Thread 對應到一個 kernel thread，屬於 kernel-level thread
  7. Thread libraries : pthreads
    Pthreads (POSIX threads) 是依據 ieee 1003.1c 標準定義的 thread 標準，定義了創建和操縱 thread 的一套 API，可用在 user-level 和 kernel-level，常用在一般 Unix 作業系統。
  8. Implicit threading methods
    • thread pools
    • openMP
    • grand central dispatch
    • TBB (threading building blocks)

# Ref Notes

  • Kipper’s Note
  • Chang-Chia-Chi’s Note
  • 陳品媛的筆記
  • Mr. Opengate. OS - Ch4
  • WillyWangkaa’s Note