> For the complete documentation index, see [llms.txt](https://real-dev.gitbook.io/real-library/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://real-dev.gitbook.io/real-library/os_with_joonion/22-..md).

# 22강. 페이지 교체 알고리즘

#### 페이지를 로딩해야하는데 빈 프레임이 없다면…?

* 신규 프로세스를 로딩해야하는데 남는 프레임이 없거나, 버퍼를 사용하는 프로그램이 실행되거나 하는 경우에 어떻게든 메모리 공간을 만들어야 한다.
* 그럼 `프레임을 차지하고 있는 페이지에서 어떤것을 내릴 것인지(victim frame)를 정하는 방식`이 바로 **페이지 교체 알고리즘**이다.
* 페이지 교체 알고리즘의 성능이 조금만 좋아지더라도 \*\*Page fault의 빈도가 줄어들고 \*\*이건 시스템에 큰 이점으로 돌아온다. 즉, 효율이 좋다.

<br>

### 페이지 교체 알고리즘의 종류

#### FIFO

* 가장 오래된 페이지를 쫓아낸다. 가장 단순한 접근지만 페이지 폴트가 상대적으로 많이 발생한다.
* `Belady’s Anomaly`: frame의 갯수가 증가할수록 Page fault 빈도가 오히려 늘어나는 이상 현상. frame갯수가 많을수록 page fault가 적게 발생하는 것이 일반적이었는데 FIFO에선 이상 현상이 발생한다.
  * 즉, 효율적인 알고리즘은 Belady 이상현상이 발생하지 않는다.
  * 결과적으로 좋은 페이징 교체 알고리즘은 **앞으로 쓸 일이 없을 것으로 예상되는 페이지를 가장 먼저 내쫓는 방식**이 된다.

<br>

#### Optimal Algorithm

* 실제로 존재하지 않는 가장 이상적인 알고리즘.
* 구현은 불가능하며, 알고리즘의 효율성을 판단하기 위한 목표치로 사용된다.

<br>

#### LRU (Least Recently Used)

* **가장 오랫동안 사용되지 않은 페이지를 메모리에서 빼는 방식**
* 참조 지역성을 근거로 생각해보면 참조된지 오래된 데이터가 앞으로도 사용될 가능성이 더 낮다.
* 때문에 페이지 마다 가장 마지막으로 사용된 시점을 기록해두고 있어야 한다. 메모리 용량 부분에서 좀 낮다.
* 성능도 좋고 자주 사용되지만, 공간을 많이 사용하고, 하드웨어 지원이 필요하지만 쉽지 않다. 때문에 카운터를 사용하거나, 스택(~~근데 스택 구조가 아님 뭔데 이게~~)을 활용하여 공간적 효율을 좀 높이기도 한다.
* 때문에 하드웨어 단위에서 지원하기 위해 reference-bit를 둬서 해당 비트의 값이 가장 작은 놈이 victim 후보가 된다.

<br>

#### Second Chance Algorithm

* FIFO를 사용하기는 하지만 reference bit를 사용하여 그야말로 목숨을 부여하는 방식
* LRU를 흉내내는 방식. 이게 뭐가 좋아서 방식이 되는걸까…

<br>

### 프레임 분배 문제

* **N개의 프로세스에 대해서 각각 몇 개의 프레임을 배정해줄 것인가?**
* 모든 프로세스에 동일한 프레임을 배정하기 VS 작업량만큼 유동적으로 프레임을 배정하기
* 전역적으로 배정하기 VS 지역적으로 배정하기
  * OS 단위에서 선출하기 VS 배정받은 프레임 안에서만 victim을 선출하기

<br>

#### Thrasing

* 페이지 스와핑의 비율이 너무 높아서 제대로 일을 못하는 경우를 의미한다.
* 하드웨어 사양에 비해 너무 많은 프로세스가 실행되고 있을 때 발생한다.