3. 페이징 속도 향상

지금까지 우리는 가상 메모리와 페이징의 기본적인 원리에 대해 알아보았다.
이제부터 어떻게 구현되는지 논의해 보자.
페이징 시스템은 다음의 두 가지 중요한 문제를 해결해야 한다.

1. 가상 주소에서 물리 주소로 주소 변환은 빠르게 이루어져야 한다.
2. 만일 가상 주소 공간이 커지면 페이지 테이블 크기도 커진다.

메모리가 참조될 때 마다 가상 주소와 물리 주소간에 변환이 필요하기 때문에, 주소 변환은 빠르게 이루어져야 한다.
모든 명령어는 결국 메모리에서 반입되어야 할 뿐만 아니라 많은 명령어들은 메모리 상에 존재하는 오퍼랜드(operand)를 참조한다. 결국 한 명령이 실행될 때 한번, 두번 또는 그 이상의 페이지 테이블 참조가 필요하다.

• 두가지 구현 예
  - 빠른 하드웨어 레지스터 배열로 구성된 단일한 페이지 테이블 사용
  - 이 테이블의 각 엔트리는 각각 가상 페이지에 대응됨
  - 프로세스 실행 시 OS는 메모리에 존재하던 프로세스의 페이지 테이블 전체를 하드웨어 레지스터 배열에 적재
  - 프로세스의 실행 중에는 페이지 테이블을 위한 메모리 참조 필요 X
  - 장점 : 직관적, 주소 변환을 위한 추가적인 메모리 참조가 없음
  - 단점 : 페이지 테이블의 크기가 커지면 구현을 위한 비용 증가
  - 단점 : 문맥 교환 시점에 페이지 테이블 전체를 적재하는데 비용이 비쌈
  • 페이지 테이블의 모든 내용을 메모리에 유지하는 방법
    • 페이지 테이블 시작 주소를 가리키는 하나의 레지스터만 필요
      • 장점 : 문맥 교환 시점에 이 레지스터의 내용만 변경
      • 단점 : 각 명령을 실행할 때 마다 페이지 테이블 엔트리를 참조하기 위해 최소한 한번의 메모리 참조가 필요하게 되며 실행이 느려짐

Paging Advatages

• 물리 메모리 allocate/free 가 쉬움
• 외부 단편화가 없음

Paging Disadvantages

• 내부 단편화가 존재
• 메모리 참조 오버헤드
• 페이지 테이블을 hold 하기 위해 요구되는 메모리가 커질 수 있음

3-1) Translation Lookasize Buffers(TLBs)

이제부터 페이징의 속도를 높이고 큰 주소 공간을 지원하는 실제 구현 기법을 살펴보자. 대부분의 기법은 페이지 테이블을 메모리에 유지한다.

예를 들어, 레지스터에서 다른 레지스터로 내용을 복사하는 1바이트 크기의 명령을 생각해보자.
페이징을 사용하지 않는다면, 이 명령은 메모리를 오직 한 번만(명령 반입 시) 참조하면 된다.
반면 페이징을 사용하면 페이지 테이블 참조를 위해 최소한 한번 이상의 추가적인 메모리 참조가 발생하한다. 일반적으로, 명령 실행 속도는 명령과 데이터를 메모리에서 가져오는 비율에 의해 결정되기 때문에 메모리를 참조할 때마다 2번의 메모리 접근은 성능을 절반으로 저하시키게 된다.
이런 조건이라면 아무도 페이징을 사용하지 않을 것이다.

하지만, 다음과 같은 해결 방법이 제안된다.
대부분의 프로그램들이 적은 개수의 페이지를 집중적으로 참조하는 경향이 있다는 관찰에 기반을 둔다.
결국 페이지 테이블 엔트리 중에서 일부만 빈번하게 참조되며, 다른 엔트리들은 아주 드물게 참조되는 것이다.

제안된 해결 방법은, 페이지 테이블 참조 없이 가상 주소를 물리 주소로 매핑할 수 있는 작은 하드웨어를 사용하는 것이다.

이 하드웨어를 TLB 또는 연관메모리(associative memory) 라고 부른다.
이것은 일반적으로
1) MMU 내부에 존재하며
2) 적은 개수의 엔트리를 갖는다.

위 그림에서는 8개의 엔트리를 가지고 있으며, 대부분 64개 미만의 엔트리를 갖는다.
각 엔트리는 한 페이지에 대한 정보를 포함한다.
(가상 페이지 번호(PTE index), 페이지의 수정 여부를 나타내는 비트, 보호코드, 물리 페이지 프레임 번호 등)

이제부터 TLB가 어떻게 동작하는지 알아보자.

1. MMU는 주소 변환을 할 때 우선 요청된 가상 페이지 번호가 TLB에 있는지 검색한다.
2. 만일 페이지가 존재하고 유효하며 보호코드를 위반하지 않는다면, 대응되는 페이지 프레임을 사용하여 주소 변환을 실행한다. (즉, 메모리에 있는 페이지 테이블에 대한 접근은 필요없다.)
3. TLB에 참조하는 페이지 번호가 존재하지 않는다면, TLB miss 가 발생한다. 그러면 MMU는 페이지 테이블을 검색하여 해당 페이지 테이블 엔트리를 찾는다.
4. 그리고 TLB 엔트리 중에 하나를 선택하여 그 내용을 교체하고, 새로 찾은 페이지 테이블 엔트리 내용을 선택한 TLB 엔트리에 기록한다.(이제부터 이 페이지가 다시 참조된다면 TLB 히트 발생)
5. TLB 엔트리가 교체될 때 수정 비트는 페이지 테이블에 기록한다.(참조 비트를 제외한 다른 정보들은 이미 페이지 테이블에 기록되어 있다.)
6. 새로운 정보가 메모리 TLB로 적재될 때 에는 대응하는 페이지 테이블 엔트리에 있는 내용이 적재된다.

3-2) 소프트웨어 TLB 관리

지금까지 논의된 시스템은 가상 메모리를 위해 페이지 테이블과 TLB를 사용한다.
이때 TLB 관리와 TLB 폴트에 대한 처리는 모두 MMU 하드웨어에 의해 처리된다.
OS로의 트랩 발생은 오직 페이지 폴트가 발생했을 때 뿐이다.

과거에는 TLB 관리는 모두 하드웨어가 담당하였다.
하지만 많은 RISC 시스템은 페이지 관리의 대부분을 소프트웨어로 처리할 수 있다. 이 시스템에서 TLB 엔트리의 관리도 OS에 의해 실행된다. TLB 미스가 발생하면 MMU는 자신이 직접 처리되는 것이 아니라 운영체제에게 TLB 결함 발생을 알릴 뿐이다. 그러면 OS가 해당 페이지 테이블을 검색하고, TLB에서 엔트리를 선택하여 교체하고, 새로운 페이지 정보를 적재하고, 결함을 발생한 명령을 다시 실행하는 모든 작업을 처리한다.
이러한 작업은 적은 부하로 실행되어야 한다. 왜냐하면 TLB 미스가 페이지 폴트보다 자주 발생하기 때문이다.

만일 TLB 가 미스 비율을 적절하게 줄일 수 있을 만큼 크다면, TLB를 소프트웨어로 관리하는 것이 충분히 효과적인 것으로 밝혀졌다.
TLB를 소프트웨어로 관리하면 MMU를 단순하게 만들 수 있고, 그 결과 CPU 칩의 여유공간을 크게하여 캐시나 다른 성능 개선 모듈을 추가할 수 있다.

• TLB 미스 비율도 줄이고 TLB 미스가 발생했을 때 처리하는 비용도 줄이는 방법에 대한 제안?
  -> TLB 미스를 줄이기 위해 OS는 어떤 페이지들이 미래에 사용될 지 예측하고 그들을 위한 엔트리를 미리 TLB에 적재

TLB Miss 처리

하드웨어적인 처리나 소프트웨어 적인 처리 모두 페이지 테이블을 찾는다.
페이지 테이블도 페이지 프레임에 존재하며 따라서 이를 위한 TLB 검색이 발생한다.
이때 만일 페이지 테이블을 담고있는 페이지 프레임의 정보 가 TLB에 없다면,추가적인 TLB 미스를 야기하게 된다.
이를 해결하기 위한 방법 중 하나는, TLB 엔트리를 위한 큰 소프트웨어 캐시를 사용하는 것이다.
이 소프트웨어 캐시는 고정된 위치에 있으며 이를 위한 페이지 정보는 항상 TLB에 존재한다. 운영체제는 소프트웨어 캐시를 먼저 검색함으로써 반복적인 TLB 미스를 줄일 수 있다.

소프트웨어적인 TLB 관리에서 발생하는 미스는 두 가지로 구분할 수 있다.

1. 소프트 미스(Soft miss)
   : 참조하려는 페이지가 메모리에 있지만 tlb에 정보가 없어 발생한 결함. TLB 갱신만 실행해주면 됨
2. 하드 미스(Hard miss)
   : TLB 뿐만 아니라 메모리에도 참조하려는 페이지가 없으며, 따라서 디스크 I/O를 필요로 하는 경우