[OS] 페이지 교체(Page Replacement)

페이지 교체는 Demand Paging 기법에서의 기본이다.

 

가상메모리 기법을 사용하면 다중 프로그래밍의 정도를 높여서 프로세스의 수를 늘릴 수 있다.
But, 갑자기 프로세스들의 페이지를 모두 필요로한다면, 메모리 과할당이 발생할 수 있다.

 

 

Page-Fault가 발생하고 Page를 Disk에서 Memory로 가져오기 위해서 Free Frame을 찾는데 없을경우?

 1) 해당 프로세스를 강제종료한다. (사용자에게 Pageing System을 들키는 꼴이다 !!)

 2) 프로세스 하나를 Swap-out해 Free Frame을 확보한다. (비효율적 ...)

 3) 페이지 교체를 통해 사용중이지 않은 페이지와 교체한다. (Page Replacement)

 

 

Demand Paging System에서 가장 중요한 2가지는 !
 1) Frame 할당 알고리즘
 2) Page 교체 알고리즘
OS마다 각자의 알고리즘을 사용하지만, 모두 Page-Fault 발생률 최소화라는 공통된 기준을 갖는다.

 

기본적인 페이지 교체

 1) Disk에서 필요한 Page의 위치를 알아낸다.

 2) Free Frame을 찾는다. 없으면 희생될 Frame을 찾기위해 교체 알고리즘을 가동한다.

                                                                          ( Demand Paging 기법에서 중요한 것중 1개 )

 3) 희생될 Page를 Disk에 기록하고 Page Table를 수정한다.

 4) Free Frame에 Page를 읽어오고 Page Table를 수정한다.

     ( 3, 4번에 의해 Disk에 두번 접근하게 된다. )

 

Disk에 두번 접근하는 것을 변경Bit 를 통해 완화시킬 수 있다.

교체 대상이 된 Frame이 변경되지 않았다면 Disk에 쓰지 않고 덮어쓴다는 원리이다.

각 페이지나 프레임은 그것과 관련된 변경비트를 하드웨어에 가지게 된다.

 

 

메모리 참조열?

 

 메모리 참조가 이루어진 Page번호 들을 나열한 것. 이 참조열은 인공적으로 생성할 수도 있고, 주어진 시스템을 추적하여 매 메모리 참조 시의 주소를 기록할 수도 있다.

 

요구 페이징 시스템은 두 가지 중요한 문제를 해결해야 되는데, 그것이 Frame Allocation Algorithm과 Page Replacement Algorithm 이다. 즉, 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 Frame을 할당해야 할지 결정해야한다. 또한 페이지 교체가 필요할 때마다 어떤 페이지를 교체할지 결정해야 한다.

 

 

---

Belady의 모순?

할당 Frame이 4개일때 Page-Fault가 9번 발생하는데, Frame이 3개일때 Page-Fault가 8번 발생하는 모순적인 상황을 일컫는다. Frame을 더 줬더니 페이지 부재율이 더 증가하는 현상이다.

 

페이지 교체 알고리즘

1. FIFO

 - 시간순 or Queue를 이용한 가장 간단한 페이지 교체 알고리즘이다.

 - 당연하게도 간단한 만큼 효율이 떨어지고, 안정성 또한 안좋다

      ( 안정성이란 초기화 모듈 혹은 자주 사용되는 Page가 교체될 수 있다. )

 

2. 최적 페이지 교체

 - 모든 Algorithm보다 Page-Fault율이 낮고 Belady의 모순이 발생하지 않는다. (이론상 최고)

 - "앞으로 가장 오랜시간 사용되지 않을 페이지를 교체해라 !" 라는 접근법이다. 

    이를 OPT 알고리즘이라고 한다.

 - 그러나 실제구현은 어렵다. 어떤 메모리를 참조할지 미리 볼 수 없기 때문이다.

 

3. LRU 페이지 교체 (Least-Recently-Used)

 - "가장 오래 이용되지 않은 페이지를 교체해라 !" 라는 접근법이다.

 - 구현가능 ?  약간의 H/W 지원을 받아서 가능하다. ( 최근 이용된 시간을 체크한다. )

 

   1) 계수기 - 각 페이지별로 사용시간 Field를 추가. CPU에 논리적인 시계나 계수기를 추가.

                  페이지 교체시 Page Table를 찾고, Page 사용시 시간 갱신을 위한 Memory Write.

                  또 추가적으로 시간 값에 따른 OverFlow도 고려해주어야 한다.

   2) Stack (사실상 List..?) - 페이지 참조시 꼭대기에 놓인다. ( 페이지 번호로 이루어진 스택 )

                                    꼭대기엔 항상 최근에 사용한 페이지 번호가 위치하게된다.

                                    갱신시 Stack을 재정비해야 하지만 페이지 교체시 Page Table탐색은 생략된다.

 

 - 위 두가지 방법 모두 반드시 H/W 지원을 받아야 한다.

   소프트웨어적으로 이러한 관리 OverHead를  감당할 수 있는 System은 거의 없다.

 

4. LRU 근사 페이지 교체

 - LRU 페이지 교체 자원을 충분히 할 수 있는 H/W는 거의 없다.

   참조비트의 형태로 어느정도의 지원은 가능하다.

    ( 최초 0, 참조시 1 : 안쓰인 페이지를 확인할 수 있다. )

 

 - 부가적 참조 비트 알고리즘.

   - 00000000 이라는 비트를 가지고 일정시간마다 Time Interrupt를 걸어서 Shift.

                        ( 최근 8구간에서 페이지 사용기록을 가진다. )

   - 가장 작은 값의 Page들을 모두 교체 or 그 중에서 FIFO 알고리즘 적용.

 

 - 2차기회 알고리즘.

   - 단순히 참조비트만을 이용.  참조비트가 0인 Page중에서 FIFO 알고리즘 적용.

 

 - 개선된 2차기회 알고리즘.

   - 참조비트 + 변경비트를 이용. ( 추가적인 설명은 생략한다. )

     변경되었다면 Disk에 써야하기 때문에 교체하기 부적절하다.

     이 두가지 비트를 확인해 교체할 페이지를 결정하는 것이다.

 

 

5. 계수-기반 페이지 교체

 - LFU (Least Frequently Used) : 참조회수가 가장 적은 페이지를 교체.

                                           반짝 사용하고 마는 Page가 있는경우 빗나가는 경우가 많다.

                                           일정시간마다 참조회수를 Shift하는 해결책이 있다.

 - MFU (Most Frequently Used) : 참조회수가 가장 많은 페이지가 최근에 참조된 것이라 판단한다.

 

하지만 위 두개의 페이지 교체 알고리즘은 구현하는데 자원소모고 심하고 OPT에 제대로 근사하지 못하기 때문에 잘 사용되는 않는 알고리즘이라고 한다.

 

 

6. 페이지-버퍼링 알고리즘.

 - 가용 Frame Pool 여러개를 보유한다. (임시 거처)

   그리고 나서 교체될 대상 Frame을 Disk에 쓰기 전에, 우선적으로 Disk에서

   Page-Fault가 발생한 Page를 Frame Pool 중 하나의 Frame에 작성한다.

 

 - 전체적으로 보면 Frame에 대한 손해지만, 실행되는 Proccess의 반응이 빨라진다.

 

 

 - 디스크가 한가할 때 변경된 Page를 Disk에 갱신 - 변경비트를 0으로 갱신한다.
 ( 한가할 때 미리미리 해두자는 마인드. 근데 그 사이에 또 변경되면 손해긴 할듯... )