[DevLog][CSAPP] 9장 가상메모리 (9.1~9.4)

책을 읽으며 흐름을 정리..

---

가상메모리 Virtual Memory

가상메모리는 '사용자가 하나의 큰 메인메모리를 사용하는 것 같도록 느끼게끔' 실제 사용가능한 저장 자원을 추상화하는 메모리 관리 기법이다.

1. 메인 메모리를 디스크에 저장된 주소공간의 캐시로 취급하여 메인 메모리 내 활성화된 영역만 유지하고, 데이터를 디스크와 메모리 간에 필요한 경우에만 전달한다.
2. 각 프로세스에 통일된 주소공간을 제공하여 메모리 관리를 단순화한다.
3. 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

9.1. 물리 및 가상주소 방식

01) 물리주소 방식

메모리에 접근하는 것은 물리주소 방식이 있고 가상주소 방식이 있다. 물리주소 방식은 메모리의 주소를 그대로 사용하는 것으로, 주소 0에 1바이트, 1에 1바이트 .. 와 같은 식이다. 물리주소 방식은 단순하고 직관적이며 초기 PC에서 많이 사용하였다.

1. 프로세서는 유효한 물리주소를 생성하고 메모리에 전달한다. [메모리 버스]
2. 메모리는 전달받은 물리주소에 있는 값을 전달한다.
3. 프로세서는 전달받은 값을 레지스터에 저장한다.

02) 가상주소 방식

가상주소 방식을 사용하면 프로세서는 유효한 가상주소를 만들어 메모리에 접근하고자 한다. 이를 위해 가상주소와 물리주소간의 번역 (또는 매핑) 과정이 필요한데, 이것을 메모리 관리 유닛 (MMU)에서 담당한다.

1. 프로세서는 유효한 가상주소를 만들어 MMU에 넘긴다.
2. MMU는 '주소 번역' 이라고 불리는 가상-물리주소 매핑을 한다.
3. 번역된 주소가 메모리에 전달되면, 메모리는 주소에 저장된 값을 다시 프로세서에게 넘긴다.

9.2. 주소공간

CPU는 가상 주소공간이라고 불리는 $N = 2^n$ 주소의 주소공간에서 가상의 주소를 생성한다. 주소공간이 가장 큰 주소를 표현하는 데 필요한 비트 수가 주소공간의 크기가 된다. 따라서 32bit 주소공간은 32비트 주소까지 표현가능하며, 64bit 주소공간은 64비트의 주소값까지 표현할 수 있다.

💡 연습문제 9.1

kilo, mega, giga, tera, peta, exa

가상주소공간의 비트수	가상주소의 수	가상주소 최댓값
4	$2^4$	$2^4-1$
14	$2^14 = 2^4K$	$2^4K-1$
24	$2^24 = 2^4M$	$2^4M-1$
46	$2^6T$	$2^6T-1$
54	$2^4P$	$2^4P-1$

9.3. 캐싱 도구로서의 VM

👀 캐싱이란 캐시는 데이터나 값을 미리 복사해놓는 것 (또는 그러한 임시장소)이다.

• 가상메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 각 바이트는 특정한 가상주소를 가진다.
• 배열의 각 바이트는 특정한 가상주소를 갖고, 이는 배열의 인덱스로 작용한다.
• 배열의 정보는 메인메모리에 캐시된다. 캐시는 블록 단위로 분할된다?

시스템은 가상메모리를 특정 사이즈의 블록으로 분할하여 관리하는데, 이 분할된 블록을 '가상페이지 Virtual Page'라고 한다. 가상페이지는 $P = 2p$ 바이트 크기를 갖는다. 분할된 물리 메모리는 '물리 프레임 Physical Frame'이라고 한다.

가상페이지는 세 가지로 나누어질 수 있다.

• Unallocated: 아직 할당되지 않음
• Cached: 할당되었고 물리 메모리에 캐시되어 있음
• Uncached: 할당되었지만 물리 메모리에 캐시되어 있지 않음

👀 동적 램 DRAM? 일단 Random-Access-Memory 랜덤-접근 메모리라는 것이 뭘까? Random의 의미가 중요한데, 이는 메모리상의 어느 위치에 저장된 데이터든지 접근하는데 걸리는 시간이 동일하다는 것이다. (반면 디스크는 저장된 위치에 따라 다르다.) 램에는 정적 램이 있고, 동적 램이 있다. 정적 램 (SRAM)은 캐시메모리고, CPU칩 내/외부에 장착된다. 메모리 계층구조에서 보았던 L1, L2, L3가 SRAM이다. 동적 램 (DRAM)은 메인메모리에 사용된다. SRAM은 DRAM보다 빠르고 비싸다.

9.3.1. DRAM 캐시의 구성

DRAM 캐시 미스는 (잘못된 페이지 매핑) 디스크에서 처리된다. 그러나 SRAM(L1, L2, L3) 캐시 미스는 DRAM에서 처리된다. 따라서 DRAM에서의 미스 처리 비용은 SRAM 대비 매우 비싸다고 할 수 있다. 또한, 디스크로부터 첫 번째 바이트를 읽는 시간은 그 후 연속적인 바이트를 읽는 시간보다 100,000배 느리다. 이 비용 때문에 가상페이지의 크기가 커지고 있으며, 4KB에서 2MB까지의 값을 가진다. (일반적으로 4KB, 8KB)

👀 캐시 미스 Cache Miss 캐시 메모리에 원하는 데이터나 명령어가 없는 상태. 내가 데이터를 요청했는데, 캐시에 없으면 캐시는 주 메모리로부터 데이터를 가져와야 한다. (가장 느린 메모리 액세스) 페이지와 관련해서 캐시 미스란 결국 Page Fault를 의미.

👀 페이지의 크기와 무슨 관계? 페이지의 크기가 작으면 페이지 폴트가 더 자주 발생한다. 또한 초기에 페이지를 접근할 때, 페이지가 작기 때문에 더 많은 페이지를 접근해야 할 수 있다. 따라서 충분히 커야 한다. 페이지가 크면 페이지 폴트가 덜 발생하지만, 페이지 내에 실제로 사용되지 않는 데이터까지 메모리에 로드할 수도 있기 때문에 메모리 낭비의 여지가 있다. (📌 더 공부해 보자)

9.3.2. 페이지 테이블

가상페이지와 물리프레임 간의 매핑에 이용되는 테이블이다. 페이지 테이블은 각각의 페이지 테이블 엔트리 (Page Table Entry)로 구성된다. PTE는 페이지의 할당 여부를 체크하는 유효비트와 해당 논리주소에 대응되는 물리주소와 같은 정보를 포함한다.

CPU는 페이지의 번호 p, 페이지 내의 상대 주소 (offset) d를 조합하여 논리주소를 생성한다. 페이지 테이블에서 p번째에 있는 물리주소 f로 접근하는데, 이 때 접근하는 주소는 $f\times S+d$가 된다. ($S$는 페이지 사이즈)

9.3.3. 페이지 적중

CPU는 가상주소를 인덱스로 하여 페이지 테이블에서 이에 대응하는 PTE를 찾는다. PTE의 유효비트가 1이면 (즉 DRAM에 캐시되어 있으면) 물리주소를 구성하여 접근한다.

9.3.4. 페이지 오류

Page Fault는 가상주소를 인덱스로 하는 PTE의 유효비트가 0일때, 즉 DRAM에 해당 워드가 캐시되어 있지 않을 때 일어난다. 이 경우 주소 번역 하드웨어는 예외상황을 유발하여 DRAM에서 희생자 페이지(victim page)를 선택하고, 이 페이지를 uncache 한 다음 디스크로부터 해당 페이지를 복제한다.



[과정]

1. 나는 VP3 내의 워드를 읽고 싶다.
2. VP3의 PTE를 찾는다. 유효비트가 0이므로 page fault가 발생한다.
3. 주소 번역 하드웨어는 DRAM에 캐시된 페이지 중 victim page VP4를 선택한다.
4. VP4를 디스크로 복제한다.
5. VP3을 디스크에서 DRAM의 VP4 자리로 (물리주소 PP3) 복제한다.
6. PTE 3을 갱신하고 리턴한다.
7. 다시 VP3을 찾으면, 적중한다.

과정 4는 디스크에 있는 페이지와 메인메모리에 있는 페이지가 서로 다른 경우를 대비하기 위함이다. 즉 프로세스가 시작된 이후 페이지에 변경사항이 있었다면, 이를 디스크에 다시 write해야 한다. 그러나 변경사항이 없었다면? 안 해도 된다. 희생자 페이지를 내릴 때 디스크에 매번 write하기보다, 애초에 다시 write 안 해도 되는 페이지를 내리면 된다. 이를 위해 페이지의 변경여부를 체크하는 비트를 두는데, 이를 오염비트(dirty bit or modify bit)라고 한다.

👀 희생자 페이지를 찾는 기준은? [GPT]

Page fault가 발생할 때 운영체제는 희생자 페이지(victim page)를 선택하여 디스크에 스왑 아웃(swap out)함으로써 메모리 공간을 확보합니다. 이때, 희생자 페이지를 선택하기 위한 몇 가지 알고리즘이 있습니다. 다음은 일반적으로 사용되는 페이지 교체 알고리즘들과 그 기준입니다:

1. FIFO (First-In, First-Out): 가장 먼저 메모리에 로드된 페이지부터 교체합니다. 페이지가 메모리에 로드된 순서를 기억하는 큐를 유지합니다.
2. Optimal (or MIN): 미래의 페이지 참조를 봤을 때, 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 이 알고리즘은 이론적이며 실제 시스템에서 구현하기는 어렵습니다. 그 이유는 미래의 페이지 참조를 미리 알 수 없기 때문입니다.
3. LRU (Least Recently Used): 가장 오랫동안 참조되지 않은 페이지를 교체합니다. 페이지 참조의 최근 순서를 추적하는 데 여러 가지 방법(카운터, 스택 등)이 사용될 수 있습니다.
4. Random: 교체될 페이지를 무작위로 선택합니다. (최악의 방법)
5. Clock (or Second-Chance Algorithm): 이 알고리즘은 순환 큐와 함께 사용됩니다. 각 페이지는 참조 비트를 가집니다. 페이지 폴트가 발생하면 포인터가 다음 페이지로 이동하면서 참조 비트를 확인합니다. 참조 비트가 0이면 해당 페이지를 교체하고, 1이면 0으로 설정한 후 다음 페이지로 이동합니다.

👀 가상메모리의 용어 정리

1. 페이지 Page: 가상메모리의 기본 단위
2. 스와핑/페이징 Swapping/Paging: 디스크와 메모리 간의 페이지 전송
3. 요구 페이징 Demand Paging: 페이지를 요구할 때까지 페이지를 메모리에 올리지 않는 방식

+) 요구 페이징을 하면 Page Fault는 필연적으로 발생. 현대의 모든 시스템이 사용하는 페이징 방식.

9.3.5 페이지의 할당

malloc 을 불렀다. 어떤 일이 일어나는가? 디스크는 새로운 메모리 공간을 만들고 페이지 테이블 엔트리가 이 공간을 가리키도록 설정한다.

9.3.6. 문제해결을 위한 또 한 번의 지역성의 등장

프로그램을 실행 중인 것만 부분적으로 적재했다가, 다시 내렸다가.. 하는 과정에서 시간이 소모되지 않을까? 그리고 실제 물리 메모리보다 더 많은 가상 메모리 주소를 사용해도 문제가 없는 이유는 뭘까? 비효율적으로 보이는 모든 과정이 잘 동작하는 이유가 바로 지역성 locality이다.

🔥 Locality of Reference

다른 말로는 Principle of Locality라고도 한다. 결국 '한 번 참조된 것이 다음에도 참조될 가능성이 높다'와 '참조된 것 근처의 것이 참조될 가능성이 높다'는 것이다.

• 프로그램이 실행되면서 메모리의 특정 부분을 반복적으로 참조하는 경향 (CPU의 경향성)
• the tendency of a processor to access the same set of memory locations repetitively over a short period of time. wikipedia

시간적 지역성 Temporal Locality: '한 번 참조된 것이 다음에도 참조될 가능성이 높다.' (ex.반복문 내 변수)

공간적 지역성 Spatial Locality: '참조된 것 근처의 것이 참조될 가능성이 높다.' (ex. 배열 원소)

시스템이 참조 지역성을 갖기 때문에, 프로세스가 실행될 때 어떤 페이지들을 반복적으로 사용하게 된다. 이렇게 '주로 사용하는 페이지나 블록들의 집합'을 일컬어 동작 집합 Working Set이라고 한다. 동작 집합이 물리메모리(메인메모리)의 크기를 초과해서 프로세스가 실행되는 동안 페이지의 교체가 빈번하게 일어날 경우 프로그램은 멈춰있는 것처럼 보이게 된다. 이 현상을 쓰래싱 Thrashing이라고 한다. (메모리와 디스크 간의 페이지 교체가 너무 자주 발생하면서 실제 프로세스의 실행이 제대로 이루어지지 않는 상태)

9.4. 메모리 관리를 위한 도구로서의 VM

• 페이지 테이블은 프로세스마다 별도로 제공된다.
• 각 프로세스는 페이지를 공유하기도 한다. (다수의 가상페이지가 동일한 물리프레임에 매핑)

VM이 메모리 할당을 단순화한다.

1. 링킹을 단순화한다: 주소공간을 별도로 둬서, 각 프로세스들이 통일된 포맷을 갖게 해 준다. (ex. 코드 세그먼트는 항상 가상주소 0x400000에서 시작) 이러한 통일성을 통해 링커의 설계와 구현을 단순화할 수 있다.
2. 로딩을 단순화한다: 프로세스가 로드될 때 시스템은 모든 메모리 세그먼트를 다 메인메모리에 로드하는 것이 아니다. 코드와 데이터 세그먼트를 위한 가상페이지를 할당(만) 하고, 이들의 페이지 테이블 엔트리를 목적파일의 해당 위치를 가리키게 한다. 그리고 필요할 때 메인메모리에 로드하여 사용한다. 오호..이를 지연 로딩 또는 lazy loading이라고 한다. (필요할 때 로드하므로 효율적이고, 프로세스의 시작이 빨라지며, 궁극적으로는 메모리를 절약할 수 있다.) + 연속된 가상페이지를 파일 내 각 위치로 매핑하는 것을 메모리 매핑이라고 하고, 이걸 하는 시스템 콜이 mmap()다. (mmap는 9.8절에서 다시 본다.)
3. 공유를 단순화해준다: 두 프로그램이 모두 printf루틴을 사용한다고 할 때 가상메모리 시스템은 물리메모리에 printf를 두 번 적재하게 될까? 아니다.. 한 번만 적재하고, 두 프로그램이 공유하여 사용할 수 있도록 각각의 가상페이지 테이블에서 이 물리프레임과 매핑해주기만 하면 된다.
4. 메모리 할당을 단순화해준다: malloc에서 추가적인 힙 공간을 요청하는 경우를 생각해 보자. 운영헤제는 가상메모리 페이지를 할당한 다음 물리메모리에 있는 물리프레임과 매핑한다. 이때 물리메모리에서 연속적인 페이지를 찾을 필요가 없다. (랜덤하다)

Runtime Memory Image

교재 670p 그림 7.15. 각 가상메모리 영역

---

운영체제 수업에서 분명 다 봤던 내용인데😇 새삼 그때는 공부를 전혀 안 했다는 사실을 깨닫는다. 필기록에 시험에 어느 부분 나오는지만 메모되어 있는 것을 보고 후회막심함을 느꼈다. 책을 읽으면서 조금 신기했?던 부분은 CPU가 요구 페이징을 한다는 점이다. Page Fault라고 해서 어떤 예방되어야 할 오류 상황이라고 생각했는데, 오히려 '필요할 때까지 미룬다'는 전략을 고수하는 것이 언뜻 의아하게 느껴지기도 했다. 나중에 다른 문제와 관련해서도 비슷한 아이디어가 나오는 것으로 보아, 결국 '필요할 때까지 하지 않는 전략' 은 때때로 불필요한 시간의 소모를 줄여 주는 것 같다. 이는 사용자로부터 언제, 무엇이 요청될지 결국 시스템은 예측할 수 없기 때문이지 않을까 생각이 들었다. 그 밖에도 캐시 지역성 개념이 신기했는데, 메모리 간의 계층 (더 빠른 것이 더 느린 것의 캐시가 된다) 구조로 인해 복잡해 보이는 페이지 로드, 매핑 방법이 실제로는 빠른 속도를 갖는다는 점이.. 멋진 것 같다. 이 모든 내용들을 진짜 코드 돌리면서 눈으로 확인하고 싶어서 perf를 설치했다. 사용법을 공부해보고 차차 정리해두어야겠다.