CS/운영체제

[운영체제] 페이징 기법

blaxsior 2022. 5. 16. 22:06

페이징 기법

 연속 적재 기법을 이용하면 내부 단편화 및 외부 단편화가 발생하는 문제점이 존재했다. 그런데 사실 프로세스는 세그멘테이션 기법에서 언급했듯이 특정 기능 단위로 쪼개서 관리하는 것이 가능하다. 특정 프로세스가 실제로 저장되는 물리적 주소는 각각의 물리적 주소를 가리키는 연속적인 논리적 주소가 있다면 사실상 연속적으로 관리되는 것 같다.

 페이징 기법은 물리적 메모리를 Frame 이라고 불리는 고정된 크기의 블럭 단위로 쪼갠 후 이를 동일 크기를 지닌 논리적 메모리 영역인 Page에 대응시켜 프로세스를 페이지 단위로 쪼개 관리하는 기법을 의미한다. 각 프로세스는 페이지라는 논리적 메모리 단위로 관리되며, 페이지와 프레임은 페이지 테이블에 의해 매핑되므로 실제 물리적 주소와는 독립적으로  동작할 수 있게 된다. 이때 각각의 프로세스는 대응되는 페이지 테이블을 기반으로 프레임 주소와 대응한다. 

 페이징 기법을 사용하기 위해서는 운영체제 및 하드웨어의 도움이 필요하다. 특정 프로세스가 N개 페이지 크기를 가지고 있다면, 운영체제는 자신이 추적하고 있는 모든 프레임 중 현재 free 한 프레임 N개를 각각의 페이지에 대응시켜 프로세스에게 공간을 할당한다. 이때 운영체제는 메모리 영역을 프레임의 크기 단위 ( 512 KB ~ 16 MB ) 단위로 쪼개고, 메모리 상에 적재되는 프로세스 역시 해당 크기에 대응되는 페이지 단위로 쪼개 관리되므로 외부 단편화 현상이 발생하지 않는다는 장점이 존재한다. 기존 Dynamic allocation 방식에서는 외부 단편화 현상으로 인한 메모리 공간을 사용할 수 있도록 주기적으로 프로세스를 메모리 상에 다시 배치하여 free hole을 합쳐주는 작업을 진행해야 했는데, 페이징 기법을 이용하게 되면 최소한 이러한 오버헤드는 절대 발생하지 않는다는 장점이 있다.

Address Translation Scheme

 주소를 2가지 분류로 나눈다.

  • Page number : 페이지 테이블에 대한 인덱스. 테이블 상에 인덱스에 대응되는 실제 base address 정보가 담긴다.
  • Page offset : 해당 페이지에서의 상대적 주소로, base address와 조합되어 실제 주소를 가리킨다.

ex ) 전체 주소가 32 비트 환경일 때 p = 10 이라면 페이지의 총 개수는 210 개이고, 페이지 하나의 크기는 222 이다.

페이징 기법 예시

(좌)페이징 기법 기반 주소가 실제 물리적 주소에 대응되는 모습 / (우) m = 4, n = 2 일때 페이지가 프레임에 대응되는 모습

우측 그림에서는 n = 2, m = 4 일때의 페이징 기법을 설명하고 있다. 이 경우 페이지의 개수는 2(m-n) = 4, 페이지의 오프셋은 2n = 4byte 가 된다. 이러한 개념에 따라 페이지 테이블에서는 총 4의 페이지 인덱스를 관리하고 있으며, 대응되는 실제 물리적 주소는 f * 4byte ( 오프셋을 통해 알 수 있는 페이지의 크기 ) + d 가 된다.

페이지 계산

 페이지의 크기가 2048 bytes , 프로세스의 크기가 72766 이면 35개의 페이지 ( 몫 ) + 1086 bytes 로 나타낼 수 있으므로 총 36개의 페이지가 필요하다. 이때 내부 단편화는 2048 - 1086 = 962 만큼 나타난다.

페이징에 의한 단편화의 크기는 다음과 같다.

  • 최악의 경우 : 1frame - 1byte ( 하나의 페이지에서 1byte만 쓰는 경우 )
  • 최선의 경우 : 0 ( 남는 페이지 없이 전부 다 씀 )
  • 평균의 경우 : 1/2 frame

 단편화 자체는 페이지 하나의 크기를 작게 만들 수록 작아지지만, 추적해야 하는 메모리상의 프레임 개수는 반대로 증가하므로 무조건 크기를 작게 만드는 것이 성능에 좋지는 않다. 따라서 적절한 크기를 선택해야 한다.

메모리 할당 방식

 운영체제는 현재 사용가능한 프레임들에 대한 리스트를 관리한다. 새로 프로세스가 들어오면 해당 프로세스의 페이지 개수를 계산한 후, 각각의 페이지를 free-frame에 대응시킨다. 대응된 프레임들은 free-frame list에서 빠져나와 사용중이라는 것을 플래그 등의 방법을 이용하여 표시한다.

페이지 테이블의 구현

 페이지 테이블은 특정 프로세스에 대한 페이지들을 물리적 메모리의 프레임과 대응시키는데 사용된다. 이때 각각의 프로세스는 자신의 고유한 페이지 테이블을 기반으로 동작하므로 프로세스에 대한 컨텍스트 스위칭이 발생하면 페이지 테이블 역시 변경된다. 따라서 해당 정보들 역시 상당히 빈번하게 변경되기 때문에 페이지 테이블의 주소 및 페이지 테이블의 길이 정보를 가리키는 레지스터를 별도로 둠으로써 페이지 테이블에 대한 빠른 접근을 가능하게 한다.

  • Page-table base register(PTBR) : 페이지 테이블의 시작 주소
  • Page-table length register(PTLR) : 페이지의 사이즈

 이때 페이지 테이블을 메모리에서 관리하게 되면 실제 주소를 가리키기 위해 2번의 메모리 엑세스가 필요하다.

  1. 페이지 테이블의 엔트리에 접근
  2. 페이지 테이블 정보를 기반으로 실제 데이터 혹은 instruction 에 접근

따라서 이 방법만 사용하면 상당히 비효율적인 구조가 된다.

Translation Look-Aside Buffer

 따라서 TLB라는 매우 빠른 하드웨어적인 캐시 메모리를 이용한다. TLB에는 페이지 번호 / 프레임 번호가 대응되어 적혀 있으며, CPU는 TLB를 이용하여 메모리를 한번만 거쳐 페이지의 실제 물리적 주소를 얻을 수 있다. TLB는 병렬적으로 즉각 검색할 수 있는 특성을 가지고 있다고 하며, 빠른 하드웨어는 비싸기 때문에 크기가 통상적으로 작다.

 TLB의 크기 한계 떄문에 모든 페이지를 TLB을 이용하여 접근할 수는 없다. 이때 찾는 페이지 번호가 TLB 상에 있다면 hit 이라고 표현하고, 없다면 miss 라고 표현한다. miss 인 경우에는 해당 프로세스에 대응되는 페이지 테이블에 접근하여 다시 해당 페이지 인덱스를 검색해야 한다.

 Effective Access Time 

  • Hit ratio : TLB를 뒤졌을 때 페이지 번호가 hit 할 확률
  • EAT = (1t + ε)α  (2t + ε)(1 -  α) = (2 - α)t + ε 
    • TCB을 사용할 때 메모리에 접근하는데 걸리는 평균적인 시간 
    • ε : TCB 에 접근할 때 걸리는 시간
    • t : 메모리에 접근할 때 걸리는 시간
    • α : Hit ratio

ex ) α = 80% , ε = 20ns, t  = 100ns 

EAT  = 0.8 * ( 20 + 100 ) + (1 - 0.8) * ( 20 + 200 ) = 140ns

ex ) α = 99% , ε = 20ns, t  = 100ns 

EAT = (2 - 0.99) * 100 + 20 = 121ns

Hit ratio에 따라 메모리 접근 성능이 크게 변화하므로 이를 높게 유지하는것이 중요하다.

Memory Protection

 연속 할당 방식에서는 해당 주소 위치가 valid 한지 여부를 프로세스에 대응되는 메모리 크기의 길이 및 시작 주소를 기반으로 알 수 있었다. 그러나 페이징 기법에서는 프로세스가 저장되는 실제 주소들이 퍼져 있기 때문에 연속적인 방식으로 주소를 판단할 수 없다.

 대신 각각의 페이지 단위로 해당 페이지에 대응되는 비트 플래그를 두고, 이를 기반으로 페이지를 관리하게 된다. 

  • Protection bit : 특정 프레임에 대한 read / write / execute 권한을 나타내는 비트
  • Valid-Invalid bit : 페이지 테이블에 존재하는 플래그로, 각각의 페이지가 유효한지 여부를 나타낸다.

valid-invalid bit는 특정 페이지가 유효한지, 유효하지 않은지를 알리는 비트이다. 특정 페이지가 유효하다(valid)는 것은 현재 해당 페이지가 프로세스의 논리적 주소에 포함되어 legal 함을 의미하고, 반대의 경우(invalid) 현재 페이지가 프로세스의 논리 주소에 포함되지 않아 illegal 함을 의미한다.

 먄약 페이지 테이블을 통해 접근한 페이지가 invalid 하다면 trap을 발생시킨다. 만약 해당 페이지가 필요한 상황이었다면 trap을 통해 대응되는 프레임을 요청하게 된다.

페이지는 5번까지이므로 6, 7번 페이지는 접근할 수 없다.

Shared Page

 printf 같은 함수들은 정말 많은 프로세스에서 사용된다. 이때 이러한 instruction 들에 대한 코드를 각각의 프로세스마다 소유 및 실행하도록 구현하는 것은 매우 비효율적이다. 따라서 연속 적재 방식에서도 DLL 같은 경우 다양한 프로세스에서 stub을 도입하여 특정 코드를 가리키는 방식으로 사용했다.

 페이징 기법에서는 다양한 프로그램에서 공유하여 사용하고자 하는 프로세스를 Shared Page에 넣어 공유한다. 해당 페이지는 다양한 프로세스들의 논리적 주소 자리를 차지하게 된다. 이때 데드락 및 기능 변경 방지 등의 이유로  공유 대상이 되는 코드는 reentrant ( read-only, 실행 중 내용 안바뀜 ) 특성을 가진 것으로 제한된다.

 동일한 Shared page을 참조하는 프로세스들의 경우 내부적으로 공유되는 프레임에 대한 페이지를 가지고 있다. 이때 해당 페이지들은 모두 동일한 프레임을 가리킨다.

 단, Shared Page라도 fork 처럼 프로세스 간 통신 용도로 사용되는 경우 읽고 쓰는 동작이 가능할 수 있다.

페이지 테이블의 구조

 address을 계산할 때 32-bit 기반의 주소를 사용한다고 생각해보자. 만약 페이지의 크기에 12 비트를 할당하면 20비트를 통해 페이지의 번호를 나타낼 수 있게 된다. 이때 페이지의 총 개수는 220 으로, 대략 백만개가 된다.

 문제는 프로세스는 페이지 단위로 쪼개지지만, 페이지와 프레임을 매핑하는데 사용되는 페이지 테이블 자체는 메모리 상에 연속된 형태로 할당된다는 것이다. 따라서 위 상황에서는 못해도 백만개의 인덱스에 대응되는 크기의 메모리가 연속적으로 할당되어야 하는 문제가 발생한다.

 따라서 페이지 테이블 조차도 더 작은 단위로 쪼개 관리하는 방법을 고려하게 되었으며, 3가지 방법이 존재한다.

  1. Hierarchical Page Tables
  2. Hashed Page Tables
  3. Inverted Page Tables

Hierarchical Page Tables

 페이지 테이블을 계층적으로 관리하는 방식. 페이지 테이블이 또 다른 페이지 테이블을 참조하는 방식으로 구현된다. 최상위 테이블인 outer page table 부터 시작하여 연쇄적으로 page of page table 을 참조하여 최종적으로 실제 메모리 공간을 가리키는 구조로 구성된다.

 일반적으로는 2계층 페이징 테이블(Two-Level Paging Table) 의 형태를 띄나, 64bit 환경의 도입 등으로 인해 주소에 사용되는 메모리 크기가 커짐에 따라 outer page table이 가리키는 범위가 너무 넓어지는 경우 계층을 하나 더 나눠 3계증 페이징 테이블 (Three-Level Paging Table) 을 구성하기도 한다. 이때 계층이 많아지면 많아질수록 실제 메모리에 도달하는데 걸리는 시간은 길어지기 때문에 충분한 고려 없이 계층을 나누는 것은 좋지 않다. 계층이 높은 경우에는 TLB의 hit ratio가 계층이 적은 상황보다 더 중요해진다. 

Hashed Page Tables

 논리적 주소에서 Page Number p 부분에 해싱을 적용하여 실제 물리적 주소로 치환하는 방식으로, 페이지 테이블을 해시 테이블로 구성하며 체이닝 기법을 이용한다. 페이징 테이블은 ( page_number, frame_number, next ) 형식의 노드를 가리키며, 해싱을 통해 얻은 포인터부터 순차적으로 실제 페이지 번호와 대응하며 비교해나간다. 페이지 번호가 같은 경우 해당 노드에 기록된 프레임 번호를 이용하여 실제 주소를 얻는다.

 간단하게 말하면 페이지 테이블을 체이닝 기반 해시 테이블로 구성한 것이다.

Inverted Page Table

 기존 방식에서는 각각의 프로세스마다 고유한 페이지 테이블을 두고, Page number p 을 페이지 테이블에 입력하여 대응되는 프레임 번호 f을 얻을 수 있었다. 이때 페이지 테이블은 "p 에 대응되는 프레임은 f 번이야" 라는 정보를 제공하는데 사용되었다. 따라서 p -> f 형태의 정보를 지닌 셈이었다.

 Inverted Page Table은 f로부터 pid와 p이 존재하는 인덱스를 역산하는 방식으로 동작한다. 이때 입력이 되는 pid 및 p는 일종의 튜플 키로, (pid, p) 가 존재하는 테이블에서의 인덱스가 frame number가 된다. 따라서 "frame number f 인덱스에 프로세스의 p번 페이지가 존재해" 라는 정보를 제공한다고 볼 수 있다. 구조상 프레임 번호로부터 프로세스 및 페이지를 역산하는 것으로 생각할 수 있겠다.

 해당 구조는 모든 프로세스에 개별적으로 존재했던 페이지 테이블을 하나의 커다란 페이지로 구성하며 페이지 테이블의 인덱스가 프레임의 번호에 대응된다는 특징을 가지고 있다. 각각의 페이지를 만들 필요가 없으므로 메모리를 아낄 수 있다는 장점이 존재하지만, 프로세스의 페이지가 전체 메모리에 대응되는 공간에 분산되어 있으므로 프로세스의 전체 페이지를 찾는데 시간이 오래 걸린다.  따라서 해시 테이블 기법이나 TLB을 활용하여 속도를 늘려야 한다.