[OS] pagenation

paging

외부 단편화가 생기는 근본적인 이유는 각기 다른 크기의 process가 memory에 연속적으로 할당되었기 때문이다.

만일 process와 memory를 일정한 단위로 자르고 이를 memory에 불연속적으로 할당할 수 있다면 외부 단편화는 존재하지 않는다.
이러한 과정을 paging이라고 하며 pagenation은 process의 논리 주소 공간을 page라는 단위로 자르고, memory 물리 주소 공간을 frame이라는 page와 같은 크기의 단위로 자른 뒤 page를 frame에 할당하는 가상 memory 관리 기법이다.

paging에서 swapping을 진행하는 경우 paging에서 swap out하는 경우를 page out, paging에서 swap in하는 경우를 page in이라고 한다.

page table

process가 memory에 불연속적으로 배치되어 있는 경우 CPU는 이를 순차적으로 실행할 수 없다.
process를 이루는 page가 어느 frame에 적재되어 있는지 CPU가 모두 확인할 수는 없으므로 물리 주소에서는 불연속적으로 배치되더라도 논리 주소에서는 연속적으로 배치되도록 하는 page table을 이용하여 다음에 실행할 명령어 위치를 찾을 수 있도록 한다.

page table은 page 번호와 frame 번호를 짝지어 놓고 CPU로 하여금 page 번호만을 보고 frame을 찾을 수 있도록 한다.

pagenation은 내부 단편화라는 문제를 야기할 수 있는데, 모든 process가 page 크기에 맞게 잘리는 것은 아니며 이러한 경우 하나의 page 크기보다 작은 크기로 발생한다.
page 크기를 너무 작게 설정하면 그만큼 page table의 크기가 커져 공간의 낭비가 발생하기 때문에 적절한 page 크기를 설정해 활용할 수 있어야 한다.
linux 등의 경우에는 기본 page 크기보다 더 큰 page도 일부 허용해 memory에 유지하기도 한다.

process는 각자의 process table을 가지고 있고 각 process의 page table은 memory에 적재되어 있다.(process의 page table 정보는 PCB에 기록되며 context change 시 다른 register와 마찬가지로 변경된다.)
CPU 내의 PTBR(Page Table Base Register)는 각 process의 page table이 적재된 주소를 가리킨다.

이러한 page table을 memory에 두면 문제가 하나 생기는데, CPU가 memory에 2번씩 접근해야 하기 때문이다.

이 문제를 해결하기 위해서 CPU 곁에 (MMU 내부에) TLB(Translation Lookaside Buffer)라는 page table의 cache memory를 두고 TLB에 논리 주소의 page 번호를 찾는다.

TLB에 논리 주소의 page 번호가 있는 경우 TLB hit라고 하고 이 경우 page가 적재된 frame을 알기 위해 memory에 접근하지 않도록 한다.
그렇기에 memory 접근 횟수를 1회로 줄이는게 가능하지만 만일 page 번호가 TLB에 없는 경우 어쩔 수 없이 page가 전재된 frame을 알기 위해 memory 내의 page table에 접근하도록 하는데 이를 TLB miss라고 한다.

paging에서의 주소 변환

하나의 page 혹은 frame은 여러 주소를 포괄하기 때문에 특정 주소에 접근하려면 아래 2가지 정보가 필요하다.

• 어떤 page 혹은 frame에 접근하고 싶은가
• 접근하려는 주소가 그 page 혹은 frame으로부터 얼마나 떨어져있는가

위 사항 때문에 pagenation에서는 모든 논리 주소가 기본적으로 page number와 offset으로 구성되어 있다.
offset은 접근하려는 주소가 frame의 시작 번지로부터 얼마나 떨어져 있는지를 알기 위한 정보이다.
즉, 논리주소 <page number, offset>은 page table을 통해 <frame number, offset>으로 변환된다.

page table의 구성

page table은 page number, frame number 외에도 아래 내용들도 포함된다.

• valid bit
  현재 해당 페이지에 접근 가능한지 여부를 알려준다.
  frame number 다음으로 중요한 정보이며, pagingㅇ서 swapping을 사용할 수 있도록 현재 page가 memory에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 bit이다.
  즉, page가 memory에 적재되어 있는 경우 1, 아니면 0인 것이다.
  만약 유효 bit가 0인 경우에 이 page에 접근하려고 하는 경우 page fault라는 exception이 발생한다.
  
  CPU가 page fault를 처리하는 과정은 hardware interrupt를 처리하려는 과정과 아주 유사하다.

  1. 기존 작업내역 백업
  2. page fault 처리 routine 실행
  3. page fault 처리 routine은 원하는 page를 memory로 가져온 뒤 유효 bit를 1로 변경
  4. page fault 처리 후 CPU는 해당 page에 접근

• protection bit
  page 보호 기능을 위해 존재하는 bit이다.
  protection bit를 통해 해당 page가 read and write인지, read only인지 나타낼 수 있다.
  bit가 1인 경우 read and write이고 0이면 read only이다.
  예를들면 process를 이루는 code 영역은 read only인 경우가 많은데 이러한 read only page에 write를 시도하면 OS가 이를 막아준다.
  더 복잡한 형태의 구현도 가능한데, read, write, execute의 RWX 조합으로 읽기, 쓰기, 실행의 권한 조합을 나타낼 수도 있다.

• reference bit
  CPU가 이 page에 접근한 적이 있는지 여부를 나타낸다.
  적재 이후 CPU가 읽거나 쓴 page는 1로 세팅되고 읽거나 쓴 적이 없는 page는 0으로 유지된다.

• modified bit
  해당 page에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다.
  dirty bit라고도 부르는데, 보조기억장치에 쓰기 작업을 해야할지 판단하기 위해 존재한다.
  만약 CPU가 한번도 접근하지 않았거나 읽기만 한 page의 경우 보조기억장치에 저장된 해당 page의 내용과 memory에 저장된 page 내용은 서로 같은 값을 가지고 있다.
  이렇게 한 번도 수정된 적이 없는 page가 swap out 되는 경우 아무런 추가 작업 없이 새로 적재된 page에 덮어 쓰기만 하면 되는데, 그렇지 않은 경우 보조기억장치에 저장된 page의 내용과 memory에 저장된 page의 내용은 서로 다른 값을 가진다.
  이러한 경우 page가 swap out 되는 경우 변경된 값을 보조기억장치에 기록해야하고 그것을 판단하기 위해 존재한다고 할 수 있다.

unix 기반 OS에서는 fork 시스템을 호출하면 parent의 복사본이 child로 만들어지고 process 간 memory 영역 등을 공유하지 않도록 완전히 고유한 page table을 갖게 된다.
이러한 process의 복사 작업은 process 생성 시간도 늦추고 불필요한 memory 낭비도 하게 되는데, copy on write를 한다면 parent와 동일한 child가 생성되는 경우 동일한 frame을 가리키도록 page table을 생성한다.
만일 parent에서 swap이 일어나지 않고 read만 이어나간다면 이 상태가 지속된다.

하지만 parent나 child 어느쪽이라도 page에 write를 한다면 그 순간 해당 page가 별도의 공간으로 복제되는데, 각 process가 자신의 고유한 page가 할당된 frame을 가리키게 되고 이를 write on copy라고 한다.

이를 통해 process의 생성 시간도 줄이고 memory 공간도 절약 가능하다.