Bộ nhớ truy cập ngẫu nhiên và bộ nhớ đệm *¶

Trong hai phần đầu của chương này, chúng ta đã tìm hiểu về mảng và danh sách liên kết, hai cấu trúc dữ liệu cơ bản và quan trọng đại diện cho hai bố cục vật lý tương ứng là "lưu trữ liên tục" và "lưu trữ phân tán".

Trên thực tế, cấu trúc vật lý (physical structure) quyết định phần lớn hiệu quả mà chương trình sử dụng bộ nhớ và bộ đệm, từ đó ảnh hưởng đến hiệu năng tổng thể của các chương trình thuật toán.

Các thiết bị lưu trữ của máy tính¶

Máy tính bao gồm ba loại thiết bị lưu trữ: ổ cứng (hard disk), bộ nhớ truy cập ngẫu nhiên (RAM) và bộ nhớ đệm (cache). Bảng dưới đây cho thấy vai trò và đặc điểm hiệu năng khác nhau của chúng trong hệ thống máy tính.

Bảng Các thiết bị lưu trữ của máy tính

	Ổ cứng	RAM	Bộ nhớ đệm (Cache)
Mục đích	Lưu trữ dữ liệu dài hạn, bao gồm hệ điều hành, chương trình và tệp tin	Lưu trữ tạm thời các chương trình đang chạy và dữ liệu đang được xử lý	Lưu trữ dữ liệu và chỉ lệnh thường dùng để giảm số lần CPU truy cập bộ nhớ
Tính khả biến	Dữ liệu không bị mất sau khi tắt nguồn	Dữ liệu bị mất sau khi tắt nguồn	Dữ liệu bị mất sau khi tắt nguồn
Dung lượng	Lớn, cỡ Terabyte (TB)	Nhỏ, cỡ Gigabyte (GB)	Rất nhỏ, cỡ Megabyte (MB)
Tốc độ	Chậm, hàng trăm đến hàng nghìn MB/s	Nhanh, hàng chục GB/s	Rất nhanh, hàng chục đến hàng trăm GB/s
Chi phí	Rẻ, từ vài phần mười nhân dân tệ đến vài nhân dân tệ mỗi GB	Đắt, từ hàng chục đến hàng trăm nhân dân tệ mỗi GB	Rất đắt, thường được tích hợp trực tiếp vào CPU

Chúng ta có thể hình dung hệ thống lưu trữ máy tính như một kim tự tháp, như hình minh họa dưới đây. Các thiết bị lưu trữ càng gần đỉnh thì tốc độ càng nhanh, dung lượng càng nhỏ và giá thành càng đắt. Thiết kế nhiều lớp này là có chủ đích, là kết quả của sự cân nhắc kỹ lưỡng bởi các nhà khoa học máy tính và kỹ sư.

Không thể dễ dàng thay thế ổ cứng bằng RAM. Thứ nhất, dữ liệu trong bộ nhớ sẽ bị mất sau khi tắt nguồn, khiến nó không phù hợp để lưu trữ dữ liệu lâu dài. Thứ hai, bộ nhớ đắt gấp hàng chục lần so với ổ cứng, điều này khiến nó khó phổ biến ở thị trường tiêu dùng.
Bộ nhớ đệm không thể đồng thời đạt được dung lượng lớn và tốc độ cao. Khi dung lượng của các bộ đệm L1, L2 và L3 tăng lên, kích thước vật lý của chúng trở nên lớn hơn, và khoảng cách vật lý giữa chúng và nhân CPU tăng lên, dẫn đến thời gian truyền dữ liệu dài hơn và độ trễ truy cập phần tử cao hơn. Với công nghệ hiện tại, cấu trúc bộ nhớ đệm nhiều tầng đại diện cho điểm cân bằng tốt nhất giữa dung lượng, tốc độ và chi phí.

Tip

Hệ thống phân cấp lưu trữ của máy tính thể hiện sự cân bằng tinh tế giữa tốc độ, dung lượng và chi phí. Trên thực tế, những sự đánh đổi như vậy rất phổ biến trong mọi lĩnh vực công nghiệp, đòi hỏi chúng ta phải tìm ra điểm cân bằng tối ưu giữa các ưu điểm và hạn chế khác nhau.

Tóm lại, ổ cứng được sử dụng để lưu trữ dữ liệu lớn trong dài hạn, RAM được sử dụng để lưu trữ tạm thời dữ liệu đang được xử lý trong quá trình chạy chương trình, và bộ nhớ đệm được sử dụng để lưu trữ các dữ liệu và chỉ lệnh thường xuyên truy cập, từ đó nâng cao hiệu quả thực thi chương trình. Cả ba phối hợp với nhau giúp hệ thống máy tính hoạt động hiệu quả.

Như sơ đồ bên dưới, trong quá trình chạy chương trình, dữ liệu được đọc từ ổ cứng vào RAM để CPU tính toán. Bộ nhớ đệm có thể được xem là một phần của CPU. Bằng cách tải dữ liệu từ RAM một cách thông minh, nó cung cấp cho CPU khả năng truy cập dữ liệu tốc độ cao, cải thiện đáng kể hiệu quả thực thi chương trình và giảm sự phụ thuộc vào RAM vốn có tốc độ chậm hơn.

Hiệu quả bộ nhớ của cấu trúc dữ liệu¶

Về mặt sử dụng không gian bộ nhớ, mảng và danh sách liên kết mỗi loại đều có ưu điểm và hạn chế riêng.

Một mặt, bộ nhớ là có hạn và cùng một vùng nhớ không thể chia sẻ cho nhiều chương trình cùng lúc, so với điều đó chúng ta hy vọng cấu trúc dữ liệu có thể sử dụng không gian hiệu quả nhất có thể. Các phần tử mảng xếp khít nhau và không cần thêm không gian để lưu trữ tham chiếu (con trỏ) giữa các nút danh sách liên kết, do đó có hiệu quả không gian cao hơn. Tuy nhiên, mảng cần phân bổ đủ không gian bộ nhớ liên tục cùng một lúc, điều này có thể dẫn đến lãng phí bộ nhớ, và việc mở rộng mảng đòi hỏi thêm chi phí thời gian và không gian. Ngược lại, danh sách liên kết thực hiện phân bổ và giải phóng bộ nhớ động trên cơ sở từng "nút", mang lại tính linh hoạt cao hơn.

Mặt khác, trong quá trình chạy chương trình, khi bộ nhớ liên tục được phân bổ và giải phóng, mức độ phân mảnh của bộ nhớ trống ngày càng trở nên nghiêm trọng, dẫn đến giảm hiệu quả sử dụng bộ nhớ. Mảng, do phương thức lưu trữ liên tục, tương đối ít bị phân mảnh bộ nhớ hơn. Ngược lại, các phần tử danh sách liên kết được lưu trữ phân tán, và các thao tác chèn và xóa thường xuyên có nhiều khả năng gây ra phân mảnh bộ nhớ hơn.

Hiệu quả bộ nhớ đệm của cấu trúc dữ liệu¶

Mặc dù bộ nhớ đệm có dung lượng không gian nhỏ hơn nhiều so với bộ nhớ RAM, nhưng nó nhanh hơn nhiều so với bộ nhớ RAM và đóng vai trò quyết định đối với tốc độ chạy của chương trình. Vì dung lượng bộ nhớ đệm có hạn và chỉ có thể lưu trữ một phần nhỏ dữ liệu thường xuyên truy cập, khi CPU cố gắng truy cập dữ liệu không có trong cache, một sự kiện hụt bộ đệm (cache miss) sẽ xảy ra, và CPU buộc phải tải dữ liệu cần thiết từ bộ nhớ RAM có tốc độ chậm hơn.

Rõ ràng, càng ít "hụt bộ đệm", hiệu quả đọc ghi dữ liệu của CPU càng cao và hiệu năng chương trình càng tốt. Chúng ta gọi tỷ lệ dữ liệu mà CPU lấy thành công từ bộ nhớ đệm là tỷ lệ trúng bộ đệm (cache hit rate), một chỉ số thường được sử dụng để đo lường hiệu quả của bộ nhớ đệm.

Để đạt được hiệu quả cao nhất có thể, bộ nhớ đệm sử dụng các cơ chế nạp dữ liệu sau đây.

Dòng bộ đệm (cache line): Bộ nhớ đệm không lưu trữ và nạp dữ liệu theo từng byte mà theo các dòng bộ đệm. So với việc truyền dữ liệu theo từng byte, việc truyền theo dòng bộ đệm có hiệu quả cao hơn.
Cơ chế nạp trước (prefetching): Bộ vi xử lý cố gắng dự đoán các mẫu truy cập dữ liệu (ví dụ: truy cập tuần tự, truy cập nhảy bước cố định, v.v.) và nạp trước dữ liệu vào bộ nhớ đệm theo các mẫu cụ thể, từ đó nâng cao tỷ lệ trúng bộ đệm.
Tính cục bộ không gian (spatial locality): Nếu một dữ liệu được truy cập, dữ liệu gần đó cũng có khả năng được truy cập trong tương lai gần. Do đó, khi bộ nhớ đệm nạp một dữ liệu cụ thể, nó cũng nạp dữ liệu gần đó để nâng cao tỷ lệ trúng bộ đệm.
Tính cục bộ thời gian (temporal locality): Nếu một dữ liệu được truy cập, nó có khả năng cao sẽ được truy cập lại trong tương lai gần. Bộ nhớ đệm tận dụng nguyên lý này bằng cách giữ lại dữ liệu mới truy cập gần đây để nâng cao tỷ lệ trúng bộ đệm.

Trên thực tế, mảng và danh sách liên kết khác nhau về hiệu quả sử dụng bộ nhớ đệm, chủ yếu ở các khía cạnh sau.

Không gian chiếm dụng: Các phần tử danh sách liên kết chiếm nhiều không gian hơn phần tử mảng, vì vậy lượng dữ liệu hữu ích có thể chứa trong bộ nhớ đệm sẽ ít hơn.
Dòng bộ đệm: Dữ liệu danh sách liên kết phân tán khắp bộ nhớ, trong khi bộ nhớ đệm nạp dữ liệu "theo dòng", do đó tỷ lệ dữ liệu vô hiệu được nạp vào sẽ cao hơn.
Cơ chế nạp trước: Mảng có các mẫu truy cập dữ liệu dễ "dự đoán" hơn danh sách liên kết, giúp hệ thống dễ dàng đoán được dữ liệu nào sẽ được nạp tiếp theo.
Tính cục bộ không gian: Mảng được lưu trữ trong vùng nhớ tập trung, vì vậy dữ liệu gần dữ liệu được nạp có nhiều khả năng được truy cập sớm hơn.

Nhìn chung, mảng có tỷ lệ trúng bộ đệm cao hơn, do đó chúng thường vượt trội hơn danh sách liên kết về hiệu năng hoạt động. Điều này khiến các cấu trúc dữ liệu triển khai dựa trên mảng phổ biến hơn khi giải quyết các bài toán thuật toán.

Cần lưu ý rằng hiệu quả bộ nhớ đệm cao không có nghĩa là mảng vượt trội hơn danh sách liên kết trong mọi trường hợp. Trong ứng dụng thực tế, việc chọn cấu trúc dữ liệu nào nên được quyết định dựa trên các yêu cầu cụ thể. Ví dụ, cả mảng và danh sách liên kết đều có thể triển khai cấu trúc dữ liệu "ngăn xếp (stack)" (sẽ được thảo luận chi tiết trong chương tiếp theo), nhưng chúng phù hợp cho các kịch bản khác nhau.

Khi giải bài toán thuật toán, chúng ta có xu hướng ưu tiên triển khai ngăn xếp dựa trên mảng, vì chúng mang lại hiệu năng hoạt động cao hơn và khả năng truy cập ngẫu nhiên, với cái giá phải trả là cần phân bổ trước một lượng không gian bộ nhớ nhất định cho mảng.
Nếu lượng dữ liệu rất lớn, tính động cao và kích thước dự kiến của ngăn xếp khó ước lượng, thì triển khai ngăn xếp dựa trên danh sách liên kết sẽ phù hợp hơn. Danh sách liên kết có thể phân tán lượng dữ liệu lớn qua các phần khác nhau của bộ nhớ và tránh được chi phí phát sinh do mở rộng mảng.