OS-0606: Page Replacement(L28)

#Page replacement policy

- 프레임이 필요한데 꽉 찼을 때 무엇을  쫓아내나(1프레임당 1페이지만 가짐)

1. Random - 아무거나

2. FIFO - 가장 오래된거

3. Optimal(minimal)

    > 가장 오랫동안 참조되지 않을(미래형) 페이지를 쫓아냄

        > 미래를 예측해야 함

    > 실제로 구현되지 않음

        > 다른거 평가하는 용으로 사용(SJF처럼)

4.★ LRU(Least Recently Used)

    > 과거로 미래 예측

    > 가장 오랫동안 참조되지 않은 것 쫓아냄

 

1. FIFO

frame1 = a       a        d 

frame2 =    b         b       a

frame3 =       c                     b

* Page references = 페이지 참조되는 순번

*page fault는 가장 최초에 아무것도 없는 상태에서 1번은 무조건 일어난다고 하

#Implementing LRU

- 완벽한 구현은 이럴 것이다:

> 페이지마다 클락 레지스터 추가

> 접근마다 클락 밸류 갱신

> 모든 페이지의 클락 레지스터에서 가장 낮은 값을 가진거 쫓아냄

 

- 간단한 접근:

> FIFO

> Not-recently-used(NRU)

    > R(참조) 비트를 사용, 참조 될 때 설정

    > 클럭 인터럽트마다 R 초기화

    > 초기화된 R비트 가진 거중 아무거나 쫓아냄

 

- Clock/Second Chance Algorithm

- Least Frequently Used / N-th chance Algorithm

 

#Frame Allocation

- 프로세스마다 몇개의 프레임을 갖는가

   > 최소 2개

   > 최대는 물리 메모리

- Allocation algorithm:

   > equal allocation (m/n frame)

   > proportional allocation

- 어느 프레임의 풀이 대체되나

   > local replacement - 자기 프레임만 가지고 정책 세움

   > global replacement - 메인 메모리 전체를 대상으로 대체 정책 세움

 

#Thrashing

- 메모리가 너무 많이 사용돼서 프로세스가 잠시 쉬는 사이에 쫓겨나 버리는거

- demand paging에서 멀티태스킹을 너무 많이 하면 page fault가 더 많이 일어나 성능이 떨어짐

* 비유: 학생이 너무 많은 학점을 들어서 할게 너무 많아지는 것

 

#Working set

- Thrashing은 모든 프로세스의 요구량이 물리 메모리보다 큰 경우 발생

    > Solution: 프로세스들이 경쟁하지 않도록 로컬 페이지 프레임 교체 사용

        > 개별 프로세스는 여전히 Thrashing에 빠질수도

    > Solution: 프로세스에 필요한 프레임 수만 할당

        > 시간이 지남에 따라 각 프로세스에 할당된 프레임 수를 변경

        > 전체 필요량이 너무 높은 경우 프로세스를 선택하여 중단시킴

- Working set은 프로세스가 작업하는 프레임의 집합, Thrasing을 피하기 위해 주 메모리에 상주해야 하는 페이지

    > 항상 이것을 메모리에 유지

    > 필요에 따라 다른 페이지는 버릴 수 있음