Demand Paging

요청시 메모리에 올리는 것이다.
즉 프로그램이 실제로 필요로 할때 페이지를 메모리에 로드하는 방식이다.
1) I/O 양의 감소
2) Memory 사용량 감소
3) 빠른 응답시간
4) 더 많은 사용자 수용

Valid/Invalid Bit를 사용한다.

• Valid Bit: 페이지가 실제 물리 메모리에 있음을 나타냄
• Invalid Bit: 페이지가 물리적인 메모리에 안올라와 있고 Backing Store에 내려가 있는 경우이다. 혹은 사용되지 않는 주소 영역일 경우일 수 도 있다.

주소변환 하려고 봤는데 Invalid인 것들은 MMU가 Page Fault 발생시킨다. (어차피 물리메모리에 없다)
Trap이 발생한다.

• Trap: Page Fault 발생하면 CPU 제어권이 OS에게 넘어감
  이제 OS가 CPU를 가지게 되고 Page Fault 루틴을 처리하게 된다. 또한 DMA 컨트롤러가 Backing Store에서 페이지를 메모리에 올린다.

Free Frame이 없는 경우

Free frame이 없을 경우 운영체제(OS)는 새로운 페이지를 메모리에 올리기 위해 기존에 메모리에 있는 페이지 중 하나를 선택하여 쫓아내야 한다. 이를 페이지 교체(Page Replacement)라고 한다. 페이지 교체 과정은 다음과 같은 단계를 포함한다.

1. Page Replacement

1) 페이지 교체 결정:

OS는 새로운 페이지를 메모리에 올려야 할 때, 메모리에 빈 프레임이 없으면 어떤 페이지를 메모리에서 쫓아낼지를 결정한다. 이 결정은 페이지 교체 알고리즘에 따라 이루어진다.

2) 백업 필요 시 백킹 스토어로 쓰기:

만약 쫓아낼 페이지가 메모리에 올라온 이후에 쓰기 연산(write)이 발생해 변경된 내용이 있다면, 이 페이지의 내용을 백킹 스토어(예: 디스크)로 기록해야 한다. 이를 "dirty page"라고 하며, 변경된 페이지가 아니면 기록할 필요가 없다.

2. Relacement Algorithm

페이지 교체 알고리즘은 어떤 페이지를 쫓아내야 하는지를 결정하는 방식이다. 좋은 페이지 교체 알고리즘은 페이지 결함률(Page Fault Rate)이 낮게, 즉 가능한 한 0에 가깝게 유지하도록 설계되어야 한다.

• Page Fault: 프로그램이 실행 중에 필요한 페이지가 현재 메모리에 로드되어 있지 않음을 발견할 때 발생한다. 즉, CPU가 참조하고자 하는 메모리 페이지가 메모리에 없을 때 발생하는 것이다.

• 평가
  페이지 결함률(Page Fault Rate): 주어진 페이지 참조 문자열(reference string)에 대해 페이지 결함이 얼마나 자주 발생하는지를 측정한다.
  페이지 참조 문자열(Page Reference String): 시간 순서에 따라 페이지를 참조한 순서를 나열한 것이다. 예를 들어 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5라는 참조 문자열이 있을 때, 이는 특정 시간 동안 페이지 1, 2, 3, 4 등을 참조한 순서를 나타냅니다.

1) Optimal Algorithm

Page Fault를 가장 적게 하는 알고리즘이다.
가정: 미래에 참조될 Page들을 다 안다고 가정
가장 먼 미래에 찹조되는 Page를 교체한다.

2) FIFO Algorithm

먼저 들어온 것을 쫓아낸다.
프레임이 많아질수록 성능이 안좋아진다.(3프레임: 9page faults -> 4프레임: 10page faults)

3) LRU(Least Recently Used) Algorithm

제일 오래전에 사용된거를 쫓아낸다.

4) LFU(Least Frequently Used) Algorithm

참조 횟수가 가장 적은 페이지부터 쫓아냄

• 최저 참조 횟수인 페이지가 여러개 있는 경우
  : 마지막 참조 시점이 오래된거부터 쫓아냄

• LRU vs LFU

1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5(현재)
1) LRU: 1번 OUT (가장 최근에 사용되지 않은거)
2) LFU: 4번 OUT (가장 사용률 적었던거)

• LRU vs LFU 구현
  

다양한 캐싱 환경

한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다.

Clock 알고리즘

LRU, LFU는 실제로 쓰지못한다.
LRU와 근사한 알고리즘이다.

과정

중간중간에 CPU가 해당 페이지를 참조하면 HW가 이를 1로 설정한다.

1) 레퍼런스 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동한다.(이동 중 1은 0으로 바꾼다)

2) 포인터가 이동하는 중에 레퍼런스 비트가 0인 것을 찾으면 그 페이지는 교체한다.

3) 1을 0으로 바꾸고, 한바퀴 돌아와서 0이면 그때에는 교체한다.

4) 자주 사용되는 페이지라면 Second Chance(한바퀴 돌아와서)가 올때 1이다.

1. 레퍼런스 비트가 0

시계바늘이 한바퀴 돌아오는 동안 이 페이지에 대한 참조가 없었다.(쫓아낸다)

2. 레퍼런스 비트가 1

시계바늘이 한바퀴 돌아오는 동안 적어도 한번의 참조는 있었다.

페이지 프레임 할당

각 프로세스에 얼마만큼 페이지 프레임을 할당할 것인가

1) Equal allocation: 모든 프로세스마다 똑같이 할당
2) Proportional allocation: 프로세스 크기에 비례하여 할당
3) Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

• Global replacement : 모든 페이지 프레임이 교체대상이 된다. 효율적일 수 있으나 스레싱 위험이 있다.
• Local replacement: 해당 프로세스에 할당된 페이지 프레임내에서만 교체를 수행한다. 안정적성능을 가지고 성능이 예측가능하다. 그러나 자원 충족이 어려울 수 있다.

Thrashing

프로세스의 원활한 수행에 필요한 최소한 페이지 프레임 수를 할당 받지 못하면 페이지 부재율이 크게 상승하여 CPU 이용률이 떨어진다. 이를 스레싱이라고 한다.

Page Fault가 전체적으로 많이 일어남 -> CPU가 인스트럭션 실행하려고 보면 그 페이지가 메모리에 없음 (I/O 해야함)

Working-set Model

적어도 프로그램들이 메모리에서 원활하게 실행되려면 어느정도의 메모리 페이지가 있어야 한다.

프로그램이 특정시간에는 특정 메모리 위치만 집중적으로 참조하는 특징이 있다. 이를 Locality of reference 라고한다.

이러한 Locality of reference에 기반하여 프로세스가 일정 시간 동안 한꺼번에 메모리에 올라와 있어야 하는 페이지의 집합을 워킹셋이라고 한다.

• working-set Model

  워킹셋 집합 전체가 메모리에 올라와 있을 수 있어야 수행이 된다. working set이 페이지 5개인데 메모리가 페이지에 3개의 공간밖에 못준다. 해당 프로세스는 모든 페이지를 반납하고 디스크로 SWAP OUT 된다.

Working-set 알고리즘

왼쪽을 보면 현재 시점에서 이 프로그램의 working set은 5개이다.
working-set 알고리즘은 이 5개의 프레임을 이 프로그램에게 줄 수 있으면 {1, 2, 5, 6, 7}을 한꺼번에 메모리에 올린다.
아니면 전부다 디스크로 Swap Out 시키고 suspended 상태로 바꾼다.

PFF(Pafe-Fault Frequency) scheme

working set 수행하지 않고, 직접 page fault rate를 시스템에서 보고 결정한다.
page fault rate의 상한과 하한값을 두고 프레임을 늘릴지 줄일지 결정한다.(page fault rate가 높다는 것은 필요한 페이지가 없다는 것을 의미한다 따라서 더 할당해줌)
만약 할당시키다가 빈 프레임이 없다면 일부 프로세스를 Swap OUt 한다.

• page size?: 메모리 크기가 커지면서 page size도 이제는 커지는게 트렌드 이다.