本章節主要在探討電腦如何用硬體電路來執行加減乘除與浮點數運算，並延伸到「平行化算術加速」與錯誤處理。這一章的內容是從「數字如何表示」一路講到「怎麼加快算術運算效率」。 3-2 加法與減法 :::warning 本章節的整數皆使用 2's complement::: 加法：直接加起來就好image 減法：加上負數就是減法image Overflow：當計算結果超過儲存大小，就會產生 overflow Saturating Operation：當 overflow 產生時，只儲存最大的資料型態

:::warning 本筆記只有抄到 2-12，因為後面的出題機率過低就不寫了之後應該會補上 ::: 本章主要在讓讀者理解電腦真正能「聽懂」的是什麼語言——也就是機器指令（machine instructions），本章將從高階語言一路深入到底層的指令集結構。 2-1 Instruction Instruction set（指令集）：不同電腦有不同的指令集（但大部分相同） 早期電腦使用較簡單的指令集 MIPS 指令集

:::warning 前面廢話蠻多的，要考前衝刺的直接跳到 Permormance ::: 1-1 Introduction Moore's Law：每 1.5 年晶片上的電晶體密度會翻倍 會有極限：因為量子穿隧效應會限制電晶體所能達到的最大密度image 電腦的種類 Personal PC：目前最廣泛使用的電腦

本系列參考的資料來源為 《Computer Organization and design 5/e 亞洲版》（白算盤），章節分段也會以這本書為主。 以下是筆記連結： 章節 標題 連結 Ch1 Computer Abstraction and Technology

本系列參考的資料來源為 《台大資工 Algorithm Design and Analysis 2023年》 與 《Introduction to Algorithms 4/e》，章節分段主要參考《Introduction to Algorithms 4/e》 以下是筆記連結： 章節 標題 連結 Ch2 ~ Ch3 Intro

理論上在不外加任何限制時，大部分排序演算法都是是 $O(\log n)$；然而當我們加上一些限制後，排序時間可以縮段到線性時間 $O(n)$。本章要來介紹如何達到線性時間排序。 8-1 Lower Bounds for Sorting 比較型排序的下限是 $O(\log n)$e.g. Insertion sort, Quicksort, Heapsort... 無論如何優化都無法突破image 如果要達到線性時間，就不能只靠元素間的比較。 8-2 Counting Sort 限制：輸入的 key 必須是非負整數且範圍有限

本章主要介紹演算法設計與分析的過程，並介紹如 big-O, big-Omega 等表示 running time 的標記。 Intro :::warning 沒錯，Ch1 太廢了，懶得介紹 >_<::: 一般來說，演算法設計與分析大致可以分以下步驟： Formulate Problem：先定義好問題的 Input, Output

本章節要介紹的 Quicksort 是一種非常實用的演算法，也是現今大多數程式語言內建排序函式所採用的演算法。雖然最壞情形是 $\Theta (n^2)$，但平均來說它的表現非常優異，並且可以原地排序，是許多實際系統中排序的首選。 7-1 Description 基本流程：選定一個 pivot 分成 high side（通常在右邊） 與 low side（通常在左邊）比 pivot 小的元素放在 low side 比 pivot 大的元素放在 high side 之後在左右遞迴繼續 quicksortimage 7-2 Performance

本章節將利用 Heap 這個資料結構，來進行排序。 6-1 Heap Heap 是一種特殊的 binary tree，其中可以分為 Max heap 與 Min heap： Max heap：每個 node 的 value 都大於等於他的 child nodesimage Min heap：每個 node 的 value 都小於等於他的 child nodesimage 通常我們會用 array 來儲存 heap 的資料：image

分治法是透過將原問題分解成幾個規模較小、形式相同或相似的子問題，遞迴地解決各子問題，最後再將這些子問題的解合併，得到原問題的解。 基本步驟 所有分治法皆可拆分為三個步驟： Divide（分割）：把大規模問題分割成好幾個小問題 Conquer（征服）：對每個小問題遞迴求解 Combine（合併）：整合小問題的答案，形成原問題的答案 範例：矩陣乘法

這裡放了我作業系統的筆記，主要是參考王超上課筆記 + 課本內容。 以下是筆記的連結： 章節 標題 連結 Ch4 The Process

過去我們都假設 Virtual memory 一定可以放進 physical memory，但這不現實，因此我們引入了 swap space 的概念。透過與硬碟的互動，我們成功提升了 virtual memory 的大小 Swap space OS 預留硬碟裡的一部分作為 swap space，當 memory 不夠時可以交換 允許 OS 同時執行多個 process，如果 physical memory 不夠也能運作image Present bit 在每個 PTE 上面新增一個 present bit present bit = 1：Page 在 physical memory 中

當 memory page 太多的時候，page table 會佔用太多空間，因此我們需要一些輕量化的 page table。而 multi-level paging 可以有效處理我們的問題 Intro Page Directory：類似目錄，紀錄那哪些 page table 是存在的 關係：VPN --> Page tableimage 流程 把 VPN 分為 Page Directory Index 與 Page Table Index 用 PD Index 搜尋 Page directory 要用哪個 Page table 用 PT index 去查對應 PTE

本章的標題是 「Paging: Faster Translations (TLBs)」，重點在於如何使用 Translation Lookaside Buffers (TLBs) 來加速虛擬位址的轉換。 Intro 是一種存放在 CPU 中的 cache，用來記錄熱門的 PTE 資訊 目的：減少 fetch memory 的次數 fetch memory 的時間比在 CPU 內查詢慢很多 基本流程 尋找 TLB 是否有存到該 VPN 對應的 PFNTLB hit：直接轉換 TLB miss：查詢 Page table 並更新 TLB，重試指令

這一章是《Operating Systems: Three Easy Pieces》的第 18 章，主題是 Paging: Introduction（分頁：簡介），目的是介紹一種在現代作業系統中非常常見的 記憶體虛擬化方法。 Intro 早期使用 segmentation 把記憶體切成不同大小的 segment，容易產生 external fragmentation Paging：把記憶體切成固定大小的區塊Virtual memory -> pages Physical memory -> frames 好處： 防止 internal/external fragmentation

這一章（第16章）是在講作業系統中記憶體管理的一種方式：Segmentation（段式管理）。 以下是整章的重點與概念講解： 背景 傳統上來說，我們會把整個 virtual address space 搬到 physical address 中。產生以下問題： Virtual address space 中間有很多空白區域，會造成 internal fregmentation 如果 address space 很大，但實際用到很少，搬運的效率會很差

在前面提到 Virtual address space 的概念後，本章要講解一個很重要的觀念—address translation。它的核心主題是介紹如何在作業系統中虛擬化記憶體（memory virtualization），並且讓應用程式以為自己擁有一整塊連續的記憶體區域，實際上這背後靠的是作業系統和硬體的合作。 基本觀念 每個程式都是用 virtual address 然而實際上資料是存在 Physical Address 中 中間的 address translation 是由 MMU 完成的 MMU（Memory Management Unit） 用來進行 memory address translation 的硬體 功能：:::warning

這一章（第13章）主要介紹作業系統中非常核心的一個概念：虛擬記憶體（Virtual Memory），具體是透過地址空間（Address Space） 這個抽象概念來實現的。以下是章節的重點內容和邏輯脈絡： Address space 是什麼 OS 提供給每個執行 program 的記憶體視角 每個 program 都有自己的 Virtual address space 每個 Virtual address 都會對應到一個 physical address 結構 Code：存放程式碼 Heap：動態配置的記憶體

在第七章的 CPU scheduling 都符合四大公設，然而在現實，我們不會事先知道每個 process 的 execution time。在這兩章，我們會介紹其他 CPU scheduling。 Multi-level Feedback Queue（MLFQ） 目標：在不考慮 execution time 的情況下排程 結構：由多個 queue 組成，每個 queue 的 priority 不一樣 會先執行 priority 較高的 queueimage 基本原則： 當 Priority(A) = Priority(B)：對 A、B 做 RR（Round-robin）

在第六章，我們講解完 CPU virtualization 的基本機制了。在第七章，我們將要講解 CPU virtualization 的政策。因為我們有許多 process 要處理，但我們只有一個 CPU，如何制定 process 的執行方式是門學問，這也是本章的重點。 7-1 四大假設 在說明以下的各種排程策略前，我們必須介紹四大假設： 同時到達 不會中途停止 只使用CPU（無I/O） 執行時間已知 -> 很難成立