08. 운영체제 - Memory Virtualization(3)

Paging

Segmentation의 문제점

앞선 게시글에서 다룬 Segmentation 방식으로 memory virtualization을 구현하는 것에는 문제점이 있다.

segment의 사이즈가 가변이기 때문에 fragmentation으로 인한 공간의 낭비가 발생할 수 있다.

이때 external fragmentation은 할당된 chunk 사이의 작은 free space 구멍들 때문에 나타나고, internal fragmentation은 프로세스가 할당된 청크의 모든 공간을 사용하지 않기 때문에 발생한다.

이렇게 되면 physical memory가 낭비되고 utilization이 작아진다. (가용한 공간이 있어도 사용하지 못하는 문제)

segment의 사이즈를 줄여 fine-grained segmentation을 하면 이러한 문제를 조금은 해결할 수 있지만 그렇게 되면 필요한 레지스터의 개수가 너무 많아지기 때문에 불가능하다.

Paging introduction

Segmentation은 프로세스의 address space를 가변사이즈의 logical한 segment로 쪼개는 것이다.

Paging에서는 Address space를 page라는 고정된 사이즈의 단위로 나누고, physical memory 또한 page frame이라는 페이지들로 나눈다.

그리고 프로세스마다 Page table을 관리하며 이를 이용해 virtual address를 physical address로 변환한다. 

간단하게 살펴보면 1번 프로세스의 Virtual Address 상의 3번 페이지는 physical address의 5번 페이지로 맵핑되는 식이다. 

Paging의 장점

• Flexibility : 어떻게 heap 과 stack이 자라고 사용되는지 등을 신경 쓸 필요 없이 address space에 대한 효과적인 추상화를 제공한다.
• Simplicity : free space 관리가 쉽다. 주소공간의 page와 physical memory의 페이지프레임은 같은 사이즈이기 때문에 coalesing과 같은 메커니즘이 필요하지 않고 free list를 관리하고 할당하기 쉽다.
• 또한 모든 공간을 동일한 규격의 페이지로 나눠놓고 사용하기 때문에 Fragmentation이 덜 발생하여 자원을 효율적으로 활용할 수 있다.

Address Translation

virtual address는 두가지 컴포넌트로 이루어져있다.

• VPN : Virtual Page Number
• Offset : page 내의 offset

예를 들어 address space가 64 byte이고 페이지 사이즈가 16bytes이면 총 4개의 페이지가 생긴다.

그러면 VPN은 2bits, Offset은 4bits로 이루어진 virtual address를 통해 주솟값을 나타낼 수 있다.

Virtual address를 Physical address로 변환하는 방식은 다음과 같다.

VPN 부분은 page table을 이용하여 Physical frame number (PFN) 으로 변환하고, offset은 그대로 사용한다.

Page table은 각 프로세스마다 메모리에 저장되어있다.

그리고 32bit address space에서 4KB 짜리 페이지를 사용한다고 하면, VPN을 위해 20bits가 필요하다. 

(4KB = 2^12 이므로 12bits가 offset으로 사용되고, 2^32 / 2^12 = 2^20 이므로 나머지 20bits가 VPN으로 사용됨)

따라서 총 페이지 entry의 개수가 2^20개이므로, page table entry 하나 당 4 byte라면 총 page table의 사이즈는 2^20 * 4 bytes = 4MB가 된다.

이 페이지 테이블의 사이즈는 상황에 따라 꽤 큰 값일 수도 있다. 왜냐면 프로세스의 규모에 상관없이 고정적으로 할당되어야하는 페이지 테이블의 크기가 4MB이기 때문이다.

Paging의 구현

• Page table : 프로세스마다 존재하며 physical page와 각 virtual page에 대한 권한(Valid, Read, Write..)을 담고있다.
  • Page table은 단지 VA를 PA로 맵핑하기 위한 자료구조일 뿐이며, 배열 등으로 구현할 수 있다.
  • OS는 VPN을 인덱스로하여 page table 에 접근하여 PFN을 얻는다.
• Virtual address mapping
  • VA(Virtual address)의 offset은 PA(Physical address)로 복사된다.
  • VPN부분은 page table를 통해 PFN으로 변환되어 PA로 복사된다. 
  • page table에 접근하기 전에 VPN이 page table 범위를 벗어나지 않는지 체크하고, 해당 Virtual page의 접근권한을 확인한다. 

하지만 Paging에는 문제점이 있다.

원하는 Page table entry를 찾기 위해서는 page table의 시작주소에 접근해야한다. 그러면 Paging기법을 사용하면 모든 메모리 참조마다 한번의 추가적인 메모리 참조를 수행해야한다. 따라서 메모리 접근이 느려진다.

// Virtual address로부터 VPN만을 추출한다.
VPN = (VirtualAddress & VPN_MASK) >> SHIFT 
// VPN을 인덱스로하여 접근해야하는 Page table entry(PTE) 주솟값을 얻는다.
PTEAddr = PTBR + (VPN * sizeof(PTE)) 
// PTE 주솟값에 접근하여 값을 가져온다.
PTE = AccessMemory(PTEAddr) 
// 프로세스의 PTE 접근권한을 확인한다.
if (PTE.Valid == False) 
	RaiseException(SEGMENTATION_FAULT) 
else if (CanAccess(PTE.ProtectBits) == False) 
	RaiseException(PROTECTION_FAULT) 
else
	// 접근이 허용되어있다면, physical address를 생성하고 접근하여 값을 가져온다.
    offset = VirtualAddress & OFFSET_MASK 
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset 
    Register = AccessMemory(PhysAddr)

Paging을 이용하였을 때 메모리 접근은 위 코드와 같이 이루어지며, 총 두번의 메모리 접근이 이루어진다.

 

예를 들어 다음과 같은 코드를 생각해보자.

int array[1000]; 
for (i = 0; i < 1000; i++) 
	array[i] = 0;

위 코드를 컴파일하고 실행하면 다음과 같은 어셈블리 코드가 생성된다.

0x1024 movl $0x0,(%edi,%eax,4)
0x1028 incl %eax
0x102c cmpl $0x03e8,%eax 
0x1030 jne 0x1024

%edi를 array, %eax를 i라고 생각하면,

0x1024 : array + 4*i 에 0을 넣고,

0x1028 : i를 1 증가시킨다.

0x102c : i와 1000 (0x03e8)을 비교하고

0x1030 : 다르다면 0x1024 번지로 점프한다. (for문을 도는 것)

위와 같은 어셈블리 코드를 수행하는데 실행되는 메모리 접근의 횟수를 trace해보면 위 그림과 같다.

맨 아래 Code 영역을 보면 instruction fetch를 위해 0x1024, 0x1028 과 같은 VA를 PA로 바꿔야한다. 따라서 위 네개의 instruction을 수행하는데 총 4번의 Address translation이 일어난다.

또한 Array 영역을 보면 array + 4 * i = 0 을 수행할 때 메모리에 접근한다. 

따라서 for loop 한번을 도는데 총 5번의 address translation이 일어난다. 그리고 loop 이므로 1000번동안 계속 같은 메모리 접근이 반복되고, 특히 코드 영역의 경우 인접한 instruction들이 같은 페이지에 존재하기 때문에 계속해서 같은 페이지에 접근하는 문제가 발생한다.

 

Translation Lookaside Buffer (TLB)

TLB는 위의 문제를 하드웨어적으로 해결할 수 있는 방법이다. 

접근되는 페이지에 locality가 있을 때, 자주 사용되는 page table entry의 일부를 가까운 버퍼에 담아두는 것이다.

TLB는 CPU의 MMU(Memory-Management Unit) 내에 들어있으며, 자주 사용되는 Virtual-to-physical address 변환을 담아두기 위한 하드웨어 캐시이다.

Virtual address가 주어지면 바로 page table에 접근하지 않고, 먼저 TLB에 접근하여 해당 virtual address에 대한 변환값이 있는지 확인한다.

그리고 TLB hit이 되면 바로 해당 주소로 접근하면 되고, TLB miss가 발생하는 경우에만 page table에 접근하여 변환을 수행한다.

 

TLB를 사용하였을 때의 기본적인 알고리즘을 나타내면 다음과 같다.

// Virtual address에서 VPN을 추출한다.
VPN = (VirtualAddress & VPN_MASK ) >> SHIFT 
// TLB를 lookup하여 해당 VPN에 대한 translation을 담고있는지 체크한다.
(Success , TlbEntry) = TLB_Lookup(VPN)
if(Success == True){ // TLB Hit
	// TLB entry에서 바로 PFN을 뽑아내서 메모리에 접근한다.
    if(CanAccess(TlbEntry.ProtectBit) == True ){
        offset = VirtualAddress & OFFSET_MASK 
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory( PhysAddr )
    }else RaiseException(PROTECTION_ERROR)
} else { //TLB Miss
	// Page table 에 접근하여 변환을 수행한다.
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr) 
    (…)
    // Page table에서 가져온 변환값을 TLB에 저장해둔다.
    TLB_Insert( VPN , PTE.PFN , PTE.ProtectBits)
    RetryInstruction()
}

Locality

• Temporal Locality : 최근에 접근된 instruction/data가 가까운 미래에 다시 접근될 확률이 높은 것
• Spatial Locality : 이전에 접근된 메모리의 인접한 주소에 곧 접근할 확률이 높은 것

TLB miss

CISC 에서는 하드웨어가 TLB miss를 핸들링한다. (Hardware-managed TLB) 

하드웨어가 page table의 시작위치를 알고, page table을 순회하여 적절한 PTE를 찾은 후 TLB를 업데이트하고 instruction을 다시실행한다.

RISC에서는 TLB miss가 소프트웨어에 의해 핸들링된다. (Software-managed TLB)

TLB miss가 발생하면 하드웨어가 exception을 발생시키고, OS 내부의 trap handler가 TLB miss를 핸들링한다. 

Context switching

프로세스마다 VPN은 겹치게 사용될 수 있으므로, 프로세스가 Context switching되면 모든 TLB table entry를 invalid하게 만들어야한다. 하지만 이렇게하면 context switching이 될때마다 초반에 TLB miss가 많이 일어나며 느려질 수 있다.

이를 해결하기 위한 방법으로 TLB 를 크게 잡고, TLB entry에 프로세스 id를 같이 적어두어 TLB를 여러 프로세스가 다같이 사용하게 하는 방법이 있다.