作業系統概論：行程與執行緒

當你打開電腦，同時瀏覽網頁、聽音樂、寫程式——你以為這些程式是「同時」在運作嗎？

其實，對單核心 CPU 來說，它一次只能做一件事。但它切換得非常快，讓你感覺像是同時進行。這就是 作業系統 (OS) 的核心工作之一：行程管理。

🔥 Vibe Prompt

「用 Python 模擬作業系統的行程排程：實作 FIFO、SJF、Round Robin 三種演算法，每個行程有 arrival time 和 burst time，輸出完整執行順序與等待時間統計。」

什麼是行程 (Process)？

行程就是一個正在執行的程式實例。當你雙擊 Chrome 圖示時，作業系統會：

將程式的程式碼從硬碟載入到記憶體
分配一個獨立的記憶體空間
建立一個「行程控制塊 (PCB)」來記錄它的狀態

每個行程擁有獨立的記憶體空間，彼此不會互相干擾。

import os
import time

print(f"目前行程 ID (PID): {os.getpid()}")
print(f"父行程 ID (PPID): {os.getppid()}")

行程 vs 執行緒 (Thread)

| 特性 | 行程 (Process) | 執行緒 (Thread) | |------|---------------|----------------| | 記憶體空間 | 獨立（隔離） | 共享同一行程的記憶體 | | 建立成本 | 高（需要完整複製空間） | 低（輕量級） | | 通訊方式 | IPC (pipe, socket) | 直接讀寫共享變數 | | 穩定性 | 一個掛了不影響其他 | 一個掛了可能整組崩潰 | | 使用場景 | 隔離性要求高的應用 | 需要高效率並行的任務 |

生活比喻

行程 = 不同的餐廳。每間餐廳有自己的廚房、食材、員工。一家餐廳火災不會影響隔壁。
執行緒 = 同一間餐廳裡的多個廚師。他們共用同一個廚房、食材庫存。協作效率高，但搞砸了會一起遭殃。

import threading
import time

shared_counter = 0
lock = threading.Lock()

def chef_task(chef_id):
    global shared_counter
    for _ in range(5):
        with lock:
            shared_counter += 1
            print(f"👨‍🍳 廚師 {chef_id} 做了第 {shared_counter} 道菜")
        time.sleep(0.1)

# 建立 3 個執行緒（廚師）
threads = []
for i in range(3):
    t = threading.Thread(target=chef_task, args=(i,))
    threads.append(t)
    t.start()

for t in threads:
    t.join()

print(f"\n✅ 總共完成 {shared_counter} 道菜")

CPU 排程演算法

當多個行程都在等待執行時，作業系統需要決定誰先誰後。這就是 CPU 排程。

1. FIFO (First In, First Out)

先來的先執行，非常公平，但短任務會被長任務阻塞。

def fifo_scheduling(processes):
    """
    FIFO 排程
    processes: [(name, arrival_time, burst_time), ...]
    """
    processes.sort(key=lambda p: p[1])  # 依照到達時間排序
    time = 0
    schedule = []
    
    for name, arrival, burst in processes:
        if time < arrival:
            time = arrival
        schedule.append((name, time, time + burst))
        time += burst
    
    return schedule

# 測試
processes = [
    ("P1", 0, 5),
    ("P2", 1, 3),
    ("P3", 2, 8),
    ("P4", 3, 2),
]

result = fifo_scheduling(processes)
for name, start, end in result:
    print(f"{name}: {start}~{end} (執行 {end-start}ms)")

2. SJF (Shortest Job First)

最短的任務先執行，能有效減少平均等待時間。

def sjf_scheduling(processes):
    """
    SJF 排程：最短作業優先
    """
    processes = sorted(processes, key=lambda p: p[1])  # 依 arrival time
    n = len(processes)
    completed = [False] * n
    time = 0
    schedule = []
    
    for _ in range(n):
        # 找出已到達且 burst time 最短的行程
        available = [(i, p) for i, p in enumerate(processes) 
                     if not completed[i] and p[1] <= time]
        if not available:
            time += 1
            continue
        
        idx = min(available, key=lambda x: x[0][2])[0]  # 最短 burst
        name, arrival, burst = processes[idx]
        schedule.append((name, time, time + burst))
        time += burst
        completed[idx] = True
    
    return schedule

result = sjf_scheduling(processes)
for name, start, end in result:
    print(f"{name}: {start}~{end} (執行 {end-start}ms)")

3. Round Robin (時間片輪轉)

每個行程輪流執行一個固定的「時間片 (time quantum)」。

def round_robin(processes, time_quantum=2):
    """
    Round Robin 排程
    """
    queue = []
    remaining = {p[0]: p[2] for p in processes}  # 剩餘執行時間
    arrival_map = {p[0]: p[1] for p in processes}
    
    time = 0
    schedule = []
    ready_queue = []
    
    # 初始載入已到達行程
    for p in processes:
        if p[1] <= time:
            ready_queue.append(p[0])
    
    while remaining:
        if not ready_queue:
            time += 1
            # 檢查新到達的行程
            for name, arrival, _ in processes:
                if arrival == time and name in remaining:
                    ready_queue.append(name)
            continue
        
        name = ready_queue.pop(0)
        execute = min(time_quantum, remaining[name])
        schedule.append((name, time, time + execute))
        time += execute
        remaining[name] -= execute
        
        if remaining[name] <= 0:
            del remaining[name]
        else:
            ready_queue.append(name)
        
        # 加入新到達的行程
        for p_name, arrival, _ in processes:
            if p_name in remaining and p_name not in ready_queue:
                start_time = schedule[-1][2]
                if start_time < arrival <= time:
                    ready_queue.append(p_name)
    
    return schedule

result = round_robin(processes, time_quantum=2)
for name, start, end in result:
    print(f"{name}: {start}~{end}")

行程狀態轉換

一個行程在生命週期中會經歷以下狀態：

New → Ready → Running → Terminated
           ↕          ↓
        Waiting  ←  I/O 或事件等待

New: 剛被建立
Ready: 準備好執行，等待 CPU 分配
Running: 正在 CPU 上執行
Waiting: 等待 I/O 或某個事件
Terminated: 執行完畢

上下文切換 (Context Switch)

當 CPU 從一個行程切換到另一個行程時，必須：

儲存目前行程的狀態（暫存器、程式計數器）
載入新行程的狀態

這個動作稱為 上下文切換。每次切換約需 1~100 µs，如果切換太頻繁，CPU 會花太多時間在切換而不是真正執行任務。

總結

| 概念 | 重點 | |------|------| | 行程 (Process) | 獨立記憶體空間，重量級，適合隔離性高的任務 | | 執行緒 (Thread) | 共享記憶體，輕量級，適合並行計算 | | FIFO | 先來先做，簡單但短任務可能被阻塞 | | SJF | 最短先做，平均等待最少，但可能造成飢餓 | | Round Robin | 輪流執行，互動性最好，時間片大小是關鍵 |

實戰練習

💡 Vibe Coding 練習：請 AI 幫你實作一個「互動式行程排程模擬器」，滿足以下需求：

使用者可以輸入多個行程的名稱、到達時間、執行時間

選擇 FIFO / SJF / Round Robin 三種演算法

輸出甘特圖 (Gantt Chart) 顯示執行順序

計算並比較平均等待時間與平均周轉時間

用 HTML + CSS 做一個漂亮的視覺化介面