Main Memory

2023-12-17

memory

Background

많은 프로세스를 메모리에 유지하기 위해서는 메모리를 공유해야 한다. 원시적인 HW 부터 paging 전략까지 전반적으로 메모리 관리 기법을 알아볼 것이다.

메모리 관리 기법은 특히 시스템의 하드웨어 설계에 따라 달라진다. 대부분의 메모리 관리 알고리즘은 하드웨어의 지원이 필요하고, 시스템이 하드웨어와 OS의 메모리 관리와 밀접하게 통합해야 한다.

Basic Hardware

물리적 메모리의 상대적 접근 속도 뿐만 아니라 정확한 동작을 보장해야 한다. 유저 프로세스로부터 OS를 보호하고, 유저 프로세스 간 보호도 필요하다. 보통 OS는 속도를 위해 CPU와 메모리 접근 간에 개입하지 않기 때문에 이 보호는 하드웨어에 의해 제공될 수 있다.

프로세스별 독립 메모리 공간을 보장하고, 프로세스 간 메모리 접근을 보호해야 하며, 이는 병행 실행을 위해 여러 프로세스를 메모리에 적재하기 위한 기반이 된다.

메모리 공간을 나누기 위해서는, 특정 프로세스가 접근 가능한 메모리의 범위를 설정하고, 프로세스가 오직 접근 가능한 범위에만 접근하도록 해야 한다.

접근 가능한 메모리 범위에 대한 보호는 다음 두 레지스터로 제공된다.

Base register
- Base 레지스터는 접근 가능한 메모리 공간의 가장 작은 주소를 hold한다.
Limit register
- Limit 레지스터는 범위의 크기를 지정한다.

Base 레지스터가 300040이고, Limit 레지스터가 120900이라면, 300040 ~ 420940 (300040 + 120900)이 접근 가능한 범위가 된다.

메모리 보호를 위해 CPU 하드웨어가 유저 모드에서 생성된 모든 주소 값을 비교한다. 유저 모드에서 실행 중인 프로그램이 OS 메모리나 다른 유저 메모리의 접근한다면 OS에 trap이 발생하고, fatal error로 간주한다.

이 방법으로 유저 프로그램이 우연히나 고의로 다른 사용자나 OS의 코드나 자료 구조를 변경하는 것을 막는다. Base와 limit 레지스터 값은 오직 OS만 특권 명령을 통해 변경할 수 있다.

특권 명령은 항상 커널 모드에서 실행되고, OS만 커널 모드에서 실행되므로 OS만 base와 limit 레지스터를 로드하는 것을 보장한다.

Address Binding

대부분의 시스템은 유저 프로세스가 물리 메모리 어느 부분에든 적재할 수 있게 허용한다. 컴퓨터의 주소 공간이 00000에서 시작한다고 유저 프로세스의 시작 주소가 00000일 필요는 없다.

유저 프로그램은 실행되기 전 여러 단계를 거치며, 메모리 주소는 각 단계에서 다르게 표현된다. 컴파일러는 symbolic 주소를 relocatable 주소에 바인딩하고, 링커와 로더는 relocatable 주소를 실제 주소에 바인딩한다.

바인딩은 아래 세 단계에 이루어진다.

Compile time
- 만일 컴파일 타임에 프로세스의 메모리 위치를 알 수 있다면 절대 코드를 생성할 수 있다.
- R부터 시작하는 프로세스라고 한다면 R부터 주소를 확장해간다.
- 하지만 언젠가 시작 위치가 변경된다면 다시 컴파일해야 한다.
Load time
- 컴파일 타임에 프로세스의 메모리 위치를 모른다면 컴파일러는 재배치 가능한 코드를 생성하고, 최종 바인딩은 로드 타임에 일어난다.
- 만약 시작 주소가 변경되어도 다시 컴파일 할 필요 없이 로드만 하면 된다.
Execution time
- 만약 실행 중에 메모리 위치가 바뀔 수 있다면 바인딩은 런타임까지 늦춰진다.
- 이때 주소 맵핑을 위해 MMU라는 특수한 소프트웨어가 사용된다.
- 대부분의 OS가 이 방법을 사용한다.

Logical vs Physical Address Space

Logical Address
- CPU에서 생성된 주소다.
- 프로그램에서 생성된 모든 논리적 주소의 집합이다.
Physical Address
- 메모리 유닛에 보여지는 실제 메모리 주소다.
- 메모리 주소 레지스터에 로드된다.
- 논리적 주소에 대응하는 모든 물리적 주소의 집합이다.

컴파일 타임이나 로드 타임에 주소를 바인딩하면 논리 주소와 물리 주소가 동일하다. 반면 실행 타임에 주소를 바인딩하면 논리주소와 물리 주소가 다르다. 보통 논리 주소를 가상 주소라고 일컫는다.

런타임에 가상 주소-물리 주소로 맵핑은 Memory-Management Unit (MMU)라는 하드웨어 장치를 통해 수행된다.

일반화 한 동작은 다음과 같으며, 맵핑을 위해 다양한 방법을 사용할 수 있다.

CPU가 논리 주소를 MMU에 전달한다.
MMU가 논리 주소를 물리 주소에 맵핑한다.

Base 레지스터 기법을 일반화 한 단순 MMU 기법을 통해 표현해보자.

Base 레지스터는 이제 Relocation register로 불린다. 주소가 MMU를 거쳐 메모리를 보내질 때 유저 프로세스가 생성한 주소에 relocation 레지스터의 값이 더해진다.

만약 base 값이 14000일 때 유저가 주소 0과 346에 접근했다면, 0과 346은 동적으로 맵핑되어 14000, 14346이 된다.

이때 두 유형의 주소가 사용된다.

논리주소
- 0 ~ MAX 범위 사이의 주소
물리주소
- R + 0 ~ R + MAX 범위 사이의 주소

유저 프로그램은 실제 물리 주소에 접근하지 않는다. 오직 논리 주소를 만들고 0 ~ MAX 범위의 주소에서 실행된다는 것만 안다. 논리 주소는 사용되기 전에 물리 주소로 변환되어야 하고, 이는 Memory Mapping Hardware의 역할이다.

별도의 물리 주소 공간에 논리 주소가 바인딩 되는 개념이 적절한 메모리 관리의 핵심이다.

Dynamic Loading

앞서 논의했듯이, 프로세스가 실행되려면 전체 프로그램과 데이터가 물리 메모리에 있어야 한다. 따라서 프로세스의 크기가 물리 메모리의 크기에 의해 제한되었다. 이를 해결하고 메모리 이용률을 높이기 위해 동적 로딩을 활용할 수 있다.

동적 로딩을 사용하면, 루틴은 호출되기 전에 로드되지 않는다. 모든 루틴은 relocatable load 포맷으로 디스크에 존재한다. 메인 프로그램은 메모리에 로드되어 실행된다. 만약 루틴이 또다른 루틴을 호출해야 하면 호출하는 루틴은 먼저 다른 루틴이 로드되었는지 확인한다. 아직 로드되지 않았다면 relocatable linking loader가 해당 루틴을 메모리에 로드하고, 이 변경을 반영하기 위해 프로그램의 주소 테이블을 갱신한다.

동적 로딩이 장점은 루틴이 필요할 때만 적재할 수 있다는 점이다. 많은 양의 코드가 있지만 자주 사용되지 않는 경우 유용하다. 이로 인해 전체 프로그램 크기는 크지만 메모리를 사용하는 부분은 작아진다.

동적 로딩은 OS의 특별한 지원이 요구되지 않는다. 유저가 동적 로딩 사용 시 프로그램 설계에 대한 책임을 지고, OS는 동적 로딩을 위한 라이브러리 루틴을 제공한다.

Dynamic Linking and Shared Libraries

Dynamically linked libraries (DLL)은 유저 프로그램이 실행될 때 유저 프로그램에 연결되는 시스템 라이브러리다. Dynamic linking도 실행 시점까지 지연된다. Static linking만을 지원하는 OS도 있다. 이럴 때는 시스템 라이브러리가 다른 모듈처럼 로더에 의해 이진 프로그램 이미지로 결합된다.

DLL은 주로 표준 C언어 라이브러리와 같이 시스템 라이브러리에 적용되는데, DLL을 적용하면 각 프로그램은 실행 가능한 이미지에 라이브러리의 복사본을 포함하지 않아도 된다. 실행 가능한 이미지의 크기를 줄이고, 메인 메모리 낭비를 줄일 수 있다.

또한 DLL은 공유 가능하므로 메모리에 하나의 인스턴스만 있으면 된다. 이러한 특징 때문에 DLL은 공유 라이브러리라고도 알려져 있다.

공유를 해야 하기 때문에 동적 로딩과 달리 DLL은 OS의 도움이 필요하다. 메모리 내 프로세스가 다른 프로세스로부터 보호된다면 이를 확인할 수 있는 것은 OS 밖에 없다. OS는 필요한 루틴이 다른 프로세스의 메모리 공간에 있는지, 아니면 여러 프로세스가 같은 메모리 공간을 접근하도록 허용하는지 확인한다. DLL이 어떻게 공유되는지에 대해서는 paging을 다루며 확인할 것이다.

Continguous Memory Allocation

메인 메모리는 OS를 포함해 다양한 유저 프로세스를 저장해야 한다. 메인 메모리에는 최대한 효율적인 방법으로 메모리를 할당해야 한다. 이 섹션에서는 연속적인 메모리 할당에 대해 알아본다. 이 방법에서 각 프로세스는 하나의 메모리 영역에 저장되는데, 이 영역은 다음 프로세스가 저장된 영역과 인접한 영역이다. 이 방법에 대해 더 구체적으로 살펴보기 전에 메모리 보호에 대해 이야기해보자.

Memory Protection

이전에 살펴본 두 가지 방법을 결합하여 프로세스가 소유하지 않은 메모리에 접근하는 것을 방지할 수 있다. Relocation 레지스터와 limit 레지스터를 사용함으로써 목적을 달성할 수 있다.

각 논리 주소는 limit 레지스터에 지정된 범위 내에 있어야 한다. MMU는 논리 주소에 relocation 레지스터의 값을 동적으로 더해 맵핑하고, 이 주소가 메모리에 전송된다.

스케줄러가 프로세스를 실행하기 위해 선택하면, context switching의 일환으로 dispatcher가 relocation 레지스터와 limit 레지스터를 적재한다. CPU에서 생성된 모든 주소가 레지스터의 값과 비교되므로 실행 중인 프로세스로부터 OS와 다른 사용자 프로그램과 그 데이터를 보호한다.

Memory Allocation

메모리를 할당하는 가장 간단한 방법은 가변 크기 파티션에 할당하는 것이다. 이때 각 파티션은 정확히 하나의 프로세스를 포함한다. 처음에는 모든 메모리가 가용하고, 마치 구멍이 뚫려있는 것 같이 하나의 큰 메모리 블록으로 간주된다. 최종적으로 메모리는 가변 크기 구멍의 집합을 포함한다. OS는 이 영역 중 어떤 것이 가용하고, 어떤 것이 사용 중인지 테이블에 유지한다.

프로세스가 시스템에 진입하면, OS는 각 프로세스의 메모리 요구와 가용한 메모리 공간을 고려하여 메모리를 할당한다. 프로세스는 공간을 할당 받으면 메모리에 적재되고, CPU 시간 경쟁에 참여할 수 있다. 프로세스가 종료되면 프로세스는 메모리를 반납하고, OS는 다른 프로세스에 메모리를 할당한다.

만약 메모리가 불충분하다면 어떻게 될까?

프로세스를 거부하고, 적절한 에러 메시지를 제공한다.
프로세스가 wait 큐에서 대기하도록 한다.
추후 메모리 다른 프로세스의 반납 시 OS는 대기 중인 프로세스의 메모리 요구를 충족시킬 수 있는지 검사한다.

가용한 메모리 블록은 메모리에 흩어진 가변 크기 구멍의 집합으로 구성된다. 프로세스가 메모리를 요구하면 시스템은 구멍의 집합에서 프로세스에게 맞는 충분히 큰 구멍을 찾는다. 만약 구멍이 너무 크면 구멍은 두 부분으로 나뉜다. 하나는 도착한 프로세스에게 할당하는 부분. 다른 하나는 구멍의 집합에 귀속되는 부분.

프로세스가 종료되고 메모리 블록이 해제되면 해당 메모리는 구멍의 집합으로 귀속된다. 만약 새로운 구멍이 다른 구멍과 인접하다면 인접한 구멍은 하나의 큰 구멍으로 병합된다.

Dynamic storage allocation problem

문제는 가용한 구멍의 집합에서 크기가 n인 메모리 요청을 어떻게 만족시킬 것인가이다. 이 문제는 다음 세 접근으로 해결할 수 있다.

First fit
- 구멍 중 충분히 큰 첫 구멍을 선택해 메모리를 할당한다.
- 충분히 큰 구멍을 찾으면 바로 탐색을 중단한다.
Best fit
- 충분히 큰 구멍 중 가장 작은 구멍을 선택해 메모리를 할당한다.
- 크기 순으로 정렬되어있지 않으면 전체 리스트를 탐색해야 한다.
- 이 전략을 사용하면 애매한 크기의 구멍이 여러 개 생길 수 있다.
Worst fit
- 가장 큰 구멍을 선택해 메모리를 할당한다.
- 마찬가지로 크기 순으로 정렬되어있지 않으면 전체 리스트를 탐색해야 한다.
- 이 전략을 사용하면 메모리를 할당하고도 최대한 큰 구멍들을 남길 수 있다.

세 방법 중 first fit과 best fit이 스토리지 이용률 측면에서 worst fit보다 낫다. 하지만 first fit과 best fit 간 스토리지 이용률은 어느 것이 더 낫다고 하기 어렵다. 하지만 보통 first fit이 best fit보다 빠르다.

Fragmentation

프로세스가 적재되고 해제되는 과정에서 가용한 메모리 공간이 작은 조각들로 나눠지는 것을 fragmentation(단편화)라고 한다. 단편화는 외부 단편화와 내부 단편화로 나뉜다.

External Fragmentation (외부 단편화)

전체적으로는 충분한 메모리 공간이 있지만 가용 공간이 연속적이지 않은 경우 외부 단편화가 존재한다. 메모리는 많은 구멍으로 단편화된 상태다. First fit과 best fit 전략 모두 이러한 외부 단편화 문제를 겪으며, 최악의 경우 모든 두 프로세스 사이에 버려지는 메모리 블록이 위치하게 된다. 만약 모든 작은 구멍이 하나의 큰 구멍으로 합쳐질 수 있다면 여러 프로세스를 실행할 수 있을 것이다.

외부 단편화에 영향을 주는 요소는 다음과 같다.

First fit 혹은 best fit 전략 사용여부
가용한 메모리 블록이 할당되는 부분 (처음 or 끝 부분)

어떤 알고리즘을 선택하던 상관없이 외부 단편화 문제는 발생한다. 하지만 전체 메모리 양과 평균 프로세스 크기에 따라 단편화는 큰 문제일 수도 아닐 수도 있다. 통계적으로 first fit 전략을 사용했을 때 N개의 할당 블록에 대해 0.5N개의 블록이 단편화로 사용이 불가하며, 이를 50 퍼센트 법칙이라 한다.

외부 단편화를 해결하기 위해 다음과 같은 방법을 사용할 수 있다.

Compaction (압축)
- 여러 가용 메모리를 모아 하나의 큰 블록을 만든다.
- 압축은 항상 가능하지 않고, 재배치가 동적이며 실행 시간에 이루어지는 경우 가능하다.
- 재배치 시 프로그램과 데이터를 옯기고 새 주소를 위해 base 레지스터 값을 변경하면 된다.
- 가장 단순한 방법은 모든 프로세스를 한쪽 끝으로 이동시키는 것이다. 하지만 이 방법은 비용효율적이지 않다.
프로세스의 논리 주소가 비연속적이어도 허용
- 프로세스가 하나의 큰 범위가 아닌 여러 비연속적인 범위에 흩어져 있는 메모리를 사용하도록 허용한다.
- 메모리가 가용하다면 물리 메모리에 할당되도록 한다. 이 전략은 paging에서 사용되며, 컴퓨터 시스템의 가장 일반적인 메모리 관리 기법이다.

Internal Fragmentation (내부 단편화)

메모리 단편화는 내, 외부 모두에서 발생한다. 프로세스에 할당되는 메모리는 가용한 메모리보다 클 수 있다.

예시로 구멍의 크기가 18,464 바이트인데, 프로세스는 18,462 바이트를 요청했다. 프로세스를 메모리에 할당해도 2바이트가 남게되며, 이렇게 파티션 내부에 사용되지 않은 메모리가 남는 상황을 내부 단편화라고 한다. 보통 구멍 자체보다, 구멍의 상태를 지속적으로 추적하는 것이 더 큰 오버헤드가 된다.

이 문제를 해결하기 위한 일반적인 방법은, 물리 메모리를 고정 크기 블록으로 나누고, 블록 크기 단위(보통 4k ~ 8k)로 메모리를 할당하는 것이다.

Paging

지금까지는 물리 주소 공간이 연속적이어야 하는 경우를 주로 다루었다. 앞으로 다룰 Paging을 활용하면 프로세스의 물리 주소 공간이 연속적이지 않아도 메모리를 관리할 수 있다. 또한 연속적인 메모리 할당의 문제인 외부 단편화와 압축의 필요성을 피할 수 있다. Paging은 OS와 하드웨어 간 협력을 통해 구현되며, 유사한 형태의 기법이 큰 서버부터 모바일 장치까지 대부분의 OS에서 사용된다.

Basic Method

Paging의 구현은 물리 메모리를 frame이라는 고정 크기 블록과, 논리 메모리를 frame과 동일한 크기로 나눈 page라는 블록이 사용된다. 프로세스가 실행되면 프로세스의 page는 원 소스에서 가용한 메모리 frame으로 적재된다. 보조저장장치는 frame 또는 frame들의 클러스터와 같은 크기의 고정 블록으로 나뉜다.

이 방법으로 논리 주소 공간과 물리 주소 공간을 완전히 분리할 수 있고, 물리 메모리보다 훨씬 큰 프로그램을 메모리에 적재할 수 있다.

Paging 기법은 논리 메모리와 이를 맵핑한 Page table, 그리고 물리 메모리로 구성된다. Page table은 프로세스별 한 개씩 존재하며, 각 프레임의 시작 주소를 저장한다.

CPU에서 생성된 모든 주소는 두 부분으로 나뉜다.

Page number (p)
- Page table의 index로 활용된다.
Page offset (d)
- Frame 내 위치다.

MMU는 다음 과정을 거쳐 CPU에서 생성된 논리 주소를 물리 주소로 변환한다.

Page numger p를 추출해 page table의 index로 사용한다.
Page table에서 p에 대응되는 frame number f를 추출한다.
Page number p를 frame number f로 갈아치운다.
- |p|d| -> |f|d|

Page의 크기는 하드웨어에 의해 결정된다. 또한 그 크기는 2의 거듭제곱이며, 보통 4KB(2^12) ~ 1GB(2^30)이다. Page 크기를 2의 거듭제곱으로 정하면 논리 주소를 페이지 번호와 offset으로 쉽게 변환할 수 있다.

논리 주소 공간이 2^m이이고, 페이지 크기가 2^n이다. 논리 주소는 다음과 같다.

m-n bit: 페이지 번호 (페이지 수 만큼) n bit: 페이지 offset (페이지 크기 만큼)

만약 논리 주소 공간 m이 2^15이고 페이지 크기가 2^12라면, 페이지 수는 m-n 2^3 = 8개이고, 페이지 크기는 2^12 = 4KB이다.

Paging을 활용하면 외부 단편화 문제를 해결할 수 있다. 하지만 내부 단편화는 여전히 존재할 수 있다. Frame 단위로 할당되기 때문에 메모리 요구가 페이지 경계에 맞지 않으면 마지막 frame이 남게 된다.

만약 프로세스가 72,766 바이트를 요구하는데, page 크기는 2,048 바이트라면?

2,048 * 35 = 71,680
72,766 = 71,680 + 1,086 (한 개의 page 추가)
2,048 - 1,086 = 962 (내부 단편화 된 메모리 크기)

962 바이트의 공간이 남게 된다. 만약 n개의 page보다 1바이트 많은 메모리를 프로세스가 요청했다면? 마지막 frame의 대부분이 내부 단편화 된다.

만약 프로세스 크기가 page 크기와 독립적이라면 평균적으로 50%의 내부 단편화가 발생한다. 작은 page 크기를 적용해볼 수 있으나, 작은 page 크기 -> 많은 page 수 -> page table 크기 증가로 연결되어 오버헤드가 발생한다.

아래 명령어로 컴퓨터의 page 크기를 확인할 수 있다. 필자의 컴퓨터의 경우 16KB를 사용하고 있다.

$ getconf PAGESIZE

32-bit CPU에서, 32-bit entry는 2^32 개의 물리 frame을 표현할 수 있다. Frame 크기가 4KB(2^12)이고, 4byte entry (2^32)라면,

frame 크기 (2^12) * frame 수 (2^32) = 물리 메모리 크기 (2^44)

총 16TB의 물리 메모리를 사용할 수 있다.

paged memory system에서 물리 메모리의 크기는 프로세스의 최대 논리적 크기와 다르다. 물리 메모리의 크기가 더 작아도 된다.

또 page table entry에 추가로 유지해야 하는 정보의 경우 추가 정보를 저장하기 위한 bit를 할당한다. 이때문에 page frame을 지정하기 위한 bit 수가 적어진다. 따라서 32-bit page-table entry를 사용하는 시스템은 가능한 최대 크기보다 작은 물리 주소를 지정한다.

실행되어야 하는 프로세스가 시스템에 도착하면 page 단위로 그 크기를 확인한다. Page와 frame이 1:1 대응되기 때문에 프로세스가 n개의 page를 요구하면, n개의 frame이 가용한지 확인한다. 가용하다면 프로세스에 n개의 frame이 할당된다. Page가 할당된 frame에 로드되고, frame의 번호가 page table에 기록된다.

프로그래머의 관점에서 메모리와 실제 물리 메모리는 완전히 분리되고, 프로그래머는 메모리를 이 프로그램만을 실행하는 하나의 독립 공간으로 본다. 하지만 실제로는 프로그램이 메모리 전역에 흩어져있고, 다른 프로그램과 함께 저장된다. 프로그래머 관점에서의 메모리 주소와 실제 물리 메모리 주소 간 차이는 address-translation hardware에 의해 조정된다. 논리-물리 주소 변환은 프로그래머에게 감춰지고, OS가 제어한다.

사용자 프로세스는 자신이 소유하지 않은 메모리에는 접근할 수 없다. Page table 외 메모리는 접근할 수 없고, page table은 오직 프로세스가 소유한 page만 저장하기 때문이다.

OS가 물리 메모리를 관리하기 때문에 OS는 물리 메모리 할당 정보를 알아야 한다. frame 할당 및 가용 정보와 얼마나 많은 frame이 있는지 등 frame 정보를 알아야 한다. 이 정보는 frame table에 저장된다. 프로세스별로 존재하는 page table과 달리 frame table은 시스템 전체에서 하나만 존재한다. 물리 frame 당 하나의 entry를 갖고, frame의 할당 여부와 할당되었다면 어느 프로세스의 어느 page인지를 나타낸다.

Hardware Supports

Page table은 프로세스별 정보이기 때문에 page table과 다른 레지스터 값에 대한 포인터는 PCB에 저장된다. CPU 스케줄러가 실행할 프로세스를 선택하면 유저 레지스터와 저장된 하드웨어 page table 값을 저장된 유저 page table에서 로드한다.

Hardware implementation of the page table

Page table의 하드웨어적 구현은 전용의 고속 하드웨어 레지스터 집합을 이용한다. 큰 page table의 경우 메모리에 저장한다.

고속 하드웨어 레지스터 집합
- Page 주소 변환이 효율적으로 이루어진다.
- Context switch 시 각 레지스터가 교체되어야 하기 때문에 context switching 시간이 늘어난다.
- Page table이 작은 경우 유용하다.
더 큰 page table
- 현대 CPU는 더 큰 page table을 지원한다.
- Page table은 메인 메모리에 저장된다. Page-table base register (PTBR)에 page table에 대한 포인터를 저장한다.
- Page table 교체 시 PTBR의 값만 바꾸면 되기 때문에 context switch 시간이 감소한다.

Translation Look-Aside Buffer (TLB)

Page table을 메인 메모리에 저장하면 context switch 시간을 줄일 수 있지만, 메모리 접근 시간을 느리게 할 수 있다.

메모리 내 위치 i에 접근한다고 하자.

먼저 i에 대한 page 번호로 PTBR offset 값을 이용하여 page table에서 indexing 한다. (첫 번째 메모리 접근)
처음 접근을 통해 구해진 frame 번호와 page offset을 결합하여 실제 주소를 생성한다.
실제 주소에 접근한다. (두 번째 메모리 접근)

위 예시처럼 필요한 데이터에 접근하기 위해서는 page table에 먼저 접근하고, 그 다음 필요한 데이터에 접근해 총 두 번의 메모리 접근이 필요하다. 즉 데이터에 접근하는 시간이 2배가 된다.

이를 해결하기 위해 작고, 빠른 검색이 가능한 특수 하드웨어 캐시인 Translation look-aside buffer (TLB)를 사용한다. TLB는 고속의 연관 메모리다. TLB의 각 entry는 key(tag)와 value로 이루어져있다. Key에 상응하는 item 발견 시 value를 반환한다. Item 검색 시 모든 key와 동시에 비교한다.

TLB lookup은 빠르다. 명령어 파이프라인의 일환이기 때문에 성능 저하가 없다. 단 파이프라인 단계 내에 검색하기 위해서 TLB는 작게(32 ~ 1024 entry) 유지되어야 한다.

CPU가 생성한 논리 주소에 대해 TLB와 page table은 다음과 같이 사용된다.

MMU가 CPU가 생성한 논리 주소의 page 번호가 TLB 캐시에 있는지 확인한다.
만약 page 번호(key)가 TLB 캐시에 있다면 (TLB Hit) frame 번호(value)를 반환한다.
TLB 캐시에 없다면 (TLB miss) page table을 확인하고, 다음 참조를 위해 page 번호와 frame 번호를 TLB 캐시에 추가한다.
메모리에 접근한다.

TLB의 entry가 꽉 찼다면 기존 entry와 교체해주어야 한다. 접근한 지 오래된 순으로 entry를 교체해주는 least recently used(LRU) 알고리즘을 사용한다.

어떤 TLB는 특정 entry를 TLB에 고정하여 교체되지 않도록 한다. 핵심 커널 코드가 그 대상이다.

TLB가 별도의 ASID를 지원하지 않으면 context switch 등으로 새 page table이 선택될 때 새 프로세스가 잘못된 변환 정보를 사용하지 않도록 TLB도 비워주어야 한다.

Address-Space identifier (ASID)를 TLB entry에 저장해 각 프로세스를 식별하여 프로세스의 주소 공간을 보호한다. 이를 통해 해당 TLB 항목이 어느 프로세스에 속하는지 식별 가능하며, TLB가 가상 page 번호를 알아낼 때 현재 실행 중인 프로세스의 ASID와 가상 page에 연관된 ASID가 동일함을 보장한다. 만약 ASID가 다르면 TLB miss로 처리된다.

Hit ratio는 TLB에서 원하는 page 번호가 발견되는 비율이다.

메모리에 접근하는 시간이 10ns 만큼 걸린다고 가정하자. TLB Hit이 성공하면 10ns 만에 데이터에 접근하고, TLB가 miss 된다면 10ns + 10ns = 20ns 만에 데이터에 접근한다.

Effective memory-Access time (EAT)는 hit와 miss에 대한 상대적인 확률을 고려한 평균 접근 시간이다.

0.80 * 10 + 0.20 * 20 = 12ns. 10 -> 12로 20%만큼 느려짐
0.99 * 10 + 0.01 * 20 = 10.1ns. 10 -> 10.1로 1%만큼 느려짐

Protection

Paging을 사용하는 환경에서의 메모리 보호는 각 frame에 연관된 protection bit에 의해 이루어진다. 비트는 read-write, read-only, valid-invalid bit가 있다. 보통 보호 bit는 page table에 저장된다.

read-write, read-only bit
- 모든 메모리 참조는 page table을 통해 frame 번호를 찾는다.
- 물리 주소 계산과 동시에 read-only page에 write가 이루어지지 않는지 알기 위해 protection bit를 확인한다.
- read-only page에 쓰려는 시도는 OS에 hardware trap을 유발한다.
valid-invalid bit
- Page table의 각 entry에 bit가 추가되는데, 이 bit는 OS가 설정한다.
- 이 bit는 page에 대한 접근을 허용할 지 결정하는 bit다.
- 만약 이 bit가 valid면, 연관 page는 프로세스의 논리 주소 공간에 있고, 합법적인 page다.
- 이 bit가 invalid면, page가 프로세스의 논리 주소 공간에 없다는 뜻이다.

14-bit 주소 공간을 가진 시스템이 있다. 2^14: 0 ~ 16,383. Page 크기는 2KB (2048 = 2^11)이다. 프로그램의 주소는 0 ~ 10,468 까지라 page 0 ~ 5가 맵핑된다. 이때 10,468 ~ 12,287 까지는 내부 단편화된 공간이다. 이 프로세스가 page 6이나 7의 주소에 접근할 수 없도록 page table의 6, 7 entry는 valid-invalid bit가 invalid로 표시된다.

Page-table length register (PTLR)

PTLR은 page table의 크기를 나타내는 하드웨어다. 논리 주소가 프로세스의 유효 범위 내에 있는지 검사하기 위해 PTLR 값과 모든 논리 주소를 비교한다. 실패 시 OS에 error trap이 발생한다. 정상적인 범위라면 모든 page 번호 p가 PTLR보다 작거나 같아야 한다.

Shared Pages

Paging의 장점은 공통 코드를 공유할 수 있다는 것이며, 이는 여러 프로세스가 있는 환경에서 특히 중요한 고려 사항이다.

예시로, Linux 시스템에서 대부분의 사용자 프로세스는 libc 라이브러리를 필요로 한다. 이를 위해서

각 프로세스가 libc의 사본을 주소 공간으로 로드한다.
- 40개의 유저 프로세스가 각각 2MB의 라이브러리를 로드하면 80MB의 메모리가 필요하다.
만약 코드가 재진입 가능한(reentrant) 코드면 공유한다.
- Reentrant 코드란 스스로 수정되지 않는 코드를 뜻한다. 실행되는 동안 변경되지 않아서 동시 공유가 가능하다.
- 따라서 여러 프로세스가 한 코드를 동시에 실행할 수 있다.
- 아무리 많은 프로세스가 2MB의 라이브러리를 사용해도 오직 2MB의 메모리만 있으면 된다.

Structure of the Page Table

다음으로 page table을 구조화하는 기법에 대해 살펴보자. 기법 세 가지는 다음과 같다.

Hierachical paging
Hashed page tables
Inverted page table

1) Hierachical paging

대부분 현대 컴퓨터 시스템은 큰 논리 주소 공간을 허용한다. 2^32 (4GB) ~ 2^64 (16EB) 정도의 논리 주소 공간을 허용하기 때문에 page table의 크기 자체도 커진다.

32-bit 논리 주소 공간을 가진 시스템이 있다. 총 주소 공간은 2^32로 4GB이고, Page 크기는 2^12로 4KB 이기 때문에, page table은 전체 논리 주소 공간 / Page 크기가 적용되어 2^20 (백만개 이상)의 entry를 가진다.

만약 각 entry가 4바이트라면, 각 프로세스는 page table만을 위해 최대 4MB를 할애해야 한다. (2^20 * 2^2 - 2^22 (4MB))

Page table이 비대해지는 문제를 해결하기 위해서는 page table을 작은 조각으로 분할하는 방법이 있다.

Two-level paging algorithm

Two-level paging에서는 page table 차제도 paging된다.

32-bit의 논리 주소 공간이 있다. Page 크기는 4KB로 2^12다. One-level paging에서는 32 - 12 = 20으로 2^20의 page entry가 필요했다면. Two-level에서는 2^10의 page 번호 영역 두 개로 나누었기 때문에 2^11 즉 2KB 만큼의 entry가 필요하다.

| P1 | P2 | Page offset |

이 구조에서 주소 변환은 Outer table (P1)부터 안쪽으로 이루어진다.

P1 10 bit로 P2의 어떤 지점에 주소가 위치하는지 변환
P2의 10 bit로 어떤 frame에 접근해야 하는지 변환
변환된 frame에 offset 값 d를 붙여 메모리 접근

64-bit의 논리 주소 공간이 있는 시스템의 경우 2단계 paging은 충분하지 않다. page 크기가 2^12로 4KB일 때, page entry 수는 2^52 개가 필요하다. 이를 2^42와 2^10 총 2단계로 나눈다고 해도 outer table은 2^42 * 2^2인 16TB가 필요하다.

따라서 64-bit 시스템에서는 outer table을 여러 방법으로 나눌 수 있다.

Three-level paging

P1(32) | P2(10) | P3(10) | offset(12)
Outer page table은 2^10으로 구성되었다. 하지만 두 번째 outer table은 2^32로 여전히 크다.

Four-level paging

Three-level paging에서 두 번째 outer table이 더 분할되는 것이다.
최대 7단계의 page 계층이 형성될 수 있다.
7단계의 paging은 엄청난 메모리 접근을 초래하기 때문에 64bit 구조에서는 계층적 page table이 부적합하다.

2) Hashed page tables

32-bit 이상의 시스템에서 메모리 주소 공간을 제어하기 위해 가상 page 번호로 hash value를 생성해 hashed page table을 사용한다. Hash table의 각 entry는 같은 위치에 hash 된 원소를 연결 리스트 형태로 저장한다. 각 원소는 세 가지 필드를 포함한다.

가상 page 번호
맵핑된 page frame의 값
다음 원소에 대한 포인터

가상 page 번호 p는 hash table에 hash 되었다. 이 p의 frame 번호를 알아내기 위한 과정은 다음과 같다.

p와 field 1을 비교한다.
field 1은 p가 아니라 q다.
q의 next인 field 2의 원소를 탐색한다.
field 2의 원소는 p다. 해당 원소의 frame 값을 사용해 물리 주소를 생성한다.

32-bit 이상의 시스템에서는 일반 hash table의 변형인 clustered page tables를 활용한다. 이는 hash table과 유사하지만 한 항목이 여러 페이지를 가리킨다는 점이 다르다. 한 page table entry가 여러 물리 frame을 맵핑하기 때문에 메모리 참조가 연속적이지 않고 흩어져 있는 경우 유용하다.

3) Inverted page table

보통 각 프로세스는 연관된 page table이 있다. 그리고 page table은 프로세스가 사용하는 각 페이지에 대해 하나의 entry를 저장한다. 프로세스가 page의 가상 주소를 통해 page를 참조하기 때문에 이는 자연스러운 표현 방법이나, 앞서 살펴보았듯이 page table이 비대해져서 많은 물리 메모리를 사용해야 한다. 즉, 물리 메모리 사용을 추적하기 위해 물리 메모리를 많이 사용하는 판국이다.

이를 해결하기 위해 물리 메모리 사용 여부를 관리하기 위한 하나의 table을 두는 것이 Inverted page table이다.

Inverted page table에는 논리적 page가 아닌 물리 메모리의 실제 frame이 하나의 entry를 가진다. 즉 실제 물리 메모리에 있는 page의 정보만을 저장한다.

각 entry는 실제 메모리 위치에 저장된 page의 가상 주소와 해당 page를 소유한 프로세스에 대한 정보가 저장된다. 따라서 프로세스별로 하나의 page table을 유지하는 것이 아니라 시스템에서 하나의 page table을 유지하는 것이다.

Inverted page table entry에는 ASID가 요구되기도 한다. Table이 물리 주소를 사상하는 여러 다른 주소 공간을 포함하기 때문이다.

Inverted page table은 기존 솔루션에 비해 검색 시간이 증가할 수 있다. Page table을 저장하는 물리 메모리 양은 줄었지만 각 entry가 물리 주소를 기준으로 정렬되고, page 참조 시에는 가상 주소를 사용하기 때문에 page 검색 시간이 증가할 수 있다.

이 문제를 해결하기 위해 hash table을 사용하여 한 번이나 몇 번의 검색만으로 원하는 주소를 찾을 수 있다. 또한 TLB를 사용하면 성능을 더 향상시킬 수 있다.

또 하나의 단점은 page를 공유할 수 없다는 점이다. 기존 프로세스별 page table에서는 하나의 물리 주소가 여러 가상 주소에 대응될 수 있었다. Inverted page table에서는 각 물리 page 당 하나의 가상 page entry가 대응되기 때문에 하나의 물리 page가 여러 가상 주소를 가질 수 없다.

Swapping

프로세스 명령어와 데이터는 메모리에 있어야 실행될 수 있다. 그러나 프로세스 혹은 프로세스의 일부가 일시적으로 백업 장치로 내보내졌다가 돌아올 수 있다. 이를 Swapping이라고 하며, swapping을 사용하면 모든 프로세스의 전체 물리 주소 영역이 실제 물리 메모리를 초과해도 된다. 그렇게 멀티프로그래밍의 차수를 올릴 수 있다.

Standard Swapping

기존 swapping 방식에서는 프로세스 전체가 메모리와 백업 장치 사이를 이동했다. 백업 장치는 프로세스의 어느 부분이든 저장/검색할 수 있도록 충분히 커야했다. 프로세스가 swap out되면 관련 자료 구저가 저장장치에 기록되어야 하기 때문이다. 멀티 스레드인 경우 모든 스레드의 자료 구조가 swap out 된다.

OS는 swap out 된 프로세스의 메타데이터를 유지해야 추후 메모리로 돌아왔을 때 복원할 수 있다.

이 방식의 장점은 실제 물리 메모리 이상의 프로세스를 수용할 수 있다는 것이다. Swapping 되기 좋은 후보는 idle 상태이거나 거의 idle 상태인 프로세스다. 비활성화 된 프로세스에 할당됐던 메모리는 활성화된 프로세스에게 할당된다. Swap out 된 비활성화 프로세스가 다시 활성화되면 swap in 된다.

기존 swapping 방식은 전통 UNIX 계열 시스템에서 사용되었으나 현대 OS에서는 더 이상 사용되지 않는다. 메모리와 백업 장치 간 프로세스 이동 시간이 상당하기 때문이다. Soraris의 경우는 여전히 Standard swapping을 사용하는데, 이마저도 가용 메모리가 매우 적은 상황에서만 사용된다.

Swapping with Paging

Paging을 이용한 swapping은 현대적인 swapping 방식이며, standard swapping의 변형이다. Linux와 Windows에서 사용된다. 이 방식에서는 전체 프로세스가 아닌 page가 swap되어 전체 프로세스를 swap 하는 비용을 줄이면서도 물리 메모리 이상의 프로세스를 수용할 수 있도록 한다. 이제부터

아래에서 Swapping은 standard swapping을 paging은 swapping with paging을 의미한다. page out은 page를 메모리에서 백업 장치로 이동하는 것을, page in은 백업장치에서 메모리로 이동하는 것을 말한다.

Swapping in mobile devices

모바일 시스템은 일반적으로 swapping을 지원하지 않는다. 첫 번째 이유는 공간의 제약이다. 비휘발성 저장 장치로 HDD 대신 flash 메모리를 사용한다. 따라서 저장 공간에 제약이 있다. 두 번째 이유는 flash 메모리의 unreliable 전까지 쓰기를 허용하는 횟수의 제한과 메인 메모리와 flash 메모리 간 성능 제약이다. 이러한 제약 때문에 모바일 시스템 개발자는 어플리케이션이 메모리를 너무 많이 사용하거나 메모리 누수에 시달리지 않도록 메모리 할당과 해제에 신경 써야 한다.

iOS의 경우 가용 메모리가 임계값 이하로 떨어지면 어플리케이션에 할당된 메모리 양도를 요청한다. 이때 코드와 같은 read-only 데이터는 메인 메모리에서 제거되고, 추후 필요하면 flash 메모리에서 다시 로드된다. 스택과 같이 수정된 데이터는 제거되지 않는다.

Android의 경우 가용 메모리가 부족하면 프로세스를 종료한다. 단 종료 전에 어플리케이션의 상태를 flash 메모리에 기록하여 빨리 재시작될 수 있게 한다.