운영체제 | 가상메모리 | 페이징과 주소번역 더 알아보기

큰 그림 요약

가상 메모리는 다음 페이지들의 집합으로 표현될 수 있다:

• 메인메모리에 로드된 cached page (익명 페이지와 file-backed page들)
  • cached page는 메인메모리에 복제(load)되어 캐싱된 페이지를 뜻한다. cached 메모리의 경우 해당 프로세스(스레드) 페이지 테이블 중에서, 해당 페이지에 해당하는 PTE의 valid bit (다른 말로 present bit)가 1로 설정된다. 해당 프로세스(스레드) 페이지 테이블의 위치는 PTBR 에 저장된다. 
• 메인메모리에 로드되지 않은 데이터 
  • cached page 였다가 스왑 아웃된 uncached page: cached page 였다가 스왑 아웃된 uncached 페이지 중 익명 페이지들은 스왑 영역 안에 존재하게 된다. file-backed 페이지는 원래 파일 위치로 돌아간다. (eviction(퇴출) = 내보내는 것)
  • 아직 한번도 로드된 적 없는 데이터: 1) 새롭게 할당되었지만 아직 쓰인 적 없는 익명 페이지, 2) 한번도 로드된 적 없는 file-backed page 후보(바이너리 형태의 파일 데이터). 아직 캐싱된 적 없는 file-backed page들은 스왑 영역 외의 디스크 상의 파일로 존재한다. 이러한 페이지들은 필요할 때 메모리로 로드된다. 
• 가상메모리에 존재하지만, 아직 할당되지 않은 빈 공간인 unallocated page
  • unallocated page는 가상 메모리의 일부이지만 메인 메모리와 디스크 어디에도 실제 존재하지는 않는 빈 공간이다. 가상 메모리 자체는 48bit 주소체계 기준으로 256TB 수준으로 매우 크기 때문에.. 실제 사용하는 일부 공간을 제외하고는 다 unallocated page 인 상태로 남아있다고 보면 된다. 

 

익명 페이지는 동적 메모리 할당이나 스택 공간 할당 시 생성되며, 초기에는 디스크에 존재한 적 없는, 메인 메모리에만 존재한다. 이 페이지들은 파일과 연결되지 않고, 런타임에 프로그램에 의해 생성된다. 익명 페이지는 일반적으로 file-backed 페이지로 변환되지 않는다. 메모리 부족 시, 익명 페이지는 스왑 영역으로 이동될 수 있으나 여전히 익명 페이지로 남는다. 파일과 연결되어 디스크에 저장되기 위해서는 파일 시스템의 파일에 명시적으로 매핑되어야 한다.

 

 

주소 번역이 되는 과정은 다음과 같다:

 

1. CPU가 논리주소로 접근한다.
2. 논리주소는 CPU 칩 내의 하드웨어인 MMU에 도달한다.
3. MMU는 논리주소를 VPN 과 오프셋으로 나눈다. 이때, shift 연산과 and 연산이 사용된다.
4. TLB(Translation Lookaside Buffer)에서 해당 PTE가 있는지를 확인한다.
   • TLB는 빠른 주소 변환을 위해 최근 사용된 페이지 주소 변환 정보를 캐시한다. TLB에서 먼저 VPN에 해당하는 항목을 검색한다. TLB hit가 발생하면 주소 변환은 빠르게 완료되며, TLB miss가 발생하면 다음 단계로 진행된다.
5. (TLB miss 일 경우) PTBR을 통해 해당 스레드의 페이지 테이블을 찾고, 페이지 테이블에 접근한다. VPN을 인덱스로 사용하여 해당 PTE를 찾는다.
6. 해당 PTE에서 valid bit를 확인하여 메인 메모리에 적재된 페이지인가를 확인한다.
7. valid bit가 1로 설정된 경우
   1. PFN을 추출한 뒤, 논리 주소의 오프셋과 결합하여 (여기서는 shift 연산과 or 연산이 사용된다.) 물리 주소를 찾는다.
   2. MMU는 이 주소를 CPU에 전달하며, CPU는 해당 주소 기반으로 캐시/메인 메모리에 데이터를 요청한다.
   3. 캐시/메인 메모리는 이 주소에 있는 데이터를 CPU에 반환한다.
8. valid bit가 0인 경우 (Page fault인 경우)
   1. 인터럽트 발생 및 커널 모드 전환
      1. Page fault는 인터럽트로 처리되며, 시스템은 커널 모드로 전환된다.
      2. 운영 체제는 페이지 폴트 핸들러를 호출한다.
   2. 페이지 폴트 원인 분석
      1. Page fault 핸들러는 fault가 발생한 주소와 원인을 분석한다. 
      2. 원인은 페이지가 아직 메모리에 로드되지 않았거나, 권한 위반, 유효하지 않은 주소 등 다양할 수 있기 때문. 
   3. 스왑 인 또는 페이지 할당
      1. 페이지가 아직 로드되지 않았다면, 운영체제는 해당 페이지를 디스크의 스왑 공간 또는 파일 시스템에서 찾아 메모리로 로드한다.
      2. 새로운 페이지가 필요한 경우(ex. 익명 페이지), 운영체제는 새 페이지를 할당하고 초기화한다.
      3. 페이지를 메인 메모리에 로드하는 것은 '종종' DMA로 이루어진다. 
   4. 페이지 테이블 업데이트
      1. 로드된 페이지에 대한 페이지 테이블을 업데이트한다. (PFN 과 valid bit)
   5. 프로세스 재개
      1. 페이지 폴트를 처리한 후, 시스템은 프로세스를 재개한다.
      2. 이제 프로세스는 중단되었던 메모리 접근을 성공적으로 수행할 수 있다.
   6. 에러 처리
      1. 만약 Page fault가 해결 불가능한 경우(ex. 유효하지 않은 메모리 접근 - segmentation fault), 운영체제는 오류를 처리한다. (프로세스 종료 또는 예외 처리 등)

 

---

CSAPP, OSTEP 정리

 

가상 메모리의 모든 페이지는 disk 안에 존재한다. swap in은 특정 uncached 페이지를 메인 메모리로 이동시키는 게 아니라, 정확히 말하면 uncached 페이지를 메인 메모리에 복제, 즉 캐싱하여 cached 페이지로 만드는 작업이다.

 

PTE는 메인 메모리 내부에 존재한다. PTE는 크게 두 가지 역할을 한다.

1) 해당 가상페이지가 메인메모리에 캐싱되어 있는지를 저장한다. (Valid bit)

• valid bit가 설정되어 있다면, 즉 1이라면 해당 페이지는 메인메모리에 캐시되어 있는 상태이다. 주소번역을 거쳐 메인메모리에 접근한다. 
• valid bit가 0이라면, 해당 페이지는 캐시되어 있지 않은 상태이다. 이는 OS의 Page fault 인터럽트 핸들러를 발생시키고, 이에 따라 다음과 같은 절차를 수행하게 된다.
  • Disk에서 해당 페이지 찾기
  • Disk에서 메인 메모리로 로드하기. 이때 메인 메모리의 가용 공간이 가득 찼다면, 어떠한 페이지를 swap out하고 해당 페이지를 swap in 할 것인가에 대한 정책이 필요하다. 이를 페이지 교체 정책(Page replacement policy)라고 한다. 

2) 해당 가상페이지의 물리주소를 저장한다.

• 만일 valid bit가 1이었다면, 해당 페이지는 cached page이다. 이때 페이지 테이블의 해당 인덱스는 물리페이지 번호(PPN)를 저장하고 있다.
• 만일 valid bit가 0이었다면, 해당 페이지는 디스크에 있으나 할당되지 않은 Uncached page 이거나, 아직 할당조차되지 않은 Unallocated page이다. 
  • Uncached page라면 Disk에서의 해당 페이지 시작부분을 가리키게 된다.
  • Unallocated page라면 NULL 값을 가지고 있다. 

 

여기서 추가적으로 알아야할 개념은 Demand paging과 Thrashing이다. 

• Demand paging: 프로그램 시작 시 꼭 필요한 최소한의 페이지만 메모리에 로드하는 정책이다. 이를 통해 초기 메모리 사용량을 줄이고, 시작 시간을 단축시킬 수 있다. 
  • 이는 메모리 절약과 캐싱 비용의 trade off 관계를 고려한 정책이다. Demand paging 정책에서는 페이지 폴트 핸들러를 통해 캐싱해오는 작업이 더 많이 필요할텐데, 그로 인한 cost가 메모리를 절약했을 때 얻는 이점 대비 낮다고 판단되기 때문에 도입되었을 것이다. 
• Thrashing: 너무 많은 스왑이 발생하여 전체 시스템 성능에 악영향을 미치는 상태이다. 프로그램을 정상적으로 설계했는데 성능이 비정상적으로 둔화된다면 쓰래싱을 의심해볼만 할 것이다. 

 

주소 번역

CPU 코어는 논리주소를 기반으로 작업을 수행한다. 

해당 논리주소는 '가상주소 = VPN + VPO' 로 1차 번역되며, 이 중 VPN을 통해 PTE에 대한 적절한 인덱스를 찾아간다. 

PTE에서 물리페이지 번호를 찾아서 최종적으로 물리 주소를 얻게된다. 

 

근데 여기서 PTE 주소(즉, 인덱스)는 어떻게 찾는거지? 라는 의문이 든다.

페이지 테이블의 시작 주소(PA)는 Page Table Base Register(PTBR)에 저장되어 있고, 어느 인덱스로 찾아갈지는 다음과 같이 결정된다. 

 

원하는 PTE 주소를 알기 위해 MMU는 다음과 같은 연산을 수행한다. (여기서 VPN과 오프셋을 구하는 방법은 위 필기와 다르다. 아래는 OSTEP 교과서의 내용 !! -> 주소 공간을 보통 2의 지수로 맞추는데 그렇게하면 곱하기와 나누기를 쉬프트 연산으로 처리할 수 있기 때문이다. 그런 경우에는 아래와 같은 방법을 통해 VPN과 오프셋을 구할 수 있다.)

• VPN = (가상주소 & VPN_MASK) >> SHIFT (= 오프셋 비트 수. 예를 들어 4)
  • and 연산 (비트마스킹) 사용하여 필요한 부분을 잘라낸다. (자르고 싶은 범위를 1, 나머지 범위를 0으로 채운 값과 비트마스킹)
• PTE 주소 = PTBR + (VPN * sizeof(PTE))

위 예제에서 VPN_MASK는 0x30 (= 이진수 110000)으로 설정되고, 이는 전체 가상 주소에서 VPN 비트만 골라내는 역할을 한다. 

 

이제 해당 PTE 주소로 접근하여 PPN을 얻는다. 그 다음엔 다음과 같은 과정으로 물리주소를 얻게 된다.

• offset(VPO) = 가상주소 & OFFSET_MASK
• 물리주소(PA) = (PPN << SHIFT) | offset
  • or 연산 사용하여 offset 값을 오른쪽에 붙인다. (쉬프트(<<)연산을 통해 생긴 000 ... 에 offset과의 or 연산을 수행하면 offset에서 1인 비트가 그대로 이식된다.)

결과적으로, '물리주소 = PPN + 오프셋'으로 번역된다. 

CPU 논리주소 -> 가상주소 -> PTE -> 물리주소 순의 과정을 거치는 것이다. 

 

 

(아래는 OSTEP의 예시)

 

이런 명령어가 있다면, 21 을 이진변환하여 010101 로 만든다. 

그리고 앞의 2비트는 가상페이지 번호, 뒤의 4비트는 오프셋이 된다. 

VPN은 주소번역 과정을 거쳐 PPN(또는 PFN = 물리 프레임 번호)으로 번역되고, 여기에 오프셋을 붙여 물리주소(PA)로 번역된다. 

21이라는 논리주소는 010101이라는 가상주소가 되고, 이는 최종적으로 1110101이라는 물리주소가 된다. 

 

 

주소 번역 과정2

페이지 적중시, 페이지 폴트시의 가상주소 번역 과정은 다음과 같다.  (우선은 TLB 없는 버전)

 

 

 

 

PTE를 구하는 과정은 위에서 살펴본 바 있다. 

 

근데 매번 메모리에 접근해서 PTE를 가져오는 것은 너무 비효율적이다. 따라서 CPU 칩 내부 하드웨어인 MMU 안에 TLB(번역 참조 버퍼, Translation Lookaside Buffer)라는 버퍼를 추가하게 되었다. 메모리의 PTE 중 일부를 또다시 캐싱하는 것이다. 

 

만일 TLB에 캐싱된 PTE에서 해당 페이지를 찾고, 이를 물리주소로 번역할 수 있다면, 전반적인 주소번역 속도는 크게 향상될 것이다. 

TLB에서 주소를 검색하는 메커니즘은 다음과 같은 수도코드로 표현할 수 있다. 

 

페이지 크기가 클수록 TLB 히트 비율이 높아져서, 전반적인 성능이 향상되는 경향이 있다.