정글사관학교 39일차 TIL: 가상 메모리(Virtual Memory) / CSAPP 9장 정리

대망의 RB트리 주차가 끝나고 malloc 함수 구현 과제 주차에 들어섰다. (현재 6주차) 어제는 시원하게 블로그 TIL을 건너뛰었다. (그래도 github에 저번 주차에서 배운 것들을 정리했다! BST 먼저 정리하고 이번주 주말에 가능하면 RB트리 readme를 작성할 예정.) 시원하게 쉬었으니 오늘부터 다시 달립시다.

 

malloc 개념은 CSAPP 책 9.9 장에 나온다. 그 전에 9장 전반적으로 정리를 할 필요가 있어 가장 큰 개념인 가상 메모리부터 정리.

 

가상 메모리(virtual memory)

가상 메모리를 쓰는 이유는 메모리를 더욱 효율적으로 & 더 적은 에러로 관리하기 위해서이다. 이와 관련해 아주 재밌게 설명한 영상이 있어 공유.

 

예를 들어, 어떤 식당이 있다고 하자. 이 식당은 예약제로만 손님을 받으며, 식당에는 총 10개의 테이블이 있다. 그런데 이 잔머리를 잘 굴리는 주인장은 늘 예약을 오버부킹으로 20팀씩이나  받는 것이 아닌가? 근데 이상하게도 한 번도 클레임이 생긴 적이 없다. 그 내막을 살펴보자.

 

우리도 식당을 예약하고 방문해봐서 잘 알겠지만, 손님들이 제 시간에 딱 맞춰서 가는 경우는 거의 없다. 그러니까, 10팀 모두 7시 정각에 예약하는 경우도 잘 없으며 (A: 6시 반에 2명(=1테이블) 예약이요~ / B: 7시 반에 8명(=2테이블) 예약할게요~) 설령 여러 팀이 똑같이 7시에 예약하더라도 누구는 10분 일찍 미리 도착하고 누구는 15분 여유있게(=코리안 타임) 도착하다 뺀찌를 먹기도 한다.(이건 뭐..손님 잘못이니)

 

또한, 나도 3번 테이블을 예약하고 뒤에 올 사람 C도 3번 테이블을 예약하지만 주인장은 내가 방문했을 때는 늘 나만을 위한 공간인 것처럼 자리를 내어준다. "여기 2시간 뒤면 C 테이블 자리예요~"라고 말하지 않는다. 내가 밥먹는 시간 동안은 나만이 쓰는 공간인 것처럼 내어준다. 실제로는 여러 사람이 다녀가면서도.

 

지금 말한 두 가지 예시에서 가상 메모리의 핵심이 있다. 실제 메모리 용량이 256MB라고 하자. 가상 메모리 개념을 적용하면, 프로그램을 실행할 때는 마치 메모리 용량이 2기가인 것처럼 행동한다(=오버부킹). 이게 가능한 이유는 프로그램을 실행할 때 모든 프로세스가 동시에 실행되는 게 아니라 여러 스텝에 걸쳐 순차적으로 실행되기 때문이다. 또한, 각 프로그램이 실행될 때 A 프로그램 입장에서도 2기가, B 프로그램 입장에서도 2기가를 내어주는 것처럼 할당한다. 이렇게 메모리 공간을 컨트롤하며 효율적으로 관리하는 방식이 바로 가상 메모리의 개요라고 할 수 있겠다.

 

본격적으로 정리를 해보자. 가상 메모리는 세 가지 주요한 기능을 제공한다.

 

1. 메인 메모리를 캐시처럼 취급해 효율적으로 사용한다. (by 하드 디스크와 메모리 사이로 데이터를 전송)

2. 단일한 주소 공간을 사용해 메모리 관리를 단순화시킨다.

3. 각 프로세스의 주소 공간을 다른 프로세스가 침입하지 않도록 보호한다. (위에서 말했듯, 특정 주소 영역에 대해 그 프로그램이 실행되는 동안에는 그 프로그램만을 위한 독립된 공간인 것처럼 인식하게 만드는 게 가상 메모리 역할.)

 

가상 메모리를 이해해야 하는 이유

1. 가상 메모리는 컴퓨터 시스템의 중심 기능이다. 컴퓨터 시스템의 모든 level에 침투해 주요한 기능을 수행하는 놈이다. 따라서 VM을 이해하면 일반적으로 컴퓨터 시스템이 어떻게 동작하는 지를 알 수 있다.

 

2. 가상 메모리는 강력한 기능이다. 응용 프로그램에 메모리 chunk를 생성하거나 삭제하는 기능을 부여해준다.

 

3. 가상 메모리는 잘못 쓰면 위험하다. 응용프로그램은 VM과 상호작용하면서 변수를 참조하거나 포인터를 생성/삭제하거나, 동적 메모리 할당(malloc)을 요청한다. 따라서 VM을 잘못 쓰면 응용 프로그램은 각종 메모리 관련 버그로 고통받는다. (포인터를 잘못 쓰거나 하면 segmentation fault나 protection fault를 야기한다.) 따라서 VM과 메모리 allocation package(malloc, calloc, realloc)을 관리하고 이해하는 것이 에러를 피하는 길이다.

 

9장에서는 두 가지 관점에서 VM을 바라보는데

 

1) VM이 어떻게 동작하는가

2) 응용 프로그램이 VM을 어떻게 사용하고 관리하는가

 

물리적 주소 & 가상 주소 접근 (Physical Addresing & Virtual Addressing, PA & VA)

컴퓨터 시스템에서 메인 메모리는 M개의 인접한 바이트 크기의 셀로 이뤄져 있다. 각 바이트는 유일한 물리적 주소(PA)를 갖는다. 예를 들어 첫 번째 byte의 주소가 0이라고 하면 그 옆 주소는 1, 2, ... 이런 식이다.

 

Physical Addressing

 

이런 단순한 조직에서 CPU가 메모리에 접근하는 가장 자연스러운 방법을 떠올려보면, 그냥 물리적 주소에 다이렉트로 접근하는 것이다. 이를 Physical Addressing이라고 한다.(주소에 접근하는 것을 addressing!) 옛날 pc는 PA 방식을 사용했다. 

 

Physical Addressing, PA

 

Virtual Addressing

 

반면, 요즘은 Virtual Addressing을 사용한다. CPU가 가상 주소(Virtual address)를 생성해 메인 메모리에 접근한다. CPU가 뭘 안다고 가상 주소를 생성할까? 아까 식당 자리를 생각해보자. 주인장이 오버부킹을 받는다고 했다. 예약하는 사람 입장에서 배정받는 자리는 가상의 테이블이기 때문에 내가 식당에 도착했을 때는 가상의 테이블 자리를 요청할 것이다. 주인장은 베테랑이기 때문에 없는 자리도 있는 것처럼 능숙하게 받아 현실에 있는 빈 공간에 날 데려간다.

 

이때, MMU(Memory Management Unit)이라는 하드웨어(얘가 주인장)가 메인 메모리로 주소를 전송하기 전에 적절한 물리 주소(PA)로 전환한다. 즉, MMU는 CPU 안에 있으면서 가상 주소를 실제 메모리 주소로 변환하는 장치이다. 이렇게 MMU가 가상 주소를 물리 주소로 전환하는 작업을 Address translation이라고 한다.

 

주소 영역(Address Spaces)

만약 주소 공간 내에 주소가 연속으로 늘어서 있다면, 이를 linear address space라고 한다. VM 시스템에서 CPU는 virtual address space(가상 주소 영역)이라고 하는 N= 2**n 짜리 주소가 있는 주소 공간을 생성한다. 그러면 가상 주소 공간은 {0, 1, 2, ..., N-1}과 같이 생성된다.

 

address space의 크기는 bit 수로 나타나는데, 이는 큰 주소의 표현에 필요하다. 예를 들어, N = 2**n인 가상 주소 영역은 n개의 비트 주소 공간으로 부른다. 현재는 32-bit(2**32) 혹은 64(2**64) 크기의 가상 주소 영역을 제공한다.

 

컴퓨터 시스템은 물리적 주소 공간 또한 갖고 있는데, 시스템 내에 M byte 크기의 물리 메모리를 다룬다. 

 

주소 공간(address space)이라는 컨셉은 상당히 중요한데, 어떤 데이터가 있다면 그 데이터의 객체 파일(bytes)과 그 데이터의 주소값을 구분하게 해주기 때문이다. 예를 들어 한 데이터 객체가 여러 구분된 address를 갖게 해준다고 볼 수 있다. 예를 들어 동일한 데이터라도 아예 다른 가상 주소를 가짐으로써 이 프로그램에서 데이터가 쓰일 때와 저 프로그램에서 데이터가 쓰일 때 아예 다른 데이터로 취급해 구분해준다. 독립성을 보장해준다고 보면 되겠다. 이게 VM의 기본 아이디어라고 볼 수 있겠다.

 

정리하면, 메인 매모리 내 각 바이트는 가상 주소 공간으로부터 선택받은 주소와 물리적 주소 공간으로부터 선택받은 물리적 주소 두 가지를 갖는다. 이때, 물리적 주소는 여러 프로그램에서 겹칠 수 있으나 가상 주소는 각 프로그램 별로 독립적으로 구성되어 있다.

 

그러면 이 가상 메모리가 어떤 식으로 구성되어 있는지 살펴보자.

 

가상 메모리 = 메인 메모리 + 하드 디스크

가상 메모리 개념은 메인 메모리에다가 하드 디스크까지 끌어서 쓰는 개념이다. 아니, 그럼 가상 메모리라는 게 그냥 부족한 메모리 용량을 하드 디스크까지 확장하는 것인가? 라고 이해하면 그건 틀린 말이다. 그러면 데이터를 가져올 때 메인 메모리에서 가져올 때와 하드 디스크에서 가져올 때 속도의 엄청난 차이가 발생한다. 그런데 이게 프로그램이 동작하는 과정에서 어떤 데이터는 하드에서, 어떤 데이터는 메인 메모리에서 가져오면 실행 속도가 일정하지 않고 매우 큰 편차가 발생할 것이다. 따라서 물리 주소는 오직 RAM에서만 쓴다. 그럼 하드는 어떻게 쓰는 걸까?

 

위에서 메인 메모리를 캐시처럼 쓴다는 말을 기억하나? 원래 캐시 메모리는 메모리 hierarchy에서 CPU와 메인 메모리 사이를 연결해주는 메모리로, SRAM으로 구성된 L1/L2/L3 메모리를 뜻한다. 이를 똑같이 적용해, 하드 디스크 내에서 메인 메모리와 하드 디스크 사이를 연결해줄 수 있게 메인 메모리를 캐시 메모리처럼 사용하자는 뜻이다.  즉, 메인 메모리 내에 가상 페이지를 캐시(임시 저장)해주는 VM 시스템에서의 캐시를 DRAM cache organization이라고 한다.

 

그럼 하드 디스크에는 무엇이 저장될까? 아래 그림을 보면 보다 명확하게 이해할 수 있다.

 

왼쪽의 Page table은 운영체제가 물리 주소와 가상 주소를 mapping하기 위해 만든 테이블이다. 페이지는 아래에 따로 설명해야 하는데 일단은 정보를 잘게 쪼개서 저장해둔 공간이라고 생각하자. 페이지 테이블은 정보를 어디에다 저장해뒀는지 적어둔 일종의 지도로, 각 칸(=페이지)에는 분할한 정보가 들어있다.

 

테이블을 보면 가장 위부터 아래까지 PTE 0 ~ PTE 7까지 적혀있는 게 보인다. PTE는 Page Table Entity로, 지금 여기서는 일단 무시하고 지도에 매겨둔 인덱스 정도라고만 생각하자. 위에서부터 PTE 0은 NULL로 아무 데이터도 들어있지 않다. PTE 1, PTE 2, PTE 4, PTE 7은 하늘색이 색칠되어 있는데 이 정보들은 physical memory와 연결되어 있다. 즉, 할당(=allocated)된 정보이다. 그리고 흰색으로 비어있는 부분인 PTE 3, PTE 6은 virtual memory를 가리키고 있는데, 저기가 바로 하드디스크이다.

 

가상 페이지 정보는 서로 다른 세부 상태 중 하나로 정해진다.

 

1) Unallocated: 위의 NULL 상태처럼 페이지가 가상 메모리 시스템으로부터 정보를 할당받지 못한 상황이다. 즉, 아무 데이터도 갖고 있지 않다.

 

2) Cached: VM으로부터 메모리를 할당받았으며, 물리 메모리에 캐시되어 있는 페이지 정보이다. 즉, 이 페이지에는 정보가 들어있으며 그 정보가 DRAM에 저장되어 있다. 

 

3) Uncached: VM으로부터 메모리를 할당받긴 했으나 물리 메모리에 캐시되어 있지 않은 상태이다. 이 경우에는 하드 디스크에 저장된다.

 

"응? 그럼 하드 디스크에 정보가 저장된 거 아냐?! 아까는 하드 디스크에 물리 주소를 할당하지 않는다 했는데?!"

 

..이미지 한 장만 더 보자. 이것까지 보면 진짜 이해 쌉가능이다.

 

위에서 어떤 건 캐시에 저장하고 어떤 건 하드에 저장해둔다고 했다. 그런데 CPU에서는 모두 다 메모리에 있다고 생각하고 부르고 실제로도 물리 주소는 전부 메모리에 배정되어 있다고 했다. 그런데 하드에 저장해둔 정보도 있다고 했으니 경우는 두 가지이다.

 

1) CPU에서 요청한 정보가 메인 메모리 내에 캐시되어 있을 때: Page hit

 

아래 이미지를 보자.

 

(1)먼저 CPU 프로세서에서 MMU에다가 가상 주소를 요청한다.

 

(2)그러면 MMU는 이를 물리 주소로 변경해 Page Table Entity address(PTEA)를 요청한다. 즉, 아까 말했던 지도(=페이지 테이블)에서 CPU에서 요청한 정보가 어느 페이지에 할당되어 있는지, 할당되어 있다면 캐시에 있는지 없는지를 확인하는 작업이다.

 

(3)지금 경우는 메인 메모리 내에 캐시되어 있는 경우이니 지도로부터 해당 페이지의 위치(메인 메모리 내 물리 주소)를 전달 받는다.

 

(4)그러고 나면 MMU는 다시 메인 메모리로 물리 주소를 요청하고,

 

(5)메인 메모리는 CPU에 해당 물리 주소에 있는 데이터를 전송한다.

 

위와 같은 경우는 메인 메모리 내에 캐시되어 있는 페이지를 때려 맞혔다(hit)고 해서 page hit이라고 한다. 그런데 CPU에서 요청한 정보가 메인 메모리 내에 캐시되어 있지 않다면? 즉, 하드 디스크에 있는 정보를 불러오려고 하면?

 

2) CPU에서 요청한 정보가 메인 메모리 내에 캐시되어 있지 않을 때: Page fault

 

Page hit과 마찬가지로 1, 2, 3까지는 동일하다. 하지만 (3)에서 PTE를 전달받는데, 이때 메인 메모리 내에 없다는 exception이라는 정보를 받게 된다. 따라서

 

(4) page fault exception handler를 통해 메인 메모리와 하드 디스크 사이에 페이지 교환이 일어나는데, 이를 page swap이라고 한다. 페이지를 교환하는 상황까지 갔다는 건 메인 메모리에는 여분의 자리가 없다는 말이 된다. (그러니 캐시에 저장 안하고 하드에 저장했겠지)

 

(5)그러니 메인 메모리에 캐시되어 있는 페이지 중, 가장 오래됐거나 가장 안 쓰는 page를 복사해 하드 디스크로 옮긴다. 이 Page를 victim page라고 한다. (희생양)

 

(6)그러고서 메인 메모리 내에 비어있는 자리에 디스크로부터 우리가 요청하려는 그 페이지가 자리를 차지한다. 이렇게 하고 나면 (3)을 다시 업데이트하는데, 그러고 나면 아까 fault exception이 발생했던 (4)에서 faulting instrction을 재시작한다. 이때는 이미 (3) PTE가 메인 메모리에 있으니 page hit이 되는 상황. 여기서부터는 위의 page hit과 마찬가지로 정보를 CPU에 보내준다.

 

이렇게 하드 디스크와 메인 메모리 사이에서 페이지를 전송하는 행위를 page swapping이라고 한다.

 

Locality: VM이 느리지 않고 잘 동작하는 이유 & Thrashing

 

그러면 추가 질문이 무럭무럭 자라날텐데, "아니, 이러면 어쨌거나 느린 거 아님? page fault 일어나면 느린 건 매한가지인데?" 이론 상으로는 그러한데, 실제적으로는 그렇지 않다. 여기서 Locality라는 개념이 나오는데, 간단하게만 말하면 우리가 자주 사용하는 정보와 그렇지 않은 정보 사이에는 거리가 멀기 때문에 자주 쓰는 애들은 거기서 거기이며 다 비슷한 위치에 있다는 느낌으로 받아들이면 된다. 보다 자세한 내용은 여기를 참조. 캐시 메모리라는 개념은 본질적으로 같기 때문에 여기서도 locality가 동일하게 작용한다.

 

하지만 잘 동작하게 만드는 지 여부는 프로그래머의 실력에 달려있다. 프로그램이 좋은 temporal locality를 갖고 있다면 VM 시스템이 잘 동작하겠으나, 모든 프로그램이 좋은 locality를 보이지는 않는다. 만약 작업하는 데이터 크기가 물리 메모리 크기를 넘어서면 어떻게 될까? 한 번에 모든 데이터를 물리 주소에 담을 수 없으니 넘쳐서 하드 디스크까지 침범하게 되고, 매 번 작업할 때마다 page가 계속해서 swap하는 일이 발생해 극도로 느려지게 된다. 이와 같은 상황을 thrashing이라고 한다. 따라서 VM이 효율적이더라도 프로그램 퍼포먼스가 그지같으면 thrashing이 일어날 가능성을 고려해야 한다.

 

 

참고 자료

 

페이징 관련 글: https://jhnyang.tistory.com/290

메모리 단편화(Fragmentation): https://jhnyang.tistory.com/264

운영체제 관련 글(나중에 꼭 다시 읽어보자 여기 엄청 잘 정리되어 있음!): https://jhnyang.tistory.com/notice/31