---
title: 謝仁偉_作業系統考古博物館
tags: 作業系統,期中考,考古題,大學檔案,重點筆記
---
# 目錄
[TOC]
# 考古題考卷與複習講義連結
[謝仁偉_作業系統考卷](https://hackmd.io/wlTWKu01TwSTFCwkxq0rHw)
[作業系統 謝仁偉](https://hackmd.io/@csie808-notes/SJ9WRVDqA)
# 名詞解釋與問答題
## 考古區
- 給解釋寫元件
- Core：The basic computation unit of the CPU
- CPU：The hardware that executes instructions
- processor：A physical chip that contains one or more CPUs
- multicore：Including multiple computing cores on the same CPU
- multiprocessor：Including multiple processors
- policy：想要達成的目標
- mechanism：要如何達成目標
- 三種將參數傳送到OS的方式
- 透過register進行傳送
- 將參數存入block利用memory address進行傳遞
- 利用stack進行傳遞
- zombie：當已結束但parent process尚未呼叫wait()的child process
- orphan：當parent process已經結束但尚未執行完畢的child process
- Interprocess communication(IPC)：Process 之間的溝通
- IPC的兩種model
- Shared memory
- Message passing
- Blocking send：等到訊息被接收才離開
- Blocking receive：等到有訊息才離開
- Non-blocking send：送完就走，不管有沒有人拿
- Non-blocking receive：可能收到東西，也可能沒有收到東西，但都會離開
- 區分Thread-Local Stroage (TLS)的local variables與static data(參考)
- local variables只獨立存在於一條Thread裡，不會被其他的Thread修改
- static data可以在所有Thread共享同樣的變數
## 隔壁班考古區
- Program, Process, Thread差別
- Program：被動程序，在disk中執行的程序
- Process：主動程序，正在memory中被執行的程序
- Thread：OS所能排程的最小程序單元，包含在Process中
- Processor affinity：Process 想儘量長時間運行在某個指定的processor上，且不被轉移至其他processor
- Soft real-time system：不保證在deadline時重要的real-time process可以排班
- Hard real-time system：保證在deadline時所有real-time process可以排班
- Paralleism：process同時處理
- Concurrency：process快速switch
- Aging：process的priority會隨時間增加
- Thread Pools：
- Atomic Variables：不受Thread執行順序影響且不會被中斷的變數(參考)
- Memory Barrier：記憶體中的任何變更傳送到其他處理器的指令(不考)
## 非考古區
- 當發生 Interrupt 時
- OS 會利用 registers 和 Program Counter 保存 CPU 的狀態
- 兩種模式去處理多個 interrupts
- **polling** ⇒ 輪詢，輪流處理 interrupt，比較慢，但 reliable，因為要依序檢查 device
- **vectored interrupt system** ⇒ 比較快，但設計較為複雜，不需要依序檢查 device，會設計一個 priority system 去處理優先處理比較重要的 interrupt
- Caching Replacement Poliy
- LRU ⇒ Least Recently Used 淘汰最久沒被使用的
- LFU ⇒ Least Frequently Used 淘汰最不常（頻率）使用的
- 兩種 Multiprocessors
- Asymmetric Multiprocessing ⇒ 可能會設計特別的 processor 處理特殊的任務（如：高負載的運算，而有些只需要負責低負載的運算）
- Symmetric Multiprocessing ⇒ 每個 processor 之間沒有差異，都能夠做相同的工作
- 對 I/O 的 memory management 有包含
- Buffering，緩衝，儲存待處理的資料，穩定處理的速度。
- Caching，快取，將特定部分的資料放在比較快的 memory 中，加速 CPU 存取資料的過程。
- Spooling，排隊，在處理一個 job 的輸出時，在輸入處理其他的 job，使處理效率增加。
- Privilege escalation ⇒ 權限升級，使 user 有更多的權限做比較危險的事情，例如在指令前面加上 sudo。
- Virtualization vs Emulation
- Virtualization 虛擬化，把實際有的硬體資源，拆分成多個資源，供給不同的執行環境使用。
- Emulation 模擬，主要是讓原生 CPU 透過模擬的方式運作不同種類的 CPU，實現跨平台的環境。例如 x86 的架構，模擬成 ARM 架構，得以運行對應的作業系統。
- 不同的 Schedulers
- Short-term scheduler (CPU scheduler) → 決定哪個 process 是下一個要執行，分配給 CPU 做運算
- 觸發頻繁 → CPU 要很快
- 目的：讓每個 process 都有機會被 CPU 執行到
- Long-term scheduler (job scheduler) → 決定哪個 process 要被放入 ready queue 裡面
- 觸發較不頻繁 → 比較慢
- 目的：控制系統的負載，防止內存爆滿
- Medium-term scheduler → 當附載太高時，可以先把 process 從內存中釋放出來（swap out 至 disk），等待內存空間足夠時，再把 process swap in 至 ready quene 中處理。\
- 兩種 process 的類型
- I/O-bound process：處理 I/O 的時間大於 CPU 運算的時間
- CPU-bound process：處理 CPU 運算的時間大於 I/O 的時間
- Context Switch → 指 CPU 在交換不同的 process 運算的動作。
- Process 溝通會需要 buffer 暫存資料 (Producer ↔ Consumer)
- unbounded-buffer ⇒ 儲存空間無限制
- bounded-buffer ⇒ 固定 buffer size，通常會使用
- Producer
- Consumer
- Nonpreemptive (cooperative) 非搶占式
- 一段 process 會使用 CPU 直到那個工作要進入 waiting state 或是 terminate
- 其他 process 無法中斷正在進行的 process
- Preemptive 搶占式
- 作業系統可以在任何時間點中斷正在進行的 process，把 CPU 分配給其他 process 使用
- 會需要大量的 context switch ⇒ 提高成本
- race condition ⇒ 可能會讓結果不正確
- Dispatch ⇒ 把 process 派送給 CPU 做處理
- Dispatch latency ⇒ 停止 process 然後開始其他 process 的時間
1. 儲存原本的 process state
2. 載入新的 process
3. 把 CPU switch 到新的 process 做處理

- Deadlock：兩個或是多個 process 在互相等待，導致沒有 process 能夠繼續執行，因為每個人都在等待對方的資源。
- 舉例：
- P0 得到 S 的資源，P1 得到 Q 的資源，現在 P0 等待 Q，P1 等待 S，但是它們要先得到對方的資源後，才會釋放手中的資源，導致 Deadlock 發生。
- Remote Procedure Calls (RPC)
- Messages can be delivered **exactly once** rather than **at most once**
- exactly once ⇒ 確保訊息只傳遞一次，不會被重複傳送，也會使用 ack 等機制，確保有被接收
- at most once ⇒ 訊息傳遞最多一次，意思是沒有 ack 等機制，確保被接收，所以訊息可你會遺失

- Starvation → indefinite blocking 無限的 blocking
- 某個 process 一直等待
- Priority Inversion
- 一個具有較低優先級的任務卻在持有一個較高優先級任務所需的資源時，導致較高優先級的任務被阻塞。
- 舉例：
- priority: A > B > C。C 正在執行，並且進入 critical session，此時 A 要佔用 CPU 所以 C 中斷，直接換 A，接著 A 執行需要進入 critical session 但是 C 還沒結束，所以要跳回 C 讓他做完（預期接下來換 A），但是 C 做到一半，B 搶佔 CPU 導致明明 A 在等待，結果 B 搶佔 A 的資源。造成 Priority Inversion。
- 假設系統中有三個任務 A、B 和 C，其中 A 的優先級最高，B 的優先級次之，C 的優先級最低。現在如果 B 持有了一個資源（例如一個互斥鎖或信號量），而 C 需要這個資源才能執行，但 A 需要等待 C 執行完成才能繼續，這樣就產生了優先級反轉的情況：C 因為 B 的佔用而阻塞，A 也因為 C 的等待而被阻塞，導致系統中的最高優先級任務被延遲執行。
- 解決方法：
- **優先級繼承（Priority Inheritance）**：當一個較低優先級的任務獲取了一個資源時，它會暫時提高到這個資源所需的最高優先級，以防止高優先級的任務被阻塞。這樣可以保證資源的優先級與需求的優先級相符。

# 畫圖與公式題
## 考古區
- Interrupt time
- 一個 process 在 memory 中會被劃分不同的區域
- 當 process 執行時，會改變 state
- new → The process is being created
- running → Instructions are being executed
- waiting → The process is wating for some event to occur
- ready → The process is waiting to be assigned to a processor
- terminated → The process has finished execution
- Amdahl's Law

- Parallel 和 Concurrent差別
- process排班
- FCFS：先來的process先做
- SJF：Burst time短的process先做
- priority：照process的優先順序做(數字低的優先)
- RR：照process的先後順序做特定的間隔，結束後換下一個，直到做完
## 隔壁班考古區
- process排班
- FCFS：先來的process先做
- SJF：Burst time短的process先做
- SRTF：剩餘Burst time短的process先做(不考)
- priority non-preemptive：照process的優先順序做，但不可被插隊
- priority preemptive：照process的優先順序做，但可被插隊
- RR：照process的先後順序做特定的間隔，結束後換下一個，直到做完
- 檢查bounded buffer哪裡有問題並修改
- Producer program 先檢查 mutex可能會因empty buffer導致無限等待，所以要先檢查empty再lock
Producer program先signal full first才signal mutex可能導致race condition，讓多個 Comsumers 進入修改過的緩衝區

## 非考古區
- Process Creation → Parent creat a Child process
- fork() ⇒ create new process
- exec() ⇒ after fork(), 執行此 process
- 當 parent fork() child 時，會等待 child 做完再換 parent 執行
- Rate Monotonic (RM) Scheduling ⇒ 處理有週期性的 process
- 週期越短的 process, priority 越高
- 如果 miss deadline，則先做 priority 高的，等空閒時，再回來處理還沒做完的 process

- Earliest Deadline First Scheduling (EDF) ⇒ 最佳的排程 algorithm
- deadline 越近，priority 越高


# 程式題
## 隔壁班考古區
- 證明以下擴充的compare_and_swap 程式在mutual exclusion, progress, and bounded waiting上的正確性
- 為什麼原本的compare_and_swap沒有滿足bounded waiting
- 因為compare_and_swap沒有優先順序，所以當有一個process在critical section時，另一個process可能卡在迴圈並無限等待
## 非考古區
- 使用硬體的方式實現 critical section code
- 方法 ⇒ locking：用 Lock 保護 critical section
- 作法：Atomic hardware instructions → non-interruptible 不會被中斷，有效率的做法
- 兩個 Atomic 的指令作法，管理 lock
- Test-and-set Instruction


- 用一個 flag 記錄原本的值
- 把 lock 設成 TRUE
- 回傳 flag
- ⇒ 不管怎麼樣， lock 最後都會變成 TRUE，只是當傳進來的 lock 是 FALSE 時，回傳的值才會是 FALSE，然後進入到 critical section（此時 lock 會是 TRUE 的，確保其他 process 不會同時進入 CS），做完後，lock 設定成 FALSE 讓其他 process 進入。
- Compare-and-swap Instruction


- 先**比較**，比較通過，才**替換**


- 等待 lock 變成 0，先把 lock 設定成 1，把 0 回傳回去，進入 Critical Section
- Bounded-Waiting Mutual Exclusion

- Mutex Locks
- 前面提到的 程式設計起來比較複雜，且不夠彈性(沒有辦法 access 到應用程式)
- Mutex lock 是利用 acquire() 跟 release() 保護 lock，且這兩個功能必須是 atomic 的(硬體實現)
- 缺點：Busy waiting → 使用迴圈等待條件不成立，並跳出迴圈。浪費 CPU 資源 ⇒ 這樣子的 lock 稱作為 spinlock
- 程式碼：
- Semaphore
- 提供更精細的方法，使 process 能夠同步(Synchronization)他們的 activities ⇒ 讓 processes 能夠照著期望的順序執行
- 主體 Semaphore S → 一個 integer variable 用來記錄剩餘資源 (Source)
- 兩個不可分個的 atomic operation
- wait() ⇒ P()
- signal() ⇒ V()

- 兩種 Semaphore
- Counting semaphore → S 的數量範圍可不受限制
- Binary semaphore → S 的數量範圍只能是 0 或 1 ⇒ 操作就如同 Mutex lock
- 實作方面
- 為了確保 Semaphore 能夠按照順序執行 process，必須要確保不會任意兩個 process 同時對同一個 S 執行 wait() 跟 signal() ⇒ 這就變成了 Critical Section Problem (不能同時進入 Critical Section)
- 所以就還是會有 busy waiting 的情況發生
- Implementation with No Busy Waiting
- Waiting queue → 讓每一個 Semaphore 都有一個對應waiting queue
- Waiting queue
- value：紀錄 S 的數量
- pointer：指向下一個等待被處理的 process
- Two operations
- block → 用來把 process 放入到 waiting queue
- wakeup → 用來呼叫 process，把 process 移出 waiting queue，放到 ready queue 裡面


- Monitor Implementation Using Semaphores
- 針對 Condition Variables



# 2024猜題區
- 每個 Computer System Components 的定義
- CPU：中央處理單元，執行指令
- Consistency ⇒ 對 multiple locations
- 一致性關心的是分散式系統中的數據一致性
- 在分散式系統中，每個系統可能同時要做同樣的操作，為了讓數據保持正確，會有順序的執行 program，前一個做完，才能往下繼續。
- Processor：由單個或多個 CPU 組成的晶片
- Core：CPU 的基本運算單元
- Multicore：在同一個 CPU 中有多個 core
- Multiprocessor：多個 processor 組合在一起
- 對 I/O 的 memory management 有包含
- Buffering，緩衝，儲存待處理的資料，穩定處理的速度。
- Caching，快取，將特定部分的資料放在比較快的 memory 中，加速 CPU 存取資料的過程。
- Spooling，排隊，在處理一個 job 的輸出時，在輸入處理其他的 job，使處理效率增加。
- Multiprocessors ⇒ parallel system 平行化系統、tightly-coupled systems 緊密耦合系統
- 優點：
- 增加 throughput
- 規模經濟 ⇒ 符合經濟效益（？）
- 增加 reliability → graceful degradation or fault tolerance （單顆核心故障，不影響整體運作）
- graceful degradation（優雅降級）
- 當有部分設備故障時，能夠確保整體還能正常運作，雖然可能會降低性能，但可用。所以 graceful degradation 主要是維護部分的功能，確保整體能夠運作。
- fault tolerance（容錯性）
- 不僅僅是在部分設備故障時，能夠確保設備能正常運作，還會確保設備性能保持在原有的水準。
- 三種將參數傳送到OS的方式
- 透過register進行傳送
- 將參數存入block利用memory address進行傳遞
- 利用stack進行傳遞
- policy和mechanism定義
- policy：想要達成的目標
- mechanism：要如何達成目標
- 一個 process 在 memory 中會被劃分不同的區域
- 當 process 執行時，會改變 state
- new → The process is being created
- running → Instructions are being executed
- waiting → The process is wating for some event to occur
- ready → The process is waiting to be assigned to a processor
- terminated → The process has finished execution
- 不同的 Schedulers
- Short-term scheduler (CPU scheduler) → 決定哪個 process 是下一個要執行，分配給 CPU 做運算
- 觸發頻繁 → CPU 要很快
- 目的：讓每個 process 都有機會被 CPU 執行到
- Long-term scheduler (job scheduler) → 決定哪個 process 要被放入 ready queue 裡面
- 觸發較不頻繁 → 比較慢
- 目的：控制系統的負載，防止內存爆滿
- Medium-term scheduler → 當附載太高時，可以先把 process 從內存中釋放出來（swap out 至 disk），等待內存空間足夠時，再把 process swap in 至 ready quene 中處理。

- Process Termination
- process 執行的最後會 exit() 使 OS 刪除 process
- Parent 可以 abort() 中斷正在執行的 child process
- 當 parent 被 terminated 時，會觸發 cascading termination 使 parent 底下的所有 child 都會被 terminated
- Zombie process → 當 child process 結束時，parent 沒有呼叫 wait() 接收 child 的資源，則 child 就換變成一個 zombie process 佔用資源。
- Orphan → parent 結束時，child 沒有被 parent 呼叫 wait()，則 child 會變成 orphan process
- Reasons for cooperating processes
1. Information sharing：共享資料
2. Computation speedup：運算加速
3. Modularity：模組化
- Interprocess communication(IPC)：Process 之間的溝通
- IPC的兩種model
- Shared memory
- Message passing
- Synchronization
- Blocking send：等到訊息被接收才離開
- Blocking receive：等到有訊息才離開
- Non-blocking send：送完就走，不管有沒有人拿
- Non-blocking receive：可能收到東西，也可能沒有收到東西，但都會離開
- Remote Procedure Calls (RPC)
- Messages can be delivered **exactly once** rather than **at most once**
- exactly once ⇒ 確保訊息只傳遞一次，不會被重複傳送，也會使用 ack 等機制，確保有被接收
- at most once ⇒ 訊息傳遞最多一次，意思是沒有 ack 等機制，確保被接收，所以訊息可你會遺失
- Amdahl's Law

- Parallel 和 Concurrent差別

- Nonpreemptive (cooperative) 非搶占式
- 一段 process 會使用 CPU 直到那個工作要進入 waiting state 或是 terminate
- 兩種情況
1. Switches from running to waiting state
2. Terminates
- Scheduling Criteria
- CPU utiliztion
- Throughput ⇒ 在單位時間內能做多少件事情
- Turnaround time ⇒ 一個 process 執行的總時間
- Waiting time ⇒ 一個 process 在 ready queue 等待的總時間 (等待次數可能不只一次)
- Response time ⇒ 一個 process 進到 ready queue 到第一次被處理的時間
- FCFS, SJF, Priority, RR Scheduling的甘特圖
- Convoy effect - short process behind long process，短的 process 會被長的 process 擋住在後面。
- SJF預測
- α 通常是1/2
- Processor affinity：Process 想儘量長時間運行在某個指定的processor上，且不被轉移至其他processor
- soft ⇒ process 能根據情況變換處理的 processor
- hard ⇒ process 只能夠在特定幾個 processor 之間變換

- 知道 RM Scheduling：週期越短，priority越高

- 架構的 3 個主要 components
- entry section
- exit section
- remainder section

    do {
    	:: entry section
    			critical section
    	:: exit section
    			remainder section
    } while(true);

- critical-section problem必須滿足三個要求
- Mutual Exclusion **互斥**：一次只能有一個 Process 在他自己的 Critical section
- Progress **要能夠持續運作**：若目前沒有 Process 在 Critical Section，且有 Process (可能不只一個)想要進入，則必須選擇一個 Process 進入。
- Bounded Waiting **限制等待時間**：若有一個 Process 等待進入 Critical Section，不能夠讓他一直等待，需要設定一些條件，使得 Process 可以在未來被選擇進入。
- 例如，設定等待時間，等待越久 Priority 越高。

- test_and_set Instruction(定義)
- 用一個 flag 記錄原本的值
- 把 lock 設成 TRUE
- 回傳 flag
- ⇒ 不管怎麼樣， lock 最後都會變成 TRUE，只是當傳進來的 lock 是 FALSE 時，回傳的值才會是 FALSE，然後進入到 critical section（此時 lock 會是 TRUE 的，確保其他 process 不會同時進入 CS），做完後，lock 設定成 FALSE 讓其他 process 進入。

- Bounded-Waiting Mutual Exclusion(填空、改錯)

- Problims with Semaphore
- 使用不當，導致錯誤發生，但是難以偵測，因為錯誤通常是在特別的情況下才會發生，而不是常常發生。
- 順序相反：signal() … wait() → 只有在 2 個以上的 process 都先進入 signal 後 wait 的時候才有可能發生問題。
- 連續使用兩個 wait() → 導致 permanently block，因為沒有使用 signal 釋放資源。
- 省略掉 wait() 或是 signal()
- Deadlock 和 starvation 也都有可能發生
- Monitor

- 是一種用於控制並發存取共享資源的同步機制
- 同時只會有一個 process 被 active 進 monitor
- Abstract data type：隱藏資源的內部細節，只讓 programmer 透過 Monitor 提供的介面進行 access → 保護資源


- Monitor Implementation Using Semaphores