---
robots: index, follow
tags: NCTU, CS, 共筆
description: 交大資工課程學習筆記
lang: zh-tw
dir: ltr
breaks: true
disqus: calee
GA: UA-100433652-1
---
作業系統概論 -- 蔡文錦
======

## Syllabus
- Grading
- mid + final: 60%
- 4-5 HW: 25%
- quiz: 15% (隨堂)
- Textbook: [Operating System Concepts, by Abraham Silberschatz, Peter B. Galvin, Greg Gagne. WILEY, Ninth Edition](https://it325blog.files.wordpress.com/2012/09/operating-system-concepts-7-th-edition.pdf)
- 1~7 midterm
- 8~13 final
- 參考: http://mropengate.blogspot.tw/2017/09/operating-system-concepts.html

## Ch1 Introduction
- OS Goals
- 執行程式
- 更有效的執行
- 更方便好用
- Different
- PC: 好用，方便
- share computer: 平行，資源分配
- Handheld: 省資源，電力
- Embedded: 不用 user interface
- OS is
- 資源分配器
- 控制程式
- "The one program running at all times on the computer" is the *kernel*
- ...

- 開機順序
- bootstrap program
- 在韌體(firmware)中，存在 ROM 或 EPROM
- CPU, mem, device controler...
- load OS kernel and start run
- Kernel starts
- start "init" (Root of tree structured processes)
- start daemons
- Interrupts(中斷)
- 停止目前的 job -> error handling
- Hardware 隨時可以觸發 interrupts，並傳訊息告訴 CPU
- Software 觸發: trap / exception / return 1 / systme call / ...
- Interrupt Service Routine (ISR)
- 當 CPU 被中斷時，會馬上終止並執行 ISR
- ISR 完成時，CPU 會恢復並繼續執行被中斷時的指令
- 但是 CPU 該跳到 ISR 的哪裡呢？
1. 可能是 ISR 都只有一個寫死的入口，進入之後再檢查是哪一種錯誤
2. 可能是有一個 interrupt vector，照著上面寫的入口(依 divice ID 查找)，跳到正確的 ISR 入口
- ISR 結束時，如何回到上次的指令？
- 可能需要儲存一下中斷時的狀態 (用 soring registers 與 PC 存)
- PC(program counter) 要被存起來
- Storage
- Main memory
- CPU 只能碰到 Main memory
- Random access, volatile (SRAM DRAM)
- non-volatile: EEPROM, ROM (bootstrap[first program] 放在的地方)
- Secondary storage
- large nonvolatile storage
- Magnetic disks
- Solid-state disks(SSD)
- Caching
- 如何選擇哪些要 cache 便是一個學問了
- I/O
- IO 與 CPU 可以同時工作
- Flow
- CPU 傳送指令到 register
- CPU/divice 傳送訊息存進 buffer
- 執行 IO
- 傳送 interup 給 CPU 說我執行完了
- CPU 再去 buffer 抓資料
- Direct Memory Access (DMA)
- 另一種執行方式
- 將搬運的角色換成 device(DMA)
- DMA 主動執行搬運資料回 Main mem 的角色，所以可以全部般完之後，再一次 Interupted 給 CPU，不用向上一個方式，每次搬運都要 call CPU 一次
- Processor System
- Single Processor System
- 只有一個 CPU
- 但是 CPU 現在遇到了 4GHz 的瓶頸了
- 
- Clustered System
- 每個節點都是可以獨立執行的系統
- 多個系統利用網路，一起合作
- Usually sharing Storage
- 
- Asymmetric clustering
- 有一個主線，其他都是備胎(stand-by mode)
- 只有在主線 fail 時，備胎才會取代他
- Symmetric clustering
- 多個節點(系統)同時在跑應用程式，並且互相監控
- Multiprocessors systems(parallel systems, tightly-coupled systems)
- 上一個只有到 share storage，這個可以 share memory
- 
- Asymmetric Multiprocessing (master-slave relationship)
- 只有一個 CPU 是 master(作比較重要的事)，其他都是 slave
- Sysmmetric Multiprocessing (對稱式多重處理)
- 最常見
- 每個 CPU 在系統所處的地位級發揮的功能都一樣，是相互對稱
- Multiprocessors system(Multicore)(多核心)
- 更有效
- 將多個處理器，合併在一起打包出售(在同一個 chip 裡)
- one-chip communication
- 共用 cache
- 比上一個更省電
- 
- OS Structure
- Multiprogramming
- 當 process 在等 IO 時，可以選擇自動把 CPU 交出去，可以讓 System 不會 han 住
- But 是 process 自動交出去，但是 Process 可以不要交出去，System 還是會 han 住
- Timesharing (multitasking)
- create interactive computing
- CPU scheduling
- Virtual memory
- 強破 Process 在一定時間(很短的時間內)後，一定要把 CPU 交出去
- 時間間隔很小，Switch 很頻繁 => 會看起來好像 process 還是一直往前跑
- OS Operations
- 保護 OS 不被攻擊
- Dual-mode
- 將 System 分為 User mode 和 kernel mode
- mode bit
- 分辨是 user code or kernel code
- privileged instruction: 提權
- multi-mode
- i.e. virtual machine manager (VMM) for guest VMs
- 
- 提權方法
- 利用 timer
- 
1. Process Management
- 正在跑得程式叫做 process
- program: passive entity
- process: active entity
- process 需要資源
- CPU / memory / I/O / file
- Initialization
- process 結束時，需要把資源還回去
- thread & program counter
- multi thread 每個 thread 都有一個 PC
- Process Management Activities
- create/delete
- supend/rusume
- process synchronization: 同步
- process communication
- deadlock
2. Memory Management
3. Storage Management
- 抽象化: 把儲存實作隱藏
- OS 把東西存在 file system，storage 自己解決 file system 要怎麼存
- Mass Storage Management
- swap
- cache coherency: 緩存一致性
4. I/O Subsystem
- buffering, caching, spooling
- device-driver interface
5. Protection and Security
- Protection:
- 資源的 access control
- 權限劃分 (uid, gid, pid)
- Security:
- 保護 OS 被內部或外部攻擊
- Kernel Data Structure
- linked list
- Singly linked list (單向)
- Doubly linked list (雙向)
- Circular linked list (環)
- Stack (LIFO)
- Queue (FIFO)
- Binary search tree
- left child <= right child
- Balanced binary search tree
- hash & hashing map
- Bitmap

## Ch2 System Structures
- Operation System Service
- Interface
- CLI (command line interface)
- in kernel or in system program
- multiple CLIs are implement -- shell
- fetches command from user and executes
- GUI (Graphic User Interface)
- mouse, keyboard, monitor
- icons
- mouse
- Other interface
- touchscreen
- System Call
- 通常都直接用高階語言介面(API)，在轉 call System Call，而不會直接用 System Call
- ex. Win32 API, POXIX API, Java API
- 傳遞參數
1. 利用 register 傳遞(存在 registers 裡)
- 可能 reg 會不夠用
2. register 只存 data 所在的 memory 的 start address
- Linux & Solaris 用
3. push pop stack (在 memory 中)
- System Call 種類
- File
- Information
- Device
- Protection
- Communication
- create, delete
- send, receive
- message passing model (A->B)
- process call system call
- copy msg from A to kernel base
- copy msg from kernel base to B
- shared memory model
- 在 memory 中在開一個空間
- msg 直接存到新開的空間中
- A, B 兩個都可以直接 access 這個空間
- 適合大量 msg
- System 需要處理同時使用這個空間的規則(不能同時寫入等等的規則[複寫])
- transfer status information
- attach, detach divice
- Operating System Design and Implementation
- Policy: What will be done (interface)
- Mechanism: How to do (implement)
- assembly language
- now, 用高階語言實作(C, Java)
- Simple Structure
MS-DOS
- 沒有切 modules
- UNIX
- Layered Approach
- 每層 layer 只能 call 比他底下一層的 api
- 比較簡單控制, debug(每次只要檢查那層的 bug)
- 有時候比較沒有效能，或者不好切 layer
- Microkernel
- ex. WinNT
- kernel 包住了三個最重要的部分
- inter-process communication
- memory managment
- CPU scheduling
- 其他那麼重要的部分，以 user mode 執行
- 用 message passing 讓次等功能互相溝通
- 好處
- 好擴展(因為除了三個部分外，剩下的程式都放在外面，所以可以直接撰寫外面的程式)
- 好改架構
- 更穩定 (kernel 小，更好保證穩定)
- 更安全 (比較不重要的功能都是用 user mode 在跑)
- 壞處
- 溝通的部分並不有效 (message passing)
- 
- Modules
- kernel modules
- 切功能
- 比 layer structure 更彈性
- lazy load: 不需要用到時，不會被 load 出來 (有點像 lib 的概念)
- 
- Hybrid Systems
- 混合多種系統
- ex. Mac OS X 同時用了 BSD(UNIX) 與 Mach(micro)

## Ch3 Process Concept
- Program (passive)
- Batch system = jobs
- Time-shared systems = user programs / tasks
- Process (active)
- 跑起來的程式
- 分層
- text
- data (global variable)
- heap (dynamically allocated)
- stack (local variable)
- 
- Process State
- new: 剛跑起來，OS 會 allocate 一些空間跟資源，loader 會跑起來
- running: CPU 跑起來
- waiting: 也在等待，但是有東西還沒準備好，像是 I/O divice
- ready: 準備的東西都好了，等待 CPU 讓他跑起來 (因為 time sharing，所以 CPU 可能還沒跑他)
- terminated
- 
- Process Control Block (PCB)
- (also called task control block (TCB))
- 當 process 要換成另一個 process 時，需要把資訊記起來
- Process state (上面的)
- Program counter
- CPU registers
- CPU scheduling
- Memory management
- Accounting info
- I/O status info
- 
- 

- Threads
- 如果 process 有多個 program counter -> 是不是就可以同時作互不干擾(independent)的事情
- PCB 裡需要有 multiple program counter
- Process Schedule
- 選擇下一個 CPU 該跳去做的 process
- schedule queue
- job queue: all process
- ready queue: ready process
- divice queue: waite for divice process
- Schedule
- long-term (job) -> multiprogramming
- short-term (CPU)
- medium-term (swapping)
- Context switch
- CPU 跳來跳去，OS 應該要存 state 與 載入 state
- Context == PCB
- lock
- Process Create
- Parent / Children / tree
- pid, ppid
- 資源分享種類
- 全部共用 (同等地位)
- child 分享 parent 資源的 subset
- 無法共用
- 執行種類
- 同時執行 ex. fock bomb
- parent 等到 child 執行完才繼續做事(wait) ex. 遞迴
- 先 fock() 自己，再 exec() children
- cpid = fock()
- wait({status pointer}): 在任意一個子程序結束後，會觸發 wait，wait 回傳結束的那個子程序，status pointer 用來存執行完的子程序的 return code
- abort(): 直接收回子程序
- 如果 parent 結束 child 還沒結束(沒被收回)，叫做孤兒(ophans)
- 如果沒有 parent 等待的子程序死掉之後，就做 zonbe，因為父程序沒有 wait，所以 pid 還存在，資源就不會被收回 => 不優
- indenpent / cooperator process
- cooperation process 需要 interprocess communication (IPC)
- 兩種 IPC
- Shared memory
- Message passing
- Synchronization (同步)
- Blocking
- 同步的
- 要等待
- Non-blocking
- 非同步的 (可平行)
- sender / receiver
- Buffing
- Queue
- Zero capacity (no buffering)
- Bounded capacity: 有限多個 msg，sender 要等待塞滿
- Unbounded capacity: 無線多 msg，sender 無須等待
- Linux IPC System
- POSIX shared memory
- create 一個 shared memory，同時打開他(讓可以被其他人看到)
- 設定 size
- Mach
- Windows
- Client / Server
#### 之前講的都是同一台機器上的溝通 => 在不同機器: Web
- Sockets
- IP & port
- TCP / UDP
- Remote Procedure Calls (RPC)
- 可以 call 一個 function，但事實上，這個 function 是執行在其他機器上
- Stubs: client proxy 事實上在 server 上運行的程序
- marshalls (打包) 參數到 server 上
- External Data Representation (XDR) format (避免不同架構差別，要用統一的表示格式)
- big-endian / little-endian
- Pipes
- ordinary pipe
- 兩個程序可以互相溝通
- 溝通是單向(unidirectional)或雙向(bidirectional)的？
- half-duplex(一方傳資料時，另一方不能同時傳送) vs. full-duplex(兩方可以同時傳送資料)
- 不需要是 parent-child 架構
- anonymous pipe
- parent-child 架構
- read write 溝通透過檔案
- name pipe
- 雙向
- not parent-child
- 多個 process 可以同時用 name pipe
- mkfifo() / CreateNamePipe()

## Ch4 Multithreaded Programming
- thread
- CPU utilization 的基本單位
- 有 PC, stack, registers
- 一個 process 可以有多個 thread
- 一個 process 的 thread 除了 stack / heap / register 之外的東西都會共用
- 
- 動機
- 一個應用理的多個功能，可以被分工到不同的 thread 下執行
- thread 比 process 輕量
- 簡化 code, 增加效能
- Benefits
- Responsiveness
- 在部分 process 被 block 住時，可以繼續執行
- Resource Sharing
- 因為很多部分共用 (data)，所以比 share memory 或 message passing 簡單
- Economy
- 消耗的資源較低 (因為資源共享等等)
- Scalability
- 可以跑 multiprocessor 的架構
- Multicore programming
- 對開發者不友善
- dividing activities, balance, data splitting, data dependency, and debug：很多東西要處理
- Concurrency (並行)
- 可以在 task 與 task 上作切換，產生並行的效果
- Parallelism (平行)
- Data parallelism
- 將資料分散
- Task parallelism
- 將 task 分散
- concurrency vs thread
- 
- Amdahl’s Law
- 平行處理的加速比是平行前的速度與平行後的速度的比值
- Ws: 問題中不可平行的規模
- Wp: 問題中可平行的規模
- p: 總共執行序數量
- $speedup = \dfrac{W_s + W_p}{W_s + \frac{W_p}{p}}$
- User / Kernel thread
- User threads
- user-level threads library
- Kernel threads
- Thread library
- API
- user space / kernel-level
- POSIX Pthreads / Win32 threads / Java threads
- Multithreading Models
- Many-to-One
- 
- 多個 user-level thread map 到 kernel-level
- thread lib 作 management
- 有一個 thread blocking 就會造成全部 thread block 住
- 雖然多個 thread，但是不能在 multicore system 下平行，因為一次只能有一個進入 kernel-level
- One-to-One
- 
- 一個 user，一個 kernel
- kernel 作 management
- 可平行
- 每個 process 的 thread 數量受限於 overhead
- Many-to-Many Model
- 
- 多對多
- OS 可以製造足夠多的 kernel thread (<= user thread)
- Two-level Model
- 
- 可以 M:M 也可以 O:O
- Pthreads (並行線程)
- user-level or kernel-level 都可以
- POSIX standard (IEEE 1003.1c) API
- 是規範，不是實作 (兩種實作)
- UNIX like OS 很常見
- Java Threads
- JVM 實作
- Implicit Threading (隱含線程)
- 用多線程很方便，現在的線程數量又可以開很大 -> 已經無法很明確多說要多少線程了 (多多益善)
- 所以 thread 的 創立與管理多是改用 compiler 跟 run-time lib 來處理
- 常見管理方法:
- Thread Pools
- 一開始就在 pool 裡開出一些 thread
- 當需要時，存 pool 裡被 allocate，不需要時回到 pool
- pool 裡沒有 thread 時，process 就要等到有 thread 回到 pool 才能繼續工作
- 使用現有 thread 比創建略快一點
- 好控制 process 的 thread
- OpenMP
- compiler 指令與 API
- 支持平行運算時的 share memory
- 可以在 preprocess 的階段，用 `# #pragma omp parallel` 讓 compiler 知道這是要平行(thread)的區段
- 
- Grand Central Dispatch (GCD)
- Threading Issue
- ???
- Signal Handling
- 訊號觸發
- 特殊事件觸發產生
- 傳送到 process
- 一到兩個 signal handler 來處理: Default or user-defined
- 每個訊號都有 kernel 提供的 default handler
- user 可以用 User-defined signal handler overwrite
- 對於單線程，訊號直接傳給 process
- But 多線程呢？
- 將訊號傳給負責處理訊號的 thread
- 將訊號傳給 process 的每一個 thread
- 將訊號傳給特定的 thread
- 指定一個 thread 來處理所有 signal
- UNIX 可以讓每個 thread 自己決定要 accept 哪些 signal
- Thread Cancellation
- Cancellation: 在 thread 完成前終止他
- 不再需要工作的 thread 可能被其他 thread cancelled
- Asynchronous Cancellation: 異步取消，立即終止 (資源分配與 thread 之間的資料傳遞可能會出問題)
- Deferred Cancellation: 推遲取消，力一個 flag，表示這個 thread 可以取消了，然後 process 會定期檢查 flag，看到有立 flag 的 thread 就會取消他
- 
- Thread-Local Storage (TLS)
- thread 會共享 data，這是 thread 的好處，但是有時候 thread 也需要自己獨立的 data => thread-local storage
- 允許每個 thread 有自己版本的資料 (copy of data)
- 大部分 lib 都有提供 (java, win32, pThreads...)
- 與 local varable 差別 (stack 沒有共享): local varable 只在 function 裡看得到，TLS 是所有 function 都看得到 (有點像全域變數)

## Ch5 Process Scheduling
- Short-term scheduler
- scheduling 發生時機
1. running -> waiting
2. running -> ready
3. waiting -> ready
4. terminates
- Nonpreemptive (cooperative) CPU 不能主動中斷，需要自己放棄 CPU 的使用權: 1, 4
- Preemptive
- access to shared memory
- in kernel mode
- Dispatcher
- 是一個用來作 switching 的 module
- switching context
- switching to user mode
- jumping to the proper location in the user program to restart that program
- dispatcher latency
- 作 switching 中 delay 的時間 (會把一個 process 關掉，在開另一個)
- Scheduling Criteria(標準)
- CPU utilization: 讓 CPU 盡可能的 buzy
- Throughput(吞吐量): 每個單位時間內，完成的 process 的數量
- Turnaround time: 全部的時間，包含在 CPU 運行的時間與在 waiting queue, ready queue, ... 的時間 (complete time - arrival time)
- Waiting time: 只有紀錄在 ready queue 的時間 (turnaround time - CPU burst)
- Response time: 寄出 request 到收到 response 的時間(第一次開始執行 - arrival time)
- 需要
- Max CPU utilization, Max throughput
- Min turnaround time, Min waiting time, Min response time
- Scheduling Algo.
- ex. 當 p1, p2, p3 三個 process 同時進來時 (在 FIFO)
- 
- waiting time: p1 是 0, p2 是 24, p3 是 27
- Turnaround time: p1 是 24, p2 是 27, p3 是 30
- SJF：如果把 FIFO 改成先作 p2, p1, p3
- 
- 發現 average waiting time 會比較小！！ (3 < 17)
- Convoy effect: 把短的 process 放在長的 process 之後 => 會有不好的影響
- SJF (Shortest Job First)
- 讓短的 process 先作
- 最好的 average waiting time
- waiting time == response time
- 不好實踐 (需要預知每個 process 的 burst time)
- 可能用過去的 burst 來修正預測未來的 burst time
- 實作:
- 對於同一個 process 的每一次執行作修正
- 
- 會逐漸收斂
- 上面講的是在 process 同時到來的情況下，但是 process 很明顯的，通常不會同時來
- SRTF (Shortest Remaining Time First)
- preemptive
- OS 可以強迫 running process 釋放 CPU
- 
- 在沒有同時來時，如果有新的 process (p2) 來了，若發現 p1 的 **剩餘時間(Remaining time)** 比 p2 還要久，OS 可以叫 CPU 先作 p2
- *在這裡算 average wait 要記得減掉 process 進來的時間以及加上中途停止進入等待狀態的時間*
- non-preemptive
- OS 無法停止已經在跑得 process
- 跑完整個 process 後，排序進 queue 的程序
- Priority Scheduling Problem
- 在每個 process 創建時，就會有一個 priority number 跟著
- 一樣有分 premptive 和 non-premptive
- 曾經出現過有一個 process 因為 priority 太低，直到機器關機之前都拿不到權限跑起來 -> starvation
- => Aging: 當時間增加之後，在 waiting 裡的 process 的 priority 會增加，等越久，priority 會提越高
- Round Robin(RR)
- 只有在 premptive 的機器下才能
- 有一個 time quantum，每次只能執行 time quantum 的時間，執行完後會強制結束並且放在 queue 的最後面
- 用 FIFO 來排
- 如果執行被中斷的 process 回到 queue 的時間與新進來的 process 同時，新進來的會排在前面
- time quantum 必須夠大，如果不夠大，avrage turnaround time 會變得很大
- ex pA: b: 10, arr: 0; pB: b: 10, arr: 0; pC: b: 10, arr:0
- 如果 q = 1 => avrage turnaround 會是 29
- 如果 q = 10 => avrage turnaround 會是 20
- Multilevel Queue
- 多個不同的 scheduling algo 一起用
- 分成 foreground(interactive) 與 background(batch)
- ex.
- freground 用 RR
- background 用 FCFS
- 兩個 queue 間的 schedule:
- 用 priority: 可能把 foreground queue 的 priority 調高 => 可是可能會造成 starvation
- 用 time slice: 把兩個 queue 的可執行時間()分開，讓 foreground 的可執行時間比較高
- 
- Multilevel Feedback Queue
- process 可以在不同的 queue 中移動 => aging 可以用這種方式實作
- 定義
- 多個 queue
- 每個 queue 有自己的 scheduling algo
- 決定何時升級、降級
- ex.
- 
- Starvation
- 有 process 可能永遠做不到
- FCFS(queue) => impossible
- SJF => possible
- SRF => possible
- priority base => possible
- RR(輪流發言) => impossible
- Real-Time CPU Scheduling
- 不是說每個 CPU 要 run 很快，而是要盡量滿足每個 task 都在 deadline 前完成
- Soft real-time system
- 雖然希望在 deadline 之前完成，但是沒有那麼嚴格
- Hard real-time system
- 如果到達 deadline，會有很嚴重的後果
- latencies
- 
- Interrupt latency
- 
- 存收到 interrupt 到 CPU 開始執行 ISR
- Dispatch latency
- 
- conflict phase
- 把舊的 process 的東西清掉
- free CPU
- free resouse
- dispatch phase
- 把新的 process 載入
- Priority Base Real time
- 只保證 soft real-time
- Rate Montonic Scheduling(RMS)
- 存在三個數值
- process time t
- deadline d
- period p
- 0 <= t <= d <= p
- priority
- 選 p 小的 (rate 高) 先作
- utilization
- process time / period time
- 即使 CPU utilization 小於 100%，但也不保證 RMS 可以讓每個 process 都可以做到
- 理論上我們希望 utilization 越高 => 代表 CPU 很有效的利用
- 但是 utilization 越高，就越不可能滿足所有 process 都在 deadline 之前做完
- ex.
- 
- (在 static priority 之中)如果 RMS 都無法讓所有 process 滿足在 deadline 之前做完，那就沒有算法可以保證滿足了
- static priority: priority 永遠一樣 (ex. 不會應為 wait time 比較久，priority 就變高)
- Earliest Deadline First Scheduling (EDF)
- 一樣有 p, d, t
- 每次做完 t 或來到 p 都會在重新檢查一次
- 每次比 priority 時，都是比較目前這幾個 process 的 deadline 誰的最接近目前的時間點，最接近的 priority 就最高
- 
- Proportional Share Scheduling
- 不是 real-time scheduling algo.
- 希望保證在 T 個 time unit，每個 process 都可以拿到 CPU
- 每個人所要的時間是以比例來要求，得到 n/T 的時間
- POSIX Real-Time Schedule
- 真 Scheduling Algo. (OS 真的在用的)
- Linux:
- O(1) Scheduler
- (2 priority range)real-time(0-99) time-sharing(100-140)
- real-time pri: static
- time-sharing: dynamic
- two priority arrays for each processor: activeand expired
- array to link list
- 
- CFS (Completely Fair Scheduler)
- nice value
- virtual run time
- 用 banance binary tree(R-B Tree) 來維護 virtual run time，越左邊的 virtual run time 越少
- Windows
- priority-based preemptive scheduling
- 32 level
- scheduler 叫做 dispatcher
- 即時的 thread 可以搶佔非即時的 thread
- real-time class 16-31, variable class 0-15
- 有一個 idle thread 是在沒有可跑的 thread 的時候跑的
- Solaris
- Algorithm Evaluation
- OS 該如何選擇 scheduling algorithm?
- 四種方法
- 計算
- 模擬
- 公式
- 實幹

## Ch6 Process Synchronization
[參考](https://sls.weco.net/node/21326)
- Background
- Process 可能同時執行 (execute concurrently)
- 同時 access share data 可能造成錯誤 (race condition)
- 用計數(count)來處理
- 分 Producer 跟 Consumer
- Race Condition
- 經典問題，不多作解釋 XD
- 關鍵問題點：
- 將每個 process 分為關鍵區塊 (critical section)
- 在這些區段中，process 可能會改變變數
- 一個 process 在關鍵區段時，其他 process 不應該也在關鍵區段
- 當要進入關鍵區段(entry section)時，要先詢問是否可以進入
- 進入時紀錄權限
- 離開時，修改權限
- 解決方法
- Mutual Exclusion
- 在一個 process 在 critical section 時，其他的就不能進入
- Progress
- 如果沒有人在 critical，又有很多 process 在等待進入 critical 時，選擇誰要進入是不應該延遲的 => 不應該出現 dead lock
- Bounded waiting
- 等待進入 critical 的 process 不應該 stavation
- Preemptive kernel: 可以中斷 process
- 更即時性
- Non-Preemptive kernel: 不能中斷 process
- 基本上不會有 race condition
- Peterson’s Solution
- 針對兩個 process
- turn: 記入換誰可以進入 cri
- flag[i]: 紀錄誰想要進入 cri
- Synchronization Hardware
-

- 用 locking 方法解決
- 單處理器：
- 正在跑得 process 會鎖住，讓其他人不能跑
- 對多處理器沒有效率
- special atomic hardware instructions
- Atomic = non-interruptible
- test_and_set instruction
- compare_and_swap instruction
- Mutex Lock
- Mutex是一把鑰匙，一個人拿了就可進入一個房間，出來的時候把鑰匙交給隊列的第一個。
- Semaphore
- 一件可以容納N人的房間，如果人不滿就可以進去，如果人滿了，就要等待有人出來。
- 對於N=1的情況，稱為binary semaphore
- 問題
- Deadlock
- 交叉等待時，就可能會出現 deadlock
- 
- Starvation
- 有可能永遠不會離開 semaphore queue
- 在 LIFO 的狀況下
- Priority Inversion
- 如果有多個 priority process 中，如果有高位階的 process 要求正在執行的低位階 process，可能會出現 somehow 中位階的 process 先搶到
- 
- 解法：
- Priority inheritance
- 高位階 process 來要求低位階時，低位階提高到跟高位階一樣的 level，導致中位階不可能攔截到執行權
- 
- 要執行時才能即時改變
- Priority Ceiling
- 在(低位階)開始拿到執行權時，就先行提升成高位階
- 
- 在 compile 時就可以預測誰要題權，要提多少
- Classic Problems of Synchronization
- Bounded Buffer Problem
- Readers-Writers Problem
- Readers: 只讀不寫
- Writers: 會讀會寫
- 在 reads 時，可以同時有多個
- 有 writers 時，只能有一個 writers，同時也不能有任何 readers
- 作法：
- 將 read_mutex 與 rw_mutex 分開計，read_mutex 在完全沒有人 read 時才提起來，這時候才考慮 rw
- Dining-Philosophers Problem
- 當 process 需要兩個(或以上)個資源才能動作時
- 就像桌上有五**支**筷子，有五個人要吃飯，每個人都一定要拿到兩隻筷子才能吃
- 
- 如果是這樣作：
- 
- 可能會產生 deadlock!!
- 在所有人都拿左邊的筷子時
- 處理方法
- 最多只能有 4 之筷子在桌上
- 只有兩邊的筷子都是可用的，才能拿
- 奇數人拿左邊，偶數人拿右邊
- Monitors
- 工程師超容易寫出 bug 的 QQ
- 用 monitors 幫助避免寫出 bug
- 不用自己寫 wait / signal，monitor 已經幫忙包好了
- 把要 share 的 data 放在 monitor，要修改的 function 放在 procedure
- 
- Condition Variables
- 如果你的 wait 不只一個，可以用 conditional variab le 幫助(?)
- condition x, y; x.wait() x.signal() y.wait() y.signal()
- 兩種 signal
- signal / wait
- signal / continue
- signal(next)
- 如果 monitor 理，有多個人被叫醒，就會被排在 next 裡，next 被清空之後，才會繼續接外面的 queue
- conditional-wait()
- 還是可以自己決定 wait 順序
- 不怕 co 爆還是可以用啊 XD
- x.wait(z)
- System example
- Solaris
- adaptive mutex
- 一開使用 spin-lock 開始
- 如果一開始在 waiting state 在進入 spin-lock 會有點浪費
- Linux
- 早期
- nonpreemptive
- 不會被搶走
- 沒有 race condition
- 後來
- preemptive