1962 - 虛擬記憶體（Atlas 與位址空間的抽象化）#

案件摘要#

1962 年，Manchester 大學的 Tom Kilburn 團隊讓 Atlas 開機—— 第一台實現虛擬記憶體（virtual memory）與分頁（paging）的電腦：

\[ \text{虛擬位址（程式看到）} \xrightarrow{\text{MMU 轉換}} \text{實體位址（記憶體真正位置）}. \]

案件的核心是一個抽象化騙術：程式以為自己獨占整台機器的記憶體，其實只拿到幾個頁框。這個「善意的謊言」讓時間共享（time-sharing）與現代作業系統的記憶體管理成為可能—— 至今每台電腦（含你的手機）都在用。

前因 -- 為什麼會有這個案子#

實體記憶體的罩門（1950s）：
程式比記憶體大：早期做法是 overlay（覆蓋）——程式設計師手動把程式切段、依序載入同一塊記憶體：

\[ \text{程式大小} > \text{實體記憶體} \quad\Longrightarrow\quad \text{開發者的噩夢（手動 overlay）}. \]

多程式共用記憶體衝突：一次只跑一個程式（batch）太浪費—— CPU 在等磁帶時閒置。要多程式同時駐留，就得保護彼此的位址空間。
時間共享的需求（1960s 初）：MIT CTSS（1961）展示了分時的可能； 多程式輪流上 CPU 需要硬體支援的位址重定位與保護。
Ferranti 的前身：Atlas 由 Manchester + Ferranti 合作開發（Atlas 是 MUSE 計畫的產品）。
Kilburn 的偵探直覺：

「既然程式只需要『一個連續的位址空間』這個幻覺，何不讓硬體製造這個幻覺？」

線索與推理 -- 數學式、程式、理論#

第一條線索：分頁與位址轉換#

把虛擬位址空間切成固定大小的頁（page），實體記憶體切成頁框（page frame）：

\[ VA = (p, d) \quad\text{（p = 頁號，d = 頁內偏移）}. \]

頁表（page table）給出轉換：

\[ PA = PT[p] \times \text{page size} + d. \]

例：頁大小 4 KB（ \(2^{12}\) ），虛擬位址 \(VA = 0x2A3F\) ： \(p = VA >> 12 = 2\) ， \(d = VA \& 0xFFF = 0xA3F\) ；若 \(PT[2] = 7\) ，則 \(PA = 7 \times 4096 + 0xA3F = 0x7A3F\) 。
MMU（memory management unit）：硬體在每次記憶體存取時做這個轉換—— 程式完全感覺不到。
保護位元：頁表可標記 read-only、supervisor-only—— 行程隔離的硬體基礎。

第二條線索：Demand paging 與 page fault#

Atlas 的關鍵發明：不把整個程式載入，只載入正在用的頁（demand paging）： - 程式存取一個不在實體記憶體的頁 → 硬體觸發 page fault（缺頁中斷）。 - OS 的 trap handler 接手：從磁碟（Atlas 用磁鼓 drum）載入該頁，若記憶體滿了就置換（replace）一頁出去。 - 對程式透明：程式照跑，只是偶爾慢一下——

\[ F = \frac{\text{faults}}{\text{accesses}} \quad\text{（缺頁率：效能的生死線）}. \]

效能數學：記憶體存取 100 ns，磁碟存取 10 ms——缺頁代價是記憶體的 \(10^5\) 倍：

\[ T_{avg} = (1-F) \cdot 100\,\text{ns} + F \cdot 10^7\,\text{ns} \quad\Longrightarrow\quad F > 0.001\%\ \text{就會毀掉效能}. \]

第三條線索：置換演算法（FIFO、LRU、Clock、OPT）#

記憶體滿了，換誰出去？ - OPT（最佳置換，Belady 1966）：換「最久以後才會用到」的頁——理論上限，不可實現（需預知未來）。 - FIFO：換最先進來的頁——簡單但有 Belady 異常（頁框越多缺頁可能反而越多）。 - LRU（Least Recently Used）：換「最久沒用」的頁——根據局部性原理（locality）：

\[ \text{剛用過的頁，很快會再用} \quad\Longrightarrow\quad \text{LRU 近似 OPT}. \]

Clock（第二次機會）：LRU 的廉價近似（用 reference bit 環狀掃描）——實務首選。
Working set model（Denning 1968）：程式在時間窗 \(\Delta\) 內活躍的頁集合 \(W(t, \Delta)\) —— 只要每個行程的 working set 都在記憶體，缺頁率就低；這是多程式數量管理（thrashing 防治）的理論。

Python：位址轉換 + LRU/FIFO 置換模擬#

def translate(va, page_bits, pt):
    """虛擬位址 → 實體位址：VA = (p, d)"""
    p, d = va >> page_bits, va & ((1 << page_bits) - 1)
    if pt.get(p) is None: return None, p, d   # page fault
    return (pt[p] << page_bits) | d, p, d

def simulate(refs, frames, policy):
    """給定存取序列 refs 與頁框數 frames，回傳缺頁次數（policy: LRU/FIFO/OPT）"""
    mem, faults, age, arrive = [], 0, {}, {}
    for i, p in enumerate(refs):
        if p in mem:                                   # 命中
            age[p] = i; continue
        faults += 1                                    # page fault
        if len(mem) < frames:
            mem.append(p); arrive[p] = i
        else:                                          # 置換
            if policy == "FIFO": victim = min(mem, key=lambda q: arrive[q])
            elif policy == "LRU":  victim = min(mem, key=lambda q: age[q])
            else:  # OPT：換最久以後才用到的
                future = {q: (refs[i+1:].index(q) if q in refs[i+1:] else 10**9) for q in mem}
                victim = max(mem, key=lambda q: future[q])
            mem[mem.index(victim)] = p; arrive[p] = i
        age[p] = i
    return faults

# 1) 位址轉換：頁大小 4KB（page_bits=12）
pt = {2: 7, 5: 1}
for va in [0x2A3F, 0x5FFF, 0x9001]:
    pa, p, d = translate(va, 12, pt)
    print(f"VA=0x{va:X} → (p={p}, d=0x{d:X}) → PA={'PAGE FAULT' if pa is None else hex(pa)}")

# 2) 置換演算法比較（經典序列，3 個頁框）
refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
for policy in ["FIFO", "LRU", "OPT"]:
    f = simulate(refs, 3, policy)
    print(f"{policy}: 缺頁 {f} 次，缺頁率 {f/len(refs)*100:.0f}%")

輸出：

VA=0x2A3F → (p=2, d=0xA3F) → PA=0x7a3f
VA=0x5FFF → (p=5, d=0xFFF) → PA=0x1fff
VA=0x9001 → (p=9, d=0x1) → PAGE FAULT
FIFO: 缺頁 15 次，缺頁率 75%
LRU: 缺頁 12 次，缺頁率 60%
OPT: 缺頁 9 次，缺頁率 45%

（位址轉換 \(PA = PT[p] \cdot 2^{12} + d\) 如預期；LRU 優於 FIFO、逼近理論上限 OPT—— 局部性原理是虛擬記憶體可行的根本原因。）

第四條線索：TLB（translation lookaside buffer）#

頁表在記憶體裡——每次存取要多查一次表，位址轉換讓記憶體存取次數翻倍：

\[ \text{無 TLB：} 2\ \text{次存取/參考} \quad\Longrightarrow\quad \text{有效速度減半}. \]

解法（Atlas 首創，名為 "one-level store" 的 associativa）： TLB——快取最近的「虛擬頁 → 實體頁框」對應（全相聯、數十至數千項）。
命中率 99%+（局部性原理）→ 轉換的攤銷成本趨近於零。
現代 CPU：L1 TLB（數十項）+ L2 TLB（數千項）+ 多級頁表（x86-64 四級）。

結案 -- 後果與影響#

Atlas（1962）的發明清單：分頁、demand paging、one-level store（TLB 雛形）、 extracode（虛擬指令）、以及第一個現代化作業系統（ Atlas Supervisor，Spooling 先驅）。
時間共享的基礎：虛擬記憶體讓多個行程安全共存—— MIT Multics（1964–69）、Unix（1969）都建立在分頁之上。
程式的解放：程式設計師永遠告別手動 overlay——程式大小不再受限於實體記憶體。
swap 與記憶體階層：磁碟作為記憶體的延伸（swap space）—— 「記憶體不夠就 swap」至今仍是所有 OS 的標配。
商業化的延續：IBM System/370（1970）加入虛擬記憶體；x86 的 80286（1982）、 80386（1985，分頁）讓 PC 也有虛擬記憶體。
歷史定位：虛擬記憶體是 OS 與硬體最成功的抽象—— 位址空間、行程隔離、記憶體保護、mmap、容器與虛擬機（1974 Popek–Goldberg）全都是「位址空間抽象化」的後代。

關鍵人物與文獻#

T. Kilburn、D. Morris、J. Howarth 等：〈The Manchester University Atlas Operating System〉（1962）；Atlas 分頁設計。
P. Denning：working set model（1968）——thrashing 理論。
L. Belady：置換演算法與 Belady 異常（1966）。
F. Corbató：CTSS（1961）與 Multics——時間共享的先驅。
相關案件：1945-vonNeumann架構.md、1964-IBMSystem360.md、1969-Unix作業系統.md。