Quản lý bộ nhớ trong hệ điều hành: Phân trang và phân đoạn

1. Tổng quan

A. Định nghĩa

Phân trang (Paging) là kỹ thuật quản lý bộ nhớ không liên tục, chia bộ nhớ vật lý thành các khung trang (frame) có kích thước bằng nhau và chia không gian địa chỉ logic của tiến trình thành các trang (page) cùng kích thước, rồi bố trí rải rác trong bộ nhớ vật lý theo đơn vị trang. Phân đoạn (Segmentation) là kỹ thuật quản lý bằng cách chia chương trình thành các đoạn (segment) có kích thước thay đổi theo đơn vị logic như mã·dữ liệu·ngăn xếp.

Cả hai kỹ thuật đều là phương thức cấp phát không liên tục để hiện thực bộ nhớ ảo (Virtual Memory), có điểm chung là bố trí chương trình rải rác khắp bộ nhớ vật lý và thông qua chuyển đổi địa chỉ (address translation) khiến tiến trình thấy như thể bộ nhớ là liên tục. MMU (Memory Management Unit) chuyển địa chỉ logic (ảo) mà tiến trình sử dụng thành địa chỉ vật lý tại thời điểm thực thi, nhờ đó chương trình không cần biết vị trí thực trong bộ nhớ vật lý và có thể dùng không gian địa chỉ lớn hơn bộ nhớ thực.

Tuy nhiên, 'chia theo tiêu chí nào' là khác nhau căn bản. Phân trang cắt một cách cơ học theo kích thước định sẵn (ví dụ: 4KB) bất kể ý nghĩa của chương trình, còn phân đoạn cắt theo đơn vị ý nghĩa logic của chương trình (hàm·mảng·ngăn xếp, v.v.). Chỉ một khác biệt này đã phân tách toàn bộ các đặc tính về phân mảnh·bảo vệ·chia sẻ. Phân trang có kích thước mảnh đồng đều nên quản lý không gian trống đơn giản, nhưng bỏ qua ranh giới logic nên bảo vệ·chia sẻ không tự nhiên; phân đoạn tự nhiên về mặt logic và dễ bảo vệ·chia sẻ, nhưng kích thước mỗi đoạn một khác nên quản lý không gian trống phức tạp.

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

Phương thức cấp phát liên tục (contiguous allocation) ban đầu phải nạp toàn bộ tiến trình vào 'một vùng liên tục duy nhất' của bộ nhớ vật lý. Cách này có hai hạn chế rõ rệt. Thứ nhất, khi các tiến trình liên tục được nạp vào và gỡ ra, phân mảnh — các khoảng trống nhỏ rải rác khắp bộ nhớ — trở nên trầm trọng, dẫn đến tình huống tổng dung lượng đủ nhưng không nạp được tiến trình lớn. Thứ hai, chương trình lớn hơn bộ nhớ vật lý hoàn toàn không thể thực thi.

Phân trang·phân đoạn giải quyết vấn đề này bằng cách chia nhỏ tiến trình và bố trí rải rác trong bộ nhớ vật lý. Toàn bộ tiến trình không cần nạp liên tục nên có thể tận dụng bộ nhớ một cách dày đặc, và hiện thực không gian địa chỉ lớn hơn bộ nhớ vật lý nhờ phân trang theo yêu cầu (demand paging) — chỉ nạp vào bộ nhớ những mảnh cần ngay, phần còn lại để trên đĩa (vùng swap). Đây là nền tảng khiến mọi hệ điều hành đa dụng ngày nay đều có bộ nhớ ảo.

2. Khái niệm và cấu trúc chuyển đổi địa chỉ

Trước tiên nhìn tổng quan cấu trúc của hai kỹ thuật, sau đó xem xét quy trình chuyển đổi địa chỉ của từng kỹ thuật.

flowchart TB
  V["Quản lý bộ nhớ không liên tục<br/>(dựa trên bộ nhớ ảo)"] --> P["Phân trang(Paging)"]
  V --> S["Phân đoạn(Segmentation)"]
  P --> P1["Chia kích thước cố định<br/>(ví dụ: trang/khung 4KB)"]
  P --> P2["Bảng trang<br/>(page# → frame#)"]
  P --> P3["Phát sinh phân mảnh trong"]
  S --> S1["Chia biến đổi theo đơn vị logic<br/>(mã·dữ liệu·ngăn xếp)"]
  S --> S2["Bảng đoạn<br/>(base + limit)"]
  S --> S3["Phát sinh phân mảnh ngoài"]
  style V fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

Chuyển đổi địa chỉ trong phân trang. Phân trang diễn giải địa chỉ ảo thành hai phần 'số trang (page number) + độ dời trong trang (offset)'. MMU dùng số trang để tìm số khung (frame number) tương ứng trong bảng trang (page table) của từng tiến trình, rồi ghép với độ dời để hoàn thành địa chỉ vật lý. Vì kích thước trang và khung bằng nhau nên độ dời được giữ nguyên, và nếu kích thước là lũy thừa của 2 (ví dụ: 4KB=2^12) thì các bit thấp của địa chỉ chính là độ dời, các bit cao là số trang, nên việc chuyển đổi được xử lý bằng phép chia bit đơn giản. Tính quy tắc này là cốt lõi giúp phân trang có thể hiện thực nhanh bằng phần cứng.

Chuyển đổi địa chỉ trong phân đoạn. Phân đoạn diễn giải địa chỉ ảo thành 'số đoạn + độ dời trong đoạn'. MMU dùng số đoạn để lấy địa chỉ bắt đầu (base) và giới hạn (limit) của đoạn đó từ bảng đoạn (segment table). Nếu độ dời nhỏ hơn limit thì tính địa chỉ vật lý bằng 'base + độ dời', nếu lớn hơn hoặc bằng limit thì đó là truy cập vượt ranh giới đoạn nên phát sinh trap (ngoại lệ) để ngăn xâm phạm bộ nhớ của tiến trình khác. Tức là phân đoạn có đặc điểm đặt base·limit·quyền (đọc/ghi/thực thi) cho mỗi đơn vị logic nên bảo vệ và chia sẻ diễn ra tự nhiên.

flowchart LR
  A["Địa chỉ ảo"] --> B{"Phương thức chia"}
  B -->|Phân trang| C["Trang# + độ dời"]
  C --> D["Tra bảng trang"]
  D --> E["Khung# + độ dời<br/>= địa chỉ vật lý"]
  B -->|Phân đoạn| F["Đoạn# + độ dời"]
  F --> G["Bảng đoạn<br/>(base·limit)"]
  G --> H{"Độ dời < limit?"}
  H -->|Có| I["base + độ dời<br/>= địa chỉ vật lý"]
  H -->|Không| J["Trap vi phạm bảo vệ"]
  style E fill:#e6f4ea,stroke:#34a853
  style I fill:#e6f4ea,stroke:#34a853
  style J fill:#fce8e6,stroke:#d93025

3. Vấn đề phân mảnh: trong vs ngoài

Điều hết sức quan trọng là điểm yếu quyết định của hai kỹ thuật là hai loại phân mảnh khác nhau. Phân mảnh là 'bộ nhớ có thể dùng nhưng thực tế không được dùng và bị lãng phí', và việc nó phát sinh ở phía nào đã định đoạt số phận của mỗi kỹ thuật.

Phân trang sinh ra phân mảnh trong (Internal Fragmentation). Vì kích thước trang cố định, nếu kích thước tiến trình không phải là bội số nguyên của kích thước trang thì trang cuối cùng thường không được lấp đầy. Không gian thừa này đã được cấp cho trang đó nên tiến trình khác không dùng được và bị lãng phí. Lượng lãng phí tối đa mỗi tiến trình là 'kích thước trang − 1', trung bình khoảng một nửa kích thước trang. Ví dụ, với trang 4KB và tiến trình 10KB, 3 trang (12KB) được cấp và khoảng 2KB bị bỏ phí do phân mảnh trong. Nếu giảm kích thước trang để giảm lãng phí này thì bảng trang lại lớn lên, phát sinh xung đột đánh đổi.

Phân đoạn sinh ra phân mảnh ngoài (External Fragmentation). Vì kích thước các đoạn khác nhau, khi cấp phát·giải phóng lặp đi lặp lại, các mảnh không gian trống lớn nhỏ rải rác khắp bộ nhớ. Phát sinh tình huống tổng các mảnh đó đủ nhưng không có không gian lớn liên tục, nên không nạp được đoạn lớn. Để giảm nhẹ điều này cần nén (compaction) — dồn các không gian trống rải rác về một phía — nhưng việc này tốn chi phí lớn để di chuyển các tiến trình đang chạy nên khó thực hiện thường xuyên. Chính độ khó quản lý phân mảnh ngoài này là lý do căn bản khiến phân đoạn thuần túy bị đẩy khỏi dòng chủ lưu.

Tóm lại, phân mảnh trong là 'không gian không dùng được bên trong mảnh đã cấp', phân mảnh ngoài là 'không gian không dùng được rải rác giữa các mảnh'. Phân trang làm kích thước mảnh đồng đều để loại bỏ tận gốc phân mảnh ngoài, đổi lại chấp nhận một lượng nhỏ phân mảnh trong; còn phân đoạn có được sự tự nhiên về logic nhưng phải gánh phân mảnh ngoài — hai lựa chọn hoàn toàn trái ngược.

4. Phân đoạn có phân trang (kỹ thuật kết hợp) và ứng dụng thực tế

Để chỉ lấy ưu điểm của hai kỹ thuật, kiến trúc hiện đại dùng phân đoạn có phân trang (Paged Segmentation) — chia đoạn thành các trang. Chia chương trình thành các đoạn là đơn vị logic để có lợi ích bảo vệ·chia sẻ, đồng thời chia mỗi đoạn thành các trang kích thước cố định và bố trí rải rác trong bộ nhớ vật lý để loại bỏ phân mảnh ngoài. Đây là phương án thỏa hiệp kết hợp ưu điểm logic của phân đoạn với sự tiện lợi quản lý vật lý của phân trang. Khi đó, chuyển đổi địa chỉ diễn ra theo thứ tự 'bảng đoạn → bảng trang (của đoạn đó) → khung', đi qua bảng hai lần.

Tình huống thực tế — kiến trúc x86. x86 thời đầu (80386) là ví dụ tiêu biểu kết hợp phân tầng phân đoạn và phân trang. Tuy nhiên, các hệ điều hành thực tế (Linux·Windows) đặt base của đoạn là 0, limit là tối đa, thực chất vô hiệu hóa phân đoạn (flat memory model) và vận hành lấy phân trang làm trung tâm. Và trên 64 bit (x86-64), phần lớn chức năng kiểm tra base·limit của phân đoạn đã bị loại bỏ, cho thấy rõ rằng quản lý bộ nhớ của OS đa dụng ngày nay có phân trang đa cấp là dòng chủ lưu tuyệt đối. Điều này chứng minh thực tế rằng 'tính đơn giản trong quản lý và loại bỏ phân mảnh ngoài (phân trang)' có giá trị lớn hơn 'sự thanh nhã logic (phân đoạn)'.

Tình huống thực tế — không gian địa chỉ lớn và bảng trang đa cấp. Trong không gian địa chỉ 64 bit, một bảng trang đơn lẻ sẽ lớn đến mức phi thực tế. Vì vậy Linux phân tầng thành bảng trang 4~5 cấp, chỉ tạo bảng con cho những vùng địa chỉ thực sự được dùng khi cần, tiết kiệm bộ nhớ dành cho bảng. Đây là cách thực tiễn để phân trang mở rộng lên các hệ thống quy mô lớn.

Phân trang theo yêu cầu (Demand Paging) và thay thế trang. Cơ chế thực tế giúp phân trang hiện thực không gian địa chỉ lớn hơn bộ nhớ vật lý là phân trang theo yêu cầu. Không nạp mọi trang của tiến trình vào bộ nhớ ngay từ đầu, mà chỉ nạp trang đó từ đĩa vào đúng thời điểm thực sự truy cập (lỗi trang, page fault). Nhờ đó, tiến trình hoạt động như thể toàn bộ không gian địa chỉ của mình nằm trong bộ nhớ, nhưng thực tế chỉ các trang đang hoạt động (working set) chiếm bộ nhớ vật lý.

Khi cần trang mới trong trạng thái bộ nhớ vật lý đã đầy, thuật toán thay thế trang can thiệp để quyết định đẩy trang nào ra. Có LRU (thay trang lâu nhất không được tham chiếu), Clock (xấp xỉ LRU), tối ưu (OPT), v.v., và mấu chốt hiệu năng là tránh thrashing — thay thế quá thường xuyên đến mức tiến trình không làm được việc gì mà chỉ lặp lại vào/ra trang. Việc phân đoạn là đơn vị kích thước thay đổi nên khó thay thế·nạp đồng đều như vậy cũng là một trong những lý do phân trang trở thành tiêu chuẩn của bộ nhớ ảo.

5. Chuyên sâu: TLB và hiệu năng, hướng ra đề dự kiến

Tăng tốc bằng TLB (Translation Lookaside Buffer). Chi phí căn bản của phân trang là phải 'truy cập bảng trang (bộ nhớ) để chuyển đổi địa chỉ', và với bảng đa cấp thì truy cập này lặp lại theo số cấp. Tức là để đọc dữ liệu một lần lại phải đọc bộ nhớ nhiều lần. Để giảm nhẹ, trong MMU đặt TLB — bộ nhớ kết hợp siêu tốc lưu cache các kết quả chuyển đổi gần đây (trang→khung). Khi TLB trúng (hit) thì lấy ngay địa chỉ vật lý mà không cần truy cập bộ nhớ, chỉ khi trượt (miss) mới duyệt bảng trang. Tỷ lệ trúng TLB thường rất cao, trên 99%, nên chi phí chuyển đổi của phân trang thực chất phần lớn được che giấu. Trang khổng lồ (Huge Page, ví dụ: 2MB·1GB) khiến một mục TLB đảm nhận vùng rộng hơn, nâng tỷ lệ trúng TLB và cải thiện hiệu năng của các khối lượng công việc thâm dụng bộ nhớ như cơ sở dữ liệu·ảo hóa.

Xu hướng mới nhất. Trong môi trường ảo hóa, phân trang lồng (Nested/Extended Page Tables) — tăng tốc bằng phần cứng việc chuyển đổi địa chỉ kép khách-chủ — đã trở thành tiêu chuẩn, và về mặt bảo mật, quyền theo đơn vị trang (ngăn thực thi bằng bit NX) và ASLR (ngẫu nhiên hóa bố trí không gian địa chỉ) được hiện thực trên cấu trúc phân trang. Tức là phân trang đang mở rộng vượt ra ngoài việc tiết kiệm bộ nhớ đơn thuần, trở thành cơ chế nền tảng bao trùm hiệu năng·ảo hóa·bảo mật.

Hướng ra đề dự kiến. Trong kỳ thi Kỹ sư chuyên nghiệp, các dạng thường được yêu cầu là: (1) giải thích khái niệm·chuyển đổi địa chỉ của phân trang và phân đoạn kèm hình vẽ, (2) đối chiếu khác biệt và nguyên nhân phát sinh của phân mảnh trong và phân mảnh ngoài, (3) luận về cách phân đoạn có phân trang kết hợp hai kỹ thuật, (4) trình bày vai trò của TLB·bảng trang đa cấp·phân trang theo yêu cầu từ góc độ hiệu năng. Bài làm triển khai theo thứ tự 'định nghĩa→cấu trúc chuyển đổi địa chỉ→so sánh phân mảnh→kết hợp/thực tiễn→hiệu năng (TLB) và hàm ý' sẽ có tính hoàn chỉnh.

6. Các điểm cần cân nhắc và hàm ý

Dưới góc nhìn Kỹ sư chuyên nghiệp, khi thiết kế·đánh giá kỹ thuật quản lý bộ nhớ cần cân nhắc tổng hợp các điểm sau.

1. Do tính nghiêm trọng của phân mảnh ngoài, nền tảng phân trang đã trở thành dòng chủ lưu. Phân đoạn thuần túy thanh nhã về logic và có lợi cho bảo vệ·chia sẻ, nhưng chi phí quản lý phân mảnh ngoài (nén) lớn nên các hệ thống hiện đại chọn phân trang hoặc phân đoạn có phân trang. Khi thiết kế cần nhận thức rõ sự đánh đổi giữa 'sự tự nhiên logic' và 'chi phí quản lý phân mảnh'.

2. Đánh đổi trong lựa chọn kích thước trang. Trang nhỏ thì phân mảnh trong giảm nhưng bảng trang lớn lên và hiệu quả TLB giảm. Trang lớn thì ngược lại. Giải pháp thực tiễn là dùng song song trang cơ bản và trang khổng lồ tùy theo đặc tính khối lượng công việc (truy cập ngẫu nhiên vs truy cập tuần tự khối lớn).

3. Chi phí chuyển đổi địa chỉ và sự phụ thuộc vào TLB. Chi phí chuyển đổi của phân trang đa cấp phụ thuộc vào tỷ lệ trúng TLB, nên các mẫu truy cập hay trượt TLB (truy cập ngẫu nhiên quy mô lớn) suy giảm hiệu năng nhiều. Cần giảm nhẹ bằng trang khổng lồ·thiết kế cấu trúc dữ liệu thân thiện với TLB, và khi tinh chỉnh hiệu năng phải quan sát TLB miss như chỉ số cốt lõi.

4. Phân trang như nền tảng bảo vệ·bảo mật. Quyền theo đơn vị trang (đọc/ghi/thực thi), bit NX, ASLR, cô lập không gian địa chỉ giữa các tiến trình đều được hiện thực trên cấu trúc phân trang. Quản lý bộ nhớ không chỉ là vấn đề hiệu quả mà là nền tảng của bảo mật·ổn định hệ thống, nên trong môi trường có yêu cầu thực thi tin cậy·cô lập càng cao thì thiết kế tầng này càng quan trọng.

5. Mở rộng sang ảo hóa·đám mây. Phân trang lồng, cấp phát vượt bộ nhớ (overcommit), chia sẻ trang (KSM) gắn trực tiếp với mật độ tài nguyên của đám mây. Để đồng thời đạt được cô lập hiệu năng và hiệu quả bộ nhớ trong môi trường đa tenant, cần hiểu đặc tính của tầng phân trang và điều phối cấu hình hypervisor.

Tài liệu tham khảo

• A. Silberschatz, "Operating System Concepts", tổng quan Memory Management: https://www.os-book.com/
• Linux Kernel Documentation, "Page Tables": https://docs.kernel.org/mm/page_tables.html
• Intel 64 and IA-32 Architectures Software Developer Manuals(Paging): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

Tóm tắt một câu: Phân trang chia theo kích thước cố định nên có phân mảnh trong, phân đoạn chia theo đơn vị logic kích thước thay đổi nên có phân mảnh ngoài; OS hiện đại kết hợp ưu điểm của cả hai bằng phân đoạn có phân trang (chia đoạn thành trang) và phân trang đa cấp, tăng tốc chuyển đổi địa chỉ bằng TLB, và tầng này là nền tảng chung của hiệu năng·ảo hóa·bảo mật.