01/10/2018, 11:48
Cần gợi ý về thuật toán LRU (Least Recently Used)
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 ??
Bài liên quan
Bạn có thể liệt kê ra những bước khi LRU thay trang sẽ làm gì không?
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.
->
Thì vì các phần tử wating sẽ chờ lần lượ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->
Vậy cơ bản là ta có cái sườn nó vầy:
Vậy bây giờ còn những gì chưa giải quyết?
…
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