Operating Systems Final Exam

CH-6/7 Synchronization

Critical Section

1. Mutual exclusion: 當任意process進入CS執行後，則其他process不能進入CS執行。
2. Progress: 如果沒有process在CS中運行，且有process想要進入CS，那麼這些process不能被無限期地推遲。
3. Bounded Waiting: 一個process在請求進入CS後，其他process只能有限次數地進入CS。

Critical Section Solutions

Software solution

1. Naïve solution for Two Processes
   
2. Peterson’s solution for Two Processes
   HW3第一題證明
   
3. Bakery Algorithm (n processes)
   就是抽號碼牌

• 每個進程在進入臨界區前會選擇一個號碼，號碼按非遞減順序生成。
• 如果兩個進程選擇了相同的號碼，則進程ID較小的進程優先進入臨界區。
  

Hardware solution: atomic operations

I am atomic

1. Atomic TestAndSet()
   門沒鎖，進門把門鎖上
   門鎖著，你進不去
   

2. Atomic Swap()
   如果Swap後key仍為true，表示其他進程正在使用臨界區，則繼續等待。
   

3. Atomic CompareAndSwap()
   這不會考

Mutex(API)

老師直接跳過

• Mutual Exclusion (互斥)：
  • 是的，這個算法保證了同一時間只有一個進程能夠進入臨界區。pthread_mutex_lock和pthread_mutex_unlock確保了互斥訪問。
• Progress (進度)：
  • 是的，如果沒有進程在臨界區中運行且有進程希望進入臨界區，那麼必須允許這些進程進入臨界區。pthread_mutex_lock會阻塞直到mutex可用，因此只要臨界區沒有被佔用，進程將能夠進入臨界區。
• Bounded Waiting (有限等待)：
  • 是的，使用mutex能夠保證有限等待。Pthreads中的mutex實現通常會確保被阻塞的進程按順序獲得臨界區的訪問權限，避免了無限期等待的情況。

Condition Variables

• wait(): 鑰匙丟掉，原地開睡
• signal(): 領導打電話叫你起床幹活

Semaphores

容易與Condition Variables的wait和signal搞混

• wait(S)：等待信號量S大於0，然後減少S的值。如果S小於等於0，進程會忙等待（自旋），這意味著進程在等待時會一直佔用CPU。
• signal(S)：增加信號量S的值，表示釋放一個資源。

• S.value--：減少信號量S的值。
• if (S.value < 0)：如果S的值小於0，將進程加入到隊列S.L並進入睡眠狀態。
• S.value++：增加信號量S的值。
• if (S.value <= 0)：如果S的值小於或等於0，從隊列S.L中移除一個進程並喚醒它。

功課題，一定要會

Monitor

Classical Synchronization Problem

Readers-Writers Problem

Dining-Philosophers Problem

test()不一定是自己做，可能是別人幫你做(別人幫你吃飯)

---

CH-8 Deadlocks

必要條件(缺一不可)

• Mutual exclusion: 在同個時間只能有1個process使用資源
• Hold and wait: process持有資源並且等待其他資源
• No preemtion: process持有的資源無法被OS打斷，除非自己願意釋放
• Circular wait: 例如A等B的資源、B等C的資源、C等A的資源，形成循環

Deadlock Detection

Handling Deadlocks

Deadlock Prevention

解決必要條件:

1. 設計preemptive的演算法
2. 避免Circular wait(困難)

Deadlock Avoidance

• Consider the “worst case"
• Single instance of a resource type
  • Resource-allocation graph (RAG) algorithm based on circle detection
• Multiple instances of a resource type
  • banker’s algorithm based on a safe sequence detection

Resource-Allocation Graph Algorithm

If P1 request R2, the OS will accept
If P2 request R2, the OS will reject(因為形成迴圈)

Banker’s Algorithm

功課題，一定會考

Deadlock Detection

不防範於未然(只在意當下)

Single instance of a resource type

Multiple instances of a resource type
使用改良版Banker’s Algorithm

圖一: 理想的狀態

圖二: 這根本我

Deadlock Recovery

不考

CH-9 Main Memory

Address Binding

Three types of an address binding:

• Compile time
• Load time: use a base register to allow for relocatable code
• Execution time (run time): use MMU for address translation
  • Logical address ≠ physical address

Load a Program into Memory

靜態加載（Static Loading） vs 動態加載（Dynamic Loading）

1. 定義

• 靜態加載：
  • 在程序開始執行之前，所有需要的程序和資源都被加載到內存中。
• 動態加載：
  • 程序執行期間，按需加載所需的程序和資源，當資源需要使用時才進行加載。

2. 實現方式

• 靜態加載：
  • 編譯時，所有依賴的庫和資源都被解析並加載到程序的可執行文件中。執行開始時，整個程序和所有依賴項被一次性加載到內存中。
• 動態加載：
  • 通過函數（如LoadLibrary在Windows中，或dlopen在Unix/Linux中）在運行時加載需要的資源或庫。加載後，可以使用這些資源或庫提供的函數和數據。

3. 優缺點

• 靜態加載：
  • 優點：
    • 加載過程簡單，運行時無需考慮資源加載問題。
    • 一次性加載，運行速度更快。
  • 缺點：
    • 需要大量內存，因為所有資源在程序開始時全部加載。
    • 可執行文件較大，佔用更多磁盤空間。
• 動態加載：
  • 優點：
    • 節省內存，只加載需要的資源。
    • 可執行文件較小，節省磁盤空間。
  • 缺點：
    • 需要處理運行時的加載錯誤，增加了複雜性。
    • 可能導致運行時性能問題，因為資源在需要時才加載。

靜態鏈接（Static Linking） vs 動態鏈接（Dynamic Linking）

1.定義

• 靜態鏈接：
  • 在編譯時將所有依賴的庫和模塊鏈接到程序的可執行文件中。最終生成的可執行文件包含所有依賴項。
• 動態鏈接：
  • 在運行時將依賴的庫和模塊鏈接到程序。可執行文件本身不包含依賴的庫，而是在運行時動態加載它們。

2. 實現方式

• 靜態鏈接：
  • 編譯過程中，鏈接器將所有依賴的靜態庫（如.lib或.a文件）合併到最終的可執行文件中。
• 動態鏈接：
  • 在運行時，運行時鏈接器（如Windows的LoadLibrary，或Unix/Linux的ld.so）動態加載共享庫（如.dll或.so文件），並將它們鏈接到正在運行的程序中。

3. 優缺點

• 靜態鏈接：
  • 優點：
    • 可執行文件在分發時不依賴外部庫，分發和部署更簡單。
    • 運行時無需處理動態鏈接錯誤。
  • 缺點：
    • 可執行文件較大，因為包含了所有依賴項。
    • 無法在運行時替換或更新依賴的庫。
• 動態鏈接：
  • 優點：
    • 可執行文件較小，節省磁盤空間。
    • 可以在運行時替換或更新庫，靈活性更高。
  • 缺點：
    • 需要處理運行時的鏈接錯誤，增加了複雜性。
    • 分發和部署時需要確保所有依賴庫的存在和兼容性。

總結

• 靜態加載和靜態鏈接通常用於需要簡單部署和快速運行的情況，但會增加可執行文件的大小。
• 動態加載和動態鏈接提供了更大的靈活性和內存節約，但增加了運行時的複雜性和潛在的性能問題。

Fragmentation

• 外部碎片：在變動大小分配中，內存空間足夠但不連續。解決方案是內存緊縮。
• 內部碎片：在固定分區分配中，分區內部未使用的空間導致內存浪費。解決方案較為困難，通常需要調整分區大小。

Paging

一定會考

Address Translation using Paging

看功課題

Translation Look-aside Buffer (TLB)

優化Paging
A cache for page table shared by all processes
先去TLB查資料(快)，如果TLB中沒有，再去Page table找(慢)
TLB可以平行去做搜尋–>效率更高

• TLB刷新：在上下文切換時，必須刷新TLB以清除前一進程的條目，防止新進程使用錯誤的頁表條目。
• 地址空間標識符（ASIDs）：另一種解決方法是在TLB條目中添加進程ID字段（PID），這樣每個條目都包含其所屬進程的信息。當發生上下文切換時，不必清除整個TLB，而是通過檢查PID來確保使用正確的頁表條目。

Effective Memory-Access Time

功課題 很簡單 一定要會算

Issues of a Page Table

• 問題：頁表可能非常大，難以在內存中連續存儲和加載。
• 解決方案：
  • 分解頁表為多個較小的頁表。
  • 使用Hierarchical paging(分層頁表)、Hash page table(哈希頁表)或Inverted page table(反向頁表)等技術來減少頁表的總大小和內存佔用。

Hierarchical Page Table

每切一次，就多一次memory access
常用在32bit的system

優點:

• 減少內存浪費：分層頁表將大頁表分解為多個較小的頁表，有效減少內存浪費，特別是在頁表不完全佔滿的情況下。
• 靈活性：內層頁表可以分散存儲，無需連續內存，增加了內存管理的靈活性。

缺點:

• 查找時間增加
• 內存開銷
• 實現複雜性
• 性能影響

Hashed Page Table

Inverted Page Table

反向頁表的概念

• 不為每個進程維護頁表：反向頁表系統不為每個進程單獨維護頁表，而是維護一個針對整個物理內存的框架表（Frame Table）。
• 框架表：框架表中每個條目對應物理內存中的一個實際框架。每個條目包含進程ID（PID）和頁號（Page Number）。

反向頁表的結構和工作原理

1. 邏輯地址：邏輯地址由進程ID（PID）、頁號（p）和頁偏移量（d）組成。
2. 查找過程：
   • 進程ID和頁號的組合被用來查找框架表中的對應條目。
   • 框架表中的每個條目包含該頁面所映射的物理框架號（Frame Number）。
   • 根據框架號和頁偏移量計算最終的物理地址。

反向頁表的優點

• 減少內存需求：反向頁表消除了每個進程需要維護單獨頁表的內存開銷，特別是在多進程系統中，這可以顯著減少內存需求。
• 統一管理：由於所有進程共用一個框架表，可以更方便地統一管理物理內存。

反向頁表的缺點

• 增加內存訪問時間：每次內存訪問需要遍歷整個框架表，這會增加內存訪問的延遲，尤其是在框架表非常大的情況下。
• 難以支持共享頁面/內存：反向頁表難以有效地支持多進程間的頁面或內存共享，這在需要進程間通信或共享內存的應用中是一個重要的限制。

總結

• 反向頁表：通過維護一個針對整個物理內存的框架表來替代每個進程的單獨頁表，減少內存開銷，但增加了內存訪問時間。
• 應用場景：適用於內存有限且進程數量多的情況，但在需要高效內存訪問和進程間內存共享的場景中可能不太適用。

Segmentation

---

CH-10 Virtual Memory

將Swapping做延伸

用途?

1. 跑大程式
2. 增加CPU/resource的utilization
3. 執行程式更迅速

Demand Paging

你要我才拿

Page Replacement Algorithms

跟作業考法一樣

First-In-First-Out (FIFO) Algorithm

Optimal (Belady) Algorithm

就是通靈

LRU (Least Recently Used) Algorithm

Thrashing(使用過度)

Definition

OS不知道頻繁的I/O是Thrashing還是degree of multi-programming不夠
所以要讓OS知道花生什麼素了

Working-Set Model

一直追蹤，很貴

Page Fault Frequency Scheme

increase number of frames代表減少運行的程式，每個程式的number of frames就會提升;反之亦然

只要看Page Fault的次數，較便宜好用