OS가 space-management문제를 해결할 때 일반적으로 2가지 방식을 활용한다.
- virtual memory에서 본 segmentation이라고 하는 방식으로 다양한 크기로 메모리를 나누는 것이다. 하지만 이 방법은 메모리를 2개의 chunk로 나눌 때 fragmentation이라는 문제를 일으킬 수 있다는 단점이있다.
- 메모리를 고정된크키로 나누는 것이다. virtual memory에서 우리는 이 방법을 paging이라고 부른다. 프로세스의 address space를 다양한 크기의 segment(code, stack, heap)로 나누지 않고, 고정된 크기의 page로 나눈다. 따라서 우리는 물리적 메모리를 고정된 크기의 page frame의 배열로 볼 수 있다.
Simple example and Overview
쉬운 이해를 위해 작은 크기의 메모리로 예들어보자 총 64byte의 크기이고, 각각 16byte크기인 4개의 page가 있다.
18.2의 그림처럼 실제 물리적 메모리는 총 8개의 page로 구성되어있고, virtual space들은 물리적 메모리의 서로 다른 주소에 위치해있다.
paging은 여러가지 장점들이 존재한다.
- flexibility
프로세스가 address space를 어떻게 사용하는지에 상관없이 추상화를 효과적으로 수행 할 수 있다. 우리는 heap, stack이 어떤 방향으로 크기가 커지는지 가정할 필요가 없다. - simplicity
free space의 관리를 쉽게 만들어준다. 만약 64KB의 address space를 물리적 메모리의 8개 page에 저장하려고 할 때 1개의 page가 16KB이므로 OS가 관리하는 free list에서 4개의 page만 가져오면 된다.
물리적 메모리의 어떤 주소에 virtual page의 주소가 위치해 있는지를 알기위해서 OS는 프로세스마다 page table이라는 것을 지니고 있어야 한다.
page table의 주 목적은 address space의 virtual page가 물리적 메모리에서 어떤 위치에 있는지를 나타내는 것을 위한 address translation을 저장하고 있는 것이다.
예를들어 18.2에서 볼 수 있듯이 virtual page 0은 physical page frame 3에 해당된다.
우선 프로세스가 생성되는 virtual address를 물리적 메모리의 주소로 변환하기 위해서 virtual page number, page의 offset 두개의 구성요소로 나누어야 한다.
viftual address space가 64KB이므로 (2^6 = 64) 즉 6개의 bit가 필요하다.
한 page의 크기가 16KB이므로 우리는 4개의 page를 가져야하고 이를 나타내기 위해서는 segment에서 활용되는 것처럼 explicit approach로 상위 2개의 비트를 활용하여 4개의 page를 표현할 수 있다.
예를들어 virtual address 21을 물리적 메모리로 translate해보자.
movl 21, %eax
21은 이진수로 위와 같으므로 virtual address 21은 virtual page 1(VPN: "01")의 5(Offset: "0101")번째 위치에 있음을 알 수 있다.
따라서 18.2의 그림에서 알 수 있듯이 virtual page1은 물리적 page 7에 있다는 것을 알 수 있다.
Where the Page Table stored?
page table은 segment table, base and bound register보다 훨씬 크다.
4KB의 page, 32bit의 address space가 일반적이다. 그렇다면 32bit의 address space에는 4kb page가 거의 몇개가 들어갈까?
우선 4kb는
이다.
따라서 약 100만개의 page가 존재한다. 따라서 상위 20개 bit가 VPN이 되고, 나머지 12개의 비트는 offset이다. 따라서 page table entry(PTE)하나에 약 physical translation, 기타 정보들을 보관하기 위해서 4kb의 메모리가 필요하다면, 100개의 프로세스가 동작하는 경우 PTE를 저장만하는데 무려 400MB가 필요하게된다. 요즘같은 64bit 환경에서는 더 크게될 것이다.
이렇게 Page table이 너무 크기때문에 실행중인 프로세스의 page table을 MMU on-chip 하드웨어에 저장하지 않는다. 그 대신 각 프로세스의 page table을 메모리에 저장한다.
What’s Actually In The Page Table?
page table이란 virtual address(virtual page number)를 physical address(physical page number)로 매칭시켜주는 자료구조이다.
가장 간단한 구조로는 linear page table이라고 불리는 배열이다. 배열처럼 OS가 VPN으로 배열을 인덱싱해서 PFN를 찾아낸다.
PTE에는 우리가 알아야 할 여러가지 bit들이 있다.
valid bit는 특정한 translation이 valid한지 아닌지를 나타내는 비트이다. 예를들어 프로그램이 동작하면 code, stack, heap영역을 사용하고 그 외에 사용되지 않는 address space에는 valid bit가 invalid인 상태를 나타낸다. 만약 invalid한 address로 접근한다면 OS로 trap되어 프로세스가 종료된다.
따라서 valid bit는 남아있는 address space를 invalid로 표현하여 물리적 프레임을 할당하지 않음으로써 메모리를 절약한다.
그리고 특정한 page를 읽고, 쓰고, 실행할 수 있는지 여부를 나타내는 protection bit도 중요하다. 그리고 present bit는 현재 page가 디스크에 있는지 메모리에 있는지를 나타낸다. dirty bit는 page를 메모리로 가져온 이후 수정되었는지 여부를 나타낸다. reference bit는 page에 대한 접근이 있었는지 없었는지 여부를 추적할 때 사용되고, 특정한 page가 자주 사용되기 때문에 메모리에 남겨두어야하는지 그렇지 아닌지를 알려준다.
Paging: Also Too Slow
데이터를 적절하게 page에 전달하기 위해서는 먼저 virtual address를 physical address로 translate 해야한다. 이를 위해서 하드웨어는 반드시 현재 실행중인 프로세스의 page table을 갖고 있어야한다.
일단 page table base register에 page table의 실제 시작 위치가 저장되어있다고 가정해보자.
PTE를 얻기위해서 위와같은 작업을 한다.
우리의 예제에서 전체 virtual address에서 VPN만을 가져오기 위한 VPN_MASK는 0x30(110000)이다. SHIFT는 offset의 bit값인 4로 설정한다. 만약 21(010101)이라는 virtual address인 경우 VPN은 01이므로 virtual page는 1에 해당되고 이를 인덱스로하여 PTE에서 page table base register를 얻어낼 수 있다.
이제 physical address를 알았으므로 하드웨어는 메모리로부터 적절한 데이터를 register eax에 보내는 것이 가능하다.
요약하자면 우리는 각각의 메모리 참조의 프로토콜에 대해서 알게되었다.
18.6을 통해 우리는 paging을 통해 메모리에 접근하는 방법을 알 수 있다. 이때 모든 메모리 참조에 대해 paging은 page table에서 translation을 가져오기 위해서 한번의 추가적인 메모리 참조가 필요하다는 것을 볼 수 있다. 추가적인 메모리 참조는 고비용이고, 이 경우 프로세스가 2배 이상 느려질 수도 있다.
따라서 하드웨어와 소프트웨어를 둘 다 신중하게 설계하지 않는다면 page table은 메모리도 많이 필요하고 시스템을 너무 느리게 만들것이다.
출처 : OSTEP
