---
tags: 大三筆記
---

# 海大作業系統(上)

> 內容節錄於：蔡國輝教授的課程。

## 測驗檢討

### ch1

#### 1. 作業系統的歸類

作業系統是**軟體程式**，管控電腦的軟硬體資源。

#### 2. Concurrently 與 simultaneously
* Concurrently：事件剛好同時進行。
* Simultaneously：發生事件的時間有**緊密關聯**。

disk controller與network interface controller-> Simultaneously

電腦同時執行多個應用-> Concurrently

西洋棋車輪戰-> Concurrently

目的：OS需同時管理多個程序及同時運作的硬體。

#### 3. [非同步(Asynchronous)與 同步(Synchronous) 及 interrupt](https://medium.com/@hyWang/%E9%9D%9E%E5%90%8C%E6%AD%A5-asynchronous-%E8%88%87%E5%90%8C%E6%AD%A5-synchronous-%E7%9A%84%E5%B7%AE%E7%95%B0-c7f99b9a298a)
* 非同步(Asynchronous)：接收到需求，不用一直等到需求完成再執行其他需求
* 同步(Synchronous)：必須等待對方完成動作，才能執行其他事情。

差別：發送需求的人是否需要等到需求完成後，才可以執行其他事情。

* **跟CPU無關**　→　Asynchronous：來源是外部。
如鍵盤、I/O、disk、Device Driver。
* **時序與CPU同步**　→　Synchronous：CPU執行的指令與程序。

-> Asyn 會使用interrupt(類似External interrupt)。

Synchronous interrupt分為兩類：
* Processor-detected exceptions：執行普通的指令後，發生異常(overflow、out of range、除以零)引發中斷。
Faults(違規)：違法操作，比如寫入沒有寫入權限的檔案。
Traps(陷阱)：原本在執行的程式，因interrupt被trap到OS中。
* Programmed exceptions：執行特定的指令引發中斷。

[**interrupt**](https://mropengate.blogspot.com/2015/01/operating-system-ch2-os-structures.html)
* #### 過程：
> 發生event → 產生signal → solve
> * Polling
> CPU命令裝置執行 → ==**"CPU等它完成並不斷詢問"**== → 直到收到完成訊號 → CPU處理後續
> * Interrupt
> CPU命令裝置執行 → ==**"CPU去處理其他事情"**== → 設備完成後發出 ==**"中斷"**== → CPU處理後續

* #### 目的：
> 1. 要從一個process到另一個process。
> 2. 跳出無限迴圈。
> 3. 需要反應外界的event(執行ISR)。
> ex. Device需要引起CPU的注意，讓CPU來幫Device做事。

分為External與Internal：
* 外部 External：由CPU周邊(I/O Device)引發
* 內部 Internal：由CPU本身的不合法使用引發(Debug、Divide-by-zero、overflow)

#### 4. 什麼情況下有中斷信號
* 網路線被拔掉(由硬體引發的External interrupt)
* 本身的電腦網卡收到封包(由硬體引發的External interrupt)

#### 5. 一個行程只有20%的時間使用CPU，要讓CPU的使用率達到65%，至少需要載入幾個行程到記憶體
一個行程：$0.8閒置$
兩個行程：$0.8^2閒置$
三個行程：$0.8^3閒置$
n個行程：$0.8^n閒置$
當$0.8^n≤0.35$時，使用率為65%，n即為答案。

#### 6. multi-programming系統
能夠同時執行多個程序的系統
* Passive：透過**事件中斷**，執行多個程序，由OS接受到中斷後切換
* Active：透過**system clock**更換執行的程序，由OS每段時間自主切換。

差別：OS是被動還是主動去切換執行的程序。

<hr>

### ch2

#### 1. User mode 與 Kernel mode
User mode：有限制的模式，避免使用者產生無法回復的錯誤。
Kernel mode：Kernel取得系統的控制權。可以執行特權指令(Privileged Instruction)。

特權指令：I/O instruction、修改Timer、關閉中斷、修改Base/limit register

* 同一個使用者行程，有時會執行使用者程式碼，有時也會執行OS的程式碼。
* 使用者行程執行的時候，不一定都在user mode裡。

user space 與kernel space 是兩塊隔絕的記憶體空間，無法直接引用
透過register、stack、table傳遞

#### 14. 特權指令
Set value of **timer**. Y
Read the clock. Y or N
**Clear memory**. Y or N
Issue a trap instruction. N
**Turn off interrupts**. Y
Modify entries in **device-status** table. Y
Switch from **user to kernel mode**. Y or N
Access **I/O device**. Y

#### 3. 程式設計師，更需要了解API勝過system call。
* System Call : OS專屬， 移植性較差，研究OS必要
* API : 跨越多個OS ， 移植性較高，寫程式必要

#### 4. write data to memory 並非特權指令

記憶體的保護交由MMU(Memory Management Unit, 內存管理單元)

#### 7. 檔案總管也需要透過system call來操作檔案(改名字)。

#### 8. 打開powerpoint使用那些system call
createProcess(), open(), read()

System call分為：
Process Control：fork(), wait()
File Management：open(), read(), write(), close()
Device Management：ioctl()
Information Maintenance：getpid()
Communication：socket()

#### 13. system call 查表
%eax 是 x86_32 的 register
%eax == 0x26h 為第38號的系統呼叫：rename
register需要輸入 %ebx(oldname) 與 %ecx(newname)

int 0x80為中斷常式，對應的是system call。
<hr>

### ch3

#### 1. Context switch

從process A 切換到 B 的過程中
kernel memory保存目前running process的狀態PCB
(行程的狀態、CPU register、stack、記憶體相關資訊、已開檔案。)
並載入下一個Process的PCB。
稱為Context switch

去讀取上一次執行時的狀態。

#### 2. fork()

建立程序的新副本，達到多工處理。
* fork()產生兩個獨立的行程。
* 執行的程式與計數器都一樣。
* 起始值一樣，但變數相互獨立。
* local variable經過fork()後，在父子行程間是相互獨立的。

差別：return value of fork()
* For parent, the return value is child’s PID
* For child, the return value is 0

exit()：讓OS回收程序所使用的資源。
wait()：讓行程等待另一個行程完成才執行，可以避免zombi。

#### 3. 子行程通常會先結束

#### 4. Process的記憶體
包含stack、heap、data、text。
**stack與heap是動態成長**

#### 5. 行程狀態

* running轉變為waiting
I/O：行程等待使用者輸入
Event-Wait：行程發出讀取檔案的要求，行程發出wait()。
* new：將 process 載入記憶體並初始化。
* ready：由於 CPU 的 core 有限，因此 process 在載入之後會先被存放在佇列（ready queue）中等待執行。
* running：程式執行中。
* waiting：程式執行的過程中，會遇到 I／O 需求，此時就會進入等待狀態，等 I／O 需求完成後再回到執行狀態 。
* terminated：程式執行完成，歸還資源。

ready status -> ready queue
waiting status -> device queue

#### 6. OS記錄行程狀態的用途

* 排程(scheduling)時只需考慮ready狀態的行程。
* 可以讓使用者查詢行程狀態

#### 12. importance hierarchy

foreground process, visible process, service process, background process, empty process, 資源緊繃的時候, 由**重要性**來決定從哪一個行程回收資源。

#### 13 zombie and orphan process

zombie被收回的過程

* zombie process
child process結束，沒有人去接住他的回傳值，導致child process還卡在process table(不占用CPU與記憶體)
* orphan process
parent process已經終止，但child process還在執行。(無意：父進程崩潰、有意：長時間的服務進程)

<hr>

### ch4

#### 1. 單核心不具備平行處理parallelism

#### 2. thread

OS中運算的最小單位。

* 一個行程可以有多個thread
* 每個thread各有不同的起點與歷程
* 有自己的執行狀態(running, ready, waiting)
* 有自己私有的儲存(local variables)
* 有自己的context (registers, stack, ...)
* 與同屬相同行程的thread 分享data section(static global variable), 檔案

共用Global variables
共用Process的資源：像Heap memory

#### 3. 兄弟 sibling threads
* sibling threads：同一行程的threads
* 如果是sibling threads，切換thread只需要thread context switch
* 而不同行程的轉換會需要process context switch

#### 4. Virtually all contemporary operating systems support kernel threads.

#### 5. It is possible to create a thread library without any kernel-level support.
透過Thread Libraries提供的API
能夠新增和管理threads。
存在user space 或 kernel-level由OS調用

#### 7. User-Level Thread(ULT)

Kernel 只認得 Process 不知道 Thread
倚靠user space的Thread Libraries
管理threads

優點
* switch 快，無須讓kernel參與
* 任何OS都可，library可以跨平台

缺點
* 一個thread waiting, 整個process waiting
* 同一行程的兩個ULTs，無法被兩個CPU分別執行

<hr>

### ch5

#### 1. Scheduling

* Preemptive：搶先
* FCFS(FIFO)：先進先出
1. 公平
2. No Starvation
3. Non-preemptive

* SJF(Shortest Job First)：不可搶先
1. Average waiting time最小
2. 不公平
3. long-burst-time job可能有starvation
4. Non-preemptive

* SRT(Shortest Remaining Time First)：搶先
1. 更多的context switch
2. 不公平
3. 排班效率更好
4. starvation
5. preemptive

* Round-Robin：輪流執行time quantum=2

* Priority Scheduling
1. 不公平
2. 可以Preemptive or Non-Preemptive
3. Starvation
4. 可與RR結合(同樣priority RR)

#### 3. Preemptive system,哪些事件會觸發CPU scheduler?


**Preemptive**
* Waiting 🡪 Ready
* Running 🡪 Waiting
* New 🡪 Ready
* Running 🡪 Terminated

有程序進入就需比較優先序
所以只要有進入ready或Running離開，皆會觸發scheduler

**Non-Preemptive**
* Running 🡪 Waiting
* Running 🡪 Terminated

只有Running的程序離開時，才會觸發scheduler

* 優缺點
**Preemptive**
優點：有彈性、效率較高、適用於real-time system和time-sharing system。
缺點：context-switch的次數頻繁、容易使priority低的process發生starvation。
**Non-Preemptive**
優點：公平、可預測
缺點：沒有彈性(工作時間短的需要等待時間長的)、較沒有效率

#### 10. Disk scheduler

Disk scheduler使用Disk queue：被挑中的行程可存取disk
Disk scheduler應該優先挑選CPU bound行程：average waiting(for disk)time比較短

<hr>

### ch5

#### 6. virtual machine

#### 7. I/O-burst 與 CPU-burst

有9個CPU bursts，正常情況下，會有 8 個I/O bursts順利執行完畢。
會進入ready queue 9次以上

#### 13. Solaris Scheduling

#### Multilevel Feedback Queues

<hr>

#### 2021 mid

2. open-source operating system
有利：人人都可以維護與監督(更穩定與安全)、更多的衍伸作品(比如基於linux內核的Android、ubuntu、)
免費的資源能讓電腦公司用更低的成本建構伺服器、開發軟體。
讓用戶不需要花錢就能用穩定的系統。

不利：影響商用或是授權軟體的發展
因為開源系統是免費的，會影響到販賣作業系統的公司。

3. RR priority
7. preemptive, non-preemptive

#### 討論區

* 使用者程式(User Program):使用者執行的程式或軟體
* 系統程式(System Program):與作業系統相關，用以控制硬體的程式
* 作業系統(Operating System):負責掌控電腦的資源，是使用者跟硬體之間的橋樑

int main(){   
int i;   
for(i = 0;i < 3; i++) {
     if(fork() == 0) {fork(); fork(); fork()}
  }
 }

9+8x9+8x(9+8x9)=729

## ch1課堂筆記
### [中斷 (Interrupt)](https://cihcih.medium.com/%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-interrupt-d2fced694da5)
* #### 過程：
> 發生event → 產生signal → solve
> * Polling
> CPU命令裝置執行 → ==**"CPU等它完成並不斷詢問"**== → 直到收到完成訊號 → CPU處理後續
> * Interrupt
> CPU命令裝置執行 → ==**"CPU去處理其他事情"**== → 設備完成後發出 ==**"中斷"**== → CPU處理後續

* #### 目的：
> 1. 要從一個process到另一個process。
> 2. 跳出無限迴圈。
> 3. 需要反應外界的event(執行ISR)。
> ex. Device需要引起CPU的注意，讓CPU來幫Device做事。

#### Interrupt根據來源分為兩類：

**1. 跟CPU無關　→　Asynchronous**：如鍵盤、IO、disk、Device Driver。
**2. 跟CPU有關　→　Synchronous**：CPU執行的指令與程序。

* **Synchronous：**
> **1. Processor-detected exceptions**：
> CPU執行的指令與偵測狀況
> * **Faults(違規)**：修正錯誤。
> * **Traps(除錯)**：找出錯誤的地方與程式，跟Debugger有關。
> * if 情況可修正->修正
> else -> 行程會被殺掉
>
> **2. Programmed exceptions**：
> 一個軟體指令，專門處理**System Calls**。

* **ISR(Interrupt Service Routine or Interrupt Handler)**
> 1. 保留會使用的暫存器。
> 2. 中斷處理完成：發出EOI(End of interrupt)command
> 給PIC(programmable interrupt controller)，讓CPU處理這個Interrupt。
> 4. 為Device提供服務。
> 5. 恢復暫存器。
> 6. 發出Iret指令(Interrupt Return) 代表結束->回復原狀。

---

### Computer System


#### Operating System

* 對使用者更友善：順利執行應用程式
* 管理硬體更效率：管理與分配資源

##### **兩種功能：**
> **1. resources allocator**
> 控管所有資源
> **2. control program**
> 管理程序的執行

---

### Computer Startup
Firmware：Bios

---

### Storage Hierarchy

* Caching
* Device Driver

#### **電腦運作模型**


#### DMA

讓CPU可與週邊裝置的工作同時進行
把週邊裝置的協調交給DMA

#### Cycle Sealing

讓DMA能夠完整控制BUS
避免與CPU之間發生衝突

1. 向CPU申請使用BUS
2. CPU核准
3. 取用BUS的所有權

---

### Process management

#### Program Counter：
> 透過OS管理行程的啟用與關閉

---