Chp 4 Threads

tags: 作業系統

• Chp 4 Threads
  • Overview
    • Motivation
    • Benifits
  • Multicore Programming
    • Issues of Programming
    • Parallelism V.S Concurrency
    • Amdahl’s Law
  • Multithreading Models
  • Thread Libraries(待補)
    • Pthread
  • Implicit Threading
    • Thread Pools
    • OpenMP
    • Grand Central Dispatch
  • Threading Issues
    • Signal Handling (待補)
    • Thread Cancellation (待補)
    • Thread-Local Storage (TLS)
    • Scheduler Activations

Overview

Motivation

(原因待補)

1. Process creation:
   • heavy-weight
2. Thread creation:
   • light-weight

context switch, memory allocate
Omnom

創一個process就要重新allocate一塊記憶體給他，連帶也造成Process之間的資料傳遞比較麻煩，相比之下不同的thread仍然是在同一個記憶體空間(main process)
Neko

增加處理的平行度
Peter

• simplify code, increase efficiency

• 考 Provide two case that multithreading does not provide better performance than a single-threaded solution:

  1. sequential program: e.g. calculates an individual tax return
  2. shell program: e.g. C-shell or Korn shell

• 考 multiple kernel threads provide better performance than a single-threaded solution:

  • page fault, another kernel thread can be switched in to use the interleaving time in a useful manner
  • single-threaded process will not be capable of performing useful work when a page fault takes

Benifits

• Responsiveness – allow continued execution if part of process is blocked
• Resource Sharing – thread sharing is easier than shared memory or message passing
• Economy – cheaper than process creation, thread switching lower overhead than context switching
• Scalability – process can take advantage of multiprocessor architectures

Multicore Programming

Issues of Programming

1. Dividing activities
2. Balance
3. Data splitting
4. Data dependency
5. Testing and debugging

Parallelism V.S Concurrency

考

• Parallelism: perform more than one task simultaneously, at least two threads are executing simultaneously, e.g. multicore processor
• Concurrency: support more than one task making progress, two or more tasks can start, run, and complete in overlapping time periods, e.g. multitasking on a single-core processer

Parallelism VS Concurrency
Omnom

• Types
  1. Data Parallelism
     • distribute data across multiple cores
       e.g. Multiple same task, different data
       (每個core執行相同的operation，只是每個core用的data不一樣)
  2. Task parallelism
     • distribute tasks(threads) across multiple cores
       e.g. Same data with multiple different tasks
       (每個core(thread)執行不同的task，可能會用一樣的data)

看到一個不錯的例子
150份15題的考卷分給三個助教去改，若是data parallelism的作法，則每一個助教分別改50份考卷；若是task parallelism的方法，則每一個助教分別改150份考卷的前、中、後5題。瞭解嗎？這裡可以分析每個助教的負擔，乍看下是一樣的，然而後者方法中每個助教分別對前、中、後5題有高度熟悉感，那麼後者的方法可以有很好的效能，一下子就把考卷給改完！而前者方法中每個助教都批改15題，無法發揮所長，效能因此較不彰。 參考
Peter Peter

Amdahl’s Law

$S$: Serial portion,

$1-S$: parallel portion

$N$: # of processing core

$speedup\le \frac{1}{S+\frac{1-S}{N}}$

• $N\to \mathrm{\infty },speedup\to 1/S$

Multithreading Models

• user_thread-to-kernel_thread

1. Many-to-One(Few system use it)
   • Many user-level threads mapped to single kernel thread
   • Pro
     1. Thread management is done by the thread library in user space, so it is efficient (?)
     2. allows the developer to create as many user threads as she wishes
   • Con
     1. the entire process will block if a thread makes a blocking system call
     2. only one thread can access the kernel at a time → unable be parallel

2. One-to-One

   • Creating a user-level thread creates a kernel thread
   • Pro
     1. provides more concurrency
     2. allows multiple threads to run in parallel
   • Con
     1. large number of kernel threads may burden the performance

3. Many-to-Many

   • Pro
     1. Has advantages from both Many-to-One & One-to-One
   • Con
     1. in practice it is difficult to implement

4. Two-level (Variation of Many-to-Many)

考

• number of kernel threads < number of processors:
  • some of the processors would remain idle
• number of kernel threads == the number of processors
  • all of the processors might be utilized simultaneously
• kernel threads > processors
  • a blocked kernel thread could be swapped out, in favor of another kernel thread that is ready to execute

Thread Libraries(待補)

Pthread

• Specification, not implementation

說"標準"的原因是Pthread是符合POSIX規範的Thread API，POSIX為可移植作業系統介面，就是說只要函式庫符合POSIX規範，都能夠在支援POSIX規範的系統上運作，至於函式庫的內容是如何實作的就不是很重要了，只要行為符合就好，比方說函式庫是使用哪一種multithread model是沒有規定的。
推出這個規範是因為Unix系統分支太氾濫，有很多Unix-like的作業系統但是又不全然可以移植程式，為了解決這個問題就誕生了POSIX
Neko

Implicit Threading

• Concept: transfer the creation and management of threading from application developers to compilers and run-time libraries.

• Note: require application developers to identify tasks—not threads—that can run in parallel

Thread Pools

• Mechanism: Create a number of threads in a pool
• Note: create multiple in advance
• Pro
  1. Servicing a request with an existing thread is often faster
  2. thread pool limits the number of threads → limit concurrent threads
  3. Separate task performing from task creating → flexibility to run tasks

OpenMP

• API for programs written in C, C++, or FORTRAN that provides support for parallel programming in shared-memory environments

• Mechanism: Identifies parallel regions – blocks of code that can run in parallel

Grand Central Dispatch

• Mechanism:

  1. identification of parallel sections (Block)
  2. Blocks placed in dispatch queue
  3. Assigned to available thread in thread pool when removed from queue

• Type of dispatch queues

  1. serial:
     • one goes out FIFO
     • called main queue
  2. concurrent
     • several go out FIFO

Threading Issues

Signal Handling (待補)

• Procedure:
  1. A signal is generated by the occurrence of a particular event.
  2. The signal is delivered to a process.
  3. Once delivered, the signal must be handled.
• default signal handler
  1. runned by kernel
  2. can be overridden by user-defined signal handler

Thread Cancellation (待補)

Note: actual cancellation depends on thread state

1. Asynchronous cancellation
   terminates the target thread immediately
   會有後遺症，資料不一致，影響另一個Thread的資訊，

補充說明：[摘自老師]
target thread 可能正在處理還沒處理完的工作，舉例來說：和其他 thread 可能有 shared data。一旦任意將 target thread cancel，可能造成資料不一致，「影響另一個Thread資訊的正確性？」
突然中止，可能導致工作無法正確交接，造成錯誤
Omnom

2. Deferred cancellation
   allows the target thread to periodically check if it should be cancelled

Thread-Local Storage (TLS)

• Uniqueness: each thread have its own copy of data
• TLS v.s. local variables
  • visibility:
    across function invocations
    v.s.
    during single function invocation

Scheduler Activations

M:M and Two-level models require communication

Each LWP is attached to a kernel thread

考

• lightweight process (LWP):
  • intermediate data structure between user and kernel threads(對user process來說相當於virtural process是virtual processor)
  • User thread 要mapping到kernel thread才能做scheduling

不確定上面描述的內容想表達的跟我想表達的是不是一樣，總之做個補充。
我們可以想成LWP是一個虛擬的處理器，會執行Process，Process裡面是User thread，一個LWP可以有同一個Process的好幾個thread，這些thread在LWP上面做scheduling的工作(就是決定這些thread要怎麼樣執行)。
正如課堂所說，OS並不知道User thread有多少，這些也不是他要管的。OS要做的事情是kernel thread的scheduling，而每一個LWP都會關聯到一個kernel thread。
每個層級schedule的對象不大一樣
Neko

• upcalls: a communication mechanism from the kernel to the upcall handler in the thread library