[운영체제] 12. Intro to Paging

Overview

• 메모리 공간 관리를 잘 하려면 2가지 접근법이 있다.
  • 의미 있는 덩어리 단위로 나눠서 적재하자 = Segmentation
    • 단편화 문제가 점점 심각해진다.
  • 의미에 관심 없고 예를 들면 4kb 씩 fixed-sized unit으로 잘라서 적재하자 = Paging
    • 프로그램을 자른 것을 page라고 부름
• physical memory도 page와 똑같은 사이즈(page frame)로 자른다.

아래 사진을 보자

왼쪽에 virtual memory(=address space) 가 있는데 프로그램을 똑같은 크기로 자른다.(보통은 4kB임)

중요한건 physical memory

똑같이 physical memory도 똑같은 단위로 미리 잘라두고 그 각각을 page frame이라 부름.

💡 **frame** : physical memory를 address spaced의 fixed-sized unit만큼 자른 것

자른 것들은 아무데나 올리면? 주소 변환이 쉽지 않다.

그래서 각각의 page가 어느 frame에 적재되어있는지 기록 해둬야함. = page table

💡 **page table** : 프로그램을 자른 page가 어느 frame에 있는지 기록해둔 것. 

Paging

• 프로세스들을 noncontiguous하게 (연속적이지 않게) 메모리 공간에 올려도 되는 기법이다.
• 어디에 들어가든 상관 없고 page table에 저장해서 기억하기만 하면 된다.
• virtual memory(=address space)를 조각낸게 page
• physical memory를 조각낸게 frames
• 각각의 크기는 power of 2. (주로 512B - 8KB)
• 메모리 관리가 쉬워진다 → 어떤 frame들이 비어있는지 os가 체크해서 관리 해줘야한다.
  • n개의 page 프로그램을 올리고 싶으면 free frames n개 찾아내면 됨. → 복잡한 알고리즘 필요 없음.
  • 다만 주소 변환을 위한 page table이 필요하다.
  • 외부 단편화는 없다. 다만 내부 단편화는 있음.

A Simple Paging Example

• page frames 크기가 16bytes라고 하면 page 크기도 16bytes이다.
• 프로그램 크기는 64-bytes이다.
• physical memory 크기는 128 bytes이다.
  
  

문제는 과연 주소 변환이 잘 될까? 이다.

주소 변환이라는 것은 cpu가 요청하는 virtual address를 physical address로 바꿔주는 것.

Address Translation

• offset : page 내에서의 주소
• VPN : page number
  

ex) address 21 = 01 0101

01 = page number, 0101 = offset

어떤 page가 어떤 frame에 있는지만 잘 체크하면 된다.

→ 위 예제에서는 1번 페이지가 7번 프레임에 있는 것

또다른 예제는 32bit 프로세스가 있다고 가정해본다.

• page size = 4KB라 하면
• 두 부분으로 나눔.
  

• page offset은 주소 변환해도 바뀌지 않는 값.
• page number는 page table의 index에 해당하는 값
  

f가 frame number, p가 page number.

• page table의 크기는?

여기서 page table entries 수는 $2^{20}$ 될 것이다.

Paging: Spatial Overhead

• 32-bit address space를 가지고 4-KB page들을 만든다.
• page table이 존재하는 위치는 main memory에 있어야 함. DRAM말이다. → DRAM 크기와 상관있음.
  
• 그래서 공간적인 overhead가 꽤 크다.

Page Table in Kernel Physical Memory

page 하나 쓸 때마다 page table에 계속 접근해서 기록해줘야함.

page table도 main memory 어딘가에 자리를 차지하고 있어야 함.

page table은 4MB 크기까지도 될 수도 있음.

What Is In The Page Table?

• 실제로는 좀 더 복잡하다.
• page table은 자료구조이긴 한데 virtual address → physical address로 mapping 해주는 자료구조임.
• 이 외에도 뭔가 더 필요하다.

Common Flags of Page Table Entry

Table Entry에는 frame number 말고도 몇가지 더 있다.

• Valid Bit : 이 Page 에 접근해도 되는 건가?
• Protection Bit : 실행 권한(read, written, executed)
• Present Bit : 메모리에 있어? 아님 아직 안올라오고 disk에 있나?
• Dirty Bit : 메모리 적재 후 업데이트 된 적 있어?
• Reference Bit : 한번 더 접근한적이 있어?

Example: x86 Page Table Entry

• 위 하나는 page table의 entry임. 4bytes.
• 반드시 필요한 건 frame number PFN

Paging: Temporal Overhead

• 메모리에 올라가는 것이므로 공간적인 오버헤드가 발생할 수 있다.
• 시간적인 오버헤드도 발생 가능.
  • 페이지 테이블 내에서도 해당 page table entry 찾기 위해 시작 위치부터 찾아야함.
• 두번씩 접근해야 한다. → TLB로 해결할 수 있다.

Accessing Memory With Paging

Demand Paging

• memory, image를 page frame, page 단위로 나눔.
• 프로그램 시작하려고 하면 전부 나눠서 전부 올리는게 아니다. 꼭 필요할 때마다 하나씩 적재한다.
• 일단은 disk에 놔둔다.
• 프로그램 시작하면 첫번째 페이지만 적재한다.
• 필요하면 on-demand로 그때그때 올린다.

Paging: Pros & Cons

Pros

• 외부 단편화 문제는 없다.
• allocate, free가 쉽다. 찾아서 해주기만 하면 된다.
• 필요할때만 들고온다 = 필요 없으면 쫓아내기도 한다.(=page out)
• 멀티프로그래밍의 degree를 높일 수 있다. = 많은 프로그램을 적재할 수 있다.
• 페이지 단위로 share가 쉽다.
  

• 다 똑같은 frame을 가리키고 있으면 share를 쉽게 할 수 있다.

Cons

• frame 단위로 하기 때문에 공간을 다 못쓰는 내부 단편화 발생할 수 있다.
• temporal overhead, spatial overhead 있다.