Thrashing (hiện tượng đập trang)

1. Tổng quan

A. Định nghĩa

Thrashing (hiện tượng đập trang) là hiện tượng trong hệ thống bộ nhớ ảo, khi lỗi trang (Page Fault) phát sinh quá mức khiến CPU dành nhiều thời gian cho việc thay thế trang (swapping) hơn là tính toán thực tế, làm thông lượng (throughput) của hệ thống sụp đổ nghiêm trọng. Dấu hiệu nhận biết là ngay khi mức độ đa chương trình (degree of multiprogramming) vượt ngưỡng tới hạn, mức sử dụng CPU rơi thẳng đứng.

Bản chất của thrashing nằm ở chỗ "không làm việc mà chỉ lặp đi lặp lại việc đổi trang". Bộ nhớ ảo là kỹ thuật không nạp toàn bộ chương trình vào bộ nhớ vật lý mà chỉ nạp các trang cần cho thực thi theo yêu cầu (demand paging). Nhờ đó có thể chạy chương trình lớn hơn bộ nhớ vật lý và chạy nhiều tiến trình cùng lúc. Tuy nhiên, kỹ thuật này dựa trên giả định về tính cục bộ tham chiếu rằng "trang cần thiết hẳn đã có trong bộ nhớ", và ngay khi giả định này sụp đổ, hệ thống rơi vào thrashing.

Gốc rễ vấn đề là tổng lượng bộ nhớ vật lý (khung trang) có hạn nhưng có quá nhiều tiến trình muốn chạy. Nếu mỗi tiến trình không giành được ngay cả tập trang tối thiểu cần cho công việc của mình, thì vòng "giành giật trang" sẽ lặp lại không dứt: để nạp trang A phải đẩy B ra (page-out), ngay sau đó lại cần B nên đẩy C ra để nạp B, trong lúc đó lại cần A. CPU không thực thi được lệnh nào mà chỉ chờ I/O đĩa kết thúc. Thực tế, chi phí xử lý một lần lỗi trang ở mức vài mili giây (khoảng 5~10ms với HDD, ngay cả SSD cũng vài chục đến vài trăm micro giây), chậm hơn hàng chục nghìn lần so với thực thi lệnh CPU tính bằng nano giây. Đây là lý do chỉ cần tỷ lệ lỗi tăng một chút là thời gian truy cập hiệu dụng bùng nổ.

Thêm vào đó, phán đoán sai của hệ điều hành hoàn tất vòng luẩn quẩn. Khi thrashing bắt đầu, mức sử dụng CPU chạm đáy, và bộ lập lịch trung hạn (chính sách lập lịch) diễn giải điều này là "CPU đang rảnh" nên tăng thêm mức độ đa chương trình. Khi thêm tiến trình, tranh chấp khung trang càng khốc liệt, lỗi trang càng bùng nổ và mức sử dụng CPU càng giảm. Vòng phản hồi (feedback loop) này là cốt lõi biến thrashing từ suy giảm hiệu năng đơn thuần thành "sụp đổ tự củng cố". Vì vậy, muốn thoát khỏi thrashing tận gốc thì không phải tăng tài nguyên mà phải kiểm soát mức độ đa chương trình.

B. Đặc điểm của thrashing

Thrashing có một số đặc điểm phân biệt với quá tải đơn thuần. Thứ nhất là sụp đổ phi tuyến. Khi tải tăng dần, hiệu năng không giảm từ từ mà ngay khi vượt ngưỡng tới hạn thì rơi xuống như vách đá. Thứ hai, nó cho thấy chỉ báo nghịch lý là mức sử dụng CPU thấp và hoạt động đĩa cao xuất hiện đồng thời. Bề ngoài CPU đang rảnh nhưng hệ thống lại tê liệt. Thứ ba là tính tự làm xấu đi. Nếu không can thiệp, nó không tự phục hồi mà càng tệ hơn.

2. Nguyên lý phát sinh và cơ chế

A. Quan hệ giữa mức độ đa chương trình và mức sử dụng CPU

flowchart LR
  M["Mức độ đa chương trình↑"] --> F["Lỗi trang↑"]
  F --> S["Swapping (I/O đĩa) tăng vọt"]
  S --> C["Mức sử dụng CPU↓"]
  C --> O["OS phán đoán sai: nạp thêm tiến trình"]
  O --> M
  style S fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style O fill:#fde8e8,stroke:#ed2f2f,stroke-width:2px

Sơ đồ trên biểu diễn vòng luẩn quẩn của thrashing. Cốt lõi là nút màu đỏ cuối cùng, tức bước hệ điều hành diễn giải sai mức sử dụng CPU thấp và chất thêm tải. Nếu không có phản hồi này, thrashing chỉ dừng lại ở suy giảm hiệu năng tạm thời, nhưng khi phán đoán sai của OS can thiệp, sự sụp đổ được đẩy nhanh.

Nếu đặt mức độ đa chương trình trên trục x và mức sử dụng CPU trên trục y, đường cong chia thành ba đoạn. Ở đoạn đầu, càng tăng tiến trình thì CPU càng không rảnh mà làm việc nên mức sử dụng tăng. Ở đoạn thứ hai, tức gần ngưỡng tới hạn, mức sử dụng đạt đỉnh. Đây là điểm cân bằng nơi bộ nhớ vật lý vừa đủ chứa working set của mọi tiến trình. Ở đoạn thứ ba, nếu nạp thêm tiến trình, khung trang của mỗi tiến trình giảm xuống dưới working set khiến lỗi trang bùng nổ và mức sử dụng CPU rơi thẳng đứng. Thrashing xảy ra chính ở đoạn thứ ba này. Trong thực tế, mục tiêu của lập lịch là kiểm soát mức độ đa chương trình nhắm vào điểm "ngay trước đỉnh".

B. Luồng chi tiết xử lý lỗi trang

sequenceDiagram
  participant P as Tiến trình
  participant M as MMU/Bảng trang
  participant OS as Hệ điều hành
  participant D as Đĩa(kho lưu trữ dự phòng)
  P->>M: Tham chiếu địa chỉ ảo
  M->>M: Kiểm tra bit hợp lệ
  M-->>OS: Bẫy lỗi trang (Page Fault)
  OS->>OS: Tìm khung trống
  Note over OS: Không có khung trống → chọn trang nạn nhân
  OS->>D: Write-back trang nạn nhân (nếu đã sửa đổi)
  D-->>OS: Hoàn tất
  OS->>D: Read-in trang được yêu cầu
  D-->>OS: Nạp trang
  OS->>M: Cập nhật bảng trang
  OS-->>P: Khởi động lại lệnh

Sơ đồ tuần tự này cho thấy có bao nhiêu bước tham gia vào việc xử lý một lần lỗi trang. Đặc biệt quan trọng là khi không có khung trống, có thể phát sinh hai lần I/O đĩa: chọn trang nạn nhân (victim) và ghi (write-back) ra đĩa, rồi lại đọc trang được yêu cầu vào. Ở trạng thái thrashing, gần như mọi lỗi trang đều đi theo đường "không có khung trống" này, nên một lần lỗi gây ra hai lần truy cập đĩa, làm nút thắt tăng gấp đôi. Lý do tồn tại tối ưu hóa ưu tiên chọn trang không bị sửa đổi (clean) làm nạn nhân cũng là để tiết kiệm một lần write-back.

Khi định lượng bằng thời gian truy cập hiệu dụng (EAT), mức nghiêm trọng trở nên rõ ràng. Đặt truy cập bộ nhớ là 100ns, xử lý lỗi trang là 8ms (=8,000,000ns), thì với tỷ lệ lỗi p, EAT ≈ (1-p)×100 + p×8,000,000. Chỉ cần tỷ lệ lỗi là 0,1% (p=0.001), EAT đã khoảng 8,100ns, chậm hơn bình thường 80 lần. Ở đoạn thrashing, tỷ lệ lỗi lên tới vài %, nên hệ thống thực tế rơi vào trạng thái đứng yên.

C. Working set và tính cục bộ

Nền tảng lý thuyết để hiểu và kiểm soát thrashing là tính cục bộ tham chiếu (locality of reference) và working set (tập làm việc). Chương trình không tham chiếu đều toàn bộ không gian địa chỉ tại mọi thời điểm, mà tại một thời điểm cụ thể, tham chiếu tập trung vào một tập trang nhất định. Đó là tính cục bộ thời gian (dữ liệu vừa dùng sẽ sớm được dùng lại) và tính cục bộ không gian (các địa chỉ liền kề được dùng cùng nhau). Việc thực thi chương trình có thể xem là chuỗi "chuyển pha (phase)" nối tiếp, trong đó các tập cục bộ này dịch chuyển theo thời gian.

Working set là khái niệm định lượng hóa ý tưởng này, được định nghĩa là tập các trang khác nhau được tham chiếu trong khoảng thời gian Δ (cửa sổ working set) gần nhất. Nhận thức sâu sắc của mô hình working set do Denning đề xuất là "nếu bảo đảm cho mỗi tiến trình số khung trang bằng kích thước working set của nó thì lỗi trang giảm mạnh". Ngược lại, nếu khung trang ít hơn working set thì lỗi vẫn lặp lại ngay cả khi pha đang ổn định. Thời điểm tổng working set của toàn hệ thống vượt quá số khung vật lý chính là ngưỡng tới hạn của thrashing, và khi đó OS phải swap-out một tiến trình để giảm tổng này.

D. Ảnh hưởng của chính sách thay thế trang

Tần suất thrashing cũng gắn với thuật toán thay thế trang. Thay thế toàn cục (global replacement) giải quyết lỗi của một tiến trình bằng cách giành khung của tiến trình khác, nên sự quá tải của một tiến trình dễ lây lan ra toàn hệ thống và gây thrashing. Ngược lại, thay thế cục bộ (local replacement) để mỗi tiến trình chỉ thay thế trong các khung được cấp cho mình nên ngăn lây lan, nhưng nếu ngay từ đầu cấp phát đã thấp hơn working set thì tiến trình đó tự thrashing bên trong. Ngoài ra, thuật toán FIFO có thể thể hiện nghịch lý Belady (Belady's Anomaly), tức tăng khung trang nhưng lỗi lại tăng, nên các thuật toán ngăn xếp (stack algorithm) họ LRU an toàn hơn xét từ góc độ thrashing.

3. So sánh các phương pháp giải quyết

Các biện pháp đối phó thrashing chia thành "phía bảo đảm working set", "phía giám sát và điều chỉnh trực tiếp tỷ lệ lỗi", "phía giảm chính tải" và "phía tăng tài nguyên". Bảng dưới đây tổng hợp chúng, còn lý do mỗi kỹ thuật hiệu quả và giới hạn của nó được giải thích tiếp bằng văn xuôi.

Phương pháp giải quyết	Nguyên lý	Giới hạn, chi phí
Mô hình working set	Cấp khung theo kích thước tập trang mà tiến trình cần	Chi phí ước lượng cửa sổ Δ và đo working set
PFF (Page-Fault Frequency)	Điều chỉnh động khung trang theo cận trên/dưới của tỷ lệ lỗi trang	Thiết lập ngưỡng phụ thuộc khối lượng công việc
Điều chỉnh mức độ đa chương trình	Khi vượt ngưỡng thì swap-out (tạm dừng) một số tiến trình	Giảm khả năng phản hồi của tiến trình bị swap-out
Tăng bộ nhớ vật lý	Giải quyết tình trạng thiếu khung trang căn bản	Chi phí, giới hạn không gian địa chỉ và điện năng
Cải thiện tính cục bộ	Thiết kế mã và cấu trúc dữ liệu có tính cục bộ tham chiếu cao	Cần thiết kế lại ứng dụng

Mô hình working set là cách tiếp cận căn bản nhất. OS ước lượng kích thước working set của mỗi tiến trình và bảo đảm số khung trang tương ứng; nếu tổng working set của mọi tiến trình vượt tổng số khung thì tạm dừng hoàn toàn (swap-out) một tiến trình. Như vậy, các tiến trình còn lại có đủ khung và lỗi giảm mạnh. Tuy nhiên, khó xác định chính xác cửa sổ working set Δ, và chi phí cập nhật working set ở mỗi lần tham chiếu lớn, nên hiện thực thực tế dùng cách xấp xỉ lấy mẫu định kỳ bit tham chiếu.

Kỹ thuật PFF (tần suất lỗi trang) là đường vòng thực dụng, thay vì đo trực tiếp working set thì chỉ giám sát tỷ lệ lỗi — chỉ số kết quả. Nếu tỷ lệ lỗi của tiến trình vượt cận trên, coi đó là tín hiệu "thiếu khung" và cấp thêm khung; nếu xuống dưới cận dưới, coi là "thừa" và thu hồi. Đây là cách điều khiển phản hồi để giữ tỷ lệ lỗi trong một dải nhất định, nên hiện thực đơn giản và phản ứng nhanh. Tuy nhiên, ngưỡng cận trên/dưới tối ưu khác nhau theo khối lượng công việc, nếu đặt sai sẽ dao động hoặc phản ứng chậm chạp.

Điều chỉnh mức độ đa chương trình là cách chính diện giảm quá tải — nguyên nhân trực tiếp của thrashing. Khi bộ lập lịch trung hạn phát hiện thrashing, nó swap-out tạm dừng các tiến trình có ưu tiên thấp hoặc working set lớn, rồi swap-in trở lại khi hệ thống ổn định. Hiệu quả tức thì lớn, nhưng thời gian phản hồi của tiến trình bị tạm dừng kéo dài nên cần thận trọng với khối lượng công việc tương tác.

Tăng bộ nhớ vật lý là cách chắc chắn nhất loại bỏ nguyên nhân gốc là thiếu khung trang, nhưng có chi phí và giới hạn vật lý, và không phải giải pháp căn bản khi khối lượng công việc tiêu thụ ngay phần bộ nhớ tăng thêm (ví dụ: tác vụ phân tích có kích thước dữ liệu tăng tỷ lệ với bộ nhớ). Cuối cùng, cải thiện tính cục bộ là biện pháp ở cấp ứng dụng; có ví dụ kinh điển rằng chỉ cần đổi vòng lặp để duyệt mảng hai chiều theo thứ tự lưu trữ ưu tiên hàng là lỗi trang giảm hàng chục lần.

4. So sánh với các hiện tượng tương tự

Thrashing xuất hiện lặp lại ở nhiều tầng với tên gọi và cơ chế tương tự. Phân biệt chúng giúp chẩn đoán nhanh hơn.

Phân loại	Tầng phát sinh	Nguyên nhân	Triệu chứng
Page thrashing	Bộ nhớ ảo (khung trang)	Khung trang < tổng working set	Swapping bùng nổ, mức sử dụng CPU rơi mạnh
Cache thrashing	Cache line của CPU	Miss xung đột, false sharing	Tỷ lệ cache miss tăng vọt, IPC giảm
TLB thrashing	Cache dịch địa chỉ (TLB)	Tập làm việc > số mục TLB	TLB miss bùng nổ, tăng page walk

Ba hiện tượng tuy khác tầng nhưng chia sẻ cùng một nguyên lý: "tập làm việc cần chứa trong bộ lưu trữ nhanh nhỏ vượt quá dung lượng, khiến việc thay thế lặp lại không dứt". Ví dụ, trên đa nhân, chia sẻ giả (false sharing) — các nhân khác nhau luân phiên ghi các biến liền kề trong cùng một cache line — là ví dụ tiêu biểu của cache thrashing, và khi chèn đệm (padding) giữa các biến để tách line thì hiệu năng phục hồi đáng kể. Như vậy, thrashing không phải vấn đề riêng của một kỹ thuật cụ thể mà là mẫu hình phổ quát xuất hiện ở bất cứ đâu có cấu trúc "bộ lưu trữ nhanh hữu hạn + tập làm việc vượt quá".

5. Chuyên sâu — Thrashing trong môi trường hiện đại và cách đối phó

Dễ lầm tưởng rằng page thrashing truyền thống đã hiếm ngày nay khi bộ nhớ vật lý lớn lên, nhưng thực tế nó vẫn phổ biến dưới hình thức khác. Tiêu biểu là cấp phát vượt mức bộ nhớ (over-commit) trong môi trường container và ảo hóa. Trong Kubernetes, khi đặt limit bộ nhớ thấp cho pod hoặc cả node rơi vào trạng thái over-commit, đường thu hồi của nhân Linux liên tục đẩy trang ra, kswapd chiếm CPU, và cuối cùng OOM Killer buộc kết thúc tiến trình. Linux hiện đại cung cấp chỉ số PSI (Pressure Stall Information) để sớm nắm bắt tình huống này; nếu tỷ lệ some, full trong /proc/pressure/memory cao, nghĩa là các tác vụ đang dừng chờ thu hồi bộ nhớ, và đó thực chất là tín hiệu định lượng của thrashing.

Thay đổi chính sách swap cũng là điểm đáng chú ý. zram và zswap lưu các trang cần swap ở dạng nén trong bộ nhớ thay vì đĩa, thay thế I/O đĩa chậm bằng chi phí nén/giải nén, qua đó giảm nỗi đau cảm nhận của thrashing. Tuy nhiên, đây chỉ làm dịu triệu chứng, nếu tập làm việc vẫn tràn sau khi nén thì cuối cùng vẫn sụp đổ nên không phải giải pháp căn bản. Ngoài ra, các hệ thống tự quản lý bộ đệm như cơ sở dữ liệu và JVM cực kỳ kỵ swapping, nên thường áp dụng tinh chỉnh tắt swap (gần swappiness=0) hoặc ghim (pinning) bộ nhớ dung lượng lớn. Ngược lại, tắt hẳn swap thì mất dư địa, chỉ vượt một chút cũng đi thẳng tới OOM — một sự đánh đổi.

Ở tầm vĩ mô, sự mở rộng phân cấp bộ nhớ đang thay đổi địa hình của thrashing. Gộp và phân tầng bộ nhớ dựa trên CXL (Compute Express Link) đặt bộ nhớ từ xa làm tầng chậm hơn cục bộ, tạo ra phổ thrashing mới nơi "swap ra đĩa" được làm dịu thành "truy cập bộ nhớ từ xa". Trong môi trường này, chính sách phân tầng quản lý tỷ lệ truy cập theo tầng quyết định hiệu năng hơn là câu hỏi nhị phân "có thrashing hay không".

6. Những điểm cần lưu ý và hàm ý

Từ góc độ Kỹ sư chuyên nghiệp (Professional Engineer), thrashing cần được hiểu mở rộng không phải là một kỹ thuật đơn lẻ mà là nguyên lý thiết kế hệ thống "kiểm soát tranh chấp tài nguyên như thế nào".

Định nghĩa lại chỉ số quan sát — đừng chỉ nhìn mức sử dụng CPU. Khi thrashing, mức sử dụng CPU lại trông thấp, nên nếu chỉ phán đoán bằng mức sử dụng, OS và người vận hành sẽ mắc sai lầm chí mạng là chất thêm tải. Nhất thiết phải xây dựng hệ thống giám sát đa chỉ số quan sát đồng thời tỷ lệ lỗi trang, lượng swap in/out, áp lực bộ nhớ PSI và hàng đợi chờ đĩa. Nếu đối tượng quan sát sai, chính hướng can thiệp sẽ bị đảo ngược.
Chiến lược hai hướng: bảo đảm working set và kiểm soát tải. Biện pháp căn bản là bảo đảm cho mỗi tiến trình số khung bằng working set, và nếu tải lớn đến mức không thể làm vậy thì phải giảm mức độ đa chương trình. "Tăng tài nguyên" và "giảm tải" không phải là thay thế cho nhau mà là hai đòn bẩy để chọn tùy tình huống, và thrashing thường chỉ được giải quyết căn bản bằng cái sau.
Thiết kế tường minh các đánh đổi. Tắt swap mang lại rủi ro OOM thay cho thrashing, over-commit bộ nhớ mang lại rủi ro sụp đổ đổi lấy mật độ, zram mang lại tiết kiệm I/O đổi lấy chi phí CPU. Không lựa chọn nào miễn phí, nên cần thiết kế có chủ đích các đánh đổi theo đặc tính khối lượng công việc (tương tác vs lô, độ co giãn bộ nhớ).
Nhận thức tính phổ quát theo tầng. Thrashing không chỉ là vấn đề của bộ nhớ ảo mà tái hiện ở mọi nơi có "tài nguyên hữu hạn + nhu cầu vượt quá" như cache, TLB, connection pool, thread pool. Hiểu khái quát cấu trúc này giúp chẩn đoán và giải quyết cả các vấn đề như cạn connection pool hay bùng nổ chuyển ngữ cảnh luồng bằng cùng một khung (tập làm việc vs dung lượng).
Liên kết với chi phí đám mây và SLA. Trong môi trường tự động co giãn, thrashing dẫn đến chuỗi độ trễ phản hồi tăng vọt → tồn đọng yêu cầu → health check thất bại → thay thế instance, gây hại đồng thời cho chi phí và tính sẵn sàng. Đặt ngưỡng co giãn theo bộ nhớ và cấu hình limit/request dựa trên số đo working set thực tế là nhiệm vụ cốt lõi từ góc độ SRE.

Tài liệu tham khảo

Silberschatz, Galvin, Gagne, Operating System Concepts — Chương Thrashing, Working-Set Model, PFF
P. J. Denning, "The Working Set Model for Program Behavior" (1968)
Linux Kernel Documentation — Pressure Stall Information (PSI): https://docs.kernel.org/accounting/psi.html
Kubernetes Documentation — Node-pressure Eviction: https://kubernetes.io/docs/concepts/scheduling-eviction/node-pressure-eviction/

Tóm tắt một câu: Thrashing là hiện tượng tự củng cố trong đó đa chương trình quá mức làm lỗi trang bùng nổ, CPU chỉ lặp lại swapping và thông lượng sụp đổ; cần đối phó bằng bảo đảm working set, PFF và điều chỉnh mức độ đa chương trình, đồng thời tránh phán đoán sai khi chỉ nhìn mức sử dụng CPU và quản lý cả các chỉ số của môi trường hiện đại như over-commit container và PSI.