作業系統期中衝刺筆記

Operating System Concepts 10th ed. · 範圍 Ch1 ～ Ch5.2 · 標 🔥 考古的是歷屆期中考出現過的觀念

dual-mode ×3 年microkernel / LKM ×3 年IPC + producer-consumer ×3 年one-to-one model ×3 年fork() + pthread 輸出題bootstrap / clustered 填空

CH 1Introduction 導論

1.1 OS 是什麼

📌 定義 DEFINITION

Operating System 作業系統：介於使用者與硬體之間的程式，提供讓程式方便且有效率執行的環境。

resource allocator 資源分配者：管理 CPU、記憶體、I/O，處理資源爭用。
control program 控制程式：控制使用者程式的執行，避免錯誤或不當使用。
kernel 核心：「一直在電腦上執行的那個程式」，其餘是 system program 或 application program。

💡 例子 EXAMPLE

你在 Mac 上同時開 Safari 和 Spotify：OS 決定誰先用 CPU（resource allocator），並阻止 Safari 去改寫 Spotify 的記憶體（control program）。

1.2 OS 什麼時候會執行？（老師必講）

OS 平常是「睡著」的，只有在下列事件發生時才會拿到 CPU。這張表把 Ch1～Ch4 串起來：

#	時機	觸發來源	例子
(1)	system booting 開機	bootstrap program	按下電源，ROM 中的程式把 kernel 載入 RAM
(2)	interrupt 中斷	硬體（H/W）	鍵盤按鍵、磁碟讀完、timer 時間到
(3)	exception 例外（trap）	軟體錯誤	`a = 5/0;`、存取 NULL 指標
(4)	system call 系統呼叫	軟體主動請求	`fork()`、`read()`、`printf()` 底層的 `write()`
(5)	kernel thread	OS 自己的執行緒	Linux 開機時建立的 thread 負責管理裝置、記憶體

⚡ 重要觀念

Modern OS 是 interrupt-driven 中斷驅動：沒有事件時 OS 什麼都不做；事件幾乎都透過 interrupt 或 trap 通知 OS。

開機流程 Bootstrap 🔥 考古 2017、2019 填空

📌 定義

bootstrap program 開機程式：存在 ROM / EEPROM / flash 中的第一個程式，initializes all aspects of the system, loads OS kernel, starts executing the OS（這句就是考古填空題的原文）。

// 開機流程

電源開啟，CPU 執行 ROM 中的 bootstrap programRAM 斷電後是空的，只有 ROM 的內容還在
初始化系統檢查並初始化 CPU 暫存器、記憶體、裝置控制器
載入 kernel image 到 RAM找到 OS kernel，複製到主記憶體
開始執行 OS，啟動第一個 process例如 UNIX 的 init / Linux 的 systemd
等待事件（interrupt）之後 OS 只在 interrupt / trap 發生時才執行

中斷處理流程 Interrupt Handling

裝置送出 interrupt 訊號給 CPU例如磁碟控制器完成讀取
CPU 保存被中斷指令的位址與狀態這樣處理完才能回來繼續執行
查 interrupt vector 中斷向量表表中存著各種中斷對應的服務程式位址
跳到 ISR（interrupt service routine，中斷服務程式）執行此時處於 kernel mode
還原狀態，回到原程式繼續執行

🔗 關聯 DMA

DMA（Direct Memory Access，直接記憶體存取）：大量資料傳輸時，裝置控制器直接把整塊資料搬進記憶體，一整塊才發一次 interrupt，而不是每個 byte 都中斷 CPU。例：從 SSD 讀 1 GB 影片檔。

Interrupt vs Trap vs System Call 🔥 考古 2019 (15%)

比較	interrupt 中斷	trap / exception 例外	system call 系統呼叫
產生者	硬體（H/W）	軟體（執行中的程式）	軟體（使用者程式主動）
是否刻意	非同步，和目前指令無關	非刻意，因錯誤造成	刻意請求 OS 服務
本質	H/W interrupt	S/W-generated interrupt	一種 trap（被硬體當成 S/W interrupt）
例子	鍵盤輸入、I/O 完成、timer 到期	除以零、非法記憶體存取	`fork()`、`open()`、`read()`
OS 處理後	回原程式繼續	通常終止程式（或處理後繼續）	回傳結果給程式繼續

🔗 關聯與差異

trap 是大分類，system call 是「刻意的 trap」；exception（如 5/0）是「意外的 trap」。三者共同點：都會讓 CPU 從 user mode 切換到 kernel mode，交給 OS 處理。

1.4 Dual-Mode Operation 與 Timer 🔥 考古每年必考

📌 定義

dual-mode operation 雙模式運作：硬體加上一個 mode bit，區分目前執行的是 OS 還是使用者程式。

kernel mode（mode bit = 0）：又稱 supervisor / system / privileged mode，執行 OS 程式碼。
user mode（mode bit = 1）：執行使用者程式。

privileged instruction 特權指令：可能造成危害、只能在 kernel mode 執行的指令（切換到 kernel mode、I/O 控制、timer 管理、中斷管理）。在 user mode 執行會被硬體 trap 給 OS。

// system call 的 mode 切換（考試畫圖題）

user process 執行中（user mode，mode bit = 1）
呼叫 system call → 產生 trap硬體把 mode bit 設成 0，切到 kernel mode
OS 查 system call table，執行對應的服務程式在 kernel mode 下可以使用 privileged instruction
return from system callmode bit 設回 1，回到 user mode，程式繼續執行

📌 定義 Timer

timer 計時器：在指定時間後對 CPU 發出 interrupt，確保 OS 能拿回 CPU 控制權。OS 在把 CPU 交給程式前先設定 counter，每個 clock tick 遞減，歸零就產生 interrupt。設定 timer 是 privileged instruction。

⚡ 申論模板：為什麼需要硬體支援的 dual-mode？（用 trap、system call、timer 回答）

目的：保護 OS 不被出錯的使用者破壞，也保護使用者彼此不互相破壞（protecting the OS from errant users, and errant users from one another）。
trap：程式做出非法動作（5/0、亂寫別人的記憶體、在 user mode 執行 privileged instruction）→ 硬體 trap 到 kernel mode，由 OS 處理（通常終止程式），錯誤不會擴散到 OS 和其他程式。
system call：使用者程式不能直接做 I/O 這類特權動作，只能透過 system call「請」OS 代做，OS 在 kernel mode 先檢查請求是否合法再執行 → 存取受控管。
timer interrupt：程式陷入 while(1){} 也不會霸佔 CPU；時間到 timer 中斷讓 OS 拿回控制權。而「修改 timer」是 privileged instruction，使用者程式無法關掉它。
結論：只有 mode bit 由硬體維護，軟體才無法自行提權；若沒有硬體支援，任何程式都能執行特權指令，保護機制就形同虛設。

💡 例子

老師投影片的 4 個 Program Misbehavior：a=5/0（除零 exception）、b=(char*)0; b[10]='A'（寫入 NULL 附近，記憶體違規）、malloc(10) 卻寫 b[10000]（越界，可能 segmentation fault）、while(1){}（無窮迴圈 → 靠 timer 解決，不會產生 exception）。

🔗 延伸 Multimode

現代 CPU 不只兩種模式：Intel 64 有 4 個 protection rings；支援虛擬化的 CPU 另有 VMM mode，給 virtual machine manager 使用，權限介於 user 與 kernel 之間。

Multiprogramming vs Multitasking 🔥 考古填空＋畫圖

比較	single tasking	multiprogramming 多元程式	multitasking / time-sharing 分時
記憶體中的程式數	1 個	多個 process 同時在記憶體	多個
何時切換	不切換，跑完才換	目前 process 需要等待（如 I/O）時才切換	time slice 用完就切換，切換非常頻繁
目標	—	提高 CPU utilization	縮短 response time，讓使用者能互動
需要的 OS 功能	—	memory management、CPU scheduling、concurrency control	再加上 virtual memory、file system、protection、synchronization、deadlock 處理

🔗 關聯

Multitasking 是 multiprogramming 的邏輯延伸：multiprogramming 只在「等待」時切換；time-sharing 則把時間切成 time slice，強制輪流，快速切換製造「多個程式同時執行」的錯覺。

💡 例子

multiprogramming：程式 A 讀磁碟時，CPU 改跑程式 B（不讓 CPU 閒著）。time-sharing：你一邊打字一邊聽音樂，每個程式每次只跑幾毫秒就換下一個，感覺所有程式都在跑。

1.3 Computer-System Architecture 🔥 考古填空

📌 定義

multiprocessor system：兩顆以上處理器，共用 bus、有時共用 clock、memory、周邊。主要優點是 increased throughput。

clustered system 叢集系統：composed of two or more individual systems or nodes joined together（考古原句），通常用來提供 high availability（高可用性）或 high-performance computing。

術語	中文	重點	例子
SMP symmetric multiprocessing	對稱多處理	所有處理器地位平等（peers），沒有 boss-worker 關係，每顆都能執行所有工作含 OS 功能	Windows、macOS、Linux 都支援
asymmetric multiprocessing	非對稱多處理	每顆處理器負責特定工作，有 boss processor 分派工作給 worker	早期大型主機
multicore	多核心	多個 core 在同一晶片，較省電、晶片內通訊較快，OS 看成 N 顆處理器	M2 晶片 8 核心
UMA	均勻記憶體存取	任一 CPU 存取任一 RAM 時間相同	一般小型 SMP
NUMA	非均勻記憶體存取	CPU 存取「自己附近」的記憶體較快，存取遠端較慢	多插槽伺服器
asymmetric clustering	非對稱叢集	一台跑應用，另一台 hot standby 只監控，主機掛了才接手	銀行備援主機
symmetric clustering	對稱叢集	多台都在跑應用，同時互相監控	web server cluster

📌 相關名詞

graceful degradation 優雅降級：服務能力隨存活硬體的比例下降，而不是整個停擺。
fault-tolerant system 容錯系統：can suffer a failure of any single component and still continue operation（2017 填空原句），例：HP NonStop 用硬體與軟體雙重複製。

⚠ 易混淆

multiprocessor 是一台電腦裡多顆 CPU；clustered 是多台電腦（nodes）透過 LAN 或 InfiniBand 連起來，通常透過 SAN 共用儲存空間。

1.7 Virtualization 與 1.10 Computing Environments

術語	說明	例子
virtualization 虛擬化	把一台電腦的硬體抽象化成多個執行環境（VM），每個 VM 跑自己的 OS	Mac 上跑 Windows
VMM / hypervisor	管理 VM 的軟體	—
Type 1 hypervisor	直接跑在硬體上	VMware ESXi、Xen
Type 2 hypervisor	跑在 host OS 上的應用程式 🔥 2017 填空	VirtualBox、VMware Workstation、Parallels
real-time system 即時系統	functions correctly only if it returns the correct result within its time constraints（2019 填空原句）	hard：汽車煞車、心律調節器；soft：串流影音
embedded system 嵌入式系統	combination of computer hardware and software, and perhaps additional mechanical or other parts, designed to perform specific tasks（考古原句）	微波爐、洗衣機、汽車引擎控制
distributed system	多台實體分離、透過網路連接的電腦	Google 搜尋後端
cloud computing	SaaS / PaaS / IaaS，透過網路提供運算、儲存	Gmail（SaaS）、AWS EC2（IaaS）

🔗 關聯

embedded system 大多有 real-time 需求（例如 ABS 煞車要在幾毫秒內反應），所以兩者常一起出現；但 real-time 不一定是 embedded（例如股票交易系統）。

CH 2Operating-System Structures 作業系統結構

2.1–2.2 OS Services 與 User Interface

📌 定義

OS 提供的服務：user interface、program execution、I/O operations、file-system manipulation、communications、error detection（對使用者有用）；resource allocation、logging、protection and security（讓系統有效率運作）。

command interpreter / shell 命令直譯器：讀取使用者輸入的指令並執行。🔥 近年填空

介面	說明	例子
CLI command-line interface	文字指令，功能強、可寫 script 自動化	macOS Terminal 的 zsh、bash
GUI graphical user interface	視窗、圖示、滑鼠操作（desktop metaphor）	macOS Aqua、Windows 桌面
touch-screen interface	手勢操作	iPhone、iPad

2.3 System Calls 系統呼叫

📌 定義

system call：提供使用者程式請 OS 代為執行 OS 工作的管道，是 OS 服務的程式介面。通常以 trap 的形式，跳到 interrupt vector 中特定位置。

API（Application Programming Interface）：程式設計師實際呼叫的函式（如 POSIX API、Windows API、Java API），API 內部再去呼叫 system call。

// printf("hi") 背後發生什麼事

程式呼叫 C 函式庫的 printf()API，仍在 user mode
C library 呼叫 write() system call把 system call 編號放進暫存器
執行 trap（或 syscall）指令 → 切到 kernel modemode bit 0
system call interface 依編號查表，呼叫 kernel 中的 write 實作把資料送到螢幕的 device driver
回傳狀態值，return 回 user modeprintf 回傳，程式繼續

🔗 API vs System call

為何不直接呼叫 system call？可攜性（portability）：同一份用 POSIX API 寫的程式可以在任何支援 POSIX 的系統編譯；另外 system call 細節比較複雜，API 比較好用。一個 API 不一定對應一個 system call（例如 abs() 根本不需要 system call）。

傳遞參數的 3 種方法

方法	做法	優缺點
registers	直接放在 CPU 暫存器	最快，但暫存器數量有限
block / table	參數存在記憶體中的一塊區域，把位址放進暫存器	參數個數不受限（Linux、Solaris 使用）
stack	程式 push 到 stack，OS pop 出來	參數個數不受限

System call 6 大類

類別	UNIX 例子	Windows 例子
Process control 行程控制	`fork()` `exit()` `wait()`	`CreateProcess()` `ExitProcess()`
File management 檔案管理	`open()` `read()` `write()` `close()`	`CreateFile()` `ReadFile()`
Device management 裝置管理	`ioctl()`	`SetConsoleMode()`
Information maintenance 資訊維護	`getpid()` `alarm()` `sleep()`	`GetCurrentProcessID()`
Communications 通訊	`pipe()` `shm_open()` `mmap()`	`CreatePipe()`
Protection 保護	`chmod()` `chown()`	`SetFileSecurity()`

2.5 Linkers & Loaders、2.7 設計原則

compiler 把 source code 編譯成 relocatable object filemain.c → main.o
linker 把多個 object file 與函式庫合併成 executablemain.o + libc → a.out
loader 把 executable 載入記憶體在 shell 輸入 ./a.out 時，shell 用 fork() + exec() 叫 loader 載入
dynamically linked library（DLL / .so）在執行時才載入多個程式共用同一份函式庫

📌 Mechanism vs Policy

mechanism 機制決定「怎麼做」；policy 政策決定「做什麼」。兩者分開，改 policy 時不用改 mechanism，彈性較高。

💡 例子

timer 能中斷 CPU 是 mechanism；「每個使用者能用 CPU 多久」是 policy。Linux 的排程器提供機制，「I/O-bound 程式優先」則是政策。

2.6 為什麼 app 綁定 OS？因為每個 OS 的 system call、執行檔格式（ELF vs PE）、ABI 都不同。

2.8 OS Structure 結構 🔥 考古 2017、2019、近年必考

結構	核心概念	例子
monolithic 單體式	所有功能放在同一個 kernel address space；OS is written as a collection of procedures, each of which can call any of the other ones whenever it needs to（填空原句）	傳統 UNIX、Linux
layered 分層式	OS 切成多層，最底層是硬體、最上層是 UI，每層只使用下一層的服務	THE OS；網路的 TCP/IP 概念類似
microkernel 微核心	只把最必要的功能留在 kernel（process / memory 管理、IPC），其他服務搬到 user space，用 message passing 溝通	Mach、QNX、Darwin（部分）
LKM loadable kernel modules	kernel 只有核心元件，其他服務以 module 形式在開機時或執行中動態載入	Linux 驅動程式（`insmod`/`rmmod`）、Solaris
hybrid 混合式	結合多種結構，兼顧效能、安全、可用性	Windows、macOS（Darwin = Mach + BSD）、Android

user mode

Application

File System

Device Driver

⇅ messages（透過 microkernel 轉送）⇅

kernel mode

IPC

memory mgmt

CPU scheduling

hardware

Microkernel 架構（Fig 2.15，考試畫圖題）

user mode

Applications / shell / libraries

⇅ system-call interface ⇅

kernel mode

file system · CPU scheduling · memory mgmt · device drivers · IPC …
（全部在同一個 kernel，彼此直接呼叫）

hardware

Monolithic 架構

三大比較：extensibility、performance、security 🔥 2019 (12%)

面向	monolithic	microkernel	LKM
extensibility 擴充性	低：新增功能要改 kernel、重新編譯、重開機	高：新增服務只要加一個 user-space 程式，kernel 不用改	高：module 可單獨編譯，執行中載入/卸載，不用重開機
performance 效能	高：函式直接呼叫，沒有額外負擔	低：服務間要靠 message passing，需多次 user↔kernel 切換與訊息複製	高：module 在 kernel space，不需要 message passing，直接呼叫
security / reliability 安全可靠	低：任一部分出錯可能讓整個 kernel crash	高：大部分服務以 user process 執行，某服務掛掉不會拖垮 kernel	中低：module 跑在 kernel mode，有 bug 或惡意的 module 會危害整個系統

⚡ 一句話記憶

LKM 結合了 monolithic 的效能與 microkernel 的彈性（「while maintaining the performance benefits of a monolithic system」），但安全性不如 microkernel。投影片：LKM「Like the microkernel approach but is more efficient」、「similar to a layered system but more flexible（any module can call any other module）」。

💡 例子

插上新的 USB 網卡：Linux 用 insmod 載入驅動 module，不用重開機。Windows NT 早期是 layered microkernel，因效能太差，NT 4.0 把很多層搬回 kernel space，到 XP 已經比較接近 monolithic，這就是 microkernel 效能問題的真實案例。

⚠ 歷屆作答卷常見失分

寫「microkernel 把常用功能放在 kernel mode 節省時間」→ 被扣分：microkernel 是把功能移出 kernel，目的不是省時間。
寫「monolithic 一個出錯整個 process 暫停」→ 被扣分：應該是整個 kernel／整個系統受影響。
寫 LKM 優點只寫「速度快」而沒寫原因 → 要寫出「不需 message passing」。

2.9 Building & Booting、2.10 Debugging

BIOS 或 UEFI 韌體執行BIOS 舊式、多階段；UEFI 較新，單一完整的 boot manager，速度較快
載入 boot loader（如 GRUB）顯示開機選單，可選擇要開的 kernel
載入壓縮過的 kernel image 並解壓縮Linux 的 vmlinuz
掛載暫時的 root file system（initramfs）
切換到真正的 root file system，啟動 systemd第一個 process，之後啟動其他服務

Debugging：core dump（process 當掉時的記憶體快照）、crash dump（kernel 當掉）、performance tuning 工具（top、ps）、tracing 工具（strace、BCC/eBPF）。

CH 3Processes 行程

3.1 Process 概念與 Memory Layout 🔥 2019 (4%)

📌 定義

process 行程：a program in execution，執行中的程式，是 OS 的工作單位。

program 是存在磁碟上的被動實體（executable file）；process 是主動實體，有 program counter 和一組資源。程式被載入記憶體後才變成 process。

stack ↓

高位址。函式呼叫時的暫存資料：local variables、參數、return address。往下長

（free）

stack 與 heap 中間的空間，兩者往中間成長

heap ↑

執行時動態配置：malloc()、new。往上長

data

global / static variables，例：int value = 1;

text

低位址。executable code（程式碼）

Memory layout of a process（Fig 3.1）

💡 例子

同時開兩個 Chrome 視窗＝兩個 process，text section 相同（同一份程式碼），但 data、heap、stack 各自不同。JVM 本身是一個 process，用來解譯執行 Java 程式。

Process State 與 PCB

Process State Diagram（Fig 3.2）

狀態	中文	意義	例子
new	新建	正在建立	剛呼叫 `fork()`
ready	就緒	在 ready queue 等 CPU	一切準備好，只差 CPU
running	執行	指令正在 CPU 上執行	正在計算
waiting	等待	等某事件（I/O 完成、收到 signal）	呼叫 `scanf()` 等使用者輸入
terminated	結束	執行完畢	呼叫 `exit()`

⚠ 易錯

waiting 結束後是回到 ready，不是直接回 running，因為 CPU 可能正被別人使用，要重新排隊。running → ready 是因為 interrupt（例如 time slice 用完）。

📌 定義 PCB

PCB（Process Control Block，行程控制區塊，也叫 task control block）：OS 用來代表一個 process 的資料結構，存放：

process state、program counter（下一個要執行的指令位址）、CPU registers
CPU-scheduling information（priority、queue 指標）、memory-management information（base/limit register、page table）
accounting information（CPU 用量、PID）、I/O status information（已開啟檔案、分配到的裝置）

Linux 中 PCB 是 C 結構 task_struct。支援 thread 的系統，PCB 會擴充成存放每個 thread 的資訊（多個 PC）。

3.2 Process Scheduling 與 Context Switch 🔥 2017 填空、2019 (8%)

名詞	說明
ready queue	已在記憶體、準備好等 CPU 的 process 排隊處（通常是 linked list，串 PCB）
wait queue	等待某事件（如 I/O 完成）的 process 排隊處，不同事件有不同 queue
CPU scheduler	從 ready queue 選一個 process 給 CPU core，執行非常頻繁（至少每 100 ms 一次），必須很快
swapping	中期排程：記憶體不夠時把 process 換出到磁碟（swap out），之後再換回（swap in），降低 degree of multiprogramming

📌 定義

context 行程的上下文：存在 PCB 裡的 process 狀態，包括 CPU registers 的值、process state、memory-management information。

context switch 內文切換：save the state of the old process and load the saved state of the new process（2017 填空原句）。

// Context switch 的步驟（P0 → P1）

P0 執行中，發生 interrupt 或 system callCPU 進入 kernel mode，OS 取得控制權
把 P0 的 context 存進 PCB0program counter、registers、state 等
更新 P0 狀態並放入對應 queueready queue（time slice 用完）或 wait queue（等 I/O）
CPU scheduler 從 ready queue 選出 P1
從 PCB1 載入 P1 的 context還原 registers、切換 memory-management 資訊（page table）
切回 user mode，跳到 P1 的 PC 繼續執行P0 此時處於 idle

⚡ 重要觀念

Context-switch time 是 pure overhead（純粹的額外負擔），切換期間系統沒做任何有用的事，一般需要幾 microseconds，速度高度依賴硬體支援（例如有些 CPU 提供多組暫存器，切換只要改指標）。

3.3 Operations on Processes：fork()、exec()、wait()

📌 定義

fork()：建立新的 child process，child 是 parent address space 的複本。回傳值：child 拿到 0，parent 拿到 child 的 PID，失敗回傳負值。
exec()（如 execlp()）：用新的程式取代目前 process 的記憶體內容，成功就不會返回。
wait()：parent 等待 child 結束。
exit()：結束 process，資源歸還 OS。

// Shell 執行一個指令（老師投影片的 shell 範例）

shell 讀取指令，例如 ls
呼叫 fork() 複製出 child兩個 process 從 fork() 之後的下一行繼續跑
child（pid == 0）呼叫 execlp("ls", ...)child 的記憶體被換成 ls 程式
parent（pid > 0）呼叫 wait()等 child 執行完
child 執行完 exit()，parent 從 wait 返回shell 印出下一個提示字元

⚡ fork() 輸出題必背規則

fork 之後 parent 和 child 有各自獨立的變數複本，child 改 value 不會影響 parent。
fork 之前的程式只執行一次；fork 之後、if 判斷之外的程式兩邊都會執行。
parent 有 wait(NULL) → child 的輸出一定先印完。
同一 process 內的 thread 共享 global 變數（見 Ch4）。

名詞	說明	例子
zombie 殭屍行程	child 已結束，但 parent 還沒呼叫 wait()，PCB 還留在 process table	parent 忘了 wait，`ps` 看到 <defunct>
orphan 孤兒行程	parent 沒 wait 就先結束，child 還在跑	Linux 會把它交給 `init/systemd` 收養
cascading termination	parent 結束時，OS 連同所有 child 一起終止	部分系統不允許 orphan

3.4 IPC：Shared Memory vs Message Passing 🔥 每年必考

📌 定義

cooperating process 合作行程：會影響其他 process 或被影響的 process。合作的理由：information sharing、computation speedup、modularity。

IPC（Interprocess Communication，行程間通訊）：讓 cooperating processes 交換資料的機制，兩種基本模型：

shared memory：建立一塊共用記憶體區域，雙方直接讀寫該區域。
message passing：透過 OS 提供的 send() / receive() 交換訊息。

Communications models（Fig 3.11，考試必畫）

比較	shared memory	message passing
速度	快：建立好之後就是一般記憶體存取，不需 kernel 介入	較慢：每次 send/receive 都是 system call，需要 kernel intervention
kernel 參與	只有建立（`shm_open`、attach）時需要 system call	每則訊息都要
同步與保護	由程式設計師自行負責，要避免同時寫入同一位置（protection and synchronization are needed）	OS 處理，不會有寫入衝突（no conflicts need be avoided）
適合資料量	大量資料	少量資料
分散式環境	難：雙方要能存取同一塊記憶體	容易：適合不同電腦間通訊
例子	POSIX `shm_open()` + `mmap()`	Mach message、聊天程式、socket

🔗 關聯 microkernel

microkernel 的各服務之間就是用 message passing 溝通，所以 message passing「較慢」的缺點，正是 microkernel 效能差的原因。兩題常常連在一起考。

Producer-Consumer Problem 🔥 2017、2019、近年

📌 定義

producer-consumer problem 生產者–消費者問題：cooperating processes 的典型範例。producer 產生資料放進 buffer，consumer 從 buffer 取出使用。必須同步：buffer 滿時 producer 不能放，buffer 空時 consumer 不能拿。

unbounded buffer：buffer 大小無限制，producer 永遠能放，只有 consumer 可能要等。
bounded buffer：buffer 大小固定，兩邊都可能要等。

💡 例子

web server（producer）產生 HTML，browser（consumer）讀取；compiler 產生組合語言給 assembler 用。

// Shared-memory 解法（bounded buffer, circular array） #define BUFFER_SIZE 10 item buffer[BUFFER_SIZE]; int in = 0; // 下一個空位 int out = 0; // 第一個有資料的位置 /* Producer */ /* Consumer */ while (true) { while (true) { while (((in+1) % BUFFER_SIZE) == out) while (in == out) ; // full, 等待 ; // empty, 等待 buffer[in] = next_produced; next_consumed = buffer[out]; in = (in+1) % BUFFER_SIZE; out = (out+1) % BUFFER_SIZE; } }

⚡ 為什麼最多只能放 BUFFER_SIZE − 1 個？

空的條件是 in == out。如果允許放滿 10 個，in 會繞一圈回到 out，此時也是 in == out，無法分辨「全空」還是「全滿」，所以犧牲一格：(in+1) % SIZE == out 就算滿。

// Message-passing 解法 /* Producer */ /* Consumer */ while (true) { while (true) { /* produce next_produced */ receive(next_consumed); send(next_produced); /* consume next_consumed */ } }

3.6 Message Passing 的設計選擇

議題	選項 A	選項 B
naming 命名	direct：明確指定對方 `send(P, msg)`；一條 link 只連兩個 process	indirect：透過 mailbox / port `send(A, msg)`；一條 link 可連多個 process
synchronization 同步	blocking (synchronous)：send 等到對方收到；receive 等到有訊息	nonblocking (asynchronous)：send 送出就繼續；receive 拿到訊息或 null
buffering 緩衝	zero capacity：sender 必須等 receiver（rendezvous）	bounded / unbounded capacity：queue 有限 n 個 / 無限，sender 滿了才等 / 永不等

📌 定義

rendezvous 會合：send 和 receive 都是 blocking 時，雙方「碰面」才完成交換，此時 producer-consumer 問題變得很簡單。

IPC 實例	說明
ordinary pipe	單向、需要 parent-child 關係，`pipe(fd)`，fd[0] 讀、fd[1] 寫。例：`ls \| grep txt`
named pipe (FIFO)	可雙向、不需 parent-child、process 結束後仍存在，`mkfifo()`
socket	IP address + port，網路兩端通訊。例：瀏覽器連 web server
RPC remote procedure call	像呼叫本機函式一樣呼叫遠端程式，stub 負責 marshalling 參數
Mach / Windows ALPC	Mach 全以 message 溝通（ports）；Windows 用 advanced local procedure call

CH 4Threads & Concurrency 執行緒與並行

4.1 Thread 概念與好處 🔥 近年 process vs thread

📌 定義

thread 執行緒：CPU 使用的基本單位，包含 thread ID、program counter、register set、stack；同一 process 的 thread 共享 code section、data section、open files、signals。也被稱為 lightweight process（LWP）。

比較	process	thread
定位	資源分配的單位	CPU 排程的單位
記憶體	各自獨立的 address space	共享所屬 process 的 code、data、heap、files
各自私有	全部	PC、registers、stack
建立成本	高（複製 address space）	低（Solaris 中建立 thread 比 process 快約 30 倍）
context switch	慢（要換 memory-management 資訊）	快
溝通	需要 IPC（shared memory / message passing）	直接讀寫 global 變數
容錯	一個 process crash 不影響其他	一個 thread crash 可能拖垮整個 process

4 大好處	說明	例子
responsiveness 回應性	某 thread 被 block 或做長時間運算，其他 thread 仍能回應使用者	Word 存檔時你仍能繼續打字
resource sharing 資源共享	thread 預設共享 process 的記憶體與資源，不需另外設定 IPC	producer thread 與 consumer thread 共用 buffer
economy 經濟	建立與切換 thread 比 process 便宜	web server 每個請求開 thread 而非 fork process
scalability 擴展性	多處理器上 thread 可真正平行執行	影片轉檔用滿 8 核心

💡 例子：多執行緒 web server

client 發出 request
server 建立（或從 thread pool 拿）一個新 thread 處理這個 request
server 主 thread 立刻回去等下一個 request不用等前一個處理完

4.2 Multicore Programming：Concurrency vs Parallelism 🔥 2019 (8%)

📌 定義

concurrency 並行：讓多個工作都有進展（make progress）。單核心時是 interleaved（交錯）執行。

parallelism 平行：同一時間真的執行多個工作，需要多核心。

⚡ 重要觀念

有 parallelism 一定有 concurrency，但有 concurrency 不一定有 parallelism。單核心 CPU 快速切換，提供平行的「錯覺」，是 concurrent 但不是 parallel。

比較	data parallelism 資料平行	task parallelism 任務平行
切分方式	把同一份資料切塊分給各核心，每核心做相同運算	把不同工作分給各核心，每個 thread 做不同運算
例子	雙核心加總 array[N]：core0 加前半、core1 加後半	thread A 加總、thread B 求乘積；producer thread / consumer thread

Multicore 程式設計 5 大挑戰：dividing activities（找出可平行的工作）、balance（工作量平均）、data splitting（資料切分）、data dependency（資料相依需同步）、testing and debugging（執行順序多變，難除錯）。

⚡ 申論：多執行緒程式在單核心上會比單執行緒快嗎？

可能會，前提是程式有 I/O 或會 block 的操作：一個 thread 等 I/O 時，另一個 thread 可以用 CPU，CPU 不會閒著，提升 responsiveness 與 throughput。
但如果是純 CPU 運算（CPU-bound），單核心上同一時間只有一個 thread 在跑，多執行緒反而多了建立與切換的 overhead，可能更慢。

在多處理器上會比單處理器快嗎？若使用 one-to-one 或 many-to-many 模型（kernel 能看到多個 thread），thread 可以分到不同 CPU 真正平行執行，所以會更快；但若是 many-to-one，kernel 只看到一個 thread，多 CPU 也沒用。

4.3 Multithreading Models 🔥 one-to-one 每年考

📌 定義

user thread 使用者執行緒：在 kernel 之上由 thread library 管理，kernel 不知道它的存在；建立與管理較快（不用進 kernel）。

kernel thread 核心執行緒：由 OS 直接支援與管理，可被 kernel 排程到 CPU。Windows、Linux、macOS 都支援。

藍圈 = user thread，橘方塊 = kernel thread

模型	對應	優點	缺點	例子
many-to-one	多個 user thread → 1 個 kernel thread	thread 管理在 user space，有效率	① 一個 thread 呼叫 blocking system call，整個 process 被 block（2017 填空） ② 同一時間只有一個 thread 能進 kernel，多核心上無法平行	Solaris Green Threads（現已少用）
one-to-one	每個 user thread → 1 個 kernel thread	① 一個 thread block 時其他 thread 仍可執行，concurrency 比 many-to-one 好 ② 多個 thread 可在多處理器上平行執行	建立 user thread 就要建立 kernel thread，kernel thread 太多會拖累系統效能，所以常限制 thread 數量	Linux、Windows
many-to-many	多個 user thread → 較少或等量的 kernel thread	可開很多 user thread，又能平行、block 時可排別人	實作困難	（少見）
two-level	many-to-many ＋允許把某 user thread 綁定（bound）到一個 kernel thread	彈性最大	實作困難	舊版 Solaris

🔗 關聯與差異

one-to-one 的優點正好是 many-to-one 的兩個缺點反過來；它的缺點（kernel thread 開銷）則由 many-to-many 解決。現代多核心系統大多用 one-to-one，因為核心數多了，限制 kernel thread 數量變得不那麼重要。

4.4 Thread Libraries：Pthreads 🔥 fork + pthread 輸出題

📌 定義

Pthreads：POSIX 標準（IEEE 1003.1c）定義的 thread 建立與同步 API，是規格（specification）不是實作。UNIX、Linux、macOS 皆有。

// Pthreads 基本流程

pthread_attr_init(&attr)設定 thread 屬性（使用預設值）
pthread_create(&tid, &attr, runner, param)建立新 thread，從 runner 函式開始執行
新 thread 執行 runner()，結束時 pthread_exit(0)pthread_exit 之後的程式不會執行
主 thread 呼叫 pthread_join(tid, NULL) 等待類似 process 的 wait()

⚡ fork vs pthread 對 global 變數的影響

int value = 0; void *runner(void *p){ value = 5; pthread_exit(0); } // 情況 1：thread pthread_create(&tid, &attr, runner, NULL); pthread_join(tid, NULL); printf("%d", value); // 印 5：thread 共享 data section // 情況 2：fork if (fork() == 0) { value = 5; return 0; } wait(NULL); printf("%d", value); // parent 印 0：child 改的是自己的複本

4.5 Implicit Threading 隱式執行緒

📌 定義

implicit threading：把建立與管理 thread 的工作從程式設計師交給編譯器與 run-time library，程式設計師只要找出可平行的 task。

技術	說明	例子
thread pool	啟動時先建一批 thread 等工作；用現成的 thread 比新建快，且限制 thread 總數避免系統被拖垮	web server、Java `ExecutorService`
fork-join	主 thread 分出（fork）子 task，等全部完成再合併（join），適合遞迴分治	Java `ForkJoinPool` 做 merge sort
OpenMP	C/C++/Fortran 用 compiler directive 標示平行區域	`#pragma omp parallel for`
GCD Grand Central Dispatch	Apple 技術，把 block 丟進 dispatch queue（serial / concurrent）	iOS app 背景下載
Intel TBB	C++ template library，`parallel_for`	—

4.6 Threading Issues

議題	重點	例子
`fork()` / `exec()`	多執行緒程式 fork 時，有的系統複製所有 thread、有的只複製呼叫的 thread；fork 後立刻 exec 就只要複製呼叫者（反正會被取代）	shell 執行指令
signal handling	signal 該送給哪個 thread？同步 signal 送給造成它的 thread；非同步（如 Ctrl+C）可送給所有或特定 thread	`kill()`、`pthread_kill()`
thread cancellation	asynchronous：立刻終止目標 thread（危險，資源可能沒釋放）；deferred：目標 thread 定期檢查是否該結束，在安全的 cancellation point 才結束（Pthreads 預設）	瀏覽器按「停止」取消載入
TLS thread-local storage	每個 thread 自己一份的資料，跨函式可見（不同於 local variable）	每個交易 thread 的交易編號
scheduler activations	kernel 透過 upcall 通知 thread library，搭配 LWP（lightweight process，介於 user / kernel thread 間的虛擬處理器）	many-to-many 模型實作

4.7 OS 例子：Windows 每個 thread 有 ETHREAD / KTHREAD / TEB；Linux 不區分 process 與 thread，統稱 task，用 clone() 建立，flag 決定要共享多少資源（全部共享 ≈ thread，都不共享 ≈ fork）。

CH 5.1–5.2CPU Scheduling 基本觀念

5.1 CPU–I/O Burst Cycle 與 CPU Scheduler

📌 定義

CPU–I/O burst cycle：process 的執行由 CPU 執行（CPU burst） 與 等 I/O（I/O burst） 交替組成。

I/O-bound 程式：很多短的 CPU burst（例：文字編輯器、網頁瀏覽）。
CPU-bound 程式：少數長的 CPU burst（例：影片轉檔、科學計算）。

CPU scheduler：CPU 閒置時，從 ready queue 選一個 process 執行。ready queue 不一定是 FIFO，也可以是 priority queue、tree、無序 linked list。

💡 例子

CPU burst 長度分布（Fig 5.2）是指數型：大量短 burst、少量長 burst。這就是為什麼排程演算法通常偏好短工作，以及為什麼 multiprogramming 能大幅提升 CPU 使用率（大多數時間 process 在等 I/O）。

Preemptive vs Nonpreemptive、Dispatcher

CPU 排程決策可能發生在 process 的 4 種狀態轉換：

running → waiting例如發出 I/O request、呼叫 wait()
running → ready例如 interrupt（time slice 用完）
waiting → ready例如 I/O 完成
terminatesprocess 結束

⚡ 判斷規則

只在情況 1 和 4 排程 → nonpreemptive（cooperative）：process 自願放棄 CPU，別無選擇一定要選新的。
情況 2、3 也會排程 → preemptive：OS 可以強行把 CPU 搶走。

比較	nonpreemptive 不可搶先	preemptive 可搶先
CPU 何時釋放	process 自己結束或進入 waiting 才釋放	OS 可隨時中斷並收回 CPU
排程時機	只有 1、4	1、2、3、4
回應性	差：長工作會卡住其他人	好，適合互動式系統
問題	一個 process 可能霸佔 CPU	存取共享資料時可能有 race condition，需要同步機制（Ch6）；kernel 設計要考慮在 system call 期間被搶先的情況
例子	早期 Windows 3.x	幾乎所有現代 OS：Windows、macOS、Linux、UNIX

📌 定義 Dispatcher

dispatcher 分派器：把 CPU 控制權交給 CPU scheduler 選出的 process 的模組。

dispatch latency 分派延遲：dispatcher 停止一個 process 並啟動另一個所花的時間，越短越好（每次 context switch 都會呼叫 dispatcher）。

// Dispatcher 的 3 個工作

Switching context把舊 process 的狀態存到 PCB，載入新 process 的狀態
Switching to user modemode bit 設回 1
Jumping to the proper location in the user program跳到新 process 的 PC，從上次中斷的地方繼續執行

🔗 Scheduler vs Dispatcher

CPU scheduler 負責「選誰」（決策）；dispatcher 負責「把 CPU 交給它」（執行切換）。這也是 mechanism（dispatcher）vs policy（scheduler 演算法）分離的例子。

5.2 Scheduling Criteria 排程評估指標

指標	中文	定義	目標	例子
CPU utilization	CPU 使用率	CPU 忙碌的比例	最大化	40%（輕載）～90%（重載）
throughput	產出量	單位時間完成的 process 數	最大化	長工作 1 個/小時；短交易 10 個/秒
turnaround time	周轉時間	從提交（submission）到完成（completion）的總時間，含等待記憶體、ready queue、CPU 執行、I/O	最小化	批次工作看這個
waiting time	等待時間	在 ready queue 中等待的總時間（不含 I/O 時間）	最小化	排程演算法唯一能直接影響的
response time	回應時間	從提交 request 到第一個回應產生的時間（是開始回應，不是輸出完成）	最小化	互動式系統看這個

⚡ 重要觀念

排程演算法不影響程式執行或做 I/O 的時間，只影響在 ready queue 等待的時間。
對互動式系統，比起平均 response time，降低 response time 的變異數（variance）更重要：穩定可預期比偶爾很快更好。
若一個 process 只有一段 CPU burst 且沒有 I/O：turnaround time = waiting time + burst time。

💡 例子

P1 在時間 0 到達，前面排了 6 ms 的工作，P1 本身要跑 4 ms：waiting time = 6，turnaround time = 6 + 4 = 10，若 P1 一上 CPU 就輸出第一個字，response time = 6。

🔗 指標之間的取捨

提高 throughput（偏好短工作）可能讓長工作的 turnaround time 變很長；縮短 response time（頻繁切換）會增加 context switch overhead，反而降低 CPU utilization。

Flashcard 翻牌記憶

正面是英文術語或情境，點一下翻到背面看中文定義與例子。

小測驗（20 題）

每題只能選一次，選完立刻顯示解析，包含每個錯誤選項錯在哪裡。

答對 0 / 0 已作答（共 0 題）

考古題解析

整理 2019、2017 兩份期中考題目，加上三份近年作答卷中看得出的出題方向與失分點。填空題答案預設模糊，點一下才顯示；申論題點「參考答案」展開。藍色標籤可以跳回對應的筆記段落。

TREND出題趨勢總覽

主題	2017	2019	近年作答卷	建議
Dual-mode（trap / system call / timer）	✔ 13%	✔ 15%	✔	申論模板背熟
Microkernel / Monolithic / LKM 比較＋畫圖	✔ 16%	✔ 24%	✔	三大面向比較表
IPC 兩種模型 + producer-consumer＋畫圖	✔ 12%	✔ 16%	✔	兩張圖＋優缺點
One-to-one model	✔ 8%	✔ 11%	✔	畫圖＋優缺點＋單/多處理器
fork() + Pthreads 輸出	✔ 10%	✔ 12%	—	練習追蹤 value
Memory layout / context switch	填空	✔ 12%	—	畫圖＋步驟
填空：bootstrap、clustered、embedded、monolithic…	✔ 20%	✔ 10%	✔	背考古原句

⚠ 作答卷上看到的扣分點

填空要寫完整術語：「bootstrap」只寫一半、「start」等都被扣分；「symmetric multiprocessing」要拼對。
Shared memory 缺點寫「容易被修改」被圈起來：應寫需要程式設計師自行處理 synchronization 與 protection。
Message passing 優點寫「×（沒有）」只拿部分分：優點是不會有寫入衝突、適合分散式系統、適合少量資料。
畫圖題多半有分（圖給 3～6 分），一定要畫圖並標 user mode / kernel mode。
Process vs thread 只寫「thread 可平行處理」只拿 2 分：要寫出共享哪些資源、各自私有哪些、建立與切換成本。

20192019/11/12 期中考

I. Fill in the Blanks（10%）

1. OS contains a large amount of functionality combined into one level; procedures can call any other → monolithic

2. Two or more individual systems or nodes joined together, high availability → clustered

3. Functions correctly only if it returns the correct result within its time constraints → real-time

4. Combination of hardware and software, perhaps mechanical parts, for specific tasks → embedded

5. Initializes all aspects of the system, loads OS kernel, starts executing the OS → bootstrap program

II. Questions（90%）

1. Give examples and describe the differences between trap, system call, and interrupt. Using trap, system call, and timer interrupt as examples to discuss why modern OS take advantage of hardware-supported dual-mode operation. (15%)

→ Interrupt / Trap / System call → Dual-mode

參考答案

差異：interrupt 由硬體非同步產生（例：鍵盤輸入、I/O 完成）；trap 是軟體產生的中斷，由錯誤引起（例：除以 0、非法記憶體存取）；system call 是使用者程式刻意請 OS 服務，以 trap 的形式進入 kernel（例：fork()、read()）。

為何需要 dual-mode：用 mode bit（kernel 0 / user 1）區分 OS 與使用者程式，保護 OS 與其他程式。

trap：使用者程式出錯或在 user mode 執行 privileged instruction 時，硬體 trap 到 kernel mode 由 OS 處理，錯誤不會破壞 OS 或其他程式。
system call：I/O 等特權操作只能透過 system call 由 OS 在 kernel mode 檢查後代為執行，結束後切回 user mode。
timer interrupt：避免程式無窮迴圈霸佔 CPU，時間到 OS 一定能拿回控制權；設定 timer 是 privileged instruction，使用者無法關閉。

以上機制都依賴硬體維護的 mode bit，軟體無法自行切換，保護才可靠。

2. (a) Draw the diagram of a typical microkernel and describe the microkernel approach. (b) Describe the loadable kernel modules approach. (c) Compare microkernel and LKM in terms of extensibility, performance, and security. (24%)

→ 2.8 OS 結構比較

參考答案

(a) 畫出 Fig 2.15：user mode 有 Application、File System、Device Driver；kernel mode 的 microkernel 只有 IPC、memory management、CPU scheduling；元件之間以 messages 溝通。
Microkernel approach：把非必要元件從 kernel 移出，實作成在各自 address space 的 user-level 程式；kernel 主要提供 client 與各服務之間的 message passing 通訊（例：Mach、QNX）。

(b) LKM：kernel 只保留核心元件，其他服務（驅動程式、檔案系統）以 module 形式在開機或執行時動態載入；module 在 kernel space，有定義好的介面，任何 module 可直接呼叫其他 module（例：Linux insmod/rmmod）。

(c)

	microkernel	LKM
extensibility	好：新增服務在 user space 加程式即可，不用改 kernel	好：module 單獨編譯，執行中載入/卸載不用重開機
performance	差：服務間 message passing 需要多次 user/kernel 切換	好：module 在 kernel 內直接呼叫，不需 message passing
security	好：服務以 user process 執行，出錯不會讓 kernel 掛掉	較差：module 在 kernel mode 執行，有問題的 module 會危及整個系統

3. What is the producer-consumer problem? Discuss the strengths and weaknesses of two IPC models to solve it. Draw the diagram for each model. (16%)

→ IPC → Producer-Consumer

參考答案

問題：producer 產生資料放進 buffer，consumer 從 buffer 取出；必須同步，buffer 滿時 producer 不能放、空時 consumer 不能拿。

Shared memory（圖：A、shared memory、B、kernel 上下堆疊，A/B 都指向共享區）：buffer 放在共享記憶體，用 in/out 指標實作 circular buffer。
優：速度快，建立後是一般記憶體存取，不需 kernel。缺：同步與保護由程式設計師負責；不易用在分散式系統。

Message passing（圖：A、B 與 kernel 中的 message queue m0…mn）：producer send()，consumer receive()，buffer 由 OS 提供。
優：不需處理寫入衝突，實作簡單；適合分散式環境。缺：每次都要 system call，kernel 介入，較慢。

4. Draw the diagram and describe the memory layout of a process. What is the context of a process? Describe the actions taken by a kernel to context-switch between processes. (12%)

→ Memory layout → Context switch

參考答案

Memory layout（高位址到低位址）：stack（區域變數、參數、return address）→ free → heap（動態配置）→ data（global 變數）→ text（程式碼）。

Context：存在 PCB 中的 process 狀態，包括 CPU registers、program counter、process state、memory-management information。

Context switch：interrupt 或 system call 發生 → kernel 把舊 process 的 context 存進它的 PCB → 將其放入 ready/wait queue → scheduler 選出新 process → 從新 process 的 PCB 載入 context（含記憶體管理資訊）→ 切回 user mode 執行新 process。切換時間是 pure overhead。

5. One-to-one model: (a) Draw and describe it. (b) Can a multithreaded application perform better on a multiprocessor than on a single-processor system? (c) On a single processor, can multithreaded perform better than single-threaded? (11%)

→ Multithreading models → Concurrency vs Parallelism

參考答案

(a) 每個 user thread 對應一個 kernel thread（畫 4 條平行線連接 user space 與 kernel space）。一個 thread block 時其他仍可執行；可在多處理器平行；缺點是建立 user thread 就要建立 kernel thread，數量過多影響效能。Linux、Windows 採用。

(b) 可以。one-to-one 中每個 thread 都是 kernel 可排程的單位，可分配到不同 CPU 真正平行執行（parallelism），所以比單處理器快。

(c) 視情況。若程式有 I/O 或 blocking 操作，一個 thread 等待時另一個可使用 CPU，提升效能與回應性（concurrency）。若是純 CPU-bound 運算，單處理器一次只能跑一個 thread，多執行緒反而增加建立與切換的 overhead，不會更快。

6. What would be the output of the following C program using UNIX fork() and Pthreads? (12%)

→ Pthreads → fork()

int value = 1; void *start(void *param){ printf(" (a) %d \n", value); value++; pthread_exit(0); value++; // 不會執行 } void main(){ printf(" (b) %d \n", value); pid = fork(); value++; if (pid == 0) { /* child */ value++; pthread_attr_init(&attr); pthread_create(&tid, &attr, start, NULL); pthread_join(tid, NULL); printf(" (c) %d \n", value); value++; } else if (pid > 0) { /* parent */ value++; wait(NULL); printf(" (d) %d \n", value); value++; } printf(" (e) %d \n", value); value++; }

參考答案與追蹤

步驟	parent 的 value	child 的 value	輸出
fork 前印 (b)	1	—	`(b) 1`
fork 後 value++	2	2
child: value++		3
child 的 thread 印 (a)，value++		3 → 4	`(a) 3`
child join 後印 (c)，value++		4 → 5	`(c) 4`
child 印 (e)		5	`(e) 5`
parent: value++，wait 等 child 結束	3
parent 印 (d)，value++	3 → 4		`(d) 3`
parent 印 (e)	4		`(e) 4`

輸出順序：(b) 1 → (a) 3 → (c) 4 → (e) 5 → (d) 3 → (e) 4

關鍵：thread 和 child 共享 value（同一 process）；parent 與 child 是不同複本。parent 有 wait(NULL)，所以 child 的輸出全部在 (d) 之前。pthread_exit 後面的 value++ 不會執行。

20172017/11/23 期中考

I. Fill in the Blank（20%）

1. Can suffer a failure of any single component and still continue operation → fault-tolerant

2. Two or more individual systems or nodes joined together → clustered

3. What virtualization software do you use? → VirtualBox（或 VMware Workstation）

4. All processors are peers, no boss-worker relationship → symmetric multiprocessing (SMP)

5. Hardware + software (+ mechanical parts) for specific tasks → embedded

6. OS keeps several jobs in memory; when one waits, switches to another → multiprogramming

7. Large amount of functionality combined into one level → monolithic

8. Initializes the system, loads OS kernel, starts executing the OS → bootstrap program

9. Save the state of the old process and load the saved state of the new process via a ___ → context switch

10. A thread makes a blocking system call, the entire process will block for the ___ model → many-to-one

II. Questions（80%）

1. What is dual-mode operation? Using trap, system call, and timer interrupt as examples to discuss why modern OS take advantage of hardware-supported dual-mode operation. (13%)

→ Dual-mode 申論模板

參考答案

Dual-mode：硬體提供 mode bit 區分 kernel mode（0）與 user mode（1）；interrupt / trap / system call 發生時切到 kernel mode 執行 OS 程式，完成後切回 user mode。privileged instruction 只能在 kernel mode 執行。

trap、system call、timer 的論述同 2019 第 1 題：trap 攔截錯誤與非法指令、system call 讓特權操作必須經過 OS 檢查、timer 防止程式霸佔 CPU。

2. Describe the microkernel and the modular kernel approach in OS design. Compare their strengths and weaknesses in terms of extensibility. (16%)

→ 2.8 OS 結構比較

參考答案

Microkernel：只把最小必要功能（process / memory 管理、IPC）留在 kernel，其他服務以 user-level process 執行，透過 message passing 溝通。
Modular（LKM）：核心元件在 kernel，其他服務以 module 動態連結進 kernel。

Extensibility 比較：兩者都容易擴充。microkernel 新增服務只要在 user space 加一個 server process，kernel 不必修改，且新服務出錯不影響 kernel（擴充較安全）；但新服務與他人溝通都要透過 message passing，擴充越多 overhead 越大。LKM 新增 module 不用重新編譯 kernel、不用重開機即可載入，且 module 間直接呼叫、效率高；但新加入的 module 在 kernel mode 執行，若有 bug 會危害整個系統。

3. Take the producer-consumer problem as an example to discuss the strengths and weaknesses of two IPC models. Draw the diagram for each model. (12%)

→ IPC

參考答案

同 2019 第 3 題。

4. What is the one-to-one multithreading model? Discuss its strengths and weaknesses. (8%)

→ Multithreading models

參考答案

每個 user thread 對應一個 kernel thread。
優點：比 many-to-one 有更好的 concurrency，一個 thread 呼叫 blocking system call 時其他 thread 仍可執行；多個 thread 可在多處理器上平行執行。
缺點：每建立一個 user thread 就要建立對應的 kernel thread，開銷大，kernel thread 太多會拖累系統效能，因此系統通常限制 thread 數量。

5. What would be the output for the following C program using UNIX fork() and Pthreads? (10%)

→ Pthreads

int value = 1; void runner(){ value++; printf("(a) %d ", value); } void *start(void *param){ runner(); value++; pthread_exit(0); } int main(){ value++; pid = fork(); value++; if (pid == 0) { /* child */ value++; printf("(b) %d ", value); pthread_attr_init(&attr); value++; pthread_create(&tid, &attr, start, NULL); pthread_join(tid, NULL); value++; } else if (pid > 0) { /* parent */ value++; wait(NULL); runner(); } value++; printf("(c) %d ", value); }

參考答案與追蹤

步驟	parent	child	輸出
value++（fork 前）	2	—
fork 後 value++	3	3
child: value++，印 (b)		4	`(b) 4`
child: value++		5
thread: runner() value++ 印 (a)		6	`(a) 6`
thread: value++，exit		7
child join 後 value++		8
child: value++ 印 (c)		9	`(c) 9`
parent: value++，wait	4
parent: runner() value++ 印 (a)	5		`(a) 5`
parent: value++ 印 (c)	6		`(c) 6`

輸出：(b) 4 (a) 6 (c) 9 (a) 5 (c) 6

⚠ 注意

考古照片上的手寫推導把 child 的 (a) 寫成 5，是錯的：child 建立 thread 前已經多做一次 value++（變 5），thread 裡的 runner 再 ++ 才印，所以是 6。另外 runner() 在 thread 裡被呼叫時，改的是 child 的 value（共享），不是 parent 的。

RECENT近年作答卷整理

三份學生作答卷（含老師批改）看不到完整題目，但從答案可以推回題型：

題型	從作答卷推測的題目	對應筆記
填空	bootstrap program、clustered、NUMA、time-sharing、monolithic、layered、symmetric multiprocessing、shell、context switch、VirtualBox、module	1.3 架構 Multiprogramming Shell
選擇題	新一屆試卷出現選擇題（多選，如 abcd、bf）及排序題（B、A、D、C、D）	整體觀念
畫圖說明	Multiprogramming 記憶體配置與 CPU 切換	Multiprogramming
畫圖說明	System call 時 user / kernel mode 切換（mode bit 0/1）	Dual-mode
流程	Exception（如 5/0）發生時 OS 如何處理：CPU → 查 interrupt vector → handler → 回 user mode 或終止	OS 何時執行
比較＋畫圖	Microkernel、monolithic、LKM 的架構圖與優缺點	2.8 結構
比較＋畫圖	Shared memory vs message passing ＋ producer-consumer	IPC
比較＋畫圖	Process vs thread 差異	Thread
畫圖說明	One-to-one model 與其優缺點	Models

作業系統 期中衝刺筆記

CH 1Introduction 導論

1.1 OS 是什麼

1.2 OS 什麼時候會執行？（老師必講）

開機流程 Bootstrap 🔥 考古 2017、2019 填空

中斷處理流程 Interrupt Handling

Interrupt vs Trap vs System Call 🔥 考古 2019 (15%)

1.4 Dual-Mode Operation 與 Timer 🔥 考古 每年必考

Multiprogramming vs Multitasking 🔥 考古 填空＋畫圖

1.3 Computer-System Architecture 🔥 考古 填空

1.7 Virtualization 與 1.10 Computing Environments

CH 2Operating-System Structures 作業系統結構

2.1–2.2 OS Services 與 User Interface

2.3 System Calls 系統呼叫

傳遞參數的 3 種方法

System call 6 大類

2.5 Linkers & Loaders、2.7 設計原則

2.8 OS Structure 結構 🔥 考古 2017、2019、近年 必考

三大比較：extensibility、performance、security 🔥 2019 (12%)

2.9 Building & Booting、2.10 Debugging

CH 3Processes 行程

3.1 Process 概念與 Memory Layout 🔥 2019 (4%)

Process State 與 PCB

3.2 Process Scheduling 與 Context Switch 🔥 2017 填空、2019 (8%)

3.3 Operations on Processes：fork()、exec()、wait()

3.4 IPC：Shared Memory vs Message Passing 🔥 每年必考

Producer-Consumer Problem 🔥 2017、2019、近年

3.6 Message Passing 的設計選擇

CH 4Threads & Concurrency 執行緒與並行

4.1 Thread 概念與好處 🔥 近年 process vs thread

4.2 Multicore Programming：Concurrency vs Parallelism 🔥 2019 (8%)

4.3 Multithreading Models 🔥 one-to-one 每年考

4.4 Thread Libraries：Pthreads 🔥 fork + pthread 輸出題

4.5 Implicit Threading 隱式執行緒

4.6 Threading Issues

CH 5.1–5.2CPU Scheduling 基本觀念

5.1 CPU–I/O Burst Cycle 與 CPU Scheduler

Preemptive vs Nonpreemptive、Dispatcher

5.2 Scheduling Criteria 排程評估指標

Flashcard 翻牌記憶

小測驗（20 題）

考古題解析

TREND出題趨勢總覽

20192019/11/12 期中考

I. Fill in the Blanks（10%）

II. Questions（90%）

20172017/11/23 期中考

I. Fill in the Blank（20%）

II. Questions（80%）

RECENT近年作答卷整理

作業系統期中衝刺筆記

1.4 Dual-Mode Operation 與 Timer 🔥 考古每年必考

Multiprogramming vs Multitasking 🔥 考古填空＋畫圖

1.3 Computer-System Architecture 🔥 考古填空

2.8 OS Structure 結構 🔥 考古 2017、2019、近年必考