1. 배경

메모리는 각각 주소가 할당된 일련의 바이트들로 구성됩니다. CPU는 PC(program counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추가적인 데이터를 더 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수 있습니다.

앞서 정리했던 것처럼 명령어는 몇 단계에 걸쳐서 실행됩니다.

1. 명령어 인출
2. 명령어 해독
3. 필요한 데이터 가져오기
4. 명령어 실행
5. 결과 저장

이러한 작업을 수행하는 동안 CPU와 메모리 그리고 레지스터들이 개입해서 수행을 합니다. 특히나, CPU의 연산 속도는 메모리 관련 작업보다 빠르기 떄문에 메모리를 어떻게 관리하는지는 성능적인 측면에서도 매우 중요한 부분입니다.

다중 프로그래밍의 경우에는 여러 프로세스들을 병행적으로 실행하므로 서로가 사용하는 메모리들을 독립적으로 관리하고 할당해주는 작업도 중요합니다.

1.1. 기본 하드웨어

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

기계 명령어들은 메모리 주소만을 인수로 취하고, 디스크의 주소를 인수로 취하지 않습니다.

만약 데이터가 메모리에 없다면 CPU가 그것들을 처리하기 전에 메모리로 이동시켜야 합니다.

레지스터에 접근하는 것은 CPU 클록(clock)의 1사이클(cycle) 내에 접근이 가능하지만, 메인 메모리에 접근하는 것은 이보다 더 많은 시간이 요구됩니다.

따라서, 이와 같은 성능적인 문제를 해결하기 위해서 캐시 메모리를 추가해서 사용하는 것입니다.

운영체제가 CPU와 메모리 간의 접근 중에 개입하게 되면 성능이 떨어지기 때문에 이러한 보호 기법은 반드시 하드웨어어가 지원해야 합니다.

이러한 상황의 발생을 피하기 위해서 우선 각 프로세스가 "독립된 메모리 공간"을 가지도록 보장해야 합니다.

이것을 위해서 두 개의 레지스터를 사용합니다.

• 기준 레지스터: 가장 작은 합법적인 물리 메모리 주소의 값을 저장
• 상한 레지스터: 주어진 영역의 크기를 저장

만약, 사용자가 다른 메모리 공간에 접근을 시도한다면 운영 체제는 이를 치명적인 오류로 간주하고 트랩(trap)을 발생시킵니다.

기준과 상한 레지스터는 여러 가지 특권 명령(special priviledged instruction)을 사용하는 운영체제에 의해서만 적재(load)됩니다.

사용자 모드는 할당 받은 메모리 영역에서만 동작을 수행할 수 있지만, 커널 모드는 이러한 제약을 받지 않는다는 것을 명심하자.

1.2 주소의 할당

프로그램은 원래 이진 실행 파일 형태로 디스크에 저장되어 있습니다.

실행하려면 프로그램을 메모리로 가져와서 프로세스 문맥 내에 배치해야 합니다.

각각의 바인딩 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것입니다.

• 컴파일 시간(compile time) 바인딩: 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있습니다.
• 적재 시간(load time) 바인딩: 만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능 코드로 만들어야 합니다. 이 경우 심볼과 진짜 번지수의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어집니다.
• 실행 시간(execution time) 바인딩: 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 우리는 바인딩이 실행 시간까지 허용되었다고 이야기합니다. 특별한 하드웨어를 이용해야 합니다.

주소의 단계별 변화를 적재 순간에 맞춰서 정리하면 다음과 같습니다.

1. 심볼 형태(주소)
2. 재배치 가능 주소
3. 절대 주소

컴파일러, 링커, 로더 전부 메인 메모리 상에서 실행되며, 앞서 언급했지만 CPU는 2차 저장장치에 접근하지 않습니다. 따라서, 소스 프로그램과 오브젝트 파일, 실행 파일도 메모리 상에 올라가긴 합니다. 하지만, 최종적으로 프로그램이 사용하는 메모리 영역이 아닌 컴파일러와 링커, 로더가 작업을 수행하기 위한 메모리 영역에 올라가는 것입니다.

1.3 논리 대 물리 주소 공간

CPU가 사용하는 주소는 두 가지로 나뉩니다.

• 논리 주소(logical address): CPU가 생성하는 주소, 프로그램에 할당되는 주소
• 물리 주소(physical address): 메모리가 취급하게 되는 주소[즉, 메모리 주소 레지스터(MAR)에 주어지는 주소]

컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같습니다.

그러나 실행 시간 바인딩 기법에서는 논리 주소, 물리 주소가 다릅니다.

이러한 논리 주소를 가상 주소(virtual address)라고 합니다.

프로그램 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 관리 장치(memory management unit, MMU)에 의해 실행됩니다.

아주 간단한 메모리 접근 방식은 기준 레지스터(base register) 기법을 일반화시킨 아주 단순한 MMU 기법을 사용하는 것입니다.

⚡️ 여기선 기준 레지스터를 재배치(relocation) 레지스터라고도 부릅니다.

논리 주소를 재배치 레지스터 값 + 오프셋(offset)의 조합으로 만들어서 사용하는 것입니다.

1.4 동적 적재

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

이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 적재됐는지를 조사합니다. 만약 적재되어 있지 않다면, 재배치 가능 연결 적재기(relocatable linking loader)가 불려 요구된 루틴을 메모리로 가져오고, 이러한 변화를 테이블에 기록해 둡니다.

그 후 CPU 제어는 중단되었던 루틴으로 보내집니다.

동적 적재의 장점은 루틴이 "필요한 경우에만 적재"된다는 것입니다.

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

동적 연결 라이브러리(DLL)는 시스템 프로그램이 실행될 떄, 사용자 프로그램에 연결되는 시스템 라이브러리입니다.

동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌었지만 동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것입니다. 동적 연결은 주로 표준 C 언어 라이브러리와 같은 시스템 라이브러리에 사용됩니다.

DLL은 다음과 같은 장점을 가지고 있습니다.

1. 메모리 절약: 필요한 경우에 메모리에 적재하여 사용
2. 라이브러리 공유: 여러 프로세스 간에 공유, 여러 프로그램이 동일한 라이브러리의 단일 복사본을 공유할 수 있어 메모리 사용을 최적화할 수 있습니다.
3. 버전 업데이트 유용: 어느 때나 새로운 버전으로 교체될 수 있다.

운영 체제는 이러한 메모리들을 관리하면서, 한 프로세스 만의 영역과 공유하는 영역을 구분하고 보호해 줍니다.

동적 적재와 동적 연결의 차이를 명확히 구분하고 갑시다.

• 적용 시점과 범위: 동적 적재는 프로그램이 실행 중에 특정 모듈을 필요로 할 때 수동으로 적재하는 것에 초점을 맞춥니다. 반면, 동적 연결은 실행 파일이 실행될 때 필요한 외부 라이브러리와의 연결을 자동으로 수행합니다.
• 관리 주체: 동적 적재는 "개발자"가 프로그램 코드 내에서 직접 관리하며, 어떤 모듈을 적재할지 결정합니다. 동적 연결은 "운영 체제"나 "런타임 환경"이 관리하며, 필요한 라이브러리를 자동으로 찾아서 연결합니다.
• 메모리 공유: 동적 연결을 통해 여러 프로그램이 동일한 라이브러리의 메모리를 공유할 수 있지만, 동적 적재는 주로 "해당 프로그램 내에서만" 사용되는 모듈을 적재하는 데 사용됩니다.

자바에서 사용하는 "동적 로딩"의 경우 동적 적재의 대표적인 예시라고 볼 수 있습니다. 이 동적 로딩은 해당 프로세스에서만 유용하지 다른 프로세스에서 해당 모듈을 사용할 수 없습니다. 하지만, DLL은 프로세스의 주소 공간에 할당되지만, 운영 체제의 메모리 관리 기능을 통해 여러 프로세스 간에 공유될 수 있습니다.

2. 연속 메모리 할당

메모리는 일반적으로 두 개의 부분으로 나누어 집니다.

• 운영체제를 위한 것
• 사용자 프로세스를 위한 것

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원하기 때문에 할당하는 방법에 대해서 고민을 해봐야 합니다.

연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재가 되어야 빈 공간이 적을 것입니다.

할당하는 방식에 대해서 논의를 하기 전에 메모리 보호 문제부터 해결을 해봅시다.

2.1 메모리 보호

앞서 논의했던 방식으로 상한 레지스터와 재배치 레지스터를 활용하여 메모리를 보호할 수 있다고 언급했습니다.

MMU는 동적으로 논리 주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 수행합니다. 이것이 할당된 범위에 있는지 확인함으로써 서로의 메모리를 보호할 수 있었습니다.

CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 문맥 교환의 일환으로 재비치 레지스터와 상한 레지스터에 정확한 값을 적재합니다.

CPU에 의해서 생성되는 모든 주소는 이 "레지스터들의 값"을 참조해서 확인 작업을 거치기 떄문에, 다른 프로그램으로부터 보호를 할 수 있습니다.

2.2 메모리 할당

메모리 할당은 페이징이라는 기술을 사용하여 효율적으로 메모리를 할당해주지만, 우선 가장 간단한 방법으로 프로세스를 그대로 메모리에 연속적으로 할당하는 방식을 확인해 봅시다.

이것은 프로세스를 메모리의 가변 크기 파티션에 할당하는 방식으로 가변 파티션 기법이라고 합니다.

초기에 메모리에 프로세스를 전부 할당한 후에, 프로세스가 종료가 된다면 빈 공간(hole)이 생기게 됩니다. 문제는 이러한 hole의 크기가 프로세스보다 매우 작거나, 클 수 있다는 것입니다.

이러한 상황에서 프로세스를 여러 hole 중에서 하나를 선택해서 할당해줘야 하는데 이러한 문제를 동적 메모리 할당 문제(dynamic storage allocation problem)이라고 합니다.

이러한 문제에 대한 해결책은 여러 개가 제시되어 있고, 일반적인 3개의 기법을 확인해 봅시다.

1. 최초 적합: 검색 도중에 첫 번째로 발견한 사용 가능한 가용 공간을 할당합니다.
2. 최적 적합: 사용 가능한 공간 중에서 가장 작은 것을 택합니다. 전 리스트를 검색해야 합니다. 이 방법은 아주 작은 가용 공간을 만들어 냅니다.
3. 최악 적합: 가장 큰 가용 공간을 택합니다. 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있습니다. 빈 공간들이 크기 순으로 정렬되어 있지 않다면 전 리스트를 검색해야 합니다.

모의실험을 통해서 연구해 보면 최조 적합과 최적 적합 모두가 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋다는 것이 입증되었다고 합니다. 공간 효율성 측면에서는 어느 것이 항상 더 좋다 말하기 힘들며, 속도 측면에서는 최초 적합이 더 빠릅니다.

2.3 단편화

최초 적합과 최적 적합 전략 모두 외부 단편화(external fragmentation)로 인해 어려움을 겪습니다.

외부 단편화는 메모리 내의 가용 공간(hole)들이 여러 작은 조각들로 흩어져 있는 것을 의미합니다.

실제로 이러한 단편화 떄문에 손실 비율은 매우 높으며, 이러한 할당 방식은 적합하지 않습니다.

이러한 문제를 해결하기 위해서 메모리를 미리 일정한 크기로 잘라놓고 정수 배로 할당해주는 방식을 고려할 수 있습니다.

물론, 이러한 상황에서도 마지막 조각에서 빈 공간이 발생할 수 있으며 이것을 내부 단편화(internal fragmentation)이라고 합니다.

외부 단편화 문제를 해결하는 방법으로는 압축(compaction)이 있습니다.

압축은 모든 가용 공간들을 한 군데로 몰아서 하나의 큰 블록으로 만드는 것으로 "재배치" 기법이 사용됩니다.

압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하며, 가능하더라도 그 비용을 검토해봐야 합니다.

우리는 컴퓨터 시스템에서 가장 일반적인 메모리 기법으로 사용되는 페이징에 대해서 살펴볼 필요가 있습니다.

3. 페이징

페이징은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법을 말합니다.

여기서 핵심적인 부분은 더이상 물리 메모리를 할당하는 과정에서 "연속적"으로 나누어 줄 필요가 없다는 것입니다.

논리 주소 공간을 나누어 놓고, 이 공간마다 메모리를 할당해주면 되기 때문에 물리 메모리에서 해당 크기의 가용 공간이 마련되면 할당해주면 됩니다.

3.1 기본 방법

물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어집니다.

논리 메모리는 페이지(page)라고 불리는 같은 크기의 블록으로 나누어 집니다.

프로그램은 메모리 프레임 혹은 프레임 묶음인 클러스터와 동일한 크기의 고정 크기 블록의 형태로 예비 저장장치에 저장되어 있으며, 프로세스가 실행될 때 그 프로세스의 페이지는 파일 시스템 또는 예비 저장장치로부터 가용한 메인 메모리 프레임으로 적재되는 것입니다.

간단하게 정리하자면, 메인 메모리는 프레임으로 나누어져 있고, 예비 저장장치에는 프레임 혹은 묶음 형태 크기의 블록으로 데이터들이 저장되어 있는 것입니다.

CPU에서 나오는 모든 주소는 페이지 주소(p)와 페이지 오프셋(d: offset) 두 개의 부분으로 나누어집니다.

페이지 번호는 프로세스 페이지 테이블(page table)을 액세스할 때 사용됩니다.

논리 주소를 물리 주소로 변환하기 위해서 MMU가 동작하는 단계를 간단하게 요약해봅시다.

1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용합니다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출합니다.
3. 논리 주송의 페이지 번호 p를 프레임 번호 f로 바꿉니다.
4. 프레임 번호 f와 오프셋 d를 이용해서 물리 메모리 주소를 찾습니다.

페이지의 크기: 2의 거듭제곱($2^n$), 일반적으로 4KB ~ 1GB 사이입니다.

페이징 자체는 일종의 동적 재배치입니다. 페이징 기법을 사용하면 외부 단편화가 발생하지 않습니다. 그러나 내부 단편화가 발생하게 됩니다.

단편화의 크기를 줄이기 위해서 페이지 크기를 줄이는 방법을 고려할 수 있지만, 이것은 페이지의 개수가 늘어나게 되면서 페이지 테이블의 크기가 커지게 됩니다.

여러 운영 체제에서는 여러 개의 페이지 크기도 허용합니다. 작은 페이지와 대형 페이지를 같이 사용할 수도 있습니다.

할당된 논리 주소는 연속적일 수 있겠지만, 물리 주소는 "연속적이지 않아도 된다"는 것에 명심하자. 이것은 주소 변환 하드웨어가 중간에 동작을 함으로써 가능케 해줍니다.

운영체제는 물리 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 합니다.

프레임 테이블(frame table)은 시스템에 하나밖에 없는 자료구조로 다음과 같은 정보들을 담고 있습니다.

• 어느 프레임이 할당되어 있는지
• 어느 프레임이 사용 가능한지
• 총 프레임은 몇 개가 되는지
• 등등

또한, 프레임 테이블은 각 프레임당 "하나의 항목"을 가지고 있으며 다음과 같은 정보들을 담고 있습니다.

• 프레임이 비어 있는지,
• 할당 되었는지
• 할당 되었다면 어느 프로세스의 어느 페이지에 할당되었는지

운영 체제는 프로세스마다 명령 카운터와 레지스터의 사본을 유지하는 것 처럼 페이지 테이블 사본도 유지합니다.

페이지 테이블 사본을 유지하는 이유는 각 프로세스의 논리 주소가 독립적으로 사용되기 때문입니다.

예를 들어, 두 프로세스가 같은 크기의 논리 주소 영역으로 0 ~ 1024만큼 할당받을 수 있고 이것은 겹치는 영역인 것 같지만, 실제로 물리 메모리에 할당할 때는 서로 다른 프레임에 할당되기 때문에 프로세스 별로 테이블을 나눠서 관리하는 것입니다.

이렇게 나눠서 관리를 하는 덕분에 같은 숫자의 페이지 번호여도 서로 다른 프로세스 테이블임을 확인할 수 있기 때문에 운영체제는 서로 다른 페이지를 독립적으로 관리할 수 있습니다.

3.2 하드웨어 지원

페이지 테이블은 프로세스별 자료구조이므로 페이지 테이블에 대한 포인터는 각 프로세스의 프로세스 제어 블록(PCB)에 다른 레지스터 값과 함께 저장됩니다.

CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터를 다시 적재하고 저장된 사용자 페이지 테이블로부터 적절한 하드웨어 페이지 테이블값을 다시 적재해야 합니다.

페이지 테이블을 전용 고속 하드웨어 레지스터 세트로 구현할 수 있지만, 현대의 CPU는 크기가 매우 큰 페이지 테이블을 지원하기 때문에, 이러한 경우에 빠른 레지스터를 사용하는 것은 부적절합니다.

따라서, 대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터(page-table base register, PTBR)로 하여금 페이지 테이블을 가리키도록 합니다.

3.2.1 Translation Look-Aside Buffer(TLB)

PTBR을 사용한다면 페이지 테이블을 메인 메모리에 저장하기 때문에 주소 값을 얻어오기 위해서 메모리에 접근을 해야 합니다.

즉, 1번의 접근에 메인 메모리로부터 주소를 얻어오며, 다시 1번의 접근을 한 후에야 비로소 데이터에 액세스를 할 수 있습니다. 총 2번의 액세스 과정 끝에 메모리 액세스를 할 수 있습니다. 이것은 일반적인 메모리 접근 시간을 2배로 느려지게 만듭니다.

이 문제에 대한 해결에는 TLB(translation look-aside buffers)라고 불리는 특수한 소형 하드웨어 캐시가 사용됩니다.

TLB내의 각 항목은 "키(key)"와 "값(value)"의 두 부분으로 구성됩니다.

• 키(key): 페이지 번호
• 값(value): 프레임 번호

TLB 검색을 명령어 파이프라인의 일부로 동작하며 성능에 추가적인 손해를 끼치지 않습니다. 그러나 파이프라인 단계 동안 검색을 하기 위해서는 TLB의 크기는 작게 유지할 수 밖에 없으며 통상 32개 ~ 1024개의 항목을 유지합니다.

현재는 여러 층의 TLB를 가진 시스템으로 발전한 것을 알 수 있습니다.

TLB를 사용하는 경우 MMU의 동작은 다음과 같습니다.

1. CPU가 논리 주소를 생성하면 MMU는 해당 페이지가 TLB에 있는지 확인
2. 페이지 번호가 발견되면 해당 프레임 번호를 즉시 알 수 있고 메모리에 접근하는데 사용
3. TLB 미스가 발생하면 페이지 테이블에 대한 메모리 참조 후 TLB에 추가

몇몇 TLB는 특정 항목들을 TLB에 고정하는데, 이러한 항목들은 TLB에서 제거될 수 없습니다. 보통 중요 커널 코드를 TLB에 저장합니다.

여기서 궁금할만한 부분은 TLB는 페이지 번호를 이용해서 프레임 번호를 반환하는데, 앞서 언급했던 것처럼 여러 프로세스가 같은 페이지 번호를 사용하는 경우 어떻게 식별해야 하는가입니다.

이것을 위해서 TLB는 각 항목에 ASIDs(address-space identifiers)를 저장하기도 합니다.

ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려주며 그 프로세스의 정보를 보호하기 위해 사용됩니다.

만약 ASID를 지원하지 않는다면 새로운 페이지 테이블이 선택될 때마다 TLB는 전부 플러시(Flush)가 되어야 합니다.

실제 TLB의 설계는 이보다 좀 더 복잡한데, Intel Core i7 CPU는 다음과 같이 TLB의 계층 구조를 가지고 있습니다.

• 128개의 항목을 가지는 L1 명령어 TLB
• 64개의 항목을 가지는 L1 데이터 TLB
• 512개의 항목을 가지는 L2 TLB

책에서 언급되어 있는 것은 L2 TLB를 검색하는데 6 CPU 사이클이 필요하며, 페이지 테이블 항목을 검색하면 수백 사이클이 필요하다고 합니다.

3.3 보호

페이징 환경에서 메모리 보호는 각 페이지에 붚어있는 보호 비트(protection bits)에 의해 구현됩니다. 이 비트들은 보통 페이지 테이블에 속해 있습니다.

이 비트를 통해 다음과 같은 상태를 정의할 수 있습니다.

• 읽고 · 쓰기
• 읽기 전용(read-only)

또한, 페이지 테이블 각 엔트리에는 유효/무효(valid/invalid) 비트가 더 있습니다.

• 유효(valid): 해당 페이지가 합법적인 페이지임을 나타낸다.
• 무효(invalid): 해당 페이지가 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.

프로세스가 자신의 모든 주소 범위를 늘 사용하는 경우는 드뭅니다. 사실 많은 프로세스들은 일정한 시간에는 단지 일부분만을 집중적으로 사용합니다.

몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(page table length register, PTLR)라는 레지스터를 제공합니다.

프로세스가 제서한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR 값과 비교됩니다. 이러한 검사에서 오류가 나타나면 트랩을 발생시킵니다.

3.4 공유 페이지

페이징의 장점은 공통의 코드를 공유할 수 있다는 점입니다.

실제로 여러 운영 체제들은 공통적으로 사용되는 라이브러리를 필요로 하는 경우가 있으며, 이러한 경우 라이브러리의 사본을 각 프로세스가 주소 공간에 적재해서 사용한다면 비효율적입니다.

코드가 재진입 코드인 경우 아래와 같이 공유해서 사용할 수 있습니다.

재진입 코드는 자체 수정을 할 수 없는 코드로서 실행 중에는 절대 변경되지 않습니다.(읽기 전용) 따라서 두 개 이상의 프로세스가 동일한 코드를 동시에 실행할 수 있습니다.

표준 라이브러리는 하나의 사본만 저장되면 되고, 각 사용자 프로세스의 페이지 테이블은 동일한 물리적 사본으로 매핑시킵니다. 이렇게 함으로써 실제로 라이브러리를 물리 메모리에 한번만 할당하면서 효율적으로 메모리를 사용할 수 있게 됩니다.

4. 페이지 테이블의 구조

여기서는 페이지 테이블을 구성하는 몇 가지 방법에 대해서 살펴볼 것입니다.

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

4.1 계층적 페이징

현대 컴퓨터는 매우 큰 주소 공간을 갖습니다.($2^{32}$ ~ $2^{64}$)

이러한 환경에서는 페이지 테이블도 상당히 커집니다. 이러한 경우에 모든 페이지 테이블을 연속적으로 할당하는 방법은 적합하지 않습니다.

생각해볼 수 있는 한 가지 방법은 2단계 페이징 기법(two-level paging scheme)으로서 페이지 테이블 자체가 다시 페이징되게 하는 것입니다.

이러한 경우에는 논리 주소는 하나의 페이지 번호가 아닌 2개의 페이지 번호로 구성되게 됩니다.

만약, 32비트의 주소 체계를 사용하고 있다면 다음과 같이 나눠질 수 있을 것입니다.

p1	p2	페이지 오프셋
10	10	12

여기서 p1은 바깥 페이지 테이블의 인덱스이고, p2는 안쪽 페이지 테이블의 페이지 내의 오프셋입니다.

이 방식에서는 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 이 방식을 foward-mapped 페이지 테이블이라고 합니다.

이러한 방식은 64비트의 논리 주소 공간을 가진 시스템에서는 적합하지 않습니다.

간단하게 말하자면, 64비트의 주소 체계는 2단계로 나누어도 매우 크므로 막대한 양의 메모리가 여전히 요구됩니다.

이를 위해서 더 많은 계층 관계를 고려해야 되는데 이것은 너무 많은 메모리 접근을 필요로 하기 때문에 비현실적입니다. 따라서 64비트의 구조에서는 계층적 페이지 테이블이 부적합하다는 것을 알 수 있습니다.

4.2 해시 페이지 테이블

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

해시 페이지 테이블의 "각 항목"은 연결 리스트를 가지고 있습니다.

각 원소는 "세 개의 필드"를 가지고 있습니다.

1. 가상 페이지 번호
2. 사상되는 페이지 프레임 번호
3. 연결 리스트상의 다음 원소 포인터

알고리즘의 동작은 다음과 같습니다.

1. 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱합니다.
2. 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교합니다.
3. 일치되면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻습니다.
4. 일치되지 않으면 그다음 원소로 2번을 반복합니다.

64비트 시스템에서 유용하도록 변형된 해시 테이블 기법이 제안되었습니다. 이 기법은 해시 테이블과 비슷한 클러스터 페이지 테이블을 사용합니다.

해시 페이지 테이블의 각 항목이 한 개의 페이지만 가리키는 것에 반해 "클러스터 페이지 테이블의 각 항목"은 여러 페이지를 가리킵니다.

따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 변환 정보를 지닐 수 있습니다.

따라서 클러스터 페이지 테이블은 성긴 주소 공간에서 유용하게 사용됩니다.

⚡️ 성긴 주소 공간 ⚡️

성긴 주소 공간(Sparse address space)은 프로세스의 주소 공간 내에서 실제로 "사용되는 메모리 영역"과 "사용되지 않는 메모리 영역"이 혼재하는 구조를 의미합니다. 즉, 전체 가능한 주소 공간 중에서 실제로 메모리에 매핑되고 사용되는 부분이 흩어져 있고, 대부분의 주소 공간은 비어 있는(할당되지 않은) 상태를 나타냅니다.

성간 주소 공간의 특징

• 비효율적인 메모리 사용: 프로세스의 주소 공간은 크지만 실제로 사용하는 영역이 작은 경우에 많은 메모리 영역이 낭비가 됩니다.
• 동적 할당의 용이성: 동적으로 메모리를 할당하고 해제하는 운영 방식에서 적합하며, 메모리 사용 시간에 따라 변하는 응용 프로그램에 유용합니다.
• 가상 메모리 관리: 성긴 주소 공간은 가상 메모리 시스템에서 자주 보입니다. 운영 체제는 실제 물리 메모리보다 더 큰 주소 공간을 프로세스에 제공합니다. 필요할때마다 메모리를 할당받아 사용하고, 사용되지 않는 메모리 영역은 실제 물리 메모리를 차지하지 않습니다.

성긴 주소 공간의 예시

• 대규모 배열 처리: 프로그램에서 큰 배열을 사용하되 실제로는 배열의 일부만 사용하는 경우, 배열 전체에 대한 주소 공간을 할당받지만 실제로 메모리에 매핑되는 것은 일부분입니다.
• 메모리 매핑 파일: 파일 내용을 메모리 주소 공간에 매핑하여 접근하는 경우, 전체 파일 크기에 비해 실제로 접근하는 부분은 소량일 수 있고, 이러한 접근 방식도 성긴 주소 공간의 한 형태입니다.

4.3 역 페이지 테이블

프로세스는 각자 하나씩 페이지 테이블을 가지고 또 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가집니다.

하지만, 이러한 방식의 단점 중 하나는 각 페이지 테이블 항목의 개수가 수백만 개가 될 수 있다는 것입니다.

이것이 무슨 말인지 헷갈리 수 있는데 이에 대한 자세한 설명은 이 파트 설명이 끝나고 정리하기로 하고, 중요한 점은 프로세스마다 각 페이지 테이블을 할당해줄 때 프로세스의 논리 주소 공간의 페이지 수만큼 엔트리가 있다는 것입니다.

이러한 문제를 해결하기 위한 한 방법이 역 페이지 테이블(inverted page table)입니다.

역 페이지 테이블에서는 메모리 프레임마다 한 항목씩을 할당합니다. 각 항목(엔트리)은 다음과 같은 정보를 담고 있습니다.

• 페이지 주소
• 페이지를 소유하고 있는 프로세스의 ID

여기서 중요한 것은 메모리 프레임마다 역 페이지 테이블의 "항목"을 할당해 놓는다는 점입니다.

즉, 프레임의 번호가 역 페이지 테이블 항목의 인덱스 역할을 수행한다고 생각하면 됩니다.

역 프레임 테이블은 하나만 존재하고 전역적으로 모든 프로세스가 사용하기 때문에 엔트리에 저장되는 요소로 주소 공간 ID(adress-space identifier)를 요구합니다.

역 페이지 테이블은 물리 주소에 따라 정렬되어 있고 탐색은 가상 주소를 기준으로 하므로 테이블 전체를 탐색하여야 할 수 있습니다.

그래서 이 문제를 해결하기 위하여, 해시 테이블을 사용할 수 있습니다. 물론 메모리 참조 횟수가 증가하기는 하지만 이를 위해서 TLB가 참조됩니다.

마지막으로 역 페이지 테이블을 사용하는 경우 한 번에 하나의 가상 주소만 공유 물리 주소에 매핑할 수 있습니다. 따라서 공유 메모리를 사용하면서 하나의 물리 메모리 영역만을 사용하는 방법을 사용할 수 없습니다.

추가적으로 정리를 하겠습니다.

우선, 역 페이지 테이블을 사용하면 전통적인 페이지 테이블 방식보다 메모리적인 측면에서 효율적이라고 합니다. 왜 이런 현상이 나오는 것일까요?

이를 이해하기 위해서 전통적인 페이지 테이블 방식을 한번 더 구체적으로 살펴볼 필요가 있습니다.

전통적인 페이지 테이블 방식의 메모리 사용

• 프로세스별 독립적인 페이지 테이블: 각 프로세스는 자신만의 페이지 테이블을 가집니다. 이는 프로세스의 가상 주소 공간 전체에 대한 매핑 정보를 포함해야 하므로, 실제 사용되는 메모리 양에 비해 상대적으로 큰 메모리 공간을 차지할 수 있습니다.
• 조각화 문제: 프로세스가 사용하는 가상 주소 공간이 흩어져 있거나(sparse), 작은 메모리 영역만을 활발히 사용하는 경우, 많은 페이지 테이블 엔트리가 실제로는 사용되지 않을 수 있습니다.

즉, 전통적인 페이지 테이블 방식은 각자의 페이지 테이블에 프로세스의 가상 주소 공간에 대한 매핑 정보를 가지고 있고, 사용하지 않는 매핑에는 유효하지 않는 값을 가지는 형태로 구성되어 있는 것입니다.

역 페이지 테이블 방식을 한번 살펴봅시다.

역 페이지 테이블 방식의 메모리 사용

• 전역 페이지 사용: 역 페이지 테이블은 모든 프로세스의 매핑 정보를 하나의 전역 테이블에서 관리합니다.
• 메모리 절약: 역 페이지 테이블은 "실제로" 물리 메모리에 할당된 프레임에 대한 정보만을 관리합니다. 따라서, 실제 사용되는 메모리 영역에 대해서만 엔트리를 유지하게 되므로, 전통적인 방식에 비해 더 적은 메모리를 사용할 수 있습니다.

실제로 사용하는 물리 메모리의 프레임을 이용해서 전역 페이지 테이블을 구성해놓기 때문에 전통적인 페이지 테이블과 다르게 가상 주소 영역에 맞춰서 테이블을 구성할 필요가 없습니다.

5. 스와핑

프로세스가 실행되기 위해서는 프로세스의 "명령어"와 명령어가 접근하는 "데이터"가 메모리에 있어야 합니다.

하지만 다중 프로그래밍에서 메모리 제한에 맞춰서 정도를 설정한다면 여러 프로세스를 동시에 실행하기 힘들 수 있습니다.

따라서 필요한 명령어 혹은 데이터만 메모리에 올려두고, 저장 공간을 효율적으로 사용하여 여러 프로세스를 동시에 실행할 수 있도록 해줄 수 있습니다.

5.1 표준 스와핑

표준 스와핑에는 메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동합니다.

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

백업 저장장치는 크기가 충분히 커야하며, 메모리 이미지에 직접 액세스 할 수 있어야 합니다.

프로세스 또는 일부가 백업 저장장치로 스왑될 때, 데이터 구조와 필요에 따라 프로세스에 대한 메타제이터도 저장되어야 합니다.

표준 스와핑의 장점은 실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있도록 물리 메모리가 초과 할당될 수 있다는 것입니다.

5.2 페이징에서 스와핑

표준 스와핑은 기존 UNIX 시스템에서 사용되었지만 메모리와 백업 저장장치 간에 "프로세스 전체"를 이동하는 데 걸리는 시간이 엄청나기 때문에 일반적으로 최신 운영체제에서는 더는 사용되지 않습니다.

대부분의 시스템은 이제 프로세스 전체가 아닌 프로세스 페이지를 스왑할 수 있는 변형 스와핑을 사용합니다.

이 전략은 여전히 물리 메모리를 초과 할당할 수 있지만 프로세스 전체를 스왑하는 비용은 발생하지 않는다.

실제로, 스와핑이란 용어는 일반적으로 표준 스와핑을 말하며,

페이징은 페이징에서의 스와핑을 의미한다. 페이지-아웃 연산은 페이지를 메모리에서 백업 저장장치로 이동시킨다. 반대 방향의 연산을 페이지-인이라고 합니다.

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

PC와 서버 대부분의 운영체제는 페이지 스와핑을 지원합니다.

이와는 대조적으로 모바일 시스템은 어떠한 스와핑도 지원하지 않는 것이 일반적입니다.

스와핑을 피하는 이유로 다음과 같은 것들이 있습니다.

1. 플래시 메모리를 하드 디스크 대신에 사용한다. 플래시 메모리는 쓰기 횟수 제한이 있기 때문에 스와핑이 비효율적이다.
2. 배터리 수명이 빠르게 소모된다.

그렇다면 어떻게 메모리 사용량과 프로세스의 사용을 조율할까요?

모바일 기기의 메모리 관리 시스템은 이를 위해 여러 가지 방법을 지원하며, 여기서 주요 매커니즘을 살펴보겠습니다.

1. 백그라운드 앱의 상태 관리

모바일 운영체제는 실행 중인 앱들 사이에서 메모리를 효율적으로 분배하기 위해, 포그라운드와 백그라운드 앱의 우선순위를 구분합니다.

사용자가 새로운 앱을 실행할 때 시스템은 메모리를 확보하기 위해 백그라운드에 있는 앱들의 상태를 조정할 수 있습니다.

2. 메모리 경고 및 자동 종료

모바일 운영체제는 메모리 사용량이 높아지면 메모리 경고를 발생시킵니다. 이때, 백그라운드 앱들에게 메모리를 해제하도록 요청할 수 있습니다.

만약 이러한 경고에도 불구하고 충분한 메모리가 확보되지 않으면, 시스템은 가장 우선순위가 낮은 백그라운드 앱부터 종료하기 시작하여 필요한 메모리를 확보합니다.

3. 앱의 생명주기 관리

모바일 운영체제는 앱의 생명주기를 관리하여, 앱이 백그라운드로 이동할 때 일부 자원을 해제하고, 필요할 때 다시 자원을 할당받을 수 있도록 합니다.

이는 앱이 사용하지 않는 메모리를 최소화하고, 시스템 자원을 효율적으로 사용할 수 있도록 돕습니다.

4. 저메모리 킬러(Low Memory Killer)

안드로이드와 같은 모바일 운영체제는 "저메모리 킬러(Low Memory Killer)"라는 매커니즘을 구현하여, 시스템의 사용량이 임계값에 도달하면 자동으로 백그라운드 프로세스를 종료합니다.

이는 메모리 사용량을 관리하고 시스템 안정성을 유지하는 데 중요한 역할을 합니다.

6. 사례: Inter 32비트와 64비트 구조

여기서는 Windows, macOS 및 Linux 등 가장 유명한 모든 PC 운영체제들이 사용하는 Intel 칩이 사용하는 메모리 관리에 대해서 알아볼 것입니다.

6.1 IA-32 구조

IA-32 시스템의 메모리 관리는 세그멘테이션과 페이징의 두 부분으로 나눌 수 있습니다.

• CPU는 "논리 주소"를 생성한 후 세그멘테이션 장치에 전달
• 세그멘테이션 장치는 논리 주소에 상응하는 "선형 주소"를 생성한 후 페이징 장치에 전달
• 페이징 장치는 선형 주소를 메인 메모리의 "물리 주소"로 변환합니다.

6.1.1 IA-32 세그멘테이션

IA-32 구조는 하나의 세그먼트가 최대 4GB의 크기를 가질 수 있으며 한 프로세스 당 16KB개의 세그먼트를 가질 수 있습니다.

각 프로세스의 주소 공간은 두 개의 파티션(partition)으로 나누어 집니다.

• 첫 번째 파티션: 해당 프로세스가 독점적으로 사용하는 8KB 세그먼트
• 두 번째 파티션: 모든 프로세스 사이에서 공유가 가능한 8KB 세그먼트

첫 번째 파티션에 대한 정보는 지역 디스크립터 테이블(local descriptor table, LDT)에 유지되며, 두 번째 파티션에 대한 정보는 전역 디스크립터 테이블(global descriptor table, GDT)에 저장됩니다.

논리 주소는 (selector, offset)의 쌍으로 구성되며, 셀렉터는 다음과 같이 16비트 수입니다.

s	g	p
13	1	2

여기서 s는 "세그먼트 번호"이고, g는 "세그먼트가 GDT인지 LDT"를 나타내며, p는 "보호(protection)와 관련된 정보"를 나타냅니다.

이 CPU는 6개의 세그먼트용 레지스터를 가지고 있어서 한 프로세스는 한 순간에 6개의 세그먼트를 가리킬 수 있습니다.

또한 LDT 또는 GDT를 저장할 수 있는 6개의 8B microprogram 레지스터를 가지고 있습니다.

IA-32는 이 캐시를 통해서 메모리 참조가 있을 때마다 메모리로부터 디스크립터를 매번 읽어 오는 것을 피할 수 있습니다.

IA-32에서 선형 주소의 길이는 32비트이며 다음과 같이 구성됩니다.

1. 세그먼트 레지스터가 LDT나 GDT 내의 적절한 항목을 가리킵니다.
2. 일단 찾고자 하는 세그먼트에 대한 "기준"과 "상한" 정보를 가져와서 실제 선형 주소(linear adderss)를 만들어내는 데 사용합니다.
   a. 주소의 타당성 검사를 합니다.
   b. 주소가 타당하다면 기준 값 + 오프셋 값으로 32비트 선형 주소를 생성

6.1.2 IA-32 페이징

IA-32 구조에서 페이지는 4 KB 또는 4 MB입니다. IA-32는 4KB 크기의 페이지를 사용할 때 2단계 페이징 기법을 사용합니다.

32 bits 선형 주소는 다음과 같이 나눌 수 있습니다.

p1(페이지 번호)	p2(페이지 번호)	d(페이지 오프셋)
10	10	12

10개의 상위 비트는 IA-32 구조에서 페이지 디렉터리(page directory)라고 부르는 "최상위 페이지 테이블 엔트리"를 가리킵니다.

페이지 디렉터리 엔트리는 다음 10개에 의해 인덱스 되는(indexed) "하나의 하위 페이지 테이블"을 가리킵니다.

마지막 하위 12비트는 페이지 테이블이 가리키고 있는 4KB의 페이지의 오프셋을 나타냅니다.

페이지 디렉터리의 엔트리에는 Page Size 플래그가 있는데 만약 값이 설정되면 "페이지 프레임"이 일반적으로 사용되는 4KB가 아니라 "4MB"라는 것을 의미합니다.

이 플래그가 설정되면 페이지 디렉터리는 하위 페이지 테이블을 가리키는 것이 아니라, 직접적으로 4MB 페이지 프레임을 가리키게 됩니다.

즉, 선형 주소의 하위 22비트는 4MB 페이지 프레임에서의 오프셋을 나타내게 됩니다.

물리 메모리 사용의 효율성을 높이기 위해 IA-32 페이지 테이블은 디스크로 스왑될 수 있다.

이런 경우에 페이지 디렉터리 엔트리가 가리키고 있는 페이지 테이블이 메모리 또는 디스크에 있는지 확인할 수 있어야 합니다.

이를 위해 invalid 비트를 사용합니다.

소프트웨어 개발자들은 IA-32 구조의 "4GB 메모리 제한"이 문제가 된다고 인식하기 시작했을 때 Intel은 32-비트 처리기가 4GB 보다 큰 물리 주소 공간에 접근할 수 있게 하는 페이지 주소 확장(page address extension, PAE)을 채택하였습니다.

PAE를 지원함으로써 발생한 근본적인 변화는 2-단계 기법에서 3-단계 기법으로 변경되었다는 것입니다.

3단계 기법에서 최상위 2비트는 페이지 디렉터리 포인터 테이블을 가리킵니다.

6.2 x86-64

용어의 유래는 여기서는 다루지 않겠습니다.

64-비트 시스템은은 $2^{64}$ 바이트의 메모리에 접근할 수 있고, 64비트를 이용해서 메모리 주소를 표현할 수 있지만, 실제로는 훨씬 적은 비트만이 주소 표현에 사용됩니다.

x86-64 구조는 현재 크기가 4KB, 2MB, 또는 1GB인 페이지를 지원할 수 있는 4단계 페이지 테이블을 사용하는 48-비트 가상 주소 공간을 지원합니다.

여기서는 ARM 구조는 다루지 않고 넘어가겠습니다.

참고한 자료

• 운영체제[공룡책]