운영체제 12 - Hybrid Approach: Paging & Segmentation [Memory Virtualization]

Bigger Pages

페이지 테이블의 크기를 간단하게 줄일 수 있는 방법이 한 가지 있다. 페이지 크기를 키우면 된다.
32비트 주소 공간에서, 이번에는 16KB 페이지를 가정해보자.
이 때 Offset은162^10 = 2^42^10 =2^14 즉, offset은 14bit가 필요하다.

자연스럽게 나머지 32-14= 18비트가 VPN을 표현하는데 사용한다.
이렇게 18비트의 VPN과 14비트의 offset을 갖게 된다.
Page Table은 VPN수에 의해 정해진다. 각 PTE가 4byte이면 42^18 = 2^20byte = 1MB 즉, Page Table은 1MB가 된다.
기존 테이블 대비 크기가 1/4로 감소된다.( 테이블의 크기가 1/4로 감소한 것은 페이지 크기가 4배 증가했기 때문이다.)
!— 페이지 크기의 증가는 부작용이 있다. 가장 큰 문제는 페이지 내부의 낭비 공간이 증가한다. 이를 내부 단편화 (*internal fragmentation**)라 한다.(할당된 내부에서 낭비가 발생하기 때문이다.)
응용 프로그램이 여러 페이지를 할당 받았지만, 할당 받은 페이지의 일부분만 사용하는 터에, 결국 컴퓨터 시스템의 메모리가 금방 고갈되는 현상이 발생한다. 이런 이유로 많은 컴퓨터 시스템들은 비교적 작은 페이지들을 사용한다. → page가 크면 internal fragmentation이 발생 → 메모리 고갈

하이브리드 접근 방법: Paging & Segment

---

힙과 스택에서 실제로 전체 공간 중 작은 부분만 사용되는 경우를 생각해보자.
먼저 1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 들자(왼쪽 Virtual Address Space).
이 주소 공간을 위한 페이지 테이블은 아래 그림과 같다.

이 예제에서 VPN 0→ 물리 페이지 10번을, VPN 4→ 23번 물리 페이지에 매핑되어 있다. 가상 주소 공간의 끝 부분에 두 개의 스택 페이지 (VPN 14, 15)가 물리 페이지 28번, 4번에 매핑되어있다. 그림을 보면 페이지 테이블 대부분이 비어 있다. 엄청난 낭비가 발생한다. ←(Internal fragmentation)
16KB 크기의 아주 작은 주소 공간에서도 이렇게 발생하는데 32비트 주소 공간에서는 더 심할 것이다. 이를 해결하기 위한 방법을 생각해보자.!!!
프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신(이전 방식),
논리 세그멘트마다 따로 페이지 테이블을 두면 어떨까?

← 뭔 소리여 ㅋㅋㅋ

즉, Code, Heap, Stack Segment에 각각 페이지 테이블을 두는 것이다.
세그멘테이션에서는 세그멘트의 물리 주소 시작 위치를 나타내는 base 레지스터, 크기를 나타내는 bound(limtit) 레지스터가 있다. 우리의 결합 방식에서도 MMU에 비슷한 구조를 사용한다.
base 레지스터는

세그멘트 시작 주소를 가리키는 것이 아니라

세그멘트의 페이지 테이블 시작 주소를 갖는다. 바운드 레지스터는 페이지 테이블의 끝을 나타내기 위해서 사용한다.
예를 보면서 이해해보자. ← 이해가 될까? 휴먼?

가상 주소

4KB 페이지를 갖는 32비트 가상 주소 공간이 4개의 세그멘트로 나누어져 있다고 가정하자.
하지만 이 예제에서는 3개의 세그멘트만 사용하도록하자. 하나는 CODE, 다른 하나는 HEAP, 또 하나는 STACK을 위해서 사용한다. 소속 세그멘트를 나타내기 위해 상위 두 비트를 사용한다.
미사용 세그멘트: 00, CODE: 01, HEAP: 10, STACK: 11을 나타낸다고 가정하자.
↑ 가상 주소는 위 사진과 같이 나타낼 수 있다.

하드웨어에 세개의 base/bound 레지스터 쌍이 CODE와 HEAP, STACK을 위해서 존재한다고 가정하자. 실행 중인 세그멘트 페이지 테이블의 시작 물리 주소를 갖는다. 이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 갖는다. context Switch시(문맥 교환), 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치 값으로 변경된다.

TLB 미스가 발생하면, (하드웨어 기반 TLB에서) 하드웨어는 SN(세그멘트 비트)를 사용하여 어떤 base, bound쌍을 사용할지 결정한다. 하드웨어는 레지스터에 들어 있는 물리주소를 VPN과 다음과 같은 형식으로 조작하여 PTE의 주소를 얻는다.

동작 순서는 눈에 익숙하다. 앞에서 살펴 보았던 선형 페이지 테이블의 작동과 거의 동일하다. 유일한 차이가 있다면 하나의 페이지 테이블 베이스 레지스터를 사용하는 대신 세 개중의 하나의 세그멘트 베이스 레지스터를 사용하는 것이다.

하이브리드 기법에서 핵심은 세그멘트마다 바운드 레지스터가 존재한다는 것이다. 각 바운드 레지스터의 값은 세그멘트의 최대 유효 페이지의 개수를 나타낸다. 해당 세그멘트의 범위가 넘어가는 곳에 대한 메모리 접근은 예외를 발생시키고, 해당 프로세스는 종료될 것이다.
이와 같은 방식으로 선형 페이지 테이블에 비해 메모리 사용을 개선시킬 수 있다. 스택과 힙 사이의 할당되지 않는 페이지들은 페이지 테이블 상에서 (유효하지 않다는 것을 표시하기 위해서) 더 이상 공간을 차지하지 않는다.

문제점

1. 여전히 Segmentation을 사용해야한다. 이전에 언급했듯이 Segmentation은 주소 공간의 사용에 있어 특정 패턴을 가정하기때문에 우리가 원하는 만큼 유연하지 않다. 큰 공간을 커버하지만 드문 드문 사용되는 힙의 경우에는 여전히 페이지 테이블의 낭비가 발생한다.
   즉, Segmentation은 특정 패턴을 가정해야하기때문에 유연하지 않고 힙의 성격과 맞지 않아 페이지 테이블의 낭비가 발생한다.
2. 하이브리드 기법은 외부 단편화를 유발한다. 페이지 테이블의 크기에 제한이 없으며 다양한 크기를 갖는다. 물론 페이지 테이블의 크기는 테이블 항목 크기의 정수배가 되어야한다. 이런 이유로메모리 상에서 페이지 테이블용 공간을 확보하는 것이 더 복잡하다.
   즉, 하이브리드 기법에서는 페이지 크기가 다양하기때문에 외부 단편화가 발생한다는 것.