[부캠챌린지] Day3 - 웹 크롤링 및 LRU 캐시

※ 본 카테고리의 내용은 부스트캠프 챌린지 기간동안 학습한 내용을 바탕으로 정리한 내용입니다.

0. 캐시 교체 정책

운영체제 수업을 들었다면 페이지 교체 알고리즘에 대해서 들어본 적이 있을 것입니다.
페이지 교체 알고리즘이란 페이지 부재로 인해 가상기억장치의 필요 페이지를 주기억장치에 적재할 때 어떤 페이지 프레임을 선택해 교체할 지를 결정하는 기법을 말합니다.
말이 어려운데, 엄청나게 느린 하드디스크에 있는 내용을 자주 쓴다면 엄청나게 빠른 캐시(혹은 램)에 데이터를 저장해놓고 빠르게 가져올 수 있도록 할 때 어떤 방식으로 하드디스크에서 캐시에 등록을 하면 좋을까 고민을 하면서 발전을 하게 된 것이 바로 페이지 교체 알고리즘입니다.

대표적인 페이지 알고리즘으로는 FIFO, OPR, LRU, LFU, MFU 등이 있습니다.

첫 번째 알고리즘은 FIFO입니다.
FIFO는 First In First Out의 준말로 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법입니다.
가장 간단하고, 이해가 쉽고, 실제로 구현할 때도 간단합니다. 하지만 성능은 그다지 좋지 않습니다.
만약 프레임이 3개라면 4개 중에 프레임에 올라와 있지 않은 1개를 포함해서 2개만 서로 바뀐다면 비효율적인 페이지 교체가 계속해서 발생하게 됩니다.

두 번째는 OPR(Optimal Page Replacement)입니다.
이름에서 알 수 있듯이 미래를 보고 교체를 결정하는 최적의 페이지 교체 알고리즘입니다. 할당된 프레임의 수가 고정된 경우 굉장히 낮은 페이지 부재율을 보장하지만, 이 방법을 사용하기 위해서는 앞으로 어떤 프로세스가 어떻게 참조할 것인지를 알아야 하기 때문에 현실성이 떨어지는 방법입니다.

세 번째로는 LRU(Least Recently Used Page Replacement)입니다.
이 알고리즘은 가장 오랜 기간동안 사용되지 않은 페이지를 교체하는 기법입니다.
실제로 구현하기 어려운 OPR에 비해 구현이 가능하면서 OPR과 비슷한 효과를 낼 수 있는 방법이기 때문에 많이 사용됩니다.

네 번째로는 LFU(Least Frequently Used)가 있습니다.
이 알고리즘은 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다. LRU가 가장 오랜 기간(시간) 기준이라면 LFU는 가장 오랫동안 참조되지 않은 횟수 기준이 됩니다.
하지만 이 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 계속 메모리에 남아있을 가능성이 있기 때문입니다.

마지막으로는 MFU(Most-Frequently-used)입니다.
LFU 알고리즘과 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.
참조가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단으로 사용할 수 있는 알고리즘입니다.

하지만 LFU와 MFU는 구현이 어렵고, OPR의 훌륭한 대안인 LRU가 있기 때문에 횟수(Counting)을 기반으로하는 두 알고리즘은 일반적으로는 잘 쓰이지 않습니다.

1. 콘솔 입출력

웹 크롤링에 있어서 사용자로부터 입력을 받는 것은 반드시 필요할 수 있습니다.
매번 같은 데이터만 크롤링하는 것은 재미가 없으니까요(?)

대부분의 언어들이 편리하게 한 줄로 입력을 받을 수 있도록 구현이 되어있는데, Javascript는 전혀 그렇지 않습니다.
입력에 있어서 정말 불친절하죠. 하지만 어쩌겠습니까.. 극복해야죠!

흔히 사용하는 두 가지 방법이 있는데, 첫 번째는 readline, 두 번째는 prompt입니다.
먼저 readline은 createInterface 명령어를 통해 input과 output을 미리 설정하고 사용할 수 있습니다.
코드가 조금 길지만, 그만큼 뭔가 신뢰감이 갑니다.