5.7 Virtual Memory

 

1. Virtual Memory의 개념

 

**Virtual Memory (가상 메모리)**는 **주 메모리(Main Memory)**가 **보조 저장장치(Secondary Storage)**를 위한 캐시 역할을 하도록 설계된 기술이다.

• 가상 메모리를 통해 프로그램은 물리 메모리 크기에 구애받지 않고 실행 가능하다.

• 메모리 관리를 단순화하며, 여러 프로그램이 동시에 메모리를 공유할 수 있도록 한다.

 

 

2. Virtual Memory의 주요 동기

 

1. 메모리 공유:

• 여러 프로그램이 동일한 물리 메모리를 안전하고 효율적으로 공유.

• 프로그램이 메모리를 읽고 쓰더라도, 다른 프로그램의 데이터에 영향을 미치지 않도록 보호.

 

2. 메모리 용량 확장:

• 프로그램 크기가 주 메모리 크기를 초과하더라도 실행 가능.

• 개발자는 프로그램을 직접 나눌 필요 없이, OS가 자동으로 관리.

 

 

 

3. Virtual Memory와 Address Translation (주소 변환)

 

가상 메모리는 프로그램이 사용하는 **가상 주소(Virtual Address)**를 **물리 주소(Physical Address)**로 매핑한다.

• 주소 변환(Address Translation):

OS와 하드웨어는 가상 주소를 물리 주소로 변환해, 올바른 데이터에 접근 가능하게 한다.

 

프로세스 간 메모리 보호:

• 각 프로그램은 **고유한 주소 공간(Address Space)**을 가지며, 다른 프로그램의 데이터에 접근할 수 없다.

• 이는 **메모리 보호(protection)**를 통해 구현된다.

 

 

 

4. Virtual Memory의 주요 구성 요소

 

1. Virtual Address (가상 주소):

프로그램이 사용하는 논리적인 주소.

2. Physical Address (물리 주소):

실제 메모리(DRAM)에서의 위치.

3. Page (페이지):

가상 메모리와 물리 메모리를 나누는 고정 크기 단위.

• 일반적으로 4KB에서 64KB 크기 사용.

4. Page Table (페이지 테이블):

• 각 가상 페이지를 물리 페이지로 매핑하는 데이터 구조.

• OS가 관리하며, 변환 속도를 높이기 위해 **TLB (Translation Lookaside Buffer)**와 함께 사용.

 

 

 

5. Address Translation (주소 변환) 과정

그림 5.24 설명:

 

• 가상 주소는 물리 주소로 변환되고, 일부 페이지는 디스크에 저장될 수 있다.

• 캐시 원리와 유사:

• CPU는 최근에 사용된 페이지가 캐시에 있기를 기대.

• 가상 페이지가 메인 메모리에 없으면 Page Fault (페이지 폴트) 발생.

 

 

그림 5.25 설명:

 

• 가상 주소는 두 부분으로 나뉜다:

• Virtual Page Number (VPN): 페이지의 인덱스.

• Page Offset: 페이지 내부 데이터의 위치.

• 변환:

1. VPN은 페이지 테이블을 통해 물리 페이지 번호로 변환.

2. Page Offset은 물리 페이지 내 데이터 위치를 지정.

 

 

 

 

6. Virtual Memory 설계 시 고려사항

 

1. 페이지 크기(Page Size):

• 페이지 크기가 클수록 디스크 액세스 오버헤드를 줄이지만, 메모리 낭비가 증가.

• 일반적으로 4KB~64KB 범위 사용.

 

2. Page Fault 처리:

• Page Fault: 접근한 페이지가 메모리에 없는 경우.

• 디스크에서 데이터를 가져오므로 매우 높은 비용 발생.

• 오버헤드를 줄이기 위해 소프트웨어로 페이지 배치 최적화.

 

3. 쓰기 정책:

• Virtual Memory는 Write-Back 정책 사용.

• Write-Through는 디스크 쓰기 속도가 느리기 때문에 적합하지 않음.

 

 

 

7. Segmentation과 Paging

 

1. Paging:

• 고정 크기 블록(페이지)을 기반으로 메모리 관리.

• 간단하고 효율적.

2. Segmentation:

• 가변 크기 블록(세그먼트)을 기반으로 메모리 관리.

• 주소: 세그먼트 번호와 오프셋으로 구성.

• 세그먼트는 크기가 다양해 프래그먼테이션(Fragmentation) 문제 발생 가능.

 

---

Placing a Page and Finding it Again

 

 

1. 페이지 배치와 Page Table

 

Virtual Memory 시스템에서 **페이지 폴트(Page Fault)**는 매우 높은 비용이 발생한다.

• 디스크 액세스가 수백만 클록 사이클을 소모하기 때문에 페이지 폴트 발생 빈도를 줄이는 것이 중요하다.

• Page Table은 가상 페이지 번호를 물리 페이지 번호로 매핑하는 데이터 구조로, 페이지를 찾는 데 핵심적인 역할을 한다.

 

Page Table의 역할:

 

1. 페이지 매핑:

가상 메모리의 각 페이지를 물리 메모리 또는 디스크 주소로 매핑.

2. 페이지 상태 추적:

• Valid Bit: 페이지가 메인 메모리에 있는지 여부를 나타냄.

• 페이지가 메모리에 없으면 페이지 폴트가 발생.

 

Page Table Register (PTR):

 

• Page Table의 시작 주소를 저장.

• 각 프로세스는 고유한 Page Table을 가지며, 운영 체제가 프로세스 변경 시 PTR을 갱신.

 

 

 

2. 페이지 폴트(Page Fault)

 

• Page Fault란?

프로그램이 접근한 페이지가 메모리에 없는 경우 발생.

• 페이지는 디스크에서 읽혀야 하며, 이는 큰 오버헤드를 초래.

 

Page Fault 처리 과정:

 

1. 예외 처리:

CPU는 페이지 폴트를 처리하기 위해 OS로 제어를 전달.

2. 디스크에서 페이지 로드:

OS는 디스크에서 페이지를 가져와 메모리에 배치.

3. LRU 또는 다른 교체 알고리즘을 사용해 페이지 교체:

오래된 페이지를 Swap Space로 옮기고 새로운 페이지를 적재.

 

 

 

3. Page Table 구조와 Valid Bit

그림 5.26: Page Table을 이용한 주소 변환

 

• 입력: Virtual Address.

• 출력: Physical Address.

• 구성:

• Virtual Page Number (VPN): Page Table에서 인덱싱.

• Valid Bit: 페이지가 메모리에 있는지 확인.

• Physical Page Number (PPN): 페이지가 메모리에 있으면 물리 주소 반환.

 

그림 5.27: Page Table과 Swap Space

 

• Valid Bit가 0이면 페이지가 디스크에 저장됨.

• Page Table은 가상 페이지를 디스크 또는 메모리와 연결.

 

 

 

 

4. Swap Space

 

Swap Space는 가상 메모리를 저장하는 보조 저장소(디스크) 영역이다.

• OS는 Swap Space에 있는 데이터를 필요에 따라 메모리로 가져오고, 메모리에서 교체된 데이터를 다시 Swap Space로 저장.

 

페이지 교체 알고리즘: LRU

 

• LRU (Least Recently Used):

가장 오랫동안 사용되지 않은 페이지를 교체.

• LRU는 정확한 구현이 비싸기 때문에, 대략적인 방식(예: Reference Bit)을 사용.

 

 

 

 

5. RISC-V의 다단계 Page Table

그림 5.28: RISC-V의 2단계 Page Table

 

• 가상 주소의 구조:

• VA[31:22]: Level 0 Page Table 인덱스.

• VA[21:12]: Level 1 Page Table 인덱스.

• VA[11:0]: Page Offset.

• 단계적 변환 과정:

1. Supervisor Page Table Base Register(SPTBR)이 Level 0 Page Table 시작 주소를 제공.

2. Level 0 Table에서 Level 1 Table의 시작 주소 검색.

3. Level 1 Table에서 Physical Page Number(PPN)를 반환.

4. PPN과 Page Offset을 결합하여 최종 물리 주소 생성.

 

 

 

 

6. Reference Bit

 

• Reference Bit (Access Bit):

페이지가 최근에 사용되었는지 추적하는 비트.

• 페이지가 액세스되면 Reference Bit이 설정.

• OS는 주기적으로 Reference Bit을 초기화해 LRU 페이지를 예측.

• 사용 목적:

정확한 LRU 구현 비용을 줄이고 효율적인 페이지 교체를 지원.

 

---

Virtual Memory for Large Virtual Addresses

 

 

1. Large Virtual Address Space와 Page Table 크기 문제

 

• 32-bit 가상 주소와 4KB 페이지를 사용하는 경우:

• 각 페이지 테이블 엔트리 크기 = 4 바이트.

• 페이지 테이블 크기 = 2^20 * 4bytes = 4MiB.

 

• 문제:

• 프로세스가 많아질수록 메모리 사용량이 증가.

• 64-bit 주소 공간에서는 페이지 테이블 크기가 기하급수적으로 커지며, 수 테라바이트가 필요.

 

 

2. Page Table 크기를 줄이는 5가지 기술

 

1. Limit Register 사용 (페이지 테이블 제한):

 

• 개념:

페이지 테이블 크기를 제한하여, 프로세스가 사용하는 가상 주소 공간만큼만 페이지 테이블 생성.

• 장점:

• 페이지 테이블이 필요 이상으로 커지지 않음.

• 단점:

• 주소 공간 확장이 한 방향으로만 가능.

 

2. Segmentation 기반 두 개의 Page Table 사용:

 

• 개념:

주소 공간을 두 개의 세그먼트로 나눔:

1. 스택: 상위 주소에서 아래로 확장.

2. 힙: 하위 주소에서 위로 확장.

• 장점:

• 메모리 사용 효율 증가.

• 각 세그먼트 크기에 따라 독립적으로 확장 가능.

• 단점:

• 희소 주소 공간(Sparse Address Space)에는 부적합.

 

3. Inverted Page Table (역방향 페이지 테이블):

 

• 개념:

물리 페이지 수만큼만 엔트리를 갖는 페이지 테이블을 생성.

• 각 엔트리는 물리 페이지에 매핑된 가상 페이지를 기록.

• 장점:

• 페이지 테이블 크기 감소.

• 단점:

• 해시 함수를 사용한 검색 과정이 추가되어 검색 속도 저하 발생.

 

4. Paging된 Page Table:

 

• 개념:

페이지 테이블 자체를 가상 메모리에 저장하고, 필요할 때만 메모리에 로드.

• 문제점:

• 페이지 테이블에 대한 페이지 폴트가 발생할 수 있음(중첩된 폴트).

• 해결책:

• 일부 페이지 테이블은 물리 메모리에 항상 유지.

 

5. Multi-level Page Table (다단계 페이지 테이블):

 

• 개념:

페이지 테이블을 여러 단계로 나눔.

• Level 0 Table → Level 1 Table → 실제 페이지.

 

• 그림 5.28 설명:

• RISC-V는 두 단계 페이지 테이블을 사용.

• 상위 비트는 Level 0 Table에서 사용되고, 하위 비트는 Level 1 Table에서 사용.

• 장점:

• 희소 주소 공간(Sparse Address Space)에 적합.

• 메모리 효율성 증가.

• 단점:

• 주소 변환 과정이 복잡해지고 지연 시간 증가.

 

3. Writes와 Dirty Bit

 

Write-Back 방식 사용:

 

• 이유:

• 디스크 쓰기는 매우 느림.

• 변경된 페이지만 디스크에 기록하도록 최적화.

• Dirty Bit:

• 페이지가 수정되었는지 여부를 추적.

• Dirty 페이지는 디스크에 기록된 후 다른 데이터로 교체.

 

4. TLB (Translation Lookaside Buffer):

 

• 페이지 테이블 액세스를 캐싱하는 고속 버퍼.

• 역할:

• 가상 페이지 번호를 물리 페이지 번호로 빠르게 매핑.

• 페이지 테이블 액세스 필요성을 줄임.

 

TLB 작동 원리 (그림 5.29):

 

1. 히트:

• 가상 주소가 TLB에 있으면 물리 주소 반환.

2. 미스:

• Page Table에서 매핑 검색 후, TLB에 로드.

 

TLB의 장점:

 

• 주소 변환 속도 향상.

• Temporal Locality와 Spatial Locality를 활용.

 

5. TLB의 특성

 

1. 크기:

• 일반적으로 16~512개 엔트리.

2. 히트 시간:

• 0.5~1 클록 사이클.

3. 미스 패널티:

• 10~100 클록 사이클.

4. 미스율:

• 0.01%~1%.

 

TLB의 대체 알고리즘:

 

• LRU (Least Recently Used):

• 정확한 구현 비용이 높음.

• 일부 시스템은 무작위 교체(Random Replacement) 방식을 사용.

 

---

The Intrinsity FastMATH TLB

 

 

1. TLB와 Cache의 역할 (FastMATH TLB와 Cache 동작)

 

TLB는 가상 주소를 물리 주소로 빠르게 변환하기 위해 사용되며, 캐시는 물리 주소로 접근된 데이터를 저장하여 데이터 액세스 속도를 높인다.

FastMATH TLB:

• 페이지 크기: 4KiB

• 가상 주소: 32bit (가상 페이지 번호는 20bit).

• TLB 크기: 16entries, 완전 연결형 (Fully Associative).

• 각 TLB 엔트리:

• 20-bit 가상 페이지 번호(Tag).

• 20-bit 물리 페이지 번호.

• Valid Bit, Dirty Bit, 기타 상태 정보 포함.

 

 

2. 동작 원리

그림 5.30: 주소 변환과 캐시 액세스 과정

 

1. TLB 검색:

• 가상 페이지 번호(VPN)를 TLB의 모든 엔트리와 비교.

• TLB Hit: TLB에서 물리 페이지 번호(PPN)를 가져옴.

• TLB Miss: Page Table에서 주소를 검색해야 함(추가 지연 발생).

 

2. 물리 주소 생성:

• 물리 페이지 번호(PPN)와 가상 주소의 Page Offset을 결합해 완전한 물리 주소 생성.

 

3. 캐시 액세스:

• 생성된 물리 주소로 캐시에 데이터 요청.

• Cache Hit: 데이터 반환.

• Cache Miss: 메모리에서 데이터 로드 후 캐시에 저장.

 

Write 처리:

 

• Write 요청 시:

1. Write Access Bit가 설정되어 있는지 확인.

2. Dirty Bit를 설정해 페이지가 수정되었음을 기록.

 

3. 읽기/쓰기 요청 처리 흐름

그림 5.31: 요청 처리 플로우차트

 

1. TLB Access:

• TLB Hit이면 물리 주소 반환.

• TLB Miss이면 Page Table에서 변환 후 TLB 갱신.

2. 읽기/쓰기 분기:

• 읽기: 캐시 Hit 시 데이터 반환, Miss 시 메모리 로드.

• 쓰기: Write Access Bit를 확인. 설정되지 않았다면 Write Protection Exception 발생.

 

 

 

4. 메모리 계층과의 통합

 

가상 메모리, TLB, 캐시 통합 (Integration):

 

1. 가상 주소 변환:

TLB를 통해 가상 주소를 물리 주소로 변환.

2. 캐시와 계층 유지:

데이터가 캐시에 없으면 메모리로부터 가져옴.

메모리에 없는 경우, Page Fault 처리.

3. 운영 체제 역할:

• 페이지 교체 시 TLB와 페이지 테이블 동기화.

• 필요시 데이터 내용을 Swap Space로 저장.

 

 

 

5. TLB, Page Table, Cache 상호작용

 

그림 5.32: 미스 시나리오

 

1. TLB Hit, Page Table Miss, Cache Miss:

• TLB에 유효한 주소가 있지만, 데이터가 메모리에 없을 때 발생.

• Page Fault 처리 후 데이터 읽기.

2. TLB Miss, Page Table Hit, Cache Miss:

• Page Table에서 물리 주소를 가져오지만, 데이터가 캐시에 없음.

• 메모리에서 데이터 읽기 후 캐시에 저장.

3. TLB Miss, Page Table Miss:

• 가상 페이지가 메모리에 없을 때 발생(Page Fault).

4. 불가능한 시나리오:

• TLB Miss와 Page Table Miss가 함께 발생하며 Cache Hit는 불가능(데이터가 메모리에 없는 경우 캐시에 있을 수 없음).

 

 

 

6. Virtually Addressed vs. Physically Addressed Cache

 

Virtually Addressed Cache:

 

• 캐시가 가상 주소를 사용해 데이터 저장 및 검색.

• 장점:

• 주소 변환 필요 없으므로 속도 향상.

• 단점:

• Aliasing 문제: 같은 물리 페이지를 다른 가상 주소가 참조하면 데이터 불일치 발생 가능.

 

Physically Addressed Cache:

 

• 캐시가 물리 주소를 사용.

• 장점:

• Aliasing 문제 해결.

• 단점:

• 가상 → 물리 주소 변환이 추가되어 지연 발생.

---

Implementig Protection with Virtual Memory

 

 

1. Virtual Memory의 보호 메커니즘

 

가상 메모리는 다중 프로세스가 동일한 물리 메모리를 공유하는 환경에서 데이터를 안전하게 보호하는 데 필수적이다.

• 목적:

1. 한 프로세스가 다른 프로세스의 메모리 데이터를 읽거나 수정하지 못하도록 보호.

2. 운영 체제가 페이지 테이블을 안전하게 관리하도록 보장.

 

Write Access Bit:

 

• 메모리 페이지가 읽기 전용인지, 쓰기 가능한지를 제어.

• 잘못된 쓰기 작업(예: 보호된 페이지에 쓰기)이 발생하면 Write Protection Exception 발생.

 

2. 하드웨어 요구사항

 

운영 체제가 보호 메커니즘을 구현하려면 다음과 같은 하드웨어 기능이 필요하다:

1. 권한 모드(Supervisor/User Mode):

• 프로세스가 사용자(User) 프로세스인지 **운영 체제(Supervisor)**인지 구분.

• Supervisor Mode에서는 사용자 모드에서 접근할 수 없는 리소스(Page Table Pointer 등)를 수정 가능.

2. 프로세서 상태 저장:

• 프로세서가 User/Supervisor Mode에서 실행 중임을 나타내는 상태를 저장.

• TLB와 Page Table Pointer도 보호.

3. 모드 전환 메커니즘:

• System Call (예: RISC-V의 ecall): 사용자 모드에서 Supervisor Mode로 전환.

• Supervisor Exception Program Counter (SEPC):

• 예외 발생 시 명령어 주소 저장.

• 예외 처리 후 sret으로 사용자 모드 복귀.

 

 

 

3. 프로세스 간 메모리 보호

 

독립적인 주소 공간 유지:

 

• 각 프로세스는 고유의 가상 주소 공간을 가진다.

• 운영 체제의 역할:

1. Page Table 보호:

• 프로세스가 자신의 페이지 테이블을 수정하지 못하도록 보호.

2. 공유 데이터 제어:

• 공유 데이터는 운영 체제가 명시적으로 제어.

• Write Access Bit를 사용하여 읽기 전용 페이지를 생성.

 

4. Context Switching

 

Context Switch (문맥 전환):

운영 체제가 P1에서 P2로 프로세스를 전환할 때 발생.

• 문제점:

• TLB는 P1의 페이지 정보를 유지하므로, P2 실행 시 혼란 발생 가능.

• 해결책:

• Address Space ID (ASID):

• 프로세스를 식별하는 8-bit 태그.

• ASID를 사용하면 P1과 P2의 TLB 엔트리를 명확히 구분 가능.

• TLB 초기화:

• Context Switch 시 TLB를 플러시하여 충돌 방지.

 

5. TLB Miss와 Page Fault 처리

 

TLB Miss:

 

• TLB에 가상 주소 매핑이 없는 경우:

1. Page Table에서 물리 주소 검색.

2. TLB에 해당 매핑 추가.

 

Page Fault:

 

• 가상 주소에 해당하는 페이지가 메모리에 없는 경우:

1. Page Table에서 디스크 주소 확인.

2. 디스크에서 페이지를 메모리로 로드.

3. 메모리가 부족하면 LRU 등을 사용해 교체할 페이지 선택.

 

6. Page Fault 처리 과정

 

1. 예외 처리:

• 프로세서 제어를 운영 체제로 넘김.

2. 페이지 검색:

• Page Table에서 디스크 주소 확인.

3. 페이지 교체:

• Dirty Bit가 설정된 페이지는 디스크에 기록 후 교체.

4. 메모리로 데이터 로드:

• 새로운 페이지를 디스크에서 읽어 메모리에 저장.

5. 프로세스 복원:

• SEPC에 저장된 명령어 주소로 복귀.

 

7. Thrashing과 성능 문제

 

Thrashing:

 

• 프로그램이 과도한 페이지 교체로 성능이 크게 저하되는 현상.

• 해결책:

• 워킹 셋(Working Set)을 줄이는 알고리즘 설계.

• 메모리 크기 확장.

 

TLB Miss 문제:

 

• TLB는 제한된 엔트리를 가지므로, 큰 데이터 집합에서는 Miss 증가.

• RISC-V의 해결책:

• 큰 페이지 크기:

• RISC-V는 1GiB 및 2MiB페이지를 지원.

• TLB Miss 감소.