---
tags: 作業系統
title: 鄭欣明作業系統期末考古
---

### 6. Please describe the definitions of deadlock prevention, avoidance, detection, recovery

1. prevention
預防比較難，因此需要針對deadlock的四個條件做處理。
- Mutual Exclusion：不共用資源不會互斥，但基本上不可能。
- Hold and Wait：process必須保證再要求一項資源時，不能佔用其他資源，除非他可以一次取得所有資源。
- No Preemption：只要process握有一些資源，但得不到其他的，就要先全部釋放，再重新申請。
- Circular Wait：對 resource type 強制安排線性順序，不讓circular wait 的條件達成
3. avoidance
- 想要avoidance的話 system 必須要知道事有。
- 每個process 要知道對不同的resource type需要多少，這是最重要的
- deadlock-avoidance演算法檢查時，要確定不會有circular wait的狀況發生
- 在資源分配時要看狀況，再決定是不是要再給resource。
- Avoidance的演算法分為兩種
- Resources Aollocation Graph(RAG)：如果resource type 只有一種 instance
- Banker's Algorithm：如果resource types有多個instance

4. detection & revocery
- 容許發生deadlock，但要能偵測到且恢復
- 偵測到有deadlock的process可以選擇一把它給終結或是把資源給中斷。如果把它終結掉，可以依照優先權高低或是資源用的多寡還有其他條件，去決定要砍掉誰，一次砍一個process。如果是把資源中斷，就找資源使用最少的開始犧牲，之後重新再來一次，不過可能導致使用資源少的程式會stravation。

### 7. Please describe the differences between clone, fork and vfork
- fork/vfork都沒有參數，而clone帶有參數
- 執行vfork的時候，完全和父process共享RAM，所以vfork之後對所有的數據進行修改，父process也會看見。而fork則指示延遲了複製，在修改數據後還是需要複製頁面。
- clone是fork的推廣形式，他允許新的process指定具體需要與父process共享哪些資源，比fork更靈活

### 8. Please describe how buddy system and Slab Allocator for kernel memory allocation
- Buddy system：讓固定大小的每兩塊組成更大的連續page，因此大小為2的密次方，類似2048遊戲那樣，優點可以快速合併大的chunk，缺點容易造成fregamentation
- EX：有33bKB的但只能用64KB的page，浪費了31KB的空間
- Slab Allocation：此方法保留了的剛存取過的object data type,以便在後續分配相同type的時候可以重用。slab是由一或多個physically contiguous page組成，而cache由一或多個slab組成，object會去使用cache。此方法沒有fragmentation的問題

### 9. Please describe the difference between segmentation and paging approachs for use program memory allocation
- paging：將實體記憶體切成最小單位frame，在virtual memory則稱為page，兩者大小一樣，將得到的虛擬記憶體位置除以size大小得到第幾頁為q值，餘數則是s值，q值即是page table的key值用來求map的value，value則是指實體記憶體內的第幾個frame，值則是在page或frame的第幾個記憶體
- segmentation：不將記憶體分成某個特定的最小單位，而是依照要load進來的process大小，給定一個base register和limit register，base代表開頭，limit代表長度，並透過map把base當作key值，value一樣儲存在實體記憶體的位置。
- **paging會有內部斷裂，segmentation有外部斷裂**

### 11-B. What's the drawback of busy waiting when we implement semaphore
- 浪費CPU cycle，因為process會一直等待，這叫做spinlock
- 改善：在等待時把process移到waiting queue中 (等同於sleep())

### 12-A. What's the different between a program, a process, and a thread
- program：只得就是我們所寫的code，而且尚未被載入記憶體裡。
- process：process則是指已經執行並被載入記憶體，隨時會被CPU執行，每一個process都是獨立的，但不是最小單位
- thread：可執行的最小單位，一個process底下有很多thread，這些thread5共享資源如記憶體、變數，但不同的process則否

### 12-B. Please briefly describe how context switch between processes works
- 讓多個process可以共用單一CPU的資源，進行context switch的時候，會先儲存當前process的狀態到該process對應的PCB，然後load要執行的process的PCB到CPU的register

### 12-C. What's the differences between Uesr Thread, Kernel Thread, and Hardware Thread
- Hardware thread：物理上能夠同時運作的執行單元數量
- 單核心的 CPU 只有一個 Hardware Thread
- 多核心的 CPU 可以有多個 Hardware Thread
- 原本這件事其實不重要，但在 Intel 做出 Hyperthreading 的技術以後，一顆 CPU 可以同時執行兩個指令，也就是有兩個 Hardware Thread
- 實際上這種 CPU 也並不總是能夠同時執行兩個指令，但對作業系統來說，一次可以放兩個指令給這顆 CPU
- User thread：程式所產生的thread
- 對程式而言，User Thread 代表兩項並行的工作，執行的速度以及順序無法保證
- kernel thread：在作業系統中被排程的單位
- 作業系統在運作時，會帶有很多 Kernel Thread，這些 Kernel Thread 要何時被放到 Hardware Thread 上執行，由作業系統中的排程器決定

### 16.Please describe the definition of thrashing and the reason why thrashing happen. To prevent thrashing, we must provide a process frames as many as it actually using. Typically, it is achieved by considering locality and please why? Please also discribe the famous solution "working-set model".
- definition of trashing：Thrashing會發生在process分配到的frame不夠多時，頻繁發生page fault，使CPU的使用效率急速下降
- Why thrashing happen：Frame不夠，發生page fault, Page replacement發生，frame又不夠用，導致CPU效率低，因為process忙著swap in/out, CPU閒下來，又抓更多process進來工作
- why achieved by locality：Process執行時，對於Memory的存取區域並非是均勻(Uniform)的，而是具有區域性(Locality)的特質
- working-set model：利用loaclity觀察一段時間內一個process所使用的pages數量，因為process的需求是動態的所以locality隨時間改變，OS要持續track process 的locality。Working Set:一段時間內process reference 的page數量，設為WSS，frame總需求數設為D=∑WSS, D > m(availabe frames) --> trashing
- D << m：增加 degree of multiprogramming
- D > m：把整個 process suspend (mid-term scheduler) 掉，free 該 process 所有的 frames

優點：
- 在最大化 multiprogramming 的情況下，同時防止 trashing 的發生
- 可以最大化 CPU 使用率

缺點
- tracking 的成本很高

### 18. Describe the following items：
#### a. In NUMA system for frame allocation, why the goal is to have memory frames allocated "as close as possible" to the CPU on which the process is running
> 因為在NUMA系統中，記憶體存取的時間取決於記憶體相對CPU的位置，因此可以的話越近越好，這樣存取的速度比較快
#### b. What is "Belady's annmaly" in page replacement
> 給予更多的frame卻發生更多的page fault
#### c. What is acyclic-graph directories
> 非循環式圖形目錄，他能共享子目錄跟檔案，也就是說會有別名。
#### d. Why interrupts from I/O device are much better than polling
> interrupt可比喻成上課直接舉手打斷老師，然後老師中斷並回你的問題，而polling則是不能舉手問問題，老師會挨個詢問有沒有問題，但若是剛好被問完後突然有問題，就要等到下次老師問完一圈重新問你才能發問，因此interrupt的主動打斷，比起polling的被動打斷會有效率很多，因為挨個詢問但都沒有問題的時候非常浪費時間
#### e. What is "double buffering" in kernel I/O subsystem
> 進一步加快輸入和輸出速度，提高裝置利用率，也稱緩衝對換（Buffer Swapping）
- 資料送入第一緩衝區，裝滿後轉向第二緩衝區。
- 輸入：資料送入第一緩衝區，裝滿後轉向第二緩衝區。
- 讀出：OS從第一緩衝區中移出資料，送入使用者程序，再由CPU對資料進行計算。
>兩個緩衝區，CPU和外設不再針對一塊交替，可能實現連續處理無需等待對方。前提是CPU和外設對一塊資料的處理速度相近。而如下圖情況CPU仍需等待慢速裝置。
#### f. What is Direct Memory Acess(DMA)
> 一種記憶體存取技術，允許某些電腦內部的硬體子系統以獨立地直接讀寫系統記憶體，而不需中央處理器介入處理。同等程度的處理器負擔下，DMA是一種快速的資料傳送方式。很多硬體的系統會使用DMA。
#### g. Which of the following memory management methods is not for kernel process
(1) Buddy system (2) Slub (3) Typical paging (4)Slab
> (3)Typical paging
#### ==h. Which of the following programming techniques and structures are "good" for a demand-paged environment==
(1) Hashed symbol (2) Array (3) Linked List (4)Goto
> ?
#### i. RAID have been widely used to provide reliability via redundancy. Please make the right binding between RAID-1 and one of following explanations
(1) block-interleaved parity (2) non-redundant (3) mirror disks (4) bit-interleaved
> (3) mirror disks
#### j. 同 5-g
> ?

#### 21. Please describe how the following features change when page size is increased
a. Fragmentation
- 上升

b. Page table size
- 降低

c. Resolution （解析度？）題目就這樣0.0
- 更差
- (老師上課只說，page size越小的resolution就越高)
- 較小的page size更能把「真正需要」的載入，如果page size = 1GB，那麼可能會載入很多不是真正需要的 (by 中正大學 羅習五)

d. I/O overhead
- 上升

e. Number of page faults
- 如果沒有Belady's Anomaly，page fault的數量應該要增加
- 平均的pages數量減少，page fault應該會降低吧

f Locality
- 越分散

g. TLB size and effectiveness
- 在 TLB size 不變的情況下，hit ratio 會變高，進而使effectiveness 上升（更有效率）
- 可以透過更少的 TLB size 達到一樣的 effectiveness

### 22. Please define four usages of semaphores and present an example for each usage.
1. Mutual exclusion
- mutex locks
2. Force suspend
- 讓execution有一個特定順序
3. Count-down lock
- A semaphore has an implicit counter
- 同時可讓n個process進入critical section，當滿了就會鎖住，直到這n個process中有人出CS
4. Notification
- Indicate that an event has occurred
- signal() &　wait()