메모리 불연속 할당 (Paging, Segmentation)

불연속 할당(Noncontiguous Allocation)

프로그램의 주소 공간을 작게 쪼개어 사용자 프로세스 영역의 여러 부분에 분산하여 할당하는 방식

하나의 프로세스가 메모리의 여러 영역에 분산되어 적재된다.
Paging, Segmentation, Paged Segmentation이 있다.

Paging 기법

프로그램의 가상 주소 공간을 page라는 단위로 쪼개는 기법

page단위로 프로그램의 일부를 메모리에 적재하거나(swap in), backing store에 swap out한다.
프로그램에 할당된 물리 메모리를 page와 동일한 크기의 page frame 단위로 쪼갠다
운영체제는 메모리를 효율적으로 사용하기 위해 empty page frame을 관리한다
Page Table을 통해 page 단위의 주소변환이 이뤄진다

장단점

장점 : 외부 조각이 발생하지 않기 때문에 Dynamic Storage-Allocation Problem 문제가 없다
단점 : page단위로 쪼개다보면 마지막 조각이 page 크기보다 작을 수 있기 때문에 내부 조각이 발생할 수 있다

📌 `Paging 기법의 주소 변환`

논리적 주소를 페이지 번호(p), 페이지 오프셋(d) 으로 구성한다

pageTable[페이지 번호(p)] = 프로세스의 p번째 페이지가 존재하는 메모리의 시작 위치 (f)
f(시작점) + d(변위) = CPU가 접근한 논리적 주소에 대응되는 물리적 주소

Page Table

그리고 page table을 통해 물리적 주소로 주소 변환이 이뤄진다.

page table은 페이징 기법에서 주소 변환에 사용되는 자료구조이다
page table는 프로세스의 page 개수만큼의 entry를 가진다
각 entry에는 해당 page가 적재된 page frame 번호가 들어있다
page table은 메인 메모리에 저장된다.

MMU → PTBR, PTLR

CPU는 특정 프로세스의 page table에 접근하기 위해서 MMU의 2개의 레지스터(PTBR, PTLR)에 접근한다.

PTBR(Page Table Base Register) = 메모리에 존재하는 특정 프로세스의 page table 시작 주소 (base register)
PTLR(Page Table Limit Register) = 특정 프로세스의 크기 (limit register)

TLB(Translation Look-aside Buffer)

MMU 로 주소 변환을 하면 2번의 Memory Access가 필요하기 때문에 오버헤드가 크다. 따라서 속도 향상을 위해 TLB라는 고속 캐시를 사용한다.

TLB에 빈번히 참조되는 페이지에 대한 주소 변환 정보(page 번호-page frame 번호 쌍의 데이터)가 저장된다.
TLB에서 특정 페이지에 정보를 찾기 위해 full scan이 필요하다 → 병렬 탐색이 가능한 associative register를 사용한다.
page table과 마찬가지로 프로세스마다 독립된 TLB 정보를 가진다. (context switch가 일어나면 TLB에 저장된 정보가 모두 지워진다)

페이징 기법에서 주소 변환 과정

CPU가 “페이지 번호(p)-페이지 오프셋(d)"으로 구성된 논리적 주소에 접근
MMU(PTBR, PTLR)를 통해 page table에 접근
pageTable[page number(p)] = “page frame number(f : 페이지 프레임의 시작 위치)” 정보 참조
offset(d)과 f를 통해 실제 물리 메모리에 접근

📌 `계층적 페이징`

현대의 컴퓨터는 많은 주소 공간을 요구하는 프로그램을 지원한다. 그에 따라 page table의 entry수도 많아져 page table의 크기가 커지게 되었지만 대부분 프로그램은 일부만 사용되기 때문에 page table의 공간 낭비가 심하다.

→ 계층적 페이징 기법을 사용하여 page table로 인한 공간 낭비를 줄일 수 있다.

2단계 페이징 기법

주소 변환을 위해 외부 페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용한다.

사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블을 생성하지 않는다.
페이지 테이블을 위해 사용되는 메모리 공간을 줄이지만, 페이지 테이블의 수가 증가하므로 시간적인 손해가 뒤따른다.

계층적 페이징 기법의 단점

page table을 위해 사용되는 메모리 공간 소모를 줄일 수 있지만 메모리 접근 시간이 늘어난다

📌 `역 페이징`

모든 프로세스의 모든 페이지에 대한 페이지 테이블 항목을 구성해야 하기 때문에 page table로 인한 공간 낭비가 심하다

→ 역페이지 기법을 사용하여 page table로 인한 공간 낭비를 줄일 수 있다.

프로세스마다 page table을 생성하는게 아니라, 물리적 메모리에 대한 page table을 생성한다.

시스템 전체에 하나의 page table만 생성한다.
page table의 entry 개수는 page frame의 개수이다.
entry에는 “프로세스 번호(pid) - 프로세스의 논리적 페이지 번호(p)”가 담긴다.
논리적 주소를 pid, page 번호, offset 으로 구성한다

역 페이징 기법의 단점

주소 변환을 위해 page table 전체를 탐색해야 한다. (속도를 높이기 위해 associative register를 사용하여 병렬 탐색을 수행한다.)

Segmentation 기법

프로그램의 가상 주소 공간을 segment라는 의미 단위로 쪼개는 기법

프로그램의 code, data, stack을 code segment, data segment, stack segment로 쪼개어 메모리에 적재한다.
작게는 프로그램을 구성하는 함수 하나씩 segment로 정의하고, 크게는 프로그램 전체를 하나의 segment로 정의한다.
segment는 main 함수, function, global variables, stack, symbol table, arrays가 될 수 있다

장단점

장점 : 의미 단위로 주소 공간에 대한 접근을 제어하기 때문에 공유, 보안 측면에서 페이징 기법보다 효과적이다
- 프로세스끼리 동일한 코드(text segment)를 공유하기 용이하다
- memory section들 마다 서로 다른 read, write 권한을 설정할 수 있다
단점 : segment 길이가 각기 다르므로 외부 조각 문제가 발생한다.

📌 `Segmentation 기법의 주소 변환`

논리적 주소를 segment number(s), offset(d)로 구성한다.

segment number(s) = 프로세스 주소 공간 내에서 몇 번째 segment에 속하는지 나타낸다
offset(d) = 해당 segment의 시작 주소에서 얼마만큼 떨어져 있는지 나타낸다

Segment Table

주소 변환에 segment table을 활용한다. segment entry에 “base- limit”정보가 담긴다.

base = 물리 메모리에서 해당 segment의 시작 주소
limit = 해당 segment의 크기 (segment마다 크기가 다르기 때문에 필요하다)

MMU → STBR, STLR

CPU는 특정 프로세스의 segment table에 접근하기 위해서 MMU의 2개의 레지스터(STBR, STLR)에 접근한다.

STBR(Segment Table Base Register) = 메모리에 존재하는 특정 프로세스의 segment table 시작 주소 (base register)
STLR(Segment Table Length Register) = 특정 프로세스를 구성하는 segment의 개수 (limit register)

주소 변환시 점검사항

CPU가 접근한 논리 주소의 segment number (s)가 STLR보다 작은 값인지 확인
논리 주소의 offset(d)이 해당 segment의 limit보다 작은 값인지 확인

📌 `Segmentation 보호 기법`

각 segment 마다 protection bit를 둔다
- 이를 통해 해당 segment에 대한 읽기/쓰기/실행에 대한 제한을 설정할 수 있다.
각 segment 마다 valid bit를 둔다
- 해당 세그먼트가 현재 물리적 메모리에 적재되어 있는 지를 나타낸다. (paging도 마찬가지)

📌 `Segmentation 공유 기법`

여러 프로세스가 특정 segment를 공유하여 사용하는 개념이다.

공유되는 segment는 프로세스의 주소 공간에서 동일한 논리적 주소를 가져야 한다. (= 공유 segment는 각 프로세스에서 동일한 segment number를 가져야 한다)

📌 `Paging과 Segmentation 차이`

Paging	Segmentation
page table	segment table
page의 크기가 균일하기 때문에 offset의 크기가 page 크기에 의해 결정된다.	segment의 길이는 offset이 표현가능한 범위내에서 서로 다른 값을 가질 수 있다.
page table에서 page의 시작 주소 대신 page frame 번호로 주어진다. (page frame도 같은 크기로 나누어져 있기 때문)	segment table에서는 segment의 크기가 각기 다르기 때문에 segment의 시작 주소(base)가 주어진다.

Paging

Segmentation

page table

segment table

page의 크기가 균일하기 때문에 offset의 크기가 page 크기에 의해 결정된다.

segment의 길이는 offset이 표현가능한 범위내에서 서로 다른 값을 가질 수 있다.

page table에서 page의 시작 주소 대신 page frame 번호로 주어진다. (page frame도 같은 크기로 나누어져 있기 때문)

segment table에서는 segment의 크기가 각기 다르기 때문에 segment의 시작 주소(base)가 주어진다.

Paged Segmentation

프로그램의 주소 공간을 segment로 나누되, 각 segment마다 page로 나누는 기법

세그먼트의 크기를 page 크기의 배수가 되도록 한다 →segmentation의 외부 조각 문제를 해결
segment 단위로 접근 제어를 하여 보호한다 → paging 기법의 보안 약점 해소

📌 `Paged Segmentation 기법의 주소 변환`

외부의 segment table, 내부의 page table을 통해 주소 변환이 이뤄진다

segment table의 entry에는 “segment length -page table base(내부 페이지 테이블 시작 주소)" 정보가 들어있다.

CPU가 “segment number(s)-offset(d)"으로 구성된 논리적 주소에 접근
MMU(STBR, STLR)를 통해 segment table에 접근
segmentTable[segment number] = “segment length- page table base” 정보 참조
page table base로 segment 내의 page table에 접근
offset(d) 는 segment 내의 page number(p)와 해당 page 에서의 변위(d’)로 이루어져있다. → p와 d’를 통해 실제 물리 메모리에 접근