TIL 정리_103(Virtual Memory 1)

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

운영체제 강의를 듣고 정리한 내용입니다.

 

Memory Management에서의 메모리 관리는 물리적인 메모리 관리를 의미하기 때문에,

주소 변환에 있어 운영체제의 역할은 없다

 

하지만 Virtual Memory에서는 I/O장치가 접근하기 때문에

사용자 프로세스가 직접 접근할 수 없게되어 운영체제의 개입이 발생한다!

 

---

Demand Paging

요청이 있으면 페이지를 올린다

-> 실제로 필요할 때 page를 메모리에 올리는 것이다

 

특징

• I/O양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

-> 한정된 메모리 공간을 효율적으로 사용할 수 있다

 

 

Valid/Invalid bit의 사용

> invalid의 의미

• 사용되지 않는 주소 영역인 경우
• 페이지가 물리적 메모리에 없는 경우

처음에는 모든 페이지 엔트리가 invalid로 초기화된다

주소 변환시에 invalid bit가 set되어 있으면

“page fault”가 발생한다 

 

 

-> 주소변환을 위해 접근시

invalid인 경우, page fault라는 현상이 발생한다(요청하는 메모리의 부재)

cpu가 자동으로 운영체제로 넘어가기 때문에 운영체제가 cpu를 가지고 fault한다

 

 

Page Fault

invalid page를 접근하면 MMU가 trap을 발생시킨다 (==page fault trap)

커널 모드로 들어가서 page fault handler가 실행된다

 

운영체제는 다음과 같은 순서로 Page Fault를 처리한다

1. 잘못된 요청이 아닌지 확인한다 (주소, 접근권한) -> 프로세스를 강제로 abort 시킨다

2. 빈 페이지를 가져온다, 없으면 뺏어온다 (==replace)

3. 해당 페이지를 디스크에서 메모리로 읽어온다

• 디스크 입출력이 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block)
• 디스크 읽기가 끝나면 page table entry를 기록한다 -> valid/invalid bit를 valid로 바꾼다
• ready queue에 프로세스를 집어넣는다

4. 이 프로세스가 CPU를 잡고 다시 실행된다

5. 중단되었던 instruction을 재개한다

 

페이지 폴트가 얼마나 나는가에 따라 메모리 접근 시간이 크게 좌우된다

대부분의 경우는 페이지 폴트가 일어나지 않고 메모리로부터 직접 주소변환이 가능하다

 

 

Free Frame이 없는 경우

== 빈 페이지가 없는 경우 페이지를 뺏어와야 한다

 

 

Page replacement

• 어떤 프레임을 빼앗아올지 결정해야 한다
• 곧바로 사용되지 않을 page를 쫒아내는 것이 좋다
• 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다

 

어떤 알고리즘이 가장 나은 알고리즘일까?

Replacement Algorithm

page-fault rate가 가급적 0이 되도록 만드는 것이(최소화) 이 알고리즘의 목표이다

알고리즘의 평가

- 주어진 page reference string에 대해 페이지 폴트를 얼마나 내는지 조사한다

**reference string의 예시

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

-> 시간 순서에 따라 페이지들이 참조된 순서를 나열한 것이다

 

 

Optimal Algorithm

4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace한다

Offline Algorithm을 통해 미래의 참조를 알 수 있다

 

미래를 안다고 가정하기 때문에 실제 시스템에서는 사용이 불가하다

대신, 다른 알고리즘의 성능에 대한 upper bound를 제공한다

-> Belady’s optimal algorithm, MIN, OPT 등으로 불린다

 

어떤 알고리즘을 쓰더라도 페이지 폴트는 6번 이하로 발생한다

-> 페이지 폴트를 가장 적게 하는 알고리즘이다

 

 

FIFO Algorithm

실제 시스템에서 미래를 모르는 상태로 운영하는 알고리즘으로 먼저 들어온 것을 먼저 내쫒는다

많은 프레임 -> 적은 페이지 폴트를 의미한다

특이한 성질 : 메모리 크기를 늘리면 보통의 경우 성능이 증가하지만, 이 알고리즘은 성능이 감소한다

FIFO Anomaly (Belady’s Anomaly)라고도 한다

 

 

LRU(Least Recently Used) Algorithm

제일 많이 사용되는 알고리즘이다.

제일 오래전에 사용된 것을 내쫒는다(지운다)

8 페이지 폴트가 나온다

 

 

LFU(Least Frequently Used) Algorithm

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

최저 참조 횟수인 page가 여럿 존재하는 경우

• LFU 알고리즘 자체에서는 여러 페이지 중 임의로 선정한다
• 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수 있다

장점

LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에

페이지의 인기도를 좀 더 명확히 반영할 수 있다

 

단점

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

LRU보다 구현이 복잡하다

 

LFU, LFU 알고리즘 예시

5번 page를 보관하기 위해 어떤 페이지를 삭제해야 하는가?

LRU의 경우 : 1번 페이지 삭제

-> 과거의 참조를 고려하지 못한다

LFU의 경우 : 4번 페이지 삭제

-> 최근의 참조를 고려하지 못한다

 

LRU와 LFU 알고리즘의 구현

LRU : 페이지를 링크드리스트의 형태로 줄을 세운다

리스트 형태로 구현하면 시간 복잡도가 O(1)이 된다

 

LFU : 힙 자료구조를 통해 구현된다 -> 이진 트리 형태이다

맨 위에는 참조횟수가 적은 페이지 밑으로 갈수록 참조횟수가 많은 페이지로 구성된다

O(n)의 시간복잡도를 갖는다