# OS 面試題

:::success
**面試整理**
1. [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)
2. [聯發科上機考面試整理](https://hackmd.io/@Rance/SkSJL_5gX)
:::

## 10/10

### 4. 什麼是OS?
from [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)

確保 Process 可以正確執行，不會讓 Process 跟 Process 之間互相干擾，並透過 kernel mode 跟 user mode 保護硬體，並提供 high level 的 system call 讓使用者不能直接操作硬體，簡化操作，也更加有效率等。

### 54. TCP/IP Model
from [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)


OSI 7 layers
physical layer
session layer
transport layer //tcp
Network //IP
link layer //mac addr
physical

### 10. pointer
From [聯發科上機考面試整理](https://hackmd.io/@Rance/SkSJL_5gX)

int a[5]={1,2,3,4,5};
int *p=a;
*(p++)+=123;
*(++p)+=123;

請問a陣列的每個值為何?
{124, 2, 126, 4, 5}

## 10/15
### 13.寫一個 function 可傳入正整數參數 N，回傳 1 + 2 + 3 +…+N 的和:
From [聯發科上機考面試整理](https://hackmd.io/@Rance/SkSJL_5gX)

:::success

int nsum (int n) {
    return (1+n)*n/2;
}

:::

### 15. 寫一個“標準”巨集MIN ，這個巨集輸入兩個參數並返回較小的一個。
From [聯發科上機考面試整理](https://hackmd.io/@Rance/SkSJL_5gX)

#define min(a,b) ((a>b?b:a))

### 10. atomic
From [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)
:::warning
atomic transaction
因為一個 transaction 由一 instruction set 所組成
如果指明了某一 transaction 是 atomic
代表這個 transaction 在執行時, 其所屬的 instruction set 不是全部執行
不然就是全部不執行, 沒有那種執行一半的
:::

### 13.Real-time operating system, RTOS
From [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)
:::danger
實時作業系統與一般的作業系統相比，最大的特色就是其「實時性」，
也就是說，如果有一個任務需要執行，
實時作業系統會馬上（在較短時間內）執行該任務，
不會有較長的延時。這種特性保證了各個任務的及時執行
設計實時作業系統的首要目標不是高的吞吐量，而是保證任務在特定時間內完成
:::

### 44. write through / write back 的差別，哪個快？
From [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)

write through: 是直接把資料寫回記憶體
write back: 是先將資料按一定數量接受下來﹐然後將相同位址的資料一次過整批送回記憶體
write back快很多，早期的 cache 只有 write through 模式﹐但現在的 cache 都使用 write back 模式

## 10/17

### 5. 講解一下如何避免 Race Condition
From [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)
#### 5-1
解決此問題的基本概念，便是讓共享的資源在不同執行緒內可以受到控制，
但有時因為設計不良，便會出現競爭危害（race hazard）。又稱為競爭條件（race condition）
OS本身有提供 Semaphore 跟 Monitor 只要使用得當就可以避免這樣的問題。

#### 5-2
下列程式會產生 race codition問題，我們無法確定最後` var `的值是 `10 `或是` 20`?

Parent thread:                         Child thread:

int var; // global variable

// create child thread
pthread_create(...)                          
var = 20;      
//
                                       //

                                       var = 10;
                                       exit
pthread_join(...)
printf("%d\n", var);

Parent thread: Child thread:

int var; // global variable
pthread_lock lock;
// create child thread
pthread_create(...)
pthread_mutex_lock(&lock)
var = 20;
pthread_mutex_unlock(&lock)
pthread_mutex_lock(&lock)
var = 10;
pthread_mutex_unlock(&lock)
exit
pthread_join(...)
printf("%d\n", var);

var = 10

:::info
#### ANS:
直覺的解法便是讓兩段設定var的程序有先後關係，如下例，
透過訊息的傳遞會讓設定 var 值的程序有 "happens-before" 關係，
也就是 var = 20; 一定會在 var = 10; 之前發生。因此最後的結果固定會是10。
Parent thread: Child thread:

int var;

// create child thread
pthread_create(...)
var = 20;
// send message to child
// wait for message to arrive
var = 10;
exit

// wait for child
pthread_join(...)
printf("%d\n", var);

所以，若是某個記憶體內的資料，會同時被兩個不同的 thread進行存取，
我們可以先檢查這兩個 thread 寫入同份資料時是否存在 "happens-before relation"，
若不存在此關係，便存在 race condition.
:::

### 8. CPU怎麼處理interrupt ? 處理的時候會做什麼?
From [面試整理](https://hackmd.io/@g9tdU4gDSTiEZrerd0g7-w/SyCXEfsSE#4)


● Interrupt 的種類
**I. External Interrupt（外部中斷）:** CPU 外的週邊元件所引起的。
（I/O Complete Interrupt, I/O Device error）
**II. Internal Interrupt（內部中斷）:** 不合法的用法所引起的。
（Debug、Divide-by-zero、overflow）
**III. Software Interrupt（軟體中斷）：** 使用者程式在執行時，若需要OS 提供服
務時，會藉由System Call 來呼叫OS 執行對應的service routine，完成服務請求
後，再將結果傳回給使用者程式。

● Interrupt 的處理流程
**Setps**
1. 暫停目前process 之執行。
2. 保存此process 當時執行狀況。
3. OS 會根據Interrupt ID 查尋Interrupt vector。
4. 取得ISR（Interrupt Service Routine）的起始位址。
5. ISR 執行。
6. ISR 執行完成，回到原先中斷前的執行。

**Interrupt I/O（中斷式I/O）**
Steps
1. 發出I/O 要求給CPU（OS）。
2. CPU 設定I/O commands 給I/O Device controller。
3. I/O Device 運作執行。
4. PA 等待 I/O 完成。
5. PB 取得CPU 執行。
6. 當I/O 運作完成，則I/O 會發出一個「I/O Complete Interrupt」（I/O完成中斷）
通知OS。
7. OS 暫停目前process 的執行。
8. OS根據Interrupt ID 去查詢Interrupt vector，取出對應的ISR（Interrupt
Service Routine）的起始位址。
9. CPU 執行ISR。
10.ISR 執行完畢，OS 通知PA 其I/O 要求完成，將PA 的狀態改成Ready。
11.由CPU 排班挑選process 執行。

ISR:
ISR簡單來說就是中斷會跳去執行的函式,而他跟task或process不同的地方是,
做context switch的時候ISR只會PUSH部份暫存器,而task或process會push所有的暫存器

## 20.Find the possible error
From [聯發科上機考面試整理](https://hackmd.io/@Rance/SkSJL_5gX)

int ival;
int **p; pointer to pointer
Ival = *p; <-

**ANS:**
reference a pointer to a int

## 10/23

### 10. 介紹一下Mutex、Semaphore、Spinlock
:::info
30秒：
最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，
而 Semaphore 沒有這個限制，
可以由原本的 thread 或是另外一個 thread 解開。
另外，Mutex 只能讓一個 thread 進入 critical section，
Semaphore 的話則可以設定要讓幾個 thread 進入。
這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。
_
60秒 (cont.)：
舉例而言，Mutex 的兩個特性：
一個是只能有持鎖人解鎖、一個是在釋放鎖之前不能退出的特性，
讓 Mutex 叫常使用在 critical section 只能有一個 thread 進入，
而且要避免 priority inversion 的時候；
Semaphore 也能透過 binary semaphore 做到類似的事情，
卻沒有辦法避免 priority inversion 出現。
_
120秒 (cont.)：
而 Semaphore 更常是用在同步兩個 thread 或功能上面，
因為 Semaphore 實際上使用的是 signal 的 up 與 down，
讓 Semaphore 可以變成是一種 notification 的作用，
例如 A thread 執行到某個地方時 B thread 才能繼續下去，
就可以使用 Semaphore 來達成這樣的作用。
Mutex是一把鑰匙，一個人拿了就可進入一個房間，出來的時候把鑰匙交給隊列的第一個。
一般的用法是用於串行化對critical section代碼的訪問，
保證這段代碼不會被並行的運行。
(Function前用mutex lock，執行完unction後把mutex後釋出，
sleep給其他thread使用)
(A mutex is really a semaphore with value 1.)
:::

:::info
Semaphore是一件可以容納N人的房間，如果人不滿就可以進去，
如果人滿了，就要等待有人出來。
對於N=1的情況，稱為binary semaphore。
一般的用法是，用於限制對於某一資源的同時訪問。

semaphore, mutex 會有睡覺的副作用,
什麼是「睡覺」, 就是原本在執行的這段程式碼,
在執行了 semaphore, mutex 的 function 之後,
有可能會自己把 cpu 讓出去 (有點像是 coroutine 的 yeild), 要
等一會兒才會再繼續執行;
那 spinlock 呢? 答案很有趣, 在 kernel space 不會,
甚是在 kernel space 的 spinlock 還需要關閉中斷,
很多情境都比 user mode 複雜;
在 user space 一樣會讓出 cpu,
不過是被迫讓出去 (os 排程的管理), 而不是自己讓出去

spinlock
spinlock利用test and set這個指令看有沒有辦法取得lock
因為是指令層級的操作所以有辦法達到atomic
當lock無法取得時會用polling的方式不斷嘗試
特別的地方是當他取得lock時 process將不會進入睡眠（沒有context switch）
效能會比semaphore好 因為他不做context switch可以一直執行
:::
:::info
**mutex vs spinlock**
Mutex 屬於 sleep-waiting 類型的鎖。
Spin lock 屬於 busy-waiting 類型的鎖。
只能用在 thread 程式, 如果是兩個 process,
你沒辦法用 mutex/spinlock 去保護共享資源,
共享資源並非只有共享記憶體/變數, file, 硬體資源都是。

**mutex vs semaphore**
mutex 除了擁有者外還有優先權的概念, 類似 thread 的優先權那樣
semaphore 不只能用在 thread 程式, 兩個不同的 process 也可以用 semaphore 共享資源。

不過 3 者的共同點都需要 atomic 的操作。
:::

### 18. Memory Hierarchy
register
cache
memory
disk(Hard disk)
Tape

:::info

Register – Cache – Main Memory – Disk –Tape
愈快 ← 速度 → 愈慢
愈昂貴 ← 價格 → 愈便宜
愈小 ← 容量 → 愈大

**SRAM (Static RAM)：** 用Flip/Flop儲存，速度快，密度低(元件大)，成本高，作Cache等快速記憶體，不須Refresh。
**DRAM (Dynamic RAM)：** 用電容器製作，速度慢，密度高(元件小)，成本低，為Main Memory的主體，須Refresh
儲存的電荷會隨著時間漸漸消失，因此需要有個再充電（Refresh）的動作保持電容儲存的資料

:::