[운영체제] 가상 메모리 1 : page fault, replacement algorithm

가상 메모리 1
(참고 강의 : http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Demand paging

(메모리 할당 방법 중 페이징 기법을 쓰고 있다고 가정한다. 그리고 요즘 대부분 시스템이 페이징을 쓴다고 한다.)

실제로 필요할 때 page를 메모리에 올리는 것을 말한다.
좋은 프로그램일수록 보안, 방어 처리 코드가 대부분이고, 자주 사용하는 부분은 얼마 안된다고 한다.
이 페이지들을 굳이 비싸고 좁은 메모리에 올려놓을 필요가 없겠지?

• I/O 양 감소
• Memory 사용량 감소
• 빠른 응답시간**
• 더 많은 사용자 (프로그램) 수용

** Q. 응답시간이 빠르다? 다 올려 놓으면 디스크 갔다 올 필요없으니 더 빠른 거 아님?
A. paging 만 놓고 봤을 땐 그럴 수 있으나, 전체 시스템적으로 봤을 때 자주 쓰는 페이지를 올려놓는다면
메모리 관리하는데 더 유용할 것이고, 전체 시스템 속도가 빨라질 수 있는 것을 말한다.

Valid/Invalid bit를 사용하여 해당 페이지가 물리적 메모리에 있는지 없는지 판단한다.

• Invalid : 사용되지 않는 주소이거나/ 페이지가 물리적 메모리에 없는 경우
• 처음에는 모든 page entry가 invalid로 초기화
• page fault : address translation 시 invalid bit이 set 되어 있는 경우

페이지를 나눠놨는데 내용이 비어있을 수도 있다. 혹은 진짜 물리적 메모리에 없거나, 그럴 때 invalid를 사용하고,
invalid로 되어 있는 페이지를 찾으려고 하는 경우 "page fault가 발생했다" 고 한다.

재밌는 것은, 이미 물리적 메모리에 올라와 있는 페이지 A,C,F가 그대로 디스크에도 있다는 것이다.
그래서 A를 메모리에서 쫓아낼 때, 만약 A가 read-only라면, 디스크로 옮길 필요없이 그냥 삭제만 해주면 되는 것이다.
(디스크와 메모리의 내용이 같을 경우 어차피 똑같은데 뭣하러 옮기누?)
만약 내용이 변경되었다면 옮겨줘야 할 것이다.

Page Fault 처리 과정

1. Invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
2. **Kernel mode로 들어가서 page fault handler가 invoke됨
3. 다음과 같은 순서로 page fault 처리됨
   1. Invalid reference ? (bad address, protection violation) => abort process
   2. Get an empty page frame(꽉 찼으면 누구 하나 버려)
   3. Disk read 끝나면 page tables entry 기록, valid로 변환
   4. ready queue에 process insert => dispatch later
4. 이 프로세스가 CPU 잡고 다시 실행
5. 페이지 테이블 접근 부터 다시 시작

**disk에서 메모리로 옮기는게 I/O 아니겠는가? 그래서 운영체제가 개입을 하는거고

demand paging을 사용할 경우,
요청한 페이지가 물리적 메모리에 있으면 아주 빠르겠지만 ( (1-p) x memory access)
없을 경우 아까 과정을 다 거쳐야 하니,
운영체제 개입 비용 + (메모리 꽉 찼으면 누구 하나 버리는 비용) + 디스크에서 불러오고, page table 기록하는 비용 + 다시 첨부터 시작

존나게 느려질 것이다.
실제로 요즘 컴퓨터(2014년)은 2% 정도의 page fault가 발생한다고 한다.

자 이제 여기까지 이해했다면 당신은 다음과 같은 의문이 들어야 한다.

"아니 꽉 찼을 때 누구 하나 버린다고 했는데, 어떤 알고리즘으로 선정하는거지?"

Free frame이 없는 경우

page replacement

• 어떤 frame 뺏을 지 결정해야 함
• 곧 바로 사용되지 않을 page 버리는 게 좋음
• 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수도 있음
  
  (아까 말했듯 read-only 페이지면 1번 필요없이 그냥 메모리에서 지우기만 하면 됨)

replacement Alogrithm

뭘 기준으로 버릴 놈을 선정할 것인가???

• page fault rate을 최소화하는 게 목표
• 알고리즘 평가 : 주어진 page reference string에 대해 page fault 얼마나 내는지 조사
• **page reference string 예시 : 1,2,3,4,1,2,5,1,2,3,4,5

**그냥 인간이 임의로 만든 페이지 불러오는 순서가 있다고 가정을 하고, page fault를 얼마나 내는지 조사하는 것이다.

Optimal Alogrithm

MIN(OPT)라고도 불리며,

가장 먼 미래에 참조되는 page를 replace!!!

메모리가 ㅈㄴ 작아서 frame이 4개라고 가정한다.
처음엔 비어있으니 1,2,3,4 불러올 때 당연히 page fault가 발생할 것이고,
그 다음 1,2는 이미 있으니 page fault가 발생하지 않겠지.
5를 불러올 때 어디를 버려야 하는가? 미래를 보면 알 수 있다.
미래가 1,2,3,4네? 4가 제일 뒤네? 너 나와

무슨 개소리냐고 생각이 들어야 한다. 미래를 어떻게 암?
가정이다. 가정. 이 완벽한 알고리즘을 기준으로 실제 알고리즘의 성능을 판단할 수 있는 것이다.

• 미래의 참조를 어떻게 아는가 ? : offline algorithm
• 다른 알고리즘 성능에 대한 upper bound 제공
• Bleady's optimal algorithm, MIN, OPT 라고도 불림

자 그럼 실제로 쓸 수 있는 알고리즘은 뭐가 있을까?

FIFO Algorithm

참 쉽다. 먼저 들어온 놈 먼저 버리는 알고리즘

재밌는 점은, 프레임이 많아질수록 page fault가 많아진다.
말이 되냐? 메모리가 커질수록 속도가 느려진다는게? ㅈㄴ 쓰레기임 그냥

LRU(Least Recently Used) Algorithm

가장 오래 전에 참조된 것을 지움

중간에 5를 보자. 5 순서 앞에 4,1,2를 참조했으니 가장 오래전에 참조된 것은 3이다. 너 나와.
뭐 그럴싸해 보인다. 그럼 최근에 뭘 참조했는지에 대한 기록은 어디에 하냐고? 운영체제 안에 저장한다.(이따 나온다)

LFU(Least Frequently Used) Algorithm

참조 회수가 가장 적은 페이지를 버린다.

최저 참조 횟수 page가 여러개면?

• 랜덤으로 하나 픽
• 가장 오래 전 참조된 page 지우게 구현도 가능

장단점

• Good: 장기적인 시간 규모를 보기에 page 인기도를 좀 더 정확히 반영가능
• Bad : 참조 시점의 최근성 반영 못함
• Bad : **LRU보다 구현 복잡함

**당연히 더 복잡하지. 최근에 불러온 순서 저장 vs 각 페이지가 몇 번 불러왔는지 카운팅
누가 더 어렵겠냐?

LFU는 카운팅을 하므로 1번 불러온 페이지 4 버릴 것이고
LRU는 참조가 가장 오래된 1번 버릴 것이다.
둘 다 완벽하지 않고 문제점이 있네 ㅇㅇ

LRU & LFU 알고리즘 구현

LRU 알고리즘 : 연결리스트

LRU 가 뭐라고 ? 옛날에 참조된거 버리는거
LRU는 연결리스트(linked-list)로 구현할 수 있다.

페이지들을 시간 순으로 줄 세우기를 한다. 위가 가장 오래된, 아래가 가장 최근 참조된 페이지.

페이지를 참조할 때 마다 밑으로 하나씩 추가를 하는 것이다.
만약 그림처럼 아까 참조했던거 다시 참조했다면? 가장 밑으로 옮기면 된다.
페이지 꽉 찼으면? 가장 위에꺼 버리면 된다.

서로 다른 페이지끼리 비교할 필요가 1도 없다. 따라서 시간복잡도가 O(1)이다.

LFU 알고리즘 : 힙 (이진트리)

가장 위가 참조 회수 가장 적은 것, 아래로 갈수록 횟수가 많은 것이다.
페이지가 꽉 찼을 땐 맨 위 버리고 트리를 다시 구성하면 되고,
특정 페이지를 다시 불러 왔을 땐 카운팅을 해줘야 되는데, 자기 자식들을 타고 가면서 비교하고 위치를 스왑하면 된다.