# 作業系統及考古
中斷機制摘要

### 中斷的定義與作用
**中斷**：是一種能夠改變 CPU 執行流程的機制，用於處理外部事件或異常情況。

**作用**：
- 提高系統效率：允許 CPU 在等待 I/O 操作完成時，可以執行其他任務。
- 處理異常事件：如除零錯誤、記憶體存取錯誤等。
- 實現系統交互：如鍵盤、滑鼠等輸入設備的處理。

### 中斷的種類
- **硬體中斷（signal）**：由硬體設備觸發，如硬碟、網路卡等。
- **軟體中斷（trap）**：由軟體觸發，如系統調用、異常情況。

### 中斷處理流程
1. **中斷發生**：硬體設備產生訊號或軟體執行系統調用。
2. **硬件檢測**：CPU 檢測到中斷訊號，暫停當前指令的執行。
3. **保存上下文**：CPU 將當前的程序計數器、寄存器等狀態保存到堆疊中。
4. **查找中斷向量**：根據中斷類型，從中斷向量表中找到對應的中斷處理程序的地址。
5. **執行中斷處理程序**：CPU 跳轉到中斷處理程序的起始地址，執行相應的處理邏輯。
6. **恢復上下文**：中斷處理程序執行完畢後，恢復被中斷程序的上下文，繼續執行。

### 中斷向量表
**作用**：用於保存各種類型中斷對應的中斷處理程序的入口地址。

**實現**：通常是一個固定大小的陣列，每個元素存儲一個中斷處理程序的地址。

### 中斷處理程序
**作用**：處理中斷事件，完成相應的操作。

**類型**：
- 硬體中斷處理程序：處理硬體設備產生的中斷。
- 軟體中斷處理程序：處理軟體觸發的中斷。

### 中斷的優先級
**作用**：決定不同中斷的處理順序。

**實現**：通過中斷向量表中的優先級位或中斷控制器來實現。

### 中斷屏蔽
**作用**：暫時禁止某些中斷的響應，以避免中斷處理程序的嵌套過深。

**實現**：通過中斷控制器或軟體方式來實現。

### 中斷與作業系統
**作業系統**：負責管理系統資源，包括中斷處理。

- 中斷與進程調度：中斷可以觸發進程的切換，實現多任務。
- 中斷與設備驅動程序：設備驅動程序負責處理特定設備的中斷。

### 關鍵概念
- **中斷向量**：指向中斷處理程序入口地址的指針。
- **中斷處理程序**：處理中斷事件的程序。
- **中斷向量表**：存儲中斷向量的一個表格。
- **中斷服務例程（ISR）**：中斷處理程序的別稱。
- **中斷屏蔽**：暫時禁止中斷的響應。

### 總結
中斷機制是現代計算機系統的核心概念之一，它使得計算機能夠高效地處理多種任務，並實現與外部設備的交互。通過了解中斷機制的原理和工作流程，可以更好地理解作業系統的工作方式，以及計算機系統的整體架構。
## Process Control Block (PCB) 與 Process Life Cycle

## PCB 的重要性

### 定義
PCB 是作業系統用來管理進程的一種數據結構，包含了進程的各種信息。

### 作用
- 記錄進程的狀態（New, Ready, Running, Waiting, Terminated）
- 保存進程的上下文信息（程序計數器、寄存器等）
- 管理進程的資源（文件、內存等）

### 內容
- 狀態
- 程序計數器
- 寄存器
- 內存管理信息
- I/O 狀態
- 賬戶信息
- 其他控制信息

## Process 的生命週期

### 五種狀態
1. **New**：進程被創建
2. **Ready**：進程準備好執行，等待分配 CPU
3. **Running**：進程正在執行
4. **Waiting**：進程等待某個事件（如 I/O 完成）
5. **Terminated**：進程結束

### 狀態轉換
- **New -> Ready**：進程初始化完成
- **Ready -> Running**：調度器選中進程
- **Running -> Waiting**：進程等待事件
- **Waiting -> Ready**：事件完成
- **Running -> Terminated**：進程正常結束或異常終止

## Context Switch

### 定義
將 CPU 從一個進程(process)切換到另一個進程(process)的過程。

### 過程
1. 保存當前進程的狀態到 PCB
2. 載入新進程的狀態到 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.之存取動作的互斥控制。