OS - Main Memory

윤형·2025년 6월 3일

Operation System

목록 보기

9/9

서론

지난시간에는 프로세스의 동기화 과정에서 생기는 교착상태에 대해서 배웠다. 이번에는 Memory에 대해서 다뤄보도록 하겠다.

Memory

운영체제에서 메인 메모리(주 기억장치)는 CPU가 직접 접근할 수 있는 유일한 저장장치 이다. 프로그램이 실행되기 위해서는 반드시 디스크에서 메인 메모리로 적재되어야 하고,
메모리 관리의 핵심 목적은 한정된 메모리 공간을 효율적으로 여러 프로세스에 분배하고 각 프로세스가 자신의 메모리 구역만 접근하도록 하는 것이다.

Memory 관리 기법의 분류

고정분할(fixed partitioning)
동적 분할(Dynamic Partitioning)
페이징(Paging)
세그멘테이션(Segmentation)
세그멘테이션 + 페이징

각 기법은 메모리 할당 방식과 단편화 문제에서 차이를 보인다.

Fixed Partitioning

고정 분할은 운영체제 초기의 메모리 관리 기법으로, 메인 메모리를 여러 개의 고정된 크기의 파티션으로 나누는 방법이다.

각 파티션은 독립적인 공간으로, 하나의 프로세스만 적재할 수 있다. 파티션의 크기는 시스템이 부팅될 때 미리 결정되며, 실행중에는 변경할 수 없다.

Equal-size partitions

메인 메모리를 N개의 동일한 크기(혹은 서로 다른 크기)의 파티션으로 나눈다.
각 파티션에는 하나의 프로세스만 적재 가능하다.
프로세스의 크기가 파티션 크기보다 작거나 같을 때만 적재 가능하다.
파티션이 비어있으면 새로운 프로세스를 적재할 수 있다.

Equal-size의 문제점

큰 프로세스 적재 불가
- 당연하지만 파티션 크기보다 큰 프로세스는 메모리에 적재를 할 수 없다.
작은 프로세스 메모리 낭비
- 프로세스 크기가 파티션 보다 작으면 빈 공간만큼은 낭비를 하게 되는 것이다.
내부 단편화(Internal Fragmentation)
- 작은 프로세스에 의해 파티션 내에 남는 미사용 공간이 생기기 때문에 이 공간은 다른 프로세스가 사용할 수 없어 낭비 된다.
동시 실행 프로세스 수 제한
- 파티션 개수만큼만 프로세스를 동시에 실행할 수 있다.
- 나머지는 대기해야 한다.
작은 프로세스가 많으면 공간 활용 저하
- 마찬가지로 작은 프로세스만 존재하면 그만큼 낭비하게 됨

Equal-size의 문제점은 내부 단편화와 유연성 부족.
메모리 활용성이 떨어지며, 다양한 크기의 프로세스를 효율적으로 지원하지 못한다.

Varied-Size Fixed Partitioning

메모리를 여러 개의 고정된 크기 파티션으로 나누되, 각 파티션의 크기를 다르게 설정한다.
예를 들어, 100MB, 200MB, 300MB, 400MB 등 다양한 크기의 파티션을 만들 수 있다.
프로세스는 자신보다 크거나 같은 파티션에만 적재할 수 있다.

문제점

하지만 여전히 내부 단편화가 존재.
- 400mb 파티션에 250mb 프로세스가 적재되면 150이 남고 낭비됨.
외부 단편화는 없음.
- 파티션 경계가 고정되어 있기 때문에 발생 X
- 외부 단편화가 없다는 것은 빈 공간들이 실제로 떨어져있어서 활용하지 못하는 것을 의미한다.
파티션 개수로 인한 동시 실행 제한
- 여전히 파티션 개수만큼만 실행됨.
파티션-프로세스 매칭 문제
- 다양한 크기의 파티션을 만들어도, 프로세스의 크기 분포와 파티션 크기 분포가 맞지 않으면 여전히 공간 낭비가 심각할 수 있음.
- 예를 들어, 대부분의 프로세스가 150MB인데 300MB, 400MB 파티션만 남아 있다면 낭비가 발생.
큰 프로세스 적재 불가
- 여전히 파티션보다 큰 프로세스는 적재할 수 없다.

Dynamic Partitioning

Dynamic Partitioning(동적 분할)은 메인 메모리를 고정된 크기의 파티션으로 나누지 않고, 프로세스가 필요로 하는 만큼의 메모리 공간을 동적으로 할당하는 방식이다.
즉, 파티션의 크기와 개수가 미리 정해져 있지 않고, 프로세스의 크기에 따라 메모리 공간이 유연하게 분할된다.

초기에는 p1,p2,p3가 존재한다. 만약 p2가 종료되면 빈자리(hole)에 p4, p5가 들어간다.
p4와 p1이 종료되면 그 자리에 p6가 들어가면서 hole을 채우게 되는 것이다.

할당(Allocation) 전략

First-fit
- 메모리의 처음부터 검색하여, 프로세스가 들어갈 수 있는 첫번째로 충분히 큰 hole에 할당하는 것.
- 구현이 간단하고 빠르다.
Best-fit
- 모든 hole을 탐색하여, 프로세스가 들어갈 수 있는 가장 작은(남은 공간이 적은) hole에 할당한다.
- 공간을 최소화 하는 전략이지만 전체를 검색해야 해서 속도가 느리다.
Worst-fit
- 모든 hole을 검색하여 가장 큰 hole에 할당.
- 남는 공간을 가장 크게 하여, 이후 큰 프로세스가 들어올 가능성을 고려한다.
일반적으로 first-fit과 best-fit이 worst보다 속도와 공간 측면에서 효율적이다.

외부 단편화(External Fragmentation) 문제

동적 분할의 가장 큰 문제점이다.

여러번의 할당/해제를 거치다 보면 메모리에는 크기가 다양한 hole들이 흩어지게 된다.
전체 빈 공간의 합은 충분해도, 연속된 공간이 부족해 새로운 프로세스가 적재되지 못하는 문제점이 생긴다.

✅ 외부 단편화를 해결하기 위한 대표적인 방법이 "컴팩션"이다.

메모리 내의 프로세스들을 한쪽으로 몰아 연속된 빈 공간을 만들고, 흩어진 hole들을 하나로 합치는 작업이다.
이는 CPU자원을 많이 소모하기 때문에 자주 수행하기는 어렵다.
프로세스가 실행 중에 메모리 위치가 바뀌어야 하기 때문에 실행 시점 주소 바인딩이 필요하다.(Execution-time binding)

50-percent rule (first-fit의 특징)

first-fit 방식에서는 할당된 블록 N개가 있을 때, 평균적으로 N/2개의 블록이 외부 단편화로 인해 사용 불가하게 된다.
즉, 메모리 공간의 1/3이 외부 단편화로 인해 낭비될 수 있다는 의미이다.

Buddy System

동적분할에서 발생하는 외부 단편화와 메모리 관리의 비효율성을 줄이기 위해 고안된 메모리 할당 기법이다.

Step 1: 메모리 블록의 분할
- 전체 메모리 공간(예:1MB)를 시작으로, 요청된 크기 이상이면서 가장 작은 2의 거듭제곱 크기의 블록을 찾아 할당한다.
- 만약 해당 크기의 블록이 없다면, 더 큰 블록을 두개의 동일한 크기의 블록으로 분할한다.
- 이 과정을 반복해, 요청된 크기에 맞는 블록이 생성될 때까지 한다.
Step 2: 메모리 블록의 병합
- 프로세스 메모리를 반납하면, 해당 블록의 버디가 비워져있을 경우 두 블록을 다시 합쳐서 더 큰 블록을 만든다.
- 이 병합은 상위 단계까지 계속 반복될 수 있다.

초기 상태: 1MB
Step 1
- 100k요청 -> 가장 가까운 2의 거듭제곱인 128이 필요하다.
- 1MB -> 512k + 512k -> ... 을 반복해 128k블록을 할당한다,
- 나머지 블록은 남아있음.
Step 2
- 240k이 요청되면 256블록이 필요하다.
- 남아있는 256k블록중 하나를 할당한다.
Step 3
- 64k가 요청되면 남은 128중 하나를 64+64로 나눈 후 할당한다.
반복

트리 형태로 보면 이런 형식으로 되어있는 것이다.

내부 단편화: 요청한 크기보다 할당된 블록이 더 크면 남는 부분이 낭비될 수 있다(예: 100K 요청에 128K 할당).
외부 단편화: 버디가 모두 비어있지 않으면 병합이 불가능해, 여러 크기의 블록이 남을 수 있다.

Background: 메모리 접근과 보호의 기본 구조

프로그램 실행 과정
- 프로그램은 디스크(보조저장장치)에 저장되어 있다가, 실행을 위해 반드시 메인 메모리로 적재되어야 한다.
- CPU가 직접 접근할 수 있는 저장장치는 오직 레지스터와 메인 메모리뿐이다.
주소와 접근
- 메모리 장치는 CPU로부터 주소와 읽기/쓰기 명령만을 받는다.
  레지스터 접근은 한 CPU 클럭 내에 끝나지만, 메인 메모리는 여러 클럭이 걸릴 수 있다.
- 캐시(cache)는 메인 메모리와 레지스터 사이에 위치해 속도를 보완한다.
메모리 보호의 필요성
- 각 프로세스가 자신에게 할당된 메모리만 접근하도록 보호가 필요함.
- 그렇지 않으면 한 프로세스가 다른 프로세스의 메모리나 운영체제 영역을 침범해 시스템 오류가 발생할 수 있음.

Base and Limit Registers: 하드웨어적 메모리 보호

Base Register: 현재 프로세스가 사용할 수 있는 메모리 구역의 시작 물리 주소를 저장한다.
Limit Register: 프로세스가 사용할 수 있는 메모리 구역의 크기(범위)를 의미한다.

✅ 동작 방식

주소 변환
- CPU가 명령을 실행할 때, 논리 주소(프로그램 내부의 주소)를 생성한다.
- 하드웨어(MMU)가 논리 주소에 base값을 더해 실제 메모리 주소로 변환한다.
메모리 접근 보호
- 논리 주소가 limit값을 초과하면, 하드웨어가 접근을 차단(trap)하여 잘못된 메모리 접근을 막는다.
- 즉, 프로세스는 base~(base+limit-1) 범위 내의 메모리만 접근할 수 있다.

그렇다면 동적 분할에서는 어떻게 동작할까??

동적 분할(Dynamic Partitioning) 에서는 프로세스마다 크기가 다른 메모리 공간이 할당된다.
이때 각 프로세스마다 base와 limit 레지스터 값을 다르게 설정하여,
각 프로세스가 오직 자신에게 할당된 메모리만 접근하도록 하드웨어적으로 보호한다.
동적 분할에서 프로세스가 메모리에 적재될 때마다, 운영체제가 해당 프로세스의 base/limit 값을 갱신한다.

Adress Binding

Address Binding(주소 결합)이란, 프로그램의 명령어와 데이터가 실제 메모리 주소에 할당(결합)되는 과정을 의미한다.

즉, 프로그램이 실행되는 동안 "이 데이터/코드는 실제 메모리의 어디에 위치할 것인가?"를 결정하는 과정이다.

모든 프로그램이 물리 메모리 0번지에서 시작할 수 없다.
여러 프로그램이 동시에 실행되거나, 프로그램이 메모리 내에서 이동될 수 있기 때문.
프로그램의 주소는 프로그램의 생애 주기(stage)에 따라 여러 형태로 표현된다.
- 소스코드 단계: 변수, 함수 등은 심볼릭(symbolic)이름으로 표현.
- 컴파일 단계: "이 모듈의 시작에서 14바이트 떨어진 곳"처럼 relocation(재배치 가능한) 주소로 변환.
- 링커/로더 단계: 실제 물리 주소로 결합

Adress Binding의 세 가지 시점

시점	특징과 예시
컴파일 시간(Compile time)	- 프로그램이 어디에 적재될지 미리 알 수 있을 때 - 절대 주소(absolute code) 생성 - 시작 위치가 바뀌면 다시 컴파일 필요
적재 시간(Load time)	- 컴파일 시 위치를 모름 - 재배치 가능한 코드(relocatable code) 생성 - 적재 시 실제 주소로 변환, 적재 위치에 따라 달라짐
실행 시간(Execution time)	- 실행 중에 프로세스가 메모리 내에서 이동 가능 - 주소 결합이 실제 실행 시점에 이루어짐 - 하드웨어 지원 필요(MMU, base/limit register 등)

Compile time: 내 프로그램이 반드시 0x1000부터 시작한다는 것이 보장될 때, 모든 주소를 0x1000 기준으로 컴파일.
Load time: 어디에 적재될지 모르기 때문에 상대 주소로 컴파일, 적재될 때 실제 주소로 변환.
Execution time: 실행 중에 프로세스가 이동될 수 있으므로, CPU가 주소를 생성할 때마다 하드웨어가 실제 주소로 변환.

Logical vs Physical Address Space

Logical Address
- CPU가 프로그램이 실행 중에 생성하는 주소이다.
- 프로그램 입장에서는 자신이 사용하는 모든 주소가 논리 주소다.
- 변수, 코드, 데이터에 접근하는데 사용되는 주소등
Physical Address
- 실제 메모리 하드웨어에서 사용되는 주소이다.
- 메모리 칩이 직접 접근하는 실제 위치다.

Logical Address Space
- 한 프로그램이 실행 중에 생성할 수 있는 모든 논리 주소의 집합
- 예: 0~1,000,000번지(프로그램 기준).
Physical Address Sapce
- 실제 메모리 하드웨어에서 접근 가능한 모든 주소의 집합.
- 예: 10,000~20,000번지(메모리 기준).

Compile-time, Load-time Binding
- 논리주소와 메모리 주소가 항상 동일하다.
- 프로그램이 사용하는 주소 = 실제 메모리 주소.
- 프로그램이 메모리 내에서 움직일 수 없다.
Execution-time Binding
- 논리주소와 물리주소가 다르다.
- 논리주소는 CPU가 생성하고, 실행시점에 하드웨어(MMU)가 물리 주소로 변환한다.
- 프로그램이 실행 중에 메모리 내에서 이동하거나, 여러 프로세스가 각자 독립적인 논리 주소 공간을 가질 수 있다.

✅ 그러면 지속적으로 MMU라는 말이 등장하는데 하드웨어 MMU는 과연 무엇인가?

MMU (Memory-Management Unit)

실행 시점에 논리 주소(virtual address)를 물리 주소(physical address)로 변환하는 하드웨어 장치.
주소 변환 방식은 여러 가지가 있지만, 가장 기본적인 방식은 "Relocation Register(재배치 레지스터)"를 사용하는 것.

사용자 프로그램이 0x100 주소에 접근 → MMU가 relocation register(예: 0x4000)를 더해 0x4100 물리 주소로 변환.
사용자 프로그램은 논리 주소만 다루고, 실제 물리 주소는 전혀 알지 못한다.
논리 주소가 실제로 메모리에 접근할 때마다 물리 주소로 변환됨.
이 덕분에 프로세스가 메모리 내에서 자유롭게 이동할 수 있고, 메모리 보호도 가능해짐.
메모리 보호와 다중 프로세스 지원
- 각 프로세스마다 다른 relocation register 값을 사용하면, 각자의 메모리 공간만 접근할 수 있게 보호할 수 있다.
- 실제 MS-DOS 등에서는 여러 개의 relocation register를 사용해 여러 프로세스를 지원했음.

컴파일/적재 시점: 논리 주소와 물리 주소가 같을 수 있음.
실행 시점: 논리 주소와 물리 주소가 다를 수 있음. 이때 MMU가 논리 주소를 물리 주소로 변환.
CPU는 프로그램 실행 중에 논리 주소(예: 346)를 생성.
Relocation register(재배치 레지스터)에는 현재 프로세스가 할당받은 메모리 구역의 시작 주소(예: 14000)가 저장되어 있다.
MMU는 CPU가 생성한 논리 주소(346)와 relocation register의 값(14000)을 더해서 물리 주소(14346)를 계산.
Memory(메모리)는 이 물리 주소(14346)에 접근.

Dynamic Loading

프로그램이 실행될 때, 필요한 루틴(함수, 코드 등)을 실제로 호출하는 시점에 메모리로 적재하는 방식

기본 원리:
프로그램의 모든 루틴이 처음부터 메모리에 올라가는 것이 아니라, 실제로 그 루틴이 호출될 때만 디스크에서 메모리로 적재한다.
장점:
메모리 공간을 효율적으로 사용할 수 있다.
사용되지 않는 루틴은 아예 메모리에 올라오지 않으므로, 대형 프로그램에서 드물게 사용되는 에러 처리 루틴 등은 메모리 낭비 없이 관리할 수 있다.
구현:
특별한 운영체제 지원이 없어도, 프로그램 설계만으로 구현이 가능하다.
다만, 운영체제가 동적 적재를 쉽게 해주는 라이브러리를 제공할 수도 있다.
활용 예시:
복잡한 프로그램에서 자주 사용되지 않는 기능(예: 특정 에러 처리, 드문 옵션 처리 등)을 동적 적재로 구현하면, 전체 메모리 사용량을 줄일 수 있다.

Dynamic Linking

프로그램 실행 시점까지 라이브러리 코드의 연결을 미루는 방식.

Static Linking(정적 연결):
컴파일/링크 단계에서 프로그램 코드와 라이브러리 코드가 하나의 실행 파일로 결합.
Dynamic Linking(동적 연결):
실행 시점까지 라이브러리 연결을 미루고, 실제로 라이브러리 함수가 호출될 때 연결.
동작 방식:
프로그램에는 "stub(스텁)"이라는 작은 코드가 들어 있다.
함수 호출 시, 스텁이 해당 라이브러리가 메모리에 이미 올라와 있는지 확인한다. 없다면 운영체제가 라이브러리를 메모리에 적재하고, 스텁이 실제 함수 주소로 자신을 교체한 뒤, 해당 함수를 실행한다.
장점:
여러 프로그램이 하나의 라이브러리를 메모리에서 공유할 수 있어, 시스템 전체 메모리 사용량이 줄어든다.
라이브러리 업데이트 시, 프로그램을 다시 컴파일하지 않아도 최신 버전을 사용할 수 있다.
운영체제 역할:
운영체제는 라이브러리가 이미 프로세스의 주소 공간에 있는지 확인하고, 없다면 적재한다.
이 방식의 라이브러리를 "shared library(공유 라이브러리)"라고도 부른다.

Swapping

실행 중인 프로세스를 메인 메모리에서 디스크(백업 저장장치, backing store)로 임시로 내보내고, 필요할 때 다시 메모리로 불러오는 메모리 관리 기법.
이 방식은 물리 메모리보다 더 많은 프로세스를 동시에 시스템에 유지할 수 있게한다.

☝️ 동작 원리

프로세스 스와핑 아웃:
실행 중이던 프로세스를 디스크(백업 저장소)로 내보내 메모리 공간을 확보하기.
프로세스 스와핑 인:
필요할 때(예: CPU 스케줄러가 해당 프로세스를 실행하려고 할 때) 디스크에서 다시 메모리로 불러오기.
Backing Store(백업 저장소):
모든 사용자 프로세스의 메모리 이미지를 저장할 수 있을 만큼 크고, 빠른 디스크 공간(예: 전용 스왑 파티션, 스왑 파일)이 필요하다.
이 저장소는 각 프로세스의 메모리 이미지를 직접 접근할 수 있어야 한다.
메모리 이미지: 프로세스가 실행될 때 사용하는 전체 메모리 공간. (코드 + 데이터 + 스택 + 힙)

Swapping 목적

메모리 초과 문제 해결
- 동시에 실행 중인 프로세스의 총 메모리 요구량이 실제 물리 메모리 용량을 초과할 수 있다. 스와핑을 통해 더 많은 프로세스를 관리할 수 있다.
우선순위 관리
- 우선순위가 낮은 프로세스를 스와핑 아웃(roll out) 하고, 높은 프로세스를 스와핑 인(roll in)하여 관리한다.

성능 및 한계

스와핑 시간(transfer time):
- 디스크와 메모리 간 데이터 전송 시간이 스와핑의 주된 비용이다.
  이 시간은 스와핑되는 메모리 크기에 비례한다.(크면 시간이 길어진다.)
문맥 교환 시간 증가:
- 스와핑이 필요한 상황에서는 문맥 교환(context switch) 시간이 매우 길어질 수 있다.
- 예를 들어, 100MB 프로세스를 디스크로 스와핑(50MB/s 전송 속도, 8ms 디스크 지연) → 스와프 아웃 2008ms, 스와프 인 2008ms, 총 4초 이상 소요될 수 있다.

swapping과 주소 바인딩

스와핑된 프로세스가 반드시 같은 물리주소로 돌아와야 하는가?

주소 바인딩 방식에 따라 다르다.
- Compile-time/Load-time 바인딩: 반드시 같은 위치로 돌아와야 한다. -> 메모리 특정 위치에서 실행될 것이라고 "결정"된 상태기 때문에 다른 물리 주소로 돌아올 경우 논리 주소와 맞지 않아 문제 발생한다.
- Excution-time 바인딩: 어디로든 이동 가능하다. (MMU)필요.
I/O충돌 문제:
- 스와핑 중인 프로세스가 입출력 작업을 하고있다면, 해당 I/O가 완료될 때까지 스와핑을 지연해야 할 수 있다.

운영체제 실제 활용

현대 OS(리눅스, 윈도우, UNIX등)에서는 보통 비활성화 되어있다.
시스템 메모리 사용량의 임계치를 초과하면 스와핑을 활성화 하고, 다시 줄어들면 비활성화 한다.
완전한 스와핑 보다는 "가상 메모리"방식이 더 일반적이다.

스와핑의 ready queue

스와핑된 프로세스들은 디스크에 메모리 이미지가 저장된 채로 "Ready Queue"에 남아있다.
CPU가 해당 프로세스를 실행하려 할 때, 메모리로 다시 불러와야 한다.

Contiguous Allocation (연속 할당)

연속할당은 메모리 관리 기법의 상위 개념으로 고정분할과 동적분할을 모두 포함하는 더 큰 개념이다.

메인메모리 구조 - 보통 두개의 파티션으로 나뉜다.

운영체제(resident OS): 메모리의 하위(낮은 주소)영역에 상주하며, 인터럽트 벡터 등 시스템 코드가 위치한다.
사용자 프로세스: 나머지 영역에 사용자 프로그램이 적재된다.
각 프로세스는 메모리 내에서 하나의 연속적인(contiguous)공간에 할당되어야 한다.

장점

구조가 단순하고, 구현이 쉽다.
프로세스마다 시작 주소와 크기만 알면 된다.

보호와 격리

Relocation Register(재배치 레지스터, Base Register):
프로세스가 사용할 수 있는 "가장 작은 물리 주소"를 저장한다.
Limit Register(한계 레지스터):
프로세스가 사용할 수 있는 "주소 범위(크기)"를 저장한다.
이 두 레지스터를 통해, 프로세스가 자신의 메모리 구역만 접근하도록 하드웨어적으로 보호할 수 있다.

CPU가 논리주소를 생성한다.
limit 레지스터와 비교를 해서 크면 trap을 걸고, 아니면 다음으로 진행한다.
relocation값을 더해 실제 물리주소를 계산한다.
계산된 물리 주소로 메모리에 접근한다.

요약

프로세스 보호
: 한 프로세스가 자신의 limit을 넘는 주소를 접근하려고 하면 trap이 발생해, 다른 프로세스나 OS 영역을 침범하지 못하도록 하드웨어적으로 보호한다.
동적 재배치
: 프로세스가 메모리 내 어디에 적재되든, relocation register만 바꿔주면 동일한 논리 주소로 프로그램을 실행할 수 있다.
OS 유연성
: 커널 코드가 일시적으로 크기가 변하거나, 여러 프로세스가 동적으로 적재/해제되는 상황에서도 각 프로세스의 base/limit만 바꿔주면 안전하게 관리할 수 있다.

Paging

기존의 고정 분할과 동적 분할은 외부 단편화 문제로 인해 메모리 활용률이 떨어진다. 따라서 메모리와 프로세스를 모두 고정크기블록으로 나누어서 관리하는 방법이다.

목표

외부 단편화 문제 해결
메모리 공간을 더 유연하고 효율적이게 관리
프로세스가 연속된 물리 메모리 공간에 할당되지 않아도 되게 함(나눴기 때문)

Paging의 기본 아이디어

메모리와 프로세스 모두를 "고정 크기 블록"으로 나눈다.
- 물리 메모리의 고정 크기 블록 = 프레임(Frame)
- 프로세스(논리 메모리) 동일 크기 블록 = 페이지(Page)
각 프로세스의 페이지를 물리 메모리의 아무 프레임에 할당 가능하다.
- 프로세스의 논리적 주소 공간은 연속적이지만, 실제 물리 메모리 상에서는 여러 군데 흩어져 있을 수 있다는 뜻.

✅ 페이지 테이블?

각 논리적 페이지가 물리 메모리의 어느 프레임에 위치해 있는지 매핑 정보를 저장하고 있는 것.

논리주소 = (페이지 번호 p, 페이지 오프셋 d)
페이지 테이블에서 p를 참조해 해당 페이지가 적재된 프레임 번호를 찾고, 프레임 시작 주소 + d를 해 실제 물리 주소를 계산한다.
오프셋 = 페이지 내에서의 상대적 위치

주소 변환(address Translate)

CPU가 논리 주소(virtual address)를 생성
: 논리 주소는 (페이지 번호 p, 오프셋 d)로 분리
페이지 테이블 참조
: 페이지 번호 p를 페이지 테이블에 입력하여, 해당 페이지가 적재된 프레임 번호 f를 얻음
물리 주소 계산
: 물리 주소 = (프레임 번호 f) × (프레임 크기) + d

논리주소 공간이 16비트고, 페이지 크기는 1Kb(1024바이트)이다.
한 페이지에 1024개의 주소가 있기 때문에 오프셋을 표현하기 위해서는 10개의 비트가 필요하다.
따라서 오프셋 = 10비트, 남은 6개는 페이지 번호.
왜 오프셋은 페이지 크기를 따르는가? => 오프셋은 페이지내에서의 상대적 위치기 때문!!

☝️ 그림 (a) - Partitioning -> 연속 할당

2700바이트 크기의 사용자 프로세스가 메모리 내 연속된 공간을 할당하고 있다.
주소 0부터 2699까지가 프로세스 메모리 공간이다.
주소 1502는 프로세스 내에서 1502번째 바이트를 의미한다.

✌️ 그림 (b) - Paging

동일한 2700바이트 프로세스가 1024바이트 단위로 나뉜다.
각 페이지는 물리 메모리의 아무 프레임에서 할당이 가능하다.
page 0(0~1023), page 1(1024~2047), page 2는 2700까지 일부만 사용
주소 1502는 페이지 1의 478번 바이트에 위치하고 있다.(1024 + 478 = 1502)

Step 1: 논리주소를 [페이지][오프셋]으로 분리.
-> 1502의 페이지 번호는 1이고 offset은 478인걸 확인했다.
Step 2: 페이지 테이블에서 프레임 번호 찾기.
-> 페이지 번호 1을 페이지 테이블의 인덱스로 사용한다.
-> 페이지 테이블 1에서 프레임 6을 가르키고 있다.
Step 3: 물리 주소 계산
-> 물리주소 = (프레임 번호) x (프레임 크기) + 오프셋
-> 6 * 1024(페이지가 1024이기 때문) + 478 = 6622

⚠️ 물리 주소 공간은 논리 주소 공간보다 항상 크거나 같아야 한다.
⚠️ 페이지 크기 = 프레임 크기, 오프셋 비트 수가 동일해야 변환이 일관되게 이루어 진다.

Paging 장점

외부 단편화 없음
: 페이지/프레임이 모두 고정이기 때문에 빈 프레임만 있으면 어디든 할당이 가능하다
효율적 메모리 활용
: 프로세스가 연속된 공간에 할당될 필요가 없으므로 효율성이 좋다.
가상 메모리 구현의 기반
: 프로세스 일부만 메모리에 올려서 실행이 가능하다.

Paging 단점

내부 단편화
: 마지막 페이지가 완전히 채워지지 않으면 남는 공간이 발생하긴 한다.
페이지 테이블 오버헤드
: 각 프로세스마다 페이지 테이블을 유지해야 하기 때문에, 주소 공간이 클수록 테이블도 커지게 된다.

프레임 번호화 오프셋을 이용해 실제 물리 주소를 얻어오는 과정

이런식으로 실제로는 물리 메모리에 나눠져서 저장되어 존재한다.

자 이제 이 그림을 통해 이해도의 막바지로 향해보자. 위에서 했던 내용을 반복하는 것이다.

m: 논리 주소의 전체 비트 수 (여기서는 4비트)
n: 오프셋 비트 수 (즉, 한 페이지 내에서 위치를 지정하는 데 필요한 비트 수)
페이지 크기: 2^n 바이트 (여기서는 4바이트)
페이지 번호 비트 수: m−n (여기서는 2비트)

Paging의 내부 단편화

페이징은 외부 단편화는 완전히 해결하지만 내부 단편화는 여전히 발생할 수 있다.

내부 단편화는 프로세스의 메모리 요구량이 페이지 크기의 정수배로 딱 맞지 않을 때, 마지막 페이지에 남는 미사용 공간이 낭비되는 현상.
페이지 크기가 클수록 내부 단편화가 커진다.

예시

프로세스 크기: 10KB
페이지 크기: 4KB

일 경우네는

필요한 페이지 수: ⌈10KB / 4KB⌉ = 3페이지 (12KB 할당)
내부 단편화: 12KB - 10KB = 2KB

즉, 2kb만큼 비는 현상이 발생.

프로세스 크기: 7KB
페이지 크기: 4KB

일 경우에는

필요한 페이지 수: ⌈7KB / 4KB⌉ = 2페이지 (8KB 할당)
내부 단편화: 8KB - 7KB = 1KB

1kb가 비는 현상이 발생한다.

✅ 내부 단편화 크기 = (할당된 페이지 수 * 페이지 크기) - 프로세스 크기

페이지 크기가 작다면
: 내부 단편화는 어느정도 해결.
: 하지만 페이지 테이블의 크기가 커지고, 오버헤드 발생
페이지 크기가 커지면
: 페이지 테이블이 작아지고, 메모리 접근이 빨라지지만
: 내부 단편화가 증가.

Free Frame

아직 어떤 서비스에도 할당되지 않은, 비워져있는 프레임을 의미한다.

Before allocation (a)

free-frame list:
- 현재 사용 가능한 프레임 번호들이 리스트로 관리되고 있다.
  (예: 14, 13, 18, 20, 15)
new process:
- 새로운 프로세스가 메모리에 올라오려고 할 때, 그 프로세스의 각 페이지(page 0, 1, 2, 3)를 저장할 프레임이 필요하다.

After allocation (b)

free-frame list:
- 프로세스에 할당된 프레임(14, 13, 18, 20)이 리스트에서 빠지고,
  남은 프레임(15)이 리스트에 남아 있다.
new-process page table:
- 프로세스의 각 페이지가 어느 프레임에 저장되어 있는지 기록
  (page 0 → frame 14, page 1 → frame 13, page 2 → frame 18, page 3 → frame 20)
메모리 상태:
- 실제로 프레임 14, 13, 18, 20에 각각 page 0, 1, 2, 3이 저장됨

Implementation of Page Table - 페이지 테이블 구현

PTBR(Page Tabel Base Register)

현재 프로세스의 페이지 테이블의 시작주소를 가르킨다.
-> 프로세스가 전환될 때마다 운영체제가 이 레지스터를 갱신한다.
PTLR(Page Table Length Register)

페이지 테이블의 크기를 저장한다.
-> 논리 주소가 유효한 범위내에 있는지 검사하는데 사용된다.

페이지 테이블 접근의 성능 문제

두 번의 메모리 접근 필요: CPU가 논리 주소를 생성할 때마다

페이지 테이블에서 프레임 번호를 읽고 (메모리 접근 1회)
실제 데이터/명령어에 접근 (메모리 접근 2회)
→ 성능 저하 발생.

TLB(Translation Look-aside Buffer)

페이지 테이블 접근 오버헤드를 줄이기 위한 하드웨어 캐시다.

동작
- CPU가 논리 주소를 생성하면, TLB에 해당 페이지가 존재하는지 확인한다.
- TLB히트 일 경우: TLB에서 프레임 번호를 즉시 얻어 물리 주소 생성.
- TLB미스 일 경우: 메인 메모리의 페이지 테이블을 접근하고, TLB에 엔트리를 갱신.
- 예: TLB 접근 시간 = 10ns, 메모리 접근 시간 = 100ns, 히트율 90%
  → 평균 접근 시간(EAT) = 0.9×(10+100) + 0.1×(10+100+100) = 120ns
특징
- ASID(Address-Space Identifier): 각 TLB 엔트리에 프로세스 식별자를 저장해, 컨텍스트 스위칭 시 TLB를 플러시(flush)하지 않아도 된다. (flush = 삭제)
  → 여러 프로세스의 페이지 테이블 엔트리가 TLB에 공존 가능.

페이지 테이블 관리

프로세스 생성/종료 시 페이지 테이블을 메모리에서 할당/해제.
context switching시 PTBR,PTLR을 갱신.
TLB 미스 발생시, 페이지 테이블에서 프레임 번호를 찾아 TLB를 업데이트 한다.

Memory Protection

보호비트(Protection Bit)
: 각 프레임에 대한 접근 권한(읽기/쓰기/실행)을 지정한다.
-> 잘못된 접근 시 trap발동
Valid-Invalid Bit
: 페이지가 프로세스의 논리 주소 공간에 속하는지 여부를 표시한다.
-> 무효한 페이지 접근 시 트랩 발생.
PTLR
: 페이지 번호가 크기를 초과하는지 검사한다.

Shared Pages

공유 코드(Shared Code)
- 여러 프로세스가 동일한 코드(예: 라이브러리)를 공유할 수 있다.
- 메모리 효율성이 좋아진다.
읽기 전용(read-only)
- 공유 코드는 일반적으로 수정되지 않으므로, 복사 없이 직접 참조한다.
전용 데이터
- 각 프로세스의 데이터는 별도의 프레임에 저장된다.

페이지 테이블 구조의 진화와 다층적 접근법

단일 수준 페이지 테이블의 문제점

32 비트 논리 주소 공간에서 4kb(2^12)의 페이지를 사용할 경우

페이지 테이블의 엔트리(PTE) 수: 32-12 = 20 -> 2^20 약 백만개
각 엔트리 크기 4바이트 시 총 4MB 메모리가 소요 (1백만 * 4)
연속 메모리 할당 필요 -> 실제 사용 영역이 희소(sparse)할 경우 비효율적이다.
희소: 공간이 넓게 있지만 실제로 사용되는 부분은 일부인 것.
예: 프로세스가 4GB중 1%만 차지해도 4MB 페이지 테이블 전체를 유지하게 된다. -> 비효율 적이다.

2단계 페이지 테이블 구조

Step 1
: outer page table이 실제 페이지 테이블들의 위치를 가르킨다.
Step 2
: 각 페이지 테이블이 실제 데이터가 저장된 메모리 프레임을 가리킴.

논리 구조의 3단계 분할
- PDI(P1): 페이지 디렉토리의 index를 가르킨다.
- PTI(P2): 페이지 테이블의 항목을 가르킨다.
- Offset(d): 페이지 내에서의 상대적 위치
Step 1: 페이지 디렉토리 접근
- PDBR(Page Directory Base Register)이 페이지 디렉토리의 시작 주소를 가르킨다.
- 논리주소의 P1 필드를 사용하여 PDE(Page Directory Enrty)위치를 계산한다.
- PDE에서 페이지 테이블의 물리 주소를 획득한다.
Step 2: 페이지 테이블 접근
- 1단계에서 얻은 물리 주소로 Page Table에 접근한다.
- 논리 주소의 P2 필드를 사용하여 해당 PTE위치를 계산한다.
- PTE = Page Table Entry
- PTE에서 실제 데이터가 저장된 Frame Number를 얻는다.

✅ 페이지 디렉토리?

페이지 테이블의 물리 주소를 저장하는 최상위 테이블.

✅ 페이지 테이블?

실제 데이터/코드 페이지의 물리 주소를 저장한다.

Multi-level Paging

✅ Offset(d)

Offset은 하나의 1KB 페이지 안에서 특정 바이트의 위치를 식별하는 데 사용.
1KB = 1024 = 2^10 바이트 이기 때문에 offset은 10비트가 필요함

✅ 페이지 테이블 인덱스(PTI)

PTI는 각 페이지 테이블의 크기를 1KB로 유지하는 것이다.
PTE(페이지 테이블 Entry)가 4바이트라면, (1024/4 = 256)256개를 저장할 수 있기 때문에 (2^8 = 256) 8비트가 필요함.

✅ 페이지 디렉토리 인덱스(PDI)

전체 주소 공간은 32비트 이기 때문에 32 - 10 (오프셋) - 8(PTI) = 14비트 남음.
이 남은 14비트가 PDI로 사용된다.

✅ 페이지 디렉토리(Page Directory)

페이지 디렉토리: 2^14개를 가짐(PDI필드 개수)
전체 크기 = 2^14 * 4(PDE 크기) = 64KB
저장위치: 64개의 연속된 물리 프레임에 저장된다.

✅ 페이지 테이블(Page Table)

페이지 테이블: 각 데이터나 코드 페이지의 물리적 주소를 저장하는 항목들로 구성됨.
항목 수: 2^8 = 256개(PTI 필드)
PTE가 4바이트기 때문에 1024, 1KB
저장 위치: 각 페이지 테이블은 정확히 1개의 물리 프레임에 딱 맞게 저장됨.

✅ 페이지 디렉토리 항목(PDE)

PDE 사이즈는 4바이트다.(PTE와 마찬가지로)
포함하는 정보: 22비트짜리 페이지 테이블의 물리 프레임 번호
제어 비트
- presence bit (자원이 유효한지 여부)
- read-only (읽기 전용 여부)
- user/kernel (사용자 모드 / 커널 모드 접근 여부) 등
항목 수: 2^14개의 PDE (PDI 필드에서 나온 인덱스 개수)

Multi-level 장점

1. 메모리 사용량 감소(Reduced Memory Concumption)

온디맨드 할당: 실제 사용되는 가상 주소 범위에 대해서만 페이지 테이블 생성
계층적 구조: 페이지 디렉토리 → 페이지 테이블 → 데이터 페이지의 2단계 구조

2. 희소 주소 공간 효율 처리(Sparse Address Handling)

실제 사용하는 일부 주소 영역에 대해서만 페이지 테이블이 할당된다.

3. 스와핑이 간단해 진다.

프로세스의 가상 메모리 중 대부분이 디스크로 스왑 아웃되었을 경우,
OS는 해당 페이지 디렉터리 항목(PDE)만 "없음(not present)"으로 표시하면 됨.
굳이 모든 페이지 테이블 항목(PTE)을 하나하나 비활성화할 필요 없음.

4. 향상된 메모리 활용

필요 없는 페이지 테이블이 줄어드니,
전체 물리 메모리 중 페이지 테이블이 차지하는 부분이 적어짐.
그만큼 더 많은 공간을 실제 프로세스 데이터에 사용할 수 있음.

Multi-level 단점

주소 변환 지연 증가

메모리에서 데이터를 읽기 위해서는, 페이지 디렉터리 항목(PDE) 한 번 + 페이지 테이블 항목(PTE) 한 번 = 총 두 번의 메모리 접근이 필요하게 됨

해결방법: TLB, Hashed Paging

TLB: CPU안에 있는 작고 빠른 하드웨어 캐시.

Hashed Paging

가상 주소를 분할한다.

| VPN (가상 페이지 번호) | Offset (페이지 내 위치) |

VPN = Virtual Page Number

해시 함수 적용

hash_index = (VPN * prime) % hash_table_size

index개수는 마음대로 생성한다.

해시 탐색

VPN을 해시를 해서, 해시 테이블(HPT)의 인덱스로 한다. 그러면 더 많은 집합에서 하위 집합으로 간것이기 때문에 무조건 충돌 내용들이 존재, 그중에서 추가적인 리스트를 만들어, 해당하는 내용을 찾으면 됨.
이렇게 가져온 내용(Physical Frame Number-PFN)과 Offset을 합치면 물리주소가 나온다.

이런식으로 해쉬 값이 중복되는 애들은 리스트나 링크드 리스트를 통해 따로 관리한다. 그러면 테이블 전체를 확인하는 것이 아니라 작아진 해시 충돌 값 내에서 테이블을 확인하면 된다.

장점

빠르다. -> 충돌이 적은게 베스트
메모리 효율성 (Memory Savings) -> 미사용 영역에 대한 페이지 테이블 공간을 전혀 할당하지 않음.

단점

충돌이 많으면 성능이 떨어진다. -> 해시 테이블을 늘리면 어느정도 해결되지만 그럴꺼면 그냥 페이지 테이블 전체를 봄.
캐시 비효율성 -> 지역성 원칙이 적용되지 않기 때문에.
복잡함 -> 균일 분포를 보장하는 해시 함수를 개발하는 것은 매우 어려움.
사실 그래서 multi-level을 더 많이 씀

Inverted Paging

원래는 Key값으로 value를 찾는데, 반대로 value로 key를 찾는 것.

저장: 원래는 frame을 찾는 것이지만, 각 프레임을 키로 어떤 가상 페이지와 어떤 프로세스가 frame을 사용중인지를 저장함.

Inverted Paging 동작

CPU는 가상 주소로 접근하려고 한다.

|F#|PID|VPN|

이런식으로 되어있기 때문에 CPU는 PID를 알아 테이블에서 정보를 얻을 수 있음.
이거를 offset과 합쳐서 물리 주소를 얻는다.

찾는법

그렇다면 테이블이 일자로 쭉 있는 상태에서 어떻게 찾는게 효율적일까?

먼저 Simple Serch는 느리다. -> 모든 테이블을 읽으니까.
해시를 이용한다. -> PID와 VPN을 이용해 해시한다.

장점

페이지의 개수가 적어진다. -> PID와 VPN값을 같이 저장하기 때문에
테이블을 하나만 사용하기 때문에 관리가 더 용이하다.

단점

search가 오래걸린다.
구현이 복잡해진다.
shared Memory와 같은 기법이 활용이 되기 어렵다.

Virtual Memory

logical 메모리와 실제 메모리 공간을 분리시켜주는 기술이다.

위에서 배운 내용처럼 CPU가 logical 메모리에 어떤 정보를 요청하게 되면 MMU는 그것을 physical memory에서 가져오고 그것을 logical에 전달하는 식으로 CPU는 정보를 받게 되는 것이다.
그렇다면 만약에 physical memory에 없고 디스크에 올라가있는 데이터를 가져오려고 CPU가 시도를 하게 되면 어떻게 될까?
MMU는 일종의 캐시처럼 동작하게 되는데, 디스크에서 데이터를 가져와서 logical 메모리에 가져오게 된다.

사실 프로그램의 모든 내용이 미리 메모리에 올라와 있으르 필요가 있을까?
파워포인트를 사용한다고 하면 일부 기능만 사용하는데, 다 올리면 낭비인 부분이 생기게 된다. -> 지역성 원칙
따라서 logical 메모리 공간을 실제 물리주소보다 더 크게 관리를 해도 적절하게 불러올 수 있다면 문제없는 것이다.
심지어 내 렘이 16기가인데 실행시키고 싶은 프로세스가 20기가면 out of memory가 발생할까? -> 정답은 No!, 초과부분은 그냥 디스크에 넣어두고 번갈아 가면서 동작시키면 된다.(성능저하는 피할 수 없음)

그렇다면 이러한 Virtual Memory는 어떻게 구현할 수 있을까?