[CS/운영체제] CH9. 가상 메모리 1

CH9. 가상 메모리 1

 

목차

1. Demand Paging
2. Page Fault
3. Optimal Algorithm
4. FIFO(First In First Out) Algorithm
5. LRU(Least Recently Used) Algorithm
6. LFU(Least Frequently Used) Algorithm
7. LRU와 LFU 알고리즘의 예제 및 구현

 

0. 가상메모리란

 가상메모리란 물리적 메모리의 크기의 한계를 극복하기 위하여 프로세스를 실행할 때 실행에 필요한 일부 부분만 메모리에 로드하고 나머지는 디스크에 두는 것을 말합니다.

 이렇게 현재 필요한 page만 메모리에 올려놓는 것을 Demand Paging이라고 하고 이번 가상메모리1,2 챕터에서는 이 Demand Paging이 뭔지, 어떻게 해야 효율적인 Demand Paging이 가능한지 여러 알고리즘을 살펴보며 학습하게 됩니다.

 

---

1. Demand Paging

 

Valid / Invalid bit은 해당 페이지가 physical memory(물리적 메모리)에 있는지 없는지 나타내는 bit입니다. 

처음에는 모든 page entry가 invalid로 초기화 되고

주소 변환시 bit가 invalid로 되어 있다면 page fault라는 오류가 발생합니다

 

---

2. Page Fault

Demand Paging의 과정

주로 page faults가 거의 없는 상태를 유지하는게 이상적 0.0x 

 

-> page fault가 일어나면 저 빨간색 시간이 추가가 되는데 이게 시간이 오래걸려 효율이 떨어지기 때문

안 쓰는 페이지 쫒아내기

---

3. Optimal Alogrithm

 

이제부터 이 page를 쫒아낼 때 어떤 페이지를 쫒아내야 performance of demand paging을 올릴 수 있을까 여러 알고리즘들을 살펴보며 고민할 것인데요

 

먼저 불가능하지만 최선의 알고리즘은 이것입니다

이렇게 가장 먼 미래에 다시 참조되는 page를 replace 하는 것이 최적이지만

컴퓨터가 점쟁이도 아니고 미래의 참조를 알 수 없습니다

이 Optimal Algorithm보다는 덜 하지만 그래도 효율이 좋은 다른 방법들이 있지 않을까요?

 

---

4. FIFO 알고리즘

 

 가장 단순히 생각할 수 있는 것은 먼저 들어온 페이지를 먼저 내쫒는 FIFO 방식입니다

 

 CS 하면서 어딘가에 FIFO를 적용했을때 좋았던 점은 단 한번도 없었던 것 같은데요

 이번에도 마찬가지입니다.

 심지어 frame을 늘렸는데 page fault가 줄어들지 않고 늘어나는 경우도 생깁니다

 

---

5. LRU (Least Recently Used) 알고리즘

가장 오래전에 참조된 것을 지우는 단순한 알고리즘 입니다

하지만 효율은 좋습니다. 뒤에 나오지만 연결리스트를 사용하면 O(1)의 시간복잡도로 구현 할 수 도 있고

가장 오래전에 참조되었다는 것은 다시 참조될 확률이 그만큼 적다는 것이기도 하니까요

 

---

6. LFU (Least Frequently Used) 알고리즘

참조 횟수가 가장 적은 페이지를 지웁니다

Heap을 사용하면 O(logN)의 시간복잡도로 구현 할 수 있고

페이지의 인기도는 반영하지만 최근에 참조된 것(뉴진스 페이지)이 삭제가 될 가능성이 있습니다.

---

예제

 

LFU 저렇게 안 함

 

힙이 맞지