Translation Lookaside Buffers

Bảng trang sử dụng trong kỹ thuật phân trang (Paging) là một danh sách liên kết và chỉ có thể tìm kiếm tuần tự. Do đó mà chi phí tìm kiếm frame number của bảng trang là rất lớn.

Để có thể giảm thiểu chi phí tìm kiếm, ta có thể sử dụng translation lookaside buffers (TLB) có bản chất là một mảng với index là các page numbers:

Khi cần truy xuất một trang nào đó, hệ thống sẽ tra ở trong TLB trước, nếu tìm thấy thì có thể lấy ra được ngay frame number mà không cần phải duyệt qua từng entry trong bảng trang một cách tuần tự.

Ngược lại, nếu không thể tìm thấy frame number ở trong TLB, MMU cần phải tìm ở trong bảng trang và bộ nhớ chính như bình thường.

Ta gọi trường hợp tìm thấy frame number ở trong TLB là hit và không tìm thấy là miss.

Effective Access time

Thời gian truy xuất hiệu dụng (effective access time - EAT): khoảng thời gian trung bình cho một lần truy xuất dữ liệu.

$$EAT=(ϵ+n)\alpha +(ϵ+2n)(1-\alpha )=2n+ϵ-\alpha n$$

Với:

• $ϵ$ (associative lookup) là thời gian tìm kiếm ở trong TLB.
• $\alpha$ (hit ratio) là tỷ lệ phần trăm trang được tìm thấy ở trong TLB, $\alpha$ càng cao thì EAT càng thấp.
• $n$ là thời gian để truy xuất bộ nhớ (có thể là bảng trang hoặc bộ nhớ thực).

Và:

• $(ϵ+n)$ là thời gian cần thiết để có được địa chỉ vật lý trong trường hợp hit.
• $(ϵ+2n)$ là thời gian cần thiết để có được địa chỉ vật lý trong trường hợp miss.

Ví dụ: với n = 200, đơn vị là nano giây.

1. Tìm thời gian truy xuất hiệu dụng khi không sử dụng TLB: $2n=400$.
2. Tìm thời gian truy xuất hiệu dụng khi có sử dụng TLB với $\alpha =75\%$, thời gian tìm trong TLB là 0:
   • $2\times 200+0-0.75\times 200=250$.