系統狀態：
  物理內存：8GB
  已分配：6GB
  空閒：2GB
  
啓動程序：
  需要內存：1.5GB
  
結果：
  分配失敗！
  
查看內存：
  空閒塊1：500MB
  空閒塊2：600MB
  空閒塊3：400MB
  空閒塊4：500MB
  
總空閒：2GB > 1.5GB ✓
但沒有連續的1.5GB塊 ❌

固定分區方案：
  分區1：1GB（分配給進程A，實際用500MB）
  分區2：1GB（分配給進程B，實際用800MB）
  分區3：1GB（分配給進程C，實際用900MB）
  分區4：1GB（空閒）
  
浪費空間：
  分區1浪費：500MB
  分區2浪費：200MB
  分區3浪費：100MB
  總浪費：800MB

連續分配方式：
  - 固定分區
  - 動態分區
  - 夥伴系統
  
非連續分配方式：
  - 分頁（已講）
  - 分段
  - 段頁式

內部碎片：
  |------ 分配的1GB ------|
  |已使用500MB|內部碎片500MB|
  
外部碎片：
  |進程A|外部碎片|進程B|外部碎片|進程C|
        ↑             ↑
     100MB         200MB
     分散，無法合併使用

停車場場景：

內部碎片：
  車位（分配單位）：5米
  汽車（實際需求）：4米
  浪費：1米（內部碎片）
  
外部碎片：
  |車1|空1米|車2|空0.5米|車3|
     ↑        ↑
  分散的空位，停不進新車（外部碎片）

方案1：分區大小相等
  |1MB|1MB|1MB|1MB|1MB|1MB|1MB|1MB|
  
  優點：簡單
  缺點：大進程裝不下，小進程浪費大
  
方案2：分區大小不等
  |512K|512K|1MB|1MB|2MB|2MB|4MB|
  
  優點：靈活
  缺點：仍有內部碎片

分區表：

| 分區號 | 起始地址 | 大小 | 狀態 | 進程號 |
|--------|---------|------|------|--------|
| 1      | 0x0000  | 512K | 空閒 | -      |
| 2      | 0x0800  | 512K | 已分配| P1    |
| 3      | 0x1000  | 1MB  | 空閒 | -      |
| 4      | 0x2000  | 2MB  | 已分配| P2    |

graph TB
    Start[進程請求內存] --> Size[檢查所需大小]
    
    Size --> Search[查找分區表]
    
    Search --> Find{找到合適空閒分區?}
    
    Find -->|是| Check{分區大小≥需求?}
    
    Check -->|是| Alloc[分配分區]
    Alloc --> Update[更新分區表]
    Update --> Success[分配成功]
    
    Check -->|否| Find
    
    Find -->|否| Fail[分配失敗]
    
    Success --> Frag[產生內部碎片]

例子：
  進程需求：700KB
  分配分區：1MB
  
內部碎片 = 1024KB - 700KB = 324KB
碎片率 = 324 / 1024 = 31.6%

初始狀態：
  |--------- 8GB空閒 ---------|
  
分配進程P1（1GB）：
  |-- P1(1GB) --|-- 7GB空閒 --|
  
分配進程P2（2GB）：
  |P1(1GB)|-- P2(2GB) --|5GB空閒|
  
分配進程P3（1.5GB）：
  |P1|P2|-- P3(1.5GB) --|3.5GB空閒|
  
釋放P2：
  |P1|-- 2GB空閒 --|P3|3.5GB空閒|
     ↑ 外部碎片產生

空閒分區表：

| 起始地址 | 大小 | 下一個 |
|---------|------|--------|
| 0x1000  | 2GB  | →      |
| 0x5000  | 3.5GB| NULL   |

原理：
  從頭開始查找，分配第一個足夠大的空閒塊
  
例子：
  空閒塊：[10MB, 5MB, 20MB, 15MB]
  需求：12MB
  
  掃描：
    10MB < 12MB ❌
    5MB < 12MB ❌
    20MB ≥ 12MB ✓ 分配這個
  
  結果：
    分配20MB中的12MB
    剩餘8MB加入空閒鏈表

原理：
  查找最接近需求的空閒塊（浪費最小）
  
例子：
  空閒塊：[10MB, 5MB, 20MB, 15MB]
  需求：12MB
  
  掃描所有：
    10MB：差2MB ❌
    5MB：差7MB ❌
    20MB：差8MB
    15MB：差3MB ← 最接近 ✓
  
  結果：
    分配15MB中的12MB
    剩餘3MB（小碎片）

原理：
  分配最大的空閒塊（剩餘塊儘量大）
  
例子：
  空閒塊：[10MB, 5MB, 20MB, 15MB]
  需求：12MB
  
  找最大：
    20MB ← 最大 ✓
  
  結果：
    分配20MB中的12MB
    剩餘8MB（較大，可再利用）

初始空閒塊：[20KB, 10KB, 30KB, 15KB]
請求序列：
  1. 分配12KB
  2. 分配10KB
  3. 釋放12KB
  4. 分配15KB
  
分別用首次適應、最佳適應、最壞適應，畫出每步狀態

緊湊前：
  |P1|碎片1|P2|碎片2|P3|碎片3|
  |2MB|1MB|3MB|2MB|1MB|3MB|
  
緊湊後：
  |P1|P2|P3|------ 空閒6MB ------|
  |2MB|3MB|1MB|

緊湊時機：
  1. 空閒碎片過多時
  2. 無法分配大塊時
  3. 系統空閒時

塊大小：
  1KB, 2KB, 4KB, 8KB, 16KB, ..., 512KB, 1MB
  
分配規則：
  1. 向上取整到2的冪
  2. 從對應大小鏈表取塊
  3. 如果沒有，從更大塊分裂
  
釋放規則：
  1. 釋放塊加入鏈表
  2. 檢查夥伴是否空閒
  3. 如果夥伴空閒，合併成大塊

夥伴判斷：
  兩個塊大小相同
  地址相鄰
  起始地址滿足：addr % (2 × size) == 0
  
例子：
  塊A：起始0x0000，大小64KB
  塊B：起始0x10000，大小64KB
  
  檢查：
    大小相同 ✓
    相鄰 ✓
    0x0000 % 128KB = 0 ✓
    → A和B是夥伴

初始：1MB空閒

請求70KB：
  向上取整：128KB
  
  分裂過程：
    1MB → 512KB + 512KB（分裂）
    512KB → 256KB + 256KB（分裂）
    256KB → 128KB + 128KB（分裂）
    分配：128KB
  
  結果：
    已分配：128KB（給進程）
    空閒：128KB, 256KB, 512KB

優點：
  ✓ 分配快（鏈表查找）
  ✓ 易於合併（夥伴檢查）
  ✓ 碎片較少
  
缺點：
  ✗ 有內部碎片（向上取整）
  ✗ 某些大小浪費大（如65KB→128KB）

必考題型：
  ✓ 內部碎片vs外部碎片
  ✓ 首次適應、最佳適應、最壞適應模擬
  ✓ 碎片率計算
  ✓ 夥伴系統分配過程
  ✓ 緊湊前後內存佈局

必記公式：
  ✓ 內部碎片 = 分配大小 - 實際需求
  ✓ 碎片率 = 碎片大小 / 分配大小
  ✓ 夥伴系統：向上取整到2的冪

必記要點：
  ✓ 內部碎片：分配塊內浪費
  ✓ 外部碎片：分配塊間分散
  ✓ 首次適應：快速，前端碎片多
  ✓ 最佳適應：省空間，產生小碎片
  ✓ 最壞適應：剩餘塊大，很少用
  ✓ 緊湊：移動進程，合併碎片
  ✓ 夥伴系統：塊大小為2^n

計算技巧：
  ✓ 畫表格模擬分配過程
  ✓ 標註每個空閒塊的大小
  ✓ 首次適應：從頭掃描
  ✓ 最佳適應：掃描全部，選最小夠用
  ✓ 最壞適應：掃描全部，選最大
  ✓ 夥伴系統：向上取整到2^n

典型考題：
  題：空閒塊[20KB, 10KB, 30KB]，請求序列12KB, 10KB, 15KB，
      用首次適應，畫出每步狀態
      
  答：
    初始：[20, 10, 30]
    分配12KB：[8, 10, 30]（從20KB分配）
    分配10KB：[8, 0, 30]（從10KB分配）
    分配15KB：[8, 0, 15]（從30KB分配）