# 第一、二章
## 使用者模式如何得到內核模式的權限？
通過系統呼叫觸發陷阱，請求內核以自身權限代為執行指定的特權操作。

## 如何描述作業系統？
作業系統主要扮演兩個角色，對上是個抽象層，把各種複雜的硬體操作抽象成乾淨的API。對下是個資源管理者，負責公平、有效綠地分配硬體資源給各個行程。

# 第三章
## 程式、行程以及執行緒的區別
- 程式：在硬碟裡的靜態指令集合
- 行程：把程式載入記憶體讓計算機執行，作業系統資料分配與保護的基本單位。有獨立的記憶體空間以及系統資源
- 執行緒：在行程內動態執行的基本單位。除了特定幾種資料（暫存器、程式計數器、堆疊），其餘所有資料執行緒間都共用。

## 行程的狀態圖

## 行程的記憶體配置
- 堆疊（Stack）（往下）：存放函式呼叫的資訊。
- Memory Mapping Segment：共享函式庫以及其他被`mmap()`對應到記憶體的檔案。
- 堆積（Heap）（往上）：動態記憶體。
- Read/Write：
- Data：初始化的全域以及靜態變數
- BSS：未初始化或初始為零的全域以及靜態變數
- Read-only code segment：你的程式本身


## 行程控制段（Process Control Block）裡面有哪些東西？
作業系統對一個行程進行「完整控制」的基本資料。
- 行程識別資訊：PID, PPID, GID
- 處理器狀態
- 程式計數器
- 暫存器
- 行程狀態（Process State）
- 記憶體管理資訊
- 檔案管理資訊

Ready Queue 以及 Waiting Queue 就是把 PCB 串起來

> 倘若你對 `fork` 並不熟悉，強烈建議你自己動手做一次

# 第四、五章
## 並行（Concurrenc）與平行（Parallelism）
- Par：多個不同單元同時進行不同的工作
- Con：一個單元不斷切換不同的工作進行

## 使用者執行緒（User Threads）、內核執行緒以及硬體執行緒
- 使用者執行緒：
使用者空間管理的執行緒，由函式庫管理（像是`pthread`），內核只會看到一個行程。因此建立和切換都不需要進入核心模式，但若一個使用者執行緒因為I/O阻塞，核心會把整個行程都給阻塞。
- 內核執行緒：
由核心直接管理，阻塞時能達成真正的平行，但建立和切換因為涉及系統呼叫而較慢。
- 硬體執行緒：
實體CPU核心在記憶體停頓（Memory Stall）時切換別的任務，藉此對外偽裝成兩個核心。

## 顯性、隱性執行緒
- 顯性：由程式設計師指名決定要用
- 隱性：由編譯器、Library自己用的

## 執行緒池（Threads Pool）
先宣告一堆執行緒，要用的時候再分配工作給它。程式設計師只需管工作內容，而不需要在意執行緒的分配與釋放。

## 搶佔式（preemptive）和非搶佔式（non-preemptive）
（很重要喔）
非搶佔式：一個行程拿到CPU就跑到爽為止，直到自己主動放棄。在現代系統就是個垃圾。
搶佔式：作業系統有個計時器中斷（Timer Interrupt），時間一到就會強行打斷該行程，讓排程器重新決定換誰。

> 每個排程器的特性都要會，因為Quiz 2的計算題必考。

## PCS（Process-Contention Scope）和SCS（System-Contention Scope）
- PCS：
使用者執行緒之間競爭行程被分配到的少數內核執行緒，屬於`many-to-many`以及`many-to-one`
- SCS：
所有的內核執行緒競爭所有的核心（幾乎現在作業系統都是這種），屬於 `one-to-one`

## 負載平衡（Loading Balancing）以及處理器親和性（Processor Affinity）
- 負載平衡：要讓所有核心都有事情做。排程器會在比較忙和比較閒的核心間不斷推拉執行緒。
- 處理器親和性：盡量讓一個執行緒在同個核心上跑。在執行緒執行過程中，一定會有資料放在該核心的L1/L2快取。如果轉移到其他核心那那些資料就要重新從記憶體抓取。
- soft：盡量在同個處理器執行
- hard：指定會在哪些處理器上執行

兩點通常衝突（非常直觀吧）。排程器通常會盡量維持 soft affinity，若負載真太不均衡才選擇遷移。

## 即時排程（Real-time Scheduling）
- soft realtime：盡量在期限內完成工作，但不保證
- hard realtime：保證、一定、必須要在期限內完成工作（~~就算獻出心臟也在所不惜~~

### 即時排程演算法
- Rate-Monotonic：
靜態優先級演算法，優先度在執行前決定後就永不改變。越頻繁的任務優先級越高
- Earliest-Deadline-First：
動態優先級演算法。任何時間下個期限最接近的任務就有最高的優先級。

# 第六章
## 競賽條件（Race Condition）的定義
當多個工作存取和操作同一個共享資料時，執行的最終結果取決於它們執行的特定時序。

entry section
// critical section
exit section
// remainder

## 生產者消費者問題
要怎麼設計導致需要保護的 race condition。

## 解決競賽條件的三大要點
- mutual exclusion
- 一次只准一個工作進入CS（Critical Section）
- progress
- 只有一個工作想進CS，它一定能馬上進去
- 若有多個工作想進CS，一定能再有限時間內選一個進去
- bounded-waiting
- 必須保證行程進入CS有次數上限（不要永遠輪不到某個行程就好）

> 一定會考一段程式，要你驗證他可不可以解決競賽條件

> Peterson's combined Solution 一定會考，因為它能夠解決以上三點。

## Synchronization Hardware
你各位一定都知道，一個高階語言指令，會被翻譯成很多段組合語言指令，是可分割的。而編譯器或CPU會為了效能擅自調換順序，這個邏輯就會崩潰（像是Peterson's combined Solution）。

因此，硬體提供原子操作，保證中間絕對絕對絕對喔齁齁不會被打斷嘻嘻。

### test_and_set

boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = true;
	return rv;
}

一個工作的 `test_and_set` 回傳 `true` 以後，其他工作一律都會是 `false`，直到那個成功進入CS的工作在 `exit section` 把 `target` 設定回 `true`。

### compare_and_swap

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	if (*value == expected)
		*value = new_value;
	return temp;
}

比較 `*value` 是否符合 `expected`，若為真則把 `*value` 改為 `new_value` 回傳成功。反之則什麼都不做並回傳失敗。

### 記憶體屏障（Memory Barrier ）

「在這條線之前的所有記憶體讀寫操作，必須全部完成，並且結果對所有核心可見之後，才能開始執行這條線之後的任何記憶體讀寫操作。」

在 Peterson's Solution 中的 `flag[i] = true;` 和 `while (flag[j] && turn == j);` 插一個記憶體屏障，就能強制 CPU 按照你寫的邏輯順序去執行，解決了重排導致的失效問題。

> 會考如何用CaS實現以及證明
> 
> 一定要把這段程式碼搞清楚