[OS] 가상 메모리 #2 (Virtual Memory)

floatFirstTOC: right

🖥️ 시작하며

📌 Page Tables의 문제 해결

• 지금껏 가상 주소 공간의 페이지 수 전체를 정적으로 잡았다.
→ 동적으로 생성하면 어떨까?

• 다른 수준의 방향성을 사용해보자.
→ Two-level, hierarchical, hashed, etc.
 

📌 Two-level Page Tables

• Master Page
Secondary Page 로 가는 주소를 담은 페이지

• Secondary Page
원래 싱글 페이지 테이블에서 쓰던 방식처럼, PFN 을 가리킴



1. p1 이 3을, p2 가 4를 가리킨다.
2. Outer(Master) Page 에서 idx 3 찾아서 그 주소로 찾아간다. (이 주소가 Secondary Page)
3. Secondary Page 에서 idx 4 찾아서 그 주소로 찾아간다. (PFN)

💡 예를 들어보자

• 32bit 운영체제, 4KB pages, PTE(Page Table Entry) 4bytes

• Secondary Page Table은 미리 만들지 않아도 되기 때문에 공간을 절약할 수 있다!
→ 하지만 그만큼 메모리 접근 시간 오버헤드가 발생한다.
 

⚙️ Two-level 말고도 3, 4 등 Multi-level도 만들 수 있다.

📌 Hashed Tables

• 보통 모듈러 연산을 이용해 해시 테이블을 생성
• % 3 → 3개의 PTE
• % 1024 → 1024개의 PTE

• 해시 특성상 충돌이 가능하므로, 연결 리스트 등을 이용해 자료를 관리함
→ Search를 여러번 하므로 메모리 접근 오버헤드 발생!

• 노드가 가져야 하는 요소:
• 가상 페이지 번호 (Virtual Page Number): 이 요소가 대응하는 가상 페이지의 번호
• 페이지 프레임 번호 (Page Frame Number): 가상 페이지가 매핑된 실제 물리 메모리의 페이지 프레임 번호
• 연결 리스트에서 다음 요소를 가리키는 포인터

📌 Clustered Page Tables

• Two-level처럼 해시 테이블을 여러 개 만듦
노드 여러개를 만들지 말고, 클러스터로 생성해 시간 오버헤드를 줄이도록 함
각 항복은 연속된 페이지 테이블 블럭에 대한 매핑 정보를 저장!

📌 Inverted Page Tables

• Page Table에 PID , VPN (가상 메모리 번호) 가 들어감

• Page Table Size
PID 와 VPN 이 각각 4byte씩 차지한다고 치면, Page Table의 크기는 가 된다.

• PID를 관리해야 하므로 유지관리가 힘듦

• 페이지 테이블이 하나만 존재하므로 필요 메모리 감소
→ 페이지 참조가 발생할 때 시간 오버헤드 증가
→ 해시 테이블 사용해 검색을 하나 또는 몇 개의 Page Table 항목으로 제한

⚙️ Inverted가 가장 공간 오버헤드 좋음, Search 오버헤드는 가장 큼

🔍 Paging Page Tables

1️⃣ 물리 메모리

• 주소 지정이 쉽고, 변환이 필요하지 않음

• 할당된 페이지 테이블이 VAS가 작동하는 동안 계속 할당되어야 함

2️⃣ 가상 메모리 (OS 가상 메모리 공간)

• Page Table 자체도 Swapping이 가능하게 됨

• 그러나 이중 변환의 필요성

• Master Page Table 은 디스크로 스왑되면 안됨 (찾을 수 없게 됨)

• 4GB의 가상 주소 공간의 커널 코드에 페이지 테이블이 존재하게 됨
→ 이 부분은 물리 메모리 한 공간에 한꺼번에 매핑됨

3️⃣ 페이지 테이블과 운영 체제 주소 공간의 페이징

🔍 TLBs

• 페이징 기법을 사용하면 메모리 → 메모리를 거치므로 접근 비용이 배가 됨

• 이를 효율적으로 하기 위해 캐싱해야 함
→ Translation Lookaside Buffer (TLB) 사용
 

📌 TLB 구조

• TLB는 Hit rate가 높아야 하기 때문에 Fully associative cache

• 캐시 태그 (Cache Tags):
• TLB의 캐시 태그는 가상 페이지 번호(VPN, Virtual Page Numbers)
가상 주소가 TLB에 들어올 때, 가상 페이지 번호를 기준으로 TLB를 조회

• 캐시 값 (Cache Values):
• TLB의 캐시 값은 페이지 테이블 항목(PTE, Page Table Entries)
PTE는 가상 페이지가 물리 메모리의 어느 페이지 프레임에 매핑되는지를 나타냄
 

📌 TLB 지역성

• TLB 항목 수:
• TLB는 보통 16~48개 각 항목은 가상 페이지 번호와 해당하는 PTE를 저장
• TLB의 크기는 보통 64~192KB

• 히트율의 중요성:
• 높은 히트율은 시스템 성능에 매우 중요
• 프로세스는 보통 한 번에 소수의 페이지를 사용하므로, TLB는 "Hot Set" 또는 "Working Set"을 캐싱하여 높은 히트율을 유지

📌 TLBs 특징

• 보통 99% 히트가 난다. 성능이 좋음

💡TLB 미스 처리

• 하드웨어 (MMU)
• 하드웨어니까 Page Table 위치만 알면 됨 (register 존재)
• Page Table이 정해진 포맷대로만 있어야 한다는 단점 존재

• 소프트웨어 (OS)
• OS에서 올바른 PTE를 찾아 TLB에 로드
• 빨라야 하지만, 일반적으로 20-200 사이클
• TLB는 하드웨어라 Instruction이 존재하긴 함
• 운영체제 마음대로 Page Table을 설정할 수 있다는 장점이 있지만 성능은 하락

📌 TLB 관리

• OS는 TLB와 페이지 테이블의 일관성을 보장
• 페이지 테이블에서 무언가가 변경되면, 해당 TLB 항목을 무효화해야 함

💡 context switch시 TLB 리로드

• 각 프로세스는 일반적으로 자체 페이지 테이블을 가짐
→ context switch가 일어나면 TLB를 리로드해야 함 (TLB Flush)

• IA-32에서는 CR3(페이지 디렉토리 베이스 레지스터)의 내용이 변경될 때 TLB가 자동으로 플러시됨

• TLB 항목에 PID를 저장할 수도 있지만, 이는 비용이 많이 듦

💡TLB 미스 처리

• 희생될 PTE를 선택하는 정책을 TLB replacement policy 라고 함

• 하드웨어에서 구현되며, 일반적으로 간단함 (예: LRU)

🔍 Memory Reference

1️⃣ 일반적인 경우 (TLB 히트, 99% 이상)

1. 읽기/쓰기가 MMU의 TLB로 전달됨

2. 가상 주소의 페이지 번호를 사용하여 TLB가 조회를 수행함

3. 페이지 번호가 일치하면, PTE를 반환함

4. TLB는 PTE의 보호 설정을 검증하여 읽기/쓰기 허용 여부를 확인함

5. PTE는 해당 페이지를 보유한 물리 프레임을 지정함

6. MMU는 물리 프레임과 오프셋을 결합하여 물리 주소를 생성함

7. MMU는 해당 물리 주소에서 읽기를 수행하고, 값을 CPU에 반환함

2️⃣ TLB 미스: 두 가지 구현 선택

1. MMU가 메모리에 있는 페이지 테이블에서 PTE를 로드
• 하드웨어가 TLB 관리 : 이 단계에서 OS가 관여하지 않음
• OS는 하드웨어가 직접 접근할 수 있도록 페이지 테이블을 이미 설정해 둠

2. OS로 트랩
• 소프트웨어가 TLB 관리 : 이 시점에서 OS가 개입
• OS가 페이지 테이블에서 조회하여 PTE를 TLB에 로드
• OS가 예외에서 복귀하고, TLB가 계속 진행

• TLB 미스를 처리한 후, 해당 주소에 대한 유효한 PTE가 TLB에 존재하게 됨

• 따라서 요청된 주소는 TLB 히트 케이스로 처리됨

3️⃣ TLB 미스: 재귀적 결함 (Recursive Fault)

1. 페이지 테이블이 Swapping되어 있으면 재귀적 오류 가능성
• 페이지 테이블이 OS 가상 주소 공간에 있다고 가정

2. Page fault handler가 페이지 테이블을 물리 메모리에 로드
• 그런 다음, PTE를 TLB에 로드

3. TLB에 PTE가 로드된 후:
• TLB가 PTE를 가지게 되면, 주소 변환을 다시 시작함
• 일반적인 경우는 PTE가 메모리에 있는 유효한 페이지를 참조하는 경우임

4. 드문 경우, TLB가 다시 결함 발생:
• 드문 경우지만, TLB가 다시 결함을 일으킬 수 있음
• 예를 들어, 페이지가 유효하지 않은 경우 다시 TLB 미스가 발생
 
 

📌 Page Fault가 나는 상황

1. 읽기, 쓰기, 실행 권한 등이 허용되지 않은 작업이 수행될 경우 (Protection fault)

2. 유효하지 않은 경우 (가상 페이지가 할당되지 않았거나 물리 메모리에 페이지 없음)

💡 TLB가 OS에 트랩

1. 읽기/쓰기/실행 - 작업이 허용되지 않음 (보호 결함)
• OS는 보통 해당 결함을 프로세스로 다시 전달
• 또는 특정 상황에서 OS가 특별한 처리를 할 수 있음
• 예: 복사 시 쓰기(Copy on Write), 매핑된 파일

2. 무효 (Invalid)
• 할당되지 않은 경우: OS는 결함을 프로세스로 다시 전달
• 예: 프로세스가 접근하려는 페이지가 아직 할당되지 않은 경우
• 물리 메모리에 없는 경우: OS는 다음 단계를 수행
• 프레임 할당: 물리 메모리에서 새로운 페이지 프레임을 할당
• 디스크에서 읽기: 디스크에서 해당 페이지를 읽어와 할당된 프레임에 로드
• PTE 매핑: 페이지 테이블 항목(PTE)을 물리 프레임에 매핑