CS/운영체제

[운영체제] 페이지 교체 알고리즘

ummchicken 2023. 2. 5. 00:04

✔️ 페이지 교체 알고리즘이란?

페이징 기법으로 메모리를 관리하는 운영체제에서,
페이지 부재가 발생하여 새로운 페이지를 할당하기 위해
현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.

 

  • 메모리는 한정되어 있기 때문에 스와핑이 많이 일어난다. 따라서 스와핑은 많이 일어나지 않도록 설계되어야 하며, 이는 페이지 교체 알고리즘을 기반으로 스와핑이 일어난다.
  • 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나, 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다.
  • 빈 페이지가 없는 상황에서, 메모리에 적재된 페이지와 적재할 페이지를 교체함으로써 페이지 부재 문제를 해결할 수 있다.
  • 페이지 교체 알고리즘은 '온라인 알고리즘'이다.

 

※ 온라인 알고리즘

시작할 때 모든 입력 정보를 가지고 있지 않고,
입력을 차례로 받아들이면서 처리하는 알고리즘을 말한다.

 

※ 오프라인 알고리즘

풀고자 하는 문제의 모든 데이터를 가지고 시작해야만 문제를 해결할 수 있다.

따라서 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘이며, 가장 좋은 방법이다.
그러나 미래에 사용되는 프로세스를 우리가 알 수 있을까? 알 수 없다.

즉, 사용할 수 없는 알고리즘이지만 가장 좋은 알고리즘이기 때문에 
다른 알고리즘과의 성능 비교에 대한 상한기준(upper_bound)을 제공한다.

 

 

 

✔️ 페이지 교체 알고리즘의 목표

Page-fault(페이지 부재) 발생 비용을 줄이는 것이다.

 

 

 

페이지 교체 알고리즘의 종류를 알아보자.

 

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

종류 알고리즘 특징
간단한 알고리즘 무작위 무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다.
  FIFO 처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다.
이론적 알고리즘 Optimal 미래의 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.
최적 근접 알고리즘 LRU 시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다.
  LFU 사용 빈도가 적은 페이지를 스왑 영역으로 보낸다.
  NUR 최근에 사용한 적이 없는 페이지를 스왑 영역으로 보낸다.
  FIFO 변형 FIFO 알고리즘을 번형하여 성능을 높인다.

 

 

이제 자세히 알아보자.

 

 

 

✔️ FIFO (First In First Out) 알고리즘

가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법이다.

 

FIFO 알고리즘

 

  • 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.
  • 구현이 간단하지만, 성능은 좋지 않은 편이다.
  • 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
  • Belady's Anomaly 현상이 나타날 수 있다.

 

※ Belady's Anomaly란?

Belady's Anomaly

Belady's Anomaly란 프레임의 개수가 많아져도 page-fault가 되려 페이지 부재가 더 많이 발생하는 모순이 존재하는 것이다.

직관적으로 생각해보면, 프레임의 개수가 많아지면 pagt-fault가 줄어들어야 할텐데, 
FIFO 알고리즘을 사용하면 그렇지 않을 수 있다.

 

 

 

 

✔️ LRU (Least Recently Used) 알고리즘 (⭐)

참조가 가장 오래된 페이지를 바꾸는 것이다.

 

LRU 알고리즘

 

  • 가장 오랫동안 사용하니 않은 페이지를 교체하는 알고리즘이다.
  • 시간 지역성 성질 고려 : 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성 높음
  • 최적 알고리즘과 비슷한 효과를 낼 수 있다.
  • 성능이 좋은 편이다.
  • 💡 많은 운영체제가 채택하는 알고리즘이다.
  • 🚨 '오래된' 것을 파악하기 위해, 각 페이지마다 계수기, 스택을 두어야 하는 문제점이 있다.
    • 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로, 막대한 오버헤드가 발생

 

 

LRU를 프로그래밍으로 구현할 때는 보통 두 개의 자료구조로 구현한다.

→ 바로 해시 테이블과 이중 연결 리스트이다.

→ 해시 테이블 : 이중 연결 리스트에서 빠르게 찾을 수 있도록 함

→ 이중 연결 리스트 : 한정된 메모리를 나타냄

 

 

 

 

✔️ NUR (Not Used Recently) or NRU (Not Recently Used)

LRU에서 발전한 알고리즘이다.

 

NUR 알고리즘

 

  • clock(클럭) 알고리즘이라고도 한다.
  • 기존(LRU, LFU) 알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식이다.

 

 

클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.

  1. 프레임 내의 페이지가 참조될 때, 하드웨어에 의해 1로 자동 세팅 된다.
  2. 클럭 알고리즘은 한 바퀴 돌며, 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
  3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.
  4. 교체한 부분을 1로 바꾼다.

 

즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 

다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 

교체 대상 페이지로 선정하는 알고리즘이다.

 

 

클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다.

때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.

 

 

 

 

✔️ LFU (Leat Frequently Used) 알고리즘

가장 참조 횟수가 적은 페이지를 교체하는 방법이다.

즉, 많이 사용되지 않은 것을 교체하는 것이다.

 

LFU 알고리즘

 

  • 교체 대상이 여러 개라면, 가장 오랫동안 사용하지 않은 페이지를 교체한다.
  • LFU 알고리즘은 크게 2가지로 나뉜다.
    • Incache-LFU : 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
    • Perfect-LFU : 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식 (Perfect-LFU의 경우 정확하게 참조 횟수를 참조할 수 있지만 시간에 따른 참조의 변화를 반영하지 못하고, 구현이 복잡하다는 단점이 있다.)

 

 

 

 

✔️ MFU (Most Frequency Used) 알고리즘

LFU와 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

 

MFU 알고리즘

 

  • 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에, 앞으로도 사용될 가능성이 높다는 판단이다.
  • 하지만 LFU와 MFU는 실제 사용에 잘 쓰지 않는다.
    • 구현에 상당한 비용이 들고,
    • 최적 페이지 교체 정책(Optimal)을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문이다.

 

 

 

 

 

출처

 

 

 

 

 

저작자표시 비영리 변경금지

'CS > 운영체제' 카테고리의 다른 글

[운영체제] 메모리 관리, 페이징 & 세그멘테이션  (0) 2023.02.04
[운영체제] 메모리 계층 구조  (1) 2023.02.04
[운영체제] 세마포어(Semaphore) & 뮤텍스(Mutex)  (1) 2023.02.03
[운영체제] 동기화(Synchronization)와 경쟁상태(Race Condition), 임계영역(Critical Section)  (0) 2023.02.02
[운영체제] 데드락 (DeadLock, 교착 상태)  (0) 2023.02.01

'CS/운영체제'의 다른글

  • 현재글[운영체제] 페이지 교체 알고리즘

관련글

댓글

티스토리툴바