Paging

저번에 Segmentation에 대해서 알아보았죠? 그런데 Segmentation에는 문제점이 많습니다.

 

• Externel fragmentation
• Free space management가 복잡하다는 점
• Compaction이 비싸다는 점
• 또 Code구간 Stack구간 Heap구간이 나뉘어져있는데 Free Space가 있어도 Heap이 자라날 공간이 없다면 더이상 allocation을 해줄수 없다는 점

 

그래서 새로운 방식인 Paging을 도입합니다.

 

Paging의 Concept는 다음과 같습니다.

 

• Virtual Address를 Code Heap Stack에 구분없이 fixed-size의 unit인 page로 나누고 이를 virtual page라고 부릅니다.
  • Segmentation은 Variable Size로 (code, heap, stack)으로 나눴습니다.
• Physical memory역시 같은 사이즈의 page로 나눕니다 이를 page frame이라고 부릅니다.
• Virtual address를 Physical address로 mapping해주는 page table이 필요합니다.

 

이 방식의 장점은

 

• Flexibility
  • address space를 효과적으로 abstract해줍니다. ( Heap 과 Stack이 Grow하는 것을 신경 쓸 필요가 없습니다. )
• Simplicity
  • Free space management를 해주기 쉽습니다.
  • Externel fragmentation이 존재하지 않습니다.

입니다.

 

그렇다면 Paging은 구체적으로 어떻게 구현될까요?

 

와 같이 VPN을 PFN으로 Mapping해주는 Page Table로 구현됩니다.

 

또 Page Table에는 여러가지 또 다른 Bit가 포함되어 다양한 기능을 제공합니다.

 

• Valid Bit
  • 이 Page에 Data가 저장되어있는지를 알려주는 Bit 입니다.
• Protection Bit
  • 이 Page의 데이터에 대한 권한을 알려주는 Bit 입니다.
  • MMU에 의해서 Protection됩니다.
• Present Bit
  • Swapping에서 사용되는 것으로 이 Page가 Physical memory에 올라가 있는지를 알려주는 Bit 입니다.
• Dirty Bit
  • 이 Page가 최근에 수정되어있는지를 알려주는 Bit 입니다.
• Reference Bit
  • 이 Page가 Access되었는지를 알려주는 Bit 입니다.

 

Page Table은 또 Page를 Share 할 수 있는 장점이 있는데, 이것은 fork()와 같은 함수에서 Page Table만을 복제하면서 일어납니다.

 

다만, 이 방법도 완벽한 것은 아니라 Page Table에도 문제점이 세가지 있습니다.

1. Internal fragmentation
   • Page Size가 크면 생기는 문제입니다.
     • 작은 Size의 Page size를 쓰면 되는 문제입니다.
     • 다만 위 방법의 경우 3번 문제점인 Huge Page Table로 연결될 수 있습니다.
2. Performance Degradation
   • Page Table에 Access하면서 생기는 문제입니다.
     • memory에 두번씩 Access해야 합니다 1) PTE에 접근 2) Physical Memory에 Physical Address를 사용하여 접근

       

     • TLB(Translation lookaside buffer)를 사용해서 문제를 회피할 수 있습니다.
3. Huge Page Table
   • Page Table이 매우 커질 수 있습니다.
   • Hybrid solution이나 Multi-level paging이 해결법이 될 수 있습니다.

 

Translation Lookaside Buffers (TLB) 란 대체 무엇일까요?

MMU의 일부로 CPU chip 내부에 있고(SRAM), 이것이 PTE중 자주 쓰이는것을 저장하게 됩니다.

 

만약 찾는 PTE가 TLB에 있을 경우 다음과 같이 동작합니다.

이렇게 보면 단 한번 Memory에 Access하기에 효율적입니다. 그러나 TLB안에 없을경우 다시 두번 Memory에 Access 해야 합니다.

 

다만 Miss가 Locality 덕분에 자주 일어나지 않아, Cache Hierarchy를 이룰 수 있습니다.

 

TLB에 대해 더 자세한 내용은 별도의 게시글에서 다루겠습니다.