⚡ 운영체제 - 가상 메모리와 페이지 교체 알고리즘

🔹 가상 메모리란?

• 가상 메모리는 실제 물리 메모리보다 큰 공간을 프로세스에 제공하기 위한 메모리 관리 기법이다.
• 각 프로세스는 독립된 주소 공간을 가지며, 운영체제가 실제 메모리(RAM)와 보조기억장치(Disk)를 조합해 가상 주소를 실제 주소로 매핑한다.
• 장점은 다음과 같다.
  • 물리 메모리보다 더 큰 공간 제공
  • 프로세스 간 메모리 격리
  • 메모리 단편화 최소화

🔹 페이징 (Paging)

• 가상 메모리와 물리 메모리를 같은 크기의 블록으로 나누는 방식
  • 가상 메모리: 페이지(Page)
  • 물리 메모리: 프레임(Frame)
• 페이지 테이블을 통해 페이지와 프레임 간 매핑을 관리하며, 논리 주소는 페이지 번호와 오프셋으로 구성된다.

🔹 세그멘테이션 (Segmentation)

• 코드, 데이터, 스택 등 논리적 단위로 메모리를 나누는 방식
• 각 세그먼트는 시작 주소(base)와 길이(limit)로 정의되며, 접근 시 유효성 검사를 수행한다.
• 가독성과 구조적 관리에는 유리하나, 외부 단편화 문제가 발생할 수 있다.

🔹 페이지 폴트 (Page Fault)

• 프로세스가 접근한 페이지가 물리 메모리에 없는 경우 발생하는 예외 상황이다.
• 이때 운영체제는 디스크에서 해당 페이지를 메모리로 로드해야 하며, 이 과정에서 교체 알고리즘이 사용될 수 있다.

🔹 페이지 교체 알고리즘

• 메모리가 가득 찼을 때 어떤 페이지를 제거할 지를 결정하는 알고리즘

▫️ FIFO (First-In First-Out)

• 가장 먼저 들어온 페이지를 가장 먼저 제거
• 구현이 간단하지만, 오히려 페이지 수를 늘렸을 때 폴트가 증가하는 Belady의 역설이 발생할 수 있다.

▫️ LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 제거
• 시간 지역성(Locality of reference)을 잘 반영한 방식
• 다만 정확한 구현에는 최근 사용 정보를 저장해야 하므로 추가적인 자원 필요

▫️ LFU, Optimal 등

• LRU 외에도 사용 횟수를 기반으로 한 LFU(Least Frequently Used), 앞으로 가장 오랫동안 사용하지 않을 페이지를 제거하는 Optimal 방식 등 다양한 알고리즘이 존재

🔹 TLB란?

• TLB(Translation Lookaside Buffer)는 페이지 테이블의 일부를 캐싱하여 주소 변환 속도를 높이는 캐시 메모리다.
• 페이지 테이블 접근은 느릴 수 있으므로, 최근 접근한 페이지 매핑을 TLB에 저장
• TLB 히트 시 빠르게 물리 주소 반환
• TLB 미스 시 페이지 테이블 접근 필요

🔹 LRU는 어떻게 구현할까?

▫️ 스택 기반 구현

• 각 페이지 접근 시 해당 페이지를 스택 맨 위로 이동
• 가장 아래에 있는 페이지를 제거
• 구현은 간단하지만 성능이 좋지 않다

▫️ 해시맵 + 이중 연결 리스트 구현

• 해시맵: 페이지 번호 → 노드 주소
• 이중 연결 리스트: 사용 순서 관리
• O(1) 시간에 삽입, 삭제, 접근이 가능해 성능이 우수
• 자바의 LinkedHashMap 으로도 구현 가능

🔹 마무리

• 가상 메모리는 운영체제의 핵심 기능이며, 페이지 교체 알고리즘은 메모리 효율성과 성능에 직접적인 영향을 준다.
• TLB, LRU 구현 방식, 페이징과 세그멘테이션의 차이 등이 자주 등장하므로 개념과 내부 동작 방식을 정확히 숙지해야 한다.