Paging

Segmentation 복습

 

Dynamic relocation 방법은 base + bounds register 를 통해서 virtual address를 physical address로

변환해준다. (MMU를 통해서)

 

Process address 공간이 물리적으로 메모리에 할당될 때 contiguous 하게 할당되어야 한다.

 

근데 중간 중간에 Free() 가 일어나서 결국 Fragmentation 이 생겨서 contiguous 하게 할당할 수 없는

문제가 생기는데 이를 해결하기 위해 Segmentation 이 나타났다.

 

code, heap, stack 영역이 각각 contiguous 하지만 서로 independent 하고 이를 table 로 만들 수 있다.

 

MMU에서 base, bound register 가 존재한다면 마찬가지로 segmentation 기법으로

만들어진 table이 통째로 MMU 에 들어간다고 볼 수 있겠다.

 

overhead가 커지겠지만 flexible 하게 메모리를 쪼갤 수 있어서 메모리 효율은 높아지겠다.

 

메모리 효율이 높아지면 process의 갯수가 늘어나고 늘어나면 전체 처리율이 높아져서 좋겠군.

 

각각의 프로세스가 관리해야하는 PCB(Process Control Block) 가 커졌지만 즉, context overhead 가

높아지겠지만 메모리 효율이 좋아진다.

 

하지만 여전히 문제점은 segment 가 contiguous 하다는점 (Code, heap, stack 각각...)

 

그래서 나타난게 Paging 기법이다.

 

 

Concept of Paging

 

 

Paging splits up address space into fixed unit called a page.

- Segmentation : variable size of logical segments(code, stack, heap 등)

 

With paging, physical memory is also split into some number of pages called a page frame.

 

Page table per process is needed to translate the virtual address to physical address.

 

 

process address space 가 있고 physical address space 가 있다. (physical 은 실제 DRAM)

 

물리적으로 동일하게 자르는데 process 쪽에서는 page , physical 쪽에서는 frame 라고 한다.

 

process A, B 가 있다고 할 때(paging 된 경우), 어떠한 page가 물리적으로 어딘가에 mapping 이 되는데동일하게 어딘가에 mapping 이 될 수도 있다.

 

page table은 frame 어딘가를 가르킬 때 virtual page를 real 한 page 로 주소로 변경하기 위한 변환기가필요한데 이게 바로 page table 이라고 한다.

 

즉, translator 가 논리적인 주소를 물리적인 주소로 변환하는 것으로 이를 page table 이라고 한다.

 

 

Advantages of Paging

 

 

 

Flexibility : Supporting the abstraction of address space effectively

   - Don't need assumption how heap and stack grow and are used.

 

Simplicity : ease of free-space management

   - The page in address space and the page frame are the same size.

   - Easy to allocate and keep a free list

 

 

Ex ) 128-byte physical memory with 16 bytes page frames and

       64-byte address space with 16 bytes pages

 

physical address 128 byte를 16 byte로 나누면 8 즉, 8 개의 page frame이 존재한다.

그리고 64 byte를 16 byte로 나누면 4 즉, 4 개의 page 가 존재한다.

 

 

여기서 VPN은 virtual page number, PFN는 page frame number 을 의미한다.

 

physical memory에서 page frame 0 은 reserve 된 영역이므로 사용할 수 없다.

 

위와같이 page Table 을 세팅함으로써 공간적인 sharing을 한다면 다른 process에서도 table이 

존재할 것이므로 각각의 process에 대한 table 이 존재한다는 것이다.

 

그래서 서로의 영역을 직접적으로 접근할 수 없어서 Protection 을 할 수 있다.

 

 

 

Address Translation

 

 

 

Two components in the virtual address

   - VPN : virtual page number

   - Offset : offset within the page

 

Example ) virtual address 21 in 64-byte address space

 

 

21 => 010101 으로 2진법 6 bit 에 대한 표현이 가능하며 4 bit는 offset, 2 bit는 VPN 이다.

 

그러나  Physical address 로 변환하기 위해서 offset은 그대로 유지되지만 VPN 에서 PFN 으로

변환하는 과정에서 Address translation 이 필요하다.

 

다음과 같은 사진처럼 virtual address를 physical address로 변환하는 과정을 이해하도록 하자.

 

 

 

Where are page tables stored?

 

 

 

Page tables can get awfully large.

   - 32 bit address space with 4 KB pages, 20 bits for VPN

        => page offset for 4 KB page : 20 bit

        => 4MB = 2^20 entries * 4 Byte per page table entry

 

만약 1000개 프로세스가 돌아간다고 하면 4MB * 1000 으로 대략 4 GB 가 된다.

 

보통 8 GB 인데 프로세스를 띄우는데 page table 에만 4 GB 라고 가정을 해보면,

page table 을 쓰는게 flexible 하면서 좋지만 크기가 너무 큰 문제점이 있다.

 

즉, MMU에 올리면 overhead가 상당할 것이고 page table이 process 마다 갖고 있는데 

많아지면 위와 같은 문제가 발생한다.

 

Page tables for each process are stored in memory.

 

 

 

What is in the Page Table?

 

 

The page table is a data structure that is used to map the virtual address to physical address.

   - Simplest form : a linear page table, an array

 

The OS indexes the array by VPN, and looks up the page-table entry.

 

 

 

Common Flags of Page Table Entry

 

 

 

(1) Valid Bit => Indicating whether the particular translation is valid.

     단순하게 PFN(Page Frame Number)이 유효하다는 것을 알려주는 것으로 알아두기

     즉, translator 가 VPN을 translate 해주는데 frame number 가 유효하지 않을 경우 쓰지 않는다.

 

(2) Protection Bit => Indicating whether the page could be read from, written to, or executed from

     page가 읽어도 되는지 써도 되는지 실행해도 되는지 등등...? (read, write, execute, ... 와 같은 bit 구성)

 

(3) Present Bit => Indicating whether this page is in physical memory or on disk(swapped out)

     예를 들어 어떤 virtual page 가 physical memory 에 올라갈때 다른 virtual page 가 안 올라갈 경우

     이를 swap space 라고 하는데 이때의 present bit 값을 0 이라고 설정한다.

 

     다른 예로 process의 address space 에서 6 page를 쓴다고 할 때 page frame 이 page 4개만

     할당할 수 있다고 한다면 6 page를 전부 올리지 못하고 4 page 만 올리기가 가능하다.

     따라서 나머지 2 page는 여전히 Disk 에 존재한다.

 

     여기서 4 page는 page frame 에 올라갔으므로 1로 설정하고 나머지 2 page는 0으로 설정한다.

     즉, 0 으로 설정된 것은 Disk 에 존재한다는 것을 간접적으로 알려주는군?

 

     Swapping => Disk 에 존재하는 page를 page frame 에 올리고 page frame 에 존재하는 page

     를 Disk 에 내리는 과정을 의미한다.

 

(4) Dirty Bit => Indicating whether the page has been modified since it was brought into memory.

     누군가(page)를 빼려고 할 때 수정되어 있어서 다르다는 것을 알리기 위해 dirty bit 이 필요하다.

 

(5) Reference Bit(Accessed Bit) => Indicating that a page has been accessed.

     Page 마다 몇번 접근했는지를 알아야 한다.

     reference 한 횟수가 작은 page를 page frame 에 올려주고, 

     reference 한 횟수가 높은 page는 Disk 에 고정시킨다.

 

 

 

Page table entry 에서 실제 frame number를 쓰는 곳은 20 bit를 사용하며

나머지 중에서 맨 끝에 present bit 가 존재하는 것도 알 수 있고 

파란색으로 색칠된 부분은 사용하지 않는 부분임을 알 수 있다.

 

 

Paging : Too Slow

 

 

To find a location of the desired PTE, the starting location of the page table is needed.

 

For every memory reference, paging requires the OS to perform one extra memory reference.

 

 

page table size가 너무 커서 MMU 에 전부 올리지 못하며instruction fetch를 할 때마다 memory 접근을 하는데 매번 reference 가 일어남으로써 이로 인한 overhead 가 발생하므로 Segmentation 에 비해서는 느릴수 밖에 없다. 

 

 

 

Accessing Memory with 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);
}

 

 

A Virtual(And Physical) Memory Trace

 

 

 

 

 

예를 들어서 크기가 1000인 int 형 배열을 선언하여 전부 0으로 초기화 하는 C 코드가 있다고 하자.

 

이를 컴파일하여 얻은 목적 파일을 실행할 때 어셈블리 코드를 주목해보도록 하자.

 

0x1024 movl $0x0, (%edi, %eax, 4)  // [edi + eax * 4] = 0

 

초기에 eax = 0 을 iteration 을 통해서 계속 증가함으로써 0을 할당해 갈 것이다.

 

이때 0x03e8 < eax 인지를 계속해서 비교함으로써 0을 할당할 것이다. (0x03e8 는 1000)

 

그리고 오른쪽 사진을 보면 Code, Array, Page Table 에 대한 정보가 있다.

 

Code 를 살펴보도록 하자

 

실제로 mov, inc, cmp, jne 에 대한 operation 이 1000번 실행됨으로써 다음과 같이 Virtual address가 변경한다. (왼쪽 어셈블리 코드의 address를 참고하면서 보기)

 

Virtual Address

=> 0x1024(mov) => 0x1028(inc) => 0x102c(cmp) => 0x1030(jne)

=> 0x1024(mov) => 0x1028(inc) => 0x102c(cmp) => 0x1030(jne)

=> 0x1024(mov) => 0x1028(inc) => 0x102c(cmp) => 0x1030(jne)

=> ...   (이러한 과정이 1000번 수행)

 

Array 를 살펴보도록 하자

 

array는 메모리를 reference 할 때 index = 0, 1, 2, 3, ..., 999 이런식으로 1000번을 reference 한다.

이때 int 형 이므로 4 bit 씩 increment 함으로써 Virtual address가 변경한다.

 

Virtual Address

=> 0x40000(index = 0) => 0x40004(index = 1) => 0x40008(index = 2) 

=> 0x4000c(index = 3) => 0x40010(index = 4) => 0x40014(index = 5)

=> ...  

 

마지막으로 Page table 를 살펴보도록 하자

 

page table은 Virtual address 1024 일때와 40000(index = 0) 에 대해서 physical address로

계속 해서 변경해줘야 한다.

 

Code 에서 instruction 4번, Array 에서 access 1번으로 한번의 cycle로 총 5번을 접근한다.

 

즉, 5번의 page table access 가 일어난다는 말이고 이를 통해 1000번을 loop 한다면 총 5000번의

page table access 가 일어난다.

 

5000번의 access...? memory reference overhead 가 상당할 것이라는것이 짐작이 간다.