HackMD
作業系統
什麼是OS?
確保行程 (Process) 可以獨立執行，並透過 kernel mode 跟 user mode 保護硬體，並提供系統呼叫 (system call) 讓使用者不能直接操作硬體，簡化操作，也更加有效率等。
1. Process Concept
行程與執行緒之間的狀態轉換類別
- 行程：具有一定獨立功能的程式關於某個資料集合上的一次執行活動，程式是系統進行資源分配和排程的一個獨立單位。
- 執行緒：程式的一個實體，是CPU排程和分派的基本單位，它是比程式更小的能獨立執行的基本單位。
行程的狀態
- 就緒：行程已處於準備好執行的狀態，即行程已分配到除 CPU 外的所有必要資源後，只要再獲得 CPU，便可立即執行
- 執行：行程處於 CPU 執行狀態
- 等待：正在執行的行程遇到 I/O 請求等，暫時無法繼續執行
行程的通訊方式有哪些？
行程間的通訊 (Interprocess, IPC)，是指行程之間的資訊交換。通訊機制可歸結為三大類：
- 共享記憶體 (Shared Memory): 共享記憶體允許兩個或多個程式訪問同一個邏輯記憶體。共享記憶體是最快的IPC方式，它是針對其它程式間通訊方式執行效率低而專門設計的。
- 舉例：剪貼簿
- 有同步的問題
- 訊息傳遞 (Message Passing): Process A 和 Process B 需要傳送訊息到作業系統才可以如下圖所示
上下文切換 (Context Switch)
對於單核單執行緒的處理器而言，在某一時刻只能執行一條CPU指令。上下文切換(Context Switch)是一種將CPU資源從一個程式分配給另一個程式的機制。從使用者角度看，計算機能夠並行執行多個程式，這恰恰是作業系統通過快速上下文切換造成的結果。在切換的過程中，作業系統需要先儲存當前程式的狀態(包括記憶體空間的指標，當前執行完的指令等等)，再讀入下一個程式的狀態，然後執行此程式。
2. Multithreaded Programming
3. Process Scheduler
排程種類
- 高階排程：(Long-term Scheduling, job Scheduler)又稱為作業排程，它決定把後備作業調入記憶體執行
- 中級排程：(Medium-term Scheduling)又稱為在虛擬儲存器中引入，在內、外存對換區進行程式對換
- 低階排程：(Short-term Scheduling, CPU Scheduler)又稱為程式排程，它決定把就緒佇列的某程式獲得CPU
非搶佔式排程與搶佔式排程
- 非搶佔式：分派程式一旦把處理機分配給某程式後便讓它一直執行下去，直到程式完成或發生程式排程程式排程某事件而阻塞時，才把處理機分配給另一個程式。
- 搶佔式：作業系統將正在執行的程式強行暫停，由排程程式將CPU分配給其他就緒程式的排程方式。
排程策略的設計
響應時間: 從使用者輸入到產生反應的時間
週轉時間: 從任務開始到任務結束的時間
CPU任務可以分為互動式任務和批處理任務，排程最終的目標是合理的使用CPU，使得互動式任務的響應時間儘可能短，使用者不至於感到延遲，同時使得批處理任務的週轉時間儘可能短，減少使用者等待的時間。
程式之間的排程演算法有哪些？
排程演算法是指：根據系統的資源分配策略所規定的資源分配演算法
- 先來先服務的排程演算法：先來先服務排程演算法是一種最簡單的排程演算法，也稱為先進先出或嚴格排隊方案
- 時間片輪轉排程演算法主要適用於分時系統。在這種演算法中，系統將所有就緒程式按到達時間的先後次序排成一個佇列。
- 短作業優先排程演算法：短作業優先排程演算法是指對短作業優先排程的演算法，從後備佇列中選擇一個或若干個估計執行時間最短的作業，將它們調入記憶體執行。
- 最短剩餘時間優先排程演算法
- 高響應比優先排程演算法
- 優先順序排程演算法
4. Synchronization
生產者與消費者問題
解釋並行和平行的含義區別
- 並行(Concurrenct): 兩個事件和多個事件在同一時刻發生，發生在不同的實體上。
- 平行(Parallel): 兩個事件或者多個事件在同一時間間隔發生，發生在統一實體。
同步和互斥的區別
當有多個執行緒的時候，經常需要去同步這些執行緒以訪問同一個資料或資源。例如，假設有一個程式，其中一個執行緒用於把檔案讀到記憶體，而另一個執行緒用於統計檔案中的字元數。當然，在把整個檔案調入記憶體之前，統計它的計數是沒有意義的。但是，由於每個操作都有自己的執行緒，作業系統會把兩個執行緒當作是互不相干的任務分別執行，這樣就可能在沒有把整個檔案裝入記憶體時統計字數。為解決此問題，你必須使兩個執行緒同步工作。
- 同步 (Synchronization)，兩個行程用同一段記憶體的情況。
- 互斥 (Mutex)，
5. Dead Lock
作業系統的死鎖 (Dead Lock) 是什麼？
死鎖就是兩個執行緒在獲取資源的時候，兩個執行緒互相具有對方所必須的資源，沒有外力的作用將一直持續等待，即為死鎖。
死鎖產生的必要條件有幾種？
- 互斥條件：程式對程式的資源採用排他的機制，也就是一段時間內某一資源僅僅為一個程式所佔有。
- 請求和保持的條件：當程式因為請求資源堵塞時，程式對所獲得的資源保持不放
- 不剝奪的條件：程式已獲得的資源在未使用完之前，不能剝奪，只能在使用完時由自己釋放。
- 環路等待條件：在發生死鎖時，必然存在一個程式–資源的環形鏈。
解決死鎖的方法？
根據死鎖產生的條件，解決死鎖包括預防死鎖，避免死鎖，檢測死鎖，解除死鎖。
如何預防死鎖？
預防死鎖，由於死鎖產生需要同時具備四個條件，因此預防死鎖的辦法就是限制其中的一個條件
（1）破壞請求條件：一次性分配所有資源，這樣就不會再有請求了；
（2）破壞請保持條件：只要有一個資源得不到分配，也不給這個程式分配其他的資源：
（3） 破壞環路等待條件：系統給每類資源賦予一個編號，每一個程式按編號遞增的順序請求資源，釋放則相反。
（4）破壞不可剝奪條件：當某程式獲得了部分資源，但得不到其它資源，則釋放已佔有的資源；
6. Memory Management
7. Virtual Memory
虛擬記憶體
虛擬記憶體是作業系統提供的⼀種機制，將不同程序的虛擬地址和不同記憶體的實體地址對映起來。
每個程序都有自己獨立的地址空間，再由作業系統對映到到實際的實體記憶體。
於是，這⾥就引出了兩種地址的概念：
程式所使⽤的記憶體地址叫做虛擬記憶體地址（Virtual Memory Address）
實際存在硬體⾥⾯的空間地址叫實體記憶體地址（Physical Memory Address）。
記憶體分段 (segment)
分段機制下的虛擬地址由兩部分組成，段號和段內偏移量。
虛擬地址和實體地址通過段表對映，段表主要包括段號、段的界限。
我們來看一個對映，虛擬地址：段3、段偏移量500 ––> 段基地址7000+段偏移量500 ––> 實體地址：7500。
記憶體分頁
分頁是把整個虛擬和實體記憶體空間切成⼀段段固定尺⼨的⼤⼩。這樣⼀個連續並且尺⼨固定的記憶體空間，我們叫頁（Page）。在 Linux 下，每⼀頁的⼤⼩為 4KB。
訪問分頁系統中記憶體資料需要兩次的記憶體訪問 ：一次是從記憶體中訪問頁表，從中找到指定的物理頁號，加上頁內偏移得到實際實體地址，第二次就是根據第一次得到的實體地址訪問記憶體取出資料。
多級頁表
作業系統可能會有非常多程序，如果只是使用簡單分頁，可能導致的後果就是頁表變得非常龐大。
所以，引入了多級頁表的解決方案。
所謂的多級頁表，就是把我們原來的單級頁表再次分頁，這裡利用了區域性性原理，除了頂級頁表，其它級別的頁表一來可以在需要的時候才被建立，二來記憶體緊張的時候還可以被置換到磁碟中。
頁面置換演算法
在分頁系統裡，一個虛擬的頁面可能在主存裡，也可能在磁碟中，如果CPU發現虛擬地址對應的物理頁不在主存裡，就會產生一個缺頁中斷，然後從磁碟中把該頁調入主存中。
如果記憶體裡沒有空間，就需要從主存裡選擇一個頁面來置換。
常見的頁面置換演算法：
