###### tags: `OS`

# 1062 - Operating System 期末考整理

### Critical section (==以下皆簡稱cs==)
* 對於共享資源之存取進行管制，當process Pi進入cs時，其他process就不能進入，必須等待。

### Memory Manage Unit (MMU)
* 將虛擬記憶體位置對應到實體記憶體位置的**硬體**裝置。

### Page Fault
* 透過page table，把logical addr轉成physical addr時，若page table中目標page為**invalid**，則會對OS發出**trap**，需要從backing store更新page。

### Race Condition
* 如果電腦中兩個執行程序試圖**修改共享記憶體資源**，在**沒有並行控制**的情況下，最後結果會因為程序的順序、時機而有機會不同(由OS而定)。

### Solve Race Condition
* Disable interrupt
* process在存取共享變數前，**先disable interrupt，在存取完後才enable interrupt**，這樣就可以保證在存取期間，**CPU不會被preempted**，即atmoically execution，故可以防止race condition。
* Critical section problem
* 對於共享變數之存取進行管制，當某一process P_i進入cs時，其他process即使取得CPU也不能進入，必須等待。

### 3 Criteria of Critical Section Design
* Mutual exclusive
* 當有一個process正執行cs，其他process不能進入cs。
* Progress
* 當沒有人在cs且有其他process想要進入cs，則選擇下一個進入cs的process的時間是有限的。
* Bounded waiting
* 自process發出申請到進入cs的時間是有限的，即若有n個process想進入cs，則任一process最多等待(n-1)次後即可進入cs，**no starvation、較公平**。

### Peterson’s solution

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
        // critical section
    flag[i] = false;
        // remainder section
} while (true);

### Mutex vs Semaphore
* Mutex
* 像是資源的鎖，當process持有mutex的鑰匙時，便可以進入cs使用資源，離開時再釋放鑰匙，讓想進入cs中的其中一個process持有進入。
* Semaphore
* Generalized mutex，限制cs中process的數量，當有人離開時，讓下個等待的process進入。

### 4 Necessary Condition for Deadlock
* Mutual exclusion
* 一個資源一次只能被一個process使用。
* Hold and wait
* process持有部分資源，又再等待其他process的資源
* No preemptive
* 不可以強奪其他process的資源，必須等待對方自願釋放後，才有機會取得。
* Circular wait
* 形成循環等待，存在一個set {P_0, P_1, ..., P_n}，P_0等待P_1所擁有的資源、P_1等待P_2所擁有的資源、...、P_n等待P_0所擁有的資源。

### External fragmentation vs Internal Fragmentation
* External
* 由**contiguous記憶體配置造成**，記憶體中的available space(hole)總和雖然大於request，但是因為不連續，無法配置，造成使用率低，**可以透過paging或compaction解決**。
* Internal
* 由**page size太大造成**，系統分配給process的空間大於該process所需的空間，造成浪費，**可以透過segmentation解決**。

### Paging vs Segmentation

### 3 Solution to Deadlock
* Deadlock prevention
* 防止四個必要條件之一成立。
* Deadlock avoidance
* 在分配之前，動態檢查resource-allocation state，沒有deadlock危險性後，才會讓過，系統事先需要以下額外資訊：
* 每個 process 所需最大資源數量
* 每個 process 目前使用資源數量
* 系統目前可用資源數量
* 然後執行**Banker's Alg**或其他alg去檢測，假設系統核准此次 request仍在safe state，就批准；若沒有，就否決，process得等一陣子再 request。
* Single instance of a resource type
* resource-allocation graph (RAG) algorithm based on circle detection
* request若是被改成assignment可能會產生circle，他將會被reject或是delay
* Multiple instances of a resource type
* banker's algorithm based on safe sequence detection
* Deadlock detection and recovery
* 定期檢查是否有deadlock，若有就要解決(recovery)

### 2 Way of Deadlock Recovery
* process termination:
* 全部砍掉，或砍一個，然後檢查，直到沒有為止(older consideration)
* resource preemption:
* 選擇victim process(mini cost)
* rollback, 回到某個safe state，restart process
* starvation: 用cost factor避免每次找相同victim

### Thrashing
* causing of thrashing
* 因為process**沒有足夠的frame造成常常page fault**，進而使得CPU使用率低，OS試著調高degree of multiprogramming來提升使用率，結果因為process增加，每個process分到的frame反而更少，CPU使用率更低，惡性循環。
* how does the system detect thrashing
* OS追蹤CPU使用率、page-fault rate，由working-set model或 page-fault frequency scheme來決定是否已經產生thrashing。
* once detect thrashing, what can system do to eliminate this problem
* 延遲部分processes的frame allocation
* 降低部分processes的frame的數量
* 減少degree of multiprogramming。

### Address binding of instructions and data to memory can happen in
* Compile Time
* Load Time
* Execution Time.

### Deadlock vs Starvation
* Deadlock
* The waiting processes will never change state, because the resources they have requested are held by other waiting processes.
* Starvation
* Process因為長期無法取得所需資源，導致無法完成工作、indefinite blocking。

### Busy Waiting
* 因為semaphore的`wait()`與`signal()`都是atomic，所以進入`wait()`的while loop會耗用大量的CPU資源在等待進入cs。

### `signal()` Operation Associated with Monitors Different from Semaphores

### Logical Address vs Physical Memory Addresses
* Logical address
* 又稱virtual address，由CPU產生
* Physical memory addresses
* 是memory unit實際看到的位置
* **在execution time的physical and logical binding會不同。**

### RAID
* Redundant Array of Independent Disks
* 透過redundancy提供硬碟的reliability。

### Optimal Page Replacement Algorithm
* 取代永遠不會用到或是最長時間才會被再次使用的page。