Jay's Develop Note

가상 메모리란 무엇일까? 

가상 메모리란 메모리가 실제보다 많아 보이게 하는 기술로, 각 프로그램에 실제 메모리 주소가 아닌 가상 메모리 주소를 할당한다. 이러한 방식은 멀티태스킹에서 자주 사용되며, 메인 메모리를 크게 보이게 하는 기술로 사용된다. 

이러한 가상 주소를 '가상 주소'(virtual address)또는 '논리 주소'(logical address)라고 부른다. 가상 주소 장치는 메모리 관리 장치에 의해 물리 주소로 변환되여 매핑된다. 

아래는 가상 메모리 주소가 실제 물리 메모리 주소로 어떻게 변환되고 매핑되는지 간략히 표현한 그림이다.

동작 과정을 설명하기전, 용어부터 간략히 알고 넘어가자.

• 페이지 : 가상 메모리의 "페이지"는 캐시의 블럭과 같다. 위 그림에서 왼쪽 위의 테이블들을 보면, 총 12개의 인덱스가 존재하는데, 각 인덱스는 가상 메모리를 담고있는 "페이지" 라고 불린다.
• 프로세서가 요청한 메모리가 가상주소 페이지에 존재하지 않으면, page fault라고 불리운다.
• 물리 주소(physical address) : RAM 상에 존재하는 "실제" 데이터가 존재하는 주소이다.
• 가상 주소 : 운영체제가 부여한 "가상"의 주소로 관리또한 OS에 의해 관리된다.

아래는 가상 메모리의 동작 과정을 간략히 표현한 그림이다.

동작 과정은 대략 이러하다.

<위 그림안의 테이블에서 각 인덱스는 가상 페이지 번호를 나타낸다.>

1. 가상 메모리에서 요청한 주소를 따라 페이지 테이블로 이동한다. 페이지 테이블에서 원하는 주소가 있는 인덱스로 이동하여 valid bit을 확인한다. valid  bit는 항상 0 또는 1이다. 

2. Valid bit이 1이라면 물리 페이지 번호를 로드한다.

3. page offset(페이지 오프셋은 페이지의 시작점부터 원하는 데이터가 얼마나 먼 거리에 떨어져 있느냐를 판별할때 쓰이는데, 가상 주소와 물리 주소의 페이지 오프셋은 항상 같다. 그다음 이 오프셋과 로드된 물리 주소를 합쳐 물리 주소를 얻어낸다.

상당히 직관적이고 간단해 보인다.

위 그림에 보면 Page Table Register라는 레지스터가 보이는데,  이 레지스터는 일반적인 레지스터와의 역할이 다르다. 이 레지스터는 항상 메인 메모리 안의 페이지 테이블의 시작점을 가리킨다. 

메인 메모리 안의 페이지 테이블,,, 뭔가 이상한 점을 눈치 챘다면 캐시와 메인 메모리의 개념을 어느정도 이해하고 있는 것이다. 혹시나 개념을 모른다면 아래 글을 참고하면 좋을것 같다. 

https://jghdg1234.tistory.com/4

정말 간단히 요약하면, 캐시는 빠르고, 메인 메모리는 느리다. 그렇지만 페이지 테이블은 메인 메모리 상에 존재하므로 매번 프로세서에게 요청을 받을 때마다 메인 메모리에 접근하는것이다. 그렇다면, 메인 메모리에 접근하기 전에 더욱 빠르게 가상 주소를 물리 주소로 변환하는 방법은 없을까? 있다. 이 문제점을 해결하기 위해 나온것이 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)이다. 

TLB는 CPU상에 존재하기 때문에 접근 속도가 메인 메모리보다 훨씬 빠르다. 또다른 fully-associative cache라고 생각하면 된다. 

동작 과정은 대략 이러하다.

1. TLB와 페이지 테이블을 동시에 확인한다.

2. TLB에 원하는 블럭을 찾으면(TLB hit) 물리 주소로 곧바로 매핑한다.

3. 찾지 못하면(TLB miss) 메인 메모리에 접근하며 페이지 테이블을 확인한 후, 물리 주소를 찾고 그 주소를 TLB의 빈 자리에 메인 메모리에서 찾은 주소를 보관해둔다. 그런데 만약 페이지 테이블에 조차 원하는 주소를 찾지 못하면 어떻게 될까?(page fault) 이 뒤로는 이제 OS의 영역이다. OS가 페이지를 어디선가 찾아오고 페이지 테이블을 업데이트 시켜 줄 것이다. 

아래는 TLB의 동작 과정을 간단히 나타낸 그림이다.

맨 위부터 차례로 

1. 32비트 물리 주소를 두 부분으로 나눈다.(가상 페이지 번호, 가상 페이지 오프셋) - 가상 페이지 오프셋은 물리 페이지 오프셋과 항상 동일하게 매핑된다. 

2. 물리 페이지 번호를 얻기 위해서, TLB에 접근하여 모든 슬롯을 찾아본다. 원하는 태그를 찾으면, 물리 주소를 로드하여 물리 주소로 변환 시킨다. 이때, TLB miss가 발생하면 DRAM으로 내려가 page table을 확인한 후, page table에 원하는 주소가 있으면 TLB를 방금 찾은 Page table entry로 업데이트 한다.

3. 변환된 물리 주소를 다시 인덱스, 오프셋, 태그 비트를 추출 한 후 나머지 캐시 동작을 수행한다. 

캐시의 동작 과정을 잘 모르겠다면, 아래 글을 한번 읽어보면 좋을것 같다.

https://jghdg1234.tistory.com/5

메모리 , 캐시에 대한 기본적인 내용을 모른다면 앞의 글을 참고하면 좋을것같다.

https://jghdg1234.tistory.com/4

CPU에서 데이터에 접근하려면 맨 처음 레지스터에 접근하여 원하는 데이터가 있는지 확인한다. 그 다음, 계속해서 아래 레벨로 내려가 원하는 데이터를 찾으면, 그 데이터를 계속해서 위로 복사하여(옮기는것이 아니라) CPU에 전달하는 방식이다. 위의 글에서 캐시는 컴퓨터 메모리 구조에서 매우 중요한 항목이라고 언급했는데, 그 이유는 메모리의 접근 시간을 단축시켜주기 때문이다.

그렇다면 캐시는 어떻게 구성되어 있을까? 간단한 예를 한번 들어보자.

위 그림에서 위에있는 블럭들은 캐시이고, 아래에 있는 더 길다란 블럭들은 메모리이다. 이 캐시는 Direct-mapped 캐시인데, 이 말은 하나의 캐시 블럭에는 단지 하나의 메모리 밖에 저장 할 수 없다. 예를들어, 현재 캐시는 8개의 블럭으로 되어있고, 각 블럭의 인덱스는 0 부터 7까지이다. 예를들어 00001주소에 있는 메모리를 프로세서가 요청했다고 가정해보자. 그러면 프로세서는 캐시를 들여다 볼 것이다. "00001"주소의 데이터가 캐시에 없다.(캐시 미스 발생[cache miss].)  그러면 이제 더 아래쪽 DRAM레벨로 내려가 메모리를 찾아와 캐시 블럭에 저장한다. 

그렇지만 여기서 한가지 의문점이 생긴다. 위에서 "프로세서에서 요청한 데이터를 캐시에서 찾는다" 라고 하였는데, 캐시 블럭이 8개가 아니라 800개라면, 탐색 시간은 O(n)이 소요된다. 그렇다면 원하는 캐시 블럭에 바로 접근하여 원하는 데이터가 있는지 확인하려면 어떻게 해야할까? 가장 기본적인 블럭 위치 연산법은 나머지 연산(modulo)이다. 예를들어, 16진수로 표현된 메모리 주소 0x1234ABCD를 찾으려고 한다고 가정해보자. 이때, (메모리 주소 % 캐시 블럭의 갯수)를 하면 캐시의 위치를 찾을 수 있다. 

위의 그림 예제로 돌아가보자. 메모리 00001은 캐시의 몇번 블록에 저장될까? 00001 % 8 은 1 이다. 그러면 이제 캐시블럭[0]은 00001의 메모리로 채워져 있는 상태이다. 그런데 여기서 만약 01001의 메모리를 참조하면 어떤 일이 벌어질까? 먼저, 나머지 연산을 수행해 캐시 블럭의 위치를 알아낸다. (01001  % 8)은 1이다. 그리고 1에는 이미 데이터가 존재한다(00001). 그러면 이것은 캐시 히트(cache hit)일까?

정답은 아니다.

이유는 간단하다. 프로세서가 요청한 데이터는 01001이지만 캐시블럭 1에 있는 데이터는 00001이기 때문이다. 그러면 여기서 또 다른 의문이 생긴다. 그렇다면 두개의 다른 메모리는 어떻게 구분될까? "Tag bit"라는 비트를 이용한다. 위의 예제에서는 간단하게 이진수로 표현된 메모리주소는 앞 두자리를 태그비트로 사용한다. 띠라서 '01' 001과 '00' 001 엄연히 다른 데이터이다. 그러면 여기서 캐시 충돌이 발생한다.(이미 캐시블럭 1번에 00001이라는 데이터가 있으므로). 이때, 원래 있던 00001을 캐시에서 내보내고 01001을 다시 캐시에 저장한다. 이런식으로 Direct-mapped cache는 캐시 블럭 하나당 하나의 데이터만 담을 수 있으므로 새로운 데이터가 이미 채워진 블록에 들어오려고 할 때마다 교체 해줘야 한다.

그렇지만 이런식으로 교체를 하다보면 그에 대한 비용은 무시 할 수 없다. 예를 하나 들어보자. 

아래는 프로세서가 요청한 데이터를 순서대로 나열한것이다.

1. 00001 (캐시 미스! 블럭 1에 이 데이터를 저장)

2. 01001 (캐시 미스! 00001을 내보내고 01001을 저장)

3. 00001 (캐시 미스! 01001을 내보내고 00001을 "다시" 저장)

이처럼 다시 저장은 또다른 프로세스를 요구한다. 다시 레지스터부터 DRAM까지 내려가 데이터를 가져오는 비용은 매우 비싸다(캐시의 존재 본질에 의문이 드는 시점이다).

그렇다면, 하나의 캐시 블럭에 여러개의 데이터를 저장 할 수 있다면 어떨까? 위의 예를 다시 들어보자.

1. 00001 (캐시 미스! 블럭 1에 이 데이터를 저장)

2. 01001 (캐시 미스! 00001을 내보내지 않고 블럭 1에 01001을 저장) <이 시점에서 블럭 1에는 두개의 데이터 (00001, 01001)이 들어있다.

3. 00001 (캐시 히트!)

이처럼 훨씬 효율적인 프로세스 처리가 가능하다. 캐시블럭 하나에 두개의 데이터를 저장할 수 있는 캐시를 (2-way set associative cache)라고 부른다.

하지만, n - ways set associative는 캐시 블럭을 검색할때, 모든 블럭들을 검색해야 한다. 예를들어, 4 ways set associative에서 세트 11에 해당하는 데이터를 찾으려고 한다면, 세트 11로 내려가 4개의 블럭을 일일히 모두 확인해야 한다.

마지막으로, 캐시 접근을 더 용이하게 하기 위해, 32비트 데이터를 여러 부분으로 나눌 수 있다.

valid bit, tag bit, index bit, offset bit.

1. **Valid bit (유효 비트):** 캐시 블록이 유효한 데이터를 가지고 있는지를 나타내는 비트이다. 보통 0은 비어있음을, 1은 캐시 블록에 유효한 데이터가 저장되어 있음을 나타낸다. 캐시 조회 시, 이 비트를 확인하여 캐시가 유효한 데이터를 가졌는지를 확인한다.

2. **Tag bit (태그 비트):** 동일한 캐시 블록으로 매핑된 데이터들을 식별하는 데 사용되는 비트이다. 캐시 블록에 저장된 데이터의 주소 일부로 사용되며, 캐시에서 데이터를 찾을 때 메모리 주소의 특정 부분을 나타낸다.

3. **Index bit (인덱스 비트):** 캐시 내에서 어느 블록에 위치하는지를 나타내는 비트이다. 이진수로 표현되며, 캐시 메모리의 어느 부분에 데이터가 저장될지 결정하는 데 사용된다.

4. **Offset bit (오프셋 비트):** 캐시 블럭내에서 어느 구간 사이에 데이터가 있는지 알려주는 비트이다. 예를들어, 32비트 크기의 캐시 블럭이 있다고 가정해보자. 한개의 블럭은 8개의 단어를 저장 할 수 있다(하나의 단어는 4바이트). 예를들어 오프셋 비트가 8이면, 8부터 11까지의 3비트가 우리가 알아봐야 할 곳이다.

이번에는 컴퓨터의 메모리에 대해 조금 더 자세히 알아보자. 컴퓨터의 메모리 구조를 그림으로 간략하게 표현하면 아래와 같다.(물론 실제 메모리의 물리적인 모습은 훨씬 복잡하다.)

맨 위(레지스터) 부터 천천히 알아보자.

• 레지스터 : 메모리 구조의 가장 상단 부분이며, 접근 속도가 "매우" 빠르다. 하지만 용량이 매우 적다. 그리고 엄청엄청 비싸다.(구글에 가격을 쳐 보면 자세히 나온다. 같은 용량의 레지스터와 하드 디스크의 가격 차이는 정말 어마어마하다.) 여기서 말하는 접근 속도란 CPU에서 레지스터의 접근 속도이다.
• 캐시 : 컴퓨터 메모리 구조에서 중요한 부분중 하나이다. 캐시는 보통 L1캐시(KB), L2캐시(MB)로 나뉘고, 또 I-cache(instruction을 담는 캐시), d-cache(데이터를 담는 캐시)로 나뉜다. 이렇게 나뉘는 이유는 캐시 또한 레지스터 못지 않게 접근 속도가 빠른 반면, 저장할 수 있는 용량이 작기 때문에 캐시를 나눴다. RAM과 레지스터 사이에 캐시를 두는 이유는 빠른 속도와 큰 용량간의 균형을 유지하기 위해서이다. 즉, 레지스터에서 처리하기엔 너무 큰 용량이고, RAM에서 처리하기엔 충분한 용량이지만 RAM은 레지스터보다 접근 속도가 현저히 느리다. 즉, 이 부분을 상쇄하기 위해 생겨난것이 캐시이다.
• 메인 메모리인 RAM(랜덤 액세스 메모리)는 컴퓨터가 실제 작업을 처리하는 곳이다(GB). 여기에는 현재 실행 중인 프로그램과 그 프로그램이 필요로 하는 데이터가 들어있다. CPU가 작업을 수행할 때 RAM에서 데이터를 읽고 쓰며 작업을 진행한다. 또한 RAM은 CPU와 직접적으로 소통하면서 데이터를 빠르게 전달하는 역할을 한다. 이 말은 CPU가 빠르게 RAM에 있는 정보에 접근하여 작업을 처리한다는 것이다. CPU가 RAM의 데이터를 빠르게 접근할 수 있어야 성능이 좋아지는데, 이를 위해 캐시가 중요하게 사용된다.
• 하드 디스크 : 우리가 흔히 알고 있는 CD, USB등등이 하드 디스크이다. CPU에서 접근 속도가 매우매우 느리다. 하지만 용량이 매우 크고, 용량당 가격이 훨씬 저렴하기 때문에 많은 용량 저장을 필요로 할때는 하드 디스크는 좋은 선택지이다.

캐시(SRAM)은 byteAddressable한 자료를 가질 수 있는데, 이는 컴퓨터가 메모리에 저장된 데이터를 하나의 바이트 단위로 주소 지정하여 읽거나 쓸 수 있다는 뜻이다. 0과 1로 표현되는 비트 단위의 데이터를 처리하는 컴퓨터는 이러한 byteAddressable한 형태로 데이터를 다루기 때문에, 이 형식이 아닌 데이터를 가져오려면 더 많은 비용이 든다.
SRAM은 해시 테이블과 비슷한 개념이다. 해시 테이블은 특정 요소를 빠르게 가져오는 데 유용한데, SRAM 역시 주소를 통해 데이터를 빠르게 가져올 수 있어서 접근 시간이 빠르고, 이는 O(1)의 시간복잡도 이다. 그러나 byteAddressable이 아닌 다른 형태의 데이터에 접근하기 위해서는 연결 리스트와 같이 순회하면서 데이터를 찾아야 해서 시간이 더 오래 걸린다. 이는 O(n)의 시간복잡도를 갖게 된다.

그러면 메모리는 어떻게 저 아래있는 데이터를 cpu까지 가져올까? CPU의 영역에는 레지스터, 캐시, 메인 메모리 모두가 있다.예를들어, 우리가 원하는 데이터가 usb에 있다고 해 보자. 컴퓨터에 usb를 꽂고, 컴퓨터에게 usb에 있는 문서를 읽어오라고 시킨다면, 먼저 CPU에서 원하는 메모리를 찾으려고 할것이다. 그러면 위 그림에서처럼 아래로 한단계씩 내려간다. 먼저 레지스터에 원하는 데이터가 있는지 확인하고, 없으면 캐시로 내려가서 확인하고(이때, 캐시에 원하는 메모리가 있으면 그것을 캐시 히트(cache hit)이라고 하고 없으면 캐시 미스(cache miss)라고 한다. 우리가 원하는 데이터는 결국 하드 디스크에 있으므로 하드 디스크가 있는 레벨까지 계속 내려간다. 하드 디스크에서 원하는 데이터를 찾으면 한단계씩 위로 데이터를 복사한다.(여기서 중요한 점은, 데이터를 '옮긴다'는게 아니라 '복사' 해서 위로 올린다. 결국 레지스터 레벨까지 복사가 되면, 마침내 CPU는 원하는 데이터를 읽어오는것이다.(여기서 알 수 있듯, 데이터가 아래에 있으면 있을수록 해야되는일은 더 많아진다.)

마지막으로, 이건 그냥 알아두면 좋은 지식인데, 메인 메모리를 포함한 그 위쪽은 Volatile이라고 불리우고, 그 아래는 non-volatile 이라고 불리운다. 각각의 뜻은, volitale은 컴퓨터를 종료하면 안에 있던 모든 데이터가 컴퓨터 종료와 동시에 사라진다는 뜻이고, 컴퓨터를 다시 켜면 텅 빈 상태로 다시 시작된다. 반대로 non-volitale은 컴퓨터를 종료해도 데이터는 안에 그대로 남아있는다.

수많은 개발 블로그들을 봐 왔다. 모르는 내용이 있을때마다 구글링을 해서 많은 정보들을 얻었지만 내가 해보는건 처음이다...

일단 간략하게 소개를 하자면

CS전공 학부생이고, 곧 4학년이다. 하지만 뒤를 돌아보니 수업을 열심히 들은거 빼고는 따로 해놓은게 너무 없어서 블로그를 해보면 나중에 포트폴리오에도 좋을것 같아서 써 본다. 되게 여러가지 내용들을 쓸것 같은데, 대략

공부 내용(알고리즘, 프로그래밍 언어) 등등, 또 요즘 새로운 내용을 배우고 있는 시스템, 컴퓨터 구조, 어셈블리어, 리액트나 클라우드같은 내용은 따로 배워서 정리해서 올려야겠다. 딱히 체계적인 블로그 라기보단 그냥 공부하면서 중요하다고 생각되는 내용 주저리 주저리 쓸 것이다. 

꾸준히 꾸준히 계속 써야겠다.