캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다.
워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.
철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다.
LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다.
캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로저장되어있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)
1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작 업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번작업은 캐시의 맨앞에 위치한다.
52316 (7번 작업은 캐시에서 삭제된다.)
2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용 한다면 Cache Hit가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.
---> 52316 35216
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다. 두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.
▣ 출력설명
마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.
▣ 입력예제 1
5 9
1 2 3 2 6 2 3 5 7
▣ 출력예제 1
7 5 3 2 6
/**
*
* @param S: 캐시 크기
* @param N: 작업 수
* @param arr: 작업 번호 배열 (1~100)
* @return: LRU 결과
*/
private static int[] solution(int S, int N, int[] arr){
int[] cache = new int[S];
boolean hasHit = false; // Hit or Miss 상태
int hitIndex = -1; // Hit인 경우 기존 엘리먼트 위치
for (int i = 0; i < N; i++) {
hasHit = false;
hitIndex = -1;
// Cache Miss, Hit 검사
for (int j = 0; j < cache.length; j++) {
if(arr[i] == cache[j]){ // Hit이 존재하는 경우
hasHit = true;
hitIndex = j;
break;
}
}
// Hit 상태인 경우
if(hasHit){
// Hit된 위치 왼쪽의 모든 엘리먼트를 우측으로 한칸씩 이동
for (int j = hitIndex; j > 0; j--) {
cache[j] = cache[j-1]; // 앞으로 당기기
// 맨 처음에 Hit 값을 넣는다.
if(j == 1){
cache[0] = arr[hitIndex];
}
}
}else{
// Miss 상태인 경우, 전부다 뒤로 한칸씩 이동 후 맨 처음에 값 입력
for (int j = cache.length - 1; j >= 0; j--) {
if(j == 0){
cache[0] = arr[i];
}else{
cache[j] = cache[j-1];
}
}
}
// 작업 내용 출력
printList(cache);
}
return cache;
}
private static void printList(int[] input){
for (Integer i : input) {
System.out.print(i + " ");
}
System.out.println("");
}
public static void main(String[] args) {
int[] solution = solution(5, 9, new int[]{1, 2, 3, 2, 6, 2, 3, 5, 7});
printList(solution);
}
'JAVA > 알고리즘' 카테고리의 다른 글
철수 짝궁 번호 출력 (0) | 2021.06.08 |
---|---|
배열 중복 검사 (0) | 2021.06.07 |
공주 구하기 (0) | 2021.06.02 |
쇠막대기 자르기 (괄호) (0) | 2021.06.02 |
크레인 인형뽑기(카카오) (0) | 2021.05.25 |