[OS][운영체제] 9. Virtual Memory / 가상 메모리

1. Background

2. Demand Paging

3. Page Replacement

---

Background

가상 메모리는 logical 메모리를 physical 메모리와 구분한다.

이는 다음과 같은 특징을 가진다.

• 실행에 필요한 일부 파트만 메모리로 가져와 실행
• 한정적인 physical 메모리 주소 공간과 별개로 더 큰 logical 주소 공간
• 주소공간을 공유함으로써 프로세스 생성이 효율적 (메모리 오버헤드 X)
• Demand paging 혹은 Demand segmentation 방식으로 구현된

[사진 1] virtual  메모리  -  매핑  - physical  메모리  - HW

Demand Paging

가상 메모리를 구현할 때 가장 중요한 기법이다.

특정 페이지가 필요할 때만 메모리로 가져와 실행한다.

이는 다음과 같은 장점이 있다.

• I/O 필요 적음
• 메모리 필요 적음
• 반응시간 빨라
• 더 많은 user 수용

페이지가 필요 -> 참조

-> invalid 참조면, abort한다.

-> 메모리에 없다면, 메모리로 올린다.

 

[사진  2]  페이지를  HW 와  Swapping 하며 큰 메모리를 사용하는 것처럼 사용한다 .

Page Table의 Valid-Invalid Bit

페이지에 접근할 때 메모리에 있는/없는지 표시해준다. (1: valid, 0: invalid)

초기에는 모든 entry가 0으로 설정된다.

 

[사진  3] valid-invalid bit

이 때, valid-invalid bit가 0이라면 Page Fault가 일어난다.

Page Fault

페이지 참조가 일어날 때 valid-invalid bit가 0(invalid)라면 OS로 trap한다.

이것이 Page Fault 현상이다.

과정은 다음과 같다.

 

[사진 4] Handling a Page Fault  과정

성능

Page Fault Rate = p일 때 EAT; Effective Access Time은 다음과 같다.

 

[사진 5] Demand Paging 의  EAT

예시 문제를 보자.

 

[사진 6] EAT  계산 예시

만약 free frame이 없다면?

-> Page replacement: 사용 않는 페이지를 swap out 한다.

이는 page faults를 최소화할 알고리즘으로 진행한다.

Page Replacement

Page Fault 났을 때 빈 공간이 없으면 victim 페이지를 swap out한다.

페이지가 변경된 적이 있으면 modify (dirty) bit을 사용하여, 나중에 swap out 시킬 필요가 없다고 결정할 수 있다.

기본 과정은 다음과 같다.

1. disk에서 원하는 페이지를 찾는다
2. frame이 비었으면 쓰고, 빈 frame이 없으면 replacement 알고리즘으로 victim frame을 선정
3. 거기에 새 page를 update한다
4. 프로세스 restart

[사진 8] Page Replacement

이제 각각의 알고리즘에 대해 알아보자.

1) FIFO

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 순으로 참조가 일어날 때,

3 frame 혹은 4 frame인 경우 page fault는 다음과 같다.

 

[사진 9] FIFO  알고리즘

보통 frame이 많을수록 page fault는 적게 일어난다.

하지만 위와 같은 경우에는 예외의 현상임을 알 수 있는데,

이를 Belady’s Anomaly이라고 한다.

2) Optimal (최적의) 알고리즘

페이지들 중에 가장 뒤에 사용될 페이지를 replacement하는 알고리즘이다.

이는 비현실적인 알고리즘으로, 상대적인 비교를 위한 알고리즘이다.

 

[사진 10] Optimal  알고리즘

4 frame임에도 불구하고 6 page faults밖에 되지 않는 것을 알 수 있다.

 

[사진 11] Optimal  알고리즘  vs FIFO  알고리즘

3) LRU; Least Recently Used 알고리즘

가장 사용한지 오래된 페이지를 replacement하는 기법이다.

 

[사진 12] LRU  알고리즘

[사진 13] LRU  알고리즘  vs optimal  알고리즘

LRU 알고리즘 구현할 때 Stack(LIFO)을 사용한다.

가장 최근에 사용된 페이지를 top으로,

사용한지 가장 오래된 페이지를 bottom으로 저장한다.

 

[사진 14] Stack  예시  (3 페이지 / 프로세스  -> 6  포인터 )

이와는 반대로 Most Recent Used 알고리즘도 있다

4) Counting 알고리즘 (LFU, MFU)

페이지가 몇 번 사용됐는지 카운트를 한다

• LFU; Least Frequently Used 알고리즘
  • : 카운트가 적은 페이지를 replace한다
• MFU; Most Frequently Used 알고리즘
  • : 카운터가 적으면 메모리에 올라온 지 얼마 안 됐고, 많이 사용될 것이므로 지금까지 많이 사용된 페이지를 replace 한다