방학 불태우기 3

김민석·2021년 7월 21일
0

방학

목록 보기
3/16

캐시

기술이 발전하면서 프로세서의 성능은 빠른 속도로 발전했지만 메모리의 성장은 이 속도를 따라가지 못했다.

프로그램이 실행되면서 데이터에 접근할 때 메모리에 대한 처리 속도가 느리면 시스템 속도 역시 빠를 수가 없다.

이런 문제점을 해결하기 위해 캐시를 사용한다.

캐시는 cpu 칩 안에 들어가는 작고 빠른 메모리로 자주 사용하는 데이터는 메인 메모리가 아니라 캐시에 저장하여 처리 속도를 빠르게 하는 것이다.

프로그램이 돌아갈 때 자주 사용하는 데이터가 있고 자주 사용하지 않는 데이터가 존재하는데, 이는 지역성의 원리를 따른다고 한다.

지역성의 원리는 시간 지역성과 공간 지역성으로 볼 수 있는데, 시간지역성이란 최근에 접근했던 데이터에 다시 접근하려는 경향을 의미한다. 반복문에서 반복 횟수를 사용하는 변수를 예로 들 수 있다.

공간 지역성이란 최근 접근한 데이터의 주변 공간에 다시 접근하려는 경향을 의미하며, 반복문에서 배열을 사용한다면 가까운 메모리 공간에 연속적으로 접근하게 되는 것이다.

그림으로 보면 다음과 같다.

위 그림은 페이지 참조 기록인데, 일정 구간마다 촘촘하게 나와있는 것을 보면 지역성의 원리가 적용되는 것을 알 수 있다.

더 알아보기

캐시의 상세적 동작원리는 다음 링크에서 확인 가능하다.
참고 : https://parksb.github.io/article/29.html

캐시 교체 알고리즘

만약 캐시에 메모리가 존재한다면 그 메모리를 바로 가져다 사용하고, 존재하지 않는다면 메인 메모리에 접근하여 데이터를 가져오고 캐시를 최신화 해야 한다.

캐시의 용량은 제한되어 있기 때문에 효율적인 메모리 관리를 위해 캐시안의 내용들을 효율적으로 관리해야 한다.

캐시를 최대한 효율적으로 사용하기 위한 알고리즘에는 다음과 같은 것들이 존재한다.

FIFO(first in first out)

가장 기본적 알고리즘으로 캐시에 새로운 것을 저장할 때 가장 오래전에 저장된 것을 지우고 새로운 것을 추가하는 것이다.

이해가 쉽고 구현이 간단하지만 활발하게 사용되는 페이지가 자주 교체된다면 캐시에 없을 확률이 높아지고, 메인메모리에 접근해야 하기 때문에 실행속도가 느려질 수 있다.

최적 페이지 교체

앞으로 가장 오랫동안 사용되지 않을 메모리를 교체하는 알고리즘이다.
이런 알고리즘을 구현하기 위해서는 미래 상황을 미리 알고 있어야 한다.
따라서 구현이 불가능한 알고리즘으로 특정 알고리즘과의 속도 비교 연구를 위해 사용된다.

LRU(least recently used)

가장 오래 사용되지 않은 캐시를 교체하는 알고리즘이다.
새로운 내용이 들어왔을 때 캐시 내의 메모리 중 가장 오래전에 사용됐던 메모리를 지우고 새로운 내용을 추가하는 전략이다.
가장 오래전에 사용된 메모리는 이후에도 사용되지 않을 것이란 예측으로 이런 알고리즘이 생겨났다.

LRU 알고리즘은 많은 운영체제에서 채택한 알고리즘이다.
성능이 제일 좋은 편에 속한다.

LFU(least frequently used)

사용 빈도가 가장 적은 메모리를 교체하는 알고리즘이다.
사용빈도가 적으면 잘 사용되지 않다고 판단하여 이런 알고리즘이 생겨났다.
새로운 내용이 들어왔을 때 남아있는 내용들 중 가장 적게 활용된 것과 교체하는 알고리즘으로, 활용 빈도 역시 관리해 줘야 한다.

하지만 시간적 지역성에 따라 최근에 들어온것이 자주 사용된다면 교체가 자주 일어나게 될 것이고, 이로인해 성능이 떨어질 수도 있다.
반면 참조가 여러번 일어나서 더이상 참조하지 않는 데이터의 경우 사용빈도가 높았기 때문에 이후에 사용되지 않더라도 교체가 일어나지 않고 메모리만 차지할 수 있다.

MFU(most frequently used)

LFU와 반대로 사용빈도가 가장 많은 것을 교체하는 알고리즘이다.
사용 빈도가 많으면 이미 다 사용해서 앞으로 사용 안할 것이라 판단하여 이런 알고리즘이 등장하였다.

사용 빈도가 많고, 앞으로도 많이 사용될 수 있는 메모리를 교체할 수 있다는 단점이 있다.

참고 : https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

LRU 알고리즘

가장 오래 사용되지 않은 메모리를 교체하는 알고리즘으로 구현을 위해서는 메모리 들의 순서 정보를 유지해야 한다.

가장 최근에 사용된 것을 맨 앞에, 가장 오래전에 사용된 것을 맨 뒤에 유지하면 새로운 것이 들어왔을 때 맨 뒤의 것을 제거하고 맨 앞에 새로운 것을 추가하면 되기 때문이다.

배열 활용하기

가장 기본적으로 구현할 수 있는 방법은 배열을 활용하는 것이다.
일정 크기의 배열을 선언하고 배열이 비었다면 그저 추가한다.
만약 꽉 찼다면 맨 뒤의 것을 삭제하고 새로운 것을 맨앞에 추가해야 한다.
현재 데이터가 캐시에 존재하는 지 탐색하는데 O(n)이 들고, 삭제 후 재정렬 하는데 O(n)이 들어서 총 시간복잡도는 O(n)이 사용된다.

linked list와 hash map 사용하기

double linked list 와 hash map을 사용하여 효율적인 알고리즘을 구현할 수 있다.

리스트를 통해 순서를 유지한다. prev,next를 나타내는 링크를 통해 삽입, 삭제가 빠르게 일어날 수 있도록 한다.
해시맵을 통해 키값과 해당 키 값의 리스트에서의 위치를 가지고 있다. 해시맵을 통해 리스트에 대한 접근이 빠르게 일어날 수 있다.
이런 식으로 구현한다면 해시맵을 통한 접근 O(1), 삽입,삭제 O(1)이 들어 총 시간복잡도를 O(1)로 할 수 있다.

참고 : https://shins94.github.io/algorithm/2019/03/15/LRU-Cache.html

자바스크립트 표준 입출력

출력

console.log()를 통해 간단히 출력할 수 있다. 하지만 이 방식을 사용하면 한번 할 때마다 줄바꿈이 일어난다.
process.stdout.write()를 사용하면 여러번 사용해도 한줄에 출력이 가능하다.

입력

readline을 사용한다.
readline 모듈은 한 번에 한줄 씩 readable 스트림에서 데이터를 읽기위한 인터페이스를 제공한다.

const readline = require('readline');

위의 코드를 통해 모듈에 엑세스가 가능하다.
그리고 나서 readline.createInterface()를 통해 인터페이스를 생성하고 이것을 활용하여 입력이 가능하다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.question('question? ', (answer) => {
  console.log(`answer: ${answer}`);
  rl.close();
});
> question? hello
> answer: hello

위의 경우는 한번 입력받고 끝이지만 계속하여 입력 받을 때에는 다음과 같이 사용할 수 있다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', (input) => {
  console.log(`input : ${input}`);
  if(input === "quit")
  	rl.close();
});

.on을 사용하면 계속 입력을 받는다. 끝내고 싶으면 input에 대한 조건을 설정해 줘서 특정 문자가 나올 경우rl.close()를 추가하여 끝낼 수 있다.

readline = require("readline");
input = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
(function loop() {
  input.question("What do you want me to do?", (answer) => {
    const askAgain = answer === "ask me again";
    if (askAgain) loop();
    else input.close();
  });
})();

위와 같이 함수를 재귀적으로 사용하여 계속 입력 받을 수 있다.

참고 : https://velog.io/@yujo/node.js%ED%91%9C%EC%A4%80-%EC%9E%85%EB%A0%A5-%EB%B0%9B%EA%B8%B0
https://www.python2.net/questions-1151247.htm

더 알아볼 것들

  • 웹 크롤링
    axios
    cheerio
  • 자바스크립트 동기 비동기
    promise()
    callback
  • 자바스크립트 자료구조
    linkedlist
    map
    set
  • 자바스크립트 모듈
    외부 파일 불러오기
  • 자바스크립트 문법
    람다식
    고차함수
  • JQuery
profile
김민석의 학습 정리 블로그

0개의 댓글