Bộ nhớ ảo và cơ chế phân trang theo yêu cầu

Bộ nhớ ảo là một khái niệm nền tảng trong hệ điều hành hiện đại, cho phép mỗi tiến trình hoạt động như thể nó sở hữu toàn bộ không gian địa chỉ liên tục và riêng biệt, bất kể dung lượng RAM vật lý thực tế có hạn. Cơ chế này được xây dựng dựa trên kỹ thuật phân trang: không gian địa chỉ logic của tiến trình được chia thành các đơn vị kích thước cố định gọi là trang, tương ứng với các khung trang (page frame) trong bộ nhớ vật lý.

Thay vì nạp toàn bộ chương trình vào RAM khi khởi động, phân trang theo yêu cầu (demand paging) chỉ tải những trang thực sự cần thiết vào bộ nhớ. Các trang còn lại được lưu trữ trên ổ đĩa (vùng swap hoặc file thực thi). Khi tiến trình truy cập đến một trang chưa nằm trong RAM, hệ thống sẽ tự động nạp nó vào thời điểm đó. Điều này giúp tối ưu hóa việc sử dụng bộ nhớ và cho phép chạy các ứng dụng lớn hơn dung lượng RAM sẵn có.

Xử lý lỗi trang (page fault)

Khi CPU truy xuất một địa chỉ mà trang tương ứng không tồn tại trong bộ nhớ vật lý (bit "present" trong mục bảng trang bị tắt), phần cứng sẽ phát sinh ngắt gọi là lỗi trang. Hệ điều hành xử lý sự kiện này theo quy trình sau:

1. Tạm dừng tiến trình gây lỗi và lưu trạng thái hiện tại.
2. Xác định vị trí trang trên đĩa từ địa chỉ logic và cấu trúc dữ liệu quản lý bộ nhớ.
3. Cấp phát khung trang trống. Nếu không còn khung trống, hệ thống phải chọn một trang hiện tại để thay thế (gọi là thuật toán thay thế trang).
4. Nạp trang từ đĩa vào khung trang, đồng thời cập nhật bảng trang (bật bit present, đặt bit sửa đổi nếu cần).
5. Khôi phục tiến trình và thực thi lại lệnh đã gây lỗi.

Quá trình này hoàn toàn minh bạch với tiến trình người dùng, nhưng số lần lỗi trang quá nhiều sẽ làm giảm hiệu năng nghiêm trọng do chi phí truy cập đĩa cao.

Các thuật toán thay thế trang

Mục tiêu chính của thuật toán thay thế trang là giảm thiểu số lần lỗi trang bằng cách chọn ra trang "ít có khả năng được dùng trong tương lai" để đưa ra ngoài. Dưới đây là hai thuật toán tiêu biểu.

Thuật toán LRU (Least Recently Used)

Nguyên lý: Thay thế trang được sử dụng lâu nhất trước đó. Giả định này dựa trên tính cục bộ – trang vừa mới được dùng có xu hướng tiếp tục được dùng. Để triển khai LRU, hệ thống cần theo dõi thời điểm truy cập cuối cùng của từng trang, dẫn đến chi phí phần cứng hoặc phần mềm khá cao.

Dưới đây là mô phỏng đơn giản dùng danh sách để duy trì thứ tự truy cập:

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.page_list = []  # Trang truy cập gần nhất ở cuối

    def access_page(self, page_id):
        if page_id in self.page_list:
            # Di chuyển trang lên cuối danh sách (sử dụng gần đây)
            self.page_list.remove(page_id)
            self.page_list.append(page_id)
            return False  # Không lỗi trang
        else:
            if len(self.page_list) == self.capacity:
                self.page_list.pop(0)  # Loại bỏ trang lâu nhất chưa dùng
            self.page_list.append(page_id)
            return True  # Phát sinh lỗi trang

# Ví dụ kiểm thử
cache_lru = LRUCache(3)
sequence = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
fault_count = sum(1 for p in sequence if cache_lru.access_page(p))
print(f"Số lỗi trang với LRU: {fault_count}")

Thuật toán Clock (Second Chance)

Đây là phương pháp xấp xỉ LRU với chi phí thấp hơn. Mỗi khung trang có một bit tham chiếu (reference bit). Khi trang được truy cập, bit này được phần cứng đặt thành 1. Con trỏ (gọi là "kim đồng hồ") quét vòng qua các khung trang:

• Nếu bit tham chiếu là 0 → chọn trang này để thay thế.
• Nếu bit là 1 → đặt lại thành 0 (tặng "cơ hội thứ hai") và tiếp tục di chuyển kim.

Triển khai mô phỏng như sau:

class ClockReplacement:
    def __init__(self, frame_count):
        self.size = frame_count
        self.pages = [-1] * frame_count     # Nội dung các khung
        self.ref_bits = [0] * frame_count   # Bit tham chiếu tương ứng
        self.pointer = 0                    # Kim đồng hồ

    def request_page(self, page_id):
        if page_id in self.pages:
            idx = self.pages.index(page_id)
            self.ref_bits[idx] = 1  # Cập nhật bit tham chiếu
            return False

        while True:
            if self.ref_bits[self.pointer] == 0:
                self.pages[self.pointer] = page_id
                self.ref_bits[self.pointer] = 1
                self.pointer = (self.pointer + 1) % self.size
                return True
            else:
                self.ref_bits[self.pointer] = 0
                self.pointer = (self.pointer + 1) % self.size

# Kiểm thử
clock_algo = ClockReplacement(3)
requests = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
page_faults = sum(1 for p in requests if clock_algo.request_page(p))
print(f"Số lỗi trang với Clock: {page_faults}")

Tổng kết

Bộ nhớ ảo kết hợp phân trang theo yêu cầu và xử lý lỗi trang cho phép hệ thống hỗ trợ các tiến trình với không gian địa chỉ lớn một cách minh bạch. Hiệu suất phụ thuộc lớn vào thuật toán thay thế trang: LRU mang lại hiệu quả lý thuyết tốt nhưng khó triển khai đầy đủ; trong khi thuật toán Clock cung cấp giải pháp thực tế, cân bằng giữa hiệu quả và chi phí, được sử dụng rộng rãi trong các hệ điều hành như Linux (dưới dạng cải tiến của NRU hay CLOCK). Việc nắm vững các cơ chế này giúp lập trình viên hiểu rõ hơn về hành vi bộ nhớ của ứng dụng và tối ưu hóa hiệu năng hệ thống.