# Operating System - 期中Note
###### `大三上` `作業系統`

## CH1 Introduction

### What Operating Systems Do

#### Computer system:
* Hardware
>CPU, memory, I/O devices
* Operating system
* System and Application programs
>Compilers, assembler, word processors, your first hello world program…
* Users


#### What Operating Systems Do?
* 是個software
* 管理computer hardware
* 提供環境給application programs執行
#### Defining Operating System
* 沒有通用的定義
* 常常用的定義
* a program running at all times(***kernel***)
#### 電腦系統組織
* 經由共用記憶體的公用匯流排(bus)連接在一起
* Device drivers: software
* OS上都有device driver(裝置驅動程式)
* CPU & controller會搶memory => 記憶體控制器(能同步存取)
* Device controller: hardware
* 有local buffer & special-purpose registers

#### 自問自答時間
>
---

### Computer-System Organization

#### Interrupts 中斷
控制器(Device controller)要通知驅動程式操作已經完成 => 中斷
1. 控制器在**中斷請求線**上(interrupt-request line)發出signal
2. CPU讀取(catches)中斷編號 -> CPU dispatches it to the **中斷處理常式**(interrupt handler)
3. handlers提供serve給裝置


:::info
:bulb: ISR(Interrupt service routine) 或interrupt handler
:::
* ISR
* 保存狀態
* Service the interrupt
* Executes a 'retrun_from_interrupt' instruction
* CPU 返回中斷前的狀態
:::success
中斷可做優先層級priority levels考量
OS用中斷處理非同步事件
:::

#### Storage Structure 儲存體結構
* organized in hierarchy(層級)
* 最讚的 = **semi-conductor memory**
* Primary storage
* 主記憶體(隨機存取記憶體RAM)
>用動態隨機存取記憶體(DRAM)的半導體技術製作
* RAM是揮發性(volatile)的 => 關閉電腦會內容消失
>用EEPROM(電子抹除式複寫唯讀記憶體) & firmware(韌體)取代
>但是EEPROM很慢
* Secondary storage 輔助儲存器
* Electrical-based: 非揮發性記憶體設備Nonvolatile Memory (NVM)
* Flash memory (SSD): 最常見的方法
* Mechanical-based: hard-disk drives (HDD) (or called magnetic disks)
* 最常見的輔助儲存器

* Tertiary storage
* 儲存備份用

* I/O operation
* Device driver : 在裝置控制器中載入適當的暫存器
* Device controller :

    1. 檢查reg的內容 -> 決定做甚麼action
    2. 開始動作 -> 從裝置傳送data到本地緩衝區(local buffer)
    3. 完成了 -> Device controller利用interrupt通知CPU

---

### Computer-System Architecture

#### Single-Processor Systems 單一處理系統
* 只有一個通用處理器
* 特殊用途處理器
>磁碟 鍵盤 圖形控制器

#### Multiprocessor Systems
* 優點: increased throughput => 完成更多工作量
* 兩種管理方案:
* Asymmetric Multiprocessing
>主處理器控制系統, 定義了**master-slave** relationship
* Symmetric Multiprocessing (SMP):
>最常見的系統
>每個處理器都是對等的(peer), **不**存在master-slave relationship
* Approaches
* Multi-processors: 每個處理器有一個單核心CPU
>
>
* Multi-core systems: 單一晶片上的多個內核
>比"很多個單核還有效率"
>**On-chip communication** 比 **between-chip communication** 快

* Non-uniform memory access (NUMA):
>在多處理器系統上增加太多CPU
>* 系統匯流排爭用成為瓶頸
>* 性能下降
>* 
>Alternative approach(替代方法): NUMA
>Provide each CPU with its local memory
>* Accessed via a local bus
>越來越受歡迎
>

* Blade server:
>多個**processor board** are placed in the **same box**
>每個processor board 獨立啟動並運行自己的OS
>

#### Clustered Systems (叢集系統)
透過區域網路 (LAN) 連接的多台電腦
>

* The key of a clustered system is high availability(高可用性)
* Graceful degradation(優雅降級): 繼續提供與surviving hardware水準成比例的服務
>
* Fault tolerant(容錯): 即使任何一個組件故障，也能繼續提供服務

---

### Operating-System Operations
>作業系統的基本運作方法: OS is event-driven
* Interrupt: driven by hardware(硬體驅動)
>

* Trap (or exception): a software-generated interrupt
>* 例如: Error： 除以零，非法指示
>
>* System calls or monitor calls
>作業系統提供的功能，為應用程式提供服務
>read(), write(), open()……
>
#### Multiprogramming and Multitasking
* Single-programming systems
* One job at a time: 一個工作做完才做下一個
* Very inefficient : 當正在執行的程式執行 I/O 時 CPU, 處於閒置(idle)狀態

* Multi-programmed systems
* Why use multiprogramming
>efficiency: 有效率多了(跟Single-programming systems比)
>執行多個程式使 CPU 或 I/O 裝置始終處於忙碌(busy)狀態
* Memory Layout(佈局) for a Multiprogramming System
>A set of jobs is kept in **memory**
>

* Time-sharing (or multitasking) systems
* **Problem** of Multi-programming systems
>Multi-programming 有些問題:
>Does not provide user interaction(用戶交互)
>

* **Solutions**: **Timesharing (Multitasking)**
>* 改善方法: Timesharing
>* Logical extension of multiprogramming
>* CPU switches jobs so **frequently** (直到要執行 I/O)
>* Users can **interact** with each job **frequently**
>* Create an **interactive**(互動式) computing environment (EX: using keyboards or mouse)
>* **Response time** is short
>
#### Dual-Mode and Multi-mode Operation
* To ensure proper execution of the system
>必須區分**execution of OS code** & **user program code**
* **Solution:** CPU supports dual-mode or multimode operations
* **Dual-Mode Operation**
>現代CPU至少有兩種執行模式
>
* User mode: 代表使用者執行
* Monitor mode: 代表作業系統執行
>* 也稱為supervisor mode, system mode, or privileged mode
>* 可以執行所有指令, 包含**privileged instructions**
* Controlled by a mode bit(模式位元)
* Privileged instructions
>* 可能cause harm的說明
>* 只能在supervisor模式下執行
>* Example: I/O control, timer management, interrupt management
* Why uses Dual-mode operation?
>* 保護
>* **Privileged instruction**只能在kernel mode執行
>如果在使用者模式下執行, 硬體會引發**trap**
>Trap導致CPU跳到作業系統, 從而終止應用程式
* Entering Monitor Mode (the same as entering OS)
* As the result of an interrupt
* Through a system call trap
* As a result of an error trap

* Multi-Mode
>EX:
>* x86 CPU has four protection rings (modes)
>* ARM8 has seven modes
#### Timers
* **Question**: 如何防止用戶程式永遠獲得CPU？
>也就是說如何實現time sharing systems
* We must have a way to enter OS
>System call traps
>Error Traps
>Interrupts
* **Solution: timer**
>引起timer interrupt periodically
>CPU回傳給作業系統
>修改定時器內容的指令是有特權的(privileged)

:::success
:collision: 作業系統的基本運作方法和CPU/硬體有密切關係
:::

---

### Security and Protection
* **Protection** – **controlling** access to resources
>區分**授權**使用和**未經授權**的使用

* **Security** – **防禦**系統免受攻擊
* 為了實現保護和安全, 系統必須**區分用戶**
* **User identifier** (user IDs): unique, one per user
>使用者ID與使用者的所有file和processes相關聯
* **Group identifier** (group ID):unique, one per group
>也與每個process和file關聯
#### Open-Source Operating Systems
* 以原始碼格式提供的作業系統
>Windows: just binary, **closed-source**
* 由自由軟體基金會 **(FSF)** 發起，該基金會擁有「copyleft」GNU 公共授權 **(GPL)**
* Examples include **GNU/Linux**, **BSD UNIX**, and **Sun Solaris**

---

### 來個CH1總結吧~
* Computer System Structure電腦系統結構
>Hardware, operating system, system and application programs, users
* Computer-System Organization電腦系統組織
>Interrupts
>Storage structure
* Computer-System Architecture電腦系統架構
>Single-Processor Systems
>Multiprocessor Systems
>Clustered Systems
* Operating-System Operations作業系統操作
>Multiprogramming and Multitasking
>Dual-Mode and Multi-mode Operation
>Timers

---
## CH2 Operating-System Structures

### Operating System Services
* 作業系統為程式和使用者提供服務
>EX:
>Program execution
>Manage hardware

---
### Operating-System Interface to Users
* 對於用戶來說, 與作業系統互動的基本方法
* Command-line interface **(CLI)** (or command interpreter)
>**命令解釋器** 允許直接鍵入命令
* 從用戶Fetch命令並執行
* 作為**系統程式(system program)** 實現
>**Not** part of OS
* Linux中實作了多種選擇－**shells**
>Bourne shell (bash), C shell (csh), Korn shell (ksh)
* Batch interface (批次介面)
* Graphical User Interface (GUI)
* 使用者友善的**桌面**介面
>Mouse-based的視窗和選單
* Touch-Screen Interface
* Touchscreen devices
>觸控螢幕裝置
* Voice commands
---
### System Calls
* 作業系統提供的Functions, 為user applications提供服務
* Example: open(), read(), write(), close()……
* 就算是簡單的程式也是可能用很多system call的 :+1:
>

* 通常每個system call都關聯一個數字
* OS維護一個根據這些數字索引的表 :grey_question:
* APIs
* 系統呼叫通常透過Application Program Interface(API)**間接存取(indirectly)**
* 不是直接call system call
* fopen(), fread(), fwrite(), printf()…都是APIs
>紅: system call; 藍: APIs
>
* API就是一組可供程式呼叫的function
* 來一鍋常見的API
1. **Win32** API for Windows
2. **POSIX** API for POSIX-based systems
>All versions of UNIX, Linux, and Mac OS X
3. **Java** API for the Java virtual machine (JVM)
* Supported by **library**
>之前組語說的Kernel32.lib就是Win32 API的函式庫
:::success
:accept: **為啥選API 不是選system call咧?**
* **Portability (可攜帶性)**
* system call的interface不同
>
* API不用修改source code
>
* **Easier to use**
>程式設計師不用知道系統呼叫是如何實現的
:::
* System Call Parameter Passing
* 傳參數(parameters)給OS的3種方法
1. Pass the parameters in **registers**
>參數可能比reg多
2. Parameters儲存在block in memory, and address of block passed as a parameter in a register
3. 參數由program壓入stack並由OS從stack彈出
* Block and stack方法不限制參數的數量或長度
* CPU Registers
>
* Memory Block
>
* Stack
>
---
### System Services
* System services (or system utilities)
>為程式開發和執行提供便利的環境
* Categories
* File management
* Status information
>Windows工作管理員
* File modification
* Programming language support
>Compiler, assembler, interpreter
* Program loading and execution
>Loader and debugger
* Communications
* Background services
>Usually called **services**, **subsystems**, or **daemons**
---
### Operating-System Design and Implementation
* 設計和實現(implementing)作業系統時遇到的問題
* Design goal
* 受影響的有:
>1. Hardware
>2. Type of system：傳統桌上型電腦/筆記型電腦、mobile、distributed或real time
* **User goals** and **System goals**
* There is no unique way to achieve all goals ⇨ compromises(妥協) may be taken
* Mechanism and policies
* mechanism跟policies分離的重要原則
* Mechanism
>怎做到?
>**insensitive(不敏感)** to changes in policy
* Policy
>將會做啥？
>可能會隨著地點或時間的推移而改變 :question:
* Separation這兩家伙是為了實現flexibility
* Implementation
* OS Implementation
>以前OS是用組語寫的 :shocked_face_with_exploding_head: 像是MS-DOS
>現在多用高階語言 :smile:
* Major performance improvement
>**不是透過assembly語言改進performance**
>compiler變先進了 現在只剩**bottleneck routine**是用assembly寫的
>是透過better **data structure** and **algorithms** :anger:
---
### Operating-System Structure
#### Monolithic (龐大的/單一的\[from課本\]) structure
* 沒有明確的結構
>Examples:
>* MS-DOS
>* Original UNIX => 在system call interface跟physical hardware之間都是**kernel**:+1:
>
:::info
:+1: :明顯的性能優勢(performance advantage),system-call interface的開銷非常小,kernel通訊速度快
:-1: :不好implement and extend
:::
* UNIX, Linux and Windows are monolithic kernels
#### Layered approach
* OS分很多層
* Layer approach: 每一層only使用lower-level layers的功能和服務
* Advantages:
* 方便 construct & debug: Starts from the lowest layer
* Information hiding: 不必了解其他層的details
* Layered File System(分層檔案系統)
>
* Difficulties
* 很難確定層數
* 很難定義每一層的功能
* 效率較低
* 一個服務可能涉及多個layers, 但多加layer會增加開銷
* Trend: 少少layers, 多多functionality
#### Microkernel
* **Motivation**: Micro是因為UNIX變得龐大且難以管理
* 想法：盡可能從核心移動到**user space**
* 小點的kernel
* CMU
* What a microkernel **should provide** ?
* **minimal process** + **memory management** + **communication facility**
* Communication facility
* 提供**客戶端程式**和**各種服務**（稱為伺服器）之間的通信
* 透過**訊息傳遞**提供
:::info
:+1: :**容易擴展**作業系統 + **容易將作業系統移植到新架構**(architecture) + **更可靠、更安全**
:-1: :服務之間**傳遞訊息**的效能開銷 + **Windows NT**：microkernel/**Windows XP**：monolithic kernel
:::
>教授挖了坑, 吊大家胃口 :wave:
>
#### Modules
* 目前OS設計中最佳的方法
* OS含有:
* A **core kernel**
* 一組**loadable kernel modules (LKMs)** <= 可在運行時dynamically loadable
* 類似於分層系統
* more **flexible**
* 類似於microkernel approach
* more **efficient**:point_left:因為Kernel module通訊是function calls, 而不是message passing
#### Hybrid systems(混合系統)
* 現代作業系統不採用(adopt)單一結構
* Hybrid systems結合了多種結構
* *Linux* is **monolithic**
* modules for dynamic loading of functionality
* *Windows* is mostly **monolithic**
* personalities (user-level services) **(microkernel)**
* modular for dynamic loading of functionality(這跟Linux一樣:shocked_face_with_exploding_head: )
---
## CH3 Processes
### Process Concept
#### The Process
* **Process又叫jobs, tasks**
* **Program – passive**
* **Process – active**
>Program - 是.exe(存在記憶體中的)
>Process - 是程式的運行實例, 儲存在RAM中(工作管理員看到的)
>
* 一個process需要certain resources(一定的資源)
* CPU
>目前活動的狀態：PC（Program Counter）、暫存器…
* Memory
>**Text section**: program code
>**Data section**: global variable
>**Stack section**: temporary data
>**Heap section**: memory that are dynamically allocated by calling **malloc()** and **free()**
>
* Files
* C Program的Actual Memory Layout(實際記憶體佈局)
* **global data section(全域資料區)** is divided into **initialized(初始)** data and **uninitialized(未初始)** data sections
>為*argc*和*argv*參數提供了separate section
* 取得segment of a program的大小

        size executable-file-name

-- **text**：程式碼段
-- **data**：初始化的全域數據
-- **bss(block start by symbol)**：未初始化的全域數據
-- **dec(10) and hex(16)**：三個部分的總和
#### Process State
* 當process執行時，它會改變狀態(state)
* **new:** The process is being created
* **running:** Instructions are being executed
* **waiting:** The process is waiting for some event to occur
* **ready:** The process is waiting to be assigned to a processor :point_right: 程式 is runable(隨時可以跑跑跑了~)
* **terminated:** The process has finished execution
* 一個core上只能運行**一個process**
* Many processes may be **ready** or **waiting**
>被打斷的running狀態變成ready
>碰上I/O的running變成waiting:point_right:完成後又變ready
#### Process Control Block ***(PCB)***
* 對於每個process, OS維護一個稱為**process control block(task control block, process descriptor, task descriptor)** 的資料結構來保存與每個process的資訊
* Keep **information** associated with each **process**
* PC: **address of the next instruction**(下一指令的位址)
* 當發生interrupt或context switches時儲存
* CPU registers
* 當發生interrupt或context switches時儲存((教授又賣關子:/
* CPU scheduling information: process優先權
* 記憶體管理資訊
* Accounting information
* **CPU time** and **real time** used
* I/O狀態訊息
* Open files and devices
* PCB大概長這樣XDD
>
* Process Representation(表示) in Linux
---
### Process Scheduling
* Process scheduler (or CPU scheduler)
* 選擇一個準備好的processes在CPU core上執行
* Degree of multiprogramming
* 當前記憶體中的processes數量
#### Scheduling Queues
* OS maintains **scheduling queues** of processes
* **Ready queue**:point_right:residing in main memory
* **A set of wait queues**:point_right:set of processes waiting for events
* Processes在**ready queue和various wait queues之間**遷移(migrate)
* **Queuing-Diagram** Representation of Process Scheduling
* 來~process執行中會發生什麼呢? 讓我們繼續看下去 :satisfied:
* The process issue an I/O request
>process 被放在 I/O wait queue
* The process creates a new child process
>process 被丟在 wait queue 等待 child 結束
* The process is removed from the core due to interrupt
>process 被放在 interrupt wait queue
* The process is removed from the core, due to its time slice expire
>process 被放回 ready queue
>
#### CPU Scheduling
* **CPU Scheduler** (or Process Scheduler)
* 從ready queues中選擇一個process並為其allocates CPU core
>如果process執行太久:point_right:換人
>
* CPU scheduler is invoked very frequently ,但不能一直用(:question:
* 某些作業系統引入了調度的中間(intermediate)形式:point_right:**Swapping**
* 如果memory空間用完, 就**remove process** from memory
* process 也可以 re-introduced into memory
>先暫時從記憶體丟出去 ,再等有空間的時候重新抓回來記憶體中
>
#### Context Switch
* CPU從一個process**切換**到另一個process
* 作業系統必須在其 PCB 中**保存(save)** old process 的 **state(context)**
* 作業系統必須從 PCB **恢復(restore)** 新process **saved state(context)**
* **Context (state):**
* CPU registers(PC)
* Memory areas
* Various tables
* 構成process的environment or context

:::info
:i_love_you_hand_sign: 切換Process時 **(Context Switch)**，必須要儲存當下Process的state，然後復原接下來要執行的Process的state!
:point_right: 儲存的state記錄會在**PCB**當中
:::
來!圖片解釋:
P0換到P1, 先把P0存到PCB, 再讓P1下去跑
:::warning
:zap:比較:
ISR 就沒有要保存/恢復的狀態
:::
* Context-switch time is overhead (開銷大)
* 切換時, 系統**不執行**使用者應用程式 (浪費了)
* 用於減少context switch overhead的Hardware支撐
* save/load所有暫存器的單一指令
:::success
:100: 複習：Related Instructions
**1. PUSHFD and POPFD**
:point_right: 壓入和彈出 EFLAGS 暫存器
**2. PUSHAD** pushes 32-bit 通用暫存器 on stack
:point_right: Order: EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI
**3. POPAD** 以相反的順序將相同的暫存器從堆疊中彈出
:point_right: PUSHA 和 POPA 對 16 位元暫存器做同樣的事情
:::
---
### Operations on Processes
#### Process creation
:::success
:key: **問題：** 當Double Click某一個應用程式，發生了什麼事情呢?
**解答:** Windows檔案總管(or Shell in Linux)會create一個process(or 請OS creates一個process)，執行此一應用程式
:::
* 一個process可能會建立多個新process
* Forming a tree of processes
>
>作業系統根據唯一的process identifier（或pid）來識別processes
* Execution
* Parent waits 要等 children terminate
* 用 **wait()**
* Address space
* fork()系統呼叫在Linux中建立一個new process
* exec()系統呼叫以新程式取代process的記憶體空間
* UNIX Process Creation
* 每個process都有一個唯一的process ID **（PID）**
* 透過 **fork()** 系統呼叫建立一個new process
* Child複製parent的address space
* system call
* **child：** fork的回傳值為**0**
* **Parent：** fork的回傳值為**child的PID**
* **execlp()** 系統呼叫用於將new binary file載入到記憶體中 - 銷毀舊程式碼
#### Process termination
* Process invokes **exit()** system call
* 回傳 **status value** with **its process identifier** 給 parent
* Parent透過 **wait()** 系統呼叫取得child的status value和process identifier
* Then, process的資源被作業系統釋放
* 當子process終止且他的父process還沒呼叫 wait()
* 子process => **zombie(殭屍) process**
>**process control block (PCB)** 仍然存在用於儲存**exit status** value
>

* BUT, 如果父process**沒有呼叫 wait()** 並且被終止
* child process => **orphans(孤兒)**
>為了避免孤兒出現: Linux 將child的**parent設定為 init**
>**init定期呼叫wait()** 來收集child的退出狀態值
>
---
### Interprocess Communication (IPC)
* Independent process(獨立)
>不會跟別人share data
>不被影響也不影響別人
* Cooperating process(合作)
>會Share data
>可被影響OR影響別人

:::info
:bulb: **為何要cooperating?**
1. Information sharing 資訊共享
2. Computation speedup 計算加速
3. Modularity 模組化
:::
* Cooperating processes 需要 **interprocess communication (IPC) mechanism(機制)**
* 2種常見models(os_lab7做過的)
1. Message passing (a)
2. Shared memory (b)
>

* Interprocess Communication (IPC)
* 比較Message passing & Shared memory
| \ | Message passing | Shared memory|
| -------- | -------- | -------- |
| **速度** | 慢(需system call)| 快(不需system call) |
| **實現** | 簡單 | 難 |
| **衝突** | No conflict | 需要protection and synchronization|
| **其他** | 交換少量資料很有用 | 共享記憶體|
:::success
:microscope: **複習: 為何Microkernel效能不好？**
Performance overhead by message passing between services (效能開銷)
:point_right: 因為system call 很多
:::
---
### IPC in Shared-Memory Systems
* Shared-Memory
>* Communicating processes 需要**建立**共享記憶體區域
>* 使用該區域的其他process必須將其**附加(attach)到其位址空間**
* 共享記憶體**消除**了一個process無法存取另一個process記憶體的限制
`教授PPT跳過Example - consumer & producer`
---
### IPC in Message Passing Systems
* 2種
1. send(message)
2. receive(message)
#### Synchronous(同步) or asynchronous(非同步) communication
* *blocking* or *non-blocking*
>**同步 or 非同步**
* **Blocking(等待)** - process 暫停直到 I/O 完成
* 易於使用 but 某些地方仍然不優呀~
* **Nonblocking(非等待)** - I/O 立即呼叫返回, 並返回盡可能多的可用數據
* return value指示傳輸了多少位元組(bytes)

*
| Blocking | Non-blocking |
| -------- | -------- |
| 又稱synchronous | 又稱asynchronous |

1.
| Blocking send | Blocking receive |
| -------- | -------- |
| 發送者被阻止，直到接收者收到訊息|接收者block直到有訊息可用|

2. |Non-blocking send |Non-blocking receive|
| -------- | -------- |
|發送方發送訊息並恢復操作|接收者檢索到有效訊息或空訊息|
---
## CH4 Thread & Concurrency
### Overview
:::warning
:question: **Problem: Process is high overhead**
1. minimize code size or shorten execution time(最小化程式碼大小或縮短執行時間)
2. Resource sharing(資源共享): by **threads**
:::
* Process: **High overhead(高開銷)** abstraction to execute a program
>E.g., 建立process是一項expensive的操作
* Solutions: **thread**
>CPU利用率(utilization)的基本單位
>跟process很像, 也需要thread ID, program counter(PC), register set, and stack
>**某些資源是和相同process的執行緒們共享**
>* **Code section**, **data section**, and other **OS resources**

* Single and Multithreaded Processes
* Create a Process v.s Create a Thread
>可以共用**Code section**, **data section**, and other **OS resources**
* **Thread Control Block (TCB)**(or Thread Descriptor)
>每個thread都有自己的TCB，就像每個process都有自己的PCB一樣
>:::success
>:bulb:: 為啥同一個Process下的Threads**不共享Program Counters(PC)和Registers Values**咧?
>:a:: Threads也有自己的執行狀態,所以,*Context Switch*時必須
>1.將目前正在執行Thread的狀態儲存到TCB
>2.復原接下來要執行Thread的狀態
>:::
>
* Thread 的 Benefits
* Responsiveness(反應能力)
>如果一個執行緒被blocked或執行冗長的操作, 其他執行緒可以繼續運行
* Resource Sharing(資源共享)
>執行緒共享它們所屬process的記憶體（code和data）和資源
* Economy(經濟)
>**Create** and **context-switch** thread 比 processes 快得多
>與processes相比, *creating速度快30倍*, *context switch速度快5倍*
* Scalability(可擴展性)
>multi-CPU machine上的多執行緒可提高並發性(concurrency)
>每個執行緒可以parallel(平行)
* Examples
* 很多 software packages 都是 multi-threaded
* *File servers* or *web servers*
* 需要在短時間內處理多個請求
1. Process sequentially：不好
2. 為每個請求建立一個process => 耗時又佔用資源
3. 為每個請求建立一個thread => 有效率
---
### Multicore Programming
#### Concurrency v.s. Parallelism
* 在single-processor系統上, **processes是concurrently**運行的, 但**不是parallel**運行的
* **Concurrency**支援多個任務取得進展
* multicore系統, processes可以**parallel**
* Parallelism意味著系統可以**同時(simultaneously)執行多個任務**
#### Types of Parallelism
:::info
:palm_tree: 教授言:
今日的電腦都是Multi-Core, 所以我們以後寫程式要Parallel Execution, 以充分利用每一個Core！
:::
* 兩種 parallelism: **data parallelism v.s. task parallelism**
1. Data parallelism
* 在資料的不同組成部分上運行**相同的任務**
:::warning
:bulb:EX：對大小為 1000 的陣列求和（如果有兩個核心）
一個核心上的執行緒 A 對元素 [0]…[499] 求和
另一個核心上的執行緒 B 對元素 [500]…..[999] 求和
:::
2. Task parallelism
* 對**相同資料**運行多個任務
:::warning
:bulb:EX：對大小為 1000 的陣列求和並相乘（如果有兩個核心）
一個核心上的執行緒 A 對元素 [0]…[999] 求和
另一個核心上的執行緒 B 執行元素 [0]x [1]x…x[999]
:::
>
* Hybrid
Most applications use **data parallelism + task parallelism**
:::warning
:warning: 例如：對大小為 1000 的陣列求和並相乘（如果有四個核心）
一個核心上的執行緒 A 對元素 [0]…[999] 求和
另一個核心上的執行緒 B 執行元素 [0]x [1]x…x[333]
另一個核心上的執行緒 C 執行元素 [334]x [335]x…x[666]
另一個核心上的執行緒 D 執行元素 [667]x [668]x…x[999]
:::
#### Multi-Core Programming Challenges
* **Divide activities**
>將應用程式劃分為單獨的線程
* **Balance**
>每個執行緒執行同等價值的同等工作
* **Data splitting**
>每個執行緒存取的資料必須劃分在每個核心上運行
* **Data dependency**
>Chapter 6 才說
* **Testing and debugging**
>比單執行緒應用程式更困難
---
### Multithreading Models
:::success
:tanabata_tree: **Question: How to Support Thread?**
1. **fork() is used to create process**
=> 程式設計師需要一個function來create thread, 假設此一function 為 *pthread_create()*
2. **fork() function is provided by OS**
=> *pthread_create()* is provided by **OS & User-level library**
:::
* **User threads**
* user-level library
* user level
* **Kernel threads**
* OS
* kernel level
* **Many-to-One**
* 用於不支援kernel threads的系統
* 執行緒管理由user space的thread library完成：**Efficient**
* **Many-to-One:** kernel process
* 傳統沒有使用thread的processes我們視為single thread process
* **Blocking problem:**
* 如果一個執行緒進行blocked系統調用, 整個行程就會被blocking
* 不支援在 MP 上並行運行
* kernel 只看到一個 thread (process)
>
* 很少有系統繼續使用這種模型
>無法利用multiple cores的優勢
* **One-to-One**
* 用於支援kernel threads的系統
* 每個user-level thread 映射(map)到一個kernel thread
* **Good: more concurrency(並發性)**
* 無blocking系統呼叫問題
>如果一個線程進行 blocking 系統調用, kernel可以運行另一個thread
* 允許多個執行緒在多處理器上parallel
* **Bad:**
* 創建用戶線程需要creating a kernel thread
* if 核心執行緒很多, overhead會很高
>
* **Many-to-Many**
:::warning
:dizzy: **前兩個models的問題:**
**Many-to-one:** 沒有獲得真正的 concurrency
**One-to-one:** 不能建立過多的 user threads
:::
* Many-to-Many 允許 ***M*** 個 使用者層級的 threads map 到 ***N*** 個 kernel threads, 其中 ***N <= M***
* 保證真正的 concurrency
* 核心執行緒可以在 multiprocessor 上 parallel
* 沒有 blocking system call 的問題
* 無限數量的使用者 threads
* 用戶可以創建盡可能多的 user threads
>
>使用者執行緒和核心執行緒的數量可能隨時間而變化。
>但無論有多少用戶線程, kernel thread的最大數量都限制為3。
##### **Two-level Model**
* 多對多的一種變體
* **many-to-many** + **one-to-one** models
* 雖然many-to-many 是最 flexible 的
1. 但很難 implement
2. 限制 kernel threads 的數量變得不再那麼重要
* 因為處理核心(processing core)數量不斷增加
3. 大部分 OS use one-to-one model
>
:::info
:earth_asia: **Summary：使用者Thread與核心Thread**
* **User thread** *(many-to-one model)*
>由**user-level threads library**完成執行緒管理
>快速建立和管理 => 因為是 **local function call** in user space
>阻止 **blocking system call** 的所有執行緒
>*無法*利用**多處理器(multi-processors)**
* Examples
>POSIX Pthreads
>Win32 threads
>Java threads
* **Kernel thread** *(one-to-one model)*
>由核心支援ㄉ
>創建和管理速度較慢 => 因為是 **system call**
>**沒有** blocking system call 的問題
>*可以*利用**多處理器 (multi-processor)** 環境
* Examples
>Windows
>Solaris
>Linux
:::
---
### Thread Library
* 提供用於**creating** and **managing** threads 的 ***APIs***
* Two approaches(兩種方法)
1. User-level thread
2. Kernel-level thread
* Three main thread libraries
1. POSIX Pthreads (Pthreads)
2. Win32 threads
3. Java threads
* Strategies for Creating Threads
* *Asynchronous(非同步) threading v.s. synchronous(同步) threading*
1. **Asynchronous(非同步) threading**
>創建 child thread 後, **parent thread 恢復(resumes)** 執行
>parent thread 和 child thread 同時運行
2. **Synchronous(同步) Threading**
>創建 child thread 後, parent thread **等待(waits)** 所有 children threads 終止
>Called **fork-join** strategy
>=> 1 & 2 是 child thread, 0 是 parent thread
>
#### Pthreads
* thread行為的規範(specification), 而不是實現(implementation)
* **API** 指定 thread **library** 的行為
* **Implementation** 取決於 library 的發展
* 常見於 **UNIX** 作業系統
* A Pthreads example
* thread 以 main() 開始
* main() 透過呼叫 **pthread_create()** 建立第二個 thread
* 兩個 thread 共享全域變數 *sum*
* 透過呼叫 **pthread_join()** 等待執行緒終止
---
### Implicit Threading
* 由於 multicore computers, 應用程式可能包含數百甚至數千個 threads
* 設計這樣一個 multi-threading 應用程式並不容易
* **Solutions:** implicit threading
* **執行緒的建立和管理**是由***編譯器***和***函式庫***完成的, 而不是程式設計師
#### OpenMP
* Define parallel regions
* 可以 parallel 運行的程式碼區塊
* 程式設計師只需插入 **compiler directives** 來識別 parallel regions
* 這些指令使 OpenMP **library parallel** 執行該區域
>
#### Grand Central Dispatch
* *蘋果的啦~* Apple technology for Mac OS X and iOS
* 允許**識別 parallel** 運行的 **section of code(tasks)**
>By defining **"block"**
>Like OpenMP
#### Intel **T**hread **B**uilding **B**locks **(TBB)**
* 用於設計平行 C++ 程式的函式庫
* EX：將陣列 v 中的每個值傳遞給 **apply()** 函數
>apply() 函數為每個輸入參數 +1
>
* **Method 1:** 簡單 for 迴圈的串列版本
* :-1:: 耗時, 無法利用多核心處理
* **Method 2:** uses TBB
* TBB提供了**parallel_for模板**
* TBB將循環迭代劃分為多個任務（工作）
* TBB創建許多執行緒來parallel運行這些任務
#### Fork Join
* 這裡所描述的 fork-join 模型是**明確的(explicit)**
* 例如, Pthreads、Windows 執行緒…
* 多個線程**被分叉(forked)**, 然後**連接(joined)**
* **fork-join 模型**也可以是**隱式的(implicit)**
> 呼叫fork不會產生對應的thread, 而是產生對應的tasks
> A library
> 對於 **recursive 分而治之(divide-and-conquer)** 演算法很有用
* **General algorithm(通用演算法)** for fork-join strategy
>* **Parallelism**
>
>---
>* 在 **fork** 階段建立 **tasks** 而**不是 threads**
>

***切***成4個任務由多個執行緒執行
#### Summary
* Implicit Threading
* 開發人員**只需要識別可以 parallel 運行的tasks**, 而不是執行緒
* **run-time library/compiler** 將任務maps到線程, 並確定thread的**創建**和**管理**
* :+1: :
>1. 開發人員只需要確定什麼 operations 可以 run in parallel
>2. library 管理細節
---
### Threading Issues
#### Thread Pools
* Consider 一個使用執行緒為 each request 提供服務的 Web 伺服器
* 動態建立和銷毀執行緒－**耗時(time consuming)**
* 無限數量的執行緒－**耗盡系統資源(exhaust system resources)**
* **Sol.: *Thread Pools***
* 預先在 pool **創建一定數量的 threads**
* 收到請求 :point_right: 從 **pool 中喚醒一個執行緒** :point_right: **將請求傳遞給 service**
* 一旦 thread **完成**其服務 :point_right: **return to the pool**
* if **沒有可用 thread** :point_right: 伺服器 **waits 直到有空閒(free)**
>1. 
>:point_down::point_down::point_down: **去pool抓threads來用**
>2. 
:::info
**Advantages** :+1:
* 更快地處理請求
>透過現有thread 而不是建立新thread
* 允許應用程式中的執行緒數與pool的大小綁定(bound)
:::
#### Semantics(語意) of fork() and exec() system calls
* **fork()** in a **multi-thread** application?
* If one thread calls ***fork()***
>複製所有 thread 或
>複製呼叫 fork() 的 thread
* How about **exec()**?
>如果執行緒調用 exec() 系統調用
>替換**整個(entire)** process —— **包括 all threads**
#### Signal handling(訊號處理)
* **Events** - 訊號在 UNIX 系統中用於通知process發生了事件
* Illegal memory access (非法記憶體訪問)
* Divided by zero… (除以零...)
* Ctrl-C to terminate a process (Ctrl-C 終止進程)
* Timer expires (定時器到期)
* 所有訊號都遵循**相同的模式(pattern)**
1. 訊號是由特定事件**產生(generated)** 的
2. 訊號**傳遞(delivered)** 給進程
3. 訊號由進程的**訊號處理程序(signal hander)**來**處理(handled)**
* 每個訊號由兩個 handlers 之一處理
* kernel 中的 **default signal handler**
* 使用者程式中 **user-defined signal handler**
* In **single-threaded** programs
* 訊號被傳遞到 process
* In a **multi-threaded** programs
* 將訊號傳送到**訊號應用(signal applies)** 的 thread.
>EX: 非法記憶體訪問, 除以零
* 將訊號傳遞給 process 中的**每個 thread**
>EX: Ctrl-C 非同步訊號
* 將訊號傳遞給 process 中的 **certain threads**
>pthread_kill( pthread_t tid, int signal)
* 分配一個 **specific thread** 來接收 process 的所有訊號
#### Thread cancellation
* 在 thread 完成之前終止該 thread
>EX: 使用多執行緒搜尋資料庫, 猜密碼
>**找到就 cancel, 猜到就 cancel**
* **Target thread:** 要取消的線程
* 取消的兩種方法:
1. Asynchronous cancellation(取消非同步)
* 立即終止target thread
* May have problems in **resource reclaim(資源回收)**
>target thread 正在**持有資源**
>target thread 正在**更新共享數據**
2. Deferred cancellation(延期取消)
* target thread **periodically** 檢查是否應該終止
* 允許 target thread 在 **safe point（cancellation point）** 自行終止
* **EX:** Pthread
* 預設類型是**延遲的(deferred)**
>收到取消請求後, 只有當執行緒到達 cancellation points 時才會發生取消
#### Thread-Local Storage
* 雖然屬於同一 process 的 threads **share** the data
>每個執行緒可能需要自己的某些資料副本
* Solution: **Thread-local Storage (TLS)**
>允許每個 thread 擁有自己的資料副本
* 與 local variables 不同
* Local variables 僅在關閉函數期間可見
* TLS 在函數呼叫中可見
* 類似於 **static** 數據
* TLS 對於每個執行緒來說是**唯一的（不共用）**
---
### Operating-System Examples
`Linux Threads`
* Linux 將它們稱為 tasks 而不是 threads
* 執行緒的創建是透過 clone() 系統呼叫完成的
* clone() 允許父子任務之間共享多少
* 如果設定了以上所有flags
* clone() **類似於創建 thread**
* 如果沒有給出任何flags
* **clone() 與 fork() 類似**
* A Sets of Flags to clone()
>
---
## CH5 CPU Scheduling
### Basic Concepts
#### CPU-I/O Burst Cycle
* Background
* **CPU–I/O Burst Cycle** – process 執行由 CPU 執行和 I/O **wait** 週期組成
>EX: CPU burst, I/O burst, CPU burst, I/O burst...(一直重複:leaves: )
* **CPU burst distribution** – 通常有大量的短 CPU bursts 和少量的長 CPU bursts
* **I/O bound:** 很多短 CPU bursts, 很少長 I/O bursts
>花在 I/O 上的時間 > 計算的時間
* **CPU-bound:** 很少長時間的 CPU burst
>花更多時間進行計算
#### CPU Scheduler
* ***Term Definition(術語定義)***
* **Process scheduler** (or CUP scheduler)
* 從準備執行的進程中選擇, 即**在 ready queue 中**
* **Degree of multiprogramming**
* 當前記憶體中的process數量
* ***Process scheduler 應滿足以下目標***
* **Objective of multi-programming**
* 讓一些 process 一直在運行, 以最大化 CPU 使用率
* **Objective of timesharing**
* process 之間的切換必須 frequent, 才能與各個程式進行交互
#### Preemptive and Nonpreemptive Scheduling
* 當 process 出現以下情況時, 可能會做出 **CPU scheduling decisions**：
1. Switches **from running to waiting** state
>e.g. perform **I/O** or **invoke wait()**
2. Switches **from running to ready** state
>e.g., when **quantum expires**
3. Switches **from waiting to ready** state
>e.g., at **completion of I/O**
4. Terminates
>**複習: Process State**
>
>
>---
>
>**複習: Process Scheduling**
>
* **Nonpreemptive v.s Preemptive**
* **Nonpreemptive** or **cooperative** scheduling
>當調度僅在 1 和 4 下進行時(上面那個數字)
>Process 保留 CPU 直到 releases CPU
>**對 time-sharing 系統不利**
* **Preemptive** scheduling
>在所有情況下都會進行調度（1 到 4）
>已經獲得CPU的 process 可能會 **be forced to** release CPU
>與 shared data 存取相關的成本 => process 可能會在 unsafe point 被搶佔
#### Dispatcher(分派器)
* 將***CPU控制權***交給短程排班器***選出process時所採用的的model***
* This involves:
* 將context從一個process切換到另一個process
* Switching to user mode
* 跳到user program中的正確位置以恢復(resume)該程式
* **Dispatch latency** – 調度程序**stop one process**並**start another running**運行所需的時間
* 應該盡可能快
* The Role of the Dispatcher
>
---
### Scheduling Criteria
* 用於判斷scheduling algorithm的效能
* **CPU utilization**
* 盡可能保持CPU繁忙
* **Throughput**
* 每個時間單位完成的process數
* **Turnaround time**
* 執行特定行程的時間量
* 從process提交到process終止
* **Waiting time**
* process在就緒佇列中等待的時間量
* **Response time**
* 從提交請求到產生response所花費的時間
* 對於interactive流程, 我們可能不關心turnaround time
---
### Scheduling Algorithms
#### **1. First-Come, First-Served(FCFS)** Scheduling
* Ready queue is a **FIFO queue**
* EX:
>**用Gantt Chart看:**
>Waiting time for **P1 = 0**; **P2 = 24**; **P3 = 27**
>Average waiting time: **(0 + 24 + 27)/3 = 17**
>
>
>***換一種順序, 平均花費的時間好多了***
>Waiting time for **P1 = 6**; **P2 = 0**; **P3 = 3**
>Average waiting time: **(6 + 0 + 3)/3 = 3**
>
* FCFS scheduling 是**不可搶先的(nonpreemptive)**
>**不適合分時系統(time-sharing systems)**
* **Convoy effect (護衛）:** 許多短process等待一個大process離開CPU
* 考慮一個 CPU-bound process 和多個 I/O-bound process
#### **2. Shortest-Job-First(SJF)** Scheduling
* 選擇 ***"下一個"*** 最小的CPU burst length
>**shortest-next-CPU-burst first algorithm**
* Two schemes:
* **nonpreemptive(不可搶先)**
>看到達時間排隊
>
* **preemptive(可搶先)**
>到達時間到的話可以搶先
>若新process到達時 CPU burst length 小於目前執行行程的**剩餘時間**,
>則搶先(preempt)目前行程, 也稱為**最短剩餘時間優先 (SRTF) 演算法**
>
* **Problem:** 如何實施？
* 不容易知道下一次CPU burst的長度
* **Sol.:** predict
>**Predict method:**
>使用previous CPU bursts的長度, 使用**exponential averaging**
>
* 預測下一次 CPU Burst 的長度
>
>1. **α = 0**: 最近的歷史不計算在內
>2. **α = 1**: 僅實際最後一次 CPU burst counts
#### 3. Round-Robin Scheduling
* 每個process獲得一小部分CPU時間
* 稱為**time quantum**或**time slice**
* 通常為 **10-100 毫秒**(milliseconds)
* 經過這個時間後, 進程**被搶先**並添加到就緒隊列的尾部
* **RR is preemptive(可搶先)**
* FCFS is non-preemptive
* **Question:**
* 作業系統如何知道time quantum已過期(expired)？
* => 定時器設定為time slice value
* EX: RR with **Time Quantum = 20**
>以20秒為界, 時間到了沒跑完就先丟到尾端乖乖排隊
>
* 平均週轉時間比 SJF 更長, 但better response
* Performance
>**time quantum 越大 => 越趨近 FCFS**
>**time quantum 必須夠大 => 以減少上下文切換開銷**
* **經驗法則(Rule of thumb):** 80% 的 CPU bursts 應該短於時間量
* Time Quantum 大的話, Context Switches 就小
>**`上下文切換不是免費的！`**
>
:::success
:dart: 複習: **Context Switch**
>
:::
:::info
:information_desk_person: **Turnaround Time Varies With The Time Quantum**
>q 取 80% 的區間才是最小的 Turnaround Time
>80% 是經驗法則
:::
#### 4. Priority Scheduling
* 每個process都有一個優先權編號（整數）
>CPU被指派給優先權最高的process
:::info
:face_palm: Problem: **starvation(飢餓)** or **indefinite blocking(無限期阻塞)**
低優先權process可能永遠不會執行 :point_down:
>有趣小故事:
>MIT, 有一項 1967 年提交的job在 1973 年 IBM 7094 系統關閉時都還沒運行XD:satisfied:

:ballot_box_with_check: Solution : **aging**
>隨著時間的推移, process的優先順序會增加
:::
>**Example of Priority Scheduling:**
>
#### 5. Multilevel Queue Scheduling
* **Questions:** 如果有兩個process有一樣的priority?
* **Sol.:** 結合 **RR** & **priority** scheduling
>運行具有最高優先權的process
>具有**相同優先權的process使用循環法(round-robin)**
:::info
:cactus: **Priority Scheduling & Round-Robin**
>**按照優先權執行, 如果優先權相同, 就用RR, 直到下一個優先權level~**
>
:::
* Question: 資料結構怎麼樣？
>如果是單一隊列, 每次需要O(n)搜尋
* sol.: 使用Multilevel queue代替
>
:::info
:wave: **A Two-Level Queue Scheduling**
>
:::
* 就緒佇列被劃分為***單獨的佇列***
* 行程被***永久***分配到一個佇列
* 每個隊列都有***自己的***調度演算法
* 調度必須在隊列***之間***進行
* **Fixed priority preemptive scheduling**
* Foreground隊列比background隊列有**絕對(absolute)優先權**
* 只有當Foreground隊列為空時, 才執行background隊列
* **Starvation** problem
* **Time-slice based**
* 每個佇列獲得一定量的CPU時間
#### 6. Multilevel Feedback-Queue Scheduling
* process可以在各個隊列之間移動
:::info
:bulb: **EX: 根據CPU bursts的特徵劃分process**
* Q0 – RR 時間量為 8 毫秒
* Q1 – RR 時間量 16 毫秒
* Q2 – FCFS
>**新作業**進入由 RR 提供服務的佇列 Q0
>當它獲得 CPU 時, 作業會收到 8 毫秒的時間
>如果未在 8 毫秒內完成, 作業將**移至佇列 Q1 的尾端**
>如果 Q0 為空, 則 Q1 由 RR 提供服務並額外接收 16 毫秒
>如果**仍未完成, 則被搶佔並移至佇列 Q2**
>
:::
* From above example:
* process使用過多 CPU 時間 => 移至較低優先權佇列
* 將 **I/O 綁定**和**交互**process留在較高優先權佇列中
* 在低優先權 Q 中等待太長時間 => 轉移到更高優先權佇列
* Aging
* It is the **most generic(最通用)** algorithm
* 可以配置以匹配特定系統
* It is the **most complex(最複雜)** algorithm
* 必須為每個參數選擇合適的值
---
### Thread Scheduling
* User threads由**thread library**管理和調度
* Kernel threads由**作業系統**管理和調度
* **Process-contention scope (PCS) - Process爭用範圍**
* Threads library調度用戶thread以放置到可用的kernel thread上
* 同一 process 的執行緒之間的競爭
* 當選擇user thread到kernel thread上
>並不意味著執行緒實際上在CPU上運行
* **System-contention scope (SCS) - 系統爭用範圍**
* 核心決定在CPU核心上運行哪個kernel thread
* 系統中所有kernel threads之間的競爭
---
### Multiple-Processor Scheduling
* 當多個CPU可用時CPU調度更加複雜
* Multi-processor可以是以下任一種架構:
* homogeneous(同質)
>Multicore CPUs(多核心CPU)
>Multithreaded cores(多執行緒核心)
>NUMA systems
* Heterogeneous multiprocessing(異構多處理)
#### Approaches to Multiple-Processor Scheduling
* **Asymmetric multiprocessing(非對稱多處理)**
:::success
:gem: **只有master processor處理調度演算法**
優點: 簡單
缺點: master成為瓶頸
:::
* **Symmetric Multiprocessing(SMP) - (對稱多處理)**
* 每個處理器做出***自己的***調度決策
* 標準方法 => **Windows、Linux、Mac OS** 採用
* SMP中就緒佇列的組織
>
* A common **ready queue**
* 需要某種形式的鎖定來protect the queue
* 訪問隊列是performance bottleneck
* 每個處理器都有其**private ready queue**
* Good
>不受protection overhead的影響
>允許更有效地使用**cache memory**
* Bad
>不同大小的工作負載**透過load balance解決**

`Most commonly used`
#### Multicore Processors
:::info
:bouquet: **Multicore processor:** 同一chip上的多個處理器核心
* Problem: **memory stall** (使動彈不得)
>等待數據可用
* Solution: **Chip-multithreading 晶片多執行緒 (CMT)**
>一個核心中有兩個或多個**hardware threads**
>如果一個硬體thread停止, core會切換到另一個硬體thread
>每個硬體執行緒對於作業系統來說都表現為一個**logical processor**
>Intel 處理器上的 **Hyper-threading**（也稱為 **simultaneously multithreading 或 SMT**）技術
:::
* A Dual-Threaded, Quad-Core System (雙執行緒、四核心系統)
>**作業系統的八個邏輯處理器**
>
* If **M-to-M or M-to-1 Model** (如果是多對多 或 多對一模式)
* 改為使用三級調度
**Level 1:** 選擇每個kernel thread上執行哪個使用者執行緒
=> Done by **thread library**
**Level 2:** 選擇在每個logical processor上執行哪個kernel thread
=> Done by the **OS**
**Level 3:** 指定每個core如何決定要執行哪個hardware thread
=> Done by the **hardware**
* If **One-to-One Model** (如果是一對一模型)
* 多執行緒多核心處理器中的兩級調度
**Level 1:** 選擇在每個logical processor上執行哪個軟體執行緒（kernel thread）
=> Done by the **OS**
**Level 2:** 指定每個core如何決定要執行哪個硬體thread
=> Done by the **hardware**
>
#### Load Balancing
* 讓工作負載 **均勻分布(evenly distributed)** 在所有處理器上
* 負載平衡是透過 **process migration(遷移)** 來完成的
* 僅在**private就緒佇列**系統上需要
>In common-ready-Q systems, the load is already balanced
#### Processor Affinity(處理器親和力/喜好)
* 當一個行程migrates到另一個處理器時
* *Old cache memory* 必須 **invalidated**
* 必須 **re-populated** *New cache memory*
* 大多數 SMP 系統避免處理程序從一個處理器遷移到另一個處理器
* **Processor affinity:** 保持process/thread在同一處理器上運行
* **Per-processor ready queues:** 免費提供處理器親和力！
* **A common ready queue:** 需要特殊處理
:::warning
:bell: **但負載平衡抵消了處理器親和力的好處**
* 負載平衡是**透過process遷移來完成**的
* 處理器親和力**盡量不要遷移process**
:::
#### Heterogeneous Multiprocessing(異構多重處理)
* 上述四個問題假設**homogeneous** multi-processors
* **Heterogeneous Multiprocessing(HMP)** - 異構多處理
* 某些系統是使用運行**相同指令集**的核心設計的，但其**clock speed**和**power management**各不相同
* 特別適用於mobile devices
* EX: ARM big.L ITTLE architecture
* **高效能big cores** & **節能LITTLE cores** 結合
:::success
:t-rex: **優點:**
* **CPU scheduler**
* 將效能要求不高, 但需要運行時間較長的任務分配給小核
* 將互動任務分配給大核心
* **Power management**
* 如果處於省電模式, 可以停用大核心, 系統僅依賴小核心
:::
---