# 2020期末考古試寫
###### tags: `作業系統`, `109-2`

:::info
<!--  -->
 J.C.出品，必屬ㄎㄧㄤ品 ((p)章節 / 投影片章節-投影片編號)
:::

[TOC]

---

## Q1 Critical-Section Problem **((p)6 / 6.8)**

- Solve: Requirement [3x]
:::success
1. **Mutal Exclusion:** 有 Process 在跑 Critical Section(CS) 時，其他 Process 不能跑他自己的 CS
2. **Progress:** 如果沒有 Process 正在執行 CS ，而有 Process 想要跑 CS，這些 processes 不能被無限的延遲 (postpone)
> 也就是必須要有程式去跑 CS [name=JCxYIS]
3. **Bounded Waiting:** 若一支程式想執行 CS，等待的 process 數量必須是有限的，不能無限被插隊
:::

## Q2 Counting Semaphore **((p)6 / 6.34)**

:::success

wait(S) {
    while(S <= 0) {
        // busy wait
    }
    S--;
}

signal(S) {
    S++;
}

:::

## Q3 Deadlock **((p)7 / 8)**

:::success
**Necessary conditions [4x]** **((p)7 / 8.6)**
1. **Mutual exclusion** 在一個時間內，只能有一個 Process 使用資源
2. **Hold & Wait** 一個行程正掌握著某些資源，且正在等待其他資源
3. **No preemption** 資源只能由 Process 自願放棄，不能被要求放棄/徵收
4. **Circular wait** Process P1 在等 P0，P2 在等 P1， ...，Pn 在等 Pn-1，但是 P0 也排到隊伍內等 Pn

**How OS handle DEADLOCK [3x]** **((p)7 / 8.12)**
1. **讓 Deadlock 永不發生**
2. **讓 OS 有處理 Deadlock 的能力**
3. **裝作什麼都沒發生**

> **如何處理期末考的壓力**
> 1. 讓壓力不要發生
> - 不要修這門課
> - 不要讓自己陷入分數壓力
> 2. 讓自己有排解壓力的能力
> 3. 當作沒有段考，繼續快樂過生活
> [name=JCxYIS] [time=2 days before final exam]

**How OS recover from DEADLOCK [2x]** **((p)7 / 8.41)**
1. **Process Termination** 關掉其中一個或所有 Process (看投影片8.41)
2. **Resource Preemption** 選一個 victim，把他 rollback 到 safe state (看投影片8.42)

:::

## Q4 Banker's Algorithm **((p)7 / 8.25)**

- Content Needed
- Safe State?
- give a request, can it be granted immediately?

:::danger
以下資訊有誤，待修正
:::
:::success
**Need**

| | Allocation | MAX | Need |
|:---:|:----------:|:-------:|:-------:|
| P0 | 0 0 1 2 | 0 0 1 2 | 0 0 0 0 |
| P1 | 1 0 0 0 | 1 7 5 0 | 0 7 5 0 |
| P2 | 1 3 5 4 | 2 3 5 6 | 1 0 0 2 |
| P3 | 0 6 3 2 | 0 6 5 2 | 0 0 2 0 |
| P4 | 0 0 1 4 | 0 6 5 6 | 0 6 4 2 |

**Safe State?**

| | Resources |
| -------------- |:---------:|
| + P0 Available | 1 5 2 0 |
| - P1 Alloc | 1 0 0 0 |
| - P2 Alloc | 1 3 5 4 |
| - P3 Alloc | 0 6 3 2 |
| - P4 Alloc | 0 0 1 4 |

把式子減一減，都是赤字。
No.

**P1 Request for (0, 4, 2, 0)**

| | Allocation | MAX |
|:---:|:----------:|:-------:|
| P0 | 0 0 1 2 | 0 0 1 2 |
| P1 | 1 4 2 0 | 1 7 5 0 |

P1 所提的要求沒超過 MAX，繼續：

| | Resources |
| -------------- |:---------:|
| + P0 Available | 1 5 2 0 |
| - P1 Alloc | 1 4 2 0 |

P1 把資源提走不會有超支的問題 (不會進 unsafe state) ，所以 OK！

:::

## Q5 External Fragmentation **((p)8 / 9)**

- Solutions? [2x]

:::success
**Which suffers from external fragmentation?** **((p)8 / 9.21)**
First fit and Best fit

> As processes are loaded and removed from the memory, the free memory space is broken into little pieces (chunks). External fragmentation exists when there is enough total memory space to satisfy a request, but the available spaces are not contiguous; storage is fragmented into a large number of small chunks. This fragmentation problem could be severe. In the worst case, we could have blocks of free (or wasted) memory between every two processes. If all these small pieces of memory were in one big free block instead, we might be able to run several more processes.
reference: https://www.u-aizu.ac.jp/~yliu/teaching/os/lec13.html

**Solutions?**
1. 壓縮 (Compaction) **((p)8 / 9.22)**
2. 分頁 (Paging) **((p)8 / 9.23)**
3. 準備多套基底暫存器 (Multiple Base-Limit Registers) **(非課程內？)**
- 把 Program 拆成小塊易載入記憶體中，降低外部碎片的機率。
- http://blog.ncue.edu.tw/sys/lib/read_attach.php?id=13418

:::

## Q6 TLB EMAT **((p)8 / 9.34)**

:::success
如果透過TLB查到資料了，那麼我們就直接去 physical memory 就好：需要的時間為 $20+120=140$ ns。
如果透過TLB查不到資料，我們要額外花一次時間查 page table 再去 physical memory：需要的時間為 $20+120+120=260$ ns

$EMAT= 90\% \times 140 + 10\% \times 260ns= 152$ ns。

> 假如沒有TLB的話，我們永遠都需要先查 page table 再去 physical memory，
永遠都是 120+120=240ns

> 考試不用寫那麼多幹話，寫這麼多是順便複習祭祖...
> [name=JCxYIS]
:::

## Q7 Page Replacement **((p)9 / 10.33)**

:::success
先記著有 20 Access

**LRU**
跟祭祖的一樣， Omit!

**FIFO**
跟祭祖的一樣，但好啦列一下

| Ref String | Page 0 | Page 1 | Page 2 | FAULT? |
|:----------:|:------:|:------:|:------:|:------:|
| **7** | 7 | | | |
| **2** | 7 | 2 | | |
| **3** | 7 | 2 | 3 | |
| **1** | 1 | 2 | 3 | |
| **2** | 1 | 2 | 3 | HIT |
| **5** | 1 | 5 | 3 | |
| **3** | 1 | 5 | 3 | HIT |
| **4** | 1 | 5 | 4 | |
| **6** | 6 | 5 | 4 | |
| **7** | 6 | 7 | 4 | |
| **7** | 6 | 7 | 4 | HIT |
| **1** | 6 | 7 | 1 | |
| **0** | 0 | 7 | 1 | |
| **5** | 0 | 5 | 1 | |
| **4** | 0 | 5 | 4 | |
| **6** | 6 | 5 | 4 | |
| **2** | 6 | 2 | 4 | |
| **3** | 6 | 2 | 3 | |
| **0** | 0 | 2 | 3 | |
| **1** | 0 | 1 | 3 | |

17 Page Fault

:::

## Q8 Dick Scheduling **((p)12 / 11.17)**

:::success
題目得知磁頭在往右(大)的方向移動，從 143 出發

**SCAN ((p)12 / 11.21)**
> 電梯會來回在0樓~199樓之間移動，
> 據說電梯就是用這種演算法，
> 避免有人一直等不到電梯。
> https://ithelp.ithome.com.tw/articles/10229624

143 913 948 1022 1470 1509 1750 1774 130 86

**C-SCAN ((p)12 / 11.23)**
> 方法前面加「C-」(circular)表示只有單向的意思，
> 磁頭只往單個方向移動，
> 好比說電梯只有往上走，
> 當電梯到199樓的時候，
> 可以瞬間回到0樓往上走了。
> https://ithelp.ithome.com.tw/articles/10229624

143 913 948 1022 1470 1509 1750 1774 86 130
:::

## Q9 (BONUS) Peterson's software solution **((p)6.16)**

:::success
**Why 過氣?**
- 在多核心系統會發生錯誤：每顆 CPU 可能收到不一樣的 event order，進而導致 一個 Process 還沒跑完 Critical Section ，另一顆 CPU 就放下一個 Process 進去了

**Solution**
- 確定每個 CPU 處理的 event order 都是一樣的
- 可以用 Memory barrier 來確保

**Reference**
https://stackoverflow.com/questions/15675676/will-petersons-solution-work-correctly-on-modern-cpu-architectures

**注意**
建議去看投影片6.16~22，跟上面寫的不太一樣
:::