[운영체제] 페이징(Paging), TLB

Paging?

---

contiguous allocation(연속 메모리 할당)을 사용하면 외부 단편화가 발생한다. Compaction을 사용하면 외부 단편화는 해결할 수 있지만, 오버헤드가 발생하기 때문에 비효율적이다. 이를 해결하기 위해 나온 방법이 페이징(paging)이다.

페이징은 프로세스가 차지하는 물리적 메모리 공간이 비연속적이 되도록 허용하는 메모리 관리 기법을 말한다. 페이징은 외부 단편화가 발생하지 않으며, 따라서 별도의 Compaction이 필요하지 않다(단, 내부 단편화는 발생할 수 있다). 논리적인 분할이 아닌 크기에 따른 분할이며 간단하다. 이러한 이점 때문에 대형 서버용 시스템에서 모바일 장치용 시스템에 이르기가지 대부분의 운영체제에서 페이징을 사용되고 있다.

페이징을 구현하는 기본적인 방법은 물리적 메모리를 고정된 크기의 프레임(Frame)으로 나누고, 논리적 메모리를 동일한 크기의 페이지(Page)로 나누는 것이다. 프로세스가 실행되면 페이지들은 메모리의 사용가능한 frame으로 적재된다. Backing store(예비 저장장치) 역시 고정된 크기의 block들로 나누어진다.

CPU에 의해 생성된 모든 주소들은 페이지 번호(Page Number, p)와 페이지 간격(Page Offset, d)으로 나뉜다. 페이지 번호는 페이지 테이블(Page Table)의 인덱스로써 사용된다.

페이지 테이블(Page table)은 물리 메모리의 각 프레임의 시작주소(base address)를 가지고 있으며, offset은 참조되는 프레임 안에서의 위치이다. 따라서 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다. CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 단계는 다음과 같다.

1️⃣ 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
2️⃣ 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
3️⃣ 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.
4️⃣ 프레임 번호 f와 오프셋 d는 물리 주소가 된다. (오프셋 d는 변하지 않는다)

페이지의 크기(프레임의 크기)는 하드웨어에 의해 정의된다. 페이지의 크기는 논리적 주소를 페이지 주소와 페이지 간격으로 바꾸는 것이 수월하도록 보통 2의 제곱 형태로 정해지며, 컴퓨터 구조에 따라 보통 한 페이지 당 512 byte ~ 16MB의 크기를 갖는다.

위의 그림과 같이 논리 주소 공간의 크기가 \(2^m\)이고, 페이지 크기가 \(2^n\) 바이트인 경우 논리 주소의 상위 m-n비트는 페이지 번호를 지정하고 하위 n비트는 페이지 오프셋을 지정한다.

페이징 기법을 사용하면 모든 사용 가능한 프레임이 프로세스에 할당될 수 있기 때문에 외부 단편화가 발생하지 않는다. 그러나 할당은 항상 프레임의 정수배로 이루어지기 때문에 내부 단편화가 발생한다. 예를들어 페이지 크기가 2048Byte이고 프로세스가 72766Btye라면 35개의 페이지 프레임을 할당하고 1086Byte가 남는다. 26번째로 할당되는 페이지 프레임은 2048-1086 = 962Byte의 내부 단편화가 발생하게 된다. 최악의 경우에는 단 1byte 차이 때문에 하나의 프레임을 더 할당해야 할 수도 있다.

그렇다면 페이지의 크기를 작게 만들수록 내부 단편화가 그만큼 덜 발생하지 않을까? 하지만 페이지의 크기가 줄어들수록 총 페이지의 갯수가 그만큼 늘어나고, 이 페이지들을 관리하는 오버헤드 또한 증가하게 된다. 또한 디스크 입출력은 한 번에 옮겨지는 데이터의 양이 많을수록 효율적이기 때문에, (일반적으로 디스크 입출력의 횟수를 줄일수록 효율이 좋다) 오늘날 일반적인 페이지의 크기는 4KB 또는 8KB로 정해졌다.

 

TLB(Translation Look-Aside Buffer)

---

실행될 때 마다 새로운 페이지테이블에 접근하는 과정을 반복하는 것은 프로세스 실행속도 면에 있어서 큰 오버헤드이다. 이를 해결하기 위해 일종의 캐시(cache)인 TLB가 사용된다. TLB는 키(key)와 값(value)을 저장한다. TLB에 페이지를 찾아달라고 요청이 들어오면 찾고자 하는 페이지를 동시에 여러개의 키와 비교한다. 페이지 번호가 같은 것이 발견되면(TLB hit) 이에 대응하는 프레임 번호를 알려준다. 

만약 페이지 번호가 TLB에 없다면(TLB miss) 그 테이블에 대한 메모리 참조가 이루어져야 한다. 위 그림과 같이 페이지 번호에 대응하는 프레임 번호를 TLB에 저장하여, 다음에 해당 페이지를 참조할 때 빠르게 메모리에 접근할 수 있도록 한다.

만약 TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택해야 한다. 교체 정책은 LRU부터 라운드 로빈, 무작위 등 다양한 정책이 사용된다. 

접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)이라고 부른다. 이를 활용하여 실질 접근 시간(effective memory access time)을 계산할 수 있다.

(Hit ratio) * (TLB Hit시 접근시간) + (1 - Hit ratio) * (TLB Miss시 접근 시간)

 

보호

---

페이징 환경에서 메모리 보호는 각 페이지에 보호 비트(protection bits)를 두어 해결할 수 있다. 이 비트들은 보통 페이지 테이블에 같이 저장된다.

대표적으로 아래 그림처럼 페이지 테이블마다 r(read), w(write), x(execute) 비트를 두어, 해당 비트가 켜져있을 때 그 수행이 가능하도록 하는 경우가 있다. (읽기 전용 페이지에 데이터를 쓰는 것은 하드웨어 Trap을 발생시킨다.)

일반적으로 페이지 테이블에 Valid-Invalid bit을 추가한다. 만약 이 bit가 valid라면, 해당 페이지는 프로세스의 논리적 주소 공간에 존재하며, 유효한(valid, legal) 페이지임을 나타낸다. 만약 이 bit가 invalid라면 그 반대이다. 운영체제는 각 페이지마다 이 bit를 설정해 페이지에 대한 접근을 허용 또는 차단한다.

 

공유 페이지(shared page)

---

페이징의 장점은 공통 코드를 공유할 수 있다는 점이다. 이는 여러 프로세스가 있는 환경에서 특히 중요하다.

40명의 사용자들이 동일 시스템 내에서 텍스트 편집기를 사용하는 경우를 생각해 보자. 편집기 프로그램은 150KB의 코드와 50KB의 데이터 공간을 가지므로, 40명의 사용자에 대해 8,000KB의 메모리가 필요하다. 그러나 코드가 재진입 코드(reentrant code)라면, 위 그림과 같이 공유될 수 있다. 그림에서 데이터를 제외한 ed1 ~ ed3은 프로세스 P1, P2, P3이 동일한 페이지를 통해 공유하는 것을 확인할 수 있다.

Reentrant code는 실행 중에 변하지 않는 코드를 의미한다. 따라서, 둘 이상의 프로세스가 동시에 같은 코드를 실행할 수 있다. 즉, 각 프로세스는 동일한 코드를 서로 다른 데이터로 실행하는 것이다.

이 경우 40명의 사용자들이 사용하는 메모리의 총량은 150KB + 50KB * 40 = 2150KB로 대폭 감소한다.