메모리 주소 변환과 달리 Virtual Memory 는 OS 가 주도적으로 처리.
Demand Paging
- 현대의 OS 는 페이징 기법을 사용한다.
- 실제로 필요할 때 페이지를 메모리에 올림
- I/O 양 감소 : 대부분의 경우에 사용 안되는 코드가 많음. 필요한 것만 메모리에 올리게
- Memory 사용량 감소
- 빠른 응답 시간 : 더 많은 프로그램이 메모리에 올라감. disk I/O 가 줄어들고 메모리에서 직접 서비스 하는 비율이 높아짐.
- 더 많은 사용자 수용
- Valid / Invalid Bit
- Invalid
- 사용되지 않는 주소 영역 (G, H)
- 페이지가 물리적 메모리에 없음. (B, D, E)
- 처음에는 모든 page entry 가 invalid
- 주소 변환 시 invalid bit 이 set 되어있으면
- disk 에서 메모리로 페이지를 올리는건 사용자 프로세스가 할 수 없음.
- page fault => trap => CPU가 OS 에 넘어감.
Page Fault
를 어떻게 처리할지가 OS 에 명시되어 있음.
- Invalid Page 접근 -> MMU 가 trap 발생 시킴. -> CPU Kernel mode -> invoke page fault handler
- Invalid reference (ex. 주소 잘못됨, 접근 권한 없음) => abort process
- 빈 page frame 을 가져온다. (없으면 뺏어옴. replace)
- 해당 페이지를 disk 에서 메모리로 읽어온다. (I/O)
- disk I/O 가 끝나기 전까지 이 프로세스는 CPU 를 preempt 선점 당함. (block)
- disk read 가 끝나면 page tables entry 에 기록하고, valid/invalid bit : valid
- ready queue 에 process insert -> dispatch later
- 이 프로세스가 CPU 를 잡고 다시 running
- 아까 중단된 instruction 재개.
Performance
- Page Fault => disk 접근 => 시간이 오래 걸림.
- Page Fault 가 나는 비율에 따라 성능이 결정됨.
- Page Fault Rate 0 <= p <= 1
- if p == 0: page fault 없음
- p == 1: 모든 참조가 전부 page fault
- 실제 시스템에서는 p 가 매우 작음 0.0x 정도
- Effective Access Time
= (1 - p) memory access +
p (OS & HW Page Fault overhead
+ [Swap page out if needed]
+ swap page in
+ OS & HW restart overhead)
Page Replacement
(쫓겨나는 걸 결정하는 시간과 실제로 쫓아낼 시간 사이에 변경된 것이 있다면)
- Free Frame 이 없는 경우
- 어떤 frame 을 빼앗아 올지 결정해야함.
- 곧바로 사용되지 않을 페이지를 쫓아내는 것이 좋음. (많이 사용되는건 계속 메모리에 있는게 좋음)
- 동일한 페이지가 여러 번 메모리에서 쫓겨나고 들어오고 할 수 있음.
- Replacement Algorithm
- page fault rate 을 최소화하기 위한 알고리즘
- 주어진 page reference string 에 대해 page fault 를 얼마나 내는지 조사해서 평가
- ex) 1 2 3 4 1 2 5 1 2 3 4 5
(Offline) Optimal Algorithm
가장 좋은 알고리즘. page fault 가 가장 적음.
- 가장 먼 미래에 참조되는 page 를 쫓아낸다.
- 성능 평가 참고용
여기부터는 미래를 몰라도 사용 가능.
FIFO
First-In-First-Out
- FIFO Anomaly : 메모리가 더 크다고 성능이 더 좋아지는(페이지 폴트가 적어지는) 것은 아님
LRU
Least Recently Used : 가장 오래 전에 참조된 것을 지운다.
메모리 관리에 가장 많이 사용됨.
LFU
Least Frequently Used : 참조 횟수가 가장 적은 페이지를 지움
- 참조 횟수가 가장 적은게 여러개라면?
- 임의 선정.
- 그 중 가장 오래전에 참고된 (LRU) 페이지를 지우게 구현도 가능.
- 직전 참조 시점만 보는게 아니라 장기적으로 보기 때문에 page 의 인기도를 비교적 정확하게 반영.
- 하지만 참조 시점의 최근성을 반영하지 못함.
- LRU 보다 구현이 복잡.
LRU vs LFU
- LRU 는 옛날에 많은 참조가 있었던 걸 고려하지 못함.
- LFU 는 앞으로 더 많이 사용될 가능성을 고려하지 못함.
구현
LRU : 참조된 시간 순서대로 줄세워서 관리
- 새로 들어오면 가장 최근 참조니까 맨 밑으로 보내고,
- 가장 오래된 맨 위에 있는 것을 쫓아내면 됨.
- 빠르게 결정해야하기 때문에 비교를 적게 해야함. O(1) good
LFU : 줄세우기 불가능.
- 새로 들어왔다고 해서 바로 맨 밑으로 가는게 아니라 전체 참조 횟수 + 1 해서 참조 횟수를 계속계속 비교해서 어디에 줄 세울지 결정해야함.
- 최악의 경우 O(n) bad.
- heap 을 이용해서 구현 O(log n)
- root 를 쫓아내고 힙 재구성 upheap O(log n)
- 새로 들어오면 downheap O(log n)
Caching
- 어떤걸 쫓아낼지 결정하는 것이 Virtual Memory 에서만 일어나는 것이 아니라
- 컴퓨터 시스템 여러군데에서 일어나는데 그 중 한가지가 캐싱
- 한정된 빠른 공간(=캐시)에 데이터를 저장해두고 다음 요청이 들어오면 캐시에서 바로 서비스
- ex
- paging system : disk (swap area) 로 가는 요청을 빠르게 처리.
- cache memory : CPU 와 main memory 사이에 존재.
- buffer caching : disk (file system) 로 가는 read/write 요청을 메모리에서 빠르게 처리.
- web caching : 웹페이지를 컴퓨터에 저장해뒀다가 읽어오게.
저장 장치 사이 속도 차이 때문이 아니라 멀리 있는 컴퓨터에서 읽어오는 것 때문 (정보가 바뀌면 다시 받아옴) - ...
시간 제약
- Buffer Caching, Web Caching
- O(1), O(log n) 까지 허용 가능.
- Paging System
- page fault 인 경우에만 OS 가 관여하기 때문에 (메모리에 있는거 읽어가는건 HW 가 함)
- 페이지가 이미 메모리에 올라와 있으면 참조 시각 같은 정보를 OS 가 알 수 없음.
- 메모리에 있는게 다시 참조되면 OS 가 LRU 의 리스트를 조작할 수도 없음.
사실 LRU LFU 는 paging system 에서 사용할 수가 없음...
buffer caching, web caching 에서는 사용 가능.
그래서 사용하는 알고리즘.
Clock Algorithm
- LRU 의 근사 알고리즘
- NRU (Not Recently Used), NUR, Second chance algorithm 등으로 불림.
- page 를 참고하면 page 의 reference bit 를 MMU 가 체크하는 것을 이용.
- reference bit = 1 이면 최근에 참조됨.
- 환형 리스트에서 한바퀴 돌면서
- reference bit = 1 이면 0으로 바꾸고
- 0 이면 쫓아냄.
- 자주 사용되면 다시 돌아왔을 때 1 이니까 안쫓겨난다.
개선
- Reference bit 으로는 read or write 어떤 참조인지 모르므로,
- modified bit (dirty bit) = 1 (최근에 변경된 페이지 == I/O 동반) 을 추가해서 write 참조도 대응.
- 1 이면 내용 수정이 있으므로, backing store 에 내용 저장 후 쫓아내고
- 0 이면 그냥 쫓아내도록 사용한다.
Page Frame 의 Allocation
- 메모리에는 여러 프로세스의 페이지가 같이 올라와있는데,
- 앞의 알고리즘들은 어떤 프로세스의 페이지인지 신경 안쓰고 쫓아냈다.
- but..... 한 프로세스 내에서 여러개가 같이 올라와 있어야 page fault 가 덜 나는 일련의 페이지들이 존재.
- ex) loop
- ex2) 메모리 참조 명령어 수행을 위해 명령어나 데이터 등 여러 페이지를 동시에 참조하므로 최소한 할당되어야 하는 Frame 수
방법
- equal allocation : 모든 프로세스에 같은 개수의 페이지 할당
- proportional allocation : 프로세스 크기에 비례하여 할당
- priority allocation : CPU 우선순위에 따라 다르게 할당.
- -> Local Replacement
이걸 고려하지 않아도 LRU LFU 같은 replace algorithm 을 쓰다보면 알아서 어느정도 할당되긴 함. -> Global Replacement
Global & Local Replacement
Global Replacement
- Replace 시 다른 프로세스에 할당된 frame 을 가져오면서 프로세스 별 할당량 조절이 되긴 함.
- FIFO, LRU, LFU, ... 을 global replacement 로 사용하면 가능.
- Working Set, PFF 알고리즘 사용
Local Replacement
각 프로그램에 메모리 할당을 따로 한다면.
- 자신에게 할당된 frame 내에서만 replacement
- 프로세스별로 FIFO, LRU, LFU, ... 알고리즘 운영
Thrashing
- 프로세스의 원활한 수행을 위해 필요한 최소 page frame 수를 할당 받지 못한 경우에 발생한다.
- page fault ⏫
- CPU utilization ⏬
- OS 는 MPD (MultiProgramming Degree) 를 높여야한다고 판단..
- 또 다른 프로세스가 시스템에 추가
- 프로세스 당 할당된 Frame 수가 더욱 감소
- 어떤 프로세스가 CPU 를 잡더라도 거의 page fault
- 프로세스는 page 의 swap in / out 으로 바쁜데
- CPU 는 놀고있음...
- throughput ⏬
- 동시에 메모리에 올라간 프로그램 개수를 조절해서 MPD 를 낮춰야함.
-> Working Set, PFF
Working-Set Algorithm
Locality of reference
- 프로세스는 특정 시간동안 일정 장소를 집중적으로 참조.
- 집중적으로 참조되는 페이지 집합 -> locality set
Working Set Model
- Working Set : Locality 기반으로 프로세스가 원활하게 수행되기 위해 한번에 메모리에 올라와 있어야하는 페이지 집합
- 프로세스의 Working Set 전체가 메모리에 올라와야 수행되고, 일부만 올라오면 모든 frame 을 반납하고 swap out (suspend)
- Trashing 방지
- MPD 조절
Algorithm
- 프로세스들의 working set size > page frame 수
- 일부 프로세스를 swap out 시켜서 남은 프로세스의 working set 을 우선 충족. (MPD ⏬)
- Working Set 을 다 할당하고 page frame 이 남으면
- swap out 되었떤 프로세스에게 working set 을 할당 (MPD ⏫)
Working Set 의 결정
Working Set 은 어떻게 알지? -> 예측
- Working Set Window
- 특정 시간 간격 사이의 Working Set 을 계산.
- 특정 시간만 유지하고 버림. (다시 참조되면 시간 유예)
- Window Size
- 너무 작으면 locality set 을 전부 수용하지 못할 수 있음. (page fault 늘어남)
- 너무 크면 여러 규모의 locality set 을 수용
- 무한대면.. 전체 프로그램을 구성하는 페이지를 working set 으로 간주.
PFF (Page-Fault Frequency)
- page fault 를 많이 일으키는 프로그램에 page 를 더 준다.
Page Size의 결정
Page Size (보통 4K) 가 작아지면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- Internal Fragmentation 의 감소
- page 안에서 사용 안하는 부분이 줄어든다. (원래 올라가던게 크기가 줄어서 안올라가니까)
- Disk Transfer 효율성 감소
- seek / rotation >> transfer
- seek 시간이 오래 걸리기 때문에 디스크에서 읽어올 때는 한번에 이동해서 많이 읽는게 좋음. == page size 가 큰 것이 좋음.
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적.
- locality 활용 측면에선 별로..
최근에는 메모리 용량이 커지면서 page frame size 도 커지고 있다.
출처 / 참고
반효경 교수님의 2014 운영체제 9. Virtual Memory 2 강의를 듣고 포스팅하고,
공룡책을 읽고 추가 정리합니다.
사진 출처는 강의 자료.
0년차 iOS 개발자입니다.