[OS] 페이징 교체 알고리즘

페이징 교체 알고리즘

페이징 교체 알고리즘이란 페이지 부재가 발생했을 때, 새로운 페이지를 할당해야 하는데 이때 현재 할당된 페이지중 어떤 것을 교체할지 결정하는 방법이다.

 

👉🏻Page Fault를 줄이는 방법에 대해서 설명하세요.

• Page Fault 란?
  프로그램을 실행하기 위해 요청한 page가 메모리에 있는지 없는지를 확인하기 위해 page table에 valid-invalid bit를 추가하여 확인한다. 만약 있다면 valid고 없다면 invalid로 세팅되는데, 없을 때를 page fault라고 부른다.
  (cache에서의 miss와 유사하다.)
• 이렇게 보면 page fault가 발생했을 때 생각보다 너무 많은 overhead가 발생된다. 메모리의 접근이 너무 많이 일어난다. page fault를 최소화하기 위한 방법에는 frame의 사이즈를 키우거나, TLB도 하나의 예가 될 수 있다.

 

👉🏻Page Fault가 발생하였을때, 이를 처리하는 과정을 설명해주세요.

1. page table을 통해 필요한 page가 없다면 (invalid) 즉, page fault

2. 운영체제에 page fault trap을 발생시킨다.

    2-1. 동작하고 있던 프로세스의 PCB를 메모리에 저장한다. 

3. 그러면 운영체제는 다른 page table을 확인한다. 그리고 뭔가 이상하다면 프로세스를 중지시키고 그냥 메모리에 없는 것이라면 backing store에서 찾는다.

4. 필요한 page를 찾아서 물리 메모리에서 빈 frame을 찾는다. 빈 frame이 없다면 교체 알고리즘으로 page in, page out을 수행해야 한다. 이때 프로그램은 wait queue에 들어가서 대기한다. 

    4-1. free frame을 찾고 있을 때 CPU는 다른 프로그램에게 할당된다.

    4-2. 찾았다면 CPU를 사용하고 있던 프로그램의 PCB를 저장하고 page fault를 발생시킨 프로그램의 PCB를 가져온다. 

5. 그리고 물리 메모리에 올리면, page table을 update 한다. 즉, valid bit를 수정한다

6. page fault를 발생시킨 코드를 다시 시작한다.

 

👉🏻페이지 교체 알고리즘엔 어떤 것들이 있나요?

1. FIFO 알고리즘
- First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

- 간단하고, 초기화 코드에 대해 적절한 방법이며, 페이지가 올라온 순서를 큐에 저장합니다.

- 단점:  중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리함. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.

 

2. OPT 알고리즘
- Optimal Page Replacement 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보낸다.

최적 페이지 교체는 선행 조건이 있는데, 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것입니다. 이 조건은 실제 활용에선 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘입니다. (때문에 연구를 목적으로 주로 사용됩니다.)

 

3. LRU 알고리즘
- Least-Recently-Used, 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘입니다.

- OPT 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법이며, OPT 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘 보다 효율적입니다.

- 단점: 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

 

• 👉🏻LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?
  • Cache Memory.
  • Cache Memory의 교체 알고리즘 캐시에 빈 공간이 없는 상태에서 새로운 내용이 메인 메모리로부터 캐시 메모리에 복사되어야 하는 상황에서 기존 적재되어 있던 내용 중 어떤 것을 내릴 것인가 결정하는 것이 필요하다. 이 또한 Cache의 성능과 관계가 있다. 이 교체 알고리즘이 필요한데, 이 교체 알고리즘에는 FIFO, LRU, LFU등이 있다.
  • 참조링크: https://wikidocs.net/65523
• 👉🏻LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?
  • LRU와 LRU Cache

 

4. LFU 알고리즘

- Least-Frequently-Used, 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘입니다.

- 만약 대상인 페이지가 여러 개 일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체합니다.

- 단점: 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생

 

 

5. MFU 알고리즘

- Most-Frequently-Used, LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.

 

*LFU와 MFU는 실제 사용에 잘 쓰이지 않는다고 합니다.
왜냐하면, 구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문입니다.

• 👉🏻MFU MRU 의 가치?
  
  • MRU?
• 👉🏻Clock / Second chance
  
  • Second-Chance(Clock) 알고리즘은 기본적으로 FIFO 알고리즘에 기반을 둔다. 대신 페이지가 선택되었을 때 그 페이지를 교체하지 않고, 그 페이지의 참조 비트를 본다.
  • 참고링크: https://www.geeksforgeeks.org/second-chance-or-clock-page-replacement-policy/