캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장 되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)
- 1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작 업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번작업은 캐시의 맨앞에 위치한다. 5 2 3 1 6 (7번 작업은 캐시에서 삭제된다.)
- 2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면 Cache Hit가 되고, 63번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.
5 2 3 1 6 ---> 3 5 2 1 6
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.
5 9
1 2 3 2 6 2 3 5 7
7 5 3 2 6
- 크기가 5개인 캐시 Array 생성
- 입력 값에서 작업 Array 가져오기
- 작업할 것들 for 문으로 순회
- Cache miss?
- cache Arr의 첫 번째 요소에 값 추가 (unshirt)
- cache Arr의 마지막 요소 삭제 (pop)- Cache hit (삽입 정렬 응용)
- 캐시 배열에서 hit 지점 까지 이동 (a[i] = a[i-1])
- Hit 값을 캐시 배열 0번으로 이동
let cacheList = [0, 0, 0, 0, 0];
let workList = require("fs").readFileSync(__dirname + "/input.txt").toString().trim().split("\n").slice(1).join().split(" ").map((i) => Number(i));
// workList 순회
workList.forEach((element) => {
let pos = -1;
let cacheSize = cacheList.length - 1;
// workList element가 cache에 있는지 확인 => 있다면 pos = 0 아니면 pos = -1
if (cacheList.includes(element)) pos = 0;
// cache miss
if (pos === -1) {
cacheList.unshift(element);
cacheList.pop();
// cache hit
} else {
for (let i = cacheSize; i >= 1; i--) {
cacheList[i] = cacheList[i - 1];
}
cacheList[0] = element;
}
});
console.log(cacheList);