운영체제 - 가상메모리(2)

2020-10-29

OS를 공부하면서 정리를 한 내용들 입니다.

지난 가상메모리 챕터에서는 관리에서 Optimal Algorithm에 대해서 공부했었습니다.

“미래에 일어나는 경우를 알고 있는 상황”이라는 전제가 붙어있기에 이상적 입니다.

실제 시스템에서 사용가능한 “미래를 모르는 상황에서 사용하는 알고리즘들”을 알아봅니다.

FIFO Algorithm

이 알고리즘은 First In First Out으로 운영이 됩니다.

즉 메모리에 먼저 들어온 페이지를 쫓아내는 방식이라는 것 입니다.

출처

위 그림은 동일한 페이지 레퍼런스 스트링에 대해서

메모리에 페이지 프레임이 3개인 경우와 4개인 경우의 FIFO 알고리즘으로 페이지 운영을 해본 것 입니다.

이 알고리즘은 특이한 성질이 하나 있습니다.

메모리상에서 프레임이 3개에서 4개로 늘려주면 보통은 성능이 좋아져야 합니다.

그러나 성능이 더 나빠지는(Page Fault가 늘어나는) 현상이 발생할 수 있습니다.

이 현상을 FIFO Anomaly(= Belady’s Anomaly)라고도 합니다.

LRU Algorithm

이 알고리즘은 Least Recently Used의 준말 입니다.

가장 덜 최근에 사용된(제일 오래전에 사용되었던) 페이지를 쫓아내는 알고리즘 입니다.

FIFO 알고리즘과의 차이는 먼저 들어왔지만 재사용이 된다면 최근에 사용된 것이기에 쫓아내지 않습니다.

출처

  • LRU의 시간 복잡도 : O(1) Complexity

LFU Algorithm

이 알고리즘은 Least Frequently Used의 준말입니다.

가장 덜 빈번하게 사용된 페이지를 메모리에서 쫓아내는 것입니다.

만약 최저참조 횟수인 page가 여럿인 경우에는?

  • LFU알고리즘 자체에서는 여러 page 중 임의로 선정합니다.

  • 성능 향상을 위해 가장 오래전에 참조된 page를 지우게 구현할 수도 있습니다.

장단점

  • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에
    page의 인기도를 좀 더 정확히 반영할 수 있습니다.

  • 참조 시점의 최근성을 반영하지 못합니다.

  • LRU보다 구현이 복잡합니다.

  • LFU의 시간 복잡도 : O(log n) Complexity

다양한 캐슁 환경

캐슁 기법

  • 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식

  • paging system 외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용됩니다.

캐쉬 운영의 시간 제약

  • 교체 알고리즘에서는 삭제할 항목을 결정하는 일에 지나치게 시간이 많이 걸리는 경우 실제 시스템에서 사용이 불가합니다.

  • Buffer caching이나 Web caching의 경우
    • O(1)에서 O(log n)정도까지 허용
  • Paging System인 경우
    • page fault인 경우에만 OS가 관여함
    • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
    • O(1)인 LRU의 list 조작조차 불가능

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의