xv6 study - Memory Management

Goal

xv6를 포함한 일반적인 메모리 관리 기법을 공부한다.

Virtual Memory

일반 프로그램이 물리적인 메모리를 직접하용하게 되면 권한, 사용여부,보안 등 고려해야할 사항이 많아진다. 따라서 운영체제는 프로그램이 물리적인 메모리를 직접적으로 엑세스하는 것을 막고, 가상 메모리를 제공한다. 일반 프로그램은 OS가 제공한 가상메모리를 사용하여, 자유롭게 메모리를 엑세스하는 것같은 경험을 제공한다.

그래서 아래와 같은 목표를 가진다.

1. Transparency
   • 프로그램은 메모리가 공유되는 걸 신경 안써도 OK
   • 개발을 위한 추상화 제공
2. Efficiency
   • memory fragmentation 방지
   • HW support로 효율적인 구현
3. Protection
   • 한 프로그램이 다른 프로그램의 메모리를 엑세스하는 것을 방지
   • Isolation (다른 프로그램에 영향을 주지 않도록)
   • Sharing (공유 메모리 또한 제공)

Paging

▪ Allows the physical address space of a process to be noncontiguous • Divide virtual memory into blocks of same size (pages) • Divide physical memory into fixed-size blocks (frames) • Page (or frame) size is power of 2 (typically 512B – 8KB) ▪ Eases memory management • OS keeps track of all free frames • To run a program of size n pages, need to find n free frames and load the program • Set up a page table to translate virtual to physical addresses • No _____ fragmentation

Paging은 물리적인 메모리 공간은 비연속적으로 사용함으로써 메모리 관리를 효율적으로 하는 기법이다.

Page Table

Page Table을

문제는 선형적으로 가상주소를 mapping할 경우 빈 공간이 굉장히 만다는 점이다. 빈 공간에 대해서도 불필요하게 주소를 관리할 경우 그만큼 pagetable이 커지게 된다. 따라서 아래의 논의는 실제 사용되는 가상 주소 공간에 대해서만 pagetable을 관리하고자 하는 목표에서 시작한다.

Note: Pagetable의 주소는 물리 주소로 관리되어야 한다. 가상 메모리를 만드는 과정이기에 CPU가 pagetable을 참조할 때 물리 주소로 접근하기 때문이다.

Segment Paging

처음에 나온 아이디어 중 하나는 segmentation을 paging에 황용하는 것이다. 실제로 사용되는 메모리 영역만 Sement로 나누어서 관리한 후 각 Segment에는 Page Table 주소들을 저장하는 것이다.

가상 주소를

Pros and Cons

Pros	Cons
Page Table이 작아짐	Page Table이 여전히 커질 가능성이 있음
연속적으로 Segment를 할당할 수 있음	Page Table로 인한 fragmentation이 발생할 수 있음1
일부 page가 swap 되었을 때도 여전히 사용할 수 있음
page를 share 할때 전체/일부 모두 가능해지며 유연

Multi-level Paging

이미 컴퓨터 구조에서도 다룬 내용이기에 빠르게 다룬다.

위 그림은 각각 linear paging과 multi-level paging의 구조를 보여준다. linear paging에서는 PFN202, PFN203처럼 mapping인 안되어 있는 경우 # todo Multi-level paging에서는 page table이 여러 레벨로 나뉘어져 있어서, 필요한 부분만 할당하여 사용할 수 있다. 만약 가리키고 있는 페이지 테이블에 사용중인 페이지가 없다면, 해당 페이지를 가리키는 링크를 끊음으로써 불필요한 페이지 테이블 할당을 방지할 수 있다.

Segment paging과는 다르게 고정된 크기로 페이지 테이블이 할당되므로, fragmentation이 발생할 가능성이 줄어든다.

Intel 64

xv6

39 bits VA -> 56 bits PA

Pros and Cons

Pros	Cons
압축적이고 빈 공간 감소	TLB miss가 발생할 때마다 느려짐
PA 관리 수월	복잡도 증가
HW 친화적
external fragmentation 방지

Inverted Page Table

PA를 기준으로 페이지 테이블을 관리하는 방식이다. 각 페이지 프레임마다 어떤 가상 주소가 매핑되어 있는지를 관리하는 방식으로

PFN → <VPN, PID>

형태의 매핑을 관리한다.

물리 메모리가 주어질 때 빠르게 VPN, PID를 알아낼 수 있으나, 일반적인 address translation은 inverted page를 순회해야하므로 느려질 수 있다. 그러나, reverse mapping 자체는 용도는 다르지만 쓰이는 기법이다.

Paging Page Table

메모리가 없어서 Page Table 또한 가상 주소로 관리하는 것이다.

• 메모리 접근시 page table을 접근하기 위한 addr translation이 필요
• Outertable 를 두어 관리
• Nested page fault 발생 가능

TLB

1. Page Table이 여전히 가변적이고 연속적으로 할당이 필요한데, 이것은 추가적인 fragmentation과 관리의 어려움을 야기할 수 있다. ↩︎