Page Fault
어떤 page 이건 한건 참조한 적이 있다면, 첫번째 참조는 반드시 O.S.에 page fault 를 야기시킨다. 이것이 발생하면 O.S.는 다음 중 어떤 경우인지를 판단하기 위해 valid-invalid bit 를 조사한다. invalid reference 이면 프로그램이 멈춘다.
not-in-memory의 경우, backing store(disk)에 있다는 것을 의미하므로, 이를 가져다 놓기 위해 free page frame을 찾는다. (Placement policy)
발견한 free page frame으로 backing store 내의 page를 읽어온다. (swap page into frame). 이 경우, 만약에 free page frame을 찾을 수 없다면 --> repalacement policy(어떤 페이지를 swap out 할것인지)
그리고 page table을 업데이트 하면서 valid bit = 1 으로 변경한다.
a. 논리주소에 있는 것을 참조한다.
b. page fault발생
c. disk에 있다.
d. 빈공간에 페이지를 swap in 한다.
e. valid bit를 1로 변경.
f. 다시 참조
빈 페이지 프레임이 없는 경우
page replacement가 발생한다. 메모리 상에 빈공간이 없는 경우 현재 메모리를 차지하고 있는 page들 중에서 어떤 page를 backing store로 swap out 할 것인지 선택해야 한다. 다양한 알고리즘 중에서 page fault 횟수를 최소화 시킬 수 있는 알고리즘이 가장 좋은 replacement 알고리즘이다.
page fault 비율은 0<= p <= 1.0 이다.
만약 p가 0이면 page fault가 없는 것이고 p가 1이면 매 참조마다 일어나는 것이다.
hit rate는 참조에 성공하는 비율이다. h = 1 - p
Page Replacement
메모리를 점유하고 있는 page들 중 어떤 page가 선택되어, backing store의 swap area로 swap out되어야만 한다. page fault 서비스 루틴에 page replacement 알고리즘을 포함시켜, 메모리의 과도한 할당을 방지한다. dirty-bit(혹은 modify-bit, 변경했는지 확인하는 것)를 사용하여, page이동에 대한 overhead를 줄일 수 있다. 즉, swap-out 시 변경된 page만 이동시키고 그렇지 않은 page는 swap-out 시킬 필요가 없다.
교체 알고리즘을 사용하여 swap out할 page를 선택한다.
page fault가 발생했는데 빈 공간이 없다면 물리 공간에 있는 페이지를 replacement 알고리즘을 통해 swap out하고 disk에 있는 M를 swap in 한다.
좋은 replacement 알고리즘
좋은 교체 알고리즘은 페이지 fault 비율이 낮다. hit rate에 영향을 미치는 주요 요소들로써 주소들의 타입이 나오는 패턴, 한번에 올라오는 block의 크기, mm의 크기, 교체 policy가 있다.
보통 사용가능한 page frame 수가 증가할수록 공간이 많으므로 page fault rate는 줄어든다. 그러나 FIFO와 같은 특정 알고리즘의 경우, 할당 가능한 page frame 수가 증가하는데도 불구하고 page fault rate까 증가하는 경우가 있는데, 이를 Belady's anomaly라고 부른다.
