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 + " ");
}
}
}'알고리즘' 카테고리의 다른 글
| 다항식 프로그램 ( c++ ) (0) | 2022.10.14 |
|---|---|
| 시뮬레이션과 완전탐색 (0) | 2022.10.10 |
| DFS 코드 이해하기 ( java ) (1) | 2022.10.06 |
| Dynamic Programming (0) | 2022.09.26 |
| 후위 표기식 (0) | 2022.09.25 |
