# 作業系統OS 面試考題整理
1. **什麼是作業系統？**
簡單：管理電腦硬體與軟體資源的系統。
功能：
* 行程管理(processing management)
* 記憶體管理(memory management)
* 檔案系統(file system)
* 網路通訊(networking)
* 安全機制(security)
* 使用者介面(user interface)
* 驅動程式(device drivers)
3. **program、process、thread**
* Program：放在二次儲存裝置中，尚沒有被Load到記憶體的一堆Code，稱之為"程式"(死的)

* Process：
* OS分配資源的對象
* 已經被Load到記憶體中，任何一行Code隨時會被CPU執行，且其宣告的在記憶體的變數的值會隨著需求而不斷變動。
* 在多工作業系統可以同時運行多的process，然而一個CPU一次只能做一件事情，CPU數量少於運行中的process，所以需要排程(Schedualing)
* 每個process在記憶體中有不同的擺放方式，分頁式(page)解決外部碎裂(external framentation)，分段式(segment)解決內部碎裂(internal fragmentation)，需要Memory Management
* 有時process需要記憶體大於實體記憶體，需要二次儲存裝置disk充當虛擬記憶體(virtual memory)，需要避免Page Fault，防止Trahing

* Thread：
* 分配CPU time的對象
* 同一個process下有許多自己的分身 Thread，是CPU執行最小單位。
* 因為都在process下，可以共享preocess的記憶體。
* 若兩個Thread要存取同一個Global Varible，可能會有同步問題(Synchronization)。
* Thread之間會互搶資源，而造成死結(Deadlock)

> 一個Process有：
> * Code Section(程式碼) [存在Memory Space]
> * Data Section(資料區間) [存在Memory Space]
> * Program Counter(程式計數器)
> * CPU Register
> * Stack(process之間互CALL或遞迴，用以存放返回地址)

> 一個Thread有：
> * Code Section(程式碼) [與同一個Process的Threads共享]
> * Data Section(資料區間) [與同一個Process的Threads共享]
> * Program Counter(程式計數器)
> * Register Set
> * Stack(推疊)

4. **行程狀態**

5. **CPU Scheduler**
* Scheduling Criteria(衡量排班效能準則)
* CPU Utilization(使用率)
* Def: (Use Time)/(Use Time+Idle Time)
* Throughput(產能)
* Def:單位時間能完成的Process數
* Waiting Time(等待時間)
* Process待在Ready Queue等待CPU的時間(一個Process真正受到排班法影響的準則)
* Turnaround Time(完成時間)
* Def:process進入系統到期完成工作的時間
* Response Time(反應時間)
* 自User下命令到系統產生第一個回應的時間

* Preemptive vs. Non-preemptive
| Preemptive | Non-preemptive |
| ---------- | -------------- |
| 排班效益佳 | Waiting Time ↑|
| Context Switching次數較頻繁|Context Switching次數較少|
| Process的完成時間不可預期|可預期 |
| 平均等待時間短| 平均等待時間長|
| 不會發生護衞效應| 會有護衞效應發生 |

* Starvation
* Def: 長期排不到足夠的CPU，無限等待
* 解決方式:
* 採用Fair的Scheduler
* Aging
* Scheduling Algorithms
* FCFS(先到先做)
* 最簡單
* 爛
* Convoy Effect(護衛效應)
* SJF(最短先做)
* 最難(太過理想，無法預測誰最短)
* 最好
* SRTF(剩最短的先做)
* 較短等待時間
* 插隊次數多(context switch多->負擔大)
* RR(循環分時)
* 規定Time Quantum(需要硬體支援-Timer)
* 互動良好
* Multilevel Queue(多層佇列)
* Multilevel Feedback Queue(多層回饋佇列)

6. **process間的溝通**

| | Share Memory | Message Passing |
| ---- | ------------ | --------------- |
| Def | 共享記憶體(變數)|1.建立link 2.互傳訊息 3.釋放link |
| 共享性 | 所有process都可以讀取|只限定建立連結|
| OS支援 |提供共享記憶體空間 | link 管理|
| 負擔 | programer較重 | OS較重 |
| 處理機制 | 小心race condition | link控制、訊息遺失 |

7. **Race Condition**
* Def:共享變數之最終結果値，會因Processes之間執行順序不同而有所不同
* 解決辦法:
* Disable Interrupt(停止使用中斷)
* Critical Section Design(臨界區間設計)
8. **Critical Section Design**
* 必須滿足三個性質
* Mutual Exclusion(互斥)
* Def:任一時間點，只允許一個 process 進入他自已的C.S.內活動。
* Progress(行進)
* Cond1:不想進入C.S.的 process 不可以阻礙其它 process 進入C.S.，即不可參與進入C.S.的決策過程。
* Cond2:必須在有限的時間從想進入C.S.的 process 中，挑選其中一個 process 進入C.S.，**隱含No Deadlock**。
* tip:有空位時讓「想進的人」「馬上」進入。
* Bounded Waiting(有限等待)
* 自 process 提出進入C.S.的申請到獲准進入C.S.的等待時間是有限的。即若有n個processes想進入，則任一process至多等待n-1次即可進入，**隱含No starvation**。

* 解決辦法
* S.W. solution : Peterson's solution

            bool flag[2] = {false, false};         //分別代表P0及P1是否想進入CS
            int turn;                              //turn = 1或0，代表這一回合誰的"進入權"比較高

            //P0
            while(1) {                             //代表P0周而復始地想進入CS
                flag[0] = true;                    //告訴大家，P0想進入CS (我要進去我要先說)
                turn = 1;                          //如果P1也想進入CS，讓P1先進去(但我會先禮讓對方)
                while(flag[1] == true && turn ==1) //P1想進入，且P1的進入權比較高(你要進去，比權力，如果輸了就讓你)
                    ;                              //用while loop實作出wait

                //跳出迴圈，表示可以進去CS    
                //Critical Section, 可以於此更新共享資料結構

                flag[0] = false;                   //離開CS,因此將flag[0]設為false，表示P0目前不需要待在CS (離開的時候我一定會告知)   
            }

* H.W. instructure
* 直接提供具有Atomic特性的指令，讓程式碼可以在單一時間點被完成，不會中途被插斷
* Test_and_Set

            int Test_and_Set(int* Target){
                int temp;
                temp = *Target;
                *Target = 1;
                return temp;
            }
            
            bool Lock = false;//共享變數
            //P0
            while(Test_and_Set(Lock)) ;//回傳值為true，跳出迴圈，並設定Lock為True
            //別的process因為Lock現在是true，會被困在迴圈中
            //CS
            Lock = false;

* SWAP

            void SWAP(int* a, int* b){
                int temp = *a;
                *a = *b;
                *b = temp;
            }
            
            bool Lock = false;//共享變數
            //P0
            key = true
            do{
                SWAP(Lock,key)
            }while(key != false) ;
            //CS
            Lock = false;

* Semaphore(號誌)
* Def: 用來解決CS跟同步問題的一種資料型態
* 假設變數S為semaphore，其為Int，通常初值為1
* 提供兩個Atomic operation:
* Wait(S) : while(S<=0) do no_op;
S=S-1;
* Signal(S) : S=S+1;

9. 同步機制
* Spinlock
* Busy waiting
* 佔CPU，不用context switch，適用
* Thread only
* Mutex
* Sleep waiting
* Thread only
* 擁有權:只有上鎖的人可以解鎖
* Semaphore
* Sleep waiting
* 允許多個thread同時往問同一資源
10. dead lock
* Def:系統中存在一組Processes陷入“互相等待對方所擁有之資源 ” 的情況(即: Circular Waiting) ，造成所有Processes皆無法往下執行，使得CPU 利用度及産能大幅降低。
* 形成Dead Lock的四個必要條件
* Mutual exclusion
* Def:資源在同一時間，只能被一個Process持有。
* Hold and wait
* Def:Process直到拿到下一個資源前，不會主動釋出自己的資源
* No preemption
* Def:必須等待其他Process主動釋放資源才可以使用。
* Circular waiting
* Def:每個人都在互等對方的資源
* 處理方式
* Dead Lock Prevention
* 觀念：打破四必要條件之一，保證死結不會發生
* 缺點：Resource Utilization低，Throughput低
* Dead Lock Avoidance
* 定義：針對提出資源申請的Process，來檢視系統“是否會因接受此一Process的申請而進入死結”
* 缺點：透過演算法，耗時，也可以保證不會有死結
* Dead Lock Detecion & Recovey
* 定義偵測死結是否存在，若存在打破他
* 優點：Resource Utilization高，Throughput高
* 缺點：打破死結需要的cost高

10. 什麼是Muti-thread
11. user mode & kernel mode

12. system call

14. pipeline hazard是什麼,cache是什麼
15. 什麼是virtual memory
16. 記憶體分配方式

16. DMA
17. RAM、register、cache

###### tags: `面試`