운영체제 파헤치기5 - 메모리 관리

개요

운영체제는 프로그램을 실행하기 위해 메모리에 적재하고, 종료된 프로그램을 메모리에서 삭제합니다. 단순히 적재하고 삭제하는 것을 넘어 낭비되는 메모리 용량이 없도록 효율적으로 메모리 관리를 수행합니다. 이를 위해 대부분의 현대 운영체제는 가상 메모리(Virtual Memory) 기술을 활용합니다.

 

논리 주소와 물리 주소

CPU와 프로세스는 직접 물리 주소(Physical Address)를 다루지 않습니다. 대신, 논리 주소(Logical Address) 라는 개념을 사용합니다.

• 논리 주소: 각 프로세스마다 0번지부터 시작하는 주소 체계로, 프로세스마다 같은 주소를 사용할 수 있습니다.
• 물리 주소: 실제 메모리(RAM)의 주소로, 논리 주소와 달리 중복되지 않고 고유합니다.

즉, 여러 프로세스가 각자의 논리 주소 공간을 가지지만, 실제로는 물리 주소에서 별개의 공간을 사용하게 됩니다.

CPU는 논리 주소를 사용하고, 메모리는 물리 주소를 사용하기 때문에 원활한 통신을 위해 메모리 관리 장치(MMU, Memory Management Unit)을 사용합니다. MMU는 CPU와 메모리 사이에서 논리 주소를 메모리가 이해하는 물리 주소로 변환합니다.

 

스와핑(Swapping)

운영체제는 여러 프로세스를 동시에 실행하지만, 메모리에 적재된 모든 프로세스가 항상 실행 상태인 것은 아닙니다. 입출력 작업을 기다리며 대기 상태가 되었거나 오랫동안 사용되지 않은 프로세스가 있을 수 있습니다.

이러한 프로세스를 일시적으로 보조기억장치의 특정 영역인 스왑 영역(Swap Space)으로 이동시키고, 프로세스를 이동시키고 확보된 메모리 공간에 다른 프로세스를 적재하여 실행하는 메모리 관리 방식을 스와핑(Swapping)라고 합니다.

• 스왑 아웃(Swap-Out): 실행 중이지 않은 프로세스를 메모리에서 스왑 영역으로 이동
• 스왑 인(Swap-In): 다시 필요해진 프로세스를 스왑 영역에서 메모리로 불러옴

이러한 과정을 통해 메모리를 보다 효율적으로 활용하고, 다수의 프로세스를 원활하게 실행할 수 있습니다.

 

연속 메모리 할당과 외부 단편화

아래 그림처럼 프로세스에 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당이라고 합니다.

물론 이러한 연속 메모리 할당은 메모리를 효율적으로 사용하는 방법은 아닙니다. 그 이유는 아래 그림과 같이 외부 단편화 문제가 있기 때문입니다.

연속 메모리 할당에서는 특정 프로세스(B, D)가 종료되면서 비어 있는 공간(16KB, 18KB)이 생겼다고 가정해 보겠습니다. 새로운 프로세스를 적재하려고 해도 각각의 빈 공간은 연속적이지 않기 때문에, 18KB보다 큰 프로세스를 적재할 수 없고, 이는 메모리 낭비로 이어집니다. 이러한 현상을 외부 단편화(External Fragmentation)라고 합니다.

 

페이징을 통한 가상 메모리 관리

외부 단편화 외에도 스와핑과 연속 메모리 할당 방식은 다른 하나의 큰 문제점을 가지고 있습니다.

바로 물리 메모리(RAM)보다 큰 프로세스를 실행할 수 없다는 점입니다.

이러한 문제를 해결하는 운영체제의 메모리 관리 기술이 바로 가상 메모리(Virtual Memory)입니다.

 

가상 메모리(Virtual Memory)란?

가상 메모리란 실행하려는 프로그램의 일부만 메모리에 적재하여, 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 하는 메모리 관리 기법입니다. 보조기억장치(예: SSD, HDD)의 일부를 마치 메모리처럼 사용하거나, 프로세스의 일부만 메모리에 적재함으로써 메모리를 실제 크기보다 더 크게 보이게 하는 방식입니다.

이러한 가상 메모리를 구현하는 대표적인 방법으로 페이징과 세그멘테이션이 있습니다.

 

페이징(Paging)란?

페이징은 프로세스의 논리 주소 공간을 일정한 크기의 페이지(Page) 단위로 나누고, 물리 주소 공간도 같은 크기의 프레임(Frame) 단위로 나눈 뒤, 각 페이지를 프레임에 할당하는 방식입니다.

이 방식은 외부 단편화 문제를 해결할 수 있습니다.

또한, 페이징 기법에서도 스와핑이 사용될 수 있으며, 페이지 단위로 스왑 아웃/인이 발생합니다.

 

프로세스를 가변적인 크기의 세그먼트(Segment) 단위로 분할하는 방식으로, 한 세그먼트는 코드 영역(의 일부)일 수도 있고, 데이터 영역(의 일부)일 수도 있다. 세그먼트의 크기가 일정하지 않기 때문에 외부 단편화 문제가 발생할 수 있다.

 

페이지 테이블(Page Table)

프로세스를 구성하는 페이지는 물리 메모리 내에 불연속적으로 배치됩니다.

따라서 CPU 입장에서는 다음에 실행할 페이지가 어디에 있는지 찾기 어려운 문제가 있습니다.

이 문제를 해결하기 위해 프로세스의 페이지와 실제 메모리의 프레임을 매핑해주는 정보인 페이지 테이블(Page Table)을 활용합니다.

페이지 테이블에는 유효 비트(Valid Bit)가 존재하며, 이는 해당 페이지가 메모리에 적재되어 있는지 여부를 나타냅니다.

• 유효 비트가 1 → 해당 페이지가 메모리에 존재
• 유효 비트가 0 → 해당 페이지가 메모리에 없음

CPU가 유효 비트가 0인 페이지에 접근하려 하면, 페이지 폴트(Page Fault)라는 예외가 발생하게 됩니다.

 

1. 기존 작업 내역을 백업
2. 원하는 페이지를 메모리로 가져와 유효 비트를 1로 변경
3. 메모리에 적재된 페이지를 실행

 

내부 단편화 문제

페이징은 외부 단편화 문제를 해결할 수 있지만 내부 단편화(Internal Fragmentation) 문제가 발생할 수 있습니다.

이는 모든 프로세스가 페이지 크기에 딱 맞게 나뉘지 않기 때문입니다.

 

페이지 테이블의 메모리 관리 문제

각 프로세스의 페이지 테이블은 메모리에 적재될 수 있습니다. 

특정 프로세스를 실행하기 위해서는 페이지 테이블이 메모리에 적재된 위치를 알아야 합니다. 특정 프로세스의 페이지 테이블이 적재된 메모리 상의 위치를 가리키는 특별한 레지스터를 페이지 테이블 베이스 레지스터(PTBR, Page Table Base Register)라고 합니다. PTBR은 프로세스마다 가지는 정보이므로 각 PCB에 기록되며, 다른 프로세스로의 문맥 교환(Context Switching)이 발생할 때 변경됩니다.

그러나 모든 프로세스의 페이지 테이블을 메모리에 유지하는 것은 메모리 접근 횟수가 많아지고 메모리 용량을 많이 차지하기 때문에 비효율적이므로, 이를 최적화하기 위해 TLB(Translation Lookaside Buffer)와 같은 캐시 기법이 활용됩니다.

 

메모리 접근 횟수 문제

모든 프로세스의 페이지 테이블이 메모리에 적재되어 있으면, CPU는 페이지 테이블에 접근하기 위해 한 번, 실제 프레임에 접근하기 위해 한 번, 이렇게 총 두 번 메모리에 접근해야 합니다. 그렇기에 메모리 접근하는 시간이 두 배로 늘어날 수 있습니다. 이를 해결하기 위해 변환 색인 버퍼(TLB, Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리가 사용됩니다.

TLB는 캐시 메모리이므로 용량이 제한적입니다. 따라서 참조 지역성(Locality of Reference)의 원리에 근거해 자주 사용할 법한 페이지 테이블의 일부 내용을 저장합니다.

 

• TLB 히트(TLB Hit)
  CPU가 접근하려는 페이지 번호가 TLB에 존재하는 경우, TLB는 CPU에게 해당 프레임 번호를 즉시 제공합니다.
  👉 한 번의 메모리 접근만으로 원하는 데이터에 접근 가능
• TLB 미스(TLB Miss)
  CPU가 접근하려는 페이지 번호가 TLB에 없는 경우, CPU는 메모리 내의 페이지 테이블에 접근해야 합니다.
  👉 메모리에 두 번 접근해야 하므로 속도가 저하됨

d는 페이지 오프셋

 

메모리 용량 문제 

일반적으로 페이지의 크기는 4KB(2^12)로 잡습니다. 32bit 주소체계의 경우 가상 페이지의 개수는 2^32 / 2^12 = 2^20개 약 100만개 입니다. 따라서, 페이지 테이블의 크기는 2^20 * 4byte로 4MB 정도 됩니다. 그리고 각 프로세스는 자신만의 페이지 테이블을 가지므로, 100개의 프로세스가 실행중이면 총 400MB의 메모리가 필요합니다.

페이지 테이블의 크기는 생각보다 작지 않습니다. 따라서 모든 프로세스의 페이지 테이블을 메모리에 유지하는 것은 비효율적이며, 메모리 낭비를 초래합니다.

이를 해결하기 위한 방법 중 하나가 계층적 페이징(Hierarchical Paging)입니다.
이는 페이지 테이블 자체를 다시 페이징하는 방식으로, 다단계 페이지 테이블(Multilevel Page Table) 기법이라고도 합니다.

계층적 페이지 테이블은 프로세스의 페이지 테이블을 여러개로 자르고, CPU와 가까이 위치한 바깥 쪽에 페이지 테이블(Outer 페이지 테이블)을 추가하여 잘린 페이지 테이블을 가리키게 합니다. 즉, CPU는 가장 가까운 Outer 페이지 테이블만 유지하고, 필요할 때마다 나머지 페이지 테이블을 참조합니다.

이 방식은 불필요한 페이지 테이블을 메모리에 유지할 필요가 없어, 메모리 낭비를 줄이는 효과가 있습니다.

 

페이지 교체 알고리즘

프로그램 실행 시 처음부터 모든 페이지를 메모리에 적재하지 않고, 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(Demand Paging)라고 합니다.

 

요구 페이징의 동작 과정은 다음과 같습니다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행
2. 해당 페이지가 현재 메모리에 있으면 (유효 비트가 1) → 정상 실행
3. 해당 페이지가 현재 메모리에 없으면 (유효 비트가 0) → 페이지 폴트 발생
4. 페이지 폴트 발생 시 페이지 폴트 처리 루틴을 통해 해당 페이지를 메모리로 적재하고, 유효 비트를 1로 설정
5. 다시 1의 과정을 수행

요구 페이징을 통해 페이지들을 메모리에 적재하다 보면 언젠가는 메모리가 가득 찰 것입니다.

메모리에 빈 공간이 없을 경우, 기존에 적재된 페이지 중 일부를 스왑 아웃(Swap Out)해야 합니다.

이때, 어떤 페이지를 내보낼지 결정하는 방식이 "페이지 교체 알고리즘(Page Replacement Algorithm)"입니다.

좋은 페이지 교체 알고리즘은 불필요한 페이지 폴트(Page Fault) 발생을 줄여 성능을 향상시키지만, 비효율적인 알고리즘은 반복적인 페이지 폴트로 성능 저하를 유발할 수 있습니다.

스레싱(thrashing): 프로세스가 실제로 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제

 

페이지 교체 알고리즘 종류
1. FIFO (First-In First-Out)

• 가장 먼저 메모리에 들어온 페이지를 가장 먼저 내보내는 방식
• 구현이 간단하지만, 가장 오래된 페이지가 아직 자주 사용될 수도 있어 비효율적일 수 있음
• 벨라디의 모순(Belady’s Anomaly): 페이지 프레임 수를 늘려도 페이지 폴트가 감소하지 않는 현상 발생 가능

 

2. OPT(Optimal) 

• 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식
• 가장 낮은 페이지 폴트율을 보장하지만, 미래의 메모리 접근 패턴을 알아야 하므로 현실적으로 구현이 어려움
• 주로 비교 기준(이론적 최적값)으로 사용됨

 

3. LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식
• 과거의 메모리 접근 패턴을 기반으로 하기 때문에 FIFO보다 성능이 우수
• 참조 지역성(Locality of Reference) 원리를 활용하여, 최근에 사용된 페이지는 앞으로도 사용할 가능성이 높다고 가정
• 하드웨어적으로 구현하려면 추가적인 저장 공간(카운터, 스택 등)이 필요

 

4. 시계 (Clock)

• 프레임 내의 페이지가 참조될 때 하드웨어에 의해 참조 비트가 1로 세팅
• 한 바퀴를 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나감
• 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체
• 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계
• 2차 기회(second chance) 알고리즘이라 부르기도 함

 

 

이 외에도 LFU(Least Frequently Used), MFU(Most Frequently Used) 알고리즘이 있습니다. 

운영체제는 이러한 알고리즘을 적절히 조합하여 효율적인 메모리 관리를 수행합니다.

리눅스에서는 Clock 알고리즘과 LRU 알고리즘을 혼용해서 사용한다고 합니다.

 

참고

 

강민철. 『 이것이 취업을 위한 컴퓨터 과학이다 』

[운영체제] 페이지 교체 알고리즘