[Operating System] Paging Mechanism

페이징 메카니즘

• 고정분할/ 가변분할 기법은 내부단편화, 외부 단편화로 문제점이 존재함.

• 페이징은 이런 단점 해결 위해 고안된 방식이다.

• 페이징 사용시 외부단편화는 발생하지 않으며 내부 단편화는 아주적은횟수 발생함

• paging이란 memory 가상화에서 가상 주소와 물리 주소를 mapping시킬 때에 page frame을 단위로 하는 방식이다

Paging이란 가상주소공간을 일정한 크기의 Page 로 나누는 것을 말한다.

가상 메모리 - 페이지(블록) 가상주소공간의 Page가 물리적 메모리의 어떤 Page Frame에 저장되는지를 Page Table 에 기록한다.

물리 메모리 - 프레임(블록) 물리적 메모리는 이런 Page들을 담기 위한 영역으로 나누는데 이를 Page Frame

페이지 테이블

• OS는 각 프로세스마다 하나의 페이지 테이블 유지
  • 페이지 테이블은 각 프로세스의 각 페이지들에 해당하는 프레임 위치 관리
  • 각 페이지마다 하나의 항을 갖고 테이블 항은 페이지 번호(인덱스)로 쉽게 접근

• 프로그램 안에서 각 논리주소는 페이지 번호와 페이지 내의 오프셋으로 구성

존재비트 P

• 해당 페이지가 메모리에 적재되어있는지의 여부

수정비트 M

• 해당 페이지가 메모리에 적재된후 그내용이 수정되었는지 여부

기타제어비트

• 페이지 수준에서 보호와 공유를 다루려면 , 그용도의 비트필요

Virtual Address

• 페이지 테이블 통해 사용되는 가상주소 물리주소 모두 number + offset의 구조를 갖는다.
  • page number를 통해 pagetable의 몇번째 row에 접근할지 파악하고 register에 저장된 pxage table의 포인터 값과 page number를 더해 해당 page table의 row에 접근한다.

• 이후 얻은 frame number를 통해 실제 물리 memory에 접근한다.
  • frame number는 결국 물리 memory에서의 시작 주소를 뜻하는 값이기 때문에 얼마나 data를 읽어들일지에 대한 정보는 알지 못한다. 이 때 사용하는 것이 offset이다. 가상 주소에서의 offset을 그대로 물리 주소에서 사용하게 된다.

가상주소에서 offset이 차지하는 bit수가 0 이라면 해당 os의 페이지프레임사이즈는 2^0이다.

가상주소에서 pagenmber가 사용하는 bit수가 p라면 해당 os 페이지 테이블의 최대크기는 2^p이다.

페이지 테이블이 순서에 맞는 물리적 메모리 위치를 찾아준다.

offset은 - pf의 크기

물리 메모리는 Page Frame(페이지 프레임), 논리 메모리는 Page(페이지) 단위로 나눌 수 있음.

과도한 크기의 page table 문제 해결

계층 구조 page table 사용 n단계 구조의 페이지 테이블 사용

• 이를 해결하기 위한 대표적인 방법이 계층 구조 page table이다. 주로 2단계 계층 구조, 3단계 계층 구조 등이 있다. 우선 page directory가 있어 각각의 항목이 page table을 가리키도록 한다. page directory가 가리키는 page table이 꽉 찼을 경우에만 page directory의 다음 항목에서 새로운 page table을 가리키도록 동적으로 운용하는 방식이다. 아래는 2단계 계층구조 페이지 테이블

역페이지 테이블 사용

• page number를 그대로 사용하지 않고 hash function을 이용해 얻은 hash value로 사용하게 된다. hash value는 hash table에서의 인덱스이다. hash table의 항목 수는 물리 memory의 page frame의 개수와 동일하다. 즉, hash table은 모든 process가 공용으로 사용하는 것이다. 같은 곳을 가리키면 다음꺼? 였던듯

TLB 사용

• translation look-aside buffer란 page table 항목들을 저장하기 위한 특수한 고속 cache 장치이다.

• 가장 최근에 참조된 n개의 page table entry항목들을 저장하게 된다.

• 만약 TLB에 여유 공간이 없을 경우 가장 오래된 항목을 제거해 공간을 확보한다. 한편, 만약 page table에서 P bit가 0이라면 Page Fault로, secondary memory(swap)에 접근해 해당 page frame을 memory로 load한다. 이후 다시 page table에서 물리 주소를 찾아나선다.

• 가상 주소가 주어지면 우선 TLB에서 해당 page number가 있는지 확인한다. page number가 TLB에 있을 경우 TLB Hit으로, 바로 frame number를 얻어 물리 주소를 구해낸다. 만약 TLB에 page number가 없을 경우 TLB Miss로, 기존과 동일하게 page table에서 page number를 통해 frame number를 구해낸다.

이를 **연관 사상(Assosiative Mapping)**이라고 한다. (바로 접근할 수 있는거)

연관 사상

• TLB가 단지 페이지테이블 일부 항목만 포함하고 있기때문에, 페이지 번호를 간단히 TLB의 인덱스로 사용 불가함

• 대신에 TLB항목들은 페이지테이블 항목 내용뿐 아니라 페이지 번호를 포함해야함

적절한 페이지 프레임 사이즈

• 만약 page의 크기가 작다면 내부 단편화가 적게 발생할 것이다. 대신 한 process 당 필요한 page의 수가 많아지고, 이는 결국 page table의 size를 늘리는 결과를 낳는다.

• page table의 size가 커지면 Multi-Programming 환경에서는 여러 활성 process 중 일부의 page table이 물리 memory가 아닌 swap 영역에 있어야 함을 의미한다. 최악의 경우에는 한 번의 memory 참조로 Page Fault가 2번(page table, page frame) 발생할 수 있는 것이다.