08. 가상 메모리 - 1

Demand Paging

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

이점

• i/o 양의 감소
• 메모리 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용 가능

valid/invalid bit의 사용

• invalid: 해당 페이지가 물리적 메모리에 없음 or 사용되지 않는 주소 영역임
• 처음에 모든 page entry는 invalid로 초기화됨
• 주소 변환 시 invalid bit으로 설정되어 있다면 page fault가 발생했다고 말한다 -> 일종의 software interrupt

Page Fault

• invalid page로 접근하면 [[8강 메모리 관리 - 1#MMU (Memory-Management Unit)|MMU]]가 trap을 발생시킴 (page fault trap)
• kernel mode로 들어가 page fault handler가 실행됨

처리 루틴

1. 잘못된 주소이거나 사용하지 않는 주소, 접근 권한이 없으면 프로세스 강제종료
2. 그렇지 않다면 빈 페이지 프레임을 가져온다. 프레임이 다 꽉 차있다면 뺏어온다.
3. 해당 페이지를 디스크에서 메모리로 올려놓는다.
   • disk i/o가 끝나기까지 프로세스는 cpu를 선점당함
   • disk read가 끝나면 page table entry에 기록해두고 valid bit으로 바꾼다.
   • ready queue에 process 삽입 -> 향후 dispatch

Page fault 발생 시 빈 페이지 프레임이 없을 경우

Page replacement (OS의 업무)

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

교체 알고리즘

• 목표: page fault 발생 확률을 최소화한다
• 알고리즘의 평가 방법
  • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사한다
• reference string의 예시 (페이지들의 참조 순서)
  • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Optimal Algorithm

page fault를 가장 적게 발생시키는 알고리즘

이 알고리즘에서는 미래에 참조되는 page를 알고 있다고 가정한다
실제로는 불가능하기 때문에 offline algorithm이라고도 함
가장 먼 미래에 참조되는 page를 쫓아내는 방식으로 동작한다

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

• Belady's optimal algorithm, MIN, OPT 등으로 불린다

FIFO (First In First Out) Algorithm

메모리에 가장 먼저 들어온 것을 먼저 내쫓는다

메모리의 크기를 늘리면 성능이 더 안 좋아진다 (FIFO Anomaly)

LRU (Least Recently Used) Algorithm

가장 오래 전에 참조된 것을 쫓아낸다

LFU (Least Frequently Used) Algorithm

가장 참조 횟수가 적은 페이지를 쫓아낸다

• 최저 참조 횟수의 page가 여러 개 있는 경우
  • LFU 알고리즘 자체에서는 임의로 선정한다
  • 성능 향상을 위해 그들 중 가장 오래 전에 참조된 걸 고르게 할 수 있다
• 장단점
  • LRU처럼 직전 시점만 보는 것이 아니라 장기적인 관점에서 보기 때문에 page의 인기도를 정확히 반영 가능

위 그림은 5번 페이지를 참조하기 위해 메모리에 있는 1, 2, 3, 4페이지 중 하나를 내쫓아야하는 상황이다.
LRU 알고리즘에서는 가장 오래 전에 참조된 1번 페이지를 쫓아낸다.
하지만 1번 페이지는 페이지들 중 가장 많이 참조된 페이지이기 때문에 또 참조될 가능성이 있다.
LFU 알고리즘에서는 한 번만 참조된 4번 페이지를 쫓아낸다.
하지만 4번 페이지는 가장 최근에 참조되었으므로 언제 또 필요할지 모르기 때문에 합리적인 선택으로 보기 어렵다.
이처럼 각자 장단점이 있어 둘의 장점만을 결합한 알고리즘에 대한 연구가 계속되고 있다.

LRU와 LFU의 구현

1. LRU
Linked List 형태로 페이지 참조 시간을 관리
가장 오래 전에 참조된 것 - 가장 최근에 참조된 것 순
어떤 페이지가 메모리에 들어오거나 메모리 내부에서 다시 참조되면 Linked List의 맨 밑으로 보내면 된다
쫓아낼 때에는 맨 처음에 있는 걸 쫓아낸다
시간복잡도: O(1)

 

2. LFU
Linked List 형태로 페이지 참조 시간을 관리
가장 적게 참조된 것 - 가장 많이 참조된 것 순
어떤 페이지가 메모리에 들어오거나 메모리 내부에서 다시 참조되면 참조횟수를 비교해서 적절한 자리에 끼워넣는다
=> 시간복잡도가 O(N)으로 비효율적이기 때문에 heap 자료구조를 이용한다. 루트 노드는 참조 횟수가 가장 적은 페이지!
쫓아낼 때에는 루트 노드를 쫓아내고 힙 재정렬
시간복잡도: O(logN)