[OS] - Paging Algorithm

Paging Change Algorithm

---

요청하는 Page가 Main Memory에 없다면(Page Fault) -> 새로운 Page 할당 -> 할당된 Page 중에서 어떤 것을 Main Memory에서 내려서 사용할 것인가?

 

• Virtual Memory는 필요한 Page만 Memory에 적재한다.
• 그럼에도 Main Memory가 가득 찰 수 있다.
• 가득차게 된다면 안쓰는 Page는 Out 하고 요청한 Page를 In해야 한다.
• 이 때 Page Out되는 Page를 Victim Page라고 하며, 수정이 되지 않은 Page를 우선으로 하여 Page Out한다. ( 수정되면 Disk 작업이 필요하다 )

 

Page Reference String

• Cpu는 Logical Address를 통해 특정 Address를 요구한다.
• Main Memory의 Address들은 Page 단위로 가져오기 때문에 번호가 연속되어도 결함이 없다.
• Processor(CPU) Address request에 따라 Page이 결함이 일어나지 않는 부분이 생략되는 것을 의미한다.

# Example
CPU 주소              = {100, 101, 102, 432, 612, 103, 104, 611, 612}
Page 번호             = {1, 1, 1, 4, 6, 1, 1, 6, 6}
Page reference string = {1, 4, 6, 1, 6}

 

Page Change Algorithm

1. FIFO ( First In First Out )

• Victim = 먼저 들어온 Page를 Out
• 간단하면서 초기화 코드에서 적절하다.
• 초기화 코드란 Process가 처음 실행될 때, 초기화 시키는 역할만 진행하고 다른 역할이 없는 Process임으로 Main Memory에 없어도 괜찮은 코드

 

2. OPT ( Optimal Page Replacement )

• 앞으로 가장 사용하지 않은 Page를 우선적으로 내보낸다.
• FIFO에 비해 Page Fault를 많이 낮추어 준다.
• 앞으로 사용하지 않을 Page를 예측은 어떻게 할 것이며, 예측하더라도 실제와 다를 가능성이 높다.

 

3. LRU ( Least Recently Used )

• 최근에 사용되지 않은 Page를 내보낸다.
• 가정 : 최근에 사용하지 않으면 이후에도 사용하지 않는다.
• OPT보다 Page Fault가 발생하지만, 현실적이고 실제로 사용 가능한 Algorithm

 

교체 방식

1. Global

• Memory 상의 모든 Process의 Page를 Out 가능
• Trashing = Memory 상에 올라온 Process가 늘어날 수록 CPU의 이용량이 증가하지만, 특정 구간을 넘어서면 많은 Page Fault를 발생시켜 CPU 이용률이 감소하고 빈버한 Swap in/Swap Out이 발생한다.

 

2. Local

• Memory 상의 자신의 Process에서만 Page Out 가능