virtual memory 사용 시 page fault로 발생하는 성능 이슈에 대한 해결법을 다루는 파트다.
Virtual memory 관리 기법
page fault frequency, page fault rate를 줄이는 것이 목표다
- Page reference string (ω)
프로세스가 접근한 페이지 번호들이다.ω= r1r2...ri...rt- Page fault rate
F(ω)= (ω 중 page fault 수) / | ω |
Hardware components(mmu)
-
Address translation device : address mapping을 효과적으로 해주는 장치로 성능보단 기능적 완성을 위한 장치다.
-
Bit vectors
-
reference bit vector: 해당 페이지 프레임이 참조됐는지 표시 (0 or 1) 한다. 주기적으로 0으로 reset하기 때문에 최근에 접근됐는지만 확인할 수 있따.
-
update bit vector: page frame의 content가 변경됐을 때 표시한다. update된 상태에서 disk에write-back이 된 후엔 다시 0으로 저장한다.
-
Software components
아래 6가지 strategies 중에 allocation, replacement 기법이 시스템에 영향을 많이준다.
1. Allocation strategies (how much?)
각 프로세스별로 page frame을 얼마나 할당해줄지 정하는 기법이다.
- Fixed allocation : 처음부터 고정된 양을 할당해주는 방법
- Variable allocation : 가변할당 방법
한 프로세스에게 page frame을 너무 많이 할당하면 memory waste, 너무 적게 할당하면 page fault rate가 올라가기 때문에 적절히 할당해줘야한다.
2. Fetch strategies (when?)
프로세스의 page들을 언제 메모리에 로딩할지 정하는 기법이다.
- Demand fetch : process에 의해 접근된 page만 fetch한다 (on-demand).
대부분의 시스템이 이 기법을 사용하기 때문에 앞 장에서 paging기법을 부를때도 demand paging이라고 했던 것이였다. - Anticipatory fetch (pre-fetch) : 접근될거같은 page를 예측해서 fetch한다. 하지만 예측을 하기 위해 메모리관리를 또 해야하는 역설이있다.
3. Placement strategies (where?)
메모리로 들어오는 page를 어디에 배치시킬지 정하는 기법이다.
paging system의 경우 주기억장치도 page 크기에 맞춰 page frame단위로 미리 고정 분할되기 떄문에 필요없다.
segmentation system의 경우 first-fit, best-fit, worst-fit, next-fit 기법 중 선택해 사용한다.
4. Replacement strategies (who?)
꽉차있는 메모리에 page가 들어와야할 때 어느 page를 내보낼지 정하는 기법이다.
- Fixed allocation based 교체 기법
- MIN(OPT, B0) algorithm
- Random algorithm
- FIFO(First In First out) algorithm
- LRU(Least Recently Used) algorithm
- Additional reference-bits algorithm
- LFU(Least Frequently Used) algorithm
- NUR(Not Used Recently) algorithm
- Clock algorithm
- Enhanced clock algorithm
- Variable allocation based 교체 기법
- VMIN(Variable MIN) algorithm
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
이 기법들에 대해서는 밑에서 자세하게 다룬다
5. Cleaning strategies (when?)
Update된 page를 언제 write-back할지 결정하는 기법.
- Demand cleaning : 해당 page가 메모리에서 쫓겨날 때
- Anticipatory cleaning(pre-cleaning) : 더이상 update되지 않을거같은 page를 예측해서 write-back
6. Load control strategies (how many?)
system의 multiprogramming degree(얼마나 많은 프로세스들에게 메모리를 할당할까)를 결정하는 기법이다.
많은 프로세스에게 메모리를 할당하면 각 프로세스당 할당받는 메모리의 크기는 줄어들기 떄문에 1번 allocation strategy와 연관되어있는 기법이다.
multiprogramming degree를 올리면 throughput(처리량)이 계속 좋아질거같지만 너무 커지면 오히려 성능이 떨어지기 때문에 적절하게 degree를 결정해주는 것이 load control strategies가 하는 일이다.
그렇다면 왜 overloaded됐을 떄 성능이 떨어질까? 너무 많은 프로그램이 할당되면 한 프로그램당 allocation 크기가 줄어들 수 밖에 없고, 이 소리는 memory에 로드되는 프로그램의 page의 양이 적다는 의미이다. 그렇기 때문에 자연스럽게 page faults가 많이 발생해 성능이 떨어진다. 이런 현상을 thrashing이라고 한다.
Locality
모든 프로세스는 program이나 data를 참조할 때 일부 영역에 국한되어 집중/반복 접근한다는 개념이다.
주로 프로그램이 가지고 있는 배열이나, Loop structure때문에 발생한다.
-
Temporal locality : 최근 접근한 부분을 시간이 지나면 다시 접근
-
Spatial locality : 접근한 지역과 가까운 부분을 접근
이런 locality의 특성을 잘 알고있어야 page fault를 최소화하기 위한 기법들을 만들 수 있다. 아래 예시를 보면 이해가 잘된다.
- Data reference
배열을 접근할때 메모리상에서 하나씩 접근 -> spatial locality
sum 변수를 for문마다 접근 -> temporal locality - Instruction reference
loop안의 코드를 차례차례 수행 -> spatial locality
이 loop를 반복적으로 수행 -> temporal locality
