빽 투더 기본기 [OS 7편]. 메모리 관리 2

1. 페이지 테이블 구현

1.1. 페이지 테이블과 메모리 이슈

• 페이지 테이블도 메모리에 저장되어있다.
  • 기준 레지스터 Page Table Base Register (PTBR)
    • 페이지 테이블의 시작 주소가 저장되어있다.
  • CS(Context Swithching) 시 페이지 테이블 교체 비용이 적다
    • PTBR 값만 변경
• 메모리 접근 시간 문제
  • 메모리 접근시간 2배
    • 하나의 메모리 접근을 위해 페이지 테이블을 거쳐야 하므로, 메모리를 2번 읽게 되고, 결과적으로 접근시간은 2배 걸림
  • TLB (Translation Look-aside Buffer)
    • 페이지 테이블의 캐싱으로 해결

1.2. TLB

메모리에 있는 페이지 테이블과 다르게, 캐시 메모리(하드웨어)에 별도로 (페이지 넘버 - 프레임 넘버)에 대한 매핑 정보를 담고 있는 테이블이다.

1) Hit vs Miss

• TLB hit
  • TLB에 페이지 넘버가 존재하는 경우.
  • TLB를 통해, 페이지 테이블에 접근하지 않으므로, 결과적으로 메모리에 2번 접근하지 않고, 1번 접근하게 된다.
• TLB miss
  • TLB에 페이지 넘버가 없는 경우.
  • 기존의 방식에 TLB 접근시간이 추가되므로, 기존보다 시간이 더 든다.

따라서, 이제 주 이슈는 TLB miss를 줄이는 방법에 대한 것이다. 구체적으로, TLB miss 가 날 때, TLB를 어떻게 바꿀 것인가 (TLB replacement) 문제가 된다. 이에 알고리즘은 LRU, FIFO, RANDOM 등이 있다.

2) ASID (Address-space Identifier)

한편, 프로세스마다 다른 페이지 테이블을 가지므로, 전역에 있는 TLB는 전체 프로세스에 대한 캐시를 다뤄야 한다. 즉, 전역에 있는 TLB 는 테이블에는 단순히 페이지 넘버뿐 아니라, 프로세스 아이디도 가지고 있어야 한다. 이를 Address-space Identifier(ASID)라고 한다.

3) EAT (Effective Memory-Access Time)

TLB를 사용할 때 평균 메모리 접근 시간을 EAT라고 한다.
다음과 같은 식으로 구할 수 있다.

1.3. 페이지 테이블의 구조

• 페이지 테이블의 크기가 너무 큰 문제

  • 예를 들어, 시스템 논리 주소 공간이 32비트인 경우,
    • 페이지 크기 : 4KB (2^12)
    • 페이지 테이블 항목(프레임 주소를 담는 곳) 크기 : 4 Bytes
    • 페이지 테이블의 크기 : 4MB (4 * 2^(32-12))
  • 그런데 페이지 테이블 메모리 공간은 연속적이어야 하므로, 실제 메모리 공간에서 각 프로세스마다 이를 배치하기가 어렵다.

• 크기가 큰 페이지 테이블의 처리

  • 계층적 페이징
  • 해시 페이지 테이블
  • 역 페이지 테이블

1) 계층적 페이징

기존의 페이지 엔트리를 더 잘게 나누는데, 이때 계층적으로 나눈다.

32비트 명령어 기준, 페이지 크기가 4K 인 경우

즉, 32비트 명령체계 기준, 페이지 넘버를 나타내는 비트가 20비트였다.
이전에는 2^20개의 공간이 연속적으로 필요했다면, 이제는 2^10개의 공간만 연속적이면 된다.
이렇게 2^10개의 공간이 여러 곳에 2^10개 분할되어 저장되므로, 기존의 페이지 테이블이 연속적으로 너무 컸던 문제를 일정 부분 해결한다. 계층은 2개 이상으로 나눌 수 있고, 이는 설계자의 몫이 되겠다.

다만, 이전과 비교했을 때 메모리를 한 번 더 참조해야 하기 때문에, (기존에는 2번 읽었다면, 2 level 계층 구조 기준, 이제는 3번 읽어야 한다.) 계층이 늘어날수록 메모리 접근시간은 느려진다.

2) 해시 페이징

기존처럼 페이지 테이블에서 페이지 번호를 '인덱스'로 인식하여 페이지 테이블에 접근하는 것이 아니라, 페이지 테이블을 해시 테이블로 보고, 페이지 번호를 해싱하여 페이지 테이블에 접근한다.

페이지 테이블은 각 해시 값에 따른 (페이지 번호, 프레임 번호) 노드로 된 연결 리스트로 구성되어있다.
좀 더 자세히 과정을 보면 다음과 같다.

1) 논리 주소에서 페이지 번호를 해싱하여, 해싱 값을 만든다.
2) 해싱 페이지 테이블에서 해당 해싱 값의 연결리스트를 탐색하며, 페이지 넘버가 일치하는지 탐색한다.
3) 일치 하는 경우, 해당 프레임 번호를 반환한다.
4) 일치 하지 않는 경우, 다음 노드로 이동한여 2~3 반복

아무래도, 해시 함수가 얼마나 균등하게 해시 값들을 뿌려주느냐에 따라 메모리 접근 시간의 성능 차이가 있다.

3) 역 페이지 테이블

역 페이지 테이블 구현은, 논리 주소 구성부터가 일단 다르다.
기존의 논리 주소는 (페이지 넘버, 오프셋 넘버)로 구성되어 있었다면, 이 시스템에서는 (프로세스 아이디, 페이지 넘버, 오프셋 넘버)로 구성된다.

이러한 논리 주소 구성 하에, 페이지 테이블 역시 달라지는데 자세히 살펴보면 다음과 같다.

1) (페이지 번호, 프레임 번호)를 엔트리로 가지는 기존의 페이지 테이블과 달리 (프로세스 아이디, 페이지 주소) 를 엔트리를 가진다.
2) 논리 주소를 가지고 페이지 테이블에서 해당하는 엔트리를 찾는다. (프로세스 아이디, 페이지 주소로 비교)
3) 찾았으면, 그 엔트리의 순서의 수(i번째)가 곧 프레임 번호가 된다.

---

2. Segmentation

앞선 장들에서 페이징을 배우면서 프로세스를 일정 크기인 페이지 단위로 잘라서 메모리에 적재하는 방법을 알았다. 페이지는 정확하게 일정한 간격으로 자르는 단위였다. 하지만 프로세스를 물리적인 단위인 페이지 말고 논리적 내용 단위인 세그먼트로 자를 수 있는 세그먼테이션 방법이 있다. 예를 들면 우리가 돼지를 잡아서 보관을 한다고 생각해보자. 페이징의 방법을 사용하면 돼지를 모두 같은 단위로 잘라서 보관을 하는 것이다. 반면에 세그먼테이션은 부위별로 다른 크기로 잘라서 보관하는 것이다.

출처: https://copycode.tistory.com/108 [ITstory]

페이징 시스템과 동일하게 비 연속적 메모리 할당 방법이지만, 메모리를 일정 크기로 나누는 페이징과 달리, 의미 있는 요소 단위로 메모리를 나눈다. 이 단위 요소 하나하나를 세그먼트(Segment)라고 한다.

2.1. 세그먼트 테이블

페이지 테이블과 비슷하게 세그먼트들의 물리 메모리 정보를 저장하는 테이블을 세그먼트 테이블이라고 한다.

• 이 테이블은 해당 세그먼트의 시작 물리 주소 base 와 세그먼트 용량을 나타내는 limit 의 정보를 담는다.
• 읽기, 쓰기, 실행 등의 권한을 담는 privilege 정보도 담는다.

세그먼트 테이블 역시 메모리에 올라와 있는데, 테이블 주소 정보를 세그먼트 테이블 베이스 레지스터 (STBR)가 담고 있다.
세그먼트 테이블 길이 레지스터 (STLR)는 프로그램에 의해 사용되고 있는 세그먼트의 개수 정보를 담는다.

2.2. 주소 변환 과정

• 오프셋 번호가 (위 그림에서는 d ) 가 limit을 넘을 경우, 해당 세그먼트의 메모리 범위를 벗어난 것이므로 오류 (Segmentation fault) 를 발생시킨다. 이런 방식으로 Memory pretection을 간단히 구현한다.
• 위 조건에 해당하지 않는 경우 (d < limit 인 경우), 오프셋 넘버는 그대로 가져가고, 세그먼트 번호만 물리 주소로 변환되어 실제 물리 주소에 접근하게 된다.

2.3. 특징

장점

• 논리 단위로 메모리를 나누기 때문에, 프로세스 실행 과정에서 메모리 접근시간이 더 좋을 수 있다.
• 페이지 테이블과 비교했을 때, 엔트리 수가 훨씬 적기 때문에, 메모리를 덜 사용한다.

단점

• 세그먼트마다 메모리 크기가 가변적이다. 따라서, 외부 파편화(External Fragmentation) 이 일어날 수 있다.

2.4. 페이지 시스템과의 혼용

실제로는 페이지 시스템과 세그먼트 시스템의 장점을 합한 페이지 + 세그먼트인 시스템을 사용한다.