Mutex lock a software tool prevent race conditions 試圖取得使用中的 lock 會被 block，直到 lock 被釋出 Spin lock a software tool prevent race conditions 不斷在迴圈重複等待進入crical section 缺點 : busy waiting這種需要 busy waiting 的 lock 也被稱作 spinlock

Race condition 多個行程同時對同一個資料存取 存取的順序影響結果 解決辦法 : 一次僅允許一個行程存取 Critical Section 一個<font color='Orange'>程式碼片段</font>，用來放置共享變數 Critical Section Problem 必須滿足下列三個要求

Deadlock avoidance 可以利用演算法避免deadlock safe state a save sequence {P~1~, P~2~, ..., P~n~} P~i~最多可以請求的資源數 = available resources + resources held by all P~j~ , with j < i unsafe state

Bounded-Buffer Problem 兩個 process shared 下列變數 假設一個 pool 中有 n 個 buffer mutex semaphore 提供mutex exclusion 初始值為1

Basic wating time 在ready queue中等待的時間 turnaround time 進去到出來的時間

Soft real-time system 會盡量完成工作，不保證 Hard real-time system 所有工作都要在時間內完成 兩種影響效能的延遲

user-level thread 對應到一個kernel-level thread kernel 不知道user-level thread的存在 由thread libary管理 schedules user-level threads to run on an available LWP

Asymmetric multiprocessing Handle all scheduling decision by a single processor Symmetric multiprocessing Each processor is self-scheduling Cache

Deadlock Detection 系統必須提供一個演算法去檢視是否有deadlock發生 需要一個演算法來回復deadlock single instance 當有cycle的時候會發生deadlock an edge from P~i~ to P~j~ 代表 P~i~ 在等 P~j~ 釋放一個 P~i~ 需要的資源 圖(b)叫做 wait-for graph

Process Termination Abort all deadlocked processes Abort one process at a time until the deadlock cycle is eliminated 每丟棄一個process就要執行一次deadlock-detection演算法 丟棄process需要考慮很多因素，如優先權 Resource Preempt

確保四個條件中至少有一個條件不符合，這樣就能防止deadlock發生 打破 Mutual Exclusion 無法打破，除非是shared-memory例如唯讀檔(read-only files) 打破 Hold and wait Protocol 1: 能在開始執行前先得到所有資源的process才可以持有這些資源 Protocol 2: 要再申請資源前，要先釋放手中所有資源

# Thread Overview ## Thread * OS分配CPU時間的對象 * 一個thread有 * thread ID * program counter * register set * stack * process內的thread彼此分享 * code section * data section * OS resource  * 優點 * Responsiveness * 允許程式中某部分被中斷或執行很久時，該程式仍可繼續執行 * Resource sharing * 分享code、data和OS資源 * Economy * a lightweight process * Scalability * 可以在不同處理器間平行處理 ## Parallelism * perform more than one task simultaneou

# Threading Issues ## Implicit Threading * thread 由 compiler 和 run-time library 建立和管理 * 常見方法 * Thread pools * OpenMP * Grand Central Dispatch * TBB(Threading Building Blocks) ### Thread Pools * 預先建立一些 thread 等待 work * 優點 * 預先建立好，速度較快 * 執行 thread 的數量被 pool 的大小限制 ### OpenMP * Provides support for parallel programming in <font color="orange">shared-memory</font> environment * Can identify parallel regions which can run in parallel ### Grand Central Dispatch * Apple t

# Multithreading Models ## Many-to-one * 多個 user-level thread 對應到一個 kernel thread * 一個 thread 被 block 會使全部被 block * 不能平行化 * 最終只有一個 thread 在 kernel 中  ## One-to-One * 一個 user-level thread 對應到一個 kernel thread * More concurrency than many-to-one * 因為 kernel thread 數量太多會有 overhead，因此會限制 thread 的數量  ## Many-to-Many * 多個 user-level thread 對應到多個 kernel thread * 結合了 M:O 和 O:O 的優點 * 允許 OS 建立足夠的(小於等於 user-level thread 數量) ker

# Paging ## Basic * 允許process 在 physical address上的位置是不連續的 * logical memory → pages * physical memory → frames * Page number ( p ) * index of page table * Page offset ( d ) * equal to page size   * page的大小通常是2的冪次方 * If the <font color="orange">size of logical address space is 2^m^ </font> and <font color="orange">page size is 2^n^ addressing units</font> * logical address 的 * 前 $m-n$ bits 代表 page nu

# Structure of the Page Table ## Single level * 一個logical address space依據page大小切割 * 對應到一個page table(每格4byte = 32bits) * 上面記錄每個page對應到的frame ## Two level * page table 本身也是一個 page table   ## Hashed Page Tables * handling address spaces ≥ 32 bits * hash function collision 的次數等同於 TLB miss 時需要存取記憶體的次數  ## Inverted Page Table * 只用一個page table(所有process共用) * 以physical memory為對象 * 若