가상 메모리 - 페이지 교체 알고리즘

페이지 교체 알고리즘

---

가상 메모리란 프로세스를 실행할 때 실행에 필요한 일부(페이지)만 메모리에 로드하고 나머지는 디스크에 둠으로써 컴퓨터가 실제로 이용 가능한 메모리 자원을 매우 큰 메모리로 보이게 만드는 기법입니다.

 

 

https://kdgdev.tistory.com/18

자세한 내용은 위 링크에 있습니다.

 

핵심은 프로세스의 전부를 메모리에 올려 두는 게 아닌 프로세스를 페이지로 나누어 필요한 페이지만 메모리에 올려놓는 것입니다.

 

 

여기서 사용하지 않는 페이지는 보조기억장치에 보관해 두었다가 필요할 때 주기억장치에 올려놓는 것이 가상메모리가 사용하는 '스와핑'이란 기법입니다.

 

 

자, 그런데 여기서 가상메모리에서 '스와핑'은 많이 일어나서는 안됩니다.

 

 

CPU에서 필요한 페이지 요청 -> TLB확인 -> 주기억장치 접근 -> 주기억장치에 필요한 페이지가 없는 것을 확인 -> 보조기억장치에 접근 -> 주기억장치에 해당 페이지를 적재 후 Page Table, TLB 갱신 -> 다시 CPU에서 필요한 페이지 요청

 

 

이런 긴 과정을 거쳐야 하기 때문입니다. 따라서 자주 사용될만한 페이지들을 미리 메모리에 올려 두는 것이 컴퓨터의 성능을 올릴 수 있는 방법입니다.

 

 

페이지 교체 알고리즘

따라서 스와핑은 스와핑이 적게 일어날 수 있게 페이지 교체 알고리즘을 통해 일어납니다.

 

방법들은 다음과 같습니다.

 

• 최적 페이지 교체 알고리즘
  • 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘입니다.
  • 가장 좋은 방법이지만 미래에 사용될 프로세스를 우리가 알 수 없으므로 사용할 수 없는 알고리즘입니다.
  • 대신 다른 알고리즘과의 성능 비교에 대한 기준을 제공합니다.
• FIFO(First in First Out)
  • 가장 먼저 온(오래된) 페이지를 교체합니다.
• LRU(Least Recently Used)
  • 참조가 가장 오래된 페이지를 바꿉니다.
  • ‘오래된’ 것을 파악하기 위해 각 페이지마다 계수기, 스택 같은 별도의 하드웨어를 두어야 하고, 프로세스가 주기억장치에 접근할 때마다 페이지 시간을 기록해야 한다는 문제점이 있습니다.
• NRU(Not Recently Used)
  • 최근에 참조되지 않은 페이지를 대상으로 선정합니다. LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않습니다.
  • 참조비트와 변형비트를 두어 (0, 0) → (0, 1) → (1, 0) → (1, 1) 순의 우선순위를 가지고 페이지를 교체합니다.
  • 모든 페이지는 (0, 0)에서 시작하며 페이지가 변형되면 (0, 1), 참조되면 (1, 0), 참조와 변형이 둘 다 일어났으면
    (1, 1)이 됩니다. 모든 페이지가 (1, 1)이 되면 초기화됩니다.
• LFU(Latest Frequently Used)
  • 가장 참조 횟수가 적은 페이지를 교체합니다.
  • 가장 최근에 불러온 페이지가 교체될 수 있고 구현이 복잡합니다.
• Clock 알고리즘
  • 시계 방향으로 돌면서 참조비트가 0인 페이지를 찾고 그 순간 해당 프로세스를 교체하는 알고리즘입니다.
  • 참조가 된 페이지는 참조 비트를 1로 두며 모든 참조비트는 한 바퀴가 돌면 주기적으로 0으로 변경합니다.
• Second chance 알고리즘
  • FIFO의 방법을 따르나 참조비트를 두어 큐에 맨 앞 페이지가 참조비트가 1일 경우 참조비트를 0으로 하고 큐에 맨 뒤로 보냅니다.
  • 참조비트가 0이었을 경우 교체합니다.

 

 

※ 잘못된 정보, 혹은 다른 의견이 있다면 댓글로 말해주세요. 감사합니다.