10.1 Virtual Memory 1

 지난 강에서 배운 메모리 주소 변환은 운영체제가 관여하지 않는다고 했었다. 그러나 이 가상 메모리 기법은 전적으로 운영체제가 관여한다. 이번 강은 일단 메모리 관리 기법 중에서 Paging 기법을 사용한다고 가정한다.  

---

Demand Paging

 요청이 있으면 그 페이지를 메모리에 올리겠다는 뜻이다. 메모리 관리 기법으로서 Paging을 사용하며 어떤 프로세스를 메모리에 올려야 한다고 하자. 이때 프로세스의 모든 페이지를 전부 올리는 것이 아니라 Demand Paging 기법을 사용한다. 이 Demand Paging은 해당 Page가 요청될 때 그 Page를 메모리에 올리는 것을 말한다.

 

 프로그램에서 빈번히 사용되는 부분은 지극히 제한적이다. 잘 만들어진 대부분의 소프트웨어는 대체로 방어적인 코드들이 산재한다. 그런데 그런 코드들은 거의 실행되지 않기 때문에 이 페이지들을 메모리에 올리는 것은 분명한 부담이다. 따라서 필요할 때만 페이지를 메모리에 올리게 된다면 I/O 양이 감소할 것이며 빠른 응답 시간을 기대할 수 있다. 또한 물리적인 메모리 사용량도 감소할 것이고 이에 따라 멀티프로그래밍 환경에서는 더 많은 사용자 프로그램을 수용할 수 있게 된다.

 

 다만 빠른 응답 시간에 대해서는 이견이 있을 수 있다. 한 번에 모든 페이지를 올리게 되면 디스크에 I/O를 할 일이 없으니 Demand Paging이 더 느릴 수도 있다는 것이다. 그러나 한정된 메모리 공간에 더 많은 사용자 프로세스를 로드하여 동시에 실행된다면 한 번에 모든 페이지를 로드하는 것보다 Demand Paging을 사용하는 편이 응답 시간의 측면에서도 더 낫다는 것이다.

 

정리 : 

1. I/O 양의 감소

2. Memory 사용량 감소

3. 더 많은 사용자 수용

4. 빠른 응답 시간

---

* Valid / Invalid bit *

 

* Invalid bit : 

- 사용되지 않는 주소 영역 (그림 1에서는 G, H가 사용되지 않는다)

- 페이지가 물리적 메모리에 없는 경우 (Backing store에 있는 경우)

 

 처음에는 모든 page entry가 invalid로 초기화되고 address translation 시에 해당 page entry의 invalid bit가 set되어 있으면 backing store에 있을 수 있으며 이를 가져오기 위해선 Disk I/O 작업이 필요하기 때문에 MMU에 의해 "page fault trap (Software Interrupt)"이 발생한다. 그러면 CPU는 운영체제에게 넘어가게 되며 운영체제에는 Page fault에 대한 처리 루틴이 정의되어 있다.

1. Invalid reference? or not? (ex. bad address, protection violation) => process를 abort 한다.

2. 정상적인 메모리 요청이라면, 메모리에서 빈 페이지 프레임을 하나 얻어야 한다(페이지가 들어가야 하니까). 만약 빈 페이지 프레임이 없다면 강제로 하나 뺏어서 replace 한다.

3. 해당 페이지를 Disk에서 memory로 읽어온다. Disk I/O가 끝나기까지 이 프로세스는 CPU를 뺏긴다(Preempt, into blocked state). Disk read가 끝나면 page tables entry를 기록하며 valid/invalid bit를 "valid"로 세팅한다. 마지막으로 ready queue에 process를 insert 한다.

 그림 1, 2를 참고하면 이해가 쉽다.

그림 1 : 페이징 기법을 사용할 때의 메모리 상태

그림 2 : Steps in Handling a Page Fault

 

---

* Performance of Demanding Paging *

 

• Page Fault Rate 0 <= p <= 1.0

  if p = 0, no page faults

  if p = 1, every reference is a fault

• Effective Access Time (EAT)

  = (1 - p) * memory access // page fault가 나지 않는 비율

             +

     p * (Operation System & HardWare page fault overhead + [swap page out if needed] + swap                   page in + OS & HW restart overhead (나중에 CPU를 얻을 때 restart 하는 비용) )

---

Page Replacement

 OS가 하는 업무이다. 어떤 Page를 쫓아낼지 결정하는 것이다. 곧바로 사용되지 않을 page를 쫓아내는 것이 좋으며 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다.

• Replacement Algorithm

  page-fault rate을 최소화하는 것이 목표이다.

  알고리즘의 평가는 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사한다.

  reference string의 예

  1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

그림 3 : 

---

* Optimal Algorithm (Offline Algorithm) *

 

page fault를 가장 적게 하는 알고리즘이다.

 

 일단 미래에 참조될 페이지들을 미리 전부 안다고 가정하자(Offline algorithm. 좀 있다가 Online Algorithm 설명). 물론 실제로는 미래를 모르기 때문에 이 방법을 실제로 시스템에 적용하기는 어려우나 실제로 적용되는 알고리즘(Belady's optimal algorithm)의 성능에 대한 upper bound는 제공할 수 있다.

 

 MIN (OPT) : 가장 먼 미래에 참조되는 page를 replace 한다. 이 방법은 optimal 하기 때문에 총 6번의 page faults보다 적게 page fault를 발생시키는 알고리즘을 찾을 수 없다. 이러한 이유로 Page Fault를 가장 적게 낸다고 해서 MIN이라고도 불린다.

 

 상식적으로 생각하면 이 방법이 당연히 optimal이다. 증명은 따로 하지 않는다. <그림 4> 예시 참조.

 

 

그림 4 : MIN Algorithm (Offline Algorithm) string reference Example

 

 

---

Replacement Algorithm (Online Algorithm)

 이번엔 실제로 시스템에서 사용되는, 미래를 모를 때 사용하는 알고리즘(Online Algorithm)에 대해 알아볼 것이다.

---

* FIFO (First In Fist Out) Algorithm *

 말 그대로 먼저 들어온 것을 먼저 내쫓는다. 그러나 일반적으로는 page frame을 늘리면 성능이 좋아져야 하는데 이 경우는 오히려 더 많은 Page Faults가 발생할 수 있다는 것이다. 이것을 FIFO Anomaly (Belady's Anomaly)라고 부른다.

 

그림 5 : FIFO Algorithm reference string Example

---

* LRU (Least Recently Used) Algorithm *

 

 LRU : 가장 오래전에 참조된 것을 내쫓는 것이다. 과거를 가지고 어떤 것을 쫓아낼지 판단한다는 것이다. 미래를 모르면 과거를 봐라. 다음 그림 6을 보면 쉽게 이해될 것임. 최근에 참조된 페이지가 다시 참조될 가능성이 높다는 것이다.

 

그림 6 : LRU Algorithm reference string Example

---

* LFU (Least Frequently Used) Algorithm *

 

참조 횟수(reference count)가 가장 적은 페이지를 쫓아낸다. 

 

최저 참조 횟수인 page가 여러 개인 경우:

• LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.

• 성능 향상을 위해 가장 오래 전에 참조된 page를 지우도록 구현할 수 있다.

 

장단점

• LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.

• 참조 시점의 최근성을 반영하지 못한다.

• LRU보다 구현이 복잡하다.

---

LRU, LFU Example & Implementation

 

* LRU, LFU Example *

 

 <그림 6>을 살펴보자. 오른쪽 화살표가 그려진 그림은 지금까지 page의 참조 시간과 횟수를 기록한 그림이다. LRU의 경우는 1번 page를 삭제할 것이다. 반면 LFU는 4번 page를 삭제할 것이다. LRU는 1번과 같이 예전에 인기 있었던 Page를 선별하지 못하고, LFU는 4번 Page와 같이 최근에 인기 있어지기 시작한 Page를 선별하지 못한다. 

 

그림 7 : LRU, LFU 비교 예시

---

*LRU, LFU Implementation *

 

 LRU는 어떤 페이지가 한 번만 참조되어도 그 노드의 우선순위가 가장 높아진다. 따라서 doubly linked list를 활용하여 메모리 참조와 preemption을 O(1) time complexity로 처리할 수 있다. 그러나 LFU는 어떤 페이지가 참조가 되더라도 MFU로 바로 내려갈 수 없고 비교를 하면서 내려갈 수 있게 된다. 따라서 최악의 경우 메모리 참조와 preemption을 O(N) time complexity로 처리하게 된다. <그림 8>을 보자.

 

그림 8 : Linked LIst로 구현한 LRU, LFU

 

 

 따라서 <그림 9>와 같이 LFU의 경우는 heap (complete binary tree)를 이용하여 구현한다. 시간 복잡도는 O(logN)이 되며 performance가 크게 개선된다.

 

그림 9 : LFU를 heap으로 구현

본 글들은 이화여대 반효경 교수님 2014학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323