4 minute read

Paging

Segmentation을 사용하게 되면 크기가 다른 logical segment 단위로 메모리를 할당해야 하기 때문에 free space을 manage하는게 어려워진다. 이로 인해 external fragmentation도 생긴다.

이런 문제를 해결하기 위해서 Paging 이라는 아이디어가 나왔다. Logical segment을 기준으로 나누는 것이 아니라 page라는 고정된 크기 단위로 virtual address space와 physical memory을 나눠서 관리하는 것이다.

joowan1108

예를 들어 address space가 64 byte일 때 이를 16 byte page 4개로 나눴다고 해보자. 그럼 각 page을 physical memory에 저장하는 것이다.

joowan1108

Page가 physical memory에 저장된 상태는 page frame이라는 용어를 사용한다.

Paging의 장점은 2 가지이다.

1) Flexibility

Logical segment을 기준으로 나눌 때는 heap과 stack이 어떻게 커지는지에 대한 것을 기억해야 했지만 paging에서는 그런 생각을 하지 않아도 된다는 장점이 있다.

2) Simplicity of Free space management

크기가 동일한 page을 기준으로 작동하기 때문에 external fragmentation이 발생하지 않고 physical memory에 저장할 때도 아무것도 고려하지 않고 그냥 빈 page slot에 넣으면 된다.

이때, paging을 하기 위해서는 virtual address의 page가 physical page의 몇 번째 page frame과 대응되는 것인지를 기록하는 page table이 필요하다. Page table은 각 virtual page의 address translation을 저장하고 있다고 보면 된다.

Page table은 process마다 존재하는 데이터 구조이고 다른 process을 실행하고자 하였다면 OS는 그 process을 위한 page table을 사용해야 한다.

Page table에서 address translation은 어떻게 되는 것인지 살펴보자. Virtual address을 page frame으로 translate하기 위해서는 virtual address으로부터 두 정보를 얻어야 한다. 이 정보는 virtual page number (VPN)과 offset within the page이다. Virtual page number는 virtual address space 내에서 몇 번째 page에 이 virtual address가 해당되는지를 의미하고 offset은 그 page 내에서 몇 번째 주소에 해당되는지를 의미한다.

예를 들어 virtual address space is 64 byte (크기가 64 byte)라고 하자. 그러면 virtual address는 이 크기를 다 표현하기 위해서 6 bit으로 되어있어야 한다. 그럼 virtual address을 다음처럼 해석할 수 있다.

joowan1108

Page의 크기가 16 bytes라고 하면, virtual address space는 64 / 16 = 4 page로 이루어져 있을 것이므로 모든 page 수를 표현하기 위해서 VPN은 2 bit으로 되어있어야 하고 page 안의 주소를 표현하기 위해서는 offset은 ($2^4$) 4 bit으로 되어 있어야 한다.

joowan1108

Process에서 movl 21, %eax 명령어를 실행했다고 해보자. 그럼 21 = $010101_2$ 이므로 VPN = 01, offset = 0101인 것을 알 수 있다.

VPN 정보를 통해 physical memory의 몇 번째 page frame에 속하는지 알아내는 것이기 때문에 page table으로부터 translation 결과를 얻어야 한다. 반대로 offset은 page이든 page frame이든 상관없이 page 크기 안에서 몇 번째 주소에 해당되는지를 의미하기에 별도의 translation 과정을 거치지 않아도 된다.

joowan1108

Translation을 거치게 되면 address는 PFN (page frame number) + offset으로 구성되게 된다.

Translation 결과, PFN이 $111_2$ 이 되므로 Page frame number는 7이 되므로 이 의미는 physical memory의 7 번째 page frame의 5번째 주소에 process가 접근하고 싶다는 것을 알 수 있다.

Page table은 어디에 저장될까

하지만 page table은 segment나 base and bounds와 비교하였을 때 더 많은 정보를 physical memory에 저장해야 한다.

교재에서 address space가 N bit라고 할 때도 있고 address space가 M byte라고 할 때도 있다. 이때 bit가 주어질 때는 virtual address가 32 bit으로 되어있다는 뜻이고 byte가 주어질 때는 address space의 크기가 M byte이라는 뜻이므로 이때는 virtual address가 $\log_2 (M)$ 로 되어있다고 해석하면 된다.

Address space가 32 bit라고 했을 때, address space의 크기는 $2^{32}$ 이다. Page의 크기가 4KB ($2^{12}$)라고 할 때, page 수는 $2^{20}$ 개이므로 VPN은 20 bit, offset은 12 bit로 이루어진다. 그러면 이때 process마다 행이 $2^{20}$ 개인 page table이 필요하다. Page table entry가 4 byte라고 한다면, page table은 $2^{20} * 4 = 2^{22}$ byte이다. MB = $2^{20}$ 이므로 4MB인 것이다.

총 100개의 process만 실행한다고 해도 400MB의 메모리가 필요한 셈이다. 즉, paging을 사용하면 너무 많은 메모리가 요구된다.

Page Table을 구성하는 정보

Page table에 존재하는 한 translation 정보를 Page Table Entry (PTE)라고 한다.

Page table은 Virutal address에 대응하는 physical address을 저장하는 데이터 구조이기 때문에 아무 형태로 될 수 있다. Linear table을 사용한다고 해보자. 그러면 VPN이 index으로 쓰여서 이에 대응하는 PTE을 찾을 수 있는 것이다.

PTE 안에는 Page frame만 들어있는 것이 아니다.

joowan1108

1) Valid bit

해당 PTE 안에 있는 translation이 valid 한지 표시해주는 정보이다. 사용되지 않는 page와 heap과 stack 사이의 free space에 해당되는 page는 invalid 하다고 표시되며 이 영역에 접근하려고 하면 trap가 발생한다.

2) Protection bit

Page가 읽히고, 바뀌고, 실행될 수 있는지를 표현한다. Protected된 page에 접근하려고 할 때도 trap가 발생한다.

3) Present bit

Page가 physical memory에 있는지, disk에 저장되어 있는지를 알려준다.

4) Dirty bit

Dirty bit은 memory에서 가져온 뒤에 내용이 변했는지를 알려준다.

5) Reference bit

Page가 전에 access 되었는지를 알려준다.

Paging : 느리다

Paging은 메모리를 많이 요구한다는 단점과 함께 느리다는 단점이 있다. 느린 이유는 address translation 과정에 있다.

Paging의 원리를 단계별로 이해해보자.

  • Virtual address 21이 주어졌을 때, 21을 바탕으로 VPN와 offset을 뽑아낸다

  • Memory에 존재하는 page table에 들어가서 대응되는 PFN을 얻는다.

    $\rightarrow$ 메모리 접근 한 번

  • PFN에 해당하는 memory 안에 들어가서 offset만큼 떨어진 정보를 얻는다.

    $\rightarrow$ 메모리 접근 두 번

즉, paging을 사용하면 한 번의 memory access instruction은 최소 두 번의 memory access가 필요한 것이다.

Paging의 과정은 다음 코드로 이해할 수 있다.

// 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)

이 속도 심각성을 loop code을 통해 알아보자.

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

이 코드가 assembly로 변환되면 다음과 같다.

1024 movl $0x0,(%edi,%eax,4)
1028 incl %eax
1032 cmpl $0x03e8,%eax
1036 jne 0x1024

명령어를 가져오는 과정에서 4*2번의 memory 접근 + movl에서 2번의 memory 접근 –> 한 loop에 10번의 memory 접근이 발생한다. 이를 1000번 한다면 10000번의 memory 접근이 발생하는 것이다.

You May Also Enjoy