페이지 교체 알고리즘 - FIFO, LRU, LFU, MFU, NUR, OPT(오프라인 알고리즘)

2024. 10. 17. 11:50·Computer Science/Operating System
반응형

 

스와핑이 일어날 때 페이지 교체 알고리즘에 의해 페이지가 교체되게 된다.

 

FIFO (First In First Out) 

  • 방법 : 메모리에 가장 먼저 올라온 페이지를 먼저 내보냄.
  • 특징
    • 구현이 간단하고 직관적
    • 성능이 좋지 않을 수 있음. Belady의 역설(FIFO anomaly)이 발생할 수 있음.
      즉, 페이지 프레임 수가 늘어날 수록 페이지 부재가 증가할 수 있음

 

 

LRU (Least Recently Used)

  • 방법 : 가장 오랫동안 사용하지 않은 페이지를 교체
  • 특징
    • "가장 오랫동안 사용하지 않았다면 앞으로도 사용할 확률이 적을 것이다"라고 가정.
    • 자주 사용되는 페이지를 유지하므로 성능이 FIFO보다 상대적으로 좋음.
    • 프로세스가 주기억 장치에 접근할 때 참조된 페이지 시간을 기록해야 한함.
      -> 막대한 오버헤드가 발생할 수 있다.
      -> 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요하다.

 

 

LFU (Least Frequently Used)

  • 방법 : 사용 빈도가 가장 낮은 페이지를 교체
  • 특징
    • 자주 사용되지 않는 페이지를 제거하여 효율성을 높임. 장기적 시간 규모에서의 참조성향 고려.
    • 초기화 시점부터의 빈도를 기준으로 하기 때문에, 새로운 페이지가 불리.
    • 오래 전에 사용되었지만 최근에는 사용되지 않는 페이지가 남아 있을 수 있어 성능에 문제가 발생할 수 있음. 
    • 때문에 특정 상황에서만 효율적...

 

 

MFU (Most Frequently Used)

  • 방법 : 사용 빈도가 가장 높은 페이지를 교체
  • 특징
    • "가장 많이 사용된 페이지는 앞으로는 사용되지 않을 것이다" 라고 가정.
    • 오래된 페이지를 제거할 수 있음.
    • 실제로 자주 사용되는 페이지를 제거할 위험이 있어 성능이 저하될 수 있음.
    • LFU와 마찬가지로, 특정 상황에서만 효율적...

 

NUR / NRU (Not Recently Used) / Clock

먼저 0과 1을 가진 비트를 둠. 1은 최근에 참조되었고 0은 참조되지 않음을 의미. 만약 한 바퀴 도는 동안 사용되지 않으면 0이 됨.

  • 방법 : 최근에 사용되지 않은 페이지를 교체. 
  • 특징
    • 두 개의 비트(참조 비트/수정 비트)를 사용하여 페이지의 사용 상태를 추적.
    • 구현이 비교적 간단하며, 효과적인 경우가 많습니다.
    • 참조 비트와 수정 비트를 주기적으로 초기화해야 함.
    • LRU보다는 덜 정밀한 편...

 

 

오프라인 알고리즘 (OPT, Optiomal)

 

  • 방법 : 현재 메모리에 있는 페이지 중에서 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
  • 특징
    • "미래의 페이지 참조를 완벽히 예측할 수 있다"고 가정.
    • 페이지 부재를 최소화하는 가장 효율적인 알고리즘. 메모리 관리의 효율성 극대화.
    • 실제 시스템에서는 미래를 예측할 수 없어 구현할 수 없는 이론적인 알고리즘임.
    • 다른 페이지 교체 알고리즘의 성능을 평가하는 기준으로 사용됨.

 

 

더보기

 

 

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)

페이지 교체 알고리즘 (Page Replacement Algorithm) 이전 포스팅으로 요구 페이징(Demand Paging)에 대해 알아보았다. 필요한 페이지가 메모리에 없을 때 page-falut가 발생하고 Backing Store에서 해당 페이지를

code-lab1.tistory.com

 

 

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

💡 페이지 교체 알고리즘 운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기

doh-an.tistory.com

 

728x90
반응형

'Computer Science > Operating System' 카테고리의 다른 글

프로세스 메모리 구조, 프로세스/스레드 차이  (0) 2024.10.22
프로그램 컴파일 과정 - C, C++/Java ( Interpreter / JIT )  (0) 2024.10.18
가상메모리(2) - 페이지폴트와 스와핑, 스레싱  (1) 2024.10.16
가상메모리(1) - 페이지테이블, TLB  (0) 2024.10.16
시스템 콜(System Call), 사용자 모드(User mode), 커널 모드(Kernel mode), modebit  (4) 2024.10.05
'Computer Science/Operating System' 카테고리의 다른 글
  • 프로세스 메모리 구조, 프로세스/스레드 차이
  • 프로그램 컴파일 과정 - C, C++/Java ( Interpreter / JIT )
  • 가상메모리(2) - 페이지폴트와 스와핑, 스레싱
  • 가상메모리(1) - 페이지테이블, TLB
settong
settong
    250x250
  • settong
    개 발 자 국
    settong
  • 전체
    오늘
    어제
    • 전체보기 (202)
      • Computer Science (50)
        • Network (7)
        • Operating System (18)
        • Data Structure (9)
        • Database (11)
        • Algorithm (5)
      • Language (17)
        • Java (17)
        • Javascript (0)
        • Python (0)
      • Devops (20)
        • AWS (0)
        • Naver Cloud (16)
        • CICD (3)
        • 웹 서버 관리 (1)
      • Front (0)
        • React (0)
      • Backend (5)
        • Spring (5)
      • 코딩 테스트 정복기 (110)
        • 백준 (51)
        • 프로그래머스 (53)
        • 기타 (6)
      • etc (0)
      • 경제 상식 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    github actions
    Spring Boot
    프로그래머스
    분할정복
    해시
    BFS
    CI/CD
    다익스트라
    ncp202
    ncp200
    벨만포드
    lcs
    다이나믹프로그래밍
    백준
    백트래킹
    DFS
    완전탐색
    ncp
    Network
    집합
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
settong
페이지 교체 알고리즘 - FIFO, LRU, LFU, MFU, NUR, OPT(오프라인 알고리즘)
상단으로

티스토리툴바