메모리 관리 전략

베경
스와핑
연속 메모리 할당
세그먼테이션
페이징
페이지 테이블 구조

배경

기본 하드웨어

시스템이 올바르게 동작하기 위해서는 사용자 프로그램으로 부터 OS 영역을 보호해야한다. 다중 사용자 시스템인 경우 추가적으로 다른 사용자 프로그램이 특장 사용자 프로그램을 접근하는 것을 막는 것도 함께 이우어 져야 한다.

OS가 CPU와 메모리 간의 접근중에 개입하게 되면 성능이 떨어지기 떄문에 이러한 보호기법은 반드시 하드웨어 차원에서 지원되어야 한다.

각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다. 개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법저인 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근 가능하도록 하는것이 필요하다.

기준(base)와 상한(limit)라고 불리는 두개의 레지스터들을 사용하여 이러한 보호 기법을 제공한다. 기준 레지스터는 가장 작은 합법저긴 물리 메모리 주소의 값을 저장하고, 상한 레지스터는 주어진 영역의 크기를 저장한다.


기준과 상한 레지스터가 논리 주소공간을 정의

메모리 공간의 보혼는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어 진다.

사용자 모드에서 수행되는 프로그램에 의해 OS의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간의 접근이 일어나면, OS는 치명쩍인 오류로 간주하고 트랩(Trap)을 발생시킨다. 이러한 기법은 사용짜 프로그램이 OS나 다른 사용자 프로그램의 코드나 데이터 구조를 수정하는 것을 막는다.


기준과 상한 레지스터 하드웨어를 통한 주소 보호

커넣모드에서 수행되는 OS는 OS 메모리 역역과 사용자 메모리 영역의 접근에 어떠한 제한을 받지 않는다. 이러한 원칙 때문에 OS는 사용자 프로그램을 사용자 메모리 영역에 적재, 오류가 발생한 경우에 그 프로그램을 덤프(dump), 시스템호출의 매개변수를 변경, 사용자 메모리로부터 입출력과 다른 많은 서비스들을 제공할 수 있다.

주소의 할당(Address Binding)

프로그램은 원래 이진 실행 파일 형태로 디스크에 저장됭어 있고, 이를 주 메모리로 올라와서 ‘프로세스’ 가 되야 한다.

디스크에서 주 메모리로 들어오기를 기다리고 있는 프로세스들을의 집합을 입력 큐(Input Queue) 를 이룬다. 보통의 단일 태스킹의 작업절차는 이 입력 큐의 프로세스 중 하나를 선택하여, 메모리로 적재한다. 이 프로세스는 실행 중에 메모리에서 명령어와 데이터를 액세스한다. 언젠가 이 프로세스가 종료되면 이 프로세스가 사용했던 기억공간이 가용공간이 되어 다른 프로세스를 위해 사용된다.

원시 프로그램에서 주소는 숫자가 아닌 변수 count와 같이 심볼 형태로 표현된다. 컴파일러는 이 심볼주소를 재배치 가능 주수로 바인딩(Binding) 시키고, 추후에 링커나 로더가 이 재배치 가능 주소를 절대 주소로 바인팅 시킨다. 각각의 바인딩 과정은 한 주소 공간에서 다른 주소공간으로 맵핑하는 것이다.

전통적으로 메모리 주소공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 다음과 같이 구분된다.

컴파일 시간 바인딩(Compile Time Binding)
- 프로세스가 메모리 내에 듫어갈 위치를 컴하일 시간에 미리 알 수 있으면 컴파일러는 절대코드 를 생성할 수 있다.
적재 시간 바인딩(Load Time Binding)
- 프로세스가 메모리 내 어디로 올라오게 될자를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진코드를 재배치 가능 코드 로 만들어야 한다.
- 심볼과 진짜 번지수와의 바인딩은 프로그램이 주 메모리로 실쩨로 적재되는 시간에 이루어 진다.
- 재배치 가능 코드는 시작주소가 변경되면 아무때나 사용자 코드를 다시 적재하기만 하면 된다.
실행 시간 바인딩(Execution Time Binding)
- 프롯세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨 질 수 있다면 우리는 “바인딩이 실행 시간까지 허용되었다” 고 이야기 한다.


사용자 프로그램의 단계별 처리 과정

논리 대 물리 주소 공간(Logical Versus Physical Address Space)

CPU가 생성하는 주소를 일반적으로 논리주소(Logical Address) 라 하며, 메모리가 취급하게 되는 주소(즉, 메모리주소 레지스터(MAR) 에 주어지는 주소)는 일반적으로 물리주소(Physical AAddresss) 라 한다.

컴파일시 바인딩과 적재시의 바인딩 기법의 경우에는 논리주소와 물리주소가 같다.

실행시간 바인딩 기법에서는 논리주소와 물리주소가 다르다. 이러한 경우, 논리주소를 가상주소(Virtual Address ) 라 한다.

프로그램에 의해 생성된 모든 논리 주소의 집합을 논리 주소 공간(Logical Address Space) 라 하며, 이 논리주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간(Physical Address Space) 라 한다.

프로그램의 실행 중에는 이와 같은 가상주소를 물리 주소로 바꾸어 줘야 한는데 이 맵핑 작업은 하드웨어 장치인 메모리 관리기(MMU, Memory Managment Unit) 에서 실행된다.

MMU에선 기준 레지스터를 재배치 레지스터(Relocation Register) 라고 부른다. 기준 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 떄마다 그 모든 주소에 더해진다. 예를 들면 재배치 레지스터의 값이 14000일때, 프로세스가 346번지를 액세스 할때, 실은 주 메모리의 14346번지를 액세스 하게된다.


재배치 레지스터를 이용한 동적 재배치

사용자 프로그램은 실제적인 물리 주소를 알 수 없다는 것을 주의해야 한다 . 위의 그림에서 사용자 프로그램은 346번지에 대한 포인터를 생성해서 그것에 대해 저장, 연산, 다른주소들과 비교하는등 여러가지 일을 수행 할 수 있다. 그러나 일단 그것이 주소(간접 적재 및 저장)로 갈때는 기준 레지스터에 대해 다시 바인딩 된다. 사용자 프로그램은 논리 주소를 사용한 것이고, 메모리 하드웨어는 논리 주소를 실제 주소로 바꾼것이다 . 따라서 참조된 메모리 주소의 실제 위치는 이 참조가 실제 실행시간에 결정(실행시간 바인딩)된다.

동적 적재(Dynamic Loading)

지금까지의 내용에는 프로세스가 실행되기 위해 그 프로세스 전체가 미리 메모리에 올라와 있어야 했다. 이 경우 프로세스의 크기는 메모리의 크기보다 컷서는 안된다.

메모리 공간을 보다 효율적으로 이용하기 위해선 동적 적재(Dynamic Loading) 을 해야한다.

동적 적재에서 각 루팅은 실제 호출이 되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기 하고 있다.

동적 적재는 루틴이 필요한 경우에만 적재하기 때문에 오류처리 루틴과 같이 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 유용하다.

동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libraries)

동적 연결 라이브러리(Dynamic Linking Libraries) 는 사용자 프로그램이 실행 될때, 사용자 프로그램에 연결된는 시스템 라이브러리 이다.

동적 적재에서는 로딩(loading)이 실행시까지 미루어졌겠지만, 동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것이다. 동적 연결은 주로 시스템 라이브러리에 사용된다. 만일 이 방식이 없었다면 모든 시스템 라이브러리를 부른는 프로그램들은 그들의 이진 프로그램 이미지내에 시스템 라이브러비 루틴들을 한부씩 가지고 있어야 할 것이다.

이러한 동적 연결은 라이브러리 루틴을 바꿀때 특히 유용하다. 여러 버전의 라이브러리 들이 시스템에 존재 할 수도 있기 때문에, 각 프로그램은 라이브러리의 어느 버전을 사용해야 할 것인지 판별하기 위해 이러한 버전 정보를 이용한다. 이러한 시스템을 공유 라이브러리(Shared Libraries)

동적 연결과 공유 라이브러리는 동적 적재와 달리 OS의 도움이 필요하다.

스와핑

프로세스가 실행되기 위해선 메모리에 있어야 하지만, 프로세스는 실행중에 임시로 예비 저장장치(Backup Store) 로 내보내어졌다가(Swap Out) 실행을 계속하기 위해 다시 메모리로 되돌아올(Swap In) 수 있다.

모든 프로세스의 물리주소 공간 크기의 총합이 시스템의 실제 메모리 크기보다 큰 경우에도 스와핑을 사용하면 동시에 실행 하는것이 가능하여 다중 프로그래밍의 정도를 증가시킨다.


디스크를 예비 저장장치로 사용하는 경우의 두 프로세스 스와핑

기본 스와핑(Standard Swapping)

기본 스와핑은 메인 메모리와 예비 저장장치 사이에서 프로세스를 이동시킨다.

이러한 스와핑의 경우 문맥교환 시간(Context Switch Time)이 상당히 오래 걸린다.

연속 메모리 할당

주 메모리는 OS뿐만 아니라 여러 사용자 프로세스도 수용해야 한다.

메모리는 일반적으로 두개의 부분으로 나누어지는데, 하나는 메모리에 상주하는 OS를 위한 영역과 다른 하나는 사용자 프로세스를 위한 영역이다.

보통 여러 프로세스가 동시에 메모리에 올라와 있는것이 바람직 하기 때문에, 메모리에 올라오고자 하는 Input Queue에서 대기중인 프로세스들에게 메모리를 얼마만큼씩 어떻게 할당할 것인가 라는 문제가 있다. 이러한 연속 메모리 할당(Contiguous Memory Allocation) 시스템에서는 각 프로세스는 다음 프로세스를 포함하는 영역과 연속된 하나의 메모리 영역을 차지하게 된다.

메모리 보호(Memory Protection)

프로세스가 자신이 소유하지 않은 메모리를 접근 할 수 없게 강제해야한다. 이는 시스템이 상한 레지스터 와 재배치 레지스터 를 가지고 있다면 해결할 수 있다.

재배치 레지스터 는 가장 작은 물리 주소의 값을 저장하고, 상한 레지스터 는 논리 주소의 범위 값을 저장한다. MMU는 동적으로 논리 주소에 재배치 레지스터 의 값을 더함으로써 주소를 변환하는 역할을 한다. 이렇게 변환된 주소는 메모리로 보내어 진다.


재배치와 상한 레지스터를 지원하는 하드웨어

CPU 스케쥴러가 다음으로 수행할 프로세스를 선택할때, 디스패처(dispatcher)는 문맥교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다. CPU에 의해 생성되는 모든 주소들은 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에, OS와 다른 사용자 프로그램을 현재 수행중인 사용자 프로그램의 접근으로부터 보호 할 수 있다.

메모리 할당(Memory Allocation)

가장 간단한 공간 할당 방법은 메모리를 똑같은 고정된 크기로 분할(Partition) 하는 것이다. 각 분할마다 한 프로세스를 가지고, 이때 분할의 개수를 다중 프로그래밍 정도(MultiProgramming Degree)이라고 부른다.

가변분할 기법에서의 OS는 메모리의 어떤 부분이 사용되고 있고, 어떤 부분이 사용되지 않는지 파악할 수 있는 테이블을 유지한다. 초기에 모든 메모리 공간은 한개의 큰 사용 가능한 블록으로 간주한다.

프로세스가 시스템에 들어오면, 일단 Input Queue에 넣는다. OS는 각 프로세스가 메모리를 얼마나 요구하며, 또한 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다. 프로새스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁한다. 프로세스가 끝내면 메모리를 반납하고, OS는 Input Queue에 있는 다른 프로세스로 이 공간을 채운다.

OS는 항상 놀고있는 공간들의 크기와 Input Queue를 유지해야 한다.

일반적으로 메모리에는 다양한 크기의 자유 공간이 여기저기에 산재 하게 된다. 프로세스가 공간을 필요로 할때 OS는 이 자유 공간들의 집합에서 적절한 것을 찾아 내야 한다.

일련의 자유 공간들의 리스트로부터 크기 n 바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정한는 문제를 동적 메모리 할당 문제(Dynamic Memory Allocation Problem) 이라고 한다. 이 문제를 해결하기 위한 일반적인 방법은 아래와 같이 세가지가 있다.

최초 적합(Firtst Fit)
- 첫번째 사용간능한 가용공간을 할당 한다.
- 검섹은 집합의 시작에서부터 하거나 이전 검색이 끝난곳부터 시작될 수 있다.
- 충분히 큰 가용 공간을 찾았을때 검색이 끝난다.
최적 적합(Best Fit)
- 사용가능한 공간들 중에서 가장 작은것을 선택한다.(Hole은 n보다 크면서 가장 작은 Hole을 선택)
- 리스트가 크기순으로 되어있지 않다면 모든 리스트를 검색해야 한다.
- 아주 작은 가용공간을 만들어 낸다.
최악 적합(Worst Fit)
- 가장 큰 가용공간을 선택한다.(Hole은 n보다 크면서 가장 큰 Hole을 선택)
- 할당해주고 남게 된는 자유공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다.

모의실험을 통해 연구한 결과, 최초적합과 최적적합이 시간과 메모리 이용 효율 측면에서 최악적합보다 좋단는 것이 입증되었다. 일반적으로 최초적합이 최적적합보다 속도가 더 빠르다.

단편화(Fragmentation)

동적 메모리 할당 문제에서의 최초적합, 최적적합, 최악적합 알고리즘은 외부 단편화(External Fragmentation, ‘fragment’는 공간중 일부가 사용 못하게 되는 부분) 을 발생한다.

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 어떤 자유공간은 너무 작은 조각이 되어 버린다. 외부 단편화 는 이처럼 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어있을때 발생한다. 즉, 메모리는 너무 많은 수의 매우 작은 조각들로 단편화되어 있는것이다.

외부 단편화를 해결하는 방법으로는 아래와 같은 방법이 있다.

압축(Compaction)
- 메모리의 모든 내용들을 한곳으로 몰고 모든 자유공간들을 다른 한곳으로 몰아서 큰 블록을 만든다.
- 압축은 프로세스들의 재배치가 실행 시간에 동쩍으로 이루어지는 경우에만 가능
- 재배치가 어셈블 또는 적재시에 정적으로 행해진다면 압축 실행 불가
- 메모리내의 전체 블록의 재배치가 필요하므로 비용이 많이듬
페이징과 세그먼테이션(Paging & Segmentation)
- 한 프로세스의 논리 주소 공간을 여러개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에게 할당

메모리 공간을 낭비하는 현상인 단편화는 내부적으로도 발생 할 수 있다. 이를 내부 단편화(Internal Fragmentation) 이라고 하며, 이 내부 단편화 역시 사용이 못되는 부분이다.

내부 단편화의 예로, 18,464B 크기의 자유로운 크기의 자유공간을 생각해본다. 어느 한 프로세스가 18,462B를 요구한다고 가정했을때, 요구된 블록을 정확히 할당하면 2B의 가용공간(hole)이 남는다. 이 경우 2B짜리의 가용공간을 놓치지 않기 위해 오히려 2B보다 더 큰 부담을 시스템이 가지게 될 것이다. 따라서 일반적으로는 메모리를 먼저 아주 작은 공간들로 분할하고 프로세스가 요청하면 할당을 항상 이 분할된 크기의 정수 배로만 해주는것이 보통이다. 이들 두 크기 사이의 남는 부분이 바 로 내부 단편화 이다.

세그먼테이션

사용자가 인지하는 메모리의 모습은 실제 물리 메모리의 모양과 같지 않다. 이러한 불편함을 해소하기위해, 프로그래머가 인지하는 메모리의 모습을 실제 물리 메모리의 모습을로 변환해주는 메모리 기법인 세그먼테이션 이 등장하게 된다.

기본 방법

일반적으로 프로그래머들은 메모리의 모습을 가변적인 길이를 갖지는 세그먼트의 집합 그리고 세그먼트 사이에는 어떠한 순서도 존재하지 않는 모습으로 생각하고 있다.


개발자가 생각하는 프로그램의 모습

세그먼테이션(Segmentation) 은 위와같이 프로그래머가 생가하는 모양을 그대로 지원하는 메모리 관리 기법이다.

프로그래머가 생각하는 논리주소 공간은 세그먼트들의 집합으로 이루어진다. 각 세그먼트는 이름과 길이를 가진다.

프로그램에서 사용되는 주소는 세그먼트의 이름과 세그먼트 안에서의 오프셋을 모두 명시한다. 따라서 프로그래머는 모든 주소를 세그먼트 이름과 오프셋의 두 부분 으로 나누어 명기 한다.

구분을 쉽게 하기 위해 세그먼트 이름 대신에 세그먼트 번호가 시스템에 의해 정해진다. 즉, 시스템 내부에서 세그먼트는 번호로 불려진다.

프로그램이 컴파일 될때 입력 프로그램을 반영하여 컴파일러가 자동으로 세그먼트를 생성한다. 예로 C 컴파일러는 다음과 같은 세그먼트들을 만들어 낸다.

코드
전역 변수
메모리 할당을 위한 힙(Heap)
각각의 스레드를 위한 스택(Stack)
표준 C 라이브러리

하드웨어

세그먼트 테이블(Segment Table) 의 각 항목은 세그먼트의 기준(base)과 세그먼트의 한계(limit)를 가지고 있다. 세그먼트 기준(Segment Base) 은 세그먼트의 시작주소를 나탄내며, 세그먼트 한계(Segment Limit) 는 세그먼트의 길이를 명시한다.

논리주소는 두 부분으로 구성된다. 세그먼트 번호 s 와 그 세그먼트 내에서의 변위(offset) d 로 구선성된다. 세그먼트 번호 s 는 세그먼트 테이블에 대한 색인으로 사용된다. 변위 d 는 0과 세그먼트 크기 사이의 값이어야 한다. 그렇지 않을 경우엔는 트랩(trap)을 발생시킨다. 이 변위가 범위 안에 있으면 세그먼트 기준과 변위가 더해져 원하는 바이트의 실제 주소가 얻어진다 . 즉, 세그먼트 테이블은 기본적으로 기준/한계 레지스터들의 쌍으로 이루어진 배열이다 .


세그먼테이션 하드웨어


세그먼테이션의 예

페이징

세그먼테이션은 프로세스가 적재되는 물리주소 공간이 연속적이지 않아도 적재를 허용한다. 페이징(Paging) 은 이러한 이점을 제공한는 또하나의 메모리 관리 기법이다.

페이징은 외부단편화를 방지하고 단편화에 따른 압축작업이 필요없지만 세그먼테이션은 그렇지 않다. 또한 페이징은 스왑 아웃되는 다양한 크기의 세그먼트를 예비 저장장치에 저장해야하는 심각한 문제도 해결한다.

기본방법

물리 메모리는 프레임(Frame) 이라 불리는 같은 크기의 블록으로 나누어 진다. 논리 메모리는 페이지(Page) 라 불리는 같은 크기의 블록으로 나누어 진다.

CPU에서 나오는 모든 주소는 페이지 번호(p) 와 페이지 변위(d: offset) 두개의 부분으로 나누어진다. 페이지 번호는 페이지 테이블(Page Table) 을 액세스 할 때 사용되며 페이지 테이블은 주 메모리에서 각 페이지가 점유하는 주소를 가지고 있다.


페이징 하드웨어

이러한 메모리의 페이징 모델애서, 페이지의 주소에 페이지 변위를 더하면 원하는 물리 주소가 된다.


논리 및 물리 메모리로 이루어진 페이징 모델

프레임의 크기와 같이 페이지의 크기도 하드웨어에 의해 정의된다. 페이지의 크기는 대개 컴퓨터 구조에 따라 페이지당 512B에서 16MB 사이이며 2의 제곱으로 증가한다. 만약 논리 주소 공간의 크기가 2^m 이고, 페이지가 2^n 크기라면 논리주소의 상위 m-n 비트는 페이지 번호를 나탄내고, 하위 n 비트는 페이지 변위를 나타낸다. 즉, 논리 주소는 다음과 같다.


예시


4B 페이지를 가진 32B 메모리의 페이징 예

페이징 그 자체는 동적 재배치의 한 형태이다. 모든 논리주소는 페이징 하드웨어에 의해 물리주소로 변환된다.

페이징 기법을 사용하게 되면 외부 단편화 문제는 발생하지 않지만, 내부 단편화 문제가 발생한다. 할당은 항상 프레임의 정수 배로 할당되기 때문이다. 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구 한다면, 마지막 페이지 프레임은 전부 할당되지 않는다.

이러한 내부 단편화를 어느정도 해결하기 위해 페이지의 크기를 줄이는 것이 바람직 해보이지만, 페이지의 크기가 작아진다면 그에 반비례하여 페이지 테이블의 크기가 커지게 되고 이 페이지 테이블이 차지하는 공간은 낭비된다.

일반적으로 페이지 테이블의 각 엔트리는 4B이다. 그러나 이 크기도 바뀔수 있다. 32bit 엔트리는 2^32개의 물리 페이지 프레임을 가리킬수 있다. 프레임 크기가 4KB이면 4B크기의 엔트리는 2^44개의 물리 주소를 저장할 수 있다.


기용 프레임 (a) 할당 전, (b) 할당 후

OS는 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다. 즉, 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇개나 되는지 등을 알아야 한다. 이러한 정보는 일반적으로 프레임 테이블(Frame Table) 이라는 자료구조에 있다.

OS는 사용자가 시스템콜을 하여 매개변수로 어떤 주소를 주면, 해당 주소를 정확히 찾아가야 한다. 이를 위해 OS는 각 사용자에 대해 페이지 테이블의 복사본을 유지해야 한다.

하드웨어 지원

몇몇 OS는 각 프로세스마다 하나의 페이지 테이블을 할당한다. 페이지 테이블을 가리키는 포인터는 프로세스의 다른 레지스터 값과 함께 프로세스 제어 블록(PCB)에 저장된다.

페이지 테이블에 레지슽터를 사용하는 것은 페이지 테이블의 크기가 작을 경우에는 적합하지만, 대부분의 시스템에서 페이지 테이블이 1백만 항목에 이를만큼 크기가 매우 크다. 즉, 레지스터를 사용하기엔 부적절하다. 이를 해결하기 위해 대부분의 시스템은 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page Table Base Register) 로 하여금 페이지 테이블을 가리키도록 한다.

그런나 PTBR 방식의 문제점은 메모리 접근 시간이다. i번지에 있는 정보를 액세스하기 위해서 두번의 메모리 접근이 필요하다(페이지 테이블을 위해서 한번, 그 메모리 자체를 위해서 한번). 그래서 메모리 접근은 두 배 로 느려지게 된다.

이러한 문젱에 대한 해결에는 TLB(Translation Lock-aside Buffers) 라고 불리는 특수한 소형 하드웨어 캐시가 사용된다. TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다.

TLB는 페이지 테이블의 일부분만 저장하며 TLB내의 각 항목은 키(key)와 값(value)의 두부분으로 구성된다. TLB에 페이지를 찾아달라고 요청이 들어오면, 이 찾고자 하는 페이지를 동시에 여러 개의 내부 키(페이지 번호)와 비교하여 페이지 번호가 같은 것이 발견되면 그에 대응하는 프레임 번호를 전달한다.

만약 페이지 번호가 TLB내에서 찾아지지 않을때, 이러한 경우를 TLB miss 라고 한다. TLB miss가 일어나게 되면, 페이지 테이블에 접근하기 위한 메모리 참조가 일어난다. 이 참조는 CPU의 종류에 따라 하드웨어서 자동적으로 이루어 지거나 OS에게 인터럽트를 걸어 수행된다. 프레임 번호가 얻어지면, 메모리 접근을 위해 사용된다. 또한 새로운 페이지 번호와 프레임 번호를 TLB에 추가하여 다음 참조시 사용되도록 한다. 만약 TLB가 가득 차게되면, 기존 항목중에서 교체할 항목을 선택하여야 한다. 교체 정책은 LRU부터 라운드로빈, 무작위등 다양한 정책이 사용된다. 몇몇 TLB는 특정 항목들을 TLB에 고정시키는데, 이러한 항목들은 TLB에서 제거될 수 없다. 보통 주요 커넣코드를 TLB에 고정시킨다.


TLB가 장착된 페이징 하드웨어

접근하는 메모리의 페이지 번호가 TLB에서 발견되는 비율을 적중률(Hit Ratio) 라고 한다.

보호

페이지화된 환경에서 메모리 보호는 각 페이지에 붙어있는 보호 비트(Protection Bit) 에 의해 구현되다. 이 비트들은 보통 페이지 테이블에 속해 있다.

각 비트는 이 페이지가 읽고-쓰기 또는 읽기전용임을 각각 정의할 수 있다.

페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid) 라는 하나의 비트가 더 있다. 이 비트가 유효(valid) 로 성정되면 관련된 페이직가 프로세스의 합법적인 페이지임을 나타내며, 무효(invalid) 로 설정되면 그 페이진는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.


페이지 테이블에서 유효(v)/뮤효(i) 비트

몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(Page Tabe Length Register)) 라는 레지스터를 제공한다.

공유 페이지(Shared Pages)

페이징의 또 다른 장점은 코드를 쉽게 공유 할 수 있다는 것이다.


페이징 환경에서의 코드 공유

페이지 테이블 구조

계층적 페이징(Hierarchical Paging)

페이지 테이블의 구성으로써 한가지 방법은 2단계 페이징 기법(two level paging scheme) 으로서 페이지 테이블 자체가 다시 페이지화 되는 것이다.


2단계 페이지 테이블 기법


2단계 32비트 페이징 구조에서의 주소 변환


예

위 그림에서 P1은 바깥 페이지 테이블의 인덱스이고, P2는 안쪽 페이지 테이블의 페이지 내의 변위이다.

해시 페이지 테이블(Hashed Page Tables)

주소공간이 32비트보다 커지면 가상주소를 해시로 사용하는 해시 페이지 테이블 을 많이 사용한다.


해시 페이지 테이블

64비트 시스템에서 유용하도록 변형된 해시 테이블 기법이 제안되었다. 이 변형 기법은 해시 테이블과 비슷한 클러스터 페이지 테이블 을 사용한다. 해시 테이블의 각 항목들이 한 개의 페이지만 가리키는 것에 반해 클러스터 페이지 테이블의 각 항목들은 여러 페이지를 가리킨다.

역 페이지 테이블(Inverted Page Tables)

보통 프로세스는 각자 하나씩 페이지 테이블을 가지고 또 페이지 테이블은 프로세스가 사용하는 각 페이지마다 하나의 항목을 가진다. 이러한 기법의 단점중 하나는 페이지 테이블의 크기이다.

이 문제를 해결하는 한 방법은 역 페이지 테이블(Inverted Page Table) 이다. 역 페이지 테이블에서는 메모리 프레임마다 한 항목씩을 할당하다. 각 항목은 그 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스의 ID를 표시하고 있다. 이렇게 되면 시스템에서는 단 하나의 페이지 테이블만 존재하게 되고, 테이블 내 각 항목은 메모리 한 프레임씩을 가맄키게 된다.

그러나 역 페이지 테이블의 단점으로는 일치하는 값을 찾을때 때까지 찾으므로 오랜 탐색시간을 가질수 있다.


역 페이지 테이블

OS - 메모리 관리 전략