HackMD
作業系統及考古
中斷機制摘要
中斷的定義與作用
中斷：是一種能夠改變 CPU 執行流程的機制，用於處理外部事件或異常情況。
作用：
- 提高系統效率：允許 CPU 在等待 I/O 操作完成時，可以執行其他任務。
- 處理異常事件：如除零錯誤、記憶體存取錯誤等。
- 實現系統交互：如鍵盤、滑鼠等輸入設備的處理。
中斷的種類
- 硬體中斷（signal）：由硬體設備觸發，如硬碟、網路卡等。
- 軟體中斷（trap）：由軟體觸發，如系統調用、異常情況。
中斷處理流程
- 中斷發生：硬體設備產生訊號或軟體執行系統調用。
- 硬件檢測：CPU 檢測到中斷訊號，暫停當前指令的執行。
- 保存上下文：CPU 將當前的程序計數器、寄存器等狀態保存到堆疊中。
- 查找中斷向量：根據中斷類型，從中斷向量表中找到對應的中斷處理程序的地址。
- 執行中斷處理程序：CPU 跳轉到中斷處理程序的起始地址，執行相應的處理邏輯。
- 恢復上下文：中斷處理程序執行完畢後，恢復被中斷程序的上下文，繼續執行。
中斷向量表
作用：用於保存各種類型中斷對應的中斷處理程序的入口地址。
實現：通常是一個固定大小的陣列，每個元素存儲一個中斷處理程序的地址。
中斷處理程序
作用：處理中斷事件，完成相應的操作。
類型：
- 硬體中斷處理程序：處理硬體設備產生的中斷。
- 軟體中斷處理程序：處理軟體觸發的中斷。
中斷的優先級
作用：決定不同中斷的處理順序。
實現：通過中斷向量表中的優先級位或中斷控制器來實現。
中斷屏蔽
作用：暫時禁止某些中斷的響應，以避免中斷處理程序的嵌套過深。
實現：通過中斷控制器或軟體方式來實現。
中斷與作業系統
作業系統：負責管理系統資源，包括中斷處理。
- 中斷與進程調度：中斷可以觸發進程的切換，實現多任務。
- 中斷與設備驅動程序：設備驅動程序負責處理特定設備的中斷。
關鍵概念
- 中斷向量：指向中斷處理程序入口地址的指針。
- 中斷處理程序：處理中斷事件的程序。
- 中斷向量表：存儲中斷向量的一個表格。
- 中斷服務例程（ISR）：中斷處理程序的別稱。
- 中斷屏蔽：暫時禁止中斷的響應。
總結
中斷機制是現代計算機系統的核心概念之一，它使得計算機能夠高效地處理多種任務，並實現與外部設備的交互。通過了解中斷機制的原理和工作流程，可以更好地理解作業系統的工作方式，以及計算機系統的整體架構。
Process Control Block (PCB) 與 Process Life Cycle
PCB 的重要性
定義
PCB 是作業系統用來管理進程的一種數據結構，包含了進程的各種信息。
作用
- 記錄進程的狀態（New, Ready, Running, Waiting, Terminated）
- 保存進程的上下文信息（程序計數器、寄存器等）
- 管理進程的資源（文件、內存等）
內容
- 狀態
- 程序計數器
- 寄存器
- 內存管理信息
- I/O 狀態
- 賬戶信息
- 其他控制信息
Process 的生命週期
五種狀態
- New：進程被創建
- Ready：進程準備好執行，等待分配 CPU
- Running：進程正在執行
- Waiting：進程等待某個事件（如 I/O 完成）
- Terminated：進程結束
狀態轉換
- New -> Ready：進程初始化完成
- Ready -> Running：調度器選中進程
- Running -> Waiting：進程等待事件
- Waiting -> Ready：事件完成
- Running -> Terminated：進程正常結束或異常終止
Context Switch
定義
將 CPU 從一個進程(process)切換到另一個進程(process)的過程。
過程
- 保存當前進程的狀態到 PCB
- 載入新進程的狀態到 CPU
開銷
- 浪費 CPU 時間
優化
- 減少寄存器數量(但是現在電腦的設計不容易這樣做)
- 硬件支持（多個寄存器組直接做切換，這樣就不需要重新load資料來處理。但是register很貴）
- 優化內存訪問
Process 與 Thread 的區別
Process
- 重量級
- 獨立的內存空間
Thread
- 輕量級
- 共享同一進程的內存空間
考古
1.什麼是os ，解釋:
- 作業系統，可說是硬體與軟體之間”溝通的橋樑”，控制電腦整體運作的軟體
- 1.提供使用者儲存和讀取檔案的路徑、
- 2.提供介面讓使用者能執行程式
- 3.提供程式執行所需的環境。
- 使用者觀點:作為USER和硬體間的介面，提供program可執行的環境。
- 系統觀點:是資源分配者，監控user program的執行。
2.Program, process, thread 的區別
- Program:被動的，儲存於次記憶體中(e.g. disk)
- Process:正在執行中的program(主動)，主要包含code section, data section, program counter,(前三項放在memory space中) cpu register, stack
是os分配資源的對象單位 - Thread:是os分配CPU time的基本單位，又稱為light weighted process。
同一個Task(process)內的Threads共享: code section, data section, os resources
3.解釋multi process, multi thread
- Multi process: 將資源複製且隔離，
優點為:process間不共享記憶體，程式較好寫
缺點為:資源利用較沒效率，所佔memory空間較大 - Multi thread: thread 之間共享資源，
優點為:較有效率，共享資源存取較快
缺點為:共享memory，須注意deadlock跟race condition等問題，且程式碼較難撰寫。
4.Process 間的溝通:
有分為shared memory跟message passing
- Shared memory:
各process透過共享的記憶體(共享變數)的存取，達到溝通、交換資訊的目的。(互斥存取控制由programmer負責，os只負責提供memory space) - Message passing:
三步驟，
1.建立communication link
2.互傳訊息
3.傳輸完畢，release link。
(此法os須提供額外支援)，有直接與間接兩種方式。
5.解釋deadlock，怎麼避免
- 定義:系統中存在一組process互相等待對方所擁有之資源(circular waiting)，造成所有process皆無法執行，cpu utilization跟 throughput大幅下降。
形成deadlock之四個必要條件:
(1)mutual exclusion, (2)hold and wait, (3)no preemption, (4)circular waiting
如何解決:分三種，deadlock prevention, deadlock avoidance, deadlock detection and recovery - (1) deadlock prevention:打破四種條件之其中一個
- (2) deadlock avoidance: process發出對資源的申請時，os會執行銀行家演算法(banker’s Algo.)判斷假設系統核准申請後，是否處於safe state。若是則允許，反之則否決。
- (3) deadlock detection and recovery:偵測死結是否存在，若存在死結，則必須打破死結。
deadlock detection Algo.
偵測所有process，看是否會進入死結
(需要O(n^2m)的time complexity，n:process個數，m:資源種類)
Deadlock recovery:
中止process(分為1.全部中止2.一次中止一個，然後recheck)後進行資源搶奪(挑victim process，恢復到此process無資源之狀態)
6.如何避免race condition
race condition定義:多組process 在shared memory溝通方式下，若未對共享變數提供互斥存取等同步機制，會造成共享變數之最終結果值，因process執行順序不同而產生結果不同，導致不可預期之錯誤發生。
避免方法:
- (1) disable interrupt(鎖住cpu):確保對shared var.存取之相關指令可於執行過程中不被中斷(缺點:只適用於single processor環境)
- (2) critical section design(鎖住共享變數):提供對shared var.之存取動作的互斥控制。
