OS & Concurrency Basics

What You Should Understand

• 能清楚區分 process 和 thread：各自擁有什麼、context switch 成本差多少
• 能區分 concurrency 和 parallelism，並根據 IO-bound vs CPU-bound 選擇正確工具
• 理解 Python GIL 的影響：為什麼 threads 加速不了純 Python 運算，但 numpy/pandas 仍能平行化
• 理解 memory hierarchy 與 cache locality — 為什麼 contiguous array 比 Python list 快一個數量級
• 知道 race condition、deadlock 是什麼，以及 lock 和 message-passing 如何避免
• 能把這些概念應用到實際 DS 工作：加速 scraping、特徵計算、DataLoader 調優、OOM 排查

Process vs Thread

A process is a running instance of a program with its own isolated virtual memory space. A thread is the smallest unit of execution scheduled by the OS — threads within a process share the same memory space but each has its own stack and registers.

直覺：process 像一間有獨立門牌的公寓（自己的記憶體、檔案、資源），thread 像同一間公寓裡的室友 — 共用客廳（heap、global variables），但各自有自己的房間（stack、program counter）。

Context switching 是 OS 暫停一個 task、儲存它的狀態（registers、program counter）、載入另一個 task 狀態的過程。Process 之間切換要換 page table、清掉 TLB 和部分 cache，成本是 microseconds 等級；thread 之間切換便宜很多，因為 address space 不變。

對 DS 的意義：

• 用 multiprocessing 開 8 個 processes 處理 DataFrame → 每個 process 要複製或序列化資料（pickle），因為記憶體不共享。傳一個 5GB DataFrame 給 worker，序列化成本可能比計算本身還貴。
• 用 threading 開 8 個 threads → 資料直接共享、零複製，但要小心 race condition，而且在 Python 裡受 GIL 限制（下面詳述）。

Concurrency vs Parallelism

The classic distinction (Rob Pike): concurrency is about dealing with many things at once; parallelism is about doing many things at once.

• Concurrency 是一種程式結構：多個 tasks 的生命週期重疊，在單核上靠快速切換（interleaving）交錯前進。任務在「等待」時（等網路回應、等磁碟）把 CPU 讓給別人。
• Parallelism 是一種執行方式：多個 tasks 真的同時在多個 CPU cores 上跑。

直覺：一個咖啡師輪流照顧三台咖啡機是 concurrency（一個人，交錯處理）；三個咖啡師各顧一台是 parallelism（真的同時做）。Concurrency 不需要多核，parallelism 需要。

選擇工具前先判斷 workload 類型：

判斷方法很實際：跑的時候看 htop — CPU 一核吃滿 100% 是 CPU-bound；CPU 幾乎閒著但程式很慢，多半是 IO-bound；記憶體逼近上限、開始 swap，是 memory-bound。

IO-bound 的任務用更多 CPU cores 沒有用 — 等待網路回應時 CPU 本來就是閒的，你需要的是「等待時去做別的事」（concurrency）。CPU-bound 的任務用 concurrency 沒有用 — CPU 已經滿載，切來切去只是增加 overhead，你需要更多 cores（parallelism）。

The Python GIL

The Global Interpreter Lock (GIL) is a mutex in CPython that allows only one thread to execute Python bytecode at any moment, even on a multi-core machine.

為什麼存在：CPython 的記憶體管理（reference counting）不是 thread-safe，GIL 用一把全域鎖保護整個 interpreter，簡化實作也讓單執行緒程式更快。代價是：多個 threads 無法同時執行 Python bytecode。

結果：

• CPU-bound 純 Python 程式：開 8 個 threads 不會變快，甚至因為 lock 競爭變慢。想用多核必須用 multiprocessing — 每個 process 有自己的 interpreter 和自己的 GIL。
• IO-bound 程式：threads 依然有效，因為 thread 在等待 IO 時會釋放 GIL，讓其他 thread 執行。
• numpy / pandas / PyTorch：許多重運算是 C/C++/Fortran 實作，進入 C 層時會主動釋放 GIL（例如 np.dot 呼叫多執行緒 BLAS）。所以 numpy 矩陣乘法本身就吃多核，即使你只寫單執行緒 Python。

三種併發工具的選擇：

經驗法則（面試可以直接背）：CPU-bound 用 multiprocessing（或先問自己能不能 vectorize）；IO-bound 少量併發用 threading；IO-bound 大量併發用 asyncio。

How Computer Memory Works

Memory is a hierarchy: each level trades capacity for speed. The CPU can only compute on data in registers; everything else is about moving data close to the CPU fast enough.

關鍵洞察：RAM 和 cache 之間差了兩個數量級，RAM 和磁碟之間差了三個數量級以上。 效能優化的本質常常不是「算得更快」，而是「讓資料待在更靠近 CPU 的地方」。

Cache Locality: Why numpy Beats Python Lists

CPU 從 RAM 讀資料時是以 cache line（64 bytes）為單位整批搬進 cache。如果你的資料在記憶體中是連續的，讀第一個元素時後面的元素會順便被載入 — 之後的存取都命中 cache（幾乎免費）。CPU 還會偵測連續存取模式並**預取（prefetch）**後續資料。

• numpy array：一塊連續的記憶體，每個元素是固定大小的 raw value（例如 8-byte float64）→ 完美的 cache locality + 可用 SIMD 向量指令一次算多個元素。
• Python list：儲存的是指標，每個指標指向散落在 heap 各處的 Python object（每個 float object 還帶著 type、refcount 等 24+ bytes 的 header）→ 每次存取都是一次 pointer chase，cache 幾乎無法發揮，也無法 SIMD。

這就是為什麼 np.sum(arr) 比 sum(list) 快 10–100 倍：不只是「C 比 Python 快」，更是記憶體佈局（contiguous vs pointer-chasing）的差異。同樣的邏輯解釋了為什麼 columnar formats（Parquet、Arrow）對分析查詢快 — 掃描單一欄位時資料完全連續。

Virtual Memory and OOM

每個 process 看到的是自己的虛擬位址空間，OS 透過 page table 把 virtual pages（通常 4 KB）對應到實體 RAM。這帶來 isolation（process 之間互不干擾）和超額配置的可能。

當實體 RAM 不夠時：

1. OS 把不常用的 pages 寫到磁碟（swap）→ 程式沒死，但存取 swap-out 的資料慢一萬倍，機器看起來像當機（thrashing）。
2. Swap 也滿了（或 container 有 memory limit）→ Linux 的 OOM killer 直接選一個吃記憶體最多的 process 殺掉 — 你的 training job 就這樣消失，log 只留下一行 Killed。

DS 常見的 OOM 場景：pd.read_csv 整份載入（pandas 常吃掉原始檔 2–5 倍的記憶體）、merge 產生意外的笛卡兒積、DataLoader 開太多 workers 每個都持有一份 dataset 副本、GPU OOM 則是 batch size 或 activation 太大。排查工具：htop、dmesg | grep -i oom（確認被 OOM killer 殺掉）、Kubernetes 的 OOMKilled status。

Concurrency Hazards

Race Conditions

A race condition occurs when multiple threads access shared state concurrently and the final result depends on the timing of their interleaving.

經典例子 — 兩個 threads 各對 counter 加一百萬次，結果卻小於兩百萬：

counter = 0

def increment():
    global counter
    for _ in range(1_000_000):
        counter += 1  # NOT atomic: read -> add -> write (3 steps)

# Two threads can both read counter=5, both write 6 -> one increment lost

counter += 1 看起來一行，實際是三步：讀值、加一、寫回。兩個 threads 可能同時讀到 5、各自加成 6、各自寫回 6 — 一次增量就此蒸發。這種 bug 最可怕的地方是不確定性：測試時可能一萬次都正常，production 高負載時才炸。

Locks (Mutex)

A lock (mutex) guarantees mutual exclusion: only one thread can hold the lock and enter the critical section at a time.

import threading

counter = 0
lock = threading.Lock()

def safe_increment():
    global counter
    for _ in range(1_000_000):
        with lock:            # acquire -> critical section -> release
            counter += 1      # now atomic with respect to other threads

代價：lock 讓 critical section 退化為序列執行（Amdahl's law 的現實版），而且引入新的風險 — deadlock。

Deadlock

A deadlock requires four conditions to hold simultaneously (Coffman conditions):

經典場景：thread 1 拿了 lock A 等 lock B，thread 2 拿了 lock B 等 lock A → 雙方永遠卡住。避免方法：（1）固定順序取鎖（破壞 circular wait — 最常用）；（2）用 timeout 取鎖，失敗就全部釋放重來；（3）一次取得所有需要的鎖；（4）根本上減少共享狀態。

Why Immutability and Message-Passing Help

Race condition 的根源是「共享且可變的狀態」。拿掉任何一個，問題就消失：

• Immutability：資料不可變就不可能被改壞 — 這是 functional programming 和 Spark RDD 設計的核心理由。
• Message-passing：process/actor 之間不共享記憶體，只透過 queue 傳訊息（"share memory by communicating"）— Python multiprocessing.Queue、Go channels、Kafka 都是這個哲學。
• Python 的 multiprocessing 順帶「免疫」大部分 race condition，因為記憶體本來就隔離 — 這是它相對 threading 的隱藏優點。

Async IO

asyncio achieves concurrency on a single thread with an event loop: coroutines voluntarily yield control at await points, and the loop switches to whichever task is ready to make progress.

直覺：一個超有效率的服務生（event loop）管理幾千桌客人（coroutines）。點完餐（發出 HTTP request）就去服務下一桌，餐好了（response 回來）再回來上菜。任何時刻只有一個服務生在動 — 但因為「等待」佔了每桌 99% 的時間，一個人就能服務幾千桌。

• Coroutine（async def）：可以在 await 處暫停與恢復的函式。暫停時完全不佔 CPU。
• Cooperative scheduling：切換點是明確的 await — 對比 threads 的 preemptive switching（OS 隨時可能切換）。好處是切換點可預測、race condition 更少；壞處是一個 coroutine 若執行長時間 CPU 運算不 await，會卡住整個 event loop。

對 DS 最實際的應用場景：批次呼叫 LLM API。一萬筆資料要標註、每個 request 來回 2 秒 — 序列跑要 5.5 小時，asyncio 開 50 個併發（配合 rate limit）大約 7 分鐘。

Applying This as a Data Scientist

把前面所有概念收斂成一張決策表：

Real-World Use Cases

Case 1: 大量呼叫 LLM API 做批次標註

你要用 GPT 類 API 幫 50,000 則客服對話標註情緒。每次呼叫來回約 1.5 秒，序列執行要 20 小時；API 有 rate limit（例如每分鐘 500 requests）。這是典型的 IO-bound + massive concurrency 問題 — 用 asyncio 加上 semaphore 控制併發數：

import asyncio
import httpx

MAX_CONCURRENCY = 50
semaphore = asyncio.Semaphore(MAX_CONCURRENCY)

async def label_one(client, text):
    async with semaphore:               # cap concurrent in-flight requests
        for attempt in range(3):        # simple retry with backoff
            try:
                resp = await client.post(API_URL, json={"input": text})
                return resp.json()["label"]
            except httpx.HTTPError:
                await asyncio.sleep(2 ** attempt)  # exponential backoff
        return None                     # give up after retries

async def label_all(texts):
    async with httpx.AsyncClient(timeout=30) as client:
        tasks = [label_one(client, t) for t in texts]
        return await asyncio.gather(*tasks)   # run concurrently

labels = asyncio.run(label_all(texts))

50 個併發下，20 小時縮到約 25 分鐘。Interview follow-ups：為什麼用 asyncio 不用 threads？（幾萬個 tasks，coroutine 記憶體成本遠低於 threads）Semaphore 在做什麼？（限制同時在途的 requests，尊重 rate limit、避免打爆對方）如果某些 requests 特別慢怎麼辦？（timeout + retry；用 asyncio.as_completed 先處理完成的）

Case 2: 特徵工程從單核 pandas 加速

你的 feature pipeline 對 2,000 萬列交易資料逐列計算特徵，df.apply(f, axis=1) 跑了 3 小時，htop 顯示只有一個 core 在 100%。診斷：CPU-bound，而且 apply 本質是 Python-level 迴圈（每列一次 interpreter 呼叫、無法用 cache locality）。加速的優先順序：

import numpy as np
import pandas as pd

# Step 1 (best): vectorize -- stays in C, uses contiguous memory + SIMD
df["ratio"] = df["amount"] / df["user_avg_amount"]
df["is_night"] = (df["hour"] < 6) | (df["hour"] >= 23)

# Step 2: if truly un-vectorizable, parallelize across processes
from multiprocessing import Pool

def process_chunk(chunk):
    return chunk.apply(complex_feature, axis=1)   # CPU-bound per chunk

chunks = np.array_split(df, 8)                     # one chunk per core
with Pool(processes=8) as pool:
    results = pool.map(process_chunk, chunks)      # data is pickled to workers
df["feature"] = pd.concat(results)

# Step 3: or switch engine -- Polars is multi-threaded Rust (no GIL issue)
import polars as pl
pl_df = pl.from_pandas(df)
pl_df = pl_df.with_columns((pl.col("amount") / pl.col("user_avg_amount")).alias("ratio"))

Vectorization 常直接快 50–100 倍，multiprocessing 大約再乘上核心數（扣掉 pickle 成本）。Interview follow-ups：為什麼不用 threading？（純 Python 的 apply 受 GIL 限制，threads 無法平行）為什麼 Polars 的 threads 可以平行而 pandas 不行？（Polars 核心是 Rust，運算在 GIL 之外執行）multiprocessing 的隱藏成本？（每個 chunk 要 pickle 傳給 worker，資料太大時序列化比計算貴）

Case 3: PyTorch DataLoader num_workers 調優與 OOM 排查

你在訓練影像模型，GPU 利用率只有 30%，一個 epoch 要 2 小時。診斷：GPU 在等資料 — 資料讀取和 augmentation（CPU 上的 decode、resize）跟不上 GPU 消化速度。DataLoader 的 num_workers 會 fork 出多個 worker processes 平行準備 batches：

from torch.utils.data import DataLoader

loader = DataLoader(
    dataset,
    batch_size=64,
    num_workers=8,       # 8 worker processes prefetch batches in parallel
    pin_memory=True,     # page-locked host memory -> faster CPU-to-GPU copy
    prefetch_factor=2,   # each worker keeps 2 batches ready
    persistent_workers=True,  # avoid re-forking workers every epoch
)

調到 num_workers=8 後 GPU 利用率升到 90%，epoch 縮到 45 分鐘 — 但機器突然被 OOM kill。原因：每個 worker 是獨立 process，如果 Dataset 物件在 __init__ 就把資料載進 RAM，8 個 workers 就是 8 份副本。解法：Dataset 只存路徑，在 __getitem__ 才 lazy load；或用 np.memmap / Arrow 讓 workers 共享唯讀資料。Interview follow-ups：為什麼 workers 是 processes 不是 threads？（augmentation 是 CPU-bound Python/PIL code，threads 會被 GIL 卡住）num_workers 越大越好嗎？（不是 — 超過 CPU cores 或 IO 頻寬後只增加 memory 和 context switch 成本）怎麼確認被 OOM killer 殺掉？（dmesg 找 oom-kill 記錄、Kubernetes 看 OOMKilled status）

Hands-on: OS & Concurrency in Python

Threading vs Multiprocessing on a CPU-bound Task

import time
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor

def cpu_task(n):
    # Pure-Python CPU-bound work: holds the GIL the whole time
    total = 0
    for i in range(n):
        total += i * i
    return total

N = 10_000_000
args = [N] * 4

# Threads: ~same as serial (GIL allows one thread to run bytecode at a time)
with ThreadPoolExecutor(max_workers=4) as ex:
    results = list(ex.map(cpu_task, args))

# Processes: ~4x speedup on 4 cores (each process has its own GIL)
with ProcessPoolExecutor(max_workers=4) as ex:
    results = list(ex.map(cpu_task, args))

asyncio.gather for Concurrent IO Calls

import asyncio

async def fetch(url):
    # Simulate a network call: while sleeping, the event loop runs other tasks
    await asyncio.sleep(1.0)          # stands in for an HTTP round trip
    return f"data from {url}"

async def main():
    urls = [f"https://api.example.com/item/{i}" for i in range(100)]
    # 100 coroutines run concurrently on ONE thread
    # total time ~1 second instead of ~100 seconds serial
    results = await asyncio.gather(*(fetch(u) for u in urls))
    return results

results = asyncio.run(main())

A Lock Preventing a Race Condition

import threading

counter = 0
lock = threading.Lock()

def unsafe_increment(n):
    global counter
    for _ in range(n):
        counter += 1          # read-modify-write: increments can be lost

def safe_increment(n):
    global counter
    for _ in range(n):
        with lock:            # mutual exclusion around the critical section
            counter += 1      # final result is now deterministic

threads = [threading.Thread(target=safe_increment, args=(1_000_000,))
           for _ in range(2)]
for t in threads:
    t.start()
for t in threads:
    t.join()
# counter == 2_000_000 with the lock; typically less without it

Memory-Mapped numpy Array

import numpy as np

# Create a 4GB array backed by a file, NOT resident in RAM
shape = (500_000_000,)
arr = np.memmap("features.dat", dtype=np.float64, mode="w+", shape=shape)
arr[:1000] = np.random.randn(1000)   # only touched pages are loaded
arr.flush()                          # write dirty pages back to disk

# Reopen read-only: multiple processes can share this with ZERO copies
# (the OS page cache backs all of them -- no pickle, no duplication)
shared = np.memmap("features.dat", dtype=np.float64, mode="r", shape=shape)
subset = shared[:1000].mean()        # OS pages in only what you access

Interview Signals

What interviewers listen for:

• 你能先診斷 bottleneck（IO / CPU / memory）再選工具，而不是反射性地「開平行」
• 你能精確描述 GIL 的影響範圍：擋住 CPU-bound Python threads，但 IO 和 C extensions（numpy/BLAS）不受限
• 你知道 multiprocessing 的隱藏成本是 pickle 序列化與記憶體副本，並能提出 shared memory / memmap / Arrow 等解法
• 你能用 memory hierarchy 和 cache locality 解釋 numpy 為什麼比 Python list 快，而不是只說「因為是 C」
• 你能講出 race condition 的成因（共享可變狀態 + 非原子操作）和 deadlock 的四個條件與破解法

Practice

Flashcards

Quiz