Cần gợi ý về thuật toán LRU (Least Recently Used)

#1

Chào các bác, hiện em có đang học về cơ chế thay trang sử dụng thuật toán LRU. Hiện tại thì em đang cần viết mã giả cho thuật toán LRU trên, em hiểu cách hoạt động của LRU nhưng mà vẫn chưa biết bắt đầu viết từ đâu. Ai có thể gợi ý một vài bước được không ?? :cry:

#2

Bạn có thể liệt kê ra những bước khi LRU thay trang sẽ làm gì không?

2 Likes
#3

Em chỉ biết là khi nó duyệt các phần tử trong chuỗi trang ảo, phần tử được thay thế trong bộ nhớ sẽ là phần tử ít được sử dụng nhất. Cứ thế sẽ loop hết toàn bộ các phần tử trong chuỗi trang ảo.

#4
  • Vậy các phần tử chưa vô Pages ta lưu thành 1 biến mảng.
  • Pages là 1 biến mảng luôn vì page có thể chứa nhiều phần tử
  • Bạn nói là nó xem phần tử nào dùng ít nhất. Vậy sao biết nó dùng ít nhất? Vậy có phải là thêm 1 mảng lưu tần xuất dùng trong page.

->

int wating[50];
int pages[4]; // giả sửa page chỉ chứa được 4 thôi
int used[4] = {0}; // = 0 vì mới đầu chưa có ai xài

Thì vì các phần tử wating sẽ chờ lần lượt xin vào page
->

for i = 0 -> 50
 current = waiting[i]; // lấy phần tử xin vào page

Để đưa current vào page thì ta phải tìm phần tử ít nhất xài ít nhất. Vậy cần 1 hàm tìm ít dùng nhất! :3
->

 findLRUElement(...);

Vậy cơ bản là ta có cái sườn nó vầy:

int wating[50];
int pages[4]; // giả sửa page chỉ chứa được 4 thôi
int used[4] = {0}; // = 0 vì mới đầu chưa có ai xài

for i = 0 -> 50:
 current = waiting[i]; // lấy phần tử xin vào page
 int replacePos =  findLRUElement(...);
 pages[replacePos] = current;
 ...

Vậy bây giờ còn những gì chưa giải quyết?

  • Làm sao biết được phần tử nào dùng bao nhiêu?
  • Nếu trong page có phần tử current rồi thì sao?
  • Làm sao biết được phần tử nào trong page đang được dùng?
    …
    :smiley:
1 Like
#5

Em làm theo kiểu thế này, cũng 1 mảng waiting, 1 mảng pages nhưng mà cái used là 1 cái queue. duyệt mảng waiting, nếu phần tử thứ i đã có trong queue used thì pop phần tử đó ra xong đẩy nó xuống cuối queue, nếu chưa có trong queue used thì pop phần tử đứng đầu queue rồi push waiting[i] vào cuối queue. Phần tử đứng đầu queue được pop ra có giá trị bao nhiêu thì kiếm trong mảng pages giá trị đó (giả sử là j), thì pages[j] sẽ thay bằng giá trị được push vào cuối queue. Cứ làm như thế tới hết :smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?