---
# System prepended metadata

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

---

---
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
    ![image](https://hackmd.io/_uploads/Hy827-5f1g.png)

- 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
        
![image](https://hackmd.io/_uploads/H1ItSWcfJg.png)

- 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
![image](https://hackmd.io/_uploads/Sykl8W5zye.png)

- Structure of Page Table (三種structure)
    - 為何需要這些 structure？ ⇒ 當 page table 越來越大的話，會非常佔空間，所以透過這些方法可以減少 page table 所佔用的空間。
    - Hierarchical Paging：將logical address space分成很多page table，形成page of page table，這個方法只抓需要的page table進入記憶體中
    ![image](https://hackmd.io/_uploads/HkzBLWqf1g.png)
    ![image](https://hackmd.io/_uploads/HklULZcMJl.png)
    - 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
    ![image](https://hackmd.io/_uploads/SyOsIW9G1g.png)

    - Inverted Page Tables：他是以physical address為對象，建立一個page table給所有process(有m個frame，就有m個table entry)，每個entry都會紀錄被哪個process的page運用，所以裡面記錄著process id跟page number
    ![image](https://hackmd.io/_uploads/r1GaLWqGyl.png)
## 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中
![image](https://hackmd.io/_uploads/ryX1nVsV1e.png)

- Performance of Demand Paging(圖50%，應該不會考、3 components、EAT)
![image](https://hackmd.io/_uploads/rJU6nEo4Jl.png)
    - 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)
    ![image](https://hackmd.io/_uploads/rk0j6ViE1x.png)

- 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 進行修改
            ![image](https://hackmd.io/_uploads/SJwQDn97Jx.png)
        - 先複製出來，再修改
            ![image](https://hackmd.io/_uploads/B1WNPh9Xyx.png)
- 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
    
    ![image](https://hackmd.io/_uploads/B1ijO35m1g.png)

- 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
    ![image](https://hackmd.io/_uploads/Hk7f3-h4yg.png)
    
- Page fault frequency (運作)
    - 解決thrashing更直接的策略，如果錯誤率太高，就增加frame給process; 如果錯誤率太低，就會收回一些frame

- Working Sets and Page Fault Rates (60%)
![image](https://hackmd.io/_uploads/Hy9q2b3Nkx.png)

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

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

- 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
    ![image](https://hackmd.io/_uploads/S1XO3ziNJg.png)

    - 沒Deadlock
    ![image](https://hackmd.io/_uploads/HyXKhziV1g.png)

- 產生標準
    - 當process要向resource產生要求時，claim edge會出現
    - 當process要求resource時，claim edge就會變成request edge
    - 當resource要給process時，request edge就會變成assignment edge
    - 當process釋放resource時，assignment edge就會變成claim edge
- 例子
    - Safe
![image](https://hackmd.io/_uploads/HyY6FB2E1g.png)

    - Unsafe
![image](https://hackmd.io/_uploads/HyGx2fsNJx.png)


## Banker’s Algorithm
- Data Structures

![image](https://hackmd.io/_uploads/ryy4-WcfJl.png)


- Safety Algorithm

![image](https://hackmd.io/_uploads/HyBHW-5Mke.png)
![image](https://hackmd.io/_uploads/BJud_fiVkl.png)


- Resource-Request

![image](https://hackmd.io/_uploads/HJ_P-Wqfyg.png)


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

    ![image](https://hackmd.io/_uploads/r1N5--qM1x.png)
    ![image](https://hackmd.io/_uploads/SkuhbZcMkg.png)
- Example2
![image](https://hackmd.io/_uploads/Hkc1uGiNJg.png)
## Detection Algorithm
- Available ⇒ 目前 system 擁有的閒置資源
- Allocation ⇒ 每個 P 目前所分配的資源
- Request ⇒ 每個 P 還需要請求的資源
- Algorithm

![image](https://hackmd.io/_uploads/BkRMzW9Gkx.png)
![image](https://hackmd.io/_uploads/HJ57MW9G1x.png)
![image](https://hackmd.io/_uploads/Sy-nKMj41x.png)

- Example
![image](https://hackmd.io/_uploads/rk9uMb9fkx.png)
![image](https://hackmd.io/_uploads/SyqFfbqzkl.png)
![image](https://hackmd.io/_uploads/ryLAtzoVJg.png)
## 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 反而增加。(*)
    ![image](https://hackmd.io/_uploads/HydQeBoE1e.png)
- Optimal Algorithm
    - 假設知道之後所有的情況，則在此情況，最少的 page-fault 數量會為多少？
    - 用來評估其他演算法之間的好壞。
- LRU (Least Recently Used) Algorithm
    - 替換最久沒有使用到的
    - Implementation
        - Counter：每個 page entry 都有一個 counter，每當需要 replacement 時，查看最小的 counter
        - Stack：當 page 被 referenced 時，會移動到 top
![image](https://hackmd.io/_uploads/Sy0vuh9XJg.png)
- 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

    ![image](https://hackmd.io/_uploads/r1rF_h9Xye.png)

# 畫圖題
- Hardware Address Protection
![image](https://hackmd.io/_uploads/SkymnQo4kg.png)
- Multistep Processing of a User Program
![image](https://hackmd.io/_uploads/HJ4E6QoEkl.png)
- Segmentation Hardware
![image](https://hackmd.io/_uploads/SyZxzEjEkx.png)
- Paging Hardware
![image](https://hackmd.io/_uploads/r1NOMVj4kg.png)
- Paging Example
![image](https://hackmd.io/_uploads/Byp8EEjEJg.png)
- Valid (v) or Invalid (i) Bit in a Page Table
![image](https://hackmd.io/_uploads/r1NEPVjNJl.png)
- Steps in Handling a Page Fault(幾乎必考)
![image](https://hackmd.io/_uploads/SJSw3VoVJe.png)