# Chap. 01 - Introduction

> 課程內容參考 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
>

**Note:** [#polling](#Q-請解釋何謂輪詢polling？) [#interrupt](#Q-簡單說明-interrupt-的機制與用意) [#ISR](#Q-何謂中斷服務程式ISR與中斷向量interrupt-vector) [#interrupt vector](#Q-何謂中斷服務程式ISR與中斷向量interrupt-vector)

## Content

* [What is an operating system](#What-is-an-operating-system)
* [1. Computer system](#1-Computer-system)
* [2. Operating system](#2-Operating-system)
* [2.1 Definition of an operating system](#21-Definition-of-an-operating-system)
* [2.2 General-purpose operating system](#22-General-purpose-operating-system)
* [Computer-system organization](#Computer-system-organization)
* [1. Computer-system operation](#1-Computer-system-operation)
* [2. Busy/wait output](#2-Busywait-output)
* [3. Interrupt](#3-Interrupt)
* [3.1 Hardware interrupt](#31-Hardware-interrupt)
* [3.2 Software interrupt](#32-Software-interrupt)
* [3.3 Others](#33-Others)
* [4. Storage device](#4-Storage-device)
* [Hardware protection](#Hardware-protection)
* [1. Dual-mode operation](#1-Dual-mode-operation)
* [2. I/O protection](#2-IO-protection)
* [3. Memory protection](#3-Memory-protection)
* [4. CPU protection](#4-CPU-protection)

## What is an operating system

### 1. Computer system

電腦系統可以粗略分為 4 個元素: (1) **硬體**(hardware) (2) **作業系統**(OS) (3) **應用程式**(application) (4) **使用者**(user)

* User: 使用者的定義非常廣泛，可以是人、機器或甚至其他電腦
* Application: 使用系統資源(system resource)來解決計算問題(computing problem)的方法或程式
* Operating system: 用來**控制(control)與協調(coordinate)硬體資源**的使用
* Hardware: 提供基本的計算資源(computing resource)，像是 CPU、memory 或 I/O 設備

> [!Note]
Hardware 在 OS 中也可以通稱為資源(resource)

<img src="https://hackmd.io/_uploads/rkNr3hbbkx.jpg" width=400>

以上 4 個元素彼此間的關係如上圖所示，user 會使用 application，而 application 是建立在 hardware 上的資源執行，中間的 **OS 則作為 application 與 hardware 之間的==溝通橋樑==**。

### 2. Operating system

作業系統可以被視為永久的軟體，只要一開機就會**常駐於記憶體**之中，主要的目的是用來**控制硬體**，或將**硬體資源抽象化**(abstract)成 API 後提供給 user 與 application，讓 user 能夠使用這些 API 控制資源。

> [!Note]
API = Application Programming Interface

#### 2.1 Definition of an operating system

作業系統的定義可以從三個不同的面向做切入

* Resource allocator: 管理(manage)與分配(allocate)資源，確保有效且公平的執行
* Control program: 控制 user program 的執行與 I/O devices 的運算，預防錯誤以及資源不正當使用
* **Kernel**: 作業系統的別名，是一種常駐在記憶體中隨時都在執行的 program

事實上作業系統並沒有一個很全面的定義，只要知道他的概念以及能夠做些什麼事情即可。

#### 2.2 General-purpose operating system

作業系統執行的過程可以以下圖說明

<img src="https://hackmd.io/_uploads/ryH_LabZ1e.jpg" width=600>

1. Device drivers
* Driver 可以視為部份的 OS
* 每個 device 都有自己的 driver，必須有 driver 才能夠控制對應的 resource。例如每次電腦新插額外裝置(Ex: USB)時，都會先進行驅動程式的安裝
2. OS 會把 device driver 提供的資源抽象化成 API 後打包成 system library
3. library 可以想像成是有很多函式包成的檔案(Ex: C 中的 `<stdio.h>`)
4. Linker 的作用是連接這些 API library 以及編譯(compile)好的 program
* 類似 C 語言執行 `printf` 時需要連接螢幕，所以會呼叫 system library 中的函式使用

## Computer-system organization

### 1. Computer-system operation

電腦系統的運算過程如下圖所示。因為 CPU 與 I/O device 的計算執行速度差異太大，所以兩者之間會多一個 device controller 來做協調。

也因為兩者的執行速度差異太多，所以 Device controller 內部會有一個緩衝區(buffer)，device 進行 I/O 時會先將資料寫入 buffer 中，CPU 再透過 buffer 讀取資料到 memory，反向亦同，CPU 將資料也務 buffer，I/O 再慢慢將資料寫入到 device 中。


### 2. Busy/wait output

> [!Tip] **Interview Ques.**
> ##### Q: 請解釋何謂輪詢(polling)？
> CPU 會不斷測試等待週邊裝置是否準備好，通常會用一個 `while` 迴圈做 polling。

**早期**的電腦架構在進行 I/O device 的運算時，採用的是 ==**busy waiting**== 的方法。在這種方法中，CPU 會有一個指令(通常是 `while` 迴圈)**不斷的進行測試等待，==輪詢(polling)== 每一個 I/O device 檢查它是否準備好**。但 CPU 在等待的過程中因為沒有辦法做其他事情，所以是處於一種 **閒置(idle)** 的狀態，造成資源以及時間的浪費。

如以下程式碼片段中要進行資料的寫入，一次只寫入一個字元，內層的 `while (peek(OUT_STATUS)!=0)` 就是在不斷的做測試等待 I/O 完成，檢查目前的字元寫入完成沒，寫好了就會換下一個字元繼續進行。

#define OUT_CHAR 0x1000   // device data register
#define OUT_STATUS 0x1001 // device status register

current_char = mystring;
while (*current_char != "WO"){
    poke(OUT_CHAR, *current_char);
    while (peek(OUT_STATUS) != 0); // busy waiting
    current_char++;
}

### 3. Interrupt

> [!Tip] **Interview Ques.**
>
> ##### Q: 簡單說明 interrupt 的機制與用意
> Interrupt 是一種由 I/O 裝置或其他硬體發出的**訊號**，用來**通知** CPU 某個事件發生，要求它**暫停目前正在執行的程序**，轉去**執行對應的中斷服務程序**(ISR)。當 ISR 結束後，CPU 能**回到原本的執行點繼續**執行。這種設計讓 CPU 不需要持續等待或檢測 I/O 裝置的完成，**提高 CPU 的使用效率**。
>
> (補充：請說明 polling 與 interrupt 的差別與使用時機？)
>

如同上面所說，因為 busy waiting 的操作方式**效率低下**，在測試 device 完成期間 CPU 無法進行其他工作，所以現代電腦的 I/O device 操作都是使用 **interrupt** 的方式進行。

所謂的 **interrupt** 指的是 ==**允許 device 能夠改變 CPU 執行指令的順序**==，強迫 CPU 轉做其他的指令。如下圖所示。


1. 一開始 CPU 在執行其他的程式，I/O device 處於閒置(idle)狀態
* 當 I/O 發出 request 後就開始運作與 data transfer(傳輸到 buffer)
2. I/O device 的 data transfer 結束(Ex: buffer 滿)
3. I/O 完成任務後會發出一個 interrupt **打斷** CPU 目前正在處理的事情，並**優先處理 I/O 的結果**

透過 interrupt 的機制來完成 I/O 切換工作的 OS 又稱為 **interrupt-driven I/O**，具體流程圖如下圖所示。

<img src="https://hackmd.io/_uploads/BJZ47rnW1e.png" width=600>

1. 一開始 device driver 初始化 I/O 設備
2. 發出一個指令給 controller 讓他開始搬移資料(同時 CPU 也還在繼續進行動作)
3. I/O 開始搬移資料
4. **完成動作後發出一個 interrupt 給 CPU**
5. CPU 接收 interrupt 後再**視排程或優先性決定要執行哪個程式**
6. 執行完成後恢復原來 CPU 狀態
7. 進行其他 I/O

現代的 OS 基本上都是透過上述的 intrrupt 方式進行，而 interrupt 又可以分為由 **H.W. 產生**或是由 **S.W. 產生**。

* 由 H.W. 產生
* Hardware 藉由發出一個 signal 給 CPU 來引發 interrupt
* 這種藉由 hardware 產生的 interrupt 稱為 ==**signal**==
* 由 S.W. 產生
* Software在**執行時發生錯誤**(Ex: 除以 0)或是**要求作業系統支援**(system call)
* 這種由 software 產生的 interrupt 稱為 **==trap==**

> [!Note]
> Software 泛指 user 的程式。兩種 interrupt 的差別在於:
>
> * Signal 是發出 interrupt **讓 CPU 處理 I/O 完成的資料**
> * Trap 是發出 interrupt 來**將控制權切換到 OS 中**，讓 OS 介入操作。

#### 3.1 Hardware interrupt

Hardware 的 interrupt 發生過程如下圖所示。

<img src="https://hackmd.io/_uploads/r1TtwS2-kx.png" width=600>

1. 當某個 device 發生 interrupt 時，會發出一個 signal 給 CPU
2. 此時 CPU 執行的指令會**被中斷**並**跳轉到** **ISR** 所在的記憶體位址(通常是固定的)開始執行
3. 執行完後會**回到 interrupt 前的指令**繼續執行

> [!Note]
> * 中斷服務程序(**I**nterrupe **S**ervice **R**outine, ISR)
> * 是當 H.W. 發出 interrupt 時 **CPU 要跳去執行的一段特定程式碼**(類似函式概念)
> * 中斷向量(Interrupt Vector)
> * 因為 interrupt 發生時必須**把 CPU 的控制權轉移執行 ISR**
> * 考慮到 interrupt 會**頻繁發生**且必須**迅速處理**，因此**會用一個表格(或陣列)來==儲存不同裝置的 ISR 的指標==**
> * 通常是該段程式碼的**起始位址**
> * 每當發生 interrupt 時 **ISR 會透過這個表格/陣列被間接呼叫**
> * 這個表格/陣列被稱為**中斷向量(interrupt vector)**

> [!Note]
> * 裝置控制器(controller)
> * 電腦周邊硬體設備的晶片，與實體裝置連接且內建暫存器
> * 功能:
> * 直接控制 I/0 設備
> * 根據驅動程式的指令執行操作
> * 發出 interrupt
> * 驅動程式(driver)
> * 執行在 OS 內核的軟體程式，為 OS 提供**與硬體互動的抽象介面**
> * 功能:
> * 將系統層級的操作(Ex. read/write)轉為 H.W. 可理解的型式
> * 設定 controller 的暫存器
> * OS 與 controller 間的**橋樑**

<!-- :::info
**補充**
1. 安裝 device driver 的時候，將 device 插到主機板(MB) 上的哪個 port，就會把 driver 放到特定的位址，無法改變
2. interrupt vector 其實就是一個用來儲存 function pointer 的 array，或是也可以看成一個表格，裡面儲存了各種處理 interrupt 的對應程式的入口位址，當發生特定 device 的 interrupt 時會進入到這裡找到能夠處理這個 interrupt 的程式的位址。
3. 當 CPU 接收到 interrupt 並從 interrupt vector 找到對應的處理程序位址後，就會跳到這些位址執行。這些能夠處理對應 interrupt 的處理程序又稱為 interrupt service routine 或 interrupt handler
4. 發生 interrupt 時會紀錄當下的 program 資訊，以便處理完後再做恢復
::: -->

#### 3.2 Software interrupt

與 hardware interrupt 類似，當 user program 執行到某個**需要 OS 服務的操作**時會觸發 trap，是由 user 主動**使用 system call 引起**的。

<img src="https://hackmd.io/_uploads/Sy4haH2-ke.png" width=500>

> [!Tip] **Interview Ques.**
> ##### Q: 何謂中斷服務程式(ISR)與中斷向量(interrupt vector)
> ISR 是當中斷發生的時候，負責處理該事件發生的一段特殊函式。ISR 執行結束會 CPU 會再恢復到原本位址繼續執行指令。
> 中斷向量是一塊固定的記憶體位址，裡面儲存了 ISR 的位址，每個 ISR 對應一種中斷事件，CPU 會透過中斷向量查找 ISR 的位址去執行。

#### 3.3 Others

* Interrupt 必須儲存發出 interrupt 的 program 的 address，才能再處理完 interrupt 後返回原來的 program
* 當有很多個 interrupt 接續而來時，會直接忽略後面的 interrupt，直到前面的處理完才會處理後面的 interrupt。例如某些時候滑鼠會卡住不能動，因為前面其他的 I/O interrupt 還沒處理完

### 4. Storage device

<img src="https://hackmd.io/_uploads/SkFuGIhZJl.png" width=550>

儲存設備是由階層式的設計構成，一般會注意三件事

* 速度(speed)
* 成本(cost)
* 揮發性(volatility)
* 揮發性: 斷電後資料會消失
* 非揮發性: 斷電後資料不會消失

在上圖的階層式設計中，**main memory 是 CPU 唯一可以==直接做存取==的儲存設備**，是透過**記憶體控制器進行**，main memory 以下的設備都必須透過 I/O 來進行存取。

Main memory 通常是採用隨機存取記憶體(**R**andom **A**ccess **M**emory, RAM)，指的是**不論在哪個位址存取的速度都一樣**。RAM 依照功能不同又可以分為兩種類型

* DRAM
* 電力需求較少，速度較慢
* 用於 main memory
* SRAM
* 電力需求較多，速度較快
* 用於 cache

:::info
在 cache 中，資料暫時從較慢的 main memory 複製到較快的地方使用。只有進行資料的複製，而不是資料的搬移。
:::

## Hardware protection

這邊所指的 protetion 是針對硬體設備的保護，而不是軟體層面的資安問題。用意是在 multi-programming 下，不影響其他 programming 的使用。

### 1. Dual-mode operation

在多工模式下為了保護系統資源，所以區分成兩種模式

* User mode
* 指的是 user 所發出的 instruction
* Kernel mode
* 由 OS 所發出的 instruction
* 通常是 user 透過 system call 要 OS 執行的 instruction

為了因應兩種模式的切換，hardware 會使用一個 bit 來區分當前模式(mode bit)，只要 interrupt 發生，就會立即切換 kernel mode，處理完後再回到 user mode。


在 kernel mode 中有一種被稱為 privileged instruction 的指令。這是一種具有某些特權的 instruction，通常是指會危害到電腦運作的 instruciton。這些指令只能在 kernel mode 中執行，如果 user 想要使用的話只能透過 system call 來執行(Ex: `printf`)

> [!Note]
> 各種 multi- 概念
> * 多處理器(multi-processor)系統
> * 每個處理器都有: 單一顆 CPU 核心(core) + 暫存器(register) + 快取(cache)
> * 多核心(multi-core)系統
> * 單一處理器(processor)中有多個 CPU 核心(core)，每個核心有自己的暫存器與快取
> * 核心(core)是 CPU 的基本計算單位
>
>
>
> * 多工(multi-programming)模式
> * 記憶體中**同時放置多個正在執行中的 program**
> * 當某個 program 切換到 I/O 計算時 CPU 可以執行其他的 program 而**不會閒置**
> * 正在執行的 program 又稱為 **process**
> * 多任務(multi-tasking)模式
> * 建構在 multi-programming 的基礎之上
> * 作業系統每過一段間會**主動打斷** CPU 正在執行中的程式，**強迫它切換**到其他程式執行，讓使用者感受到跟電腦間的**互動(interaction)**
> * 需要依靠 **time-sharing** 的技術才能做定時切換
> * 與 multi-prgramming 的差別: **不論有沒有 I/O 的介入，都會因為 time-sharing 的原因切換執行中的程式**

### 2. I/O protection

與 I/O 相關的 instruction 都是 privileged inst.

<img src="https://hackmd.io/_uploads/BJaXKLnZkx.png" width=400>
![未命名]()

### 3. Memory protection

確保資料的存取(access)或覆寫(over-write)不會影響到其他的 program。由硬體支援上會設計兩個特殊的 register。

* Base regiser : 儲存最小的 physical memory address
* Limit register: 儲存範圍的大小

執行程式時會檢查這兩個 register，如果 instruction 超過這個 address 表示無效，如下圖所示。

<img src="https://hackmd.io/_uploads/rkNVcLnWkl.png" width=400>

:::info
有一個 privileged instruction 可以更改這個兩個 register 所儲存的數值，例如 C 語言中的 `malloc()` 函式就可以透過 system call 來做更改。
:::

### 4. CPU protection

CPU protection 的目的是阻止某個 program(包含 OS)過度霸佔 CPU 的資源，簡單來說就是 time-sharing 的設計概念。

硬體支援的設計上會有一個 timer，當某個 program 過度使用 CPU 時，timer 會發出一個 interrupt 中止該 program 繼續使用 CPU。