Bộ nhớ ảo (Virtual Memory) và các thuật toán thay trang

1. Tổng quan

A. Định nghĩa

Bộ nhớ ảo là kỹ thuật quản lý bộ nhớ của hệ điều hành, cung cấp cho mỗi tiến trình một không gian địa chỉ liên tục và độc lập (không gian địa chỉ ảo) tách rời khỏi kích thước bộ nhớ vật lý, và chỉ giữ thường trú trong bộ nhớ vật lý phần thực sự cần cho việc thực thi. Phương tiện hiện thực cốt lõi của nó là phân trang theo yêu cầu (demand paging), còn quy tắc quyết định trang nào bị đẩy ra khi bộ nhớ vật lý đầy chính là thuật toán thay trang.

Ý tưởng căn bản của bộ nhớ ảo xuất phát từ nhận xét rằng "toàn bộ chương trình không nhất thiết phải cùng lúc nằm trong bộ nhớ." Hầu hết chương trình tại một thời điểm chỉ tham chiếu tập trung vào một phần vùng mã và dữ liệu (tính cục bộ), nên hệ thống vẫn hoạt động đúng nếu chỉ giữ phần đang thực thi trong bộ nhớ vật lý còn phần còn lại nằm trên đĩa (vùng swap). Hệ điều hành tạo ra ảo giác này qua MMU (Memory Management Unit) và bảng trang vốn dịch địa chỉ ảo thành địa chỉ vật lý, và lập trình viên có thể làm việc với một không gian địa chỉ lớn mà hầu như không phải ý thức về dung lượng bộ nhớ vật lý.

B. Bối cảnh ra đời và sự cần thiết

Trong các hệ thống buổi đầu, một chương trình chỉ chạy được nếu được nạp đầy đủ vào bộ nhớ vật lý. Ràng buộc này sinh ra hai vấn đề nghiêm trọng. Thứ nhất, chương trình lớn hơn bộ nhớ vật lý không thể chạy được, và lập trình viên phải tự thiết kế overlay để nạp luân phiên các mảnh mã. Thứ hai, mức độ đa chương trình bị trói vào dung lượng bộ nhớ vật lý, giới hạn số tiến trình chạy đồng thời. Bằng việc "chỉ nạp phần thực sự cần," bộ nhớ ảo cởi bỏ cả hai ràng buộc cùng lúc, cho phép vừa thực thi chương trình vượt quá bộ nhớ vật lý vừa đạt mức độ đa chương trình cao.

Trên hết, bộ nhớ ảo đã đơn giản hóa chính mô hình lập trình. Lập trình viên có thể viết mã với giả định về một không gian địa chỉ sạch, liên tục bắt đầu từ địa chỉ 0, hoàn toàn không bận tâm chương trình của mình được nạp ở đâu trong bộ nhớ vật lý hay chia sẻ không gian với chương trình khác ra sao. Đó là vì phần cứng và hệ điều hành xử lý việc tái định vị (relocation) và bảo vệ một cách trong suốt; nếu không có trừu tượng này, độ phức tạp của trình biên dịch, trình liên kết và trình nạp sẽ lớn hơn hiện nay một cách không thể so sánh.

Sự cần thiết ngày nay càng lớn. Trên một máy chủ có hàng trăm container và tiến trình chạy đồng thời, mỗi tiến trình dùng vài GB không gian địa chỉ ảo nhưng tập thường trú thực tế (RSS) chỉ là một phần nhỏ trong đó. Nếu không có bộ nhớ ảo, việc chia sẻ tài nguyên mật độ cao dựa trên overcommit như vậy là bất khả thi. Hơn nữa, sự cô lập các không gian địa chỉ ảo trở thành nền tảng của bảo vệ giữa các tiến trình (một tiến trình không thể xâm phạm bộ nhớ của tiến trình khác), và các chức năng cốt lõi của hệ điều hành hiện đại — chia sẻ bộ nhớ của thư viện dùng chung, ánh xạ tệp dựa trên mmap, và sao chép khi ghi (Copy-on-Write) — tất cả đều đứng trên bộ nhớ ảo.

C. Đặc điểm

Bộ nhớ ảo có vài đặc điểm bản chất. Thứ nhất là tính trong suốt: ứng dụng không cần biết rằng mình đang được phân trang theo yêu cầu. Thứ hai là sự phụ thuộc vào tính cục bộ: hiệu năng của bộ nhớ ảo tăng mạnh khi tính cục bộ theo thời gian và không gian của các tham chiếu càng tốt, và sụp đổ khi tính cục bộ tan vỡ. Thứ ba là sự gắn kết chặt với I/O đĩa: khi xảy ra lỗi trang, một lần truy cập đĩa hàng chục micro giây đến vài mili giây chen vào, gây độ trễ tương đương hàng nghìn đến hàng chục nghìn chu kỳ CPU. Chính khoảng chênh lệch chi phí khổng lồ này khiến chất lượng của thuật toán thay trang trong việc hạ tỷ lệ lỗi trang trở thành yếu tố quyết định hiệu năng hệ thống.

Những đặc điểm này bắt nguồn từ việc bộ nhớ ảo là một tầng của hệ thống phân cấp bộ nhớ (memory hierarchy). Trong hệ phân cấp chạy từ thanh ghi–cache–bộ nhớ chính–bộ nhớ phụ, bộ nhớ ảo tương ứng với cơ chế "dùng bộ nhớ chính như một cache của bộ nhớ phụ." Giống như cache CPU tự động thăng/giáng các khối của bộ nhớ chính, bộ nhớ ảo thăng các trang của đĩa lên bộ nhớ, và các khái niệm cục bộ, thay thế, nhất quán của caching được tái hiện nguyên vẹn ở cấp trang. Chỉ khác biệt quyết định là, vì chi phí trượt (lỗi) lớn gấp hàng nghìn lần một lần trượt cache, nên khác với cache do phần cứng đảm nhận hoàn toàn, phần mềm (hệ điều hành) can thiệp bằng chính sách tinh vi.

2. Cơ chế hoạt động của bộ nhớ ảo

Bộ nhớ ảo chia thành quá trình dịch địa chỉ ảo thành địa chỉ vật lý và quá trình lấy trang từ đĩa khi trang cần tham chiếu không có trong bộ nhớ vật lý. Dưới đây là sơ đồ cấu trúc tổng thể của dịch địa chỉ và phân trang theo yêu cầu.

flowchart TD
    CPU["CPU: sinh địa chỉ ảo"] --> TLB{"tra cứu TLB"}
    TLB -->|"trúng (hit)"| PA["tính địa chỉ vật lý"]
    TLB -->|"trượt (miss)"| PT["tra cứu bảng trang"]
    PT --> V{"bit hợp lệ (valid)?"}
    V -->|"1 (thường trú)"| PA
    V -->|"0 (trên đĩa)"| PF["phát sinh lỗi trang"]
    PF --> OS["bộ xử lý lỗi của OS"]
    OS --> FREE{"có khung trống?"}
    FREE -->|"có"| LOAD["nạp trang từ đĩa"]
    FREE -->|"không"| REPL["thuật toán thay trang<br/>chọn trang nạn nhân"]
    REPL --> DIRTY{"bit sửa đổi (dirty)?"}
    DIRTY -->|"1"| WB["ghi phần thay đổi về đĩa (write-back)"]
    DIRTY -->|"0"| LOAD
    WB --> LOAD
    LOAD --> UPD["cập nhật bảng trang và TLB"]
    UPD --> PA
    PA --> MEM["hoàn tất truy cập bộ nhớ"]

Cổng đầu tiên của dịch địa chỉ là TLB (Translation Lookaside Buffer). Nó lưu cache các ánh xạ ảo→vật lý dùng gần đây để hoàn tất phần lớn truy cập trong vài chu kỳ, và chỉ khi TLB trượt thì mới xảy ra việc duyệt bảng trang chậm (nhiều lần truy cập bộ nhớ trong bảng phân cấp). Mỗi mục bảng trang, cùng với số khung, chứa bit hợp lệ (thường trú hay không), bit sửa đổi (dirty), bit tham chiếu (reference) và bit bảo vệ, làm cơ sở cho quyết định của thuật toán thay trang và cơ chế bảo vệ.

Dịch địa chỉ ẩn chứa một biến thiết kế quan trọng: kích thước trang. Trang nhỏ giảm phân mảnh trong nhưng tăng số mục bảng trang và áp lực lên TLB, còn trang lớn cải thiện hiệu quả của bảng và TLB nhưng tăng tổn thất "nạp cả vùng không cần" và phân mảnh trong. Việc các hệ điều hành đa dụng giữ 4KB làm mặc định lâu dài chính là điểm cân bằng lịch sử của sự đánh đổi này, và các trang khổng lồ bàn ở Mục 5 là lựa chọn cố ý phá vỡ mặc định này cho các tải công việc nhất định để cực đại hóa hiệu quả TLB.

A. Phân trang theo yêu cầu và xử lý lỗi trang

Phân trang theo yêu cầu chỉ nạp trang vào đúng khoảnh khắc nó được tham chiếu. Khi tham chiếu một trang có bit hợp lệ bằng 0, phần cứng gây bẫy (trap) và phát sinh lỗi trang, rồi bộ xử lý của OS xử lý theo thứ tự ①kiểm tra tính hợp lệ của địa chỉ → ②bảo đảm một khung trống (thay trang nếu không có) → ③nạp trang từ đĩa → ④cập nhật bảng trang và TLB → ⑤thực thi lại lệnh đã lỗi. Lúc này nếu bit sửa đổi của trang nạn nhân bằng 1 thì phải ghi về đĩa trước (write-back), cần hai lần I/O đĩa, còn nếu bằng 0 thì có thể bỏ qua việc ghi — đây là lý do ưu tiên "trang sạch" khi chọn đối tượng thay thế.

B. Các chức năng cốt lõi mà bộ nhớ ảo nâng đỡ — CoW và ánh xạ bộ nhớ

Bộ nhớ ảo không chỉ là một thiết bị "mở rộng bộ nhớ" mà là nền tảng trên đó nhiều chức năng cốt lõi của hệ điều hành hiện đại đứng vững. Tiêu biểu là sao chép khi ghi (Copy-on-Write). Vì sao chép ngay toàn bộ bộ nhớ của tiến trình cha khi tạo tiến trình con qua fork() sẽ tốn kém khổng lồ, nên hệ điều hành cho hai tiến trình chia sẻ cùng một khung vật lý ở chế độ chỉ đọc và chỉ sao chép trang đó vào đúng khoảnh khắc một bên thử ghi. Sao chép trì hoãn này không thể hiện thực nếu thiếu tầng dịch (bit bảo vệ của bảng trang) và cơ chế lỗi trang, và nó loại bỏ gần như toàn bộ việc sao chép thừa trong mẫu hình phổ biến exec ngay sau fork.

Một chức năng khác là ánh xạ bộ nhớ (mmap). Khi ánh xạ một tệp vào không gian địa chỉ ảo, tệp được xử lý chỉ bằng truy cập con trỏ mà không cần lời gọi hệ thống read/write, nhân chỉ nạp các khối cần thiết qua phân trang theo yêu cầu, và ghi trả phần thay đổi một cách trì hoãn. Việc nhiều tiến trình chia sẻ một bản mã vật lý cho thư viện dùng chung, và việc ánh xạ một trang heap mới lên khung chung đã được điền 0 qua demand zeroing rồi chỉ cấp khung thật vào thời điểm ghi, đều theo cùng một nguyên lý. Như vậy bộ nhớ ảo nâng hiệu quả hệ thống theo ba trục: bảo vệ, chia sẻ và cấp phát trì hoãn.

C. Thời gian truy cập hiệu dụng và độ nhạy hiệu năng

Hiệu năng của phân trang theo yêu cầu được định lượng bằng thời gian truy cập hiệu dụng (EAT). Nếu tỷ lệ lỗi trang là p, thời gian truy cập bộ nhớ là ma, thời gian xử lý lỗi là pft thì EAT = (1-p)×ma + p×pft. Chẳng hạn với ma=100ns, pft=8ms (8,000,000ns), ngay cả tỷ lệ lỗi chỉ 0,1% (p=0.001) cũng khiến EAT ≈ 100×0.999 + 8,000,000×0.001 ≈ 8,100ns, vọt lên khoảng 80 lần so với trường hợp không lỗi. Phép tính cho thấy để giữ suy giảm hiệu năng trong 10%, phải giữ tỷ lệ lỗi dưới khoảng 1/800,000. Độ nhạy cực đoan này cho thấy bằng con số vì sao một thuật toán thay trang "giảm lỗi tối đa" và việc bảo đảm tính cục bộ lại mang tính sống còn.

3. Các thuật toán thay trang

Để đưa một trang mới vào khi bộ nhớ vật lý đầy, phải đẩy ra một trang hiện có. Mục tiêu là cực tiểu hóa tỷ lệ lỗi bằng cách giữ lại các trang sắp được dùng lại và đẩy ra các trang sẽ không dùng trong một thời gian. Dưới đây là luồng ra quyết định của các thuật toán tiêu biểu.

flowchart LR
    REQ["cần thay trang"] --> OPT["OPT: thay trang<br/>không dùng lâu nhất trong tương lai"]
    REQ --> FIFO["FIFO: thay trang<br/>vào sớm nhất"]
    REQ --> LRU["LRU: thay trang<br/>ít được tham chiếu gần đây nhất"]
    REQ --> CLOCK["Clock (cơ hội thứ hai):<br/>thay bit tham chiếu 0"]
    OPT -.->|"không hiện thực được, cận dưới lý thuyết"| BENCH["chuẩn so sánh hiệu năng"]
    FIFO -.->|"có thể gặp nghịch lý Belady"| SIMPLE["đơn giản nhưng kém hiệu quả"]
    LRU -.->|"phản ánh cục bộ, chi phí hiện thực"| GOOD["xấp xỉ gần tối ưu"]
    CLOCK -.->|"xấp xỉ LRU, chi phí thấp"| REAL["được dùng trong thực tế"]

A. OPT (thay thế tối ưu) và cận dưới lý thuyết

OPT (Optimal, thuật toán Belady) thay "trang sẽ không được tham chiếu trong thời gian dài nhất phía trước." Vì phải biết chuỗi tham chiếu tương lai nên không thể hiện thực thực tế, nhưng nó cung cấp cận dưới lý thuyết của số lỗi tối thiểu có thể đạt và được dùng làm thước đo để đánh giá các thuật toán khác. Chẳng hạn chạy chuỗi tham chiếu 7 0 1 2 0 3 0 4 2 3 0 3 2 với 3 khung, OPT được xử lý với ít lỗi hơn FIFO hay LRU, và một thuật toán thực tế tiến gần OPT đến đâu trở thành thước đo chất lượng thiết kế.

B. FIFO và nghịch lý Belady

FIFO thay trang được nạp sớm nhất. Hiện thực đơn giản, nhưng có điểm mù là đẩy ra cả "trang vào đã lâu nhưng vẫn được dùng liên tục." Nghiêm trọng hơn là nghịch lý Belady (Belady's Anomaly), hiện tượng phản trực giác — xuất hiện ở FIFO — trong đó tăng số khung lại khiến lỗi tăng. Chuỗi tham chiếu 1 2 3 4 1 2 5 1 2 3 4 5 là phản ví dụ kinh điển, sinh nhiều lỗi hơn với 4 khung so với 3 khung. Điều này cho thấy FIFO hoàn toàn không phản ánh tính cục bộ, và nghịch lý không xảy ra ở LRU hay OPT vốn có tính chất thuật toán ngăn xếp.

C. LRU và các xấp xỉ của nó

LRU (Least Recently Used) thay "trang ít được tham chiếu gần đây nhất." Dựa trên giả định cục bộ rằng mẫu tham chiếu quá khứ sẽ tiếp diễn trong tương lai gần, nó cho hiệu năng gần OPT, nhưng LRU chính xác phải cập nhật dấu thời gian ở mỗi lần tham chiếu hoặc duy trì danh sách thứ tự tham chiếu, nên chi phí phần cứng lớn. Vì vậy thực tế dùng kỹ thuật xấp xỉ. Tiêu biểu là thuật toán Clock (cơ hội thứ hai), sắp các khung thành vòng tròn và kiểm tra bit tham chiếu — nếu là 1 thì xóa về 0 và đi tiếp (thêm một cơ hội), gặp 0 thì thay. Clock cải tiến, cũng xét bit sửa đổi, ưu tiên thay trang "không được tham chiếu + sạch," tiết kiệm cả write-back. Các hệ điều hành thực tế như Linux và Windows dùng biến thể của họ Clock này kết hợp với danh sách LRU đa cấp (active/inactive) và lão hóa (aging).

Bảng dưới đây so sánh các thuật toán tiêu biểu theo hiệu năng, chi phí và đặc tính. Vì chỉ bảng không làm lộ ra "tại sao," cần đọc kèm nguyên nhân của khác biệt.

Thuật toán	Tiêu chí thay	Hiệu năng lỗi	Chi phí hiện thực	Nghịch lý Belady	Ứng dụng thực tế
OPT	không dùng lâu nhất tương lai	tối ưu (cận dưới)	không hiện thực được	không	dùng làm chuẩn đánh giá
FIFO	thứ tự nạp	kém	rất thấp	xảy ra	hầu như không dùng
LRU	ít dùng gần đây	xuất sắc	cao (HW)	không	chỉ dạng xấp xỉ
Clock	quét bit tham chiếu	tốt (xấp xỉ LRU)	thấp	không (xấp xỉ)	dùng rộng rãi
LFU	tần suất tham chiếu nhỏ nhất	tùy tình huống	trung bình	có thể	hạn chế (cache v.v.)

Gốc rễ của khác biệt hiệu năng nằm ở "dự đoán tương lai tốt đến đâu." FIFO chỉ nhìn thời điểm nạp và bỏ qua mẫu sử dụng nên không có năng lực dự đoán; LRU xấp xỉ tương lai bằng tính cục bộ "nếu dùng gần đây thì sẽ sớm dùng lại" nên mạnh. Clock bắt chước năng lực dự đoán của LRU một cách rẻ tiền bằng một bit tham chiếu, nắm được điểm cân bằng giữa hiệu năng và chi phí, nên thống trị thực tế. LFU mạnh với các trang phổ biến lâu dài, nhưng vướng vấn đề ô nhiễm cache khi một trang được dùng nhiều trong một đợt bùng phát ban đầu rồi bị bỏ lại cứ bám trụ vì số đếm tần suất cao, nên phải dùng kèm kỹ thuật lão hóa.

D. Ví dụ so sánh bằng số — cùng chuỗi tham chiếu, kết quả khác nhau

Để cảm nhận khác biệt giữa các thuật toán, đếm trực tiếp số lỗi trong cùng điều kiện là hữu hiệu. Giả sử 3 khung và chuỗi tham chiếu 2 3 2 1 5 2 4 5 3 2 5 2. FIFO, chỉ nhìn thứ tự nạp, vô tư đẩy ra một trang (2) sẽ được dùng lại về sau, làm lỗi tăng; LRU giữ lại 2 và 5 vừa được tham chiếu, làm lỗi giảm; còn OPT, biết tương lai, đẩy ra trang được dùng muộn nhất, cho số lỗi tối thiểu. Nói chung với chuỗi này số lỗi xuất hiện theo thứ tự OPT < LRU ≤ FIFO, tái hiện trật tự kinh điển trong sách giáo khoa nơi LRU gần với cận dưới do OPT đặt ra còn FIFO tụt lại xa nhất. Điểm cốt lõi là ngay cùng một dung lượng bộ nhớ (số khung), chỉ riêng chính sách thay thế đã có thể làm thay đổi lớn tỷ lệ lỗi, và kết hợp với độ nhạy EAT ở Mục 2, khác biệt số lỗi này có thể bị khuếch đại thành khác biệt hàng chục lần về hiệu năng cảm nhận.

Trật tự này không phải lúc nào cũng cố định. Nếu chuỗi tham chiếu thiếu tính cục bộ rõ ràng và gần ngẫu nhiên thì không thuật toán nào tiến gần OPT, và có khi FIFO tình cờ giống LRU hoặc bị vượt bởi nghịch lý Belady. Nghĩa là ưu thế của một thuật toán thay trang phụ thuộc vào mẫu tham chiếu, nên về nguyên tắc người thiết kế đo tỷ lệ lỗi trên vết thực của tải công việc mục tiêu để chọn chính sách.

Chính sách thay thế trong thực tế còn tiến thêm một bước và xét cả khả năng chống quét (scan). Một tác vụ đọc tuần tự một tệp lớn chỉ một lần đẩy vô số trang lên đỉnh LRU và tống khứ các trang hay dùng; để ngăn điều này, Linux có cấu trúc thăng cấp hai giai đoạn không thăng ngay một trang mới vào lên active mà chỉ thăng sau khi xác nhận tái tham chiếu trên danh sách inactive. Các chính sách của vùng đệm cơ sở dữ liệu như LRU-K, 2Q và ARC cũng là sản phẩm của cùng mối bận tâm, tách "dùng một lần" khỏi "dùng nhiều lần" để một lần quét tuần tự không thể làm ô nhiễm cache.

4. Cấp phát khung và thrashing — vì sao chỉ thay trang là chưa đủ

A. Chính sách cấp phát khung

Dù thuật toán thay trang tốt đến đâu, nếu số khung cấp cho một tiến trình nhỏ hơn tập làm việc của nó thì lỗi bùng nổ. Cấp phát khung chia thành cấp phát cố định (đều, tỷ lệ) và cấp phát biến đổi, đồng thời phân biệt thành thay thế cục bộ vốn giới hạn phạm vi thay thế trong khung của chính tiến trình và thay thế toàn cục vốn lấy từ toàn bộ. Thay thế toàn cục có thể dồn khung cho các tiến trình năng động, nhưng lỗi của một tiến trình có thể cướp khung của tiến trình khác và gây suy giảm hiệu năng dây chuyền.

Việc chọn phương thức cấp phát phơi bày nguyên vẹn căng thẳng giữa công bằng và hiệu quả. Cấp phát đều cho mọi tiến trình cùng số khung, đơn giản, nhưng tiến trình nhỏ thì thừa khung còn tiến trình lớn lại thiếu. Cấp phát tỷ lệ chia theo tỷ lệ kích thước không gian địa chỉ ảo để làm nhẹ điều này, nhưng rơi vào cái bẫy "lớn không có nghĩa là dùng năng động." Vì vậy các hệ điều hành hiện đại lấy cấp phát biến đổi + thay thế toàn cục làm cơ sở, điều chỉnh theo thời gian thực qua quan sát hành vi lỗi, đồng thời đặt một chặn trên như giới hạn bộ nhớ cgroup để sự chạy loạn của một tiến trình không kéo cả hệ thống xuống.

B. Thrashing và mô hình tập làm việc

Cực điểm của vấn đề này là thrashing. Nâng mức độ đa chương trình quá mức làm khung của mỗi tiến trình co lại dưới tập làm việc, rơi vào trạng thái CPU không làm việc mà chỉ bám lấy việc thay trang (I/O đĩa). Lúc này nạp thêm tiến trình để tăng mức sử dụng CPU rơi vào vòng luẩn quẩn làm thrashing tăng tốc. Lời giải là mô hình tập làm việc (Working Set Model), coi tập trang (WS) được tham chiếu trong cửa sổ thời gian Δ gần nhất là số khung mà tiến trình cần, và điều chỉnh mức độ đa chương trình sao cho tổng kích thước WS của mọi tiến trình không vượt quá số khung vật lý. Một cách tiếp cận khác, PFF (Page Fault Frequency), cấp thêm khung khi tỷ lệ lỗi vượt chặn trên và thu hồi khi nó rơi dưới chặn dưới, điều khiển tỷ lệ lỗi về một dải mục tiêu. (※ Chi tiết về thrashing xem [[thrashing]], các kỹ thuật phân chia bộ nhớ xem [[paging-vs-segmentation]].)

Là một trường hợp cụ thể, trên một máy chủ Linux eo hẹp bộ nhớ, khi áp lực bộ nhớ tăng, kswapd không ngừng thu hồi trang và I/O swap đĩa vọt lên, các cột si/so của vmstat đột biến, và hệ thống gần như đình trệ — một cảnh trong đó thrashing của sách giáo khoa được tái hiện nguyên văn ở hiện trường vận hành. Đây chính là lý do nhiều tổ chức giới hạn swap trên các dịch vụ như vậy hoặc thiết kế kèm giới hạn bộ nhớ cgroup và chính sách OOM.

5. Nâng cao — Bộ nhớ ảo trong hệ điều hành và phần cứng hiện đại

A. Mở rộng bảng trang và TLB

Lý thuyết kinh điển vẫn còn hiệu lực, nhưng các hệ thống hiện đại đã mở rộng mạnh bộ nhớ ảo theo nhịp của quy mô và tiến bộ phần cứng. Thứ nhất là bảng trang đa cấp và bảng trang đảo. Xử lý không gian địa chỉ 64 bit bằng bảng trang tuyến tính khiến chính bảng lớn phi thực tế, nên x86-64 dùng bảng trang phân cấp 4–5 tầng và đặt TLB đa cấp cùng các cache bảng để giảm chi phí duyệt bảng. Thứ hai là trang khổng lồ (Huge Page, 2MB, 1GB), phóng to kích thước trang để một mục TLB phủ một vùng rộng, nâng tỷ lệ trúng TLB và giảm số lần duyệt bảng — các trường hợp hiệu năng cải thiện vài đến vài chục phần trăm được báo cáo ở cơ sở dữ liệu, heap JVM lớn và ảo hóa. Thứ ba là phân trang lồng (EPT/NPT) của ảo hóa, trong đó phần cứng xử lý dịch hai tầng khách ảo → khách vật lý → chủ vật lý, loại bỏ chi phí của bảng trang bóng (shadow) bằng phần mềm.

Chi phí ẩn của mở rộng này là độ trễ của chính việc dịch địa chỉ. Khi TLB trượt trong bảng trang 5 tầng, cần tới năm lần truy cập bộ nhớ, và trong phân trang lồng, một lần dịch của chủ còn chen vào ở mỗi tầng, nên trong trường hợp xấu nhất có thể xảy ra tới 24 lần truy cập bộ nhớ. Vì vậy phần cứng đặt một cache chuyên dụng (page-walk cache) lưu các tầng trên của bảng trang, còn phần mềm nâng tỷ lệ trúng TLB nhờ trang khổng lồ và tính cục bộ truy cập bộ nhớ để bù chi phí này — tức là mở rộng "phóng to bảng trang" và tối ưu "làm nhanh việc dịch" luôn tiến song đôi.

Trang khổng lồ không miễn phí. Có báo cáo về các trường hợp trang khổng lồ trong suốt (THP) chiếm dụng bộ nhớ quá mức, hoặc độ trễ dồn nén bộ nhớ (compaction) khi nhân gom các trang nhỏ để bảo đảm một trang khổng lồ làm xấu đi độ trễ đuôi. Vì vậy trong vận hành cơ sở dữ liệu, nhiều nhà cung cấp khuyến nghị tắt THP và chỉ dùng trang khổng lồ tường minh qua hugetlbfs — một ví dụ thực cho thấy ngay cả quyết định bật/tắt một tính năng phần cứng cũng có thể phản tác dụng nếu thiếu đặc tính tải công việc và đo lường.

B. Bộ nhớ phân tầng và sự tiến hóa của chính sách thu hồi

Các xu hướng gần đây cũng sôi động. Mở rộng bộ nhớ dựa trên CXL và bộ nhớ phân tầng (tiered memory) phân tầng DRAM và bộ nhớ từ xa chậm, với hệ điều hành tự động thăng/giáng các trang nóng và lạnh — đây về bản chất là "đa tầng hóa việc thay trang" (liên quan: [[cxl]]). MGLRU (Multi-Gen LRU) của Linux là một cải tiến tiêu biểu từ 2022 mở rộng LRU hai cấp active/inactive truyền thống thành nhiều thế hệ, nâng độ chính xác và hiệu quả của quyết định thu hồi trên bộ nhớ quy mô lớn. Ngoài ra, Copy-on-Write, demand zeroing và nén bộ nhớ (zswap/zram) đều là các kỹ thuật tiết kiệm bộ nhớ vật lý ở tầng bộ nhớ ảo, nâng mật độ của các môi trường container dày đặc.

Nén bộ nhớ đặc biệt được chú ý như một thay thế cho swap đĩa. Thay vì đẩy các trang lạnh ra đĩa chậm, nén chúng bằng CPU và giữ trong bộ nhớ (zram, zswap) có thể mở rộng bộ nhớ hiệu dụng mà không cần I/O đĩa. Bí quyết để Android giữ nhiều ứng dụng ở nền trên RAM hạn chế chính là zram, và trên các node Kubernetes cũng vậy, việc bật swap nén để giảm OOM kill đang gia tăng. Điều này cho thấy câu hỏi bản chất của bộ nhớ ảo — "đặt một trang ở đâu và dưới hình thức nào" — đang mở rộng sang các kho lưu nền đa dạng: đĩa, nén và bộ nhớ từ xa.

6. Điểm cân nhắc và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)

Chiến lược áp dụng — chọn chính sách theo tải công việc: dịch vụ nhạy độ trễ (web, DB) nên kìm hãm swap và bảo đảm trang khổng lồ cùng đủ khung tập làm việc để chặn lỗi một cách cấu trúc, còn tải công việc theo lô và phân tích nên nâng mật độ bằng cách khai thác overcommit bộ nhớ và bộ nhớ phân tầng — phải thiết kế tách biệt chính sách bộ nhớ phù hợp mục đích. Không có thiết lập tối ưu duy nhất, và phân tích tính cục bộ tham chiếu phải đi trước.
Quản lý đánh đổi: kích thước trang là cân bằng giữa phân mảnh trong (lớn) và hiệu quả TLB (lớn), overcommit là cân bằng giữa mật độ (cao) và rủi ro OOM (cao), còn thay thế toàn cục/cục bộ là cân bằng giữa hiệu quả tổng thể và cô lập giữa các tiến trình. Năng lực đo lường định lượng các mâu thuẫn này qua vmstat, perf và tỷ lệ lỗi rồi tinh chỉnh là điều được đòi hỏi.
Thể chế hóa hệ thống quan sát và kiểm chứng: chất lượng bộ nhớ ảo hiện ra không ở giá trị trung bình mà ở phân bố của tỷ lệ lỗi, I/O swap, tỷ lệ trượt TLB và lỗi chính (major fault), nên nếu thiếu một hệ quan sát đo liên tục các chỉ số này, gắn chúng với SLO và cảnh báo sớm các dấu hiệu thrashing thì việc tinh chỉnh hiệu năng mất căn cứ.
Liên kết với lập kế hoạch dung lượng: bộ nhớ ảo cho phép dùng vượt bộ nhớ vật lý, nhưng điều đó không có nghĩa là bộ nhớ vô hạn. Ngay khoảnh khắc tổng các tập làm việc vượt bộ nhớ vật lý, hiệu năng sụp đổ phi tuyến, nên khi lập kế hoạch dung lượng máy chủ và container cần một nguyên tắc thiết kế cấp phát bộ nhớ dựa trên nhu cầu đo được căn cứ vào RSS và tập làm việc, và chỉ dùng swap như một lưới an toàn.
Liên kết với bảo mật và cô lập: cô lập địa chỉ ảo là nền tảng của bảo vệ tiến trình, nhưng các kênh phụ của thực thi suy đoán như Meltdown và Spectre đã khai thác các đường dịch địa chỉ và TLB (liên quan: [[speculative-execution-branch-prediction]]). Vì các biện pháp giảm nhẹ như cô lập bảng trang nhân (KPTI) hy sinh hiệu năng, thiết kế quản lý bộ nhớ nay phải xử lý cả đánh đổi bảo mật–hiệu năng.
Bảo đảm tính cục bộ như một nguyên tắc thiết kế: dù tinh chỉnh thuật toán thay trang đến đâu, nếu tính cục bộ tham chiếu của chính chương trình kém thì không thể chặn lỗi. Tối ưu tính cục bộ ở cấp ứng dụng — bố trí bộ nhớ của cấu trúc dữ liệu (mảng so với danh sách liên kết), thứ tự truy cập của vòng lặp (ưu tiên hàng so với ưu tiên cột), thiết kế hướng dữ liệu — phải song hành với quản lý bộ nhớ của hệ điều hành thì hiệu năng mới hoàn chỉnh, và Kỹ sư chuyên nghiệp phải có khả năng bao quát cùng lúc cơ chế bên dưới và thiết kế bên trên.
Triển vọng và công nghệ liên kết: bộ nhớ phân tầng CXL, MGLRU và nén bộ nhớ hội tụ về hướng "quản lý một tầng dung lượng lớn chậm bằng chính sách thay thế," và sắp tới bộ nhớ ảo sẽ tiến hóa vượt DRAM thành một động cơ bố trí dữ liệu cai quản toàn bộ hệ phân cấp bộ nhớ không đồng nhất. Trực tiếp giáp ranh với quản lý tài nguyên đám mây ([[finops]]) và mật độ container, hiểu các nguyên lý bộ nhớ của hệ điều hành trở thành nền tảng của tối ưu chi phí hạ tầng.

Tài liệu tham khảo

Operating System Concepts (Silberschatz et al.), chương "Virtual Memory"
Arpaci-Dusseau, "Operating Systems: Three Easy Pieces" — Paging/Swapping/Policy — https://pages.cs.wisc.edu/~remzi/OSTEP/
Linux Kernel Documentation, "Multi-Gen LRU" — https://docs.kernel.org/admin-guide/mm/multigen_lru.html
Denning, P., "The Working Set Model for Program Behavior" (CACM, 1968) — nguồn gốc của mô hình tập làm việc

Tóm tắt một câu: Bộ nhớ ảo là kỹ thuật chỉ nạp các trang cần thiết qua phân trang theo yêu cầu để cung cấp không gian địa chỉ vượt bộ nhớ vật lý và sự cô lập tiến trình; vì cực kỳ nhạy với tỷ lệ lỗi nên nó chặn thrashing bằng các thuật toán thay trang như OPT, FIFO, LRU, Clock và bằng cấp phát khung dựa trên tập làm việc, và ở thời hiện đại đang mở rộng sang trang khổng lồ, phân trang lồng, MGLRU và bộ nhớ phân tầng CXL.