[OS-반효경] Memory Management

지금까지 프로세스 관리와 CPU 관리에 대해 알아보았습니다. 이번 포스팅에서는 메모리 관리에 대해 정리해보겠습니다.

메모리는 ‘주소’를 통해 접근하고, 이때 운영체제가 다루는 주소는 논리 주소와 물리 주소로 나뉩니다.

논리 주소는 각 프로세스가 독립적으로 가지는 주소 공간으로, 프로그램이 실행된 이후 CPU가 생성하는 주소입니다. 반면 물리 주소는 실제 메모리 상에 데이터가 올라가 있는 위치를 의미합니다.

CPU가 만들어내는 논리 주소를 그대로 메모리에 사용할 수는 없기 때문에, 논리 주소를 물리 주소로 변환해주는 과정이 필요합니다.

Address Binding

주소 바인딩(Address Binding)은 논리 주소를 물리 주소로 변환(매핑)하는 과정입니다. 매핑 결정 시점에 따라 크게 Compile time, Load time, Run time 바인딩으로 나뉩니다.

Compile time binding

물리 메모리에서 실행 위치가 컴파일 시점에 이미 고정되어 있는 경우입니다. 컴파일러는 실제 물리 주소를 기준으로 절대 코드(Absolute code)를 생성할 수 있고, 실행 위치가 바뀌면 다시 컴파일해야 합니다.

Load time binding

컴파일 시점에는 실행 위치를 확정하지 않고, 프로그램을 메모리에 올리는 로딩 시점에 주소를 결정합니다. 이때 프로그램은 재배치 가능한(Relocatable) 형태로 만들어 두었다가, 로더가 실제 적재 주소에 맞춰 재배치 적용해 주소를 보정합니다. 단, 로딩이 끝난 뒤에는 실행 위치를 바꾸기 어렵습니다.

Run time binding

프로그램이 실행되는 이후에도 프로세스가 메모리 위치를 옮길 수 있는 경우입니다. 즉, 주소 바인딩이 실행 중에도 계속 일어나며 이를 위해 하드웨어(MMU 등)의 주소 변환 지원이 필요합니다.

Compile time/Load time 바인딩은 프로그램 시작 시 물리 주소가 결정되는 반면, Run time 바인딩은 프로그램 시작 이후에도 주소 변환이 계속 일어나 프로세스의 위치가 바뀔 수 있습니다.

Memory-Management Unit(MMU)

MMU는 논리 주소를 물리 주소로 변환해주는 하드웨어입니다.

논리 주소가 물리 주소로 변환되는 과정을 보여주는 사진입니다. relocation register는 이 프로세스가 메모리에서 시작하는 베이스 주소가 들어 있습니다.

CPU가 논리 주소로 346을 만들었다면, MMU는 베이스 주소와 논리 주소를 더해(14000 + 346 = 14346) 물리 주소를 14346에 위치시킵니다.

하지만 relocation register를 이용해 논리 주소를 물리 주소로 옮겨주는 것만 생각하면, 프로세스는 사실상 메모리 어디든 접근할 수 있게 됩니다. 예를 들어 잘못된 포인터나 버그로 인해 논리 주소가 비정상적으로 커지면, 다른 프로세스의 메모리 영역이나 심지어 운영체제 커널 영역까지 침범할 수 있습니다. 따라서 운영체제는 각 프로세스가 허용된 범위 안에서만 메모리를 접근하도록 해야 하고, 이 역할을 MMU가 지원합니다.

limit register는 해당 프로세스가 접근 가능한 논리 주소의 크기를 의미합니다. 논리 주소가 limit register보다 작으면 MMU는 베이스 주소와 논리 주소를 더해 물리 주소를 만들고, 그 주소로 메모리를 접근합니다. 반대로 논리 주소가 limit register 이상이면 주소 변환을 진행하지 않고, trap을 발생시켜 접근을 차단합니다.

MMU는 단순히 base + offset을 계산하는 장치가 아니라, 프로세스가 자신의 주소 공간 밖으로 나가는 순간 이를 즉시 막아 프로세스 간 격리와 커널 보호를 보장합니다.

Allocation of Physical Memory

메모리는 운영체제의 커널 영역과 사용자 프로세스 영역으로 나뉩니다. 사용자의 프로세스 영역 메모리 할당 방법에 대해 알아보겠습니다.

사용자 프로세스 영역 할당에는 연속 할당과 불연속 할당이 있습니다.

• Contiguous allocation(연속 할당): 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

  • Fixed partition(고정 분할) 방식
  • Variable partition(가변 분할) 방식

• Noncontiguous allocation(불연속 할당): 하나의 프로세스가 여러 영역에 분산되어 올라갈 수 있음

  • Paging
  • Segmentation
  • Paged Segmentation: Paging + Segmentation

Contiguous allocation(연속 할당)

연속 할당에는 고정 분할과 가변 분할 방식이 있습니다. 고정 분할 방식은 물리 메모리를 미리 나눠 프로그램을 적재하는 방식입니다. 고정 분할 방식은 동시에 메모리에 올라갈 수 있는 프로세스 수가 분할 개수로 고정되고, 분할 크기보다 큰 프로세스는 적재하지 못합니다.

가변 분할 방식은 프로그램의 크기를 고려하여 메모리를 할당합니다. 분할 크기와 개수가 동적으로 변하기 때문에 기술적 관리가 필요합니다.

메모리 할당에는 단편화(Fragmentation) 문제가 있습니다.

단편화는 내부 단편화와 외부 단편화가 있는데, 내부 단편화(Internal Fragmentation)는 분할 크기가 프로그램 크기보다 커서 메모리 낭비가 발생하는 상황입니다.

외부 단편화(External Fragmentation)는 메모리 할당·해제 반복으로 빈 공간(hole)이 흩어져 hole 여유가 있어도, 연속 공간을 못 찾아 할당이 실패하는 현상입니다.

그래서 가변 분할 방식에는 크기가 $n$인 요청을 만족하는 가장 적절한 hole을 찾는 문제(Dynamic Storage-Allocation Problem)가 있다.

• First-fit: 제일 처음 발견되는 hole에 할당
• Best-fit: 모든 hole을 살펴보고, 프로그램 크기와 가장 잘 맞는 hole에 할당 → 시간 부담이 있음
• Worst-fit: 모든 hole을 살펴보고, 가장 큰 hole에 프로그램 할당

Noncontiguous allocation(불연속 할당)

불연속 할당에는 Paging과 Segmentation이 있습니다.

Paging

Paging은 논리 주소 공간을 고정 크기 페이지로 나누고, 페이지 테이블로 이를 물리 메모리의 프레임에 매핑해 주소를 변환하는 메모리 관리 기법입니다.

페이지 테이블은 메인 메모리에 있고, Page-table base register(PTBR)과 Page-table length register(PTLR)를 이용하여 페이지를 프레임에 매핑합니다. Paging 기법은 페이지 테이블에 접근하고, 물리 메모리에 접근하기 때문에 2번의 메모리 접근 연산이 필요합니다. 이는 시간이 많이 걸리고 비용이 많이 들어서 외부 단편화를 줄여 메모리 활용도를 높일 수 있지만, 메모리 접근 오버헤드가 발생해 전체 성능 측면에서는 오히려 비효율이 커질 수 있습니다. 그래서 테이블 접근 시간을 줄이기 위해 Associative Register나 TLB(Translation Lookaside Buffer)를 활용하여 메모리 접근 오버헤드를 줄입니다.

CPU는 페이지 테이블 접근 전에 TLB 테이블을 먼저 접근합니다. TLB 테이블에 해당하는 주소 변환 정보가 없다면 페이지 테이블을 참조하고, TLB 테이블에 해당하는 주소 변환 정보가 있다면 페이지를 프레임과 매핑합니다. 따라서 TLB를 이용하면 메모리 접근 시간을 줄여줍니다.

또한 Associative Register를 사용하면 메모리 접근 시간을 더 줄여줄 수 있는데, Associative Register는 TLB 테이블에서 페이지 번호와 프레임 번호를 병렬 비교(연관 검색)하여 일치하는 프레임 번호를 빠르게 찾을 수 있습니다.

Two-Level Page Table

하지만 프로세스의 가상 메모리 공간이 커지면, 단일 페이지 테이블은 사용하지 않는 주소 영역까지 포함해 엔트리를 가져야 하므로 페이지 테이블 자체가 커져 메인 메모리 공간을 많이 차지하고 낭비가 발생할 수 있습니다. 이를 메인 메모리 공간을 줄이기 위해 Two-Level Page Table을 사용하며, 페이지 디렉터리(외부 디렉터리)를 통해 필요한 하위 페이지 테이블만 동적으로 생성하여 페이지 테이블이 사용하는 메모리와 낭비를 줄입니다.

또한 가상 주소 공간이 더 커지는 경우에는, Two-Level 구조만으로도 상위 테이블의 크기가 부담될 수 있습니다. 이때 페이지 테이블을 여러 단계로 나누는 Multi-Level Page Table을 사용하여, 필요한 하위 테이블만 단계적으로 생성함으로써 페이지 테이블이 차지하는 메모리를 더욱 줄일 수 있습니다.

Page Table Memory Protection

페이지 테이블은 메모리 보호를 위해 페이지 테이블 각 엔트리마다 Protection bit와 Valid-invalid bit를 설정합니다. Protection bit는 페이지에 대한 접근 권한을 설정합니다. → read/write/read-only

Valid-invalid bit는 해당 페이지가 현재 프로세스의 논리 주소 공간에서 유효한 페이지인지를 나타내는 비트입니다.

• valid(1): 해당 페이지가 프로세스의 논리 주소 공간에 포함되어 있으면 접근 허용(매핑된 프레임이 존재하거나 필요 시 적재 가능)
• invalid(0): 프로세스 논리 주소 공간에 속하지 않거나 아직 할당/적재되지 않은 페이지로, 물리 주소에 접근하면 trap 발생

Inverted Page Table

일반적인 페이지 테이블은 프로세스마다 존재하며, 페이지 번호마다 엔트리를 가져 프로세스의 가상 주소 공간이 커질수록 페이지 테이블 메모리 사용량이 증가합니다. 페이지 테이블 메모리 사용량을 줄이기 위해 Inverted Page Table을 사용합니다.

Inverted Page Table은 페이지 기준이 아니라 프레임 기준으로 테이블을 구성합니다. 즉, 시스템 전체에 하나의 테이블을 두고, 각 프레임마다 1개의 엔트리를 둡니다.

테이블 크기가 프레임 개수에 비례하므로, 가상 주소 공간이 매우 커져도 페이지 테이블 메모리 사용량이 크게 늘지 않습니다. 하지만 Inverted Page Table은 프레임 기준이라서, 페이지를 보고 프레임으로 바로 매핑하기 어렵습니다. 또한 프레임에 맞는 페이지 번호를 찾아야 하기 때문에 페이지 테이블을 전부 탐색해야 합니다.

Associative Register를 사용하면 테이블 탐색 시간을 줄일 수 있지만 비싸기 때문에 상황에 맞게 페이지 테이블 방법을 선택해야 합니다.

Shared Page

메모리를 더 효율적으로 사용하기 위해 Shared Page를 사용합니다. Shared Page는 여러 프로세스가 같은 물리 프레임을 함께 사용하는 방식으로, 대표적으로 공유 라이브러리(libc)나 동일한 코드 영역에 적용됩니다.

여러 프로세스가 같은 내용을 각각 메모리에 올리면 프레임이 중복해서 사용되지만, Shared Page를 사용하면 하나의 프레임을 여러 프로세스가 공통으로 참조하므로 메모리 사용량을 줄일 수 있습니다.

일반적으로 공유되는 페이지는 읽기 전용(read-only)으로 설정하여 한 프로세스의 수정이 다른 프로세스에 영향을 주지 않게 합니다. 만약 어떤 프로세스가 공유 페이지를 수정하려고 하면, 운영체제는 Copy-on-Write(COW)¹를 통해 그 프로세스만 사용할 새 프레임을 복사해 할당합니다.

Segmentation

Paging은 논리 주소 공간을 고정 크기 페이지로 나눴지만, Segmentation은 의미 단위로 논리 주소 공간을 나눕니다.

또한 각 Segmentation마다 protection bit가 있고, Segmentation은 의미 단위기 때문에 공유와 보안에 있어 Paging보다 효과적입니다.

Conclusion

메모리 관리에서 논리/물리 주소, MMU, 연속 할당, 불연속 할당 등 메모리 관리에 필요한 개념들에 대해 알아 보았습니다. 여기서 꼭 기억해야 하는 부분은 주소 변환은 운영체제가 아닌 하드웨어가 합니다. → MMU, Register, TLB..

다음 포스팅은 가상 메모리에 대해 자세히 알아 보겠습니다.

References

[1] KCOW 운영체제 반효경 강의

[2] Operating System Concepts(Silberschatz, Galvin and Gagne)

[3] 단편화