Page table trong hệ điều hành

Page table là một cấu trúc dữ liệu được sử dụng bởi hệ thống bộ nhớ ảo để lưu trữ ánh xạ giữa địa chỉ logic và địa chỉ vật lý.

Địa chỉ logic được tạo ra bởi CPU cho các trang của quy trình, do đó chúng thường được các quy trình sử dụng.

Địa chỉ vật lý là địa chỉ khung thực của bộ nhớ. Chúng thường được sử dụng bởi phần cứng hoặc cụ thể hơn là bởi các hệ thống con RAM.

Các bài viết liên quan:

• Tự học html: table
• Mô hình Domain Logic, cách tổ chức Domain logic
• Hướng dẫn Table Layout trong android
• Viết bài bán hàng Sale Page
• Tìm hiểu về Paging trong hệ điều hành
• Địa chỉ nhị phân của bộ nhớ máy tính trong hệ điều hành

Giới thiệu về Page table

Page table (bảng trang) là một cấu trúc dữ liệu quan trọng trong hệ điều hành, được sử dụng để quản lý bộ nhớ ảo trong môi trường hệ thống có hỗ trợ bộ nhớ ảo. Page table là một phần của cơ chế dịch địa chỉ ảo thành địa chỉ vật lý, cho phép các quá trình trong hệ thống truy cập đến bộ nhớ ảo một cách hiệu quả.

Page table được sử dụng trong kiến trúc bộ nhớ ảo phân trang (paging), trong đó không gian địa chỉ của quá trình được chia thành các trang (pages) có kích thước cố định. Mỗi trang có một địa chỉ ảo và một địa chỉ vật lý tương ứng. Page table chứa các mục (entry) tương ứng với các trang trong không gian địa chỉ ảo, và mỗi mục trong page table chứa thông tin về trang đó, chẳng hạn như địa chỉ vật lý tương ứng của trang đó.

Xem thêm Kích thước của page table trong hệ điều hành

Khi quá trình cần truy cập đến một địa chỉ ảo, hệ điều hành sẽ sử dụng page table để chuyển đổi địa chỉ ảo thành địa chỉ vật lý. Quá trình này bao gồm việc tìm kiếm trong page table để xác định trang tương ứng, và sau đó sử dụng địa chỉ vật lý từ mục tương ứng để truy cập đến bộ nhớ thực.

Page table đóng vai trò quan trọng trong việc cung cấp không gian địa chỉ ảo rộng hơn so với bộ nhớ vật lý thực tế có sẵn. Nó cho phép hệ điều hành quản lý quá trình truy cập bộ nhớ một cách linh hoạt và hiệu quả, đồng thời giúp giảm bớt việc cần có bộ nhớ vật lý lớn hơn.

Tuy nhiên, việc sử dụng page table cũng đòi hỏi bộ nhớ để lưu trữ các mục trong page table, và quá trình truy xuất page table có thể tốn thời gian. Do đó, các kỹ thuật tối ưu hóa page table cũng được áp dụng để cải thiện hiệu suất và sử dụng bộ nhớ một cách hiệu quả trong hệ thống.

Tóm lại, page table là cấu trúc dữ liệu quan trọng trong hệ điều hành, sử dụng để quản lý bộ nhớ ảo và cung cấp khả năng truy cập bộ nhớ linh hoạt. Nó đóng vai trò quan trọng trong việc dịch địa chỉ ảo thành địa chỉ vật lý và giúp tăng cường hiệu suất và linh hoạt của hệ thống.

Hình ảnh đưa ra dưới đây cho thấy,

Không gian địa chỉ vật lý = M từ

Không gian địa chỉ logic = L từ

Trang Kích thước = P từ

Địa chỉ vật lý = log ₂ M = m bit

Địa chỉ logic = log ₂ L = l bit

Độ lệch trang = log ₂ P = p bit

CPU luôn truy cập các tiến trình thông qua các địa chỉ logic của chúng. Tuy nhiên, bộ nhớ chính chỉ nhận ra địa chỉ vật lý.

Trong tình huống này, một đơn vị có tên là Đơn vị quản lý bộ nhớ đã vào cuộc. Nó chuyển đổi số trang của địa chỉ logic thành số khung của địa chỉ vật lý. Sự bù đắp vẫn giống nhau trong cả hai địa chỉ.

Để thực hiện tác vụ này, bộ phận Quản lý bộ nhớ cần một loại ánh xạ đặc biệt được thực hiện bởi Page table. Page table lưu trữ tất cả các số Khung tương ứng với các số trang của Page table.

Nói cách khác, Page table ánh xạ số trang đến vị trí thực của nó (số khung) trong bộ nhớ.

Trong hình ảnh được đưa ra bên dưới cho thấy, từ cần thiết của khung được truy cập như thế nào với sự trợ giúp của offset.

Xem thêm Cách Run android App trong android studio

Cấu trúc của Page table

Cấu trúc của page table trong hệ điều hành thường được tổ chức dưới dạng một mảng hoặc danh sách các mục (entry), mỗi mục đại diện cho một trang trong không gian địa chỉ ảo. Mỗi mục trong page table chứa thông tin về trang tương ứng, bao gồm địa chỉ vật lý tương ứng của trang đó và các thông số khác liên quan.

Cấu trúc của mỗi mục trong page table có thể khác nhau tùy thuộc vào kiến trúc của hệ điều hành cụ thể, nhưng thông thường, nó bao gồm các trường thông tin sau:

1. Trường Địa chỉ vật lý (Physical Address): Đây là địa chỉ vật lý tương ứng của trang trong bộ nhớ thực. Khi trang được truy cập, hệ điều hành sẽ sử dụng địa chỉ vật lý này để truy cập đến trang trong bộ nhớ.
2. Các trường kiểm soát (Control Bits): Các trường này chứa các thông tin quản lý và kiểm soát liên quan đến trang, bao gồm:
   • Bit có hiệu lực (Valid/Invalid bit): Được sử dụng để xác định xem trang có hiệu lực (đang được sử dụng và có địa chỉ vật lý tương ứng) hay không. Nếu bit này là không hiệu lực, nghĩa là trang đó chưa được tải vào bộ nhớ vật lý.
   • Bit cấp độ bảo mật (Protection bit): Xác định cấp độ bảo mật của trang, cho phép kiểm soát quyền truy cập đến trang từ các quá trình khác nhau.
   • Bit thay đổi (Dirty bit): Được đánh dấu khi trang được sửa đổi sau khi được nạp vào bộ nhớ. Bit này cho phép hệ điều hành quản lý việc lưu trữ trang thay đổi vào bộ nhớ thực.
   • Bit trang nhớ (Reference bit): Được đánh dấu khi trang được truy cập. Bit này giúp hệ điều hành quản lý và theo dõi việc sử dụng trang.
3. Các trường khác (Optional): Ngoài các trường trên, page table cũng có thể chứa các trường khác, như các trường để xử lý kiểm tra lỗi (error checking) hoặc các trường mở rộng để lưu trữ thông tin bổ sung về trang.

Tổng quan, cấu trúc của page table bao gồm các mục chứa thông tin về các trang trong không gian địa chỉ ảo, giúp quản lý và dịch địa chỉ ảo thành địa chỉ vật lý tương ứng trong bộ nhớ thực.

Xem thêm Giao thức Mạng trong TCP/IP

Cách hoạt động của Page table

Page table hoạt động như một bản đồ ánh xạ giữa không gian địa chỉ ảo và không gian địa chỉ vật lý trong hệ thống bộ nhớ ảo. Khi một quá trình trong hệ thống cần truy cập đến một địa chỉ ảo, hệ điều hành sử dụng page table để dịch địa chỉ ảo thành địa chỉ vật lý tương ứng.

Quá trình hoạt động của page table thông thường như sau:

1. Quá trình tạo và cấu hình page table: Trước khi một quá trình bắt đầu thực thi, hệ điều hành tạo và cấu hình page table cho quá trình đó. Page table có thể được tạo và cấu hình trong vùng nhớ chung hoặc được lưu trữ trong các cấu trúc dữ liệu riêng.
2. Truy cập đến địa chỉ ảo: Khi quá trình cần truy cập đến một địa chỉ ảo, hệ điều hành sẽ sử dụng page table để xác định địa chỉ vật lý tương ứng.
3. Tìm kiếm trong page table: Hệ điều hành sẽ tìm kiếm trong page table để xác định mục (entry) tương ứng với trang ảo được yêu cầu. Quá trình tìm kiếm được thực hiện thông qua việc so sánh địa chỉ trang ảo với các mục trong page table.
4. Kiểm tra bit hiệu lực và quyền truy cập: Khi một mục trong page table được tìm thấy, hệ điều hành kiểm tra bit hiệu lực (valid/invalid bit) để đảm bảo rằng trang là hiệu lực và đã được tải vào bộ nhớ vật lý. Ngoài ra, hệ điều hành cũng kiểm tra các quyền truy cập trong mục để đảm bảo rằng quá trình có quyền truy cập vào trang đó.
5. Dịch địa chỉ ảo thành địa chỉ vật lý: Nếu trang là hiệu lực và quyền truy cập hợp lệ, hệ điều hành sử dụng địa chỉ vật lý từ mục tương ứng trong page table để dịch địa chỉ ảo thành địa chỉ vật lý. Địa chỉ vật lý này sẽ được sử dụng để truy cập đến bộ nhớ thực.
6. Truy cập đến bộ nhớ vật lý: Cuối cùng, quá trình có thể truy cập đến bộ nhớ thực thông qua địa chỉ vật lý được dịch từ địa chỉ ảo.

Quá trình trên được lặp lại cho mỗi truy cập đến địa chỉ ảo, và page table đóng vai trò quan trọng trong việc xác định và cung cấp địa chỉ vật lý tương ứng để quá trình có thể truy cập đến bộ nhớ một cách chính xác và hiệu quả.

Xem thêm Virtual Memory trong hệ điều hành

Tối ưu hóa Page table

Tối ưu hóa page table là quá trình cải thiện hiệu suất và sử dụng bộ nhớ của page table trong hệ thống bộ nhớ ảo. Dưới đây là một số phương pháp tối ưu hóa phổ biến:

1. Paging tầng: Một phương pháp tối ưu hóa phổ biến là sử dụng các cấp độ của page table. Thay vì duy nhất một page table lớn, ta sử dụng nhiều bảng trang nhỏ hơn, được tổ chức theo cấp độ. Khi truy cập đến một địa chỉ ảo, hệ điều hành chỉ cần truy cập vào page table cấp độ thích hợp thay vì tìm kiếm trong toàn bộ page table. Điều này giảm thời gian truy cập và giúp tiết kiệm bộ nhớ.
2. Page table cây: Một cấu trúc page table được sử dụng phổ biến là cây page table. Trong cây page table, các mục page table được tổ chức theo cấu trúc cây, với các mục con đại diện cho các trang con của trang cha. Cấu trúc cây này giúp giảm số lượng mục cần lưu trữ trong page table và giảm thời gian truy cập. Các thuật toán cây như cây B hoặc cây Patricia có thể được sử dụng để cải thiện hiệu suất tìm kiếm trong page table.
3. Page table thưa (Sparse page table): Trong hệ thống bộ nhớ ảo lớn, không phải tất cả các trang đều được sử dụng. Page table thưa là một kỹ thuật tối ưu hóa cho phép chỉ lưu trữ các mục page table cho các trang thực sự được sử dụng. Các trang không sử dụng sẽ không có mục tương ứng trong page table, giảm bộ nhớ được sử dụng cho page table và tăng tốc độ truy cập.
4. Caching page table: Một phương pháp tối ưu hóa khác là caching page table. Thay vì truy cập page table từ bộ nhớ chính mỗi khi cần, một bộ nhớ cache có thể được sử dụng để lưu trữ các mục page table được truy cập gần đây nhất. Việc sử dụng caching page table giúp giảm thời gian truy cập và tăng tốc độ của việc dịch địa chỉ ảo thành địa chỉ vật lý.
5. Tối ưu hóa bộ nhớ: Cuối cùng, tối ưu hóa bộ nhớ tổng thể có thể cải thiện hiệu suất page table. Điều này bao gồm việc sử dụng các kỹ thuật như nén page table, sử dụng các cấu trúc dữ liệu hiệu quả, và quản lý bộ nhớ một cách tối ưu để giảm bộ nhớ phụ và tăng tốc độ truy cập.

Tổng quát, tối ưu hóa page table nhằm tăng hiệu suất và tiết kiệm bộ nhớ trong hệ thống bộ nhớ ảo. Các phương pháp trên có thể được kết hợp hoặc tùy chỉnh phù hợp với kiến trúc và yêu cầu cụ thể của hệ thống.

Xem thêm Virtual Dedicated Server là gì?