cache storage

yhko1992·2021년 11월 23일
1

ALGORITHMS - PRACTICE

목록 보기
7/49
post-thumbnail

1. cache 일거리 저장

캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.

철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

2 3 1 6 7

만약 캐시의 사이즈가 5이고 작업이 순으로 저장되어 있다면,
(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.)

1) Cache Miss : 해야할 작업이 캐시에 없는 상태로 위 상태에서 만약 새로운 작업인 5번 작업을 CPU가 사용한다면 Cache miss가 되고 모든 작업이 뒤로 밀리고 5번작업은 캐시의 맨 앞에 위치한다. (7번 작업은 캐시에서 삭제된다.)

5 2 3 1 6

2) Cache Hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 CPU가 사용한다면 Cache Hit가 되고, 6,3번 앞에 있는 5, 2번 작업은 한 칸 뒤로 밀리고, 3번이 맨 앞으로 위치하게 된다.
5 2 3 1 6 ---> 3 5 2 1 6

캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

ram에다가 일거리를 저장한다. 차곡차곡 일이 저장된다. 그러다가 이미 저장된 일을 해야한다고 하면 그 일을 맨 처음으로 끌어온다.

아래 진행상태를 적어보겠다.

일이 들어온 순서
[1,2,3,2,6]

캐시 메모리 상태 변화

10000

21000

32100

23100

62310

이런식으로 일거리가 들어오면 최종 ram을 리턴하면 된다.

어떻게 밀어넣으면 될까? unshift 라는 built-in을 사용해도 되지만 논리력을 끌어올리기 위해서 수동으로 할 필요도 있다.

어떻게 하면 될까? 바로 메모리 끝에서 부터 돌면서 각 숫자를 하나씩 뒤로 옮긴다음에 맨 처음에 칸에 일을 밀어넣으면 된다.

그리고 이미 있는 경우는 그 위치에서 시작해서 같은 작업을 하면 된다. 그럼 시작해보자.

function cacheStorage(size, arr) {
  const answer = Array.from({ length: size }, () => 0);
  arr.forEach((x) => {
    let pos = -1;
    // 메모리안에 작업이 있는지 찾는 작업
    for (let i = 0; i < size; i++) {
      if (x === answer[i]) pos = i;
    }
    // 메모리 안에 작업이 없으면 맨 마지막에서 부터, 있으면 그 자리서 부터 한칸씩 뒤로 옮기기
    if (pos === -1) {
      for (let i = size.length - 1; i >= 1; i--) {
        answer[i] = answer[i - 1];
      }
    } else {
      for (let i = pos; i >= 1; i--) {
        answer[i] = answer[i - 1];
      }
    }

    // 다 옮겼으면 마지막 앞에 x를 갔다놓기
    answer[0] = x;
  });
  return answer;
}


const size = 5
const cacheOrder = [1, 2, 3, 2, 6, 2, 3, 5, 7]

cacheStorage(size,cacheOrder) //7 5 3 2 6

크... 기분 좋은 작업이다. 명쾌하고 확실하다. 상자밖에서 생각해보자. 그리고 그림을 그려서 시각화하면 더 쉬워질거다.

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글