Khi triển khai bộ đệm, điều quan trọng là phải có chính sách thay thế bộ đệm để xác định mục nào trong bộ đệm sẽ bị xóa khi bộ đệm đầy. Dưới đây là một số chính sách thay thế bộ đệm phổ biến nhất:
Least Recently Used – LRU
LRU là một chính sách thay thế bộ nhớ cache loại bỏ mục ít được truy cập gần đây nhất khỏi cache khi nó đầy. Chính sách này giả định rằng các mục được truy cập gần đây có khả năng sẽ được truy cập lại trong tương lai.
Thuật toán này yêu cầu theo dõi những gì đã được sử dụng và thời điểm sử dụng, điều này khá phức tạp. Nó yêu cầu các “age bits” cho các dòng cache và theo dõi dòng cache ít được sử dụng gần đây nhất dựa trên các age bits này. Khi một dòng cache được sử dụng, tuổi của các dòng cache khác sẽ thay đổi. LRU là một họ các thuật toán caching, bao gồm 2Q của Theodore Johnson và Dennis Shasha và LRU/K của Pat O’Neil, Betty O’Neil và Gerhard Weikum.
Least Frequently Used – LFU
LFU là một chính sách thay thế loại bỏ mục ít được truy cập nhất khỏi cache khi nó đầy. Chính sách này giả định rằng các mục đã được truy cập thường xuyên hơn sẽ có khả năng được truy cập lại trong tương lai.
Đây là một trong những thuật toán đơn giản và phổ biến nhất. Thuật toán này sẽ sắp xếp các mục dữ liệu của bạn dựa trên thời điểm truy cập. Mục dữ liệu mới truy cập sẽ đứng đầu tiên. Khi bộ nhớ cache đầy, nó sẽ xoá các mục ở dưới cùng (truy cập cách đây lâu nhất).
First In, First Out – FIFO
FIFO là một chính sách thay thế loại bỏ mục cũ nhất khỏi cache khi nó đầy. Chính sách này giả định rằng các mục cũ nhất trong cache ít có khả năng được truy cập lại trong tương lai.
Thuật toán FIFO sẽ xoá dữ liệu dựa vào thứ tự nó được thêm vào cache. Dữ liệu đầu tiên được lưu trữ trong cache (first in) sẽ được xoá đầu tiên (first out). Thuật toán này không xem xét thời gian truy cập hoặc theo dõi tần suất truy cập của dữ liệu. Do đó, dù dữ liệu mới được truy cập gần đây nhưng nó là một trong những dữ liệu đầu tiên được lưu trữ trong cache thì nó vẫn bị xoá.
Thuật toán FIFO khá đơn giản và dễ triển khai. Ngoài ra, nó còn được đánh giá cao về khả năng tận dụng tối đa bộ nhớ cache, đặc biệt khi dữ liệu truy cập gần đây quan trọng hơn dữ liệu cũ.
Random Replacement
Thay thế ngẫu nhiên là một chính sách thay thế loại bỏ một mục ngẫu nhiên khỏi cache khi nó đầy. Chính sách này không đưa ra giả định về khả năng truy cập trong tương lai và có thể hữu ích khi mô hình truy cập không dự đoán được.
Thuật toán Random Replacement sẽ chọn dữ liệu ngẫu nhiên để loại bỏ khi cần giải phóng dung lượng. Thuật toán này khá đơn giản. Tuy nhiên, nó có thể không tối ưu và không đảm bảo hiệu năng tốt trong nhiều trường hợp.
Adaptive Replacement Cache – ARC
Thuật toán ARC là sự kết hợp của thuật toán LRU và LRU-2 để tận dụng tối đa lợi ích. Thuật toán này sẽ chia bộ nhớ cache làm 2 phần:
- Phần phía trước gọi là T1 dùng để lưu trữ các dữ liệu mới gần đây. LRU quản lý T1. Khi T1 đầy, dữ liệu ít truy cập sẽ bị loại bỏ theo cơ chế của thuật toán LRU.
- Phần phía sau gọi là T2 dùng để lưu trữ các dữ liệu có tần suất truy cập cao. LRU-2 quản lý T2.
Khi cần giải phóng dung lượng cho dữ liệu mới, ARC sẽ xoá dữ liệu ít truy cập trong thời gian gần đây (LRU) và không có tần suất truy cập cao trong quá khứ (LRU-2).
Thuật toán ARC mang lại hiệu suất cao, nhất là trong trường hợp có sự biến đổi về tần suất truy cập dữ liệu.
Segmented LRU – SLRU
Thuật toán Segmented LRU là sự cải tiến của thuật toán LRU. Nó khắc phục các nhược điểm của LRU như: giảm thiểu khả năng dữ liệu được truy cập một lần lại chiếm một vị trí trong bộ nhớ cache trong thời gian dài và đẩy các mục thường xuyên được truy cập ra ngoài. Vì vậy, thuật toán SLRU giúp tối ưu hóa hiệu suất với các loại dữ liệu khác nhau. Vậy thuật toán SLRU hoạt động như thế nào?
Thuật toán SLRU chia cache thành hai phân đoạn:
- Phân đoạn thử nghiệm (Probationary Segment): Phân đoạn này sẽ lưu trữ dữ liệu mới được thêm vào cache. Nếu dữ liệu đó được truy cập lại, nó sẽ được chuyển sang phân đoạn bảo vệ.
- Phân đoạn bảo vệ (Protected Segment): Những dữ liệu đã được truy cập ít nhất hai lần sẽ được lưu trữ ở đây.
Nếu bộ nhớ cache ở một trong hai phân đoạn trên đầy, nó sẽ loại bỏ dữ liệu trong phân đoạn đó theo thuật toán LRU.
So Sánh Các Chính Sách Thay Thế Khác Nhau
Mỗi chính sách thay thế bộ nhớ cache đều có ưu và nhược điểm riêng, và chính sách tốt nhất phụ thuộc vào từng trường hợp sử dụng cụ thể. LRU và LFU thường hiệu quả hơn so với FIFO và random vì chúng dựa vào mô hình truy cập của cache. Tuy nhiên, LRU và LFU có thể đắt đỏ hơn khi triển khai vì cần duy trì các cấu trúc dữ liệu bổ sung để theo dõi mô hình truy cập. FIFO và thay thế ngẫu nhiên thì đơn giản hơn để triển khai nhưng có thể không tối ưu hiệu năng cache bằng. Do đó, chính sách thay thế bộ nhớ cache cần được lựa chọn cẩn thận để cân bằng giữa hiệu năng và độ phức tạp.
Để lại một bình luận