作業系統
===

## What does os do
1.management (管理)
2.allocation (分配)
3.control (控制)
4.service (服務)

## cluster architecture/叢集式架構
高可用性、容錯、（非）對稱架構

## multiprogramming/多段程序
多道程序設計透過組織程序，使CPU始終有一個程序在執行，從而提高了CPU的使用率。
- 正在執行的程式稱為進程。
- 作業系統同時保持多個進程在記憶體中。
- 當正在執行的一個進程需要等待時，作業系統會切換到並執行另一個進程。這種切換使得多個進程能夠並行執行，提高了系統的效率和響應性。

## multitasking/多工處理
- 多工處理是多道程式設計的邏輯擴展。
- CPU透過在多個進程之間切換來執行多個進程，但切換發生得非常頻繁，以為用戶提供快速的回應時間。
- 分時作業系統使用CPU調度和多道程式設計，為每個使用者提供共享電腦的一小部分時間。
## time-sharing/分時處理
- 分時是將時間分割成間隔或時間片的技術，然後限制一個作業一次只能執行一個時間片。
- 在每個時間片結束時，當前作業被暫時擱置，允許另一個作業在下一個時間片內執行。
- 透過以這種方式快速切換作業，可以建立多個作業同時執行的假象。

## 關於作業系統的運作原理
- 現代的作業系統是中斷驅動的，也就是說，它們會根據外部或內部的事件來執行相應的動作。
- 事件通常是由中斷或陷阱所觸發的，中斷是由硬體訊號引起的，陷阱是由軟體指令產生的。
- 中斷或陷阱發生時，硬體會切換到核心模式，並執行作業系統的代碼，稱為中斷服務程序或異常處理程序。
- 陷阱可以分為兩種，一種是由錯誤造成的，例如除以零或無效的記憶體存取，另一種是由使用者程式有意發出的，請求作業系統提供某種服務，稱為系統呼叫。

## 5個os作用時機
1 system boost
2 io interrupt
3 timer interrupt
4 exception occurs
5 system call occurs

## 雙模和多模操作
- 區分作業系統程式碼的執行和使用者定義的程式碼的執行,以保護系統和資源不被濫用或破壞。
- 雙模式運作需要電腦硬體提供一個模式位元(mode bit)來指示目前的模式是使用者模式(user mode)還是核心模式(kernel mode)。
- 大多數電腦系統提供硬體支持，至少能夠區分兩種操作模式：
- 使用者模式/user mode（1）
- 代表使用者執行
- 核心模式/kernal mode（0）
- 代表作業系統執行
- 也稱為監管模式、系統模式或特權模式

## Two fundamental models of interprocess communication:
- ### Shared memory
- 提供了最大的速度和便利性，因為在電腦內部進行記憶體傳輸時可以以記憶體傳輸速度進行通訊。
- 需要進行保護和同步。

- ### Message passing
- 用于交换少量数据非常有用，因为==不需要避免冲突==。
- 对于跨计算机通信来说，比共享内存更容易实现。

## monolithic 的優化方式
- ### Layer approach
- 主要優點：建置和調試的簡單性
- 透過模組化，層次被選擇，以便每一層僅使用較低層次的功能（操作）和服務。
- 簡化調試和系統驗證
- 簡化系統的設計和實施。
- 主要困難：需要仔細的規劃！
- 需要適當定義每個層次的功能，因為每個層次只能使用較低層次的功能。
- 效率較低（較多層次，較多開銷，效能較慢）
- 每個層次都會為系統呼叫增加開銷，最終導致系統呼叫耗時較長，而非分層系統上的系統呼叫則較快。
- 正在設計更少層次但具有更多功能的系統，提供模組化程式碼的大部分優點，同時避免了層次定義和互動的問題。

- ### Microkernels
- 優點：
- 更容易擴展微內核
- 更容易將作業系統移植到新的架構
- 提供更多的安全性和可靠性（大多數服務作為用戶進程運行，而不是核心進程）
- 缺點:
- 微核心可能會受到效能下降的影響，這是由於系統功能的增加引入了額外的開銷。
- 用戶空間到核心空間的通訊帶來效能開銷。

- ### Solaris 可加載模組(LKM)
- 優點：
- 模組可以單獨編譯。
- 模組可以在運行時載入到內核，而無需重新啟動電腦。
- 模組可以隨時卸載，因此不會對核心大小產生永久性影響。

## 隨著 ==進程(process)== 的執行，它會改變狀態：
- 新（New）：進程正在被創建。
- 運行中（Running）：指令正在執行。
- 等待中（Waiting）：進程正在等待某個事件發生（例如I/O完成或接收到訊號）。
- 就緒（Ready）：進程正在等待分配給處理器。
- 終止（Terminated）：進程已經執行完畢。

## context switching

## 多執行緒程式設計的好處包括：
- **回應性**：多執行緒化的互動式應用程式可能會在部分被阻塞或正在執行長時間操作的情況下繼續運行，從而增加對使用者的回應速度。
- **資源共享**：執行緒共享它們所屬進程的記憶體和資源。
- **經濟性**：創建和上下文切換線程更經濟。
- **可擴展性**：可以利用多處理器架構，其中執行緒可以並行運行。

## 在多核心系統中進行程式設計的挑戰包括：
- **活動劃分**：劃分可以並行運行的任務。
- **平衡**：確保任務執行相等的工作量。
- **資料分割**：存取任務的資料必須分割以在不同的核心上運行。
- **資料依賴**：確保任務的執行被同步以滿足資料依賴性。
- **測試和調試**。

## Types of Parallelism
- **資料並行性**（Data parallelism）是將相同資料的子集分佈在多個計算核心上，並在每個核心上執行相同的操作。例如，在雙核心系統上，兩個執行緒可以並行地對陣列[N]進行求和。線程A在核心0上對數組[0]..[N/2-1]求和，線程B在核心1上對數組[N/2]..[N-1]求和。
- **任務並行性**（Task parallelism）是將任務（執行緒）分佈到多個運算核心上，每個執行緒執行獨特的操作。例如，執行緒A執行求和操作，而執行緒B執行乘法操作。又如，生產者執行緒和消費者執行緒執行不同的任務。

## Relationship between user threads and kernel threads
- **Many-to-one**
- 執行緒管理由使用者空間中的執行緒庫完成，因此效率較高。
- ==如果一個執行緒進行了阻塞系統調用，整個程序將被阻塞==。
- 這是因為==一次只有一個執行緒可以存取核心==。
- ==多個執行緒無法在多核心系統上並行運行==。
- ==無法利用多個處理核心==。
- ==目前很少系統使用這種模型==。
- 例如：Green threads - 用於Solaris系統的線程庫。

- **One-to-one**
- 與多對一模型相比，這種模型提供了更多的並發性，因為當一個執行緒進行阻塞系統呼叫時，允許另一個執行緒運行。
- ==允許多個執行緒在多處理器上並行運行==。
- 創建用戶線程需要創建相應的核心線程，==大量的核心線程可能會降低系統效能==。
- 範例包括Linux和Windows作業系統系列。

- **Many-to-many**
- 這些是不同的線程模型，用於管理使用者級線程和核心級線程的關係：
- **多對一模型（Many-to-One Model）**：
允許開發人員創建任意數量的使用者線程，但不會實現並行性，因為==核心一次只能調度一個核心線程==。
- **一對一模型（One-to-One Model）**：
允許更大的並發性，但開發人員需要小心，不要在應用程式中建立過多的執行緒。
當一個執行緒執行阻塞系統呼叫時，核心可以安排另一個執行緒進行執行。
- **多對多模型（Many-to-Many Model）**：
開發人員可以建立任意數量的使用者線程，對應的核心線程可以在多處理器上並行運行。
當一個執行緒執行阻塞系統呼叫時，核心可以安排另一個執行緒進行執行。

- **Two-level**
這是==多對多(Many-to-many)模型的變體==：
- 仍然將許多用戶級執行緒復用到較少或等量的核心級執行緒上。
- 也允許將使用者級線程綁定到核心級線程。
- 看起來是最靈活的模型，但==實現起來較為困難==。
- 隨著處理核心數量的增加，限制內核執行緒數量變得不那麼重要。
- ==大多數作業系統現在使用一對一模型==。

## 線程庫為程式設計師提供了用於建立和管理線程的API。
**實作執行緒庫的兩種主要方法**：
- 在用戶空間提供完全沒有核心支援的函式庫：
- 庫中的所有程式碼和資料結構都存在於使用者空間。
- 調用庫中的函數會導致在用戶空間進行本地函數調用，而不是系統調用。
- 在作業系統直接支援的核心級庫中實作：
- 庫的程式碼和資料結構存在於核心空間。
- 呼叫庫的API中的函數將導致對核心的系統呼叫。

# 期末

## CH5

### 附載平衡(Load Balance)
在多線程情況下OS會平衡每個線程的工作量

**Dispatch latency/調度延遲**:
- 停止目前的進程開啟下一個進程的時間
**Turnaround time/執行時間**：
- 執行特定進程所需的時間。
- 從提交到完成的時間間隔。
**Waiting time/等待時間**：
- 進程在就緒隊列中等待的總時間。

### FCFS(First-Come, First-Served)

### SJF(Shortest-Job-First)
#### 兩種方案：
==**Waiting time = completion time – Arrival time – Execution time**==
- 非抢占式短作业優先（SJF）：
- 一旦CPU分配給一個進程，直到完成其CPU突發，不能被抢占。
- 抢占式短作业優先（SJF）：
- 如果一個新的進程到達，其CPU突發長度小於當前正在執行進程的剩餘時間，則進行抢占。
- 也被稱為最短剩餘時間優先（SRTF）。
- SJF在理論上是最優的：對於給定的一組進程，提供最小的平均等待時間。
- 經常在長期調度中使用。
- 不能在短期調度中實現。
- 如何知道下一個CPU爆發的長度？
- 只能預測長度。
- 通過選擇預測CPU爆發最短的進程，來近似實現SJF調度。

## RR(Round-Robin)
- 特別為分時系統設計。
- 每個進程獲得一小部分的CPU時間（時間量子或時間片），通常為10到100毫秒。
- 當時間量子用完時，進程被抢占。
- 將就緒隊列保持為進程的FIFO隊列：
- 新進程被添加到隊列尾部
- 第一個進程被調度運行
- 如果計時器超時，運行的進程被抢占並添加到尾部。

### Priority(優先級)
- 每個進程都與一個優先級數字（整數）關聯。
- 首先選擇具有最高優先級的進程。
- 具有相等優先級的進程按照FCFS順序調度。
- 優先級可以是內部或外部定義的。
- 外部優先級：重要性，政治因素等。
- 內部優先級：可測量的數量，時間限制等。
- SJF是一種優先級算法，其中：
- 優先級是預測的下一個CPU爆發時間。
- CPU爆發越大，優先級越低。
#### Non-Preemptive Priority Scheduling

#### Priority Scheduling with Round-Robin
==Run the process with the highest priority. Processes with the same priority run round-robin==
==**主要问题是低优先级进程的无限阻塞**==

### Multilevel Queue
将进程分类为不同的组，因为不同的组可能具有不同的调度需求。例如，前台（交互式）进程和后台（批处理）进程。
#### 将就绪队列划分为单独的队列：
- 进程永久分配到一个队列
- 每个队列都有自己的调度算法
- 例如，前台队列使用轮转（RR），后台队列使用先来先服务（FCFS）。
#### 在队列之间进行调度（两种可能的方式）：
- 固定优先级的抢占式调度
- 每个队列都具有绝对优先级，优先级高于低优先级队列。
- 除非所有更高优先级的队列都为空，否则不允许运行任何进程。
- 当新的高优先级进程进入时，会抢占一个进程。
- 存在阻塞的可能性。
- 时间片轮转在队列之间
- 每个队列获得一定比例的CPU时间，可以在其进程之间进行调度。
- 例如，在轮转中80%分配给前台队列，20%分配给后台队列。

### 處理器傾向

### RMS(Rate Monotonic Scheduling)
以週期為優先及(週期短的先執行)
==**Worst Case**==
### EDF(Earliest Deadline First)
優先及(P)高先做遇到下個週期會打斷正在執行的其他項目

## CH7
## 如何預防 Deadlock

<style>
img {
width: 450px;
}
</style>