새로운 abstraction을 만들었다. → safety, convenience, efficiency
메모리에 대한 보호는 MMU라는 CPU 하드웨어에서 함
Goal
1.
Protection
a.
프로세스를 다른 것으로부터 막음
b.
isolation, 때로는 공유할 수 있게 함.
2.
Transparency
a.
메모리가 공유되고 있다는 사실을 몰라야한다. 연속 메모리 공간으로 인식 시킴
3.
Efficiency
a.
variable-sized request 덕분에 단편화를 최소로 줄임
b.
h/w support를 가짐
주소 공간
•
주소 해석은 런타임에 일어난다.
•
lazy allocation을 지원함. 물리 주소는 동적으로 배치되거나 on demand로 릴리즈 됨.
VM API
1.
malloc, calloc, free, realloc
2.
brk, sbrk
a.
heap size 변경
3.
mmap
a.
가상 주소랑 실제 주소를 매핑하는 거
i.
addr: 새롭게 할당하려는 주소. NULL이면 커널이 알아서 정함
ii.
length: mapping size
iii.
prot: 보호 정보
iv.
flags: (MAP_PRIVATE, MAP_SHARED, MAP_ANONYMOUS)
v.
fd, offset: file descriptor, file offset
b.
Shared vs Private mapping
i.
Shared: 수정이 관련된 프로세스에게 다 보인다.
ii.
Private: 안 보인데, but Copy-on-Write 전략 사용ㅎ마.
Backing Store
•
File
◦
일반 파일이 backing store, 파일 영역이랑 메모리 영역을 일치시키는 것
◦
파일의 내용이 읽거나 써진다, load, store 명령으로
•
Device Memory
•
Shared Memory
•
Anonymous Mapping
◦
파일로 백업이 안 되는 것들. 9으로 일단 채운다. Zero-page swaaping
Address Translation
Static Relocation
•
OS는 각 프로그램을 메모리에 로딩하기 전에 다시 쓴다.
•
서로 간의 privacy 보호 되지 않음. 다른 영역에 써버릴 수도 있음
•
한 번 place되면 움직일 수가 없다.
Dynamic Relocation
•
MMU가 주소 해석을 수행함.
•
hw에서 Protection이 수행됨. 가상 주소가 invalid하면 exception을 발생 시킴
•
OS는 valid address space에 대한 정보를 MMU에게 넘겨줌
•
구현 종류
◦
Base and Bound
◦
segmentation
◦
pagin
•
디자인 고려 점
◦
memory protection을 어떻게 할까
◦
구현이 쉽냐?
◦
fragmentation
▪
internal fragmentation, external fragmentation
◦
on-demand allocation이 되느냐
•
Fixed Partition
◦
이러면 Internal fragmentation 많이 발생함
Base and Bound
•
bound register가 protection의 역할
•
less internal fragmentation
◦
그래도 여전히 free space가 있을 수 있음
•
각 프로세스는 물리 메모리에 연속적으로 할당되어야함
•
external fragmentation
◦
홀들이 분산될 수 있음
◦
컴팩션을 해야함
•
No partial sharing: sharing 같은 거 없다.
•
프로세스가 시작할 때, 적절한 주소를 찾아야하고, 프로세스가 종료될 때, reclaiming 해야하고, 컨텍스트 스위치가 발생하면 그걸 다 레지스터에 저장해야한다.
Segmentation
•
로지컬한 부분으로 주소공간을 나눈다
◦
code, data, stack heap
•
각 세그먼트는 독립적으로 관리됨.
◦
줄었다, 늘었다가 가능, 보호도 된다
•
코드 영역은 sharing이 가능하다.
•
sparse allocation이 가능하다
•
valid bit를 통한 protection이 쉽다.
•
different protection bits를 통해서 다른 세그먼트에 대한 protection이 된다
•
dynamic relocation을 지원
•
base and bound보다 공유가 쉽다.
•
세그먼트 자체는 연속적으로 할당 되어야한다.
◦
external fragmentation
•
세그먼트 테이블이 크다.
◦
메인 메모리를 차지한다.
•
internal fragmentation이 있을 수 있음
◦
heap에 대해서 free를 하면 발생함
◦
이런 것들은 compaction으로 해결
Paging
•
메모리 공간을 page라고 하는 고정 사이즈로 자르는 것이다.
•
엄청 많은 페이지로 잘림
•
페이지 테이블이 해석을 위해서 각 프로세스별로 하나 필요하다
•
Virtual address: 32bits
•
physical address: 20bits
•
page size: 4KB
•
4 bytes per PTE
→ offset: 12 bits
→ VPN: 20bits
total number of PTEs: 2^20
page table size: 2^20 * 4 = 2^22 = 4MB
•
이 페이지 테이블은 엄청 커질 수 있다. 이걸 줄이는 과정도 배워볼 예정.어쨌든 물리 메모리 안에 있음
•
컨텍스틑 스위치가 발생하면 현재 페이지 테이블의 베이스 주소를 가리킨다.
•
valid, invalid 비트가 있음
◦
valid는 현재 사용 중이라는 듯, invalid: 할당이 안 되었다는 뜻
•
디맨드 페이징
◦
필요할 때만 들고 오는 것임
◦
물리 메모리에서 evict 될 수도 있음
◦
evict이 되면 disk로 감
◦
없는 경우에 page fault가 발생함
▪
major
•
valid한데 메모리에 로드가 되지 않았다
•
OS는 컨텐츠를 찾는 데 필요한 정보를 유지함
•
disk I/O 발생
▪
minor
•
페이지 폴트는 disk I/O 없이 해결됨
•
lazy allocation
•
prefetched page에 접근하기
◦
external fragmentation이 없다.
◦
allocate, free가 빠르다
◦
protect, share가 쉽다.
◦
internal fragmentation이 생길 수 있음
◦
memory를 레퍼런스 해야하는게 오버헤드가 있을 수 있음
▪
TLB라는 캐시를 CPU가 내장함.
◦
페이지 테이블을 위한 스토리지가 필요
mmap API
◦
그냥 open, read를 하면 user 커널 버퍼에 옮기는 비용이 듬
◦
clibrary fopen, fget를 쓰면 중간에 clibrary 내의 메모리에 복사 후에 버퍼로 옮김
◦
mmap을 쓰면 그냥 커널 주소 공간을 바로 매핑해버림
Copy on Write
•
메모리 카피를 미루는 것
•
PRIVATE 영역이면 WRITE가 들어왔을 때, page fault를 발생 시키고, 새로운 영역을 가리키고 거기에 쓰도록 함
•
일단 더 적은 메모리 카피가 일어남
•
파이프, 소켓 등과 같은 streamed I/O에는 generalized 되지 않는다.
Shared Memory
•
페이지 테이블은 각 프로세스에 있는데, 각 PTE는 같은 공간을 가르킨다. 각 PTE는 개별적인 protection bit가 있음.
•
하나가 무효화되면 다른 것들도 무효화가 되어야한다.
Advanced Page Table
•
기본적으로 관찰을 해보면 많은 page table이 사용되지 않는다. 엄청 많은 invalid entry가 많음.
Paging and Segments
•
일단 Segment로 나눔. Segment는 variable length를 가짐
•
각 세그먼트는 페이징으로 나눠짐.
•
각 세그먼트는 페이지 테이블이 있음
•
각 세그먼트는 페이지 테이블의 시작이랑 끝을 알고 있음
•
page 테이블에 쓰이는 메모리 사용량을 줄일 수 있음
•
세그먼트들은 reshuffling 없이 자란다
•
각 싱글 페이지나 전체 세그먼트에 대해서 page table을 공유할 수 있음
•
다만 페이지 테이블이 커질 가능성이 있음
•
외부 단편화가 페이지 테이블 때문에 있을 수 있음
◦
각 페이지 테이블이 연속적으로 배치되어있음
Multi-Level page table
linear page table을 트리로 바꾸자
•
페이지 테이블을 페이지 사이즈만큼씩 자르자
•
페이지 테이블 내 전체 페이지가 invalid 하면, 페이지 테이블의 페이지를 더 할당하지 마라
•
page directory라는 걸 이용해서 페이지 테이블의 페이지가 valid한지 판단하자
Multi Level paging Table
•
확실히 컴팩트 해진다
•
physical memory를 관리하기 쉽다
•
external fragmentation이 없다
•
address translation에서 메모리 접근이 많아진다.
•
좀 더 복잡한 하드웨어가 필요함
TLB
매 접근마다 아래를 해야한다.
•
Extract VPN from VA
•
Calculate the address of PTE
•
Read the PTE from memory
•
Extract PFN from PTE
•
Build PA
•
Read contents of PA from memory into register
이 과정에서 Read the PTE from memory, Read Contents of PA from memory into register가 느림. 메모리를 2번 갔다온다.
칩의 MMU의 일부이다.
virtual to physical address translation의 캐시임
•
각 엔트리가 어느 프로세스에 속한 건지 확인한다. ASID(Address Space ID)
•
컨텍스트 스위치 시 TLB를 처리해야한다.
◦
다른 프로세스로 전환되면 기존 주소는 유효하지 않기 때문에
◦
Page Table base Register가 바뀌고 TLB가 자동으로 비워진다.
◦
공유 커널 페이지와 같이 공유하는 경우는 제거하지 않도록 설정할 수 있음
•
Miss가 난다면?
◦
MMU는 페이지 테이블에서 PTE를 로드해온다. (HW 기반)
◦
OS에게 Trap을 보내고, OS가 살펴본다음 TLb에 로드한다. (SW 기반)
TLB on Multi-core
•
Coherence
◦
다른 코어에 있는 것도 비워줘야한다
◦
TLB shootdown
▪
IPI(inter-processor interrupt)를 보낸다.
▪
remote core가 그 TLB를 invalidate 시킨다
Swapping
•
Swap space
◦
페이지를 넣었다가 다시 놓았다가 하는 공간이 예약되어있다.
◦
swap space는 사용하고 있는 메모리의 최대량에 따라 다르다
◦
Block size는 페이지 사이즈랑 같다
Page replacement
•
어떻게 evict 하느냐는 타입에 따라 다르다
•
code
◦
메모리에서 그냥 없앤다.
•
data
◦
수정된 친구들은 swapped을 하고
◦
unmodified 친구들은 그냥 drop
•
unmodified anonymous page
◦
이전에 swapp이 된 적 있는 친구면 그냥 지워버림
◦
한 번도 disk로 간적이 없는 친구면 새로 하나를 만든다
•
modified(dirty) anonymous page
◦
저번에 swap한 친구이면 그 공간에 쓴다
◦
한 번도 없으면 할당 후 쓰기
•
언제 하냐
◦
Lazy
▪
메모리가 다 찰 때까지 기다리고, 스왑하기 시작. 이건 현실적이지 ㅇ낳음
◦
threshold 기반
▪
항상 free memory portion을 유지하고 싶어함.
▪
HW/LW가 있음
▪
swap daemon이 이걸 조절하는 걸 책임지고 있음
▪
LW보다 작으면 evict을 시작, HW 보다 많으면 잠에 든다
Policy
•
미래에 가장 안 쓸 걸 같은 걸 replace 하는게 최선이다
•
FIFO
◦
먼저 들어온거부터 나감
▪
제일 들어온지 오래 된게 많이 안 쓰일 때는 좋다
▪
어떤 페이지들은 항상 필요할 수 있는데, 이건 안 좋다.
◦
Belady’s anomaly에 고통받음
▪
캐시를 늘려도 오히려 page fault가 더 많이 발생함
•
이건 캐시가 늘어남에 따라서, 필요 없는건 오래 남아서 유용한 페이지가 빨리 제거되기 때문
▪
메모리에 있는 것보다 많은 걸 순차적으로 요구하면 Miss가 많이 남
•
Random
◦
LRU
▪
history를 사용함
▪
가장 안 쓴걸 지운다.
•
랜덤 엑세스에서는 그냥 세 개가 다 꾸준히 오른다
•
80프로의 접근이 20프로의 페이지에 집중된다.
•
이런 경우 지역성을 가장 잘 살리는 건 LRU이다.
•
순차적으로 돌아가는 거에는 LRU, FIFO가 같고, 0으로 박는다.
•
왜냐면 캐시 사이즈가 요구되는 메모리 범위보다 작으면, 계속 미스가 나게 되어있다.
다른 방법으로 Clock algorithm이라는 것도 있는데, 이건 LRU를 근사한다.
•
use bit를 사용한다.
•
page가 reference 되면, use bit가 1로 세팅된다.
•
모든 페이지가 circular list에 있다
•
시계는 특정 페이지에서 시작함
•
만약 1이면 끄고 넘어가고 0이면 그걸 evict 함.
•
원래는 LRU 리스트를 유지하는데, 그게 아니라 순차적으로 돌아가면서 찾는 것이다.
Prefetching
•
쓰일 거 같으면 한 번에 다 들고 오는 거다
Clustering, Grouping
•
write pending인 페이지들을 모아서 디스크에 한 번에 다 쓰는거다
•
single large write를 하는게, 여러 번 작은 거 하는 거보다 낫다
Thrashing
•
메모리가 working set을 담기에 작아서, 계속 데이터를 디스크에 왔다갔다 시키는 걸 의미함
•
working set을 줄이거나 processes의 subset을 줄인다.
