LRU ( Least Recently Used Algorithm )

LRU 알고리즘

가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

 

 

 

페이지 교체 알고리즘

페이징 기법으로 메모리를 관리하는 운영체제에서

새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할 지를 결정하는 방법

 

종류 : FIFO, LFU, LRU

 

1) FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 때 페이지를 선정하는 기법

2) LFU : 가장 최근에 사용한 프로그램 중 적은 횟수로 참조하는 페이지 교체

3) LRU : 가장 오랫동안 참조되지 않은 페이지 교체

 

 

LRU 알고리즘

[ 예시 ]

Input : 12345

Output : 5413

위의 그림에서 참조 스트링이 입력되고, 이에 따른 주기억 장치의 상태를 보면 됩니다.

 

- 4초 : 1 이 재참조되어 순서가 변경됩니다.

- 6초 : 캐시사이즈가 가득차서 가장 오랫동안 참조되지 않은 2를 제거 후 저장합니다.

 

 

[ 문제 ]

캐시 크기가 주어지고, 캐시가 비어 있는 상태에서 N개의 작업을 CPU가 차례대로 처리한다면 N개의 작업을 처리한 후

캐시 메모리 상태를 가장 최근 사용된 작업부터  차례대로 출력하는 프로그램을 작성하시오.

 

- 입력

1) 첫 번째 줄에 캐시 크기 (S) 와 작업 개수 (N) 이 입력됨

2) 두 번째 줄에 N 개의 작업 번호가 처리순으로 주어짐 ( 1 ~ 100 )

 

- 출력

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로  출력

 

[ 예시 입력 ]

5 9

1 2 3 2 6 2 3 5 7

[ 과정 ]

1) 1

2) 2 1

3) 3 2 1

4) 2 3 1

5) 6 2 3 1

6) 2 6 3 1

7) 3 2 6 1

8) 5 3 2 6 1

9) 7 5 3 2 6

 

[ 예시 출력 ]

7 5 3 2 6

 

[ 소스코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LRU {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int s = kb.nextInt();
        int n = kb.nextInt();
        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(kb.nextInt());
        }
        myLRU(s, arr);
    }

    public static void myLRU(int s, List<Integer> arr) {
        List<Integer> temp = new ArrayList<>();
        int cnt = 0;
        boolean check = false;

        while (cnt < arr.size()) {
            // 이미 숫자가 있는지 확인
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i) == arr.get(cnt)) {
                    temp.remove(i);
                    temp.add(0,arr.get(cnt));
                    check = true;
                    break;
                }
            }
            if(!check){
                temp.add(0,arr.get(cnt));
            }
            // 최대 크기를 넘은 경우
            if(temp.size() > s){
                temp.remove(temp.size() - 1);
            }
            cnt++;
            check = false;
        }
        
        for (Integer i : temp) {
            System.out.print(i + " ");
        }
    }
}