[OS 기초] 08. 가상메모리 (Virtual memory)

[가상메모리의 3가지 특성]

1. 동적 주소 변환: 실행 중에 논리 주소(Logical)가 물리 주소(Physical)로 실시간 변환된다.
2. 비연속적 메모리 할당: 프로그램을 여러 블록으로 나누어, 메모리의 빈 공간 어디에든 흩어져서 배치될 수 있다. (단편화 해결)
3. 부분 적재 실행: 프로그램 전체가 아닌, 실행에 필요한 일부만 메모리에 올려서 실행한다.

 

1. 동적 주소 변환 (Logical to Physical)

• 프로세스가 참조하는 모든 메모리 주소는 논리 주소(Logical Address)이다.
  이 논리 주소는 프로그램 실행 중에 실제 데이터 접근을 위해서 물리 주소(Physical Address)로 실시간(동적)으로 변환된다.

 

2. 비연속적 메모리 할당

• 분할 적재: 프로세스의 주소 공간은 한 덩어리가 아니라 여러 개의 블록(페이지 또는 세그먼트)으로 나뉜다.
  유연한 배치: 이 블록들은 주기억장치(RAM) 상에 연속적으로 붙어 있을 필요가 없으며, 순서나 위치에 상관없이 흩어져서 배치될 수 있다.
• 이점: 연속 할당 방식에서 발생하는 단편화(빈 공간 활용 불가) 문제를 해결하여 메모리 낭비를 줄인다.

 

3. 부분 적재 실행

• 일부만 있어도 실행 가능: 프로세스 전체를 메모리에 다 올릴 필요 없이, 현재 실행에 필요한 '일부 블록'만 주기억장치에 올려놓고(적재) 실행할 수 있다.
• 이점: 메모리 공간을 절약하여 더 많은 프로세스를 동시에 실행(멀티 태스킹 능력 향상)할 수 있다.

• 적재 집합 (Resident Set)
  
  • 프로세스의 전체 데이터 중, 현재 주기억장치(RAM)에 실제로 올라와 있는 블록들의 집합
  • 즉, 프로세스가 당장 사용할 수 있는 준비된 데이터들을 의미함

• 메모리 접근 오류 (Memory Access Fault)
  • 정의: 주기억장치에 없는(적재되지 않은) 데이터를 쓰려고 할 때 발생하는 하드웨어 인터럽트(Event)
  • 보통 '페이지 폴트'라고 부른다.
  • 처리 과정:
    1. 발생: 필요한 블록이 RAM에 없음이 확인됨.
    2. 대기(Block): 해당 프로세스는 잠시 멈추고 블록(대기) 상태로 전환됨.
    3. 적재: 운영체제가 디스크(HDD/SSD)에서 필요한 데이터를 찾아 RAM으로 가져옴.
    4. 재개(Ready): 적재가 끝나면 프로세스는 다시 준비(Ready) 상태가 되어 실행을 기다림.

• 가상 메모리와 물리 메모리의 관계

가상메모리의 실용성

블록 적재 요구의 빈도에 따라 실용성이 달라짐.

프로세스 수행 시간 중 임의의 ‘짧은’ 구간을 관찰했을 때 메모리 참조 행태가 너무 분산되면 안 됨, 최대한 많이 참조되도록 관리

 

• 프로세스의 전체 주소 공간 (가상 메모리):
  • 디스크(Disk)에 설정된다. 방대한 저장 공간을 활용하므로 매우 큼
• 실제 참조 공간 (물리 메모리):
  • 주기억장치(RAM)에 적재됩니다. 전체 중 '당장 필요한 일부'만 캐시(Cache) 형태로 적재되어 CPU가 참조한다.

 

• 부분 적재 수행의 이점 

1. 시스템 효율성 향상 (다중 프로그래밍)

• 메모리를 적게 차지하므로 더 많은 프로세스를 동시에 메모리에 유지할 수 있다.
• 결과: 준비 상태(Ready)의 프로세스가 많아지므로, CPU가 쉴 틈 없이 일할 수 있어 CPU 활용도(Utilization)와 처리율이 높아짐.

2. 물리 메모리보다 큰 프로그램 실행 가능

• 물리 메모리(RAM) 용량의 한계를 극복함
• 내 컴퓨터 램이 8GB라도, 16GB짜리 프로그램을 실행할 수 있게 됨 (필요한 부분만 가져다 쓰니까!)
• 과거 (오버레이 기법): 메모리가 부족하던 시절에는 프로그래머가 직접 코드를 쪼개고, 언제 메모리에 올리고 내릴지(Swap)를 일일이 코딩해야 했다.
• 현재: 이 복잡한 작업(가용 메모리 파악, 블록 교체 등)을 운영체제(OS)가 알아서 담당하므로 프로그래머는 프로그램 로직에만 집중할 수 있다.

 

가상 메모리

구조적 특징

• 왼쪽 (주기억장치 / 물리 주소 공간):
  • 프로그램 A와 B의 조각(페이지)들이 메모리 이곳저곳에 흩어져(불연속적) 배치되어 있다.
  • 부분 적재 확인: 프로그램 A를 보면 디스크에는 0~10번까지 있지만, 주기억장치에는 3, 4, 6, 10번이 없다. (필요한 것만 올라와 있음)

• 오른쪽 (디스크 / 가상 주소 공간):
  • 사용자 프로그램 A(0~10번)와 B(0~6번)가 순서대로(연속적으로) 저장되어 있다.
  • 사용자나 프로세스 입장에서는 데이터가 차례대로 이어져 있는 것으로 인식합니다. (논리적 연속성)

 

• 불연속적 배치 가능:
  • 논리 주소 공간 상에서 연속적으로 배치가 되어 있으면, 물리적으로는 불연속적으로 배치되어도 논리 주소 공간 상에 연속적으로 배치가 되어 있으면 프로세스 실행에는 문제가 없다.
  • 즉, CPU가 바라보는 '논리 주소'만 잘 이어져 있다면, 실제 RAM 어디에 있든 상관없다!!

• 디스크 (보조기억장치):
  • 고정 길이 페이지(Page): 디스크에 있는 프로그램은 일정한 크기의 블록인 '페이지' 단위로 나뉜다.
  • 모든 프로그램과 운영체제 데이터는 파일처럼 이곳에 영구 저장된다.
• 주기억장치 (RAM):
  • 고정 길이 프레임(Frame): 주기억장치도 페이지와 동일한 크기의 방(Frame)들로 구성된다.
  • 프로그램 실행을 위해 페이지들 중 '일부 혹은 전부'가 이 프레임에 끼워져(적재되어) 있어야 한다.

프로그램은 디스크에 '페이지' 단위로 보관되다가, 실행 시 필요한 페이지만 RAM의 빈 '프레임'에 순서 상관없이(불연속) 적재된다.

 

 

[ 가상 메모리 주소지정 ]

'동적 주소 변환'이 실제로 하드웨어(HW) 레벨에서 어떻게 일어나는지 보여주는 핵심 메커니즘이다.

CPU는 가상 주소만 알고 던지면, 중간에 있는 MMU가 테이블을 보고 실제 주소(RAM)나 디스크 위치로 연결해 준다.

 

주소 변환 흐름 (Process)

1단계: CPU의 요청 (Virtual Address)

• CPU(처리기)가 데이터를 읽거나 쓰기 위해 가상 주소(Virtual Address)를 보낸다.
• 예시: 그림의 0xffff1234가 바로 가상 주소

2단계: MMU의 개입 (Translation)

• CPU가 보낸 가상 주소는 메모리로 바로 가지 않고, MMU(메모리 관리 장치)라는 하드웨어가 중간에서 가로챈다.
• MMU의 역할: 가상 주소를 실제 데이터가 있는 물리 주소(Real Address)로 변환해 주는 역할을 한다.

3단계: 주소 매핑 확인 (MMU Table)

• MMU는 내부에 있는(또는 연결된) MMU Table(페이지 테이블)을 참조한다.
• 질문: "가상 주소 0xffff1234는 실제 메모리 어디에 있어?"
• 답변: 테이블에서 매칭되는 실제 물리 주소를 찾는다.

4단계: 최종 접근 (Real vs Disk)

• 주기억장치에 있는 경우: 변환된 실주소(Real Address)를 통해 RAM의 해당 위치에 바로 접근한다.
• 주기억장치에 없는 경우: 만약 테이블을 봤는데 RAM에 없다면? 디스크 주소를 가리키게 되며, 이때 아까 배운 '페이지 폴트'가 발생하여 디스크에서 데이터를 가져온다.

 

용어 정리

가상메모리	보조기억장치를 주기억장치처럼 주소지정 가능하게 만든 저장공간 할당체제. 프로그램이 메모리를 참조할 때 사용하는 주소는 메모리시스템이 물리메모리의 특정 위치를 식별할 때 사용하는 주소와 구별된다. 프로그램이 생성한 주소는 그에 대응된 물리주소로 자동 변환된다. (MMU 관여) 가상메모리의 크기는 주기억장치의 크기가 아니라 컴퓨터시스템의 주소지정체계와 보조기억장치의 가용크기에 의해 제한된다.
가상주소	주기억장치(메모리)처럼 참조될 수 있도록 가상메모리의 특정위치에 배정된 주소
가상주소공간	특정 프로세스에게 할당된 가상 주소의 영역
주소공간	특정 프로세스가 접근할 수 있는 메모리 주소의 영역
실주소	주기억장치 상의 특정 저장위치의 주소
MMU (Memory Management Unit)	가상 주소를 물리 주소로 변환해주는 하드웨어 장치 (소프트웨어가 아니라 하드웨어라서 속도가 매우 빠름)
MMU Table (매핑 테이블)	[가상 주소 : 물리 주소]의 대응 관계를 적어둔 표 이 테이블을 통해 시스템은 데이터가 현재 RAM에 있는지, 디스크에 있는지 파악할 수 있다.

 

1. 가상 메모리의 크기 제한

• 만약 CPU가 주소를 전달하는 통로(버스)가 8비트(bit)라면?
• 만들 수 있는 주소의 개수는 0부터 2^8 - 1 (0 ~ 255)까지다.
• 램(RAM)을 아무리 많이 꽂아도, CPU가 가리킬 수 있는 주소의 한계가 정해져 있다는 뜻. (32비트 운영체제에서 램 4GB 이상 못 쓰는 이유와 같다.)

2. 가상주소 vs 실 주소

• 가상주소 (Logical Address): 프로세스가 "나는 100번지에 데이터를 저장할래"라고 할 때의 100번지다. (프로세스만의 착각)
• 실 주소 (Physical Address): 실제 RAM의 칩 안에 전자가 저장되는 진짜 위치다. (특정 데이터의 위치)
• 자동 변환: 이 둘 사이를 MMU가 매핑해 준다.

3. 주소 공간 (Address Space)

• Process는 자신이 할당받은 논리주소공간 이용, 각 프로세스는 자신만의 독립적인 방(주소 공간)을 가지고 있다고 생각하고 작업한다. (실제로는 물리 메모리 여기저기에 흩어져 있더라도)

 

[ 가상메모리의 실용성 ]

1. 효율성 (낭비 절감)

• 미리 다 올리지 않고, 오류(Fault)가 나서 필요해진 블록만 딱 골라서 적재하므로 불필요한 메모리 낭비가 없다.

2. 실용성의 관건 (빈도 관리)

• 가상 메모리가 성공하려면 블록을 불러오는 횟수(적재 요구)가 적어야 한다.
  • 집중 참조: 데이터 참조가 여기저기 흩어지지 않고 집중되어야 한다. (한 번 가져온 건 최대한 오래 쓸 수 있어야 함)
  • 교체 전략: 메모리가 꽉 차서 이미 적재된 블록 중 하나를 내보내야 할 때(Swap-out), 금방 다시 참조될 페이지를 선택하지 않는 것이 중요하다.

3. 스레싱(Thrashing) 방지

• 정의: 페이지 부재/적재 요구가 빈번하게 발생하여, 시스템이 실제 프로세스 실행보다 블록을 교체(Swap In/Out)하는 데 대부분의 시간을 소비하는 현상
• 이 스레싱 현상을 막는 것이 가상 메모리 실용성의 핵심이다.

 

[ 지역성의 원리(principle of locality) ]

정의: 프로그램이 메모리에 접근할 때 특정 데이터를 집중적으로 참조하는 경향

 

• 프로세스의 메모리 참조가 군집을 이루는 특성

• 시간적 지역성 (Temporal Locality)
  • 방금 쓴 데이터를 조만간 또 쓴다는 의미
  • 예시: 반복문(for/while)의 제어 변수, 스택(Stack), 서브루틴(함수), 카운터 변수 등
• 공간적 지역성 (Spatial Locality)
  • 방금 쓴 데이터의 바로 옆에 있는 데이터를 쓴다는 의미
  • 예시: 배열(Array) 순회, 프로그램의 순차적 코드 실행(위에서 아래로)

 

• 지역성이 전제될 때, 가상 메모리 실용성의 필요조건

1. 가상메모리 지원 하드웨어 지원의 효율성: 주소 변환을 담당하는 하드웨어(MMU) 등의 성능이 좋아야 한다.
2. 블록 이동 관리의 효율성: 주기억장치(RAM)와 보조기억장치(Disk) 사이에서 데이터를 주고받는 과정(Swap)이 똑똑하게 관리되어야 한다.

 

[ 페이징(paging) ]

1. 메모리 분할의 단위 (고정 크기) 가상 메모리와 물리 메모리를 '똑같은 크기'의 조각으로 자릅니다. (통상적 4KB, 아키텍처마다 다름)

• 페이지(Page): 가상 메모리를 나눈 조각 (고정 크기)
• 페이지 프레임(Frame): 물리 메모리(RAM)를 나눈 조각 (페이지와 동일한 크기)
  • 핵심: 크기가 같기 때문에 가상 메모리의 '페이지'가 물리 메모리의 어느 '프레임'에든 들어갈 수 있다.

2. 페이지 테이블 (Page Table)

• 가상 주소를 물리 주소로 바꿔주는 이정표 역할 (페이지-프레임 매핑 관계)
• 프로세스가 특정 가상주소 (해당 페이지 상의 한 주소)를 참조할 경우 그에 대응된 물리주소(해당 페이지가 적재된 프레임 상의 대응 주소)가 참조되도록 주소 사상/변환
• 예시: 프로세스가 "나 1번 페이지 쓸래"라고 하면, 페이지 테이블이 "그건 실제 RAM의 5번 프레임에 있어"라고 알려준다. (주소 사상/변환)

3. 프로세스별 독립 관리

• 일반적으로 각 프로세스마다 하나의 페이지 테이블을 가집니다.
• CPU(하드웨어)는 이 테이블을 보고 주소를 찾아갑니다.

4. 적재 여부와 페이지 폴트

• 페이지 테이블에는 지금 이 페이지가 RAM에 있는지 적재 여부(Valid/Invalid)를 표시하는 정보가 있다.
• 페이지 폴트(Page Fault): 만약 참조하려는 페이지가 RAM에 없다면(적재 안 됨), 하드웨어가 이를 감지하여 이벤트(인터럽트)를 발생시킨다. → 이후 OS가 디스크에서 가져온다.

 

[ 페이징(paging) : 페이지테이블 항목 구성 ]

페이지테이블 항목 구성

(1) 프레임 번호 (Frame Number)

• 가상 주소의 '페이지 번호'에 대응하는 실제 물리 메모리의 위치

(2) 제어 비트 (Control Bits)

• P (Present Bit, 존재 비트):
  • 의미: 현재 이 페이지가 주기억장치(RAM)에 있는가?
  • 1 (True): 메모리에 있음 → 바로 접근 가능.
  • 0 (False): 메모리에 없음 → 페이지 폴트(Page Fault) 발생! (디스크에서 가져와야 함)
• M (Modify Bit, 변경 비트):
  • 의미: 메모리에 올라온 후, 내용이 수정된 적이 있는가?
  • 0: 읽기만 했다. (내용 변경 없음)
  • 1: 쓰기(Write) 작업으로 내용이 바뀌었다.
  • 용도: 나중에 메모리가 꽉 차서 이 페이지를 쫓아낼 때, 1이라면 디스크에 변경된 내용을 기록(저장)하고 쫓아내야 한다. 0이면 그냥 덮어씌워도 된다(디스크랑 내용이 같으니까).

 

[ 페이징(paging) : 주소 변환 ]

주소변환

• 가상 주소 (총 32bit) 가정
  • 상위 20bit (페이지 번호, p): 페이지 테이블에서 몇 번째 줄을 볼지 결정하는 인덱스 (0~2^20-1 = 1MB니까 약 100만 개)
  • 하위 12bit (오프셋, d): 페이지 내부에서의 위치 (2^12 = 4096, 즉 페이지 크기는 4KB)

페이지 내부 주소 지정 (Addressing)

1. 접근 방식: 2단계 주소 지정 (Two-Step) 프로세스의 주소 공간은 페이지(Page) 단위로 잘려있기 때문에, 원하는 데이터에 접근하려면 두 가지 정보가 필요!

1. 어떤 페이지인가? (페이지 번호: Page Number) → 큰 덩어리 식별
2. 그 페이지의 어디쯤인가? (오프셋: Offset) → 세부 위치 식별

2. 4096B(4KB) 페이지의 의미

• 한 페이지의 크기가 4096 Byte라는 것은, 그 안에 0번째 바이트부터 4095번째 바이트까지 데이터가 들어갈 수 있는 방이 4096개 있다는 뜻
• 이 4096개의 방을 하나하나 구별하려면 숫자가 몇 개 필요할까?
  • 4096=2^12
  • 즉, 12비트(bit)가 있어야 4096가지의 위치를 표현할 수 있다.

3. 오프셋(Offset)의 역할: 페이지 내부의 나침반

• 정의: 페이지의 시작점(0번지)으로부터 얼마나 떨어져 있는가를 나타내는 수치
• 범위: 12비트가 할당되므로 표현 가능한 주소 범위는 0∼2^12−1 (즉, 0∼4095) 
• 작동:
  • 오프셋이 0이면 → 페이지의 맨 처음 바이트
  • 오프셋이 4095면 → 페이지의 맨 마지막 바이트

비유

• 페이지 번호 (20bit) = "동"
  • 예: "101동으로 가세요." (큰 위치)
• 오프셋 (12bit) = "호수"
  • 예: "그 동의 0호부터 4095호 사이에 있는 30호 데이터를 가져오세요." (세부 위치)

 

[ 페이징(paging) : 페이지테이블 크기 ]

• 가상 주소 공간이 클수록 관리해야 할 페이지 개수가 늘어난다.
• 문제: 페이지 테이블(지도)의 크기도 덩달아 커져서, 정작 데이터를 저장해야 할 주기억장치 공간을 테이블이 다 차지해버리는 문제가 발생

해결을 위한 접근 방법 (3가지)

• n-단계 계층 구조 (Hierarchical Paging) : 실제 데이터가 존재하는 영역에 대해서만 단계별로 테이블을 생성
• 페이지 테이블 자체를 가상 메모리에 적재 : 현재 참조에 필요한 테이블 조각만 RAM에 가져와서 수행
• 역 페이지 테이블 (Inverted Page Table) 이용
  • 기존 방식: 페이지 번호를 기준으로 프레임 번호를 찾음 (테이블 크기 = 가상 메모리 크기에 비례 → 매우 큼)
  • 역 방식: 프레임 번호를 기준으로 어떤 페이지가 들어있는지 기록 (테이블 크기 = 실제 물리 메모리 크기에 비례 → 작음)
  • 왜 역 페이지 테이블이 효율적인가?
    • 모든 Process들의 페이지 개수는 프레임 개수보다 훨씬 많다. (가상 메모리가 물리 메모리보다 훨씬 크니까)
    • 프레임 수는 메모리 크기에 따라 결정되므로 메모리 절약 가능 (RAM이 8GB면 프레임 개수는 딱 정해져 있다.
    • 모든 프레임에 대한 관계를 다 담는 게 아니라, 역으로 실제 적재된 페이지 정보만 관리. (기존에는 수억 개의 페이지 정보를 다 리스트업 해야 했지만, 역 페이지 테이블은 RAM에 존재하는 프레임 개수만큼만 리스트를 만들면 됨)

 

[ 페이징(paging) : 2-단계 페이지테이블 ]

2-단계 페이지테이블

 

[ 페이징(paging) : 주소변환 2-단계 페이지테이블]

2-단계 페이징 시스템에서의 주소변환

 

[ 페이징(paging) : 역페이지 테이블 ]

기존 방식 (페이지당 하나) / 역 방식 (프레임당 하나)

보통 가상 주소 공간(n)이 물리 주소 공간(m) 보다 훨씬 크기 때문에 (n > m), 테이블 크기가 획기적으로 줄어든다.

 

해시 함수 (Hashing)

문제 : 테이블이 '프레임 순서'로 되어 있어서, CPU가 주는 '페이지 번호'로 몇 번째 줄을 찾아야 할지 바로 알 수가 없다. (인덱싱 불가)

페이지 번호에 대한 해시값(hash value)을 해당 페이지가 적재된 프레임의 번호로 간주

 

• 입력: n비트 페이지 번호
• 출력: 테이블의 인덱스 (어디쯤 있는지 위치를 찍어줌)

연결기법 (충돌(collision) 해결을 위해)

• 같은 칸에 여러 명이 배정되면, 연결 리스트(Linked List)처럼 줄줄이 엮어서(Chain) 저장
• CPU는 그 체인을 따라가며 자신이 찾는 페이지 번호가 맞는지 하나씩 확인

 

[ 페이징(paging) : 역페이지 테이블의 구조 ]

역페이지 테이블의 구조

 

 

[ 페이징(paging) :  TLB(Translation Lookaside Buffer) ]

데이터를 하나 읽으려면 메모리에 두 번 가야 한다.

(1차) 페이지 테이블을 읽어서 주소 변환 → (2차) 실제 데이터 읽기

 

자주 쓰는 주소 변환 정보(페이지 번호 → 프레임 번호)"를 CPU 옆에 있는 아주 빠른 캐시 메모리(TLB)에 저장해 두자!

TLB의 사용

① TLB 탐색

• CPU가 페이지 번호를 주면, 해당 페이지에 대한 프레임 번호가 담겨있는지 확인
• TLB 적중 (TLB Hit): 페이지 테이블(메모리)에 갈 필요 없이, 즉시 프레임 번호를 얻는다.

② TLB 부재 (TLB Miss)

• 주기억장치에 있는 페이지 테이블로 간다.
• 여기서 주소 변환 정보를 찾아서 실주소를 만든다.
• 중요: 찾은 정보는 다음에 쓸 것을 대비해 TLB에 등록(Update)

③ 페이지 폴트 (Page Fault)

• 페이지 테이블을 봤는데도 메모리에 없다고 나올 때.
• 그림 맨 오른쪽의 보조기억장치(디스크)까지 가서 데이터를 가져와야 한다. (가장 느림)

MMU 캐시 : TLB는 MMU(메모리 관리 장치) 내부에 있는 일종의 고속 캐시 메모리

 

[ 페이징(paging) :  TLB에 대한 연관사상 ]

(a) 직접 사상 (Direct Mapping) : 배열을 순서대로 읽는다. (인덱스 접근)

(b) 연관 사상 (Associative Mapping) : 페이지 번호를 키(Key)로 검색한다. (내용 비교 검색)

 

[ 페이징(paging) : TLB와 캐시의 동작 ]

TLB와 캐시의 동작

 

1단계: 주소 변환

가장 먼저 가상 주소를 물리 주소로 바꾸는 작업

1. 가상 주소 도착: CPU가 페이지 번호와 오프셋을 보냄
2. TLB 탐색:
   • 페이지 번호를 들고 TLB를 먼저 확인
   • TLB 적중 (Hit): 바로 프레임 번호를 얻는다. (매우 빠름)
   • TLB 부재 (Miss): 페이지 테이블(메모리)로 가서 프레임 번호를 가져와야 한다. (느림, 가져오면서 TLB 업데이트)
3. 물리 주소 완성:

• 얻어낸 프레임 번호 + 원래 있던 오프셋을 합쳐서 실주소(Physical Address)를 만든다.

2단계: 데이터 접근 

주소 변환이 끝났으니, 데이터(값)를 가지러 간다. 이때 실주소를 사용

1. 캐시 탐색:
   • 실주소를 들고 캐시(L1/L2 등)를 탐색
   • 캐시 적중 (Hit): 주기억장치까지 안 가고 바로 CPU에 값(Value)을 전달 (가장 빠름)
   • 캐시 부재 (Miss): 캐시에 없으면 어쩔 수 없이 주기억장치(RAM)로 가서 데이터를 읽어온다.

 

[ 페이징(paging) : 페이지/프로그램 크기 ]

1. 페이지 크기가 작을 경우 (Small Page Size)

일반적으로 페이지 크기는 4KB 또는 8KB를 많이 사용. 페이지를 작게 쪼개면 장점과 단점이 명확히 갈린다.

장점

• 내부 단편화(Internal Fragmentation) 감소:
  • 페이지가 작으면, 마지막 페이지의 남는 공간(낭비되는 공간)이 줄어든다. 메모리 효율성 높아짐
• 높은 지역성 활용 (적재 집합 효율):
  • 불필요한 데이터 없이, 필요한 부분만 골라서 메모리에 올릴 수 있다. (정밀한 적재 가능)

단점

• 페이지 테이블 크기 증가:
  • 페이지가 작으면 개수(Entry)가 엄청나게 많아진다.
  • 문제: 테이블이 너무 커져서 테이블 자체를 또 쪼개서 가상 메모리에 넣어야 하고, 페이지 테이블을 읽기 위한 페이지 폴트까지 발생할 수 있다.
• I/O 입출력 횟수 증가:
  • 메모리 할당/회수: 디스크에서 데이터를 가져올 때, 작은 짐을 여러 번 나르는 꼴이라 입출력 오버헤드가 커진다.

---

2. 프로그램 크기가 커질 경우 (Modern Environment)

• 참조 지역성(Locality)의 감소:
  • 원인: 현대의 객체지향(OOP) 프로그래밍이나 다중 스레딩(Multi-threading) 기술은 코드가 여기저기 흩어져서 실행되는 경향이 있다.
  • 결과: 예전처럼 코드가 순차적으로 실행되지 않고, 이쪽저쪽 왔다 갔다 하므로 지역성이 떨어진다.
• TLB 성능 저하:
  • 원인: 지역성이 떨어지면, 좁은 영역을 커버하는 TLB(캐시)에 없는 주소를 찾을 확률이 높아진다.
  • 결과: TLB 적중률(Hit Ratio)이 감소하여 전체적인 시스템 성능이 느려진다.
  • 요즘은 페이지 크기를 좀 더 키우거나, Huge Page를 쓰는 추세

 

[ 세그먼테이션(segmentation) ]

• 가변 크기 분할: 프로세스의 주소 공간을 고정된 크기(Page)가 아니라, 동적으로 설정되는 가변 크기(Variable Size)의 블록들로 나눈다.
• 논리적 단위: 보통 의미 있는 단위(함수, 배열, 스택 등)로 자르기 때문에 블록마다 크기가 제각각이다.

사용 시 이점

① 확장성 자료구조 처리가 단순함

• 스택(Stack)이나 동적 배열처럼 크기가 변하는 자료구조를 다루기 쉽다.
• 비교: 페이징은 크기가 고정이라 데이터가 늘어나면 페이지를 계속 덧붙여야 하지만, 세그먼테이션은 해당 세그먼트의 크기만 늘려주면 된다.

② 독립적인 변경 및 재컴파일 가능

• 프로그램 전체를 다시 빌드할 필요 없이, 수정된 세그먼트만 따로 변경하거나 재컴파일할 수 있다. (모듈화에 유리)

③ 공유와 보호(Sharing & Protection)에 강력함

• 논리적 개체 단위로 자르기 때문에 관리가 편하다.

 

[ 세그먼테이션: 페이징과 결합 시의 주소변환 ]

주소 구조 : 가상 주소가 기존(2개)과 달리 3 부분으로 나뉜다. (s, p, d)

변환 과정 :

1단계: 세그먼트 테이블 조회

• 가상 주소의 세그먼트 번호를 가지고 세그먼트 테이블을 찾아간다.

2단계: 페이지 테이블 조회

• 방금 찾은 페이지 테이블에서, 가상 주소의 페이지 번호를 이용해 프레임 번호를 찾다.
• 실제 물리 메모리의 위치(프레임)가 나온다.

3단계: 물리 주소 완성

• 찾아낸 프레임 번호 뒤에, 원래 있던 오프셋을 그대로 붙여서 최종 주소를 만든다.

 

[ 세그먼테이션: 페이징과 결합 ]

두 기법을 섞어서 서로의 단점을 보완하고 장점만 취한다.

• 페이징 (물리적 관리 담당)
  • 장점: 메모리를 일정한 크기로 잘라서 관리하므로 외부 단편화(External Fragmentation)가 사라진다.
• 세그먼테이션 (논리적 관리 담당)
  • 장점: 프로그램을 의미 단위(함수, 데이터 등)로 나누므로 공유(Sharing)와 보호(Protection) 설정이 아주 쉽다.

 

가상주소에 대한 관점

 

• 프로그래머 관점 (논리적): 가상주소 = 세그먼트 번호 + 세그먼트 오프셋
  • 세그먼트 번호와 그 안에서의 거리(Offset)에 집중
  • (예: 1번 세그먼트의 500번지)
• 시스템 관점 (물리적 변환): 세그먼트 오프셋 = 페이지 번호 + 페이지 오프셋
  • 프로그래머가 말한 '거리(Offset)'가 길면 페이지 번호와 페이지 오프셋으로 쪼개서 관리
  • (예: 1번 세그먼트 안의 -> 2번째 페이지의 -> 10번째 줄)

 

[ 세그먼테이션: 보호와 공유 ]

 

세그먼트 간의 보호 관계

 

1. 완벽한 영역 보호 (Protection)

• 핵심: 세그먼트 테이블에 '길이(Limit)' 정보가 있음.
• 동작: 프로세스가 할당된 길이를 벗어나는 주소에 접근하면?
  • → 하드웨어가 즉시 차단 (Trap 발생).
  • → 다른 프로세스나 OS 영역 침범을 원천 봉쇄

2. 명확한 권한 설정과 공유 (Sharing)

• 페이징 (투명성/Invisible):
  • 시스템이 임의로 자르므로 프로그래머는 경계를 모름 → 권한 설정이 애매함
• 세그먼테이션 (가시성/Visible):
  • 논리적 단위(코드, 데이터)로 잘림 → 프로그래머 눈에 보임
  • 이점: "코드는 실행만", "데이터는 읽기/쓰기만"처럼 보호나 공유 요건을 아주 명확하게 설정 가능

 

[ 페이징과 세그먼테이션의 특성 ]

단순 페이징	가상 메모리 페이징	단순 세그먼테이션	가상 메모리 세그먼테이션
주기억장치는 프레임이라 불리는 고정 크기의 작은 블록으로 분할됨		주기억장치는 분할되지 않음
프로그램은 컴파일러나 메모리 관리 시스템에 의해 다수의 페이지로 분할됨		프로그래머가 컴파일러에게 프로그램 세그먼트를 명시해 줌 (분할 방식은 프로그래머에 의해 결정됨)
내부 단편화		내부 단편화 없음
외부 단편화 없음		외부 단편화
각 페이지가 어느 프레임에 적재되어 있는지 나타내기 위해, 운영체제는 프로세스 각각을 위한 페이지 테이블을 관리해야 함		각 세그먼트의 적재 위치와 길이를 나타내기 위해, 운영체제는 프로세스 각각을 위한 세그먼트 테이블을 관리해야 함
운영체제는 가용 프레임 리스트(free frame list)를 관리해야 함		운영체제는 메모리에 흩어져 있는 가용 공간(free hole)들의 리스트를 관리해야 함
처리기는 페이지 번호와 오프셋을 사용해 절대 주소를 계산함		처리기는 세그먼트 번호와 오프셋을 사용해 절대 주소를 계산함
오버레이를 사용하지 않을 경우, 수행할 프로세스의 모든 페이지가 주기억장치에 있어야 함	수행할 프로세스의 모든 페이지가 주기억장치에 있을 필요 없으며, 필요할 때 적재 가능함	오버레이를 사용하지 않을 경우, 수행할 프로세스의 모든 세그먼트가 주기억장치에 있어야 함	수행할 프로세스의 모든 세그먼트가 주기억장치에 있을 필요 없으며, 필요할 때 적재 가능함
	주기억장치로 한 페이지를 읽어 들이기 위해, 한 페이지를 디스크에 기록해야 할 수도 있음		주기억장치로 한 세그먼트를 읽어 들이기 위해, 하나 이상의 세그먼트를 디스크에 기록해야 할 수도 있음

 

[ 운영체제의 가상메모리 관리 정책 ]

가상메모리 관리 정책의 범주

– 반입정책(fetch policy)

– 배치정책(placement policy)

– 교체정책(replacement policy)

 

[ 반입정책(fetch policy) ]

디스크에 있는 프로세스의 페이지를 언제 주기억장치(메모리)로 적재할지 결정하는 정책

 

• 요구반입(demand paging)
  • 페이지폴트(적재되지 않은 페이지 중 일부분 참조) 시 적재
    • 장점: 메모리 공간을 아껴 멀티프로그래밍 정도(동시 실행 프로세스 수)를 높일 수 있음.
    • 단점: 초기 실행 시 잦은 페이지 폴트로 인한 처리 오버헤드 발생.
  • 일반적인 경우 지역성에 의해 안정적 운용 가능

 

• 선반입(prepaging)
  • 페이지폴트에 의해 요구된 페이지 이외의 페이지도 적재 (시작 시점에 모두 적재)
    • 프로그램 수행을 시작할 때나 페이지폴트 시 적용
    • 한 프로세스의 페이지들이 보조기억장치에 연속적으로 저장되어 있을 경우 그들을 한꺼번에 반입하는 것이 나중에 필요할 때 따로따로 반입하는 것보다 효율적임.
  • 스와핑(swapping)과 구분

 

[ 배치정책(placement policy) ]

메모리 할당, 회수 반복으로 메모리의 빈 공간에 흩어져있을 수 있음 → 어떤 프로그램의 실행을 위해 한 페이지의 할당 필요시 어서 할당될지 모름! 

적재될 블록이 주기억장치의 어느 구간에 메모리 할당할 것인지 결정하는 정책

 

Fit정책 사용 (First, Best, Last, Next, Worst)

First : 메모리 처음부터 탐색하여 가장 먼저 발견된 충분한 공간에 할당

Best : 단편화된 크기를 최소화시킬 수 있는 영역

Last : 메모리 끝에서부터 탐색하여 할당

Next : 마지막 위치를 가리키는 포인터 존재 시 다음 위치를 탐색하는 방법

Worst : 남는 공간을 크게 만들어서(작은 조각 방지) 활용성을 높이는 방식

 

• 페이징 시스템의 경우, 주소변환 하드웨어와 주기억장치접근 하드웨어들이 어떠한 페이지/프레임 조합에 대해서도 같은 효율로 기능하기 때문에 배치정책은 무의미
• NUMA(NonUniform Memory Access) 구조의 다중처리기인 경우, 각 페이지를 그것을 참조할 처리기와 가까운 메모리모듈에 배치시키는 배치전략 필요

 

[ 교체정책(replacement policy) ]

메모리가 포화된 상태에서 메모리 할당 요구 시, 새로운 페이지를 반입하기 위해 현재 적재되어 있는 페이지들 중 어떤 페이지를 교체할 것인지 결정하는 정책 (강제 회수 정책)

 

• 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택하여 교체하는 것이 교체정책의 이상적 목표
• 지역성의 원리(principle of locality)를 전제로 과거의 참조 행태에 근거하여 미래의 참조 가능성 예측 (스레싱 문제 발생 가능)

 

[ 교체정책: FIFO ]

• 가장 오래전에 적재된 페이지 교체하는 정책
• 가장 쉽게 구현 (구현 간단, 비효율)
• FIFO’s anomaly: 특정 참조열에 대해 패턴에 대해 할당된 프레임 수를 증가시켰음에도 보다 많은 페이지폴트가 발생하는 현상

예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

구분	할당된 프레임 수	메모리 적재 상태 예시	최종 결과
Case 1	3 Frames	[1, 2, 3] ... [4, 1, 2] ... [5, 3, 4]	9 Page Faults
Case 2	4 Frames	[1, 2, 3, 4] ... [5, 1, 2, 3] ...	10 Page Faults 🔺

 

일반적으로는 메모리(프레임)를 많이 주면 페이지 폴트가 줄어들 것이라 기대하지만, FIFO 알고리즘에서는 특정 패턴(Reference String)에 따라 오히려 페이지 폴트가 늘어나는(9회 → 10회) 문제가 발생할 수 있음

 

[ 교체정책: Optimal ]

최적(Optimal)

• 가장 오랫동안 참조되지 않을 페이지 교체
• 가장 낮은 페이지 폴트율
• 미래에 대한 정확한 지식이 없어 구현 불가능

예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

진행 순서	입력 페이지	메모리 상태 (4 Frames)	설명
1	1	[1]	Page Fault (초기 적재)
2	2	[1, 2]	Page Fault
3	3	[1, 2, 3]	Page Fault
4	4	[1, 2, 3, 4]	Page Fault (메모리 가득 참)
5	1	[1, 2, 3, 4]	Hit (이미 있음)
6	2	[1, 2, 3, 4]	Hit (이미 있음)
7	5	[1, 2, 3, 5]	Page Fault 💥 (미래에 1,2,3은 곧 쓰이고 4가 가장 늦게 쓰이므로 4를 5로 교체)
8	1	[1, 2, 3, 5]	Hit
9	2	[1, 2, 3, 5]	Hit
10	3	[1, 2, 3, 5]	Hit
11	4	[4, 2, 3, 5]	Page Fault 💥 (미래에 1은 쓰이지 않으므로 1을 4로 교체)
12	5	[4, 2, 3, 5]	Hit

FIFO와 달리 불필요한 교체를 최소화하여 페이지 부재(Page Fault)가 6번으로 가장 적게 발생

 

[ 교체정책: LRU(Least Recently Used) ]

미래를 예측하기 어려우므로 LRU(과거)를 보고 페이지 교체

• 가장 오랫동안 참조되지 않은 페이지 교체 (문제점 : 인접한 미래에 참조 가능성)
• 최적에 근접한 성능
• 구현이 어렵고 큰 오버헤드

 

예제

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

순서	입력	메모리 상태 (4 Frames)	결과	판단 근거 (Look Backward)
1~4	1,2,3,4	[1, 2, 3, 4]	Fault (4회)	초기 적재 (빈 공간 채움)
5~6	1, 2	[1, 2, 3, 4]	Hit	이미 있음 (최근 사용 기록 갱신: 2, 1은 방금 씀)
7	5	[1, 2, 5, 4]	Fault (5회)	과거 기록을 보니 1, 2, 4는 최근에 썼는데, 3은 가장 옛날에 씀. 3을 5로 교체
8~9	1, 2	[1, 2, 5, 4]	Hit	이미 있음 (기록 갱신)
10	3	[1, 2, 5, 3]	Fault (6회)	2, 1, 5는 최근 사용. 4가 가장 오랫동안 안 씀. 4를 3으로 교체
11	4	[1, 2, 4, 3]	Fault (7회)	3, 2, 1은 최근 사용. 5가 가장 오랫동안 안 씀. (7번 이후로 안 씀) 5를 4로 교체
12	5	[5, 2, 4, 3]	Fault (8회)	4, 3, 2는 최근 사용. 1이 가장 오랫동안 안 씀. (8번 이후로 안 씀) 1을 5로 교체

 

Optimal 보다는 성능이 떨어지지만(8회 vs 6회), 실제로 구현 가능한 알고리즘 중에서는 성능이 좋음

하지만 매번 시간을 기록하고 비교해야 하므로 오버헤드(Overhead)가 크다. (그래서 실제로는 Clock 알고리즘 같은 근사치를 사용)

 

[ 교체정책: LFU (Least Frequntly Used) ]

교체 횟수가 가장 적었던 페이지 교체

 

• 과거에 참조된 페이지들의 카운트(참조 횟수)를 측정하고, 이를 계산 및 비교하여 교체 대상을 선정함
• LRU와 마찬가지로 Optimal(최적) 알고리즘에 가까운 성능을 낼 수 있지만 오버헤드가 크다.

 

LRU/LFU의 구현 복잡도 문제로 인해 실제 OS에서 Clock(시침) / Two-Handed Clock(시침, 분침 형태) 근사 알고리즘 주로 사용

 

[ 교체정책: Clock ]

• 프레임 별로 use 비트 연계시켜, 처음 적재 시 1, 참조 시 1로 설정
• 페이지를 적재한 프레임들이 환형으로 배치되어 있다고 간주하고, 첫 교체후보를 가리키는 포인터(시곗바늘) 설정
• 시계 방향으로 포인터를 이동시키면서 포인터가 가리키는 프레임 중 use 비트가 0인 첫 프레임 상의 페이지를 교체
  (use 비트가 1인 경우 그 값을 0으로 변경하고 다음 프레임으로 이동)

 

P : 적재된 상태

M : 변경된 내용이 있는 페이지인지

 

[ 교체정책: 클록 정책의 적용 예 ]

 0번부터 n - 1까지 n개의 프레임으로 구성

• 시곗바늘이 프레임 2를 가리키고 있는 상황에서, 페이지 727을 적재하기 위해 클록정책 작동
• 프레임 2와 3의 use 비트 값이 1이므로 차례로 그 값을 0으로 변경한 후 포인터 이동, use 비트 값이 0인 프레임 4를 발견하여 교체페이지로 선택하게 됨
• 프레임 4에 페이지 727을 적재하고 그 use 비트 값을 1(최초 적재)로 한 후, 시곗바늘이 그다음 프레임을 가리키게 설정함

use 비트가 0이면 적재된지가 한참 됐거나 참조된지가 한참 됐다고 간주하고 use 비트를 변경하는 구조

 

[ 교체정책: 기본 알고리즘의 적용 예 ]

모든 알고리즘은 페이지를 적재 후 시작, 5번부터 문제 발생 (이 예제에서는 최초 적재를 페이지폴트로 간주하지 않음)

OPT : 미래를 보고 선택, LRU : 과거, FIFO : 가장 오래 적재된 페이지 교체, CLOCK : 화살표와 *(use 비트) 사용

CLOCK 알고리즘에서 use 비트를 0으로 변환하는 부분은 생략되어 있음