Introduction: Paging
space-management에는 크게 두 가지 방법이 있다.
먼저 가변 크기로 나눠서 관리하는 방법 중 segmentation이 대표적이다. segment는 서로 다른 크기의 chunk 때문에 fragmentation이 발생한다.
두 번째로 고정된 크기로 나눠서 관리하는 paging 기법이 있다. 고정된 크기의 단위인 page로 나눠서 관리하는 방법이다.
paging에서는 physical memory를 page frame이라고 불리는 fixed-size slot들의 배열로 본다. 각 page frame은 virtual memory page를 하나씩 가지고 있다.
- Overview
위 그림처럼 64bytes address space에 각 크기가 16bytes인 4개의 page가 있다고 생각해 보자.
다음 그림은 128-byte의 Physical memeory에 8개의 slot이 있는 그림이다.
각 슬롯은 모두 크기가 16바이트로 고정되어 있으며, used space에 OS를 위한 주소 공간이나 page를 할당해 주었다.
Advantages
- Flexibility
Paging을 사용하면 Heap이나 Stack이 자라는 방향이나, 프로세스가 address space를 사용하는 방법에 상관없이 address space의 abstraction을 잘 지원할 수 있다.
- Simplicity
free-space management가 쉬워진다.
Page table
Address Space의 각 page들이 physical memory의 어디에 저장되는지 기록하기 위해 프로세스마다 page table이라는 구조체를 가지고 있다.
page table의 main role은 address space의 virtual page를 physical memory로 address translations하는 것이다.
위 그림을 예로 들면, page 1 of AS는 page frame 7로 매핑되므로, Physical memory의 8번째 slot에 있다는 것을 알 수 있다.
중요한 점은 page table이 per-process data structure라는 점이다. 다른 프로세스의 virtual page를 잘못 매핑하면 다른 물리 메모리를 가리킬 것이다.
Address Translation
프로세스의 virtual address space 크기가 64 바이트라고 가정하자.
그러면 우리는 virtual address를 위해 6비트가 필요하다. ()
는 highest-order bit, 는 lowest-order bit이다.
페이지의 크기가 16바이트이므로, Virtual address를 위 그림처럼 나눌 수 있다.()
64바이트의 address space에 16바이트 크기의 페이지가 들어가므로 4개의 페이지를 관리해야 한다.
따라서 상위 2비트를 이용해야 한다.(00, 01, 10, 11)
이렇게 나눈 상위 2비트는 VPN(Virtual Page Number)이고, 나머지 4비트가 offset이다.
movl 21, %eax instruction을 수행한다고 하면, virtual address인 21(0b 010101)을 이용해 physical memory를 찾을 것이다.
Virtual address 21은 위 그림처럼 표현되고, virtual page 01의 5번째(0b 0101) 바이트라고 해석할 수 있다.
이 VPN을 이용해 address translation을 하면 그에 해당하는 PFN(physical frame number)을 찾을 것이다.
이렇게 virtual address의 VPN을 이용해 PFN(Page Frame Number)을 매핑해서 physical memory로 주소 변환을 할 수 있다. 이때 offset은 변하지 않는다.
위의 예시대로 찾은 Physical memory는 117(0b 111 0101)이고, [Figure 18.2]의 117은 page frame 7의 5번째 바이트이며 동시에 page 1의 5번째 바이트로 일치한다.
- Where Are Page Tables Stored?
page table은 앞서 다루었던 segment table이나 base bounds register보다 훨씬 클 것이다.
32비트 address space에 4KB 크기의 page를 다룬다고 가정하자.
그럼 32비트를 20비트의 VPN과 12비트의 offset으로 나눌 수 있다.
이므로, 4KB 페이지를 나타내기 위해 12bit offset이 필요하다.
나머지는 20비트이므로 PTE(Page Table Entry)가 개 생긴다.
page table이 너무 커서 MMU에 저장하는 것이 아니라, Memory의 각 process에 저장한다.
- What’s Actually In The Page Table?
page table은 virtual address를 physical address로 매핑해주는 data structure다.
array 형태이므로 linear page table이라고도 불린다.
OS는 VPN을 기준으로 indexing 해서 PTE를 찾아가고, 해당 PTE에서 PFN을 읽는다.
앞으로 Page table을 Simple linear structure라고 가정하자. PTE에는 PFN 외에도 valid bit, protection bit, present bit, reference bit 등의 정보를 포함 한다.
- Slow
movl 21, %eax instruction을 수행한다고 생각해보자.
먼저 fetch를 위해 virtual address 21을 physical address 117로 translate 해야 한다.
따라서 H/W는 실행 중인 프로세스의 page table 위치를 알아야 한다.
PTBR(page-table base register)이 page table의 시작 위치에 해당하는 physical address를 포함한다고 가정하자.
// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))
// Fetch the PTE
PTE = AccessMemory(PTEAddr)
// Check if process can access the page
if (PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else
// Access is OK: form physical address and fetch it
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)그러면 H/W는 위 코드로 VPN을 계산할 수 있다. (VA & 0b110000으로 VPN을 구한 뒤 shift 4)
PTBR에 VPN을 인덱싱 한 값을 더하면 PTE 주소를 구할 수 있다.
마지막 else 문에서 offset을 구한 뒤 physical address에 접근할 수 있다.
이러한 paging 구현은 너무 느리고 너무 많은 메모리를 필요로 한다.
- Memory Trace
아래 C 코드를 실행할 때의 memory access를 tracing 해보자.
int array[1000];
for (i = 0; i < 1000; i++)
array[i] = 0;위 코드를 disassemble 하면 다음과 같다.
0x1024 movl $0x0,(%edi,%eax,4)
# PT 접근(CODE 주소 찾기) → CODE 영역 접근(fetch) → PT 접근(array 주소 찾기) → STACK 영역 접근(execute)
0x1028 incl %eax
# PT 접근(CODE 주소 찾기) → CODE 영역 접근(fetch)
0x102c cmpl $0x03e8,%eax
# PT 접근(CODE 주소 찾기) → CODE 영역 접근(fetch)
0x1030 jne 0x1024
# PT 접근(CODE 주소 찾기) → CODE 영역 접근(fetch)$ebi에는 array의 base address가 있고, $eax은 index i의 값이다.
movl $0x0,(%edi,%eax,4)($edi = $edi + $eax * 4)에서 integer size라서 4를 곱했다.
virtual address space의 크기는 64KB이고, page size는 1KB라고 가정하자.
이는 단순한 C 코드 예제일 뿐이지만 더 복잡한 메모리 접근의 복잡성을 나타내기에 충분한 그래프다.
Uploaded by Notion2Tistory v1.1.0