|
톰 길번이 제안했던 가상 메모리 개념은 아틀라스 프로젝트에서 완성된 이후 현대 컴퓨터 아키텍처에까지 중요하게 사용되고 있다. 이후 발전된 가상 메모리와 페이지 교체 알고리즘의 다양한 아이디어는 DBMS의 버퍼 캐시를 관리하기 위한 알고리즘의 토대가 됐다. 이는 LRU 버퍼 교체 알고리즘과 클락 버퍼 교체 알고리즘이라는 두 가지 갈래로 나눠져 상용 DBMS들에 적용됐다. <편집자>
| |
 |
|
| ▲ (왼쪽부터) 엑셈 연구콘텐츠팀 권건우 상무, 이근오 부장, 김숙진 연구원, 이대덕 연구원 |
가상 메모리와 페이지 교체 알고리즘
프로그램이 컴퓨터 내부에 저장돼 순차적으로 실행된다는 폰 노이만 컴퓨터 아키텍처의 기본적인 한계점은 보조기억장치에 비해서 메인 메모리가 매우 부족하다는 것이었다. 일찍이 이러한 문제점에 대한 대안으로 맨체스터 대학의 톰 길번은 가상 메모리와 페이징이라는 개념을 제안했다. 톰 길번의 가상 메모리 개념은 현대 컴퓨터 아키텍처에서도 여전히 중요하게 쓰이는 혁신적인 개념으로, 1956년에 시작돼 1962년에 완료된 아틀라스(Atlas) 프로젝트에서 완성됐다.
가상 메모리는 프로세스에게 각자의 가상 주소(Virtual address)를 부여해 프로세스를 분할해 사용하는 부분만 메모리에 올리고, 나머지는 디스크에 보관하는 기법이다. 각 프로세스가 갖는 페이지들의 가상 주소는 메모리 맵(Memory map) 또는 페이지 테이블(Page table)을 거쳐 실제 물리 메모리의 주소를 의미하게 되고, 만약 메모리 맵에 존재하지 않는다면 이는 메모리에 존재하지 않고 디스크에만 존재함을 의미한다.
가상 메모리에서 필요한 페이지를 메모리에 올리는 방식으로는 요구 페이징(Demand paging) 기법이 있다. 요구 페이징 기법은 페이지를 미리 메모리에 올려두는 것이 아니라 페이지가 필요해질 때 메모리에 올리는 기법으로, 프로세스를 실행하던 중 필요한 페이지가 생기면 페이지 테이블에서 유효-무효 비트(valid-invalid bit)를 검사한다.
유효할 경우 메모리에 올라와 있다는 것으로 프레임의 주소를 가져와 사용할 수 있다. 그러나 유효하지 않을 경우 메모리에 존재하지 않는다는 것으로, 운영체제에 페이지 부재(Page fault)가 발생했다는 것을 알린다.
운영체제는 디스크에서 페이지를 찾아 메모리의 빈 공간에 올리고, 페이지 테이블을 업데이트 시킨 후 다시 프로세스를 진행한다. 페이지 부재가 발생하는 동안 실행 중인 프로세스는 필요한 페이지가 메모리에 올라올 때까지 잠들게 된다.
또한 디스크에서 메모리로 페이지를 불러오는 과정은 비용이 많이 든다. 따라서 잦은 페이지 부재는 전체 성능에 악영향을 끼치게 되므로, 페이지 부재의 발생 빈도를 낮추는 것이 페이징 성능의 주요 척도가 된다. 이를 위해 페이지 부재가 일어났을 때 디스크로 내보낼 희생자 페이지(victim page)를 효율적으로 선정하는 알고리즘이 연구돼 왔는데, 이를 페이지 교체 알고리즘이라고 한다.
이후 찰스 바크만에 의해 DBMS가 만들어지고 다양한 상용 DBMS가 출현함에 따라 DBMS의 버퍼 캐시를 효율적으로 관리할 필요가 생겼는데, 기본적으로 가상 메모리의 페이지 교체 알고리즘을 차용해 발전시켜 왔다.
DBMS 버퍼 매니저(Buffer manager)의 개념
DBMS의 버퍼 캐시는 버퍼 매니저에 의해서 관리되는 메인 메모리 영역으로 프레임이라는 고정 크기로 분할돼 있으며, 디스크의 페이지가 메인 메모리에 올라오면 프리(Free) 프레임에 할당된다. 만일 모든 프레임이 사용 중이라면 새로운 페이지를 버퍼로 로딩하기 위해서는 비어있는 대상 프레임을 확보해줘야 하는데 이를 희생자 프레임 선택(victim frame selection)이라 한다.
| |
 |
|
| ▲ 버퍼 캐시의 기본 구조(출처: Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. McGraw Hill) |
대상 프레임에 있는 페이지가 더티(Dirty) 상태라면 비우기 전에 디스크에 변경된 내역을 저장해야 하고, 더티 상태가 아니라면 프레임을 비워주기만 하면 된다. 이 동작을 관리하기 위해서 DBMS의 버퍼 매니저는 더티 비트(Dirty Bits)를 유지 관리해야 한다. 이 때 어떤 프레임을 선택해서 교체해주느냐를 결정해야 하는데, 이를 버퍼 교체 알고리즘(Buffer Replacement algorithm)이라 한다.
| |
 |
|
| ▲ 버퍼 교체 알고리즘의 분류 (출처: Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. McGraw Hill) |
DBMS 버퍼 매니저에서 사용하는 버퍼 교체 알고리즘은 가상 메모리에서의 페이징 교체 알고리즘과 유사한데 오라클(Oracle), MySQL/이노DB(InnoDB), 인포믹스(Informix) 등은 LRU(Least Recently Used) 알고리즘을 개선해 사용했고, IBM DB2, MS SQL 서버, 포스트그레SQL(PostgreSQL)은 클락(Clock) 알고리즘을 기본으로 수정해 사용했다. DBMS마다 특수한 개별 상황에서는 MRU(Most Recently Used), FIFO(First In First Out) 알고리즘도 사용하고 있지만, 상용 DBMS에서는 크게 LRU 알고리즘과 클락 알고리즘 두 가지를 사용하며 발전해 왔다고 말할 수 있다.
기존 DBMS 교과서에서는 수명(Age)과 참조(Reference)를 기준으로 버퍼 교체 알고리즘을 분류했는데, 이 분류는 현실적으로 상용 DBMS에서 가장 많이 사용되는 LRU 계열과 클락 계열의 알고리즘이 동일한 차원으로 분류된다. 이에 버퍼 프레임의 논리적 배열과 희생 프레임 탐색(Victime Frame Search)의 순서가 다이내믹하게 변경되느냐를 기준으로 크게 두 개의 흐름으로 정리해본다.
첫 번째 흐름, LRU 버퍼 교체 알고리즘
LRU 알고리즘은 가장 최근에 사용된 버퍼(MRU end)부터 가장 오래전에 사용된 버퍼(LRU end)까지 다이내믹하게 버퍼 프레임 배열의 순서를 변화시키면서 유지하고, 희생자 프레임 선택 단계에서는 가장 오래전에 사용된 버퍼부터 찾아나가는 방식이다.
LRU 교체 정책은 실제 상용 DBMS에서는 LRU-K 등 다양하게 변용돼 발전해왔지만, 기본적으로 버퍼가 사용되면 다이내믹하게 버퍼 프레임의 논리적 배열순서가 바뀐다는 점이 두 번째 클락 교체 정책과 다르다고 할 수 있다. 순서를 유지하기 위해서 각 프레임을 가리키는 포인터의 대기열(Queue) 정보를 유지해야 하고, 버퍼가 사용되고 unpin(pageNo, dirty)이 되면 해당 버퍼를 대기열의 꼬리 부분에 추가한다. 희생자 프레임을 찾는 단계에서는 대기열의 머리 부분부터 찾아나가면서 pinCount(pageNo)가 0인 프레임을 발견하면, 희생자 프레임 선택이 이뤄진다.
| |
 |
|
| ▲ LRU 알고리즘의 기본 구조 |
LRU 알고리즘을 사용하는 대표적인 상용 DBMS는 오라클로, 최신 버전에서는 LRU-K 알고리즘에 터치 카운트(Touch Count) 알고리즘을 추가하는 등 다양하게 개선된 LRU 알고리즘을 사용한다.
| |
 |
|
| ▲ 터치 카운트 기반 LRU 알고리즘 개요 |
두 번째 흐름, 클락 버퍼 교체 알고리즘
클락 알고리즘은 시스템 R(System R)과 잉그레스(Ingres) 계통의 DBMS에서 사용하는 교체 정책이다. 버퍼 프레임을 시계 형태로 차례로 나열하고, 현재의 시계 바늘은 가장 첫 번째 프레임을 가리키도록 초기화한다. 그리고 각 프레임의 참조 횟수를 0으로 초기화 시켜놓는다. 이어서 프레임이 사용된다면 참조 횟수를 증가시켜 나가고, 희생자 프레임 선택 단계에서는 시계 바늘을 차례로 이동시키면서 참조 횟수가 0인 프레임을 찾는다.
시계 바늘이 가리킨 해당 프레임의 참조횟수가 0보다 크면 -1을 연산해주고 다음 프레임으로 이동하며, 프레임이 고정된(pinned) 상태로 사용 중이라면 바로 건너뛴다. 해당 프레임의 참조횟수가 0이면 희생자 프레임 선택이 이뤄져 그 프레임을 비운 다음에 디스크에서 읽어 들인 페이지로 업데이트한다. 이러한 클락 알고리즘은 버퍼의 논리적 순서가 일정하게 고정돼 있어 희생자 프레임 탐색 순서가 항상 같다는 점이 LRU 알고리즘 계열과 다르다고 할 수 있다.
| |
 |
|
| ▲ 클락 알고리즘 개요 |
물론 실제 개별적인 DBMS에서는 버퍼를 거치지 않고 다이렉트 패스 다이렉트 패스 리드(Direct Path Read)를 사용하거나 킵 버퍼(Keep Buffer), 리사이클 버퍼(Recycle Buffer) 등 같은 DBMS 내 다른 알고리즘이 적용되는 버퍼를 유지하는 등 버퍼의 효율적 사용을 높이기 위한 다양한 기법을 사용한다.
그러나 크게 분류해 보면 오라클, MySQL/이노DB 등에서는 LRU 알고리즘을 개선해 사용하고 있으며, IBM DB2, MS SQL 서버, 포스트그레SQL 등은 클락 알고리즘을 사용하고 있음을 알 수 있다. |
webmaster@datanet.co.kr
KT, ‘28GHz 기업전용 5G 네트워크’ 개발 성공
