메인 메모리

배경

 

메인 메모리는 현대 컴퓨터 시스템 작동의 중심이며, 각각 고유한 주소를 가진 큰 바이트 배열.

CPU는 프로그램 카운터가 가리키는 위치에서 다음 명령어를 메모리로부터 가져오고, 

필요하면 추가 데이터를 읽거나 결과를 다시 메모리에 저장하는 구조.

전형적인 명령어 실행은 명령어 인출, 명령어 해독, 피연산자 인출, 연산 수행, 결과 저장의 흐름.

메모리는 주소가 어떻게 만들어졌는지, 그 주소가 명령어를 가리키는지 데이터를 가리키는지 알지 못하는 장치.

따라서 메모리 관리에서 중요한 것은 프로그램이 생성하는 주소들을 실제 메모리와 어떻게 연결할 것인지에 관한 문제.

 

기본 하드웨어

메인 메모리와 각 처리 코어에 내장된 레지스터는 CPU가 직접 접근할 수 있는 유일한 범용 저장장치.

기계 명령어는 메모리 주소를 인수로 사용할 수 있지만, 디스크 주소를 직접 인수로 사용할 수 없는 구조.

실행 중인 모든 명령어와 데이터는 CPU가 직접 접근 가능한 메인 메모리나 레지스터 안에 존재해야 하는 조건.

데이터가 메모리에 없다면 CPU가 처리하기 전에 먼저 메모리로 이동시켜야 하는 필요.

레지스터 접근은 일반적으로 CPU 클록 한 사이클 안에 가능한 반면, 

메인 메모리 접근은 메모리 버스를 거쳐야 하므로 여러 CPU 클록 사이클이 필요한 느린 접근.

CPU가 필요한 데이터를 기다리며 명령어를 수행하지 못하는 현상은 스톨(stall).

메인 메모리 접근 지연을 줄이기 위해 CPU와 메인 메모리 사이에 빠른 캐시 메모리를 두는 구조.

캐시는 보통 하드웨어가 관리하며, 운영체제의 직접 개입 없이 메모리 접근 속도를 향상시키는 장치.

다중 스레드 코어에서는 메모리 스톨 동안 다른 하드웨어 스레드로 전환해 지연을 숨길 수 있는 구조.

메모리 관리에서는 속도뿐 아니라 올바른 동작과 보호도 중요한 조건.

사용자 프로그램으로부터 운영체제 영역을 보호해야 하고, 

사용자 프로그램들 사이에서도 서로의 메모리를 보호해야 하는 필요.

운영체제가 CPU와 메모리 접근 사이에 매번 개입하면 성능이 크게 떨어지므로, 

메모리 보호는 반드시 하드웨어 지원이 필요한 기능.

각 프로세스가 독립된 메모리 공간을 갖도록 보장하려면 

특정 프로세스만 접근 가능한 합법적인 메모리 주소 영역 설정이 필요한 구조.

기준 레지스터와 상한 레지스터는 가장 기본적인 메모리 보호 기법.

기준 레지스터는 가장 작은 합법적인 물리 메모리 주소를 저장하고, 

상한 레지스터는 해당 프로세스가 접근할 수 있는 주소 영역의 크기를 저장하는 레지스터.

예를 들어 기준 레지스터 값이 300040이고 상한 레지스터 값이 120900이면 

접근 가능한 주소 범위는 300040부터 420940까지의 영역.

CPU 하드웨어는 사용자 모드에서 생성되는 모든 주소가 기준과 상한의 범위 안에 있는지 검사하는 역할.

사용자 프로그램이 운영체제 메모리 영역이나 다른 사용자 프로그램 영역에 접근하면 운영체제로 트랩이 발생하는 구조.

트랩은 잘못된 메모리 접근을 치명적인 오류로 처리하기 위한 제어 이동.

기준 레지스터와 상한 레지스터는 특권 명령으로만 적재 가능하며, 특권 명령은 커널 모드에서만 실행 가능한 명령.

사용자 프로그램이 기준 레지스터와 상한 레지스터 값을 직접 변경할 수 없도록 막는 것이 보호의 핵심.

커널 모드에서 실행되는 운영체제는 운영체제 메모리와 사용자 메모리 모두에 접근 가능한 권한.

이 권한 덕분에 운영체제는 

사용자 프로그램 적재, 오류 발생 시 덤프, 시스템 콜 매개변수 변경, 사용자 메모리 기반 입출력, 문맥 교환 등의 

작업 수행 가능.

문맥 교환에서는 한 프로세스의 상태를 레지스터에서 메인 메모리로 저장하고, 

다음 프로세스의 상태를 메인 메모리에서 레지스터로 복원하는 과정.

 

 주소의 할당

프로그램은 처음에 이진 실행 파일 형태로 디스크에 저장된 상태.

프로그램이 실행되려면 디스크의 실행 파일이 메모리로 올라와 프로세스 문맥 안에 배치되어야 하는 과정.

프로세스가 실행되면 메모리에서 명령어와 데이터에 접근하고, 

종료되면 해당 메모리는 다른 프로세스를 위해 회수되는 흐름.

대부분의 시스템은 사용자 프로세스가 메모리의 어느 위치에도 올라올 수 있도록 지원하는 구조.

사용자 프로그램의 주소가 00000번지에서 시작한다고 해서 

실제 물리 메모리의 00000번지에 올라가야 하는 것은 아닌 구조.

사용자 프로그램은 실행되기까지 여러 단계를 거치며, 

그 과정에서 주소 표현도 여러 형태로 변화.

소스 프로그램에서 주소는 변수 count와 같은 심벌 주소 형태.

컴파일러는 심벌 주소를 재배치 가능한 주소로 변환하고, 

링커나 로더는 재배치 가능한 주소를 절대 주소로 바인딩하는 역할.

주소 바인딩은 한 주소 공간의 주소를 다른 주소 공간의 주소로 매핑하는 과정.

사용자 프로그램의 처리 과정은 

소스 프로그램, 컴파일러, 오브젝트 파일, 링커, 실행 파일, 로더, 메모리의 프로그램 순서.

다른 오브젝트 파일과 동적으로 링크되는 라이브러리는 프로그램 실행 과정에서 함께 연결될 수 있는 요소.

명령어와 데이터의 바인딩은 바인딩이 이루어지는 시점에 따라 컴파일 시간, 적재 시간, 실행 시간 바인딩으로 구분.

컴파일 시간 바인딩은 프로세스가 메모리의 어디에 들어갈지 컴파일 시점에 이미 알고 있는 경우의 방식이며, 

컴파일러가 절대 코드를 생성할 수 있지만 시작 위치가 바뀌면 다시 컴파일해야 하는 한계.

적재 시간 바인딩은 프로세스가 메모리의 어디에 올라갈지 컴파일 시점에 모르는 경우의 방식이며, 

컴파일러가 재배치 가능 코드를 만들고 실제 적재 시점에 심벌과 실제 주소의 바인딩이 이루어지는 구조.

적재 시간 바인딩에서는 시작 주소가 바뀌어도 사용자 코드를 다시 적재하기만 하면 되는 장점.

실행 시간 바인딩은 프로세스가 실행 중에도 한 메모리 세그먼트에서 다른 세그먼트로 이동할 수 있는 경우의 방식이며, 

바인딩이 실행 시간까지 지연되므로 특별한 하드웨어 지원이 필요한 구조.

이 장의 중요한 요점은 여러 바인딩을 효과적으로 구현하는 방법과 이를 위한 하드웨어 지원.

 

논리 대 물리 주소 공간

CPU가 생성하는 주소는 일반적으로 논리 주소이고, 

메모리 주소 레지스터에 주어져 실제 메모리가 취급하는 주소는 물리 주소.

컴파일 시간 바인딩과 적재 시간 바인딩에서는 논리 주소와 물리 주소가 같은 경우.

실행 시간 바인딩에서는 논리 주소와 물리 주소가 서로 다르며, 이때 논리 주소는 가상 주소라고도 부르는 개념.

논리 주소 공간은 프로그램이 생성하는 모든 논리 주소의 집합이고, 

물리 주소 공간은 논리 주소와 실제로 대응되는 모든 물리 주소의 집합.

프로그램 실행 중에는 가상 주소를 물리 주소로 변환해야 하며, 

이 변환 작업은 MMU가 수행하는 역할.

(MMU는 memory management unit의 약자이며, 메모리 관리 장치라는 의미.)

단순한 MMU 방식에서는 기준 레지스터 기법을 일반화한 재배치 레지스터 사용.

재배치 레지스터 값은 주소가 메모리로 보내질 때마다 논리 주소에 더해지는 값.

예를 들어 재배치 레지스터 값이 14000이고 프로세스가 논리 주소 346에 접근하면 실제 물리 주소는 14346.

사용자 프로그램은 실제 물리 주소에 직접 접근하지 않고 논리 주소만 사용하는 구조.

사용자 프로그램이 포인터를 만들고 저장하고 연산하고 비교해도 그것은 논리 주소에 대한 작업.

실제 메모리 하드웨어는 MMU를 통해 논리 주소를 물리 주소로 바꾼 뒤 접근하는 구조.

논리 주소는 0부터 max까지의 범위를 갖고, 대응되는 물리 주소는 R+0부터 R+max까지의 범위를 갖는 구조.

논리 주소 공간과 물리 주소 공간이 서로 분리되는 개념은 올바른 메모리 관리의 핵심.

 

동적 적재

지금까지의 설명은 프로세스 전체가 실행 전에 메모리에 올라와 있어야 한다는 전제.

메모리 공간을 더 효율적으로 이용하려면 필요한 루틴만 메모리에 올리는 동적 적재가 필요.

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

main 프로그램이 먼저 메모리에 올라와 실행되고, 

다른 루틴이 호출될 때 해당 루틴이 이미 적재되었는지 검사하는 방식.

호출된 루틴이 메모리에 없다면 재배치 가능 연결 적재기가 루틴을 메모리로 가져오고, 

주소 변환 정보를 테이블에 기록하는 과정.

그 뒤 CPU 제어는 중단되었던 루틴으로 돌아가는 흐름.

동적 적재의 장점은 루틴이 필요한 경우에만 적재된다는 점이며, 

오류 처리 루틴처럼 가끔 발생하지만 코드 크기가 큰 부분에 특히 유용한 기법.

동적 적재를 사용하면 전체 프로그램 크기는 클 수 있어도 실제 사용되는 부분만 메모리에 올라오는 효과.

동적 적재는 운영체제로부터 특별한 지원이 반드시 필요한 기법은 아니며, 사용자 프로그램 설계가 책임지는 부분.

운영체제는 동적 적재 구현을 쉽게 하기 위한 라이브러리 루틴을 제공할 수 있는 역할.

 

 동적 연결 및 공유 라이브러리

동적 연결 라이브러리 DLL은 사용자 프로그램 실행 중에 사용자 프로그램에 연결되는 시스템 라이브러리.

정적 연결은 라이브러리 코드가 실행 가능 이미지 안에 포함되는 방식이고, 

동적 연결은 라이브러리 연결을 실행 시점까지 미루는 방식.

동적 적재가 적재를 실행 시점까지 미루는 것이라면, 동적 연결은 연결을 실행 시점까지 미루는 개념.

동적 연결은 표준 C 언어 라이브러리 같은 시스템 라이브러리에 주로 사용되는 방식.

동적 연결이 없으면 각 실행 가능 이미지가 필요한 라이브러리 루틴 사본을 포함해야 하므로 

실행 파일 크기 증가와 메인 메모리 낭비.

동적 연결에서는 라이브러리 루틴을 참조하는 작은 코드 조각인 스텁이 실행 이미지에 포함되는 구조.

스텁은 해당 라이브러리 루틴이 이미 메모리에 있는지 찾거나, 없으면 적재하는 방법을 알려주는 역할.

루틴이 메모리에 적재되면 스텁은 해당 루틴의 실제 주소로 대체되고, 

다음 호출부터 바로 라이브러리 루틴으로 이동하는 흐름.

동적 연결의 장점은 라이브러리 하나를 여러 프로세스가 공유할 수 있다는 점.

메모리에는 DLL 인스턴스 하나만 존재하고 여러 프로세스의 주소 공간에 함께 매핑될 수 있는 구조.

이런 이유로 DLL은 공유 라이브러리라고도 부르며, Windows와 Linux에서 널리 사용되는 방식.

동적 연결의 또 다른 장점은 라이브러리 갱신의 용이성.

버그 수정이나 기능 확장으로 라이브러리가 교체되면, 

해당 라이브러리를 사용하는 프로그램은 자동으로 새 버전을 사용할 수 있는 구조.

정적 연결에서는 새 라이브러리 사용을 위해 프로그램 전체를 다시 링크해야 하는 한계.

라이브러리 버전 정보는 프로그램과 라이브러리 안에 함께 포함되어야 하며, 

동일한 버전 번호를 유지하는 소규모 수정과 버전 번호를 올리는 대규모 수정의 구분이 필요한 이유.

동적 적재는 사용자 프로그램만으로 구현 가능하지만,

 동적 연결과 공유 라이브러리는 일반적으로 운영체제의 도움이 필요한 기능.

운영체제는 각 프로세스가 자기 공간만 접근하도록 보호하면서도, 

여러 프로세스가 같은 메모리 주소의 루틴을 공유할 수 있게 배치해야 하는 역할.

 

연속 메모리 할당

메인 메모리는 운영체제와 여러 사용자 프로세스를 모두 수용해야 하는 자원.

메모리의 각 영역은 목적에 맞게 효율적으로 관리되어야 하는 공간.

초기 메모리 할당 방법 중 하나가 연속 메모리 할당.

메모리는 일반적으로 운영체제를 위한 영역과 사용자 프로세스를 위한 영역으로 분리.

운영체제는 낮은 메모리 주소나 높은 메모리 주소에 배치될 수 있으나, 

Linux와 Windows를 포함한 많은 운영체제는 높은 메모리 영역 사용.

여러 사용자 프로세스가 동시에 메모리에 상주하기를 원하므로, 

운영체제는 사용 가능한 메모리를 적절히 나누어 할당해야 하는 역할.

연속 메모리 할당에서는

 각 프로세스가 다음 프로세스가 적재된 영역과 인접한 하나의 연속적인 메모리 영역에 적재되는 방식.

연속 메모리 할당을 논의하기 전에는 먼저 메모리 보호 문제 해결이 필요.

 

메모리 보호

메모리 보호는 기준 레지스터와 재배치 레지스터의 아이디어를 결합하여 구현 가능한 방식.

재배치 레지스터는 가장 작은 물리 주소 값을 저장하고, 상한 레지스터는 논리 주소의 범위 값을 저장하는 레지스터.

각 논리 주소는 상한 레지스터가 지정한 범위 안에 있어야 하는 조건.

MMU는 논리 주소에 재배치 레지스터 값을 더하여 물리 주소로 변환하는 역할.

변환된 주소만 실제 메모리로 보내지는 구조.

CPU 스케줄러가 다음 프로세스를 선택하면 디스패처는 문맥 교환 과정에서 

재배치 레지스터와 상한 레지스터에 올바른 값을 적재하는 역할.

CPU가 생성하는 모든 주소는 이 레지스터 값을 참조하는 확인 과정을 거치는 구조.

이 구조 덕분에 운영체제와 다른 사용자 프로그램은 현재 실행 중인 사용자 프로그램의 접근으로부터 보호되는 상태.

재배치 레지스터를 사용하면 운영체제의 크기를 실행 중에도 어느 정도 변경할 수 있는 장점.

장치 드라이버처럼 필요한 경우에만 메모리에 적재해도 되는 운영체제 코드 공간을 유동적으로 관리할 수 있는 구조.

사용 중이 아닌 장치 드라이버를 메모리에 계속 유지하지 않고, 

필요할 때만 적재하거나 제거하여 메모리를 다른 요청에 할당 가능.


9.2.2 메모리 할당

메모리 할당의 가장 단순한 방식 중 하나는 프로세스를 메모리의 가변 크기 파티션에 배치하는 방식.

각 파티션에는 정확히 하나의 프로세스만 적재 가능한 구조.

운영체제는 사용 가능한 메모리 부분과 사용 중인 메모리 부분을 나타내는 테이블을 유지하는 역할.

처음에는 모든 사용자 메모리가 하나의 큰 가용 메모리 블록 [hole]로 간주되는 상태.

시간이 지나면 프로세스의 적재와 종료에 따라 메모리 안에 다양한 크기의 hole이 생기는 구조.

프로세스가 시스템에 들어오면

운영체제는 그 프로세스가 요구하는 메모리 크기와 가용 공간의 위치를 고려하여 공간을 할당.

프로세스가 메모리를 할당받으면 이후에는 CPU를 할당받기 위해 경쟁하는 상태.

프로세스가 종료되면 해당 메모리는 반환되고, 

운영체제는 그 공간을 다른 프로세스에 다시 할당 가능한 상태로 관리.

도착한 프로세스의 요구를 충족시킬 만큼 메모리가 충분하지 않다면 프로세스를 거부하거나 대기 큐에 넣는 선택지.

나중에 메모리가 해제되면 운영체제는 대기 큐를 검사하여 

대기 중인 프로세스의 메모리 요구를 충족할 수 있는지 확인하는 흐름.

프로세스가 필요한 공간보다 큰 hole을 할당받으면 hole은 두 부분으로 나뉘며, 

한 부분은 프로세스에 할당되고 남은 부분은 다시 hole 집합으로 돌아가는 구조.

프로세스가 종료되면 그 공간은 hole 집합으로 되돌아가며, 인접한 hole이 있다면 합쳐져 더 큰 hole이 되는 과정.

동적 메모리 할당 문제는 일련의 가용 공간 리스트에서 

크기 n바이트 블록 요청을 어떻게 만족시킬 것인지 결정하는 문제.

최초 적합은 첫 번째로 발견한 충분히 큰 가용 공간을 할당하는 전략이며, 

리스트의 시작점이나 이전 검색 종료 지점에서 검색을 시작할 수 있는 방식.

최초 적합은 충분히 큰 가용 공간을 찾으면 검색을 즉시 끝낼 수 있으므로 속도 측면에서 유리한 전략.

최적 적합은 사용 가능한 공간 중 요청 크기를 만족하는 가장 작은 공간을 선택하는 전략이며, 

리스트가 크기 순으로 정렬되어 있지 않다면 전체 리스트를 모두 검색해야 하는 방식.

최적 적합은 아주 작은 가용 공간을 만들어내는 경향.

최악 적합은 가장 큰 가용 공간을 선택하여 할당 후 남는 공간도 다른 프로세스에 유용하게 쓰이기를 기대하는 전략.

최악 적합도 가용 공간 리스트가 크기 순으로 정렬되어 있지 않으면 전체 리스트 검색이 필요한 방식.

모의실험 결과 최초 적합과 최적 적합은 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋은 것으로 입증된 경향.

최초 적합과 최적 적합 중 어느 것이 항상 더 공간 효율적인지는 단정하기 어려운 문제.

일반적으로 최초 적합이 최적 적합보다 더 빠른 방식.

 

단편화

최초 적합과 최적 적합 모두 외부 단편화 문제를 가질 수 있는 전략.

외부 단편화는 사용 가능한 총 메모리 공간은 충분하지만 작은 조각으로 흩어져 있어 요청을 만족하지 못하는 상황.

프로세스가 메모리에 적재되고 제거되는 일이 반복되면 여러 작은 hole이 생기는 구조.

외부 단편화가 심해지면 모든 작은 hole을 합치면 충분한 공간인데도 큰 프로세스를 넣지 못하는 문제.

최악의 경우에는 모든 프로세스 사이마다 사용되지 못하는 가용 공간이 존재하는 상태.

외부 단편화의 크기는 메모리 전체 크기, 프로세스 평균 크기, 할당 알고리즘에 영향을 받는 요소.

어떤 시스템에서는 최초 적합이 더 우수하고, 어떤 시스템에서는 최적 적합이 더 우수할 수 있는 상황.

어떤 알고리즘을 선택하더라도 외부 단편화 자체는 여전히 남는 문제.

최초 적합에 대한 통계적 분석에서는 N개의 블록이 할당되었을 때 약 0.5N개의 블록이 단편화로 손실될 수 있다는 결과.

이 현상은 50퍼센트 규칙이며, 메모리의 약 3분의 1이 사용할 수 없게 될 수 있다는 의미.

단편화는 외부적으로만 발생하는 것이 아니라 내부적으로도 발생 가능한 현상.

내부 단편화는 할당된 메모리 블록 안에서 실제로 사용되지 않는 부분이 생기는 문제.

예를 들어 18,464B의 hole에 18,462B 요청을 정확히 맞추면 2B의 hole이 남는 상황.

2B짜리 hole을 관리하기 위한 오버헤드가 더 클 수 있으므로, 

시스템은 조금 더 큰 고정 단위로 메모리를 할당하는 경향.

이 경우 요청한 공간보다 조금 더 큰 공간이 할당되고, 

그 안의 남는 부분은 사용할 수 없는 내부 단편화.

외부 단편화의 해결 방법 중 하나는 메모리의 모든 내용을 한쪽으로 몰고 

모든 가용 공간을 다른 한쪽으로 모아 큰 블록을 만드는 압축.

압축은 항상 가능한 방법이 아니며, 재배치가 어셈블 또는 적재 시에 정적으로 이루어진다면 실행 불가능한 방식.

압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능한 방식.

주소가 동적으로 재배치될 수 있다면 프로그램과 데이터를 새 위치로 옮기고 기준 레지스터만 수정하여 압축 가능.

가장 단순한 압축 알고리즘은 모든 프로세스를 한쪽 끝으로 이동시켜 모든 가용 공간을 반대편으로 모으는 방식이며, 

비용이 매우 큰 한계.

외부 단편화를 해결하는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 비연속적인 공간으로 나누어 

물리 메모리에 배치하는 방식.

세그멘테이션은 사용자가 생각하는 메모리 관점에서 공간을 나누는 일반적인 메모리 관리 기법.

페이징은 운영체제와 컴퓨터 하드웨어가 주로 사용하는 비연속 메모리 관리 전략.

 

페이징

페이징은 프로세스의 물리 주소 공간이 연속적일 필요가 없도록 만드는 메모리 관리 기법.

페이징은 연속 메모리 할당의 두 문제인 외부 단편화와 압축 필요성을 피하는 방법.

페이징은 대형 서버 시스템부터 모바일 장치 시스템까지 대부분의 운영체제에서 다양한 형태로 사용되는 방식.

페이징은 운영체제와 컴퓨터 하드웨어의 협력을 통해 구현되는 구조.

 

 기본 방법

물리 메모리는 프레임이라는 같은 크기의 블록으로 나누어지고, 

논리 메모리는 페이지라는 같은 크기의 블록으로 나누어지는 구조.

프레임과 페이지는 같은 크기.

프로세스가 실행될 때 그 프로세스의 페이지는 

파일 시스템이나 백업 저장장치에서 사용 가능한 메인 메모리 프레임으로 적재되는 흐름.

백업 저장장치는 메모리 프레임과 같은 크기의 고정 크기 블록으로 나누어지는 구조.

페이징은 논리 주소 공간과 물리 주소 공간을 완전히 분리할 수 있게 만드는 방식.

물리 메모리가 2의 64승 바이트보다 작은 시스템에서도 프로세스는 64비트 논리 주소 공간을 사용할 수 있는 구조.

CPU에서 나오는 모든 주소는 페이지 번호 p와 페이지 오프셋 d로 구성.

페이지 번호 p는 프로세스 페이지 테이블을 접근할 때 사용하는 인덱스.

페이지 테이블은 각 페이지가 올라가 있는 물리 메모리 프레임의 시작 주소 또는 프레임 번호를 저장하는 자료구조.

페이지 오프셋 d는 참조되는 프레임 안에서의 위치이며, 프레임 번호와 결합하면 실제 물리 메모리 주소가 되는 값.

논리 주소를 물리 주소로 변환하는 과정은 

페이지 번호 추출, 페이지 테이블 인덱싱, 프레임 번호 추출, 페이지 번호를 프레임 번호로 대체하는 순서.

페이지 오프셋은 주소 변환 과정에서 변경되지 않는 값.

프레임 크기와 페이지 크기는 하드웨어에 의해 정해지는 값.

페이지 크기는 보통 2의 거듭제곱이며, 일반적으로 4KB부터 1GB까지 다양한 크기.

페이지 크기를 2의 거듭제곱으로 정하면 논리 주소를 페이지 번호와 페이지 오프셋으로 쉽게 나눌 수 있는 장점.

논리 주소 공간 크기가 2의 m승이고 페이지 크기가 2의 n승 바이트라면, 상위 m-n비트는 페이지 번호, 

하위 n비트는 페이지 오프셋.

작은 예로 페이지 크기가 4B이고 물리 메모리가 32B라면 물리 메모리는 8개의 프레임으로 구성되는 구조.

논리 주소 0이 페이지 0, 오프셋 0이고 페이지 0이 프레임 5에 있다면 실제 주소는 20.

논리 주소 3은 페이지 0, 오프셋 3이므로 실제 주소는 23.

논리 주소 4는 페이지 1, 오프셋 0이고 페이지 1이 프레임 6에 있다면 실제 주소는 24.

페이징 자체는 일종의 동적 재배치이며, 모든 논리 주소는 페이징 하드웨어에 의해 실제 주소로 바인딩되는 구조.

페이징을 사용하면 빈 프레임이 어떤 프로세스의 페이지에도 할당될 수 있으므로 

물리 메모리의 연속성이 필요 없고 외부 단편화가 발생하지 않는 장점.

페이징에서도 내부 단편화는 발생 가능한 문제.

할당은 항상 프레임의 정수 배 단위로 이루어지므로, 

프로세스의 마지막 페이지가 프레임 전체를 다 쓰지 못할 수 있는 구조.

예를 들어 페이지 크기가 2,048B이고 프로세스가 72,766B를 요구하면 36개의 페이지 프레임이 필요.

마지막 페이지에는 1,086B가 사용되고 962B가 내부 단편화로 남는 상태.

최악의 경우 프로세스가 n개의 페이지와 추가 1B를 요구하면 n+1번째 프레임 대부분이 내부 단편화가 되는 상황.

프로세스 크기와 페이지 크기가 무관하다고 가정하면 평균적으로 프로세스당 반 페이지 정도의 내부 단편화 예상.

작은 페이지 크기는 내부 단편화를 줄이는 데 유리하지만, 페이지 테이블 크기를 키우는 단점.

디스크 입출력 측면에서는 페이지 크기가 클수록 보통 더 효율적인 경향.

페이지 크기는 시간이 지나면서 프로세스, 자료, 메인 메모리 크기 증가에 맞추어 함께 커진 경향.

현대 시스템의 보통 페이지 크기는 4KB 또는 8KB 수준.

일부 CPU와 운영체제 커널은 여러 페이지 크기를 지원하는 구조.

x86-64 시스템의 Windows 10은 4KB와 2MB 페이지를 지원하는 예시.

Linux는 보통 4KB 기본 페이지와 아키텍처마다 다른 대형 페이지를 지원하는 예시.

Linux에서 페이지 크기는 getpagesize() 시스템 콜이나 getconf PAGESIZE 명령으로 확인 가능.

32비트 CPU에서 페이지 테이블 항목 크기는 일반적으로 4B.

4B 항목은 2의 32승 개의 물리 페이지 프레임을 가리킬 수 있는 잠재적 표현력.

프레임 크기가 4KB라면 4B 엔트리로 16TB 규모의 물리 주소 공간 표현 가능.

실제 페이지 테이블 항목에는 프레임 번호뿐 아니라 

여러 제어 비트도 필요하므로 모든 비트가 주소 표현에 쓰이는 것은 아닌 구조.

프로세스가 실행되기 위해 도착하면 운영체제는 프로세스가 몇 페이지를 요구하는지 조사.

프로세스가 n개의 페이지를 요구하면 메모리에는 n개의 가용 프레임이 있어야 하는 조건.

가용 프레임이 충분하면 운영체제는 프레임들을 프로세스에 할당하고, 각 페이지가 어느 프레임에 들어갔는지 페이지 테이블에 기록.

페이징에서 프로그래머가 보는 메모리는 하나의 연속적인 공간이지만, 

실제 물리 메모리에서 프로그램은 여러 프레임에 흩어져 저장되는 구조.

프로그래머가 보는 메모리와 실제 물리 메모리의 차이는 주소 변환 하드웨어가 숨기는 부분.

사용자 프로세스는 자기 소유가 아닌 메모리에 접근할 수 없는 구조.

다른 프로세스의 메모리에 접근하려면 해당 페이지가 자신의 페이지 테이블에 있어야 하지만, 

페이지 테이블은 해당 프로세스 소유 페이지들만 가리키는 구조.

운영체제는 어떤 프레임이 할당되었고, 어떤 프레임이 사용 가능하며, 총 프레임 수가 얼마인지 파악해야 하는 역할.

이 정보는 프레임 테이블이라는 시스템 전체 자료구조에 저장되는 정보.

프레임 테이블은 각 물리 프레임마다 하나의 항목을 갖고, 

프레임의 빈 상태, 할당 상태, 할당된 경우 어느 프로세스의 어느 페이지인지 나타내는 자료구조.

운영체제는 사용자 프로세스의 논리 주소를 물리 주소로 변환할 수 있어야 하는 존재.

시스템 콜의 인자로 논리 주소가 전달되면 운영체제는 이를 올바른 물리 주소로 변환해야 하는 상황.

운영체제는 각 프로세스의 페이지 테이블 사본을 유지하는 구조.

페이지 테이블 사본은 프로세스가 CPU에 할당될 때 하드웨어 페이지 테이블 값을 설정하는 데 사용.

페이징은 주소 변환 관리 때문에 문맥 교환 시간을 증가시키는 요소.

 

하드웨어 지원

페이지 테이블은 프로세스별 자료구조.

페이지 테이블에 대한 포인터는 각 프로세스의 프로세스 제어 블록에 다른 레지스터 값들과 함께 저장되는 정보.

CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터뿐 아니라 

해당 프로세스의 페이지 테이블 관련 하드웨어 값도 다시 적재되어야 하는 구조.

페이지 테이블은 하드웨어로 여러 방식 구현 가능.

가장 단순한 방식은 페이지 테이블을 전용 고속 하드웨어 레지스터 집합으로 구현하는 방법.

전용 레지스터 방식은 페이지 주소 변환이 매우 효율적이지만, 

모든 레지스터 내용을 문맥 교환 때마다 교체해야 하므로 문맥 교환 시간이 증가하는 단점.

전용 레지스터 방식은 페이지 테이블이 작은 경우에만 적합한 방식.

현대 CPU의 페이지 테이블은 매우 큰 경우가 많으므로 전용 레지스터만으로 구현하기 어려운 구조.

대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터, 

PTBR을 사용하는 방식.

PTBR은 페이지 테이블의 시작 위치를 가리키는 레지스터.

다른 페이지 테이블을 사용하려면 PTBR 값만 변경하면 되므로 문맥 교환 비용을 줄일 수 있는 장점.

하지만 페이지 테이블을 메인 메모리에 두면 페이지 테이블 항목을 찾기 위한 

첫 번째 메모리 접근과 실제 데이터나 명령어를 읽기 위한 두 번째 메모리 접근이 필요한 문제.

이 방식만 사용하면 메모리 접근 시간이 거의 두 배로 느려질 수 있는 한계.

 

Translation Look-Aside Buffer[TLB]

TLB는 translation look-aside buffer의 약자이며, 

페이지 테이블 접근 지연을 줄이기 위한 특수한 소형 하드웨어 캐시.

TLB는 매우 빠른 연관 메모리로 구성되는 장치.

TLB 항목은 키와 값의 두 부분으로 구성되며, 키는 보통 페이지 번호이고 값은 대응되는 프레임 번호.

CPU가 논리 주소를 생성하면 MMU는 먼저 해당 페이지 번호가 TLB에 있는지 검사하는 흐름.

TLB 안에서 페이지 번호가 발견되면 TLB 히트.

TLB 히트가 발생하면 대응되는 프레임 번호를 즉시 얻고, 오프셋과 결합하여 물리 주소를 생성하는 구조.

이 절차는 CPU 내부 명령어 파이프라인의 일부로 실행되므로 

페이징을 사용하지 않는 시스템과 비교해 큰 성능 저하가 없는 편.

페이지 번호가 TLB에 없으면 TLB 미스.

TLB 미스가 발생하면 이전에 설명한 방식대로 메모리에 있는 페이지 테이블을 참조해야 하는 과정.

페이지 테이블에서 프레임 번호를 얻으면 해당 프레임 번호로 메모리에 접근하고, 

동시에 페이지 번호와 프레임 번호를 TLB에 추가하는 흐름.

TLB가 가득 차면 기존 항목 중 하나를 교체해야 하는 상황.

TLB 교체 정책에는 LRU, 라운드 로빈, 무작위 등 다양한 방식.

일부 CPU는 운영체제가 TLB 항목 교체에 참여하도록 허용하고, 일부 CPU는 하드웨어가 직접 선택하는 방식.

일부 TLB 항목은 제거되지 않도록 고정 가능하며, 보통 중요한 커널 코드에 대한 주소 변환 정보가 고정 대상.

일부 TLB는 ASID를 항목에 함께 저장.

ASID는 address-space identifier의 약자이며, 

해당 TLB 항목이 어느 프로세스에 속하는지 알려주는 정보.

ASID는 서로 다른 프로세스의 주소 공간을 구분하고 보호하기 위한 값.

주소 변환 시 현재 프로세스의 ASID와 TLB 항목의 ASID가 일치해야 해당 항목이 유효한 변환으로 인정되는 구조.

ASID가 맞지 않으면 TLB 미스로 처리되는 방식.

ASID 지원이 있으면 하나의 TLB 안에 여러 프로세스의 주소 변환 정보를 동시에 보관 가능.

ASID 지원이 없으면 문맥 교환 때마다 이전 프로세스의 TLB 항목을 전부 플러시해야 하는 비용.

TLB를 플러시하지 않으면 이전 프로세스의 페이지 번호와 프레임 번호가 남아 잘못된 주소 변환을 제공할 위험.

TLB 적중률은 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율.

적중률 80퍼센트는 원하는 페이지 번호를 TLB에서 찾을 확률이 80퍼센트라는 의미.

메인 메모리 접근 시간이 10ns이고 TLB 히트 시 접근 시간이 10ns, 

TLB 미스 시 페이지 테이블 접근과 실제 접근을 합쳐 20ns가 걸린다면, 적중률 80퍼센트의 실질 접근 시간은 12ns.

같은 조건에서 적중률이 99퍼센트라면 실질 접근 시간은 10.1ns.

TLB 적중률이 높을수록 페이징으로 인한 추가 비용이 크게 감소하는 구조.

현대 CPU는 여러 단계의 TLB를 갖는 경우가 많아 실제 계산은 더 복잡한 편.

예를 들어 Intel Core i7 CPU는 L1 명령어 TLB와 L1 데이터 TLB, 그리고 L2 TLB를 사용하는 구조.

L1에서 미스가 발생하면 L2 TLB를 검색하고, 

L2에서도 미스가 발생하면 메모리의 페이지 테이블을 검색해야 하는 흐름.

이러한 페이지 테이블 검색에는 수백 사이클이 필요하거나 운영체제 인터럽트 처리가 필요할 수 있는 비용.

TLB는 하드웨어 구성요소이지만 운영체제 설계에 큰 영향을 주는 요소.

운영체제는 특정 하드웨어 플랫폼의 TLB 구조에 맞게 페이징 방식을 구현해야 하는 필요.

 

보호

페이징 환경에서 메모리 보호는 각 페이지에 붙는 보호 비트로 구현되는 방식.

보호 비트는 보통 페이지 테이블 항목 안에 포함되는 정보.

보호 비트는 해당 페이지가 읽기 전용인지, 읽기와 쓰기가 가능한지, 실행이 가능한지 같은 권한을 나타내는 값.

주소 변환 과정에서 하드웨어는 해당 페이지에 대해 요청된 접근이 허용되는지 검사 가능.

읽기 전용 페이지에 쓰기를 시도하면 운영체제로 메모리 보호 위반 트랩이 발생하는 구조.

페이지 테이블의 각 엔트리에는 유효·무효 비트도 포함되는 방식.

유효 비트는 해당 페이지가 프로세스의 합법적인 논리 주소 공간에 속한다는 의미이고, 

무효 비트는 해당 페이지가 프로세스의 논리 주소 공간에 속하지 않는다는 의미.

운영체제는 유효·무효 비트를 통해 특정 페이지 접근을 허용하거나 차단 가능.

 

예를 들어 14비트 주소 공간을 가진 시스템에서 프로그램이 0부터 10,468까지의 주소만 사용할 수 있는 경우.

페이지 크기가 2KB라면 페이지 0부터 5까지는 정상적으로 사상될 수 있는 페이지.

페이지 6과 7에 대한 접근은 무효 비트 때문에 잘못된 페이지 참조로 처리되는 구조.

페이지 5는 일부 주소만 실제 프로그램 범위에 속하지만 페이지 단위로 유효 처리될 수 있는 상태.

이 문제는 페이징의 내부 단편화를 반영하는 예시.

프로세스가 전체 주소 범위를 항상 사용하는 경우는 드문 편.

많은 프로세스는 일정 시간 동안 주소 공간의 일부만 집중적으로 사용.

모든 페이지 테이블 항목을 계속 유지하는 것은 낭비가 될 수 있는 상황.

페이지 테이블 길이 레지스터 PTLR은 페이지 테이블의 크기를 나타내기 위한 레지스터.

모든 논리 주소는 유효한 범위 안에 있는지 확인하기 위해 PTLR 값과 비교되는 구조.

이 검사에서 오류가 나타나면 트랩이 발생하는 흐름.

 

공유 페이지

페이징의 중요한 장점 중 하나는 공통 코드를 공유할 수 있다는 점.

여러 프로세스가 있는 환경에서는 공유 페이지가 특히 중요한 메모리 절약 기법.

UNIX와 Linux에서 많은 사용자 프로세스는 표준 C 라이브러리인 libc를 필요로 하는 상황.

각 프로세스가 자체 libc 사본을 주소 공간에 적재하면 프로세스 수만큼 메모리 사용량이 증가하는 문제.

예를 들어 40개의 사용자 프로세스가 있고 libc가 2MB라면, 사본을 각각 적재할 경우 80MB의 메모리 필요.

코드가 재진입 코드라면 여러 프로세스가 같은 물리 페이지를 공유 가능.

재진입 코드는 실행 중에 자체 수정되지 않는 코드.

여러 프로세스가 동일한 코드를 동시에 실행해도 코드 내용이 변하지 않으므로 공유 가능한 구조.

각 프로세스는 자신의 실행을 위한 레지스터 사본과 데이터 저장 영역을 별도로 보유하므로, 

공유 코드는 같아도 각 프로세스의 데이터는 서로 다를 수 있는 구조.

표준 C 라이브러리는 물리 메모리에 하나의 사본만 저장하고, 

각 프로세스의 페이지 테이블이 동일한 물리 사본을 가리키게 만들 수 있는 대상.

이렇게 하면 40개 프로세스의 libc 사용 공간을 80MB가 아니라 2MB로 줄일 수 있는 효과.

libc 외에도 컴파일러, 윈도 시스템, 데이터베이스 시스템처럼 많이 사용되는 프로그램은 공유 대상이 될 수 있는 구조.

앞서 설명된 공유 라이브러리는 일반적으로 공유 페이지로 구현되는 방식.

공유가 가능하려면 공유 코드는 재진입 코드로 작성되어야 하는 조건.

운영체제는 공유 코드의 읽기 전용 속성을 강제해야 하는 역할.

프로세스 사이의 메모리 공유는 이전에 설명한 스레드의 주소 공간 공유와 유사한 개념.

프로세스 간 통신 방법으로도 메모리 공유가 사용 가능.

일부 운영체제는 프로세스 간 공유 메모리를 페이지 공유를 통해 구현하는 방식.

페이징을 통한 메모리 관리는 같은 물리 프레임을 여러 프로세스가 공유할 수 있게 하여 다양한 이익을 제공하는 구조.

 

페이지 테이블의 구조

페이지 테이블 구조는 큰 주소 공간에서 페이지 테이블 자체를 어떻게 저장하고 검색할 것인지에 대한 문제.

대표적인 페이지 테이블 구성 방법은 계층적 페이징, 해시 페이지 테이블, 역 페이지 테이블.

 

계층적 페이징

현대 컴퓨터는 매우 큰 주소 공간을 갖는 구조.

주소 공간이 커지면 페이지 테이블도 함께 커지는 문제.

예를 들어 32비트 논리 주소 공간에서 페이지 크기가 4KB라면 페이지 테이블 항목 수는 2의 20승 개 이상.

각 항목이 4B라면 각 프로세스는 페이지 테이블만을 위해 약 4MB의 공간 필요.

모든 페이지 테이블을 메인 메모리에 연속적으로 할당하는 것은 비효율적인 방식.

해결 방법 중 하나는 페이지 테이블을 여러 작은 조각으로 나누는 것.

2단계 페이징 기법은 페이지 테이블 자체를 다시 페이지화하는 방식.

32비트 주소와 4KB 페이지 크기의 예에서 논리 주소는 20비트 페이지 번호와 12비트 페이지 오프셋으로 구성.

2단계 페이징에서는 20비트 페이지 번호를 다시 10비트 p1과 10비트 p2로 나누는 구조.

p1은 바깥 페이지 테이블의 인덱스이고, 

p2는 안쪽 페이지 테이블 안에서의 오프셋 또는 인덱스이며, d는 페이지 안에서의 오프셋.

주소 변환은 바깥 페이지 테이블에서 시작해 안쪽 페이지 테이블로 들어가는 흐름.

이 방식은 forward-mapped 페이지 테이블이라고도 부르는 구조.

64비트 논리 주소 공간에서는 2단계 페이징도 충분하지 않은 문제.

페이지 크기가 4KB라면 페이지 테이블은 2의 52승 개의 항목으로 구성될 수 있는 규모.

2단계 페이징을 적용하면 안쪽 페이지 테이블은 한 페이지 크기 2의 10승 개 항목을 갖는 구조.

그 결과 바깥 페이지 테이블은 2의 42승 개 항목이 필요하고, 2의 44승 바이트 규모가 될 수 있는 문제.

큰 바깥 페이지 테이블을 피하기 위해 바깥 페이지 테이블을 다시 페이지화하는 3단계 페이징 가능.

3단계 페이징에서도 64비트 주소 공간에서는 

두 번째 바깥 페이지 테이블이 여전히 2의 34승 바이트인 16GB 크기를 요구할 수 있는 한계.

계속 단계를 늘리면 4단계 페이징도 가능하지만, 

주소 변환에 필요한 메모리 접근 횟수가 증가하는 문제.

64비트 UltraSPARC 구조는 7단계 페이징이 필요할 수 있으나, 

각 논리 주소를 변환하기 위해 너무 많은 메모리 접근이 필요하므로 비현실적인 방식.

이 예시는 일반적인 64비트 구조에서 단순한 계층적 페이지 테이블이 부적합할 수 있음을 보여주는 사례.

 

해시 페이지 테이블

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

해시 페이지 테이블의 각 항목은 연결 리스트를 갖는 구조.

연결 리스트는 같은 해시값으로 매핑되는 원소들이 충돌하여 함께 저장되는 위치.

각 원소는 가상 페이지 번호, 사상되는 페이지 프레임 번호, 연결 리스트의 다음 원소 포인터라는 세 필드로 구성.

주소 변환은 가상 주소에서 페이지 번호를 얻고, 그 값을 해시 함수에 넣는 과정으로 시작.

해시 결과로 해시 페이지 테이블의 특정 버킷이 선택되는 구조.

운영체제나 하드웨어는 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교.

일치하면 해당 원소의 페이지 프레임 번호를 가져와 물리 주소를 구성.

일치하지 않으면 연결 리스트의 다음 원소로 이동하여 같은 비교를 반복하는 흐름.

64비트 시스템에서 유용하도록 변형된 방식으로 클러스터 페이지 테이블 존재.

클러스터 페이지 테이블은 해시 페이지 테이블과 비슷하지만, 

각 항목이 하나의 페이지가 아니라 여러 페이지를 가리키는 구조.

예를 들어 한 항목이 16개 페이지에 대한 변환 정보를 저장할 수 있는 방식.

클러스터 페이지 테이블은 성긴 주소 공간에서 유용한 구조.

메모리 접근이 비연속적이지만 주소 공간 전체로 넓게 퍼지는 경우에 클러스터 페이지 테이블이 효과적인 방식.

 

역 페이지 테이블

보통 프로세스는 각각 하나씩 페이지 테이블을 가지며, 

페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 갖는 구조.

또는 가상 주소의 유효 여부와 상관없이 각 가상 페이지마다 하나의 항목을 갖는 방식도 가능.

각 프로세스의 페이지 테이블은 가상 주소를 통해 페이지를 참조할 때마다 필요.

운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 

페이지 테이블을 통해 물리 페이지 주소로 변환해야 하는 역할.

하지만 페이지 테이블 항목 수가 수백만 개가 될 수 있어 물리 메모리를 많이 소비하는 단점.

이 문제를 해결하는 방법 중 하나가 역 페이지 테이블.

역 페이지 테이블은 각 프로세스마다 페이지 테이블을 두지 않고, 

시스템 전체에 하나의 페이지 테이블만 두는 방식.

역 페이지 테이블에서는 메모리 프레임마다 한 항목이 할당되는 구조.

각 항목은 그 프레임에 올라와 있는 페이지 주소와 해당 페이지를 소유한 프로세스 ID를 표시.

이 방식에서는 테이블의 각 항목이 메모리의 한 프레임을 가리키는 구조.

역 페이지 테이블은 각 프로세스의 페이지 테이블 엔트리에 저장되는 주소 공간 ID를 요구.

주소 공간 ID는 서로 다른 프로세스들의 주소 공간을 구분하기 위한 정보이며, 

프로세스 ID가 그 역할을 할 수 있는 구조.

메모리 참조가 발생하면 가상 주소의 일부인 process-id, page-number, offset이 

메모리 하위 시스템에 전달되는 흐름.

역 페이지 테이블은 process-id와 page-number 쌍이 일치하는 항목을 찾는 방식.

일치하는 항목이 발견되면 그 항목의 위치 i와 offset을 결합해 물리 주소를 구성.

일치하는 항목이 없으면 잘못된 메모리 접근으로 간주되는 구조.

역 페이지 테이블의 장점은 

논리 페이지마다 항목을 두는 대신 물리 프레임마다 항목을 두기 때문에 훨씬 적은 메모리를 사용한다는 점.

역 페이지 테이블의 단점은 

물리 주소에 따라 정렬되어 있지만 탐색은 가상 주소를 기준으로 하므로 전체 테이블 검색이 필요할 수 있어 

주소 변환 시간이 길어질 수 있다는 점.

이 검색 비용을 줄이기 위해 해시 테이블을 함께 사용하는 방식.

주소 변환 시 성능 향상을 위해 해시 테이블을 보기 전에 먼저 TLB를 참조하는 것이 일반적인 흐름.

역 페이지 테이블의 흥미로운 문제 중 하나는 공유 메모리와의 관계.

일반 페이지 테이블에서는 여러 가상 주소가 하나의 물리 주소를 가리킬 수 있는 구조.

역 페이지 테이블은 물리 페이지마다 하나의 가상 페이지 항목만 갖기 때문에 

하나의 물리 페이지가 둘 이상의 공유 가상 주소를 동시에 갖기 어려운 구조.

따라서 역 페이지 테이블을 사용하는 경우 공유 메모리 구현에 추가적인 처리 필요.

 

Oracle SPARC Solaris

Oracle SPARC Solaris는 낮은 오버헤드로 가상 메모리를 제공하기 위해 해시 테이블을 활용하는 사례.

Solaris는 완전한 64비트 운영체제이며, 

여러 단계 페이지 테이블을 메모리에 유지하면서 물리 메모리를 과도하게 소비하지 않는 해결책이 필요한 구조.

Solaris는 이 문제를 해시 테이블을 사용하여 해결하는 방식.

이 방식은 두 개의 해시 테이블을 커널과 모든 사용자 프로세스를 위해 유지하는 구조.

각 해시 테이블은 가상 메모리 주소를 물리 메모리 주소로 변환하는 정보를 저장.

각 해시 테이블 항목은 사상된 가상 메모리의 연속된 영역을 나타내며, 

기준 주소와 해당 항목이 나타내는 페이지 개수를 표현하는 범위를 가짐.

변환 때마다 해시 테이블을 직접 검색하면 가상 주소 변환 시간이 길어질 수 있는 문제.

이를 줄이기 위해 CPU는 TTE를 저장하는 TLB를 구성.

TTE는 translation table entry의 약자이며, 변환 테이블 항목이라는 의미.

TTE를 위한 캐시가 TSB.

TSB는 translation storage buffer의 약자이며, 최근 접근한 페이지의 항목을 저장하는 장치.

가상 주소 참조가 발생하면 하드웨어는 먼저 TLB를 검색.

TLB에서 주소를 찾지 못하면 하드웨어는 메모리 안의 TSB를 탐색하여 해당 가상 주소에 대응하는 TTE를 찾는 흐름.

TSB에서 발견되면 CPU는 TSB 항목을 TLB로 복사하고 주소 변환을 완료.

TSB에서도 항목을 찾지 못하면 커널이 해시 테이블을 탐색할 수 있도록 인터럽트 발생.

커널은 해시 테이블에서 TTE를 생성하고, MMU가 자동으로 TLB에 적재할 수 있도록 TSB에 저장.

인터럽트 핸들러가 제어를 MMU에 넘기면 MMU는 주소 변환을 마치고 

요청된 바이트나 워드를 메인 메모리에서 읽는 흐름.

 

스와핑

프로세스가 실행되려면 명령어와 명령어가 접근하는 데이터가 메모리에 존재해야 하는 조건.

그러나 프로세스 전체 또는 일부는 실행 중 임시로 백업 저장장치로 내보내졌다가 다시 메모리로 돌아올 수 있는 구조.

이 기법이 스와핑.

스와핑을 사용하면 모든 프로세스의 물리 주소 공간 크기 합이 실제 물리 메모리 크기보다 커도 동시 실행이 가능.

스와핑의 효과는 다중 프로그래밍 정도 증가.

 

기본 스와핑

표준 스와핑은 메인 메모리와 백업 저장장치 사이에 전체 프로세스를 이동시키는 방식.

백업 저장장치는 일반적으로 빠른 보조저장장치.

백업 저장장치는 저장해야 하는 프로세스 크기와 무관하게 충분히 큰 공간을 제공해야 하고, 

메모리 이미지에 직접 접근할 수 있어야 하는 장치.

프로세스나 그 일부가 백업 저장장치로 스왑될 때, 해당 프로세스와 관련된 자료구조도 함께 기록되어야 하는 필요.

다중 스레드 프로세스의 경우 모든 스레드별 데이터 구조도 스왑 대상.

운영체제는 스왑아웃된 프로세스에 대한 메타데이터를 유지해야 하며, 다시 스왑인될 때 복원 가능해야 하는 구조.

표준 스와핑의 장점은 실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있다는 점.

유휴 상태이거나 대부분 시간을 기다리는 프로세스는 스와핑의 적합한 후보.

비활성 프로세스에 할당된 메모리는 활성 프로세스에 다시 할당 가능.

스왑된 비활성 프로세스가 다시 활성화되면 다시 스왑인해야 하는 흐름.

 

페이징에서의 스와핑

표준 스와핑은 기존 UNIX 시스템에서 사용된 방식.

하지만 전체 프로세스를 메모리와 백업 저장장치 사이에서 이동시키는 비용이 크기 때문에 

최신 운영체제에서는 일반적으로 잘 사용되지 않는 방식.

Solaris는 여전히 표준 스와핑을 사용할 수 있지만, 

사용 가능한 메모리가 매우 부족한 극단적인 상황에서만 사용하는 구조.

Linux와 Windows를 포함한 대부분의 시스템은 프로세스 전체가 아니라 

프로세스 페이지를 스왑하는 변형 스와핑 사용.

이 전략은 물리 메모리를 초과 할당할 수 있게 하면서도 전체 프로세스를 이동시키는 비용을 피하는 방식.

프로세스의 일부 페이지를 메모리에서 백업 저장장치로 이동시키는 작업은 페이지 아웃이고, 

백업 저장장치에 있던 페이지를 다시 메모리로 가져오는 작업은 페이지 인.

현대 문맥에서는 스와핑이라는 용어가 표준 스와핑을 가리키기도 하고,

페이징에서의 스와핑을 넓게 가리키기도 하는 표현.

페이징이라는 용어는 보통 페이징 환경에서의 스와핑을 의미하는 경우가 많음.

페이징에서의 스와핑은 가상 메모리와 함께 잘 작동하는 구조.

 

 모바일 시스템에서의 스와핑

PC와 서버 운영체제 대부분은 페이징 스와핑을 지원하는 구조.

반대로 모바일 시스템은 일반적으로 어떤 형태의 스와핑도 지원하지 않는 경우가 많음.

모바일 장치는 비휘발성 저장장치로 하드디스크보다 플래시 메모리를 주로 사용하는 구조.

플래시 메모리는 저장 공간이 상대적으로 제한적일 수 있어 스와핑 공간 확보가 부담.

플래시 메모리는 쓰기 횟수 제한이 있어 스와핑이 장치 수명에 영향을 줄 수 있는 특성.

플래시 메모리와 메인 메모리 사이의 처리량이 낮아 성능 측면에서도 스와핑이 불리한 구조.

이러한 이유로 모바일 운영체제 설계자는 스와핑을 피하는 경향.

iOS는 응용 프로그램에 할당된 메모리를 자발적으로 반환하도록 요청하는 정책 사용.

코드와 같은 읽기 전용 데이터는 필요하면 메인 메모리에서 제거했다가 나중에 플래시 메모리에서 다시 적재 가능.

스택과 같이 변경된 데이터는 함부로 제거할 수 없는 대상.

충분한 메모리를 반환하지 못한 응용 프로그램은 운영체제에 의해 종료될 수 있는 구조.

Android도 iOS와 유사한 정책을 사용하며, 

가용 메모리가 부족하면 프로세스를 종료할 수 있고 종료 전에 응용 상태를 플래시 메모리에 저장하여 

나중에 빠르게 재시작할 수 있는 구조.

모바일 운영체제 개발자는 응용이 너무 많은 메모리를 사용하거나 메모리 누수로 고생하지 않도록 주의해야 하는 필요.

스와핑이 필요하다는 것은 사용 가능한 물리 메모리보다 활성 프로세스가 더 많다는 신호.

이 상황의 일반적인 해결책은 일부 프로세스 종료 또는 더 많은 물리 메모리 장착.

 

사례: Intel 32비트와 64비트 구조

Intel 칩 구조는 오랫동안 개인용 컴퓨터 분야를 주도한 구조.

16비트 Intel 8086은 1970년대 후반에 등장한 프로세서.

8088 칩은 원 IBM PC에 사용되어 널리 알려진 프로세서.

이후 Intel은 32비트 Pentium 계열을 포함한 IA-32 구조의 칩 시리즈를 생산.

최근 Intel은 x86-64 구조에 기반한 64비트 칩 시리즈를 생산.

Windows, macOS, Linux 같은 주요 PC 운영체제는 Intel 칩 위에서 실행 가능한 구조.

Linux는 다른 구조에서도 실행 가능하지만, PC 환경에서는 Intel 계열이 중요한 대상.

Intel의 주도권은 모바일 시스템으로 이어지지 않았고, 모바일에서는 ARM 구조가 큰 성공을 거둔 상황.

이 절의 목적은 IA-32와 x86-64 구조에서 메모리 관리가 어떻게 변해왔는지 살펴보는 것.

모든 Intel 칩의 세부 구조를 설명하기보다 주요 메모리 관리 개념 중심의 정리.

 

IA-32 구조

IA-32 시스템의 메모리 관리는 세그멘테이션과 페이징의 두 부분으로 구성.

CPU는 먼저 논리 주소를 생성하고, 이 주소는 세그멘테이션 장치에 전달되는 구조.

세그멘테이션 장치는 논리 주소에 대응하는 선형 주소를 생성.

선형 주소는 다시 페이징 장치에 전달되어 메인 메모리의 물리 주소로 변환.

따라서 IA-32에서 세그멘테이션 장치와 페이징 장치는 함께 MMU 역할을 수행하는 구조.

 

IA-32 세그멘테이션

IA-32 구조에서 하나의 세그먼트는 최대 4GB 크기를 가질 수 있고, 

한 프로세스는 최대 16KB개의 세그먼트를 가질 수 있음.

각 프로세스의 주소 공간은 두 개의 파티션으로 분리.

첫 번째 파티션은 해당 프로세스가 독점적으로 사용하는 8KB 세그먼트들로 구성.

두 번째 파티션은 모든 프로세스 사이에서 공유 가능한 8KB 세그먼트들로 구성.

첫 번째 파티션 정보는 지역 디스크립터 테이블 LDT에 유지되고, 

두 번째 파티션 정보는 전역 디스크립터 테이블 GDT에 저장.

LDT와 GDT의 각 항목은 8B 크기.

각 디스크립터 항목은 세그먼트의 기준 위치, 길이, 보호 정보를 포함한 세부 정보.

논리 주소는 selector와 offset의 쌍으로 구성.

selector는 16비트 수.

selector의 13비트 s는 세그먼트 번호.

selector의 1비트 g는 해당 세그먼트가 GDT에 있는지 LDT에 있는지를 나타내는 값.

selector의 2비트 p는 보호와 관련된 정보.

offset은 세그먼트 안에서 찾고자 하는 바이트 위치를 나타내는 32비트 값.

CPU는 6개의 세그먼트용 레지스터를 가지고 있어 한 순간에 6개의 세그먼트를 가리킬 수 있는 구조.

CPU는 LDT 또는 GDT 디스크립터를 저장할 수 있는 6개의 8B 마이크로프로그램 레지스터도 가짐.

이 캐시는 메모리 참조 때마다 디스크립터를 메모리에서 다시 읽어오는 비용을 줄이는 역할.

IA-32에서 선형 주소 길이는 32비트.

세그먼트 레지스터는 LDT나 GDT 안의 적절한 항목을 가리키는 역할.

주소 변환 과정에서는 먼저 찾는 세그먼트의 기준과 상한 정보를 가져와 주소 타당성 검사 수행.

주소가 한계를 넘으면 메모리 오류가 발생하고 운영체제로 트랩 발생.

주소가 타당하면 offset 값이 기준 값에 더해져 32비트 선형 주소 생성.

 

IA-32 페이징

IA-32 구조에서 페이지 크기는 4KB 또는 4MB.

4KB 페이지를 사용할 때 IA-32는 2단계 페이징 기법 사용.

32비트 선형 주소는 페이지 디렉터리 인덱스 10비트, 페이지 테이블 인덱스 10비트, 페이지 오프셋 12비트로 구성.

상위 10비트는 페이지 디렉터리의 엔트리를 가리키는 값.

CR3 레지스터는 현재 프로세스의 페이지 디렉터리를 가리키는 레지스터.

페이지 디렉터리 엔트리는 하위 페이지 테이블 하나를 가리키는 구조.

다음 10비트는 해당 페이지 테이블 안의 엔트리를 인덱싱하는 값.

하위 12비트는 4KB 페이지 안의 오프셋.

페이지 디렉터리 엔트리에는 Page Size 플래그가 존재.

Page Size 플래그가 설정되면 페이지 프레임은 보통의 4KB가 아니라 4MB 크기.

이 경우 페이지 디렉터리는 하위 페이지 테이블을 가리키지 않고 직접 4MB 페이지 프레임을 가리키는 구조.

선형 주소의 하위 22비트는 4MB 페이지 프레임 안의 오프셋 역할.

IA-32 페이지 테이블은 물리 메모리 효율을 위해 디스크로 스왑될 수 있는 구조.

페이지 디렉터리 엔트리는 가리키는 페이지 테이블이 메모리에 있는지 

디스크에 있는지 확인하기 위해 invalid 비트 사용.

페이지 테이블이 디스크에 있으면 운영체제는 invalid 비트를 제외한 31비트를 

디스크 안의 테이블 위치를 저장하는 데 사용할 수 있음.

필요할 때 해당 페이지 테이블을 메모리로 가져오는 방식.

32비트 처리기의 4GB 메모리 제한이 문제가 되면서 Intel은 페이지 주소 확장 PAE를 채택.

PAE는 page address extension의 약자이며, 

32비트 처리기가 4GB보다 큰 물리 주소 공간에 접근할 수 있게 만든 기능.

PAE의 근본적인 변화는 2단계 페이징을 3단계 페이징으로 바꾼 점.

PAE에서는 최상위 2비트가 페이지 디렉터리 포인터 테이블을 가리키는 구조.

PAE는 페이지 디렉터리와 페이지 테이블 항목의 길이를 32비트에서 64비트로 증가.

이 증가로 페이지 테이블과 페이지 프레임의 기저 주소를 나타내는 비트 수가 20비트에서 24비트로 확장.

12비트 오프셋과 결합하면 총 36비트 주소 공간을 제공.

36비트 물리 주소는 총 64GB의 물리 메모리에 접근 가능.

PAE 활용을 위해서는 운영체제 지원이 필요.

Linux와 Intel macOS는 PAE를 지원.

32비트 Windows 데스크톱 운영체제는 PAE 기능이 활성화되어도 여전히 4GB 물리 메모리 접근으로 제한되는 구조.

PAE는 2MB 페이지도 사용할 수 있는 기능.

 

x86-64

Intel의 초기 64비트 진입은 IA-64 구조였으나 널리 채택되지 못한 구조.

IA-64는 나중에 Itanium이라는 이름으로 알려진 구조.

AMD는 x86-64라는 64비트 구조를 개발하여 성공적인 확장을 제공.

x86-64는 IA-32 명령어 집합의 확장을 기반으로 하는 구조.

역사적으로 AMD가 Intel 기반 칩을 만들어 왔지만, x86-64에서는 Intel이 AMD의 구조를 채택한 상황.

이 장에서는 AMD64나 Intel 64 같은 상표명 대신 일반적인 x86-64 용어 사용.

x86-64는 IA-32보다 훨씬 큰 논리 주소 공간과 물리 주소 공간 지원.

64비트 주소는 이론적으로 2의 64승 바이트 규모의 메모리 접근 가능.

그러나 현실의 64비트 시스템은 전체 64비트를 모두 주소 표현에 사용하지 않는 구조.

x86-64는 현재 4KB, 2MB, 1GB 페이지를 지원.

x86-64는 48비트 가상 주소 공간을 위한 4단계 페이지 테이블 사용.

48비트 가상 주소는 

page map level 4, 페이지 디렉터리 포인터 테이블, 페이지 디렉터리, 페이지 테이블, 오프셋으로 나뉘는 구조.

 

선형 주소의 0~11비트는 페이지 오프셋.

12~20비트는 페이지 테이블 인덱스.

21~29비트는 페이지 디렉터리 인덱스.

30~38비트는 페이지 디렉터리 포인터 테이블 인덱스.

39~47비트는 page map level 4 인덱스.

48~63비트는 현재 미사용 비트.

x86-64는 PAE를 사용할 때와 비슷하게 가상 주소는 48비트지만 52비트 물리 주소 공간을 지원.

52비트 물리 주소 공간은 4096TB 규모.

 

사례: ARM 구조

Intel 칩은 오랫동안 개인용 컴퓨터 시장을 주도했지만, 

스마트폰과 태블릿 같은 이동 장치 컴퓨터는 ARM 처리기를 많이 사용하는 구조.

Intel은 칩 설계와 제조를 모두 담당하지만, ARM은 구조 설계와 라이선스 제공을 중심으로 하는 모델.

ARM은 구조 설계를 이용해 칩을 만들 수 있는 허가를 칩 제조회사에 제공하는 방식.

Apple은 iPhone과 iPad를 위해 ARM 설계 라이선스를 받은 사례.

대부분의 Android 기반 스마트폰도 ARM 처리기를 사용하는 구조.

ARM은 모바일 장치뿐 아니라 실시간 임베디드 시스템을 위한 아키텍처 디자인도 제공.

ARM 아키텍처가 실행되는 장치는 매우 많고, 생산된 ARM 프로세서 수는 1,000억 개가 넘는 수준.

이 절은 64비트 ARMv8 아키텍처의 주소 변환 구조에 대한 설명.

ARMv8에는 4KB, 16KB, 64KB의 세 가지 변환 단위가 존재.

변환 단위는 translation granule이라는 용어.

각 변환 단위는 페이지 크기뿐 아니라 region이라 부르는 더 큰 연속 메모리 영역도 제공.

4KB 변환 단위에서는 페이지 크기 4KB, region 크기 2MB와 1GB 제공.

16KB 변환 단위에서는 페이지 크기 16KB, region 크기 32MB 제공.

64KB 변환 단위에서는 페이지 크기 64KB, region 크기 512MB 제공.

4KB와 16KB 변환 단위에서는 최대 4단계 페이징 사용 가능.

64KB 변환 단위에서는 최대 3단계 페이징 사용 가능.

ARMv8은 64비트 아키텍처이지만 현재는 48비트만 사용한다는 점에 주의.

TTBR 레지스터는 translation table base register의 약자.

TTBR은 현재 스레드의 레벨 0 테이블을 가리키는 변환 테이블 기본 레지스터.

 

4KB 변환 단위에서 네 단계 레벨을 모두 사용하면 주소의 0~11비트는 4KB 페이지 안의 오프셋.

레벨 1과 레벨 2 테이블 항목은 다음 레벨 테이블을 참조할 수도 있고, 

큰 region을 직접 참조할 수도 있는 구조.

레벨 1 테이블 항목이 레벨 2 테이블이 아니라 1GB region을 참조하면 

하위 30비트가 1GB region 안의 오프셋으로 사용.

레벨 2 테이블 항목이 레벨 3 테이블이 아니라 2MB region을 참조하면 

하위 21비트가 2MB region 안의 오프셋으로 사용.

ARM 아키텍처는 두 가지 수준의 TLB를 지원.

내부 레벨에는 데이터용 마이크로 TLB와 명령어용 마이크로 TLB가 존재.

마이크로 TLB는 ASID를 지원하는 구조.

외부 레벨에는 단일 메인 TLB가 존재.

주소 변환은 마이크로 TLB 수준에서 시작.

마이크로 TLB에서 미스가 발생하면 메인 TLB를 확인하는 흐름.

마이크로 TLB와 메인 TLB에서 모두 미스가 발생하면 하드웨어가 페이지 테이블 순회를 수행하는 구조.