---
title: 謝仁偉_作業系統猜題館
tags: 作業系統,期末考,大學檔案,重點筆記
---
# 目錄
[TOC]
# 參考區

[作業系統 謝仁偉](https://hackmd.io/@csie808-notes/SJ9WRVDqA)
[作業系統 鐵人賽](https://ithelp.ithome.com.tw/m/users/20112086/ironman/1851)
[作業系統 鐵人賽(推)](https://ithelp.ithome.com.tw/users/20112132/ironman/1884)
[作業系統 Kipper的hackmd(推)](https://hackmd.io/@Kipper)
# 名詞、解釋與觀念
## Chapter 8: Deadlocks
- 必須同時滿足四個條件，才有可能影發 deadlock(8分:名詞、12 or 16分:名詞+解釋)
- Mutual exclusion：互斥條件，一個資源同時只能被一個 process 使用。
- Hold and wait：一個 process 手上握有一個資源，且正在等待其他資源。
- No preemption：不會搶奪其他人的資源，一定會等待其他人釋放資源。
- Circular wait：當多個 process 等待下一個 process 所持有的資源，並形成一個循環。

- Methods for Handling Deadlocks
- Deadlock prevention: 讓一種 deadlock condition 不成立
- Deadlock avoidance: 確保系統在 safe state
- Recover deadlock: 解決發生 deadlock 的狀況
- Igbore the problem: 忽略 deadlock

- Safe State 定義：
- 如果系統能夠依照某種順序滿足所有程序的資源需求，並保證所有程序都能完成，則系統處於 safe state。

- Methods for Handling Deadlocks
- Deadlock prevention → 讓一種 deadlock condition 不成立
- Deadlock avoidance → 確保系統在 safe state
- Recover deadlock → 解決發生 deadlock 的狀況
- Igbore the problem → 忽略 deadlock

- Deadlock Prevention
- 設計時就不讓deadlock產生->讓一種 condition 不成立

- Deadlock Avoidance
- 核心想法
- 在資源分配時，動態地檢視 resource-allocation state，確保他不會有 circular-wait 的情況發生
- Algorithm
- 單一資源類型的instance：使用resource-allocation graph--->Circle Detection
- 多重資源類型的instance：使用banker's algorithm

- Deadlock Detection
- 目的
- 檢測出可能發生 deadlock 的情況 ⇒ cycle
- 如果有 cycle 則嘗試 recovery
- Single Instance
- Maintain wait-for graph
- 如果 Pi → Pj 形成一個 cycle -> Deadlock
- 週期性檢測
- O(n^2)
- Several Instances
- 用Detection Algorithm

- Recovery
- Process Termination
1. 終止所有 deadlock 的 processes
2. 一次終止一個 process 直到解除 deadlock cycle

- order
1. Process的優先順序
2. Process計算了多長時間，以及需要多長時間才能完成
3. Process使用的resources
4. Resources process需要完成
5. 需要終止多少processes
6. Process是interactive還是batch？

- Process Preemption：如果可以使用 preemption，就可以解決 deadlock 問題。
- Selecting a victim - 選代價最小的 process
- Rollback - 返回到safe state，重新執行
- Starvation - 但如果每次選擇的 victim 都是同一個，就有可能 starvation ⇒ 可以在被選擇為 victim 時，提高他的 priority

## Chapter 9: Main Memory
- Address Binding(compile time, load time)
- 綁定 program 的 symbolic 的位址和實際位址
- 在以下三個階段，會有不同的 Binding：
- Compile time：若記憶體位置在編譯期間已知，則可生成 absolute code，開始位置改變時需要重新編譯
- Load time：若編譯期間位置未知，可生成 relocatable code，在程式載入記憶體時，進行最終位址綁定
- Execution time：程式執行期間可移動至不同記憶體區段，需硬體支援

- Dynamic Linking and Shared Libraries(名詞解釋、DLL好處)
- Dynamically linked libraries (DLLs)
- 是一個 system libraries，能夠在程序執行時連結 user program
- 好處
- 可以在多個process之間共享
- 可以擴充程式庫的更新，不用重新更新
- Static linking
- system libraries和program code由loader組合成binary program image
- 打包程式專案時，連同程式所寫需的 libraries 也一起打包。確保程式可以在任何地方執行，但是檔案可能會很大
- Dynamic linking
- linking 延後到 execution time
- 打包程式專案時，只打包最重要的程式部分，程式所需要的函式庫，可以在執行時動態去連結，減少了檔案的大小，但很有可能會因為執行環境不同，導致無法與函式庫做動態連結，導致不相容的問題

- Swapping(backing store、roll in, out 的名詞解釋)
- 程式需要執行時，swap in Main memory。不需要時，swap out Main memory。
- Backing store
- 要是一個 fast disk，有足夠的空間容納所有 copies of memory images
- 能夠直接 access 這些 memory images
- Roll out, roll in：swap 的變形，使用 priority 管理。低順位的，會被 swap out，使高順位的能夠 swap in main memory 執行
- 大部分的 swap time 是 transfer time（搬入、搬出記憶體的時間）
- 交由 ready queue 存放即將要 swap in memory 執行的 processes

- Context Switch Time and Swapping(double buffering名詞解釋)
- 如果我要做 context switch，但是 next process 不在 memory，則我必須要把原本的 process swap out，再把需要的 process swap in 進來，則會需要兩倍的 transfer time。 ⇒ 這樣的 context switch 代價很高。
- 減少的方法：藉由知道需要多少的 memory 空間
- 如果在執行到 I/O 時，不可以 swap out 否則會發生錯誤
- Double buffering：
- 當要載入 I/O 的資料到 Main memory 時，假設是直接載入到 user memory 中，若發生 context switch 時，會直接把 user memory 的內容覆蓋掉，則 I/O 就會遺失，必須重新 request。
- 所以使用 Double buffering 的概念，先讓 I/O 載入到 kernal memory 中，等到 CPU 要取用那些資料時，再把資料載入到 user memory，進行兩次的 buffer。

- Dynamic Storage-Allocation Problem(First, Best, Worst fit)
- 如果有一個 process 要求空間，那 memory 有什麼策略可以提供空間？
- First-fit：分配 the first 可以滿足的 hole
- Best-fit：分配 the smallest 可以滿足的 hole
- search list
- sort by size
- Worst-fit：分配 the largest 可以滿足的 hole
- First-fit 跟 best-fit 的操作速度以及 utilization 會比 worst-fit 好。

- Fragmentation (internal, external fragmentation, 數字, reduce external fragmentation)
- External Fragmentation：不是連續的 free memory，加總起來可以滿足 request（被要求的記憶體空間）
- Reduce：compaction ⇒ 把 free memory 放在一起，形成一個足夠大的空間。要求 relocation 機制是 dynamic 的。
- Internal Fragmentation：當某個 process 要求的 memory 大小與分配給的 memory 大小之間有較大差異。那個剩餘的空間，未被使用，但也沒辦法分配給其他 process 使用。
- First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation
- 1/3 may be unusable ⇒ 50-percent rule

- Segmentation Architecture (STBR, STLR)
- Logical address：<segment-number, offset>
- Segment table：儲存每個 segment 的實際位址，透過
- base：segment 在 memory 的起始位址
- limit：length of the segment
- Segment-table base register (STBR)：這個暫存器會指向 segment-table 的位址。
- Segment-table length register (STLR)：這個暫存器表示 segment-table 的大小。所以 segment number 必須 < STLR

- Implementation of Page Table (PTBR, PTLR, TLBs, ASIDs, 圖)
- Page table：logical 跟 physical address 之間的轉換
- page table 會儲存在主記憶體中。
- Page-table base register (PTBR)：指向 page table 的位址
- Page-table length register (PTLR)：表示 page table 的 size
- fast-lookup hardware cache（如：associative memory、translation look-aside buffers ⇒ TLBs），當 TLB hit 時，只需要 1 次的 memory access，取代原本都要 access memory 兩次的狀況
- TLBs 用來暫存最近被訪問的地址，用來加速查找實際位址的過程。
- 有些 TLB 會儲存 address-space identifiers (ASIDs)：ASIDs 是用來區分不同的 process，防止在對不同 prcoss 做實際位址拜訪時，access 到不屬於此 process 的內容，是一個保護 process 的機制。
- 示意圖：
- 會先查找 TLB 如果 Hit，則直接計算 physical 位址
- 如果 Miss，則去 page table 查找，並更新 TLB


- Shared Pages (reentrant code, 圖)
- 多個 process 可以共享相同的 physical page，節省記憶體空間
- Shared code：使用相同的 code（reentrant），做相同的事情。如 text editors
- reentrant code：類似read-only code，在多個thread呼叫時，code不會影響彼此正確性
- Private code and data：共享相同的 code，但是還是可以保有私自的 code 跟 data

- Structure of Page Table (三種structure)
- 為何需要這些 structure？ ⇒ 當 page table 越來越大的話，會非常佔空間，所以透過這些方法可以減少 page table 所佔用的空間。
- Hierarchical Paging：將logical address space分成很多page table，形成page of page table，這個方法只抓需要的page table進入記憶體中
- Hashed Page Tables：將logical address的page透過雜湊運算，取得hash table內的bucket address。每個bucket，都用link list來連接擁有相同hashing number的page number跟frame number。後來再去link list中搜尋符合的page number，取得frame number，在與offset相加取得physical address

- Inverted Page Tables：他是以physical address為對象，建立一個page table給所有process(有m個frame，就有m個table entry)，每個entry都會紀錄被哪個process的page運用，所以裡面記錄著process id跟page number
## Chapter 10: Virtual Memory

- Background
- 因為把整個 program 載入 memory 不會使用到所有的內容，所以希望可以只載入部分的程式
- 每個 program 只需要更少的 memory(*)
- 同時可以執行更多的 program(*)
- 提高 CPU 的 utilization and throughput 且不會增加 respone time or turnaround time ⇒ 不用切換
- Demand Paging(好處)
- 好處
- Less I/O needed, no unnecessary I/O
- Less memory needed
- Faster response
- More users
- Lazy swapper：除非需要page，否則永遠不會將page交換到memory中

- Performance of Demand Paging(圖50%，應該不會考、3 components、EAT)
- 3 major tasl componenets of the page-fault service time
- Service the page-fault interrupt ⇒ 處理 page-fault，可以靠演算法優化
- Read the page ⇒ 從 backing store 讀取 page 花最多時間
- Restart the process 可以靠演算法優化
- Effective Access Time (EAT)
- EAT = (1 - p) * memory access + p * (page fault overhead 支出 + swap out + swap in)

- anonymous memory：Pages not associated with a file (like stack and heap)

- Copy-On-Write(COW)(目的)
- 目的：讓 parent process 跟 child process 能夠共用同一個 page
- 如果要修改資源，會先檢查目前是否有跟其他人共享，如果有，則會在修改前先複製。（Cpoy and Write）
- free pages 會在一個 pool of zero-fill-on-demand pages
- Pool 的功用在於，加速 free page 的 allocated
- 在 allocation 前，會先清除 page，保護原本 page 的內容。
- COW 的優點在於，避免不必要的資源複製，和大量的內容使用。只有要進行修改時，才執行複製。
- Example
- 假如 process 1 要對 page C 進行修改
- 先複製出來，再修改
- Page and Frame Replacement Algorithms
- frame-allocation algorithm: 決定一個 process 到底可以被分配到多少個 frames。
- page-replacement algorithm:選擇哪一個 page 可以替代。

- Global vs. Local Replacement
- Global replacement：可以選擇其他人的 frame 做 replacement
- Local replacement：只能在自己的 set of allocated frame 中選擇 frame 做 replacement

- Thrashing(解釋、原因)
- 如果 process 沒有足夠的 pages，則就很容易發生 page-fault，導致：
- Low CPU utilization
- OS 會認為需要增加 process 提高 CPU utilization
- 最終 Thrashing ⇒ busy swapping pages in and out


- Working-Set Model (75%~85%)
- **Δ =** working-set window：表示 number of page。
- 在 window 中，都會被提前存取，期望加速 program 的執行速度。
- WSS（working set size of Process） = total number of pages referenced in the most recent **Δ**
- D = sum of WSS = total demand for frams
- if D > m (系統提供的 frame 個數) ⇒ Thrashing

- Page fault frequency (運作)
- 解決thrashing更直接的策略，如果錯誤率太高，就增加frame給process; 如果錯誤率太低，就會收回一些frame

- Working Sets and Page Fault Rates (60%)

- Allocating Kernal Memory(Buddy, Slab)
- 通常 kernel memory 會需要 contiguous (連續的空間)
- Buddy System
- 可以讓固定大小的區段組成更大的連續page，他的分配大小通常為2的次方。他的優點是可以快速合併成更大的chunk，但他也容易造成fragmentation，像是33KB的就只能使用64KB的page，浪費了31KB的空間


- Slab Allocator
- 他是個替代策略，slab是由一或多個physically contiguous page組成，而cache由一或多個slab組成，object會去使用cache。這個方法就沒有fragmentation的問題，以下有例圖：
- Cache 由一個或是多個 slab 組合
- 一個 cache 只能給特定的 kernal data structure 儲存
- Benefit: no fragmentation, fast memory request satisfaction


- Page size (60% 列4個)
- page size 的決定因素有以下幾點：
- Fragmentation
- Page table size
- Resolution ⇒ 解析度，若 size 太大，浪費；size 太小 page fault 提高
- I/O overhead
- Number if page fault
- Locality
- TLB size and effectiveness

- TLB Reach (80%)
- TLB(translation look-aside buffer)，TLB Reach代表TLB可存取的記憶體大小
- 大小由TLB size x page size決定
- 理想中，process的working set存放在TLB中。如果不是，那可能要花很多精力處理page fault
## Chapter 11: Mass-Storage Structure
- Overview of Mass Storage Structure(名詞解釋)
- Transfer rate(傳遞速率)：資料在drive(磁碟機)與computer(電腦)中傳送的速度
- Positioning time(定位時間)：又稱隨機存取時間，等於seek time加上rotational latency，也就是將disk arm移動到所需柱面的時間和所需磁區在磁碟頭下旋轉的時間
- Head crash(碰劃)：一種硬碟故障，硬碟讀寫頭和旋轉的磁碟片接觸時發生，磁碟表面產生不可恢復的損害

- Hard Disk Performanc(80%)
- 公式
- Latency based on spindle speed = 60 / RPM(Revolution Per Minute)
- Average latency = 1/2 latency
- Access Latency = Average access time = average seek time + average latency
- Average I/O time = average access time + (amount to transfer / transfer rate) + controller overhead
- 例子
- Suppose we want to transfer a 4KB block on a 7200 RPM disk with a 5ms average seek time, 1Gb/sec transfer rate, and a 0.1ms controller overhead. What is the Average I/O time for 4KB block?
- latency = $\frac{60}{7200}$ = $\frac{1}{120}$
- Average latency = $\frac{1}{2}*\frac{1}{120}$=$\frac{1}{240}$(s)
- Average access time = 5 + $\frac{1}{240}$ * 10^3^ ≈ 5 + 4.17 = 9.17(ms)
- Amount to transfer / Transfer rate = $\frac{4k}{\frac{1Gb}{8}}$ = $\frac{4*2^{10}}{\frac{1*2^{30}}{8}}$ = $\frac{4*2^{10}}{2^{27}}$ = $\frac{4*2^{10}}{2^{27}}$=$\frac{1}{2^{15}}$(s) ≈ 0.03(ms)
- Average I/O time = 9.17 + 0.03 + 0.1 = 9.21

# 計算題
## Resource-Allocation Graph
- Resource-Allocation Graph(RAG)的頂點分兩種，process跟resource ; edge也分兩種，request edge(process指向resource)和assignment edge(resource指向process)。
- Basic Facts
- No cycles ⇒ No deadlock
- contains a cycle ⇒
- 每個 resource type 只有一個 instances ⇒ deadlock
- 每個 resource type 有多個 instances ⇒ 有可能 deadlock
- 例子
- 有Deadlock

- 沒Deadlock

- 產生標準
- 當process要向resource產生要求時，claim edge會出現
- 當process要求resource時，claim edge就會變成request edge
- 當resource要給process時，request edge就會變成assignment edge
- 當process釋放resource時，assignment edge就會變成claim edge
- 例子
- Safe

- Unsafe

## Banker’s Algorithm
- Data Structures


- Safety Algorithm


- Resource-Request


- Example
- The content of the matrix Need is defined to be Max – Allocation

- Example2
## Detection Algorithm
- Available ⇒ 目前 system 擁有的閒置資源
- Allocation ⇒ 每個 P 目前所分配的資源
- Request ⇒ 每個 P 還需要請求的資源
- Algorithm


- Example
## Paging
Calculating internal fragmentation
- Page size = 2,048 bytes
- Process size = 72,766 bytes
- 35 pages + 1,086 bytes
- Internal fragmentation of 2,048 – 1,086 = 962 bytes
- Worst case fragmentation = 1 frame – 1 byte
- On average fragmentation = 1 / 2 frame size
- So small frame sizes desirable?
- But each page table entry takes memory to track
- Page sizes growing over time
- Solaris supports two page sizes – 8 KB and 4 MB

## Effective Access Time(EAT)
- Hit ratio α：有多少的比率會 hit
- Effective Access Time (EAT)
- EAT = α * memory access time + (1 - α) * 2 * memory access time
⇒ Hit * 1 次 memory access time + Miss * 2 次 memory access time
- 例子
- Consider α = 80%, 10ns for memory access
- EAT = 0.80 * 10 + 0.20 * 20 = 12ns
- Now consider α = 99%
- EAT = 0.99 * 10 + 0.01 * 20 = 10.1ns

## Page-replacement Algorithm
- FIFO Algorithm
- 先來的page先放到frame裡面
- 理論上，frame 的數量越多，發生 page fault 的次數就越少
- Belady’s Anomaly：在 FIFO 的演算法中，free frame 的數量越多，但 page-fault 反而增加。(*)
- Optimal Algorithm
- 假設知道之後所有的情況，則在此情況，最少的 page-fault 數量會為多少？
- 用來評估其他演算法之間的好壞。
- LRU (Least Recently Used) Algorithm
- 替換最久沒有使用到的
- Implementation
- Counter：每個 page entry 都有一個 counter，每當需要 replacement 時，查看最小的 counter
- Stack：當 page 被 referenced 時，會移動到 top
- LRU Approximation Algorithm
- 不使用 LRU，但期望可以有近似、相同的效果
- Additional-Reference-Bits Algorithm
- 額外使用一個 bit 記錄之前是否被 referenced 過。
- 選擇一個 bit = 0 的 page 做 replacement
- Second-Chance Algorithm
- 有一個指針會指向目前指到的 page，會輪流指向（clock algorithm）
- 也有額外的 bit 指向，當要取用 page 時，若指向的 page referenced bit = 1，則 reset 成 0，指針++ (Second-Chance)
- 直到指針指到 bit = 0，做 replacement


# 畫圖題
- Hardware Address Protection
- Multistep Processing of a User Program
- Segmentation Hardware
- Paging Hardware
- Paging Example
- Valid (v) or Invalid (i) Bit in a Page Table
- Steps in Handling a Page Fault(幾乎必考)