# Operating System
[toc]
## Ch1 Introduction

### 大綱

- 電腦架構
- OS架構
- OS扮演啥角色
- **系統類型**

### 電腦架構含HW OS App Users

### 核心 Kernel

> The one program running **at all times** on the computer is the kernel, part of the OS.
>

### Operation System

> Everything a vendor ships when you order an operating system
>

### OS扮演的角色

- 對人：(1 ) 方便使用的電腦以及好的效能 (2) 提供讓user program 容易執行的地方
- 對電腦：(1) 資源分配的管理者 (2) 控制監督code的執行

### System Type

| Type | 特點 | 別名 |
| --- | --- | --- |
| Multiprogramming | 同一段時間內可以一次執行很多code、同步方式有concurrent和parallel | in 恐龍，視為batch system |
| Time-sharing | 讓user有互動的感覺(因response time < 1 sec.) | multitasking |
| Multiprocessors | 同一部電腦裡有很多CPUs，但共享memory, I/O devices→共享clock | Parallel system、tightly-coupled system(緊密耦合) |
| Distributed system | 一堆處理器的集合(無共享，透過網路 or buses 連接) | loosely-coupled(鬆散耦合) |
| Real-time system | 主要都是時間為主 | 無 |
| Mobile system | 可攜性、輕量化 | 無 |
| Batch system | 整理非即時性的tasks，在冷門時段處理 | 無 |

- Time-sharing:

> Time-sharing system is a logical extension of multiprogramming.
>

最大差別：CPU switches jobs so frequently, creating an **interactive** computing

- Multiprogramming:

concurrent : 切來切去

parallel : 同時平行處理

- Multiprocessors:

優點：(1) 增加效能 (2) 經濟效益→不用額外memory, I/O devices (3) 增加依賴性→若有cpu掛掉可以互相頂著用

分兩種：(1) Asymmetric Multiprocessors (2) Symmetric Multiprocessor

Asymmetric Multiprocessors : 主僕關係

Symmetric Multiprocessor : 均等關係

要求更快：Multicore sys. : on-chip 溝通比 between-chip快(但CPU數量對於電腦來說一樣)

增加太多CPU遇到瓶頸？Non-Uniform Mem. Access(NUMA)

→把memory切成數等分，各cpu擁有各自的，但所有CPUs共享同一個physical address

優點：不會遇到資源使用上的瓶頸

缺點：會有延遲時間→OS可以改善penalty, via CPU scheduling, memory management

- Distributed :

分三種：

(1) Client-Server : Client post requests, server serve →若server掛了會卡一段時間

(2) peer-to-peer : 每個node都一樣，彼此幫忙

(3) Hybrid

優點：(1) 資源共享→節省成本 (2) 運算可以加速→平行處理 (3) 可靠度

- Real-Time system :

分兩個類型：Hard & Soft real-time sys.

Hard主要對於時間要求較嚴格，e.g.軍事防衛系統、嵌入式即時系統→設計上須盡可能縮小延遲、要特別的CPU排班，市面上無OS可以應用在他身上(客製化)

Soft僅需確保有real-time要求的process須在時間內完成，其餘無限制，e.g. VR、多媒體系統→設計上需支援Preemptive(CH4)且不提供Aging(防止Process餓死)，也須降低kernel dispatch的延遲

降低dispatch latency → 讓kernel 在處理tasks時可以被preemptive，反之要做好同步機制:

- 針對某些時段 kernel 才可以被 preemptive → 增加preemption point
- 讓 kernel 變成 完全可preemptive
- Mobile Computing (handheld sys.) :

行動系統犧牲了

1. 螢幕大小→便攜性
2. 記憶體大小→大小限制
3. 高速的CPU→耗能及散熱不易處理

但比較不在乎 Storage, 因為有雲端幫助(國外題目)

- Batch system :

把非急迫且具週期性的工作排至冷門時段處理，user就不需與其互動以提高工作效率，e.g.盤點庫存

## Ch2 Interrupt、I/O、OS Structure、Virtual Machine

### 大綱

- I/O 運作方式
- 硬體保護機制
- Interrupt種類

### I/O 運作方式

因為 I/O 之運作速度與 CPU clock 差異太大，所以需要方法控制他們

就產生了 I/O subsystem → kernel 中專門管 I/O 的，每個 device 也有專屬的 driver

再由 driver 去控制device controller，進而控制device運作

### Work flow (→為request ←為response)
<pre>
User program ←→ kernel subsystem ←→ device driver ←→device controller ←→ device

User mode | Kernel mode

Software | Hardware
</pre>
### I/O在執行時有三種方式：

- Polling:

a.k.a. Programmed I/O, Busy-waiting I/O，最簡單的溝通方式。

steps:

(1)CPU會不斷讀取busy-bit，直到ready(clear)。

(2)If clear, CPU設定write bit在command register中，且寫入byte data 到data-out reg.

(3)CPU set command-ready bit

(4)Controller 看到command-ready bit時控制器會設定busy-bit

(5)Controller讀取command register 且開始控制I/O執行，運用data-out reg.

(6)Controller 清除command-ready bit 和 busy-bit，當CPU Polling到此signal即得知完成

若Controller and Device 速度較慢→會減低CPU utilization ，故需要後面方式

**大概念：**

**CPU定時發出詢問，去詢問各個device(polling)是否需要服務，服務結束後再詢問其他設備。**

- Interrupt:

為改善 Polling，不要讓CPU乾等device回應，交由controller 告訴CPU I/O設備已完成工作。

steps:

(1)透過 CPU 硬體端新設置的 interrupt-request line 去偵測是否有I/O device controller raise a signal. (IRL連接CPU和device controller)

(2)CPU偵測到後，將會先進行保存當前Process執行狀況且暫停，jump to interrupt-handler routine(fixed address in memory) → Context Switch

(3)interrupt-handler (software)會處理此中斷

→此為Asynchronous Event (不需要定期去輪詢)

其中fixed address in memory為interrupt vector(提供table去儲存各個中斷處理器在哪個位置)

- 中斷種類

(i) 早期分類

(1)External Interrupt: CPU以外的設備

(2)Internal Interrupt: CPU執行程式時發生的重大錯誤

(3)Software Interrupt: 執行中的Process需要OS提供服務時才會發出此類中斷

(ii) 演化後

(1) External Interrupt → Interrupt 硬體

(2) Traps: 包含Internal Interrupt and Software interrupt

(iii) 現在分類

(1) Non-maskable Interrupt: 此中斷發生必須立刻處理

(2) Maskable Interrupt: 可延後或忽視的

- DMA

Direct Memory Access Block-transfer oriented(NOT Byte-transfer, NOT Character transfer)

提供一個裝置控制器，讓I/O做資料傳輸(in memory)時，CPU不用參與

steps:

(1) device driver 告知device controller 需要進行資料傳輸 (e.g. disk to mem.)

(2) device controller 告知DMA controller 傳輸來源的位置 & 資料量 & destination

(3) device controller 指揮device 傳輸資料並透過PCI bus 傳資料給DMA

(4) 資料傳完畢後，才會發出I/O complete 通知 CPU 中斷

### 三種IO優缺點比較

| | Polling | Interrupt | DMA |
| --- | --- | --- | --- |
| 缺點 | 若device 運作時間長，則CPU會耗費CPU time 去不斷polling直到device ready →Interrupt | 若I/O operation time小於interrupt handle time則會浪費時間在處理content switch. | 會增加硬體的複雜程度 |
| | 若怕CPU polling太久則將其切換給其他工作執行則有可能導致資料流失(when device is fast) | CPU仍要監看data transfer →DMA | 因DMA priority 較高，當與CPU有衝突時，CPU會拿不到memory |
| 推演 | 不想浪費CPU time -> interrupt | 若中斷次數過多則也會影響效能→DMA | |
| 優點 | 成本低 不需硬體支持 | 可以讓CPU平行處理其他工作(when I/O operating) | CPU不需參與data transfer過程 |
| | | 若I/O operation time大於interrupt handle time, 使用interrupt 會提高CPU utilization 比起Polling來說 | Highly suitable for Block-transfer oriented device such as disk. |