# 作業系統 Operation Systems(上)

:::info
+ 課程名稱：作業系統 Operation Systems
+ 授課老師：[name=蔡國輝 Kuo-Hui Tsai]
+ 開課學期：1121
:::

[TOC]
***

## Ch1

### OS
* 對使用者
* 便利性、易用性
* 共享電腦要讓所有用戶滿意
* 負責資源管理
* 負責控制程式
* Kernel
* 無時無刻執行的程式
* Bootstrap
* 在電源啟動時跟著啟動
* 儲存在ROM、EPROM
* 所謂的韌體
* 負責運行OS Kernel
* Clustered System
* 多系統連接所組成的
* 與多核心系統差異在於組成
* 多個多核心系統組成Clustered System
### Interrupt
* **信號**的一種
* 接收者為**CPU**
* 發出者為周邊裝置或程式
* 中斷訊號**IRQ (interrupt request)**
* Many sources can generate IRQ
* 每個來源都有獨立的**Interrupt ID**
* 目的在事件發生地當下呼叫CPU處裡
* **強制**切換執行順序
* 會保留原本執行狀態
* CPU會保留中斷前的工作狀態
* Process Control Block(PCB)
* PCB會記錄行程狀態、程式計數器(PC)、CPU暫存器、記憶體管理

#### Interrupt分類
|Hardware Interrupt|Sofeware Interrupt|
|-|-|
|Signal|Trap|
|來自硬體|來自程式|

#### CPU與裝置的互動

|過程|Polling | Interrupt|
|--------|----------|------|
|1|CPU呼叫裝置|CPU呼叫裝置|
|2|CPU持續詢問|CPU做其他事|
|3|裝置完成|裝置完成並發出中斷
|4|後續處理|後續處理|

#### Interrupt Service Routine(ISR)
* 負責處理中斷發生後要做甚麼事
* ISR包括在Driver和OS中

#### Programmable Interrupt Controller(**PIC**)

* 外部設備希望中斷時通知CPU
* 告訴CPU哪個設備發出中斷
* 將IRQ轉為vector
* 對CPU發起中斷
* 等待CPU回應
* PIC會對多個中斷排優先順序
* 可以禁用對CPU或IRQ發起的中斷
* 早期為串聯兩個8259A(IC)組成

#### IRQ分類

|Asynchronous|Synchronous|
|------------|-----------|
|來自I/O設備|來自CPU|
||通常是**異常(exception)**|
||System Call|

異常Exception
[中斷和例外-NTU CSE](https://www.csie.ntu.edu.tw/~wcchen/asm98/asm/proj/b85506061/chap4/overview.html)
* Processor-detected exceptions
* **Fault**：
可糾正，在IP到達前檢測到，糾正後可繼續執行
舉例：
* 對只讀作寫入
* 錯誤的記憶體或硬碟讀取
* 執行特權指令(會動到系統核心的那種)
* **Trap**：
在執行完Trap指令後立刻產生，通常用於測試
* **Abort**：
不可糾正，無法返回原程式繼續執行其他異常
* Programmed exceptions
* **違法的使用者對kernel操作**

#### 中斷發生流程
[參考](https://eve-huang.medium.com/operating-system-%E4%B8%AD%E6%96%B7-eaa9262664cc)

#### 分類樹狀圖
在此感謝我同學廖顯中

### Device-status table
* 包含每個 I/O 裝置的項目，指示其類型、地址和狀態

***

### 學習單

#### P1
作業系統的歸類
\(a\)完全都是軟體
\(b\)包含軟體，硬體，兩者都有
\(c\)完全都是硬體
**Ans：** \(a\)

#### P4

什麼狀況會讓產生中斷信號? 信號的目的地是?
\(a\) 網路線被拔掉
\(b\) 由網路線傳進一個封包, 封包太小, 小於64bytes
\(c\) 由網路線傳進一個封包, 封包大小正常, 但目的MAC是另外一台PC的
\(d\) 由網路線傳進一個封包, 封包大小正常, 目的MAC就是網卡的MAC

**Ans：** A、D
* A. 網路卡會檢測到連接的變化，並產生一個中斷信號來通知系統
* D. 在這種情況下，網路卡會產生一個中斷信號。因為封包的目的MAC地址與網路卡的MAC地址相匹配，所以網路卡需要處理該封包，並通知系統有新的數據到達
#### P5
如果一個行程只有20%的時間使用CPU，要讓CPU的使用率達到65%，至少需要載入幾個行程到記憶體？
|行程數|CPU閒置比率|
|-|-|
|1|$0.8^1 = 0.8$|
|2|$0.8^2 = 0.64$|
|3|$0.8^3 = 0.512$|
|4|$0.8^4 = 0.4096$|
|5|$0.8^5 = 0.32768$|

使用率高於65%, 至少五個行程
> $R為單行程閒置比$
> $P為行程數$
> $(1-R)^P為閒置比$

#### P6
(a)說明什麼是multi-programming系統
**Ans：** 可以讓多個工作可以同一段執行(分成兩種concurrent跟parallel)
* Concuurrent就是多個工作在輪流取得CPU執行
* Parallel是多個工作在同一個時間點取得CPU執行 目的就是提高CPU使用度

(b)說明passive multi-programming與 active multi-programming的差異
* Passive Multi-programming
中斷主要由程序控制並由事件生成
* Active Multi-programming
中斷由CPU控制並由時間生成
* Workstation:屬於type1:類似於os但是只提供virtualization功能
* ESX:屬於type2:執行在user mode的應用程式,專門提供vmm features to gues

#### P7
VMware Workstation 與VMWare ESX 有何區別?
**Ans：**
* **VMware Workstation：** 它需要在一個已經安裝了操作系統的電腦上運行，並且可以在這個電腦上創建和運行多個虛擬機
* **VMware ESX：** 它是一種裸機虛擬化解決方案，它直接安裝在物理服務器上，而不需要一個預先安裝的操作系統，而這使得它能夠更有效地利用硬體資源。

#### P12
(a) Synchronous Interrupts 在定義上與Asynchronous Interrupts有何區別?
* Asynchronous Interrupts
的來源是外部裝置, 產生的時序與CPU無關
* Synchronous Interrupts
則是由CPU執行指令之後產生的, 時序與CPU同步

(b) Synchronous Interrupts 又可以分成哪兩類? 定義上有何區別?
* Processor-detected exceptions
是執行普通的指令後, 由於環境特殊而引發中斷
* Programmed exceptions
是執行特定的指令引發, 引發中斷就是這些指令的目的之一,

***

### 討論區

Q：
在中斷式I/O中，CPU收到interrupt後，
除了查詢interrupt vector，還有找到什麼的位址？
(A)CPU
(B)ISR
(C)device driver
(D)I/O subsystem

A：
CPU收到interrupt後，會根據Interrupt ID 
去查詢Interrupt vector，以取出OS對應ISR的起始位址。
(A) CPU代表中央處理器，並不是在處理中斷時需要找到的位址。
(C) device driver代表設備驅動程式，通常由ISR呼叫以執行特定設備的操作，也不是在處理中斷時需要找到的位址。
(D) I/O subsystem是操作系統的一部分，用於管理I/O操作，也不是在處理中斷時需要找到的位址。

Q：
呼叫副函數或是執行迴國的時候是用jump指令完成的
還是能用interrupt呢 
如果都可以 兩者的利弊是分別是什麼？

A：
在程式中，迴圈和函式較常的是用jump指令來達成的
interrupt: 通常是在發生錯誤,或者接收到某事件要優先處理時才會執行
ex: 除以0, 另值錯誤, 非法函式, Asynchronous Interrupts等...
jump: 是一般語法中for, while, break常見的指令，就是將指向目前指令的指針做移動(加法)，去決定下一個要被執行的指令
總之interrupt比較偏向看有哪個事件比目前執行的指令還要重要，而jump比較偏向看下一個指令要執行哪一個

Q：
(1) explain the difference between hardware and software interrupts

A：
hardware interrupts:
由外部的裝置產生中斷，例如在鍵盤上按下一個按鍵
software interrupts:
由軟體產生中斷，例如違規存取內核或發生除以0

Q：
(2) ISR會執行五個步驟
1.Save all registers used
2.Issue EOI command to PIC
3.Service the device
4.Restore registers
5.Finish with iret instruction
請說明1,2,4,5步驟的目的

A：
1.Save all registers used:
將使用到的暫存器全部存起來
2.Issue EOI command to PIC:
告訴PIC ISR已經受理interrupt
3.Service the device
4.Restore registers:
將暫存器再存回去原本軟體存資料的地方
5.Finish with iret instruction:
回到被interrupt之前的行程

Q：
不可遮罩中斷(nonmaskable)與可遮罩中斷(maskable)的差別是什麼?

A：
不可遮罩中斷：
不可修正的記憶體錯誤之類的事件保留
EX:電源被關掉、硬體或記憶體錯誤、時鐘中斷(這是一個由硬體時鐘以固定頻率（例如50Hz）發出的中斷)
可遮罩中斷：
當關鍵指令執行前必須禁止中斷的執行，可藉由CPU關閉
EX:印表機發起的中斷、滑鼠或鍵盤中斷

Q：
1. 行程中斷的優缺點

A：
優點:
提高效率:當系統程式，將注意力放在某個事發生時，無法將資源分配到其他程式。中斷可以有效解決此問題。
反映敏捷:當電腦察覺這段程式沒有必要執行，或是有安全風險時，可立即使用中斷跳出。
系統流暢:當系統察覺硬體故障時，可立即使用中斷處理較緊急的任務。
紀錄:每次呼叫中斷時，便會被系統紀錄，方便系統統計並改善。

缺點:
互相影響:當程式非可重入，原程式與中斷後執行的程式一偶機率造成干擾。
競爭:當兩個中斷發生時，可能會影發競爭，造成系統執行出現故障。
資源浪費:當中斷發生時，要記錄原程式發生中斷的位置，
要決定優先權，又要從記憶體區，提取並解碼中斷處理程式，最後還要記錄這次中斷的發生。非常浪費運算資源。

Q：
2. 如果多核心要如何處理

A：
在多核心處理器中每個核心，都有自己的中斷控制器，負責彙總外部接收到的訊號，傳送給cpu。為了避免核心間產生競爭或是衝突，多核處理器採用中斷親和性(Interrupt Affinity)來分配哪個中斷要給哪個核心做處理。藉由修改中斷親和性，把特定的中斷，綁訂定到適合處理此類問題的核心來提高系統效率。

Q：
說明以下名詞：disk drive, disk driver, disk controller, user application, system call, 
可否都放在同一張圖?

A：
Disk Drive: 磁碟機，一種硬體裝置，包含了磁碟片及一或多個磁頭，其磁頭可用於讀取和寫入磁碟片上的資料。

Disk Driver: 磁碟機的驅動程式，可以讓作業系統和磁碟機的控制器溝通。

Disk Controller: 磁碟機的控制器，可以解析並執行驅動程式的命令，例如：讀取、寫入。

User Application: 我們平常會使用到的各種應用程式，例如：文書處理程式、編譯器、網頁瀏覽器。

System Call: 系統呼叫，提供一個由作業系統服務的介面，一般是用C或C++寫成的函數。

在圖中，當使用者應用程式需要讀取磁碟上的資料時，會先透過系統呼叫，請求作業系統的服務，接著磁碟驅動程式會載入正確的內容到磁碟控制器的暫存器中，並在磁碟控制器解析並執行讀取的命令後，把資料從磁碟讀取出來，最後再將資料傳遞回應用程式。


## Ch2

### Dual Mode Operation

#### Batch vs Multiprogramming
* Batch
只有一個程式在同時執行
* Multiprogramming
不同程式在同時執行
* 會產生Protection Issue

#### Protection Issue
* I/O Protection
* 防止使用者執行非法I/O操作
* 中止其他Process的I/O
一個Process不應該能終止其他Procss的I/O操作
* 查看其他Process的I/O
一個Process不應該能存取其他Procsee從磁碟讀取/寫入的資料
* 為特定的Procsee I/O提供優先權
* Memory Protection
* 防止使用者修改Kernel code和data srtucture
* 阻止使用者訪問其他人的記憶體

* CPU Protection
* 防止使用者長時間占用CPU

#### 雙層模式(Dual Mode)
* User Mode
* 常規操作
常規操作：Jump、運算、記憶體存取(要檢查)
* 允許User-memory
* Kernel Mode
* 常規/特殊操作
特殊操作：Mapping、TLB、設備暫存器、IO Channel、Change Mode Bit(改變CPU模式)
* 允許User-memory和Kernel-memory
* CPU只能處於一種模式
||User Mode|Kernel Mode|
|-|-|-|
|信任|不可信|可信|
|功能|有限|完整|

#### 作業系統設計
* 分離政策
* Policy：要採取甚麼措施
* Mechanism：怎麼做
* 分類
* 單一結構(**Simple structure**)
* Tightly coupled(緊密耦合)
對系統某一部分修改就對其他功能產生廣泛影響
* 將內核所有功能塞在單個空間執行的二進制檔
* 通信速度快
* EX：傳統UNIX
* 分層結構(**Layered Approach**)
* loosely coupled(鬆散耦合)
系統分為特定且有限功能的小元件
* 使用分層方式
第0層為硬體、最高層為使用者
* 微核心(**Microkernel** System Structure)
* 將不同的**功能**拆成不同的**微核心**
* 各個微核心可以使用**Message passing**溝通
* 因為**Message passing**所以效能較低
* EX：Darwin(iOS, MacOS)
* 模組(Modules)
* 可載入核心模組**loadable kernel modules**
* 物件導向化
* 核心元件互相獨立
核心元件透過已知介面傳輸
* 物間根據需要在內核中載入其他元件
* EX：現行作業系統

### System Calls
* Kernel與User app的溝通介面
* 請求作業系統以允許使用者等待 I/O 完成
* 種類
* Process control
* create process, terminate process
* end, abort
* load, execute
* get process attributes, set process attributes
* wait for time
* wait event, signal event
* allocate and free memory
* Dump memory if error
* **Debugger** for determining **bugs, single step** execution
* **Locks** for managing access to shared data between processes
* File management
* create file, delete file
* open, close file
* read, write, reposition
* get and set file attributes
* Device management
* request device, release device
* read, write, reposition
* get device attributes, set device attributes
* logically attach or detach devices
* Information maintenance
* get time or date, set time or date
* get system data, set system data
* get and set process, file, or device attributes
* Communications
* create, delete communication connection
* send, receive messages if **message passing model** to **host name** or **process name**
* From client to server
* **Shared-memory model** create and gain access to memory regions
* transfer status information
* attach and detach remote devices
* Protection
* Control access to resources
* Get and set permissions
* Allow and deny user access

#### System Call vs API
| System Call|API |
|--|--|
|OS專屬|跨越多個OS|
|移植性差|移植性高|
|OS研究|一般寫程式|
| Specianl interrupt(int 80h)|C lib, DLL |

#### System Call參數傳遞
* 因為是兩塊區隔的記憶體無法直接引用
* 傳遞方式
* 利用暫存器
快速 量少
* 利用Stack
* 傳遞表格位置，但需要轉換
User Space to Kernel Space

### 學習單

#### P1
(True of False)使用者行程執行的時候一定在user mode。
**Ans：** F；User Process可以透過System Call切到Kernel Call

#### P2
(True of False)同一個使用者行程，有時會執行使用者的程式碼, 有時會執行OS的程式碼。
**Ans：** T

#### P3
(True of False)對於程式設計師而言，瞭解API(相較於System call)比較重要。
**Ans：** T

#### P4
(True of False)write data to memory是特權指令
**Ans：** F；記憶體的保護靠MMU
**Memory Management Unit(MMU)**
* 虛擬位址到實體位址的轉換（即虛擬記憶體管理）
* 記憶體保護
* 中央處理器高速緩衝記憶體的控制

#### P5
(True of False)由programmability的角度來看，command-line interface (相較於GUI)是較佳的選擇
**Ans：** T

#### P6
OS的發展有三個主要的階段, multi-programming, simple batch, time-sharing
\(a\)請依照時間先後排列這三個階段
**Ans：** Simple-batch$\to$multiprogramming$\to$time-sharing$\to$multiprocessing
\(b\)時間較晚的兩個階段, 他們的主要目的是什麼?
**Ans：**
* Time-sharing
為了創造interactive(互動式)的系統$\to$response time非常短(要在短時間服務多個user)
* Multi-programming
為了提高CPU使用率使得CPU idle time減少$\to$增加產能

\(c\)這兩個階段, 要達成主要目的, 面臨的挑戰(困難點)在哪裡?
**Ans：**
* Time sharing
* 多用戶支持
需要有效地管理多個用戶，以確保用戶之間的隔離和安全性。
* Response time low
需要提供低延遲的響應時間，以支持交互式應用程序
* Multi-Programming
* 記憶體管理
需要有效地分配和管理記憶體，以便多個程序可以共享計算機的物理記憶體，而不會相互干擾。
* 資源分配
需要一種高效的Process調度算法，以確保公平分配CPU時間和資源。
#### P7
一般人需要更改檔案名稱的時候都是透過檔案總管。對於這一類的使用者，更改檔案名稱的系統呼叫，其實沒有存在的必要。這樣的講法是否正確？理由？
**Ans：** 不正確，事實上，檔案總管這個程式也要透過前述的系統呼叫才能更改檔案名稱。

#### P8
雙擊桌面的簡報檔, 帶出了powerpoint程式. 請問這樣的過程引發了那些系統呼叫? 請舉出三個
**Ans：** createProcess( ), open( ), read( )

#### P9
實務上，應用程式不直接發出system call，而是透過API(Application Program Interface)，請說出兩個原因
**Ans：**
* 程式可攜性高
* 使得application programmer更容易使用

#### P11
作業系統使用高階程式語言，還是低階程式語言寫作完成？列出此項作法的三個優點，兩個缺點。
* 高階語言
* 優點
* **易於編寫和維護**
高階語言更接近人類語言，因此更容易理解和編寫。
* **可移植性**
高階語言編寫的程式可以在不同的硬體平台上運行，只要有相應的編譯器或直譯器。
* **抽象化**
高階語言提供了更多的抽象化，使開發人員可以專注於解決問題，而不必關心硬體細節。
* 缺點
* **效率較低**
相對於低階語言，高階語言編寫的程式可能效率較低並使用更多記憶體
* **硬體控制能力較差**
由於高階語言的抽象化，它們對硬體的控制能力較差
* 低階語言
* 優點
* **效率高**
低階語言編寫的程式可以直接在處理器上執行，因此執行速度非常快。
* **硬體控制能力強**
低階語言允許開發人員直接控制硬體，這在需要精確控制硬體的情況下（如作業系統開發）非常有用
* 缺點
* **編寫困難**
由於低階語言更接近機器語言，因此它們通常較難理解和編寫
* **可移植性差**
低階語言編寫的程式通常是與特定硬體平台緊密相關的，因此在其他平台上可能無法運行

#### P12
作業系統都不採用layered approach來實作，主要原因為何？
**Ans：** 因為要清楚地把layer分開是很困難的,而且如果分成太多layer$\to$Performance會非常低

#### P13
使用x86的組合語言，第一個指令將%eax的值設定為26h，第二個指令執行INT 80h的指令。
(a)請問這兩指令會有何效果？
**Ans：** 更改檔案名稱, rename。80h號的中斷常式,對應的是系統呼叫。接下來執行第38號系統呼叫,對應的就是rename 。
(b)如果要正確執行, 程式要更完整, 還有那些暫存器的數值需要設定? (h代表前面的數字為16進位，請參照LInux System Call Table, x86 (32 bits))
**Ans：** %ebx, %ecx, 分別指向oldname 與newname

#### P14
Windows作業系統有兩個system call，CreateProcess()以及Sleep()。請寫出它們的用途。並且請找出Unix作業系統相對應的system call的名稱。
**Ans：**
* CreateProcess()
這是一個系統呼叫，用於創建一個新的進程並運行一個新的程序
* Sleep()
這是一個系統呼叫，用於暫停當前進程的執行一段指定的時間

UNIX
* CreateProcess()$\to$fork()+exec()
* sleep()$\to$sleep()
#### P15
你覺得會不會有一種system call，它的唯一效果就是讓使用者行程呼叫它之後，就能轉換為kernel mode？請說明理由。
**Ans：** 不會,因為user mode轉變到kernel mode是特權指令.(特權指令:可能會造成系統重大error的指令)

#### P20
(a)說明什麼是multi-programming系統
**Ans：** 在記憶體中載入多個行程, 系統得以並行(concurrently)地執行多個行程
(b)說明passive multi-programming與 active multi-programming的差異
**Ans：** OS不主動更換行程去執行, 只有執行的行程發生了狀況(i.e., I/O operations, exit), 才有context switch, active 的就會主動更換, 例如time-out
(c)前述的passive與active都是形容詞, 形容的對象是?
**Ans：** OS

### 討論區

Q：
API跟systemcalls兩者的差異性和關聯性

A：
兩者差異性:

System call(系統呼叫):
    提供一個由作業系統服務的介面通常用於存取硬體資源，如檔案系統、網路、設備驅動程式等。

    特點
    主要用於應用程式和操作系統之間的通信。
    位於操作系統的核心層次。
    OS 提供的Function 就是System call。
    由User mode 到Kernel mode。
    因為負責低階工作(硬體直接存取的工作)，必須由組合語言（Assembly language）所撰寫。

    舉例:
    檔案I/O系統呼叫

API(應用程式介面):
    由於System calls 是組合語言，為了方便使用者操作，因此會多一層介面，用以與System calls 溝通，這就是API。API 的形式通常為library，不一定用特定語言撰寫，但大部分的API 都是使用C 語言寫成。
    
    特點:
    相比system call較方便設計者使用。並沒有直接轉換成Kernel mode，除非System call。指定可用的函數給設計者，包括其參數與預期回傳值。設計者經由作業系統提供函數庫使用API。
    
    舉例常用API:
    WINDOWS API，JAVA API
    
兩者關聯性:
API可以包含System Call，以便應用程式或設計者可以藉由API使用System Call來存取操作系統的功能。

總結:
API和System Call都是軟體開發中重要的概念，最大差異在於API通常用於應用程式層次，較方便使用者操作與System calls 溝通，而System Call位於系統核心，提供低階的硬體存取能力。開發者通常使用API來開發應用程式，而API可能使用System Call以實現特定的功能。

Q：
OS帶有三種protection, CPU, memory, 以及I/O, 
1.說明它們的任務為何?
2.它們是在以下的哪一個階段導入OS? multi-programming, simple batch, time-sharing

A：
1.
見Batch vs Multiprogramming-Protection Issue

2.
在Multi-programming、Time-sharing中都會用到，但是Multi-programming出現的較Time-sharing早
Multi-programing：多個Procsss可以同時存在於系統中，並且CPU會在他們之間切換。這些Hardware Protention確保Process之間的隔離和資源保護

Q：
說明課本66頁，Unix 的三個system calls : fork( ), exit( ), wait( )的用途

A：
fork(): 設計多行程的平行化程式時使用，呼叫fork()時會把當前的程式(父行程)複製一份，複製出來的稱為子行程

wait(): 用來解決殭屍程序問題。如果子程序還沒運行結束就將父程序關閉的話，就會有僵屍程序產生。為了避免此情況，可以呼叫wait() 來讓父程序等待，直到子程序結束

exit():命令shell或程式終止

Q：
雙擊桌面的簡報檔, 帶出了powerpoint程式. 請問這樣的過程引發了那些系統呼叫? 請舉出三個

A：
open() 系統呼叫用於開啟磁碟上的檔案。
a program initializes access to a file in a file system using the open system call.

exec() 載入並執行 PowerPoint 程式
runs an executable file in the context of an already existing process, replacing the previous executable.

read() 從檔案系統儲存的ppt檔案存取資料
a program that needs to access data from a file stored in a file system uses the read system call.

A：
Micro kernel 
1.採用極簡設計，僅在核心中實現作業系統最基本的功能，把很多功能都放到核外

2.具有高度靈活性，大多數作業系統功能實現為在user mode中運行的單獨進程

3.安全性和可靠性較高

4.優先考慮極簡和穩定性

5.系統效能較慢，但更穩定和安全

Modular kernel 
1.採用整體設計，所有作業系統功能都在核心中實現

2.彈性低，所有作業系統功能緊密耦合，無法輕易修改或取代

3.安全性和可靠性較低

4.優先考慮功能和性能

5.系統效能更快，但更容易發生故障和攻擊


Micro kernel 
優點：
1.安全性高：萬一 service fail，因為 service 大都 run 在 user mode，頂多相當於 user process 死掉而已，對系統及其他 users、process 無害；核心功能較少，因此攻擊面較小，提高了系統的安全性

2.穩定性高：由於內核功能有限，因此可能更穩定，一個模組的崩潰通常不會影響整個系統

3.隨時能替換不同的 Module

4.模組化和可擴展：Microkernel提供了更高的客製化性，因此可以輕鬆添加或刪除功能模組，從而更容易擴展和自訂

缺點：

1.效率低：每一個 Module 溝通都要 Call System call，消息傳遞慢

2.複雜：管理多個模組和流程可能會增加系統的複雜性

3.資源消耗：作業系統的各個功能被分割成多個模組，這些模組需要獨立運行，因此可能消耗額外的系統資源


Modular kernel 
優點：
1.高效能：模組化核心架構非常高效，因為所有作業系統功能都在內核內實現，從而減少了與進程間通訊相關的開銷

2.簡單：相對於Microkernel，模組化內核操作架構更簡單，減少了管理多個進程和模組的複雜性

3.資源效率高：由於模組通常位於核心位址空間中，可以更有效地使用系統資源

缺點：
1.安全性低：更多的功能位於核心中，所以攻擊面可能會增加

2.穩定性低：由於更多功能位於核心空間，內核崩潰或故障可能會對整個系統產生更大的影響

3.較難客製化修改：相對於Microkernel，可能更難實現高度的客製化，因為必須核心本身

Q：
(a)為什麼system call要越簡潔、越快越好，而又為什麼API可以設計得很長，做再久也沒差?
(b)承上題，所以system call跟API比，誰執行時通常較耗時?為什麼?

A：
(a)
1.system call因為攸關系統穩定性及安全性，若system call過於複雜會增加系統運行的風險，比較容易讓程式或使用者破壞系統內核的程式或數據
2.system call是一個耗時的操作，因此儘可能簡潔也能避免耗時 
3.API是在用戶的空間做執行，因此就算複雜的操作也不會對系統內核造成安全及穩定性的影響
4.API可以根據不同的場景或需求，提供更多細節或選項，讓用戶或程式有更大的靈活性和自由度

(b)
一般來說，System Call的執行時間會比API長。原因在於System Call需要進行使用者模式（User Mode）與核心模式（Kernel Mode）之間的切換。當一個應用程式需要使用作業系統提供的服務時，它需要透過System Call來請求作業系統提供這些服。這種請求需要從使用者模式切換到核心模式，然後再切換回來，這個過程需要一定的時間。

相較之下，API（應用程式介面）是一種讓應用程式能夠使用某些特定功能或服務的介面。API可以是系統呼叫，也可以是純數字運算。API可能只需要執行一些簡單的運算，或者調用一些已經在記憶體中的資料，而不需要進行模式切換。因此，API的執行時間通常會比System Call短。

Q：
1.請說明 command interpreter 的功能以及當中的 command 是如何實作的。
2.command interpreter 是作業系統的一部份嗎？（可以舉例說明）

A：
1.
請說明 command interpreter 的功能以及當中的 command 是如何實作的。

command interpreter 的功能：作為user與OS之間的溝通介面，負責接收和解釋使用者輸入的指令，然後協調操作系統資源以執行這些指令。

運作方式：接收usercommands > 判斷command正確與否 > 若正確，則呼叫對應的Service routine(commandroutine)完成工作 > 將結果回傳給(display to)user

2.
命令直譯器是作業系統的一部分，範例：使用Windows Command Prompt
    1. 用戶啟動了WindowsCommand Prompt（命令提示符）。

    2. 用戶在命令提示視窗中輸入dir，(列出目前的目錄中的檔和子目錄的命令)

    3. 命令提示符(commandprompt)接收到用戶的輸入，傳遞這個命令給Windows作業系統的command interpreter（通常是`cmd.exe`）。

    4. command interpreter解釋並執行命令，告訴作業系統去列出目前的目錄的內容。

    5. 作業系統執行該命令，獲取檔和子目錄的列表，並將其發送回給command interprete

    6. command interprete將結果顯示在命令提示視窗中，使用者可以看到列出的檔和目錄。

1.system call跟system program有什麼區別呢?

2.如果在user mode執行只能在kernel mode執行的process，我們會觸發trap，舉一些實際例子或操作觸發trap

1. System Call 是應用程式與作業系統之間的介面，用於請求作業系統執行特定任務。例如文件操作、進程管理等。

System program是使用了system call來訪問作業系統功能

2.見的例子是網絡設定。當一個用戶應用程式嘗試更改系統的網絡設定，例如配置網絡介面卡的 IP 地址或端口，這需要特權訪問權限，

當用戶應用程式嘗試進行這些變更時，操作系統會引發一個 Trap，將控制權轉交給 Kernel Mode 中的網絡設定處理程序。

確保它們不會對系統的穩定性和安全性造成威脅。

Q：
1.
請解釋The Shared Memory Model和The Message Passing Model。各舉一項例子。並說明他們的優缺點。

2.
在Message Passing Model中，訊息傳遞有什麼格式上的限制?

A：
1.
The Shared Memory Model（共享記憶體模型）： 各個行程利用對共享的記憶體 (共享變數；Shared Variables)的存取，來達到彼此溝通、交換資訊的目的。

shared memory是用讀取(read)和寫入(write)資料來完成資訊交換。

優點：通信速度較快。因為直接存取內存，內存的訪問速度是很快，不需要藉助第三方的幫助。
缺點： 實作比較複雜，並行率低。容易引起競爭條件（Race Condition）和死鎖（Deadlock）
EX：多執行序程式設計

The Message Passing Model（訊息傳遞模型）：行程間會建立連接通道(Communication Link)來溝通。透過使用系統呼叫在進程之間發送(send)和接收(receive)訊息來共享資料。每個執行緒都有自己的私有內存，只有通過明確的訊息傳遞才能共享資訊。

– 建立Communication Link
– 互傳訊息 (Message) 
– 傳輸完畢 中斷連接通道release link

優點：實作簡單，能夠實現多個行程的並行。只需要將訊息傳遞給對方進程的訊息佇列中即可。減少競爭條件的風險，因為訊息是按順序處理的。更容易調試和理解，因為每個執行緒都有自己的內存空間

缺點：通信速率較低。需要系統呼叫來使內核(kernel)幫自己工作，以及內核(kernel)連接訊息佇列時都需要比較多的時間。所以速率較低。

2.
在The Message Passing Model(訊息傳遞模型)中，訊息的格式通常有一些限制，這些限制取決於通信框架和庫的實現。通常，訊息應該是可序列化的，這意味著它們可以被轉換成二進制數據以便在不同執行緒或節點之間傳輸。這樣，通信系統可以有效地傳送和接收訊息。
常見的格式包括JSON、XML、ProtocolBuffers等。
限制還包括訊息的大小和傳輸速率，這取決於通信通道的頻寬和延遲。

Q：
請說明protection ring的ring1和ring2為何不常被使用

A：
因為ring0為具有最高權限的ring，可以管理系統資源，如記憶體和處理器，而ring3用於一般的應用程式，具較低的權限。

1.而ring0及ring3已經可以解決大部分的問題(操作系統及應用程式)，因此ring1及ring2的需求就不是必需的。

2.ring1和ring2並不能直接使用大部分的資源，且有一定的特權，但又不像ring0受到保護，使他們更容易遭受攻擊

## Ch3

### Process

* Process State
* new
Process被創立
* running
Procsee正在被執行
* waiting
Process正在等待某事發生
* ready
Process等待處理器
* terminated
Process完成並結束
* Process Control Block(PCB)(Task Control Block)
* Process State
* Program Counter
下次執行的指令位置
* CPU Register
以Porcess為中心的暫存器
* CPU Scheduling Information
Process優先度，排程隊列指標
* Memory-Management Information
分貝的記憶體
* Accunting Information
以使用的記憶體、啟動以來經過的時間以及時間限制
* I/O Status Information
分配給Process的I/O和打開的檔案清單
* Thread
* Process Scheduling
* I/O bound
在I/O的花費的時間多於CPU計算的時間
* CPU bound
在CPU的花費的時間多於I/O計算的時間
* Job Queue
所有在系統中的Process
* Ready Queue
在主記憶體中等待被CPU執行的Process
* Wait Queue(Device Queue)
等待I/O中的行程
* Long-term scheduling
從Job Pool挑出Job,載入到memory執行
* Medium-term scheduling
當memory space不足時,會把某些processes swap out到disk,等到memory足夠時再將processes swap in memory(Swapping)
* Short-term scheduler
選擇接下來要執行的Process並分配給CPU
* Context Switch
將CPU現在的PCB儲存(state save)並載入儲存的狀態(state restore)還原並執行
* Process Creation
* 使用(Procsee Indetifier)PID做識別
* 資源共享
* 父行程與子行程共享所有資源
* 子行程共享部分父行程資源
* 子行程與父行程不共享任何資源
* 執行狀況
* 子父行程同時中止
* 父行程等待子行程中止後中止
* Process Termination
* exit()
中止行程進行
* abort()
中止子行程進行
* cascading termination
中斷所有行程樹
* Orphan Process
父行程已結束，但子行程還在進行
* Zombie Process
子行程已終止，但父行程未調用wait檢查子行程狀態，此時子行程的Porcess ID還在Process Table(此時的子行程為Zombie Process)
* Interprocess Communication(IPC)
* Process分類
* Indepent Process
不需要依靠任何Process就可以進行
* Cooperating Process
需要多個Process進行，其中可能有包含資源共享
* IPC方法
* shared memory共享記憶體(b)
* message passing訊息傳遞(a)
* unbounded-buffer
無限空間的共享空間
* bounded-buffer
有限空間的共享空間
* Shared Memory
會有多行程間的共享資源同步操作問題
* Message Passing
* Process通訊和同步操作的機制
* 系統不共用變數的情況下通訊
* Process Q和P通訊前需要建立連線
* 通訊方式物理連接和邏輯方法
* Direct Communication
* 自動建立連結
* 一對一
* 雙向或單向通訊
* send(P, msg)、receive(Q, msg)
* Indirect Communication
* 多對一
* 需要Process共用同一個mailbox
* 雙向或單向通訊
* 建立mailbox、傳送資料至mailbox、銷毀mailbox
* send(A, msg)、receive(A, msg)
* Synchronization
* Blocking send(synchronous)
傳送行程等待，直到行程或信箱接收到訊息
* Blocking receive(synchronous)
傳送行程送出訊息及重新操作
* Non-Blocking send(asynchronous)
接收者等待直到有訊息出現
* Non-Blocking receive(asynchronous)
接收者取回有效訊息或無效訊息
* Buffering
* Zero capacity
隊列長度限制為0，發送者須等待接收者
* Bounded capacity
訊息有限容量，若隊列已滿Process要等到友空間才能繼續進行
* Unbounded capacity
訊息無限容量

### 學習單

#### P1
(True of False) Context switch是作業系統的重要概念，而stack內容就是context的一部份。
**Ans：** T

#### P2
(True of False)假設lvar為本地變數(local variable)。經過fork()系統呼叫之後， lvar在父子兩行程之間是獨立的。
**Ans：** T

#### P3
父行程與子行程，通常哪一個先結束？(a)父行程, (b)子行程, \(c\)沒有顯著的傾向，機會差不多各半
**Ans：** B

#### P4
Process 需要佔據好幾塊記憶體；除了text, data, heap, 之外還有?
**Ans：** stack
這四者之中, 通常會動態成長的是哪些?
**Ans：** heap,stack
heap存放什麼樣的資訊?
**Ans：** 儲存動態配置的變數

#### P5
發生什麼樣的事件，會讓行程的狀態會由running轉變為waiting？請舉出兩項具體的事件。
**Ans：** I/O, Event-Wait(行程發出讀取檔案的要求, 行程發出wait()系統呼叫)

#### P6
OS記錄行程的狀態, 有何用途?
**Ans：** 排程(scheduling)的時候, 只需要考慮ready狀態的行程, 可以讓使用者查詢狀態

#### P7

考慮以下依序發生的兩個事件，(1)程A正在執行，行程B在等硬碟讀取檔案。(2)硬碟控制器讀取完畢行程B所需之檔案，而發出了interrupt信號。
* 請問在此interrupt信號發出前，行程A的狀態為？
**Ans：** running
* 請問在此interrupt信號發出前，行程B的狀態為？
**Ans：** waiting
* 請問在此interrupt信號發出後，行程A可能的狀態有哪些？
**Ans：** running，ready
* 請問在此interrupt信號發出後，行程B可能的狀態有哪些？
**Ans：** ready，running

#### P8
The list of processes waiting for a particular I/O device is called a(n) \_\_\_\_.
(a)standby queue, (b)device queue, \(c\)ready queue, (d)interrupt queue
**Ans：** B

#### P9
(a) 請說出兩個device queue的名稱。
**Ans：** I/O queue和input data queue
(b) 什麼樣的事物會放在這個queue裡？
**Ans：** I/0 request完成的process
(c) 會放在這個queue的原因與device有何關係？舉例而言，在戲院售票口排隊的是”人”，排隊的原因是”想買這個戲院的票”。
**Ans：**
可以讓device必較容易挑出process到ready queue上(FIFO原則)

#### P10
如果需要建立一個新的, 不同於原來的行程,
* 在UNIX作業系統之下，該使用哪些系統呼叫？
**Ans：** fork(),exec()
* 在Windows作業系統之下，該使用哪些系統呼叫？
**Ans：** createProcess()

#### P11
System Clock在OS的運作上, 擔任很重要的角色. 請舉出兩個任務
**Ans：**
時間管理：System Clock提供了一個準確的時間來源，讓OS可以追蹤當前的時間
處理器排程：在多任務的作業系統中，System Clock用於觸發中斷，讓作業系統可以定期地切換正在CPU上執行的任務。

#### P12
Android 的行程有”importance hierarchy”
(a) 行程分為哪幾類?
**Ans：** foreground process, visible process, service process, background process, empty process
(b) 分類的目的?
**Ans：** 資源緊繃的時候, 由重要性來決定從哪一個行程回收資源

#### P13
(a) 說明orphan process 與zombie process有何不同
**Ans：**
* Orphan Process
父行程已結束，但子行程還在進行
* Zombie Process
子行程已終止，但父行程未調用wait檢查子行程狀態，此時子行程的Porcess ID還在Process Table(此時的子行程為Zombie Process)

(b) zombie行程的資訊為何還需要保留在系統之中？
**Ans：** 保留著以備父行程將來收割子行程的結束碼

#### P14
說明cascading termination, Windows作業系統是否採用?可以實證嗎?
**Ans：** 不會,根據網上的寫法,父process被終止後,其子process並不會被終止(會變孤兒),但是會由initial process來接收資料(PCB,PID)

#### P15
Pipes有兩種, 一種是Ordinary Pipe, 在Windows作業系統中稱之為\_\_\_\_,另一種是\_\_\_\_.
**Ans：** Anonymous Pipe、Named Pipe

通常需要父子關係才能使用的是哪一種?原因?
**Ans：**
Ordinary Pipe
因為沒有名稱, 非父子關係的行程沒有辦法查詢到此pipe

#### P16
1. degree of multiprogramming
存在於 System 內執行之工作個數,一般而言degree越高$\to$CPU使用率越高
2. long-term scheduler、short-term scheduler、medium-term scheduler
* Long-term scheduling
從Job Pool挑出Job,載入到memory執行
* Medium-term scheduling
當memory space不足時,會把某些processes swap out到disk,等到memory足夠時再將processes swap in memory
* Short-term scheduling
從ready queue中挑選出最高優先權的process來獲取CPU執行
5. device queue
儲存正在等待I/O的Process
6. PCB
CPU為了要追蹤每個porcess,會在每個process建立PCB(Process的重要資訊),例如procress status(running,waiting…),program table,CPU registers…
8. heap
Process的一部分,用來做動態記憶體分配(malloc,new…..)
10. swapper, swap in, swap out
* Swapper
是一個軟體負責process的swap in(out)
* Swap in
把processes從disk移到memory中當有足夠的memory時
* Swap out
把processes從processes從memory到disk當memory不夠時
12. context switch
CPU從processA切換給processB時之前,要先儲存ProcessA的PCB儲存下來並load到processB上
14. process identifier
類似於每個Process的身分證,當process被創造出來時就會被賦予,有時候也會叫PID(Process ID)
16. fork()
creat process的system call呼叫此system call,如果呼叫成功會回傳pid>0給父process,跟回傳0給被子process
18. exec()
此system call是載入binary code file執行來取代父process duplicate的資訊, 並將其內容替換到目前進程的內存空間中，以執行新process
20. exit()
此system call是用以終止process執行(當process完成工作時->自願)
22. wait()
此system call是只當子procress還在執行的時候,父process必須取得取得子process的資訊才能往下執行
24. abort()
此system call是用以終止process的執行(當process執行完工作後)
26. zombie process
28. orphan process
29. cascading termination
當父process終止時,不允許其子process繼續執行
31. CPU-bound process, I/O-bound process
* CPU-bound process:此process主要在做CPU運算(I/0較少)產出速度取決於CPU速度
* IO-bound process:此process主要在做I/O處理(CPU較少)產出速度取決於I/0 Devices速度
33. foreground application, background application (in mobile device)
* foreground application
使用使用者正在使用的applications
* background application
雖然有在執行但是對使用者是不可見的

### 討論區

Q：
行程狀態圖, 由running 到 ready的事件標示著"interrupt" (process.pptx, page 6), 這個事件與InterruptBasic.pptx 討論的 interrupt 有何關係? (完全一樣, 完全不一樣, ...)

A：
以上兩個interrupt我覺得是不同的，

因為第三章的interrupt是指操作系統的調度決策，是行程的運行狀態切換，作業系統通常會進行排程切換以確保公平的 CPU 分配。(不是內部中斷)。

而第一章的interrupt則是在描述hardware的中斷，在執行程式過程中，CPU遇到外部或內部的緊急事件(event)須優先處理，因此暫停執行當前的程式，轉而服務突發的事件，直到服務完畢，再回到原先的暫停處(為一記憶體地址)繼續執行原本尚未完成的程式

Q：
進程調度的概念如何有助於系統資源的有效利用，操作系統中常用的一些調度算法是什麼？

A：
進程調度是指操作系統中的一個重要機制，它可以幫助系統資源的有效利用。進程調度的主要目的是確保系統中的進程能夠按照一定的優先級和時間片來執行，從而提高系統的效率和性能。
常用的進程調度算法是：
A. 先來先服務（FCFS）：按照進程到達的先後順序來執行，即先到達的進程先執行，後到達的進程後執行。
B. 最短作業優先（SJF）：按照進程需要執行的時間長短來排序，即需要執行時間最短的進程優先執行。
C. 優先級調度：按照進程優先級來排序，即優先級高的進程優先執行。
D. 時間片輪轉（Round Robin）：按照時間片大小來排序，即每個進程都有一定的時間片，當時間片用完之後，就會被換下來，換下來的進程會被放到就緒隊列的末尾等待下一次執行。

Q：
請問CPU bound的行程與I/O bound的行程的差異為何？請各舉出一個例子。

A：
CPU-Bound指的是花在CPU computation的時間占大多數，花在I/O operation的時間相對少，例如: 氣象預測分析
I/O-Bound則是在I/O operation的時間站比較多，花在CPU computation的時間相對較少，例如: 薪資報表列印

Q：
APPLE的iOS的原始版本並未提供並行的處理方式。請討論作業系統並處理帶來的三個主要困難。

A：
1.Race conditions 多個process共享同個資源，當系統輸出取決於事件的順序和時間時，而造成不同結果。 
2.Deadlocks 死鎖發生在當兩個或多個程序或執行緒互相等待資源時，形成循環等待，造成系統停滯。 
3.Starvation 當一個程序或執行緒無法訪問其需要完成任務的資源，因為其他程序或執行緒一直佔著資源，導致無限循環等待。

Q:
1. 說明什麼是context switch？
2. 哪些事件會引發context switch?
3. 說明context switch 所花費的時間，由哪些因素決定？ 
4. 說明”context switch time is pure overhead”這句話的含意

A：
1.
context有周圍的環境、因果的脈絡的意思，對程式來說就是執行的環境，包含行程的狀態、CPU暫存器、堆疊區、記  憶體、已開檔案...，在執行一個程式前必須先準備好它的context。

當CPU從一個process切換到另一個process時，OS要儲存舊的process的context，並載入新的process的context，這個過程就是context switch。

2. 
interrupt 或 system call，像是multitasking或user and kernel mode switching。

3. 
除了受到context內容的多寡和硬體速度的快慢影響，register和thread也會影響。

增加的register，讓每個process有專屬的register，可以減少重新載入register的次數。

用thread代替process，藉由共享memory space，可以減少重新載入memory的次數。

4. 
overhead有經常性開支，營運費用的意思。沒有context switch，就沒辦法切換process，所以context switch對於系統的運作是必要的，而且會經常發生，符合"overhead"。

當進行context switch時，沒有process正在運行，所以這段時間只有支出，沒有產出(收入)，符合"pure"。

綜合以上兩點，context switch time的確是pure overhead。

Q：
1. 當parent process 沒有呼叫wait()函式就結束會產生什麼事? 
2. 針對這個事件 linux 和 unix 的對應處理有何不同?

A：
1. 父行程會使用wait()呼叫以取得子行程的退出狀態，核心就可以從記憶體中釋放已結束的子行程的PCB，而如果父行程沒有呼叫wait()函式就結束的話，它的子行程就會留下來當孤兒。

2. Linux和UNIX系統在處理父行程未等待子行程的情況時，基本上遵循相似的原則。Linux系統針對這種情況，會藉由設定init行程為孤兒行程的新父行程。UNIX系統層次結構中init 行程是行程樹的根。Init行程週期性地呼叫wait()，從而允許任何孤兒行程的離開狀態可以被收集，並釋放孤兒行程的識別碼和行程表進入點。

## Ch4

### Multiple Processes
* Multiple Process
* 多個行程共同完成一個任務
* Web Browser
* Server
* 優點
* 程式好寫
* 利用多核心執行
* Process當掉/休眠還有其他Process

### Thread
* Thread vs Process
* Thread
靜態的資源容器
* Process
動態的執行單元
* 簡介
* 執行緒、線程
* 新式作業系統一個行程可以有多線程
* 舊式作業系統一個行程搭配一個線程
* 有自己的執行狀態、儲存、Context
* 與相同行程的Thread分享Data Section
* 同行程的線程稱之為sibling threads(兄弟線程)
* 優點
* New Thread相較New Process快
* Switch to sibling thread較快
不需要做Context switch只需要thread context
* Thread等待時Sibling Thread可以執行
* User Level Thread
* Kernel不知道Thread的存在也不提供Thread相關服務
* User Space的Thread lib處理Thread相關內容
* Thread發出I/O後Process會進入Wait，所有Sibling Thread都會等待
* 優點
* switch 快，無須讓kernel參與
* application-specific thread scheduling
* 任何OS都可，只要library
* 多線程記憶體共享效率比行程通訊效率更高
* 缺點
* 一個thread waiting, 整個process waiting
* 既使有兩個CPU，也無法讓同一行程的兩個ULTs被兩個CPU分別執行
* kernel支援thread
* CPU排程以thread為單位

### 學習單

#### P1
(T or F)在SMP或者multi-core之前的時代，電腦大多只有單一個處理器，這樣的電腦無法提供並行處理(concurrency)的能力。
**Ans：** F
處理器可以透過context switch達成
**並行**，但無法**平行**

#### P2
(T or F)同一行程的兩個thread，可以有不同的起始執行位置
**Ans：** T

#### P3
(T or F)如果A,B並不是sibling threads，當CPU的控制權由thread A轉到 thread B的時候，只需要執行thread context switch，而不需要執行process context switch。
**Ans：** F

#### P4
(T or F) Virtually all contemporary operating systems support kernel threads.
Translate
幾乎所有的當代操作系統都支持內核線程。
**Ans：** F

#### P5
(T or F) It is possible to create a thread library without any kernel-level support.
Translate
不需要任何內核級支持就可以創建線程庫。
**Ans：** T

#### P6
(多選)Which of the following components of program state are shared across threads in a multithreaded process?
Translate
以下哪些程序狀態的組件在多線程進程中的線程之間是共享的？
(A) Heap memory, (B) Register values, (C) Global variables, (D) Stack memory
**Ans：** A、C

#### P7
在一個只有ULT沒有KLT的系統之中，如果某一個ULT因為發出了I/O request而必須等待其完成。那麼它的sibling thread是否可以進入running state？
**Ans：** 只有ULT system中,kernel不會管理threads(因為kernel把整個threads視為一個processes而已),所以當其中block時候,kernel會視為整個process都是block

#### P8
在multi-core的環境之下寫程式，面臨哪些困難(Textbook 4.2.1)？
**Ans：** Identifying tasks:檢查應用程式中哪些是可以切割且分開且可以並行的工作
請說明其中「identifying tasks」的意義，並列出其餘四個。
**Ans：**
1. Blance
2. Data splitting
3. Data dependency
4. test and debug

#### P9
使用multithreaded programming有哪些好處(Textbook 4.1.2)？
請說明其中"responsiveness"的意義，並列出其餘三個。
**Ans：**
Responsiveness:當執行中的thread因某些事件而block時,CPU可以切換給其他available thread使用
1. Resource sharing
2. economy
3. scability

#### P10
請舉出一個實例說明，既使只有一個CPU，一個core，採取multi-process的方式會比較(相對於single process)有效率。
**Ans：** 在任何時間點,最多只有一個Task ex command interpreter

#### P11
下列的程式執行時, 會產生多少process, 多少thread? 請將Process-Thread的樹狀結構畫出來，有多少個Processes, 各Process 之下又有多個threads. (請注意<a.>thread_create呼叫時, 參數中必須給定一個function的名稱, <b.>thread_create結束時控制回到哪裡?)

pid_t pid;
pid = fork();
if (pid == 0) { /* child process */
fork();
thread_create( . . .);
}
fork();

**Ans：** 8 threads,6 processes控制會回到thread_create的參數function

#### P12
(a)請參考課本4.2.2, 說明Data Parallelism 與Task Parallelism的區別。
**Ans：**
* 資料平行:把資料集分成幾個subsets分給cores(每個core做相同的工作)
* 任務平行:把不同的task分給cores(每個core做unique工作)
(b)課本Figure 4.2的Web Server屬於Data Parallelism 還是Task Parallelism?
**Ans：** Task

#### P13
請說明課本4.6.1, 說明fork()以及exec()帶來的爭議。
**Ans：**
就是fork()時,究竟要複製所有的threads還是複製defalut threads就好
課本給出的結論就是如果呼叫exec()(叫子thread做跟父親不同的事情)就複製default thread就好,如果沒呼叫就複製所有的threads

#### P14
碼頭的設施被颱風吹毀, 眾多的居民主動協助船員卸貨, 居民們排成一列人龍, 由岸邊的船一路延伸到倉庫, 貨物箱子就順著人龍進入倉庫.
(a) 這種方式類似於\[ 任務平行化 | 資料平行化 \]
**Ans：** 任務平行化
(b) 如果採取另外一種平行化, 居民該如何做?
**Ans：** 每個人從船到倉庫來回搬貨(做一樣的事)

#### P15
Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single processor system? Explain.
Translate
在多處理器系統上使用多個用戶級線程的多線程解決方案是否能比在單處理器系統上獲得更好的性能？請解釋。
**Ans：**
是,因為在multiple user-level threads上,threads可以執行parallel(平行化)，Performance會相較於sing processor很多，然而single process最多只能做的就是concurrrent(CPU在一段時間只能做一個task)，這項前者也可以做到.(但是前者較難實現)

#### P18
名詞解釋
(a)Amdahl’s law
此理論來表示平行化比起多cores的效能來的關鍵
(b)thread pool
創一些threads放到pool裡,一有request,thread可以直接處裡request(不用收到request才要create)
\(c\)thread cancellation
在thread完工之前就終止,通常此thread叫做target thread
(d)clone()
類似於fork(),但是有更高的靈活性,可以利用flags來決定父子
task的資訊共享程度

## Ch5

### 排班
|工作編號 |到達時間 |所需CPU週期|
|-|-|-|
|A |0 |8|
|B |1 |6|
|C |2 |3|
|D |3 |1|
|E |10 |5|
* First Come First Serve(FCFS)
先來先做

| 順序 | 編號 | 結束剩餘時間 | 結束CPU週期 |
|-|-|-|-|
|1 |A |0 |8|
|2 |B |0 |14|
|3 |C |0 |17|
|4 |D |0 |18|
|5 |E |0 |23|

* Short Job First(SJF)
總工作量最短的先
* Non-Preemptive SJF
做完才會換下一個
* Preemptive SJF
若新來的比較短做新來的

Non-Preemptive SJF
| 順序 | 編號 | 結束剩餘時間 | 結束CPU週期 |
|-|-|-|-|
|1|A|0|8|
|2|D|0|9|
|3|C|0|12|
|4|E|0|17|
|5|B|0|23|

Preemptive SJF
與SRT相同

* Shorest Remaining Time(SRT)
剩餘最少的先做

| 順序 | 編號 | 結束剩餘時間 | 結束CPU週期 |
|-|-|-|-|
|1 |A |7 |1 |
|2 |B |5 |2 |
|3 |C |2 |3 |
|4 |D |0 |4 |
|5 |C |0 |6 |
|6 |B |0 |11 |
|7 |E |0 |16 |
|8 |A |0 |23 |

* Round-Robin(RR)
做$N$週期後丟回queue換下一人

| 順序 | 編號 | 結束剩餘時間 | 結束CPU週期 | Queue |
|-|-|-|-|-|
|1|A|4|4|BCD|
|2|B|2|8|CDA|
|3|C|0|11|DABE|
|4|D|0|12|ABE|
|5|A|0|16|BE|
|6|B|0|18|E|
|7|E|0|22||
|8|E|0|23||

* Priority Scheduling
照權重去分配誰要先做
EX：Solaris
### 評估
* Deterministic Modeling
答案只適合實際給定的情況
* Queueing model
* Little's Formula
$n = \lambda \times W$
$\lambda$：新形成到達比率(幾秒到達一個行程)
$W$：等待時間
$n$：Queue平均長度
* Simulatin
一個模擬器模擬CPU、Process的行進過程
* Implementation
直接把模型塞進作業系統
#### Amdahl’s Law
阿姆達爾定律（Amdahl’s Law）是一種用於預測並行計算理論最大加速度的表達式
並行最大加速度：
$S = 1/(a+(1-a)/n)$
$n$：處理器數量/提升比率
$a$：某事件在程式運行占比

#### Memory Stall
“Memory stall"是指當主記憶體的速度無法跟上CPU的速度時，CPU可能需要等待數個時間週期才能從主記憶體中取得資料，這種現象就被稱為"memory stall”。換句話說，當CPU需要從主記憶體中讀取資料時，如果主記憶體的反應速度較慢，則CPU可能需要暫停其操作，直到資料可用為止。

此外，"Memory Stall"也可能指的是圖形處理過程中，由於可用記憶體不足而無法繼續進行的情況。在這種情況下，增加可用於GrafEq的記憶體量可能會有所幫助
**By Bing**

多線程解決Memory Stall

### 學習單-1

#### P1
(複選)CPU scheduling的趨勢是preemptive, 其原因是
(a)減少平均等待時間, (b)提高CPU使用率, \(c\)較公平 (d)前面三項都對 (e)以上皆非
**Ans：** E

#### P2
[T or F]CPU scheduling的趨勢是preemptive, 其原因是可以減少平均等待時間
**Ans：** F

#### P3
Preemptive system,哪些事件會觸發CPU scheduler?
(a) Waiting 🡪 Ready, (b) Ready 🡪 Running, \(c\) Running 🡪 Waiting, (d)New 🡪 Ready, (e)Running 🡪 Terminated
**Ans：** A、C、D、E

#### P4
Non-reemptive system,哪些事件會觸發CPU scheduler?
(a) Waiting 🡪 Ready, (b) Ready 🡪 Running, \(c\) Running 🡪 Waiting, (d)New 🡪 Ready, (e)Running 🡪 Terminated
**Ans：** C、E

#### P5
以下哪一種scheduling的實作有困難？
(a) First-come, first-served, (b) Shortest job first, \(c\) Priority , (d)Round robin
**Ans：** B

#### P6
平均等待時間最短的是哪一種排程？
(a) First-come, first-served, (b) Shortest job first, \(c\) Shortest remaining time first, (d) Priority , (e)Round robin
**Ans：** C

#### P7
適用於互動系統的是哪一種排程？
(a) First-come, first-served, (b) Shortest job first, \(c\) Shortest remaining time first, (d) Priority (e)Round robin
**Ans：** E

#### P8
在期限過後才完成的任務，等同於完全沒有執行。這樣的系統稱之為 \[hard | soft\] real-time system。
**Ans：** hard

#### P9
real-time system需要針對外界的事件做出即時的回應，回應的時間除了回應的計算以及interrupt latency 之外，還有一項延遲時間是\[Dispatch | latency\]
**Ans：** Dispatch

#### P10
Disk scheduler應該在哪一個佇列中挑選行程?
**Ans：** device queue
被挑中的行程會如何?
**Ans：** I/0 request(等待I/0 Device)
Disk scheduler應該優先挑選\[CPU bound | I/O bound\]行程. 理由？
**Ans：** CPU bound
因為CPU bound在I/O處理時間很短(所以優先權較高)

#### P11
(a)請說明”processor affinity”的涵義
**Ans：** 一旦process在一個CPU執行後,盡量不要轉移到其他CPU上

(b)它有何好處?
**Ans：** 轉移到另一個CPU上,要load原本的CPU上的PCB還要

\(c\)何種情境下,它和負載平衡(load balancing)會有衝突?
**Ans：** loading balance就是防止CPU有些idle有些over loading所以系統會把Overloading CPU某些工作給idle CPU做(剛好與process affinity衝突-><-)

#### P12
假設工作進入系統的時間以及所需要的CPU週期如下表所示。請以FCFS(First Come First Serve)，SJF(Shortest Job First)，SRT(Shortest Remaining Time)以及RR(Round-Robin，時間配額為4)分別排程，畫出甘特圖並計算出每一個工作的等待時間。SRT排程，時間4之後，行程D的狀態可能有哪些？
|工作編號|到達時間|CPU週期|
|-|-|-|
|A |0 |8
|B |1 |6
|C |2 |3
|D |3 |1
|E |10 |5

參考上面

#### P13
(Ex5.2) Discuss how the CPU utilization and response time conflict in certain settings.
a、 CPU utilization and response time
b、 Average turnaround time and maximum waiting time
c、 I/O device utilization and CPU utilization
Translate
討論在某些設定中，CPU利用率和響應時間如何產生衝突。
a、 CPU利用率和響應時間
**Ans：** 如果CPU使用率高的話(context switch要低)可是如果context switch要低的話,response time就會低

b、 平均周轉時間和最大等待時間
**Ans：** 如果要降低average turnaround time的話就要採用SJF排班可是這樣會造成Long burst time process waiting time會增加

c、 I/O設備利用率和CPU利用率
**Ans：**
CPU使用率高的話會造成I/O處理時間非常少(代表I/O 使用率低)
I/O 使用率……………………….CPU………………………..(代表CPU使用率低)

#### P14
解釋名詞
(a) contention scope
在多對多和多對一的module中,thread library排班中的thread在可取得的LWP上執行

(b) memory stall
當CPU會花很長時間讀取memory data(運算速度大於memory存取速度會發生)

\(c\)exponential average
會用於SJF排班上,可以用這次的CPU burst time跟這一次CPB(前面簡稱)預估的跟預估出下一次的CPB

(d)convoy effect
多個processes都在等一個Long CPU burst time process執行造成整體系統waiting time上升

### 學習單-2

#### P1

哪一種scheduling對於Context switch的時間成本最為敏感？
(a) First-come, first-served, (b) Shortest job first, \(c\) Shortest remaining time first, (d) Priority , (e)Round robin
**Ans：** E

#### P2
台北市的紅綠燈常有在停等線之前設置了\[機車停等區\], 汽車就需要在其後排隊, 綠燈後讓機車可以先走, 請問如此的設計比較符合哪一項排程的理念? 請說明理由
(a)FCFS, (b)SJF, \(c\)Priority, (d)Round-Robin, (e)以上皆非
**Ans：** B、C

#### P3
In Little's formula, λ, represents the \_\_\_\_.
(a)average waiting time in the queue, (b)average queue length, \(c\)average arrival rate for new processes in the queue, (d)average CPU utilization
**Ans：** C

#### P4
\_\_\_\_ 以下四種評估方式，最適合教學，展示使用的是:
(a)Deterministic model, (b)Queueing model, \(c\)Simulation, (d)Implementation
**Ans：** A

#### P5
\_\_\_\_以下四種評估方式，需要使用trace tape的是:
(a)Deterministic model, (b)Queueing model, \(c\)Simulation, (d)Implementation
**Ans：** C

#### P6
\_\_\_\_以下四種評估方式，最有可能藉助virtual machine的是:
(a)Deterministic model, (b)Queueing model, (c)Simulation, (d)Implementation
**Ans：** D

#### P7
Please state two factors that related to the learning effect of watching an instruction video clip. Please summarize these factors into an OS terminology. 同一個學生, 同一個教學影片, 觀賞影片後的學習成效也不是始終固定不變,
(a) 請舉出兩項影響學習成效的因素?疲倦, 飢餓, 有沒有預習,…
**Ans：** 略
(b) 請歸納到OS的一個術語context
**Ans：** Context

#### P8
某一個行程有9個CPU bursts, 正常情況下, 會有\_\_\_\_個I/O bursts, 順利執行完畢, 此行程會進入ready queue 多少次?
**Ans：** 8個I/O bursts、進Ready Queue 9次以上

#### P9
PCS(Process Contention Scope)與 SCS(System Contention Scope)有何區別？
**Ans：**
*　Process Contention Scope
適用於多對多,多對一module,thread library的user thread如何在LWP執行
* System Contention Scope
適用於一對一module決定kernel thread在哪個CPU上

#### P10
比較soft realtime system與non-realtime system。
**Ans：** 前者的完成時間有限制(雖然違反也不會致命), 後者沒有
#### P11
由Linux 2.6.23版開始，預設的CPU scheduling演算法為何？
**Ans：** 完全公平排班器(completely fair scheduler)CFS

#### P12
To reduce the waiting time, an expert proposes that each time interval of the traffic light system is reduced to half of its original value, i.e., it was 40 seconds for green light, now it is 20 seconds.
Translate
為了減少等待時間，一位專家提議將交通燈系統的每個時間間隔減少到原來的一半，也就是說，原本綠燈是40秒，現在變成20秒。
(a)Please evaluate this proposal.
(b) Name an OS terminology most related to this question.

#### P13
Process A issued a disk-read I/O operation, and its state was changed to “waiting”. Operating system choose Process B to execute, and priority of B is higher than Process A. Suppose that the disk operation of Process A is finished, and an interrupt signal is raised.
Translate
行程A發出了一個磁碟讀取I/O操作，並且其狀態被更改為“等待”。作業系統選擇行程B來執行，並且B的優先級高於行程A。假設行程A的磁碟操作已完成，並且產生了一個中斷信號。
(a) CPU is going to run the ISR or not?
Translate
CPU是否要運行ISR（中斷服務程序）？
**Ans：** 關鍵在於行程B的優先序是否高於硬碟的中斷(而非行程A), 通常答案為否, 所以會執行ISR, 反之, 則行程B需要遮罩硬碟的中斷, 以保證其繼續執行

(b) What will be the state of Process A?
**Ans：** 前面的答案會決定何時執行ISR, 執行ISR之前行程A的狀態維持waiting, 執行ISR之後, 行程A的狀態才會轉為ready

#### P14
Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.
Tanslate
考慮一種RR（Round Robin，輪詢）調度算法的變體，其中就緒隊列中的條目是指向PCB（Process Control Block，行程控制塊）的指針。
(a) What would be the effect of putting two pointers to the same process in the ready queue?
Translate
如果在就緒隊列中放入兩個指向同一個行程的指針，會有什麼影響？
**Ans：** 在ready queue中兩個pointers將獲得較多使用CPU的時間

(b) What would be two major advantages and disadvantages of this scheme?
Translate
這種方案的兩個主要優點和缺點是什麼？
**Ans：** 好處就是可在 RR scheduling algorithm 將重要的PROCESS提供較多使用CPU的時間 壞處當然就是會有不公平的情況產生 若有多個PROCEESS有兩個以上的POINTER 單一POINTER的PROCESS就可能拉長等待的時間

\(c\) How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?
Translate
你會如何修改基本的RR算法，以在不使用重複指針的情況下達到相同的效果？
**Ans：** 依照每個程式的重要性給予不同的time quantum

#### P17
名詞解釋
1. Trace Tape
由於模擬時,系統不會記錄事件發生的順序(而是頻率),此檔案紀錄事件發生的順序來確保輸出結果
3. Queueing Theory
在操作系統中，排隊理論可以用來預測和管理系統資源的使用。例如，當多個進程需要同時訪問同一個資源（如CPU或I/O設備）時，它們可能需要在隊列中等待。排隊理論可以幫助我們理解和預測這種情況下的系統行為，例如平均等待時間、隊列長度等(bing)
5. Nice Value (Linux CPU scheduling)
CFS會分配每個task nice value值(-20到19)default值為0 值越低相對優先權越大

## 考古
這裡只收錄名詞解釋

### 2018
#### context switch
Ch3自己看

#### Amdahl’s law
此理論來表示平行化比起多cores的效能來的關鍵

#### soft realtime system
對一個非常即時的行程何時被排班沒有保證，只保證該行程比迫切行程會被優先考慮
* hard realtime system
則有比較嚴格的要求，任務必須在期限內被服務；在期限過等同完全沒服務

#### trace tape
由於模擬時,系統不會記錄事件發生的順序(而是頻率),此檔案紀錄事件發生的順序來確保輸出結果

### 2019
#### convoy effect
這是一種與先來先服務（FCFS）演算法相關的現象，其中整個作業系統會因為少數幾個慢速的進程而變慢。FCFS演算法的性質是非抢占式的，也就是說，一旦CPU時間被分配給一個進程，其他進程只能在當前進程完成後才能獲得CPU時間。這種情況導致了所謂的Convoy Effect。假設就緒隊列中有一個CPU密集型（大突發時間）的進程，以及其他一些突發時間相對較短但是I/O繫結（需要頻繁進行I/O操作）的進程。當CPU密集型進程正在執行時，I/O繫結的進程完成了他們的I/O操作並被移回到就緒隊列。然而，由於CPU密集型進程還沒有完成，所以I/O繫結的進程被迫等待，導致I/O設備閒置。因此，在Convoy Effect中，一個慢速的進程會降低整個進程集的性能，並導致CPU時間和其他設備的浪費。
**By Bing**
#### exponential averaging
這是一種用於預測下一個CPU突發的技術。它使用以下公式來計算預測的突發時間：$T_{n + 1} = \alpha T_n + (1 - \alpha )T_n$，其中$α$是平滑因子$（0 <= α <= 1）$，$T_n$是第n個進程的實際突發時間，$Τ_n$是第n個進程的預測突發時間。這種方法通常用於最短工作優先（SJF）CPU排程。
**By Bing**
#### loadable kernel module
* 模組(Modules)
* 可載入核心模組**loadable kernel modules**
* 物件導向化
* 核心元件互相獨立
核心元件透過已知介面傳輸
* 物間根據需要在內核中載入其他元件
* EX：現行作業系統

#### processor affinity
處理器親和性是一種允許系統管理員和開發人員控制作業系統如何在電腦的中央處理單元（CPU）上排程進程和線程的功能。它使您能夠指定哪些核心負責執行特定的進程或應用程序，優化工作負載和資源的分配。如果您不設定親和性，一個線程可以在任何CPU核心上運行。所以它會很有幫助，因為它不需要等待特定的CPU核心可用。
**By Bing**

### 2020
#### daemon process
是一種在後台執行，而不由使用者直接互動控制的電腦程式。系統通常在啟動時一同啟動Daemon Process。Daemon Process會執行一些工作以回應網路請求、硬體活動或其他應用程式的請求。
#### system programs
系統程式，非核心必要，但system program可以透過system call達成任務
#### thread control block
線程控制塊（Thread Control Block，TCB）是一種與進程控制塊（PCB）相似的子控制塊。TCB只包含執行需要的信息，例如程序計數器（PC）、堆疊指標（SP）、條件碼、數據寄存器等寄存器信息

#### system call
[看前面](https://hackmd.io/@HongMJ1315/Operation_Systems#System-Calls)

### 2021
#### programmable interrupt controller
[看前面](https://hackmd.io/@HongMJ1315/Operation_Systems#Interrupt)
#### scheduler and dispatcher
* schedular
從記憶中選擇要執行的Process
* dispatcher
為schedular子元件，dispatcher會將CPU控制權交給被schedular選擇的Process
Dispatcher功能包含
* context switch
* 轉換成user mode
* 跳躍到使用者程式位置，以便重新開始程式
#### thread control block
看去年的
#### dual mode
[看前面](https://hackmd.io/@HongMJ1315/Operation_Systems#Dual-Mode-Operation)

### 2022
#### cycle stealing
指利用CPU不訪問暫存器的週期來做到Driect Memory Access，此時Driect Memory Access可以使用總線而不通知CPU
#### context switch
將CPU現在的PCB儲存(state save)並載入儲存的狀態(state restore)還原並執行
#### degree of multiprogramming
當前在記憶體的行程數
#### device queue
[看前面](https://hackmd.io/@HongMJ1315/Operation_Systems#Process)