OS ch08. Memory Management

김민성·2026년 5월 25일

운영체제(OS)

목록 보기

8/8

이번 장에서는 메모리 관리의 개념과 그 기법들에 대해 다룬다.

Background

프로그램은 메모리에 올라와야 실행된다

디스크에 저장된 프로그램은 실행되기 전에 반드시 메모리에 적재되어 프로세스가 되어야 CPU가 실행할 수 있다. 이때 하드디스크에 위치한 프로세스들이 메모리로 올라가기 위해 대기하는 큐를 input queue라고 한다. 즉 inqut queue를 통해 메모리로 올라온다.

프로그램은 실행되기 전에 아래와 같은 여러 단계를 거친다.

User Program의 처리 단계

1. 소스 코드 작성
2. 컴파일 (object module 생성) 단계
3. 링킹 (load module 생성) 단계
4. 로더(loader)를 통해 main memory에 자리를 잡고 실행됨

이 흐름이 중요한 이유는 주소 바인딩(Address Binding)이 이 과정의 어느 시점에 일어나느냐에 따라 방식이 달라지기 때문이다.

Address Binding

Address Binding이란 프로세스의 명령어와 데이터를 메모리에 매핑하기 위해, 프로그램이 사용하는 논리적 주소를 실제 메인 메모리의 물리적 주소와 연결하는 작업이다.

아래의 3가지 시점에 바인딩 작업이 이뤄질 수 있다.

세 가지 시점

Compile Time Binding: 사전에 프로그램이 메모리의 몇번지에 적재될지 정보를 미리 알 때 수행되며, 컴파일 시점에 바인딩 된다.
Load Time Binding: 사전에 적재 위치를 모를 때, 컴파일러는 일단 재배치 코드(relocatable code)를 생성하고 실제 메모리에 로딩되는 시점에 주소 바인딩이 이뤄진다.
Execution Time Binding: 프로세스 실행 중 프로세스가 메모리의 다른 위치로 이동할 수 있는 환경에서 사용된다. 이 경우 주소 변환이 실행시간에 계속 일어나야하므로 하드웨어 지원(base/limit register, MMU)이 필요하며, 최종적인 바인딩은 실제 명령어가 실행되는 막판 시점까지 지연된다.

Logical Address vs Physical Address

Logical address: CPU에 의해 임의로 생성되는 주소이다. 실제 메모리에 할당된 물리적 위치와는 전혀 상관이 없기 때문에 virtual address라고도 불린다.
Physical address: 크기가 한정된 실제 메모리 상에 할당된 주소이다. 메모리 공간에서 워드 단위로 하나씩 할당돼있는 실제 위치 번지수를 뜻한다.

바인딩 시점에 따라 logical address와 physical address가 같을 수도, 다를 수도 있다.

Compile-time / Load-time binding에서는 둘이 같다. 프로그램이 메모리에 올라갈 위치가 미리 고정되거나 load 시점에 확정되므로, CPU가 내보내는 주소가 곧 실제 메모리 주소가 된다.

반면 Execution-time binding에서는 두 주소가 서로 다르다. 메모리에 한번 올라온 프로세스라도 실행 도중 다른 메모리 구역으로 위치를 이동할 수 있기 때문에, 최종 physical address는 실행되는 순간에 계속 바뀔 수 있기 때문이다.

MMU (Memory-Management Unit)

MMU(Memory-Management Unit)는 논리 주소를 물리 주소로 변환해주는 하드웨어 장치다.

relocation register + logical address = physical address

즉 MMU 내부에 있는 relocation register의 값과 logical addr의 값을 더한 값이 최종 physical addr의 값이 된다.

relocation register = 14000
logical address     = 346
physical address    = 14000 + 346 = 14346

이때 사용자 프로그램(프로세스)은 오직 logical address만 다루며, 본인의 데이터가 진짜 메모리의 몇번지에 저장돼있는지는 절대 알지 못한다.

Dynamic relocation using a relocation register

Dynamic relocation은 메모리에 적재돼 실행 중인 프로세스의 위치가 도중에 위 그림처럼 동적으로 바뀔 수 있도록 지원하는 기능이다.

CPU가 임의로 발생시키는 논리적 주소는 프로그램 내부의 상대적 위치일뿐 실제 주소가 아니다. 이 논리적 주소를 실제 메모리 위치로 매핑하기 위해, 해당 프로세스에게 할당된 실제 물리적 메모리의 시작 위치를 재배치 레지스터가 갖고있는 것이다.

즉 실행 도중 프로세스의 메모리 위치가 바뀌어도 상관 없는 이유는, 재배치 레지스터의 값만 새롭게 이동한 위치의 값으로 업데이트해주면 되기 때문이다.

이러한 dynamic relocation 방식은 메모리 관리를 효율적으로 하기 위해 프로세스들을 한쪽으로 밀어버리는 Compaction 작업에서도 중요하게 쓰인다. 메모리 곳곳에 흩어진 작은 빈 조각들을 모아 큰 여유공간을 만들기 위해 프로세스들을 이동시킬때, dynamic reloaction이 있기에 위치 이동이 가능한 셈이다.

Dynamic Loading과 Dynamic Linking

Dynamic Loading

프로그램의 특정 루틴(코드)이 실제로 호출돼 사용되기 전까지는 메모리에 적재하지 않는 기법이다.

즉 기존의 static loading은 프로그램이 실행될때 코드 전체를 한꺼번에 메모리에 올려버리는 반면 dynamic loading은 프로그램 내부의 특정 루틴(함수나 서브프로그램)이 호출되기 전까지는 메모리에 적재하지 않고 디스크에 놔두고, 실행 중에 해당 루틴이 실제로 필요한 순간, 이미 메모리에 올라와있는지 확인하고 없다면 그때서야 load한다.

호출되지 않는 코드는 메모리에 올라가지 않으므로 메모리 공간을 훨씬 효율적으로 사용할 수 있으며, 발생빈도는 낮지만 처리하기 위해 매우 방대한 양의 코드가 필요한 경우에 유용하게 쓰인다.(ex:에러 처리 루틴)

Dynamic Linking

프로그램에서 사용하는 시스템 라이브러리 함수 등의 linking 작업을 처음부터 수행하지 않고, 프로그램이 실제로 실행되는 시점(Execution time)까지 최대한 지연시키는 기술이다.

기존 static linking은 자주 쓰는 라이브러리들을 초기에 모조리 연결(linking)시켜 메모리에 올려놓는 반면 dynamic linking은 라이브러리를 연결시키지 않고 놔뒀다가 프로그램이 실제로 실행될 때 연결한다.

이때 stub라는 일종의 메모 쪽지 역할을 하는 개념을 이용하는데, 사용하려는 라이브러리 함수가 메모리의 몇번지에 위치해있는지에 대한 주소 정보만을 stub에 기록해둔다.

프로그램이 쭉 실행되다가, 마침내 해당 함수가 실제로 필요한 실행시점(Execution time)이 되면, stub에 적혀있던 주소값을 보고 메모리에 접근하고, 거기 있는 해당 라이브러리 함수의 코드를 가져와 실행시킨다.

즉 이 기법이 정상적으로 작동하려면 호출하려는 대상 라이브러리 함수들이 이미 메모리 위에 올라와있어야하고, 메모리 위에 올라와있는지 아닌지를 체크해주는건 운영체제의 몫이다.

Swapping

Swapping은 한정된 메인 메모리 공간의 한계를 극복하기 위한 방법으로, 프로세스를 통째로 메모리와 하드디스크 사이에서 교환하는 메모리 관리 기법이다.

Swap-out: CPU가 지금 당장 실행하지 않고 대기 중인 프로세스를 메인 메모리에서 잠시 빼내 backing store로 쫓아낸다.
Swap-in: backing store에 있던 프로세스가 다시 실행되어야할 때가 오면 다시 메인 메모리로 불려들여 실행을 이어간다.
Backing store: 메모리에서 밀려난 프로세스들을 임시로 보관하는 하드디스크 공간이다. 메모리에서 내려온 모든 정보들을 다 백업할 수 있을만큼 충분히 커야한다.
Roll-out & Roll-in: 우선순위 기반 스케줄링에서 주로 사용하는 swapping 방식으로, high-priority 프로세스가 주소공간에 들어왔는데 메모리가 부족하다면, 현재 메모리에 있는 low-priority 프로세스를 디스크로 쫓아내고(roll-out), high-priority를 메모리에 올려 실행한다.(roll-in)

swapping 소요 시간은 메모리와 디스크 사이에서 전송되는 데이터와 프로그램의 양에 비례한다.

Contiguous Allocation (연속 할당 방식)

연속 메모리 할당 방식은 프로세스가 메모리에 적재될 때 한 덩어리로 연속적으로 붙어있는 빈 공간(파티션)을 통째로 할당해주는 기법이다.

single-partition allocation방식에서 메모리는 보통 두 영역으로 나뉜다.

낮은 주소 영역: 운영체제
높은 주소 영역: 사용자 프로세스

Base Register와 Limit Register

프로세스가 자기 영역 밖을 침범하지 못하도록 두 레지스터로 보호한다.

Base Register: 특정 프로세에게 할당된 실제 물리적 메모리의 시작 주소 값을 나타낸다. 즉 프로세스가 메모리의 몇번지부터 자리 잡았는지를 알려주는 기준점 역할을 한다.
Limit Register: 그 시작주소로부터 얼마만큼의 메모리 공간을 사용할것인지에 대한 크기 정보를 나타낸다. 즉 이 프로세스에게 허락된 전체 메모리 영역의 길이를 말한다.

두 레지스터를 활용한 Memory Protection

CPU가 특정 메모리 주소에 접근을 시도할 때, 시스템은 이 두 레지스터를 이용해 해당 접근이 정당한지 검사해 메모리를 보호한다.

접근하려는 주소값이 base register에 기록된 시작 주소값보다 크거나 같은지 확인한다.
또한 그 주소값이 base register의 값 + limit register의 값보다 작은지 확인한다.
만약 이 허용된 범위를 벗어난다면, 시스템은 이를 유효하지 않은 접근으로 간주하고 트랩(에러)을 발생시켜 접근을 즉각 차단한다.

multiple-partition allocation방식에서는 메모리의 사용자 영역을 여러 개의 조각으로 쪼개서 사용한다.

Hole과 할당 방식

프로세스가 종료되면 빈 메모리 블록인 hole이 생긴다. 위 그림 속 회색 부분이 hole이다. 새 프로세스가 메모리에 들어오려고 하면, OS는 흩어져있는 빈 공간들을 탐색하다가 그 프로세스를 수용할 수 있을만큼 충분히 큰 hole을 찾아 거기에 집어넣는다.

이때 운영체제는 항상 아래 두가지 상태를 테이블에 기록, 관리해야한다.
1. 현재 어느 프로세스들이 메모리 어디를 차지하고있는지
2. 현재 메모리 어디어디가 비어있고, 그 크기는 얼마인지

그럼 흩어져 있는 hole들 중에 뭘 내줘야할까?
이걸 결정하는 방식은 아래 3가지가 있다.

First-fit: 테이블을 검색하다가 프로세스가 요청한 크기보다 큰 첫번째 hole이 발견되면 무조건 즉시 할당하는 방식이다. 속도 측면에서 가장 유리하다.
Best-fit: 전체 리스트를 다 검색한 뒤, 조건을 만족하면서도 남는 자투리공간이 가장 최소가 되는 hole을 찾아 할당하는 방식이다. 메모리 공간 이용률이 가장 좋다.
Worst-fit*: 전체 리스트를 다 뒤져 가장 큰 hole을 할당하는 방식이다. 할당 후 남는 부분(leftover)을 최대한 큼직하게 남겨 향후 다른 프로세스가 쓸수있는 hole로 만들고자 하는 의도다.

Fragmentation

연속 할당 방식은 메모리 공간이 작은 조각으로 나눠져 메모리가 낭비되는 단편화 문제가 발생한다.

단편화 종류로는 외부 단편화와 내부 단편화가 있다.

External Fragmentation

여기저기 흩어진 빈 hole들을 모두 합치면 요청한 크기를 충분히 만족하지만, 연속된 한 덩어리가 아니기 때문에 정작 프로세스에게 메모리를 할당해주지 못하는 상태다.

이는 Compaction으로 해결할 수 있다.

Compaction

Compaction이란 외부 단편화 문제를 해결하기 위한 메모리 공간 압축 기법이다.

compaction이란 메모리 곳곳에 여기 찔끔 저기 찔끔 작게 흩어져있는 빈 hole들을 모아 하나의 큰 빈 hole로 만들기 위해, 흩어져 있는 프로세스들을 메모리의 한쪽 방향으로 쫙 밀어버리는 작업이다.

예를 들어 프로세스의 위아래로 작은 hole들이 있을때 이 프로세스를 한쪽으로 밀어붙이면 반대쪽에 흩어져있던 공간들이 합쳐져 더 큰 공간이 만들어지게 되며, 이를 통해 크기가 큰 새로운 프로세스도 수용할 수 있게 된다.

이때 앞서 살펴본 dynamic reloaction 기술이 뒷받침되어야만 compaction이 가능하다. 실행 중인 프로세스의 물리적 메모리 위치가 도중에 바뀌더라도 MMU의 지원을 통해 올바른 주소를 찾아갈 수 있기 때문이다.

I/O 문제

compaction을 수행할때 심각한 입출력 문제가 발생할 수 있다. 만약 어떤 프로세스가 디스크 읽기 등의 I/O 작업을 요청해 둔 상태에서 컴팩션이 일어나 메모리의 다른 위치로 밀려났다고 가정해보자. I/O 작업이 완료돼 그 결과를 메모리에 쓰려고 할때, 프로세스는 이미 다른 곳으로 이동했음에도 불구하고 과거의 위치에 덮어써버리는 치명적 오류가 발생할 수 있다.

이러한 주소 꼬임 문제를 방지하기 위해, 모든 I/O 작업은 메모리 내에 미리 지정된 운영체제 버퍼 영역으로만 수행하도록 제한한다. 이렇게 규칙을 정해두면 프로세스가 컴팩션으로 인해 메모리 내 어디로 밀려가있든 상관없이 I/O 결과물은 항상 고정된 OS버퍼 영역에 안전하게 기록되므로 데이터가 엉뚱한 곳에 쓰이는 문제를 원천적으로 차단할 수 있다.

Internal Fragmentation

프로세스에게 할당된 메모리 공간이 요청한 크기보다 약간 더 커서, 그 차이만큼의 공간이 쓰이지 못하고 낭비되는 상태다.

가령 100K를 요청한 프로세스에게 110K짜리 hole을 줬을때, 남는 10K를 새로운 빈 hole로 관리하는 오버헤드를 피하고자 110K를 통째로 넘겨주며 발생한다.

Compaction — 흩어진 hole을 하나로 모으는 방법이다. dynamic relocation이 가능해야 하며, I/O 작업 중인 프로세스는 고정시키거나 운영체제 버퍼를 통해 I/O를 수행해야 한다.

이 외부 단편화 문제를 해결하기 위해 Paging이 등장한다.

Paging

프로세스의 논리 주소 공간이 물리 메모리에서 연속적일 필요가 없도록 만드는 방식이다. 즉 연속 메모리 할당은 프로세스가 통째로 묶여서 메모리에 들어갔다면, 페이징은 프로세스를 잘게 쪼개서 메모리 여기저기에 흩뿌린다. 이 덕분에 연속 할당의 고질병이었던 외부 단편화가 완벽히 해결된다.

Frame: 실제 물리적 메모리를 고정된 크기로 나눈 블록
Page: CPU가 다루는 논리적 메모리를 frame과 동일한 크기로 나눈 블록

프로세스가 특정 크기(page n개)의 메모리를 요구하면, OS는 메모리 곳곳에 흩어져있는 frame들을 찾아 n개만큼 할당해준다.

이때 프로세스의 페이지들이 메모리 여기저기 흩어져있기 때문에, "논리적 페이지 몇번이 실제 메모리의 몇번 프레임에 들어있는지"를 기록해두는 page table이 필요하며, 각 프로세스는 자기 자신만의 독립적인 page table을 가진다.

하지만 이 방식은 외부 단편화 문제는 해결하지만 마지막 page가 frame을 다 채우지 못하면 내부 단편화가 생길 수 있다는 한계가 있다.

주소 변환

paging 기법에서 CPU가 발생시키는 논리적 주소는 page number와 page offset이라는 두가지 파트로 나뉘어 구성된다.

Page number(p): 논리적 주소의 앞부분을 차지하며, page table을 검색하기 위한 기준값 역할을 한다. 시스템은 이 page number를 가지고 프로세스의 page table을 뒤져서, 해당 page가 실제 물리적 메모리의 몇번 frame에 적재돼있는지를 나타내는 frame number를 찾아낸다.
Page offset(d): 논리적 주소의 뒷부분을 차지하며, 하나의 page(또는 frame) 내부에서 정확히 어느 위치에 있는지를 나타내는 상세주소 역할을 한다.

page number를 통해 page table에서 frame number를 찾고나면, 앞서 구한 frame number 뒤에 page offset 값을 아무런 변환 없이 그대로 갖다붙여서 최종적인 물리적 주소를 완성한다.

Page Table 구현

Page table은 메인 메모리에 저장된다. 아래의 두 레지스터로 관리한다.

PTBR (Page-Table Base Register)  : page table 시작 주소
PRLR (Page-Table Length Register) : page table 크기

Two Memory Access Problem

page table 자체도 메인 메모리 위에 존재한다. 따라서 CPU가 데이터를 읽거나 쓰려면 page table을 읽기 위한 접근 1번, 실제 데이터를 읽거나 쓰기 위한 접근 2번 이렇게 총 2번씩 메모리에 접근해야 하는 비효율성이 생긴다.

이러한 문제를 해결하기 위해 일종의 고속 캐시 메모리인 TLB(=Associative memory)을 사용한다.

TLB (Translation Look-aside Buffer)

주소 변환을 빠르게 하기 위한 특수 고속 캐시다 메모리다. 병렬 탐색(Parallel)이 가능해 찾고자 하는 page number를 한꺼번에 쫙 뿌려서 frame number를 순식간에 찾아낸다.

TLB Hit  : page number가 TLB에 있음 → 바로 frame number 획득
TLB Miss : page number가 TLB에 없음 → page table 접근 후 TLB 갱신

Effective Access Time (EAT)

TLB를 활용했을 때 메모리 접근 속도가 얼마나 빨라지는지 수치적으로 계산해보자.

ε : TLB를 접근하는데 걸리는 시간
1 microsecond: 메인메모리를 한번 접근하는데 걸리는 시간
α : TLB 안에서 원하는 주소를 한번에 찾을 확률

hit time  = 1 + ε
miss time = 2 + ε
EAT = (1 + ε)α + (2 + ε)(1 - α) = 2 + ε - α

α = hit ratio, ε = TLB 검색 시간
→ α가 1에 가깝고 ε가 작으면 EAT ≈ 1

즉 TLB가 없었다면 모든 메모리 접근마다 page table과 실제 데이터 확인을 위해 무조건 메모리르 2번씩 접근해야했지만, TLB를 활용하면 전체 접근 시간을 메모리를 거의 1번만 접근하는 수준으로 크게 단축시킬 수 있다는 것을 증명한 것이다.

Memory Protection

paging 방식에서의 memory protection은 page table의 각 행에 valid/invalid bit를 붙인다.

valid: 해당 page가 현재 프로세스에서 실질적으로 사용되고 있는 합법적이고 유효한 page임을 의미한다.
invalid: 해당 프로세스에게 할당되지 않았거나, 프로세스의 논리적 주소공간을 벗어난 잘못된 page임을 의미한다.

예를 들어 어떤 프로세스가 0번부터 5번까지 단 6개의 페이지만을 필요로 한다면, page table에서 이 6개의 페이지에만 v표시를 해두고, 나머지 테이블에는 모두 i 표시를 한다.

만약 프로세스가 이 i로 표시된 영역에 접근을 시도하면, 시스템은 프로세스의 정상적인 영역을 벗어난 불법적인 접근으로 간주해 즉각 차단하게 된다.

page table은 각 프로세스마다 존재하며 main memory 위에 올라가있어서 프로세스 수가 많아지면 메모리 상에서 차지하는 공간이 매우 커지는 문제가 발생한다. 따라서 이를 관리하기 위해 아래와 같은 다양한 page table 구조가 등장한다.

Hierarchical page table
Hashed page table
Inverted page table

Hierarchical Paging (Two-Level)

Hierarchical paging은 하나의 커다란 page table을 여러 개의 계층으로 쪼개는 방식으로, 마치 책의 목차에서 장과 절을 찾아가는 것과 같은 원리이다.

대표적인 방식으로 two-level paging이 있는데, 이의 구조는 아래와 같다.

위 예시는 32bit의 주소, 4KB의 page size일때의 예시이며, 4KB는 2^12바이트이므로 page 안에서의 세부위치를 나타내는데(offset) 12비트가 필요하다. 32bit-12bit=20bit이므로 page number는 20비트이다. 이때 이 20비트의 page number는 약 100만개(2^20)의 항목을 의미하므로 이를 통째로 관리하면 table이 너무 커진다. 따라서 이 20비트의 page number를 다시 p1(10비트),p2(10비트)로 나눈것이다.

전체 page number를 두 부분(p1,p2)으로 나누고, 앞의 10비트인 p1값을 이용해 outer page table을 검색한다. 검색한 결과로 찾아낸 두번째 단계의 page table(inner page table)에서 다시 나머지 10비트인 p2값을 이용해 검색해 최종 목적지인 frame number를 찾아낸다. 마지막으로 처음에 빼뒀던 12비트의 displacement값을 이 frame number 뒤에 그대로 붙여주면 실제 메모리의 물리적 주소가 완성된다.

장점

프로세스가 논리주소 공간 전체를 다 쓰지 않고 일부분만 사용해 inner page table은 메모리에 생성하지 않아도 된다. 따라서 거대한 단일 page table을 통째로 유지하는 것보다 메모리 공간을 크게 절약할 수 있다.

단점

outer page table 접근 1번, inner page table 접근 1번, 실제 데이터 접근 1번 이렇게 총 3번 메모리에 접근해야하므로 주소 변환에 걸리는 시간이 더 길어진다.

Hashed Page Table

주소 공간이 커지면 hierarchical paging 방식 사용 시 level이 4-5단계 이상으로 깊어질 수 있다. 이는 메모리를 여러 번 참조함을 의미하므로 성능이 저하될 것이다.

Hashed paging 방식은 이러한 문제를 해결하기 위한 방식으로, 주소 주소 크기가 32비트 이상인 넓은 논리적 주소 공간에서 많이 사용된다. virtual page number를 해시 함수의 입력값으로 넣어 계산된 결과값을 바탕으로 table을 검색한다.

해시 함수: 어떤 값을 넣으면 인덱스로 바꿔주는 함수

주소 변환 과정은 아래와 같다.

page number를 해시함수에 넣어 도출된 index로 hash table 접근한다.
해당 위치에 여러 항목이 있다면 pointer로 연결된 chain을 따라가며, 내가 찾고자하는 page number와 일치하는 항목을 찾고 그곳에 기록된 frame number를 추출한다.
찾아낸 frame number 뒤에, 논리적 주소에 원래 있던 displacement 값을 그대로 붙여주면 실제 물리적 주소가 완성된다.

장점

각 항목에는 특정 page number와 frame number가 쌍으로 저장되며, 전체 table을 검색할 필요 없이 해시함수의 결과 위치만 따라가면 한번 또는 몇번의 탐색만으로 원하는 frame number를 찾을 수 있어 효율적이다.

단점

서로 다른 page number가 동일한 결과를 내는 hash collision 문제가 자주 발생해 chain이 너무 길어지면 연결 리스트를 처음부터 끝까지 순차적으로 뒤져야 하므로 탐색 성능이 떨어진다.

Inverted Page Table

프로세스마다 독립적인 page table을 가진 기존의 paging 방식과 반대로, 시스템 전체에 실제 물리 메모리의 frame 개수만큼만 엔트리를 가지는 단 하나의 page table만 유지하는 방식이다.

page table의 항목(엔트리) 개수는 실제 물리적 frame의 개수와 동일하다.
table의 각 항목에는 해당 frame을 어느 프로세스(PID)의 어느 페이지(p)가 사용하고 있는지에 대한 정보가 쌍으로 기록된다.

주소 변환 과정은 아래와 같다.

논리적 주소가 발생하면, 주소 안에는 PID와 page number 정보가 쌍으로 저장돼있다.
이 정보를 가지고 page table의 맨 앞에서부터 순차적으로 하나씩 검색해나간다.
일치하는 정보를 찾게되면, 그 항목이 table에서 앞에서부터 몇번째(i번째)에 위치하는지를 확인한다. 이 i값이 곧 우리가 찾는 물리적 frame number가 된다.
찾아낸 frame number 뒤에 기존의 displacement 값을 그대로 붙여주면 물리적 주소로 변환이 완료된다.

장점

프로세스가 늘어나도 page table을 추가로 생성할 필요가 없으므로 page table 관리에 들어가는 메모리 공간을 절약할 수 있다.

단점

특정 page가 어느 frame에 있는지 찾으려면 page table을 맨 처음부터 하나씩 전부 검색해야하므로, 주소를 매핑하는데 걸리는 시간이 길어질 수 있다.

Shared Pages

Paging에서 여러 프로세스가 동일한 코드나 데이터를 함께 사용할 수 있도록, 서로 다른 프로세스의 page table 항목이 물리 메모리의 동일한 frame을 가리키게 하는 기법니다.

공유 가능한 코드는 보통 read-only (reentrant) code 이며, shared code는 모든 프로세스의 logical address space에서 같은 위치에 나타나야 한다.

예를 들어 한글 프로그램 자체는 내용이 변하지 않는 읽기 전용 코드이므로 여러 프로세스 사이에서 공유될 수 있다. 이를 구현하기 위해 각 프로세스(P1,P2,P3)의 page table에서 해당 editor program에 해당하는 항목들이 모두 동일한 물리적 frame number(ex:3번,4번,6번 frame)를 가리키도록 동일하게 설정한다. 이렇게 하면 세 프로세스가 물리적 메모리 어딘가에 단 하나만 깔려있는 editor program을 똑같이 참조해 공유할 수 있다.

Segmentation

Segmentation은 메모리를 고정된 크기(page)로 자르는 paging과 달리, 사용자의 관점을 반영해 논리적인 단위(segment)로 나눠 메모리에 할당하는 방식이다.

각 segment는 그 역할에 따라 크기가 다를 수 있으며, 하나의 segment 안에서는 물리적 메모리 공간을 연속적으로 통째로 할당받지만, 한 프로그램을 이루는 여러 segment들은 메모리 상에서 서로 뿔뿔이 흩어져서 위치할 수 있다.

즉 앞서 학습한 contiguous allocation과 같은 방식으로 할당된다.

Paging      : 운영체제 관점, 고정 크기
Segmentation: 사용자 관점, 논리적 단위

주소 구조와 변환

Segmentation 시스템에서 CPU가 생성하는 논리 주소는 다음 두 가지 정보로 구성된다.

s(segment number): 접근하고자 하는 segment의 번호(index)
d(offset): 해당 segment 내부에서 데이터가 위치한 상대적인 거리

Segment table의 각 항목은 page table과 달리 아래 두 가지 정보를 가진다.

Base : segment가 물리 메모리에서 시작하는 주소
Limit : segment 길이

segment table이 메모리 어디에 있는지를 먼저 알아야하는데, 이때 아래의 두 레지스터를 통해 알 수 있다.

STBR (Segment-Table Base Register) : segment table 시작 위치
STLR (Segment-Table Length Register) : segment 개수
메모리 접근 요청이 발생하면 가장 먼저 주소 안의 segment number를 확인한다. 이 번호가 프로세스의 전체 segment 개수 정보가 담긴 STLR의 값보다 크다면 잘못된 접근이므로 오류가 발생한다.
STBR가 가리키는 segment table의 위치로 찾아가, segment 번호에 해당하는 항목을 뒤진다.
table에서 가져온 Limit 값과 논리주소의 displacement를 비교해 만약 displacement값이 limit보다 크다면 해당 segment의 범위를 벗어난 것이므로 에러가 발생한다.
범위를 벗어나지 않는 정상적인 접근이라면, table에 적힌 base값에 displacement 값을 더해 최종 물리주소를 완성한다.

특징

Relocation: segment table의 base 값만 수정하면 실행 중에도 segment의 위치를 이동시킬 수 있다.
Sharing & Protection: 의미가 있는 단위(segment)로 나뉘어있기 때문에, 특정 segment를 보호하거나 여러 프로세스 간에 segment 단위로 코드를 공유하기에 매우 적합하다.
Allocation: 빈 공간(hole)을 찾아 메모리를 할당할때 first-fit/best-fit 방식을 사용하게 되는데, segment들의 크기가 일정하지 않기 때문에 할당과 해제를 반복하다보면 물리 메모리 사이에 빈틈들이 생겨난다. 이때 전체 빈 공간을 합치면 요구량을 충족하지만 연속된 공간이 아니라 새 segment를 올리지 못하는 외부 단편화 문제가 발생한다.

Segmentation with Paging

논리적 보호 및 공유에 유리한 segmentation의 장점과 external fragmentation을 해결하는 paging의 장점을 모두 취하기 위해 두 방식을 결합한 기법이다. 대표적으로 MULTICS 시스템에서 사용된다.

순수 segmentation 방식에서는 segment table의 base가 물리 메모리의 시작 주소를 가리켰으나, 이 방식에서는 segment가 page로 쪼개져있기 때문에, segment table의 base는 해당 segment를 관리하기 위한 page table의 시작주소를 가리킨다.

사용자(외부) 관점: 프로세스를 segment 단위로 분할해 바라보며, 각 segment는 메모리 상에서 연속 공간을 할당받은 것처럼 보인다.
물리 메모리(내부) 관점: 실제 물리 메모리에 할당할때는 크기가 제각각인 segment들을 그대로 올리지 않고, 해당 segment를 다시 고정된 크기의 page 단위로 잘게 쪼개 메모리의 여러 빈 frame에 흩어져 분산 저장한다.

주소 변환 과정

CPU가 던진 segment number s를 이용해 segment table을 찾아간다. 이때 offset d가 해당 segment의 전체길이(limit)보다 작은지 검사해 허용된 범위를 벗어나면 에러를 발생시켜 프로그램을 종료한다.
범위를 벗어나지 않아 안전하다면, 하드웨어는 offset d를 다시 쪼개 page number p와 page 내의 offset d'으로 나눈다. 예를 들어 d가 7123이고 page size가 2KB라면, 7123 나누기 2048 을 계산해 page number p는 3, 나머지는 offset d'는 979가 된다.
segment table에 기록된 page table 시작 주소에 방금 구한 page number p를 결합해 해당 segment 전용의 page table을 찾는다.
page table에서 실제 물리 메모리의 frame number f를 획득하고, 그 뒤에 아까 쪼개둔 page 내 offset d'를 이어 붙여 최종 물리 주소를 완성한다.

김민성

JUST DO IT

이전 포스트