Page Replacement Algorithms

페이지 교체 알고리즘

 

페이지 교체 알고리즘(Page Replacement Algorithm)은 가상 메모리를 사용하는 운영체제에서 메모리에 적재된 페이지(Page) 중 일부를 다른 페이지로 교체하는 방법을 결정하는 알고리즘 입니다.

 

운영체제에서는 물리적인 메모리(RAM) 크기보다 큰 프로세스를 실행하기 위해 가상 메모리를 사용합니다.

가상 메모리는 디스크의 일부를 논리적인 메모리로 사용하는 것입니다.

이때, 실제 메모리보다 큰 용량을 가진 가상 메모리에서 프로세스가 실행될 때

페이지(Page) 단위로 분할되어 메모리에 적재됩니다.

 

메모리에 적재된 페이지가 모두 사용 중 일 때 새로운 페이지를 적재하려면 기존의 페이지 중 어느 페이지를

교체해야 할지 결정해야 합니다. 이때 사용되는 것이 페이지 교체 알고리즘 입니다.

 

---

• FIFO(First-In, First-Out)
  • FIFO 알고리즘은 가장 간단한 페이지 교체 알고리즘 중 하나입니다.
    이 알고리즘은 메모리에 적재된 페이지 중에서 가장 먼저 들어온 페이지를 교체하는 방식으로 동작합니다.
    
    예를 들어, 메모리에는 페이지 1, 2, 3이 적재되어 있습니다.
    이후 새로운 페이지가 4가 요청되면 메모리에서 가장 먼저 적재된 1을 교체합니다.
    이때, 페이지 1이 가장 오래된 페이지 이므로 'First-In'에 해당합니다.
    그리고 새로운 페이지 4는 메모리에 적재됩니다.
    
    FIFO 알고리즘은 구현이 간단하고, 페이지 부재(Page Fault) 발생 시간이 빠른 것이 장점입니다.
    하지만 페이지를 교체할 때 페이지의 사용 여부를 고려하지 않기 때문에,
    사용 빈도가 낮은 페이지가 계속해서 메모리에 적재되는 문제가 있습니다.
    
    이러한 문제로 인해 최근에는 LRU(Leat Recently Used) 알고리즘이
    보다 효율적인 페이지 교체 알고리즘으로 사용되고 있습니다.
    
    
    

• LRU(Least Recently Used)
  • LRU 알고리즘은 가장 최근에 사용되지 않은 페이지를 교체하는 알고리즘 입니다.
    
    LRU 알고리즘은 각 데이터가 마지막으로 사용된 시간을 추적하고,
    메로기 공간이 부족해 질 때, 가장 오래 전에 사용된 데이터부터 삭제합니다.
    
    이렇게 함으로써, 가장 최근에 사용된 데이터는 보존되며, 가장 오래된 데이터는 삭제됩니다.
    메모리에 적재된 페이지 중에서, 가장 오래 전에 사용된 페이지를 교체하는 방식으로 동작합니다.
    이를 위해서 운영체제는 각 페이지의 사용 시간을 추적하며, 가장 오래 전에 사용된 페이지를 찾아 교체합니다.

 

• LFU (Least Frequently Used)
  • LFU 알고리즘은 가장 적게 사용된 데이터를 우선적으로 삭제하는 방식으로 동작합니다.
    LFU 알고리즘은 각 데이터가 사용된 횟수를 추적하고,
    메모리 공간이 부족해질 때, 가장 적게 사용된 데이터부터 삭제합니다.
    이렇게 함으로써, 가장 적게 사용된 데이터는 삭제되며, 자주 사용되는 데이터는 보존되게 됩니다.
    
    LFU 알고리즘은 LRU 알고리즘과 비교하여 자주 사용되는 데이터가 많은 경우에 더 효율적입니다.
    그러나 자주 사용되는 데이터와 드물게 사용되는 데이터의 차이가 크지 않은 경우에는 성능이 좋지 않을 수 있습니다.
    
    
    
• OPT(Optimal Replacement)
  • OPT 교체전략은 현재 시점에서 미래에 사용되지 않을 데이터를 우선적으로 삭제하는 방식으로 동작합니다.
    각 데이터가 미래에 언제 사용될지를 미리 예측하고, 메모리 공간이 부족해 질 때,
    가장 나중에 사용될 데이터부터 삭제합니다. 이렇게 함으로써 현재 시점에서 사용하지 않을 데이터를
    우선적으로 삭제하여 메모리 공간을 확보합니다.
    
    
• NUR(Not Used Recently)
  • NUR 알고리즘은 최근에 사용되지 않은 데이터를 우선적으로 삭제하는 방식으로 동작합니다.
    NUR 알고리즘은 각 데이터가 최근에 사용되었는지 여부를 추적하고, 메모리 공간이 부족해 질 때
    사용되지 않은 데이터부터 삭제합니다. 이렇게 함으로써 최근에 사용되지 않은 데이터를 우선적으로
    삭제하여 메모리 공간을 확보합니다.
    
    
• SCR(Second Chance Replacement)
  • SCR 알고리즘은 NUR 알고리즘과 유사한 방식으로 동작하지만 삭제할 데이터를 찾을 때 사용되는 방식이
    다릅니다. SCR 알고리즘은 사용되지 않은 데이터 중에서도 참조 비트(reference bit)가 0인 데이터를
    우선적으로 삭제하지 않고, 참조 비트가 1인 데이터를 찾아서 삭제합니다. 이후에는 삭제한 데이터의
    참조 비트를 0으로 초기화합니다. 이렇게 함으로써 최근에 참조된 데이터가 삭제되지 않고 메모리에 보존될
    가능성이 높아집니다.

 

#Ref

Operating System - Virtual Memory