운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

목차

페이지 교체 알고리즘 (Page Replacement Algorithm)

• 페이지 교체 알고리즘이란 ?
• 페이지 교체 알고리즘의 종류  
  • OPT 알고리즘
  • FIFO 알고리즘
  • LRU 알고리즘
  • LFU 알고리즘
  • MFU 알고리즘  

LRU Cache

• 캐시 (Cache)
• LRU 알고리즘

페이지 교체 알고리즘 (Page Replacement Algorithm) 

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

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

즉, 필요한 페이지가 메모리에 없을 때 page-fault가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 한다. 만약 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다.

프레임: 물리 메모리를 일정한 크기로 나눈 블록
페이지: 가상 메모리를 일정한 크기로 나눈 블록

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

• OPT (Optimal) : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO (First In First Out) : 가장 오래된 페이지 교체
• LRU (Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지 교체 = 많은 운영체제가 채택하는 알고리즘
• LFU (Least Frequently Used) : 참조 횟수가 가장 적은 페이지 교체
• MFU (Most Frequently Used) : 참조 횟수가 가장 많은 페이지 교체
• NUR (Not Used Recently) : 최근에 사용하지 않은 페이지 교체

OPT 알고리즘

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다.
• Belady`s Anomaly 현상이 발생하지 않는다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야한다.
• 실제로 구현하기 거의 불가능한 알고리즘으로, 연구 목적을 위해 사용된다.

Bealady's Anomaly : 프레임의 개수가 많아져도 page-fault가 줄어들지 않고 늘어나는 현상

FIFO 알고리즘

• 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.
• 구현이 간단하고, 초기화 코드에 대해 적절한 방법이다.
• 성능은 좋지 않은 편이다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
• Belady`s Anomaly 현상이 발생할 수 있다.

LRU (Least Recently Used) 알고리즘

• 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.
• 최적 알고리즘과 비슷한 효과를 낼 수 있다.
• 최적 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘보다 효율적이다.
• 성능이 좋은 편이다.
• 많은 운영체제가 채택하는 알고리즘이다.

LFU (Least Frequently Used) 알고리즘

• 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.

• 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다.
• 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다.
• 초기에만 쓰인 7이 메모리에 잔존해 낭비가 일어난다.

MFU (Most Frequently Used)  알고리즘

• LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
• 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.

LFU와 MFU는 실제 잘 사용하지 않는다.
구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU만큼) 제대로 유사하게 구현하지 못하기 때문이다.

LRU Cache

캐시 (Cache)

캐시는 연산에 필요한 데이터, 값을 미리 갖다놓는 임시 메모리이다. CPU에서 주기억장치, 보조기억장치까지 도달하는 비용은 매우 크고, 물리적으로 거리가 멀다고 할 수 있다. 그런데 캐시의 경우 CPU 바로 옆에 딱 달라붙어있기 때문에 물리적으로도 거리가 매우 짧아 접근 비용이 매우 적다. 따라서 자주 사용되는 값이나, 사용될 예정인 값을 미리 캐시에 적재해놓는다면 참조 시간을 대폭 줄여 성능을 높일 수 있다.

CPU는 어떤 값이 필요할 때 가장 먼저 캐시를 방문하고 만약 캐시에 원하는 값이 있을 경우 이를 사용하는데, 만약 없다면 주기억 장치를 방문한다. 따라서, CPU 가 자주 사용하는 값, 필요로 하는 값 등을 적절히 캐시에 배치해두어야 한다. 즉, 캐시 히트율을 높여야 성능을 높일 수 있다.

Cache Hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우
Cache Miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

캐시의 내용물들은 자주 갈아끼워질 필요가 있다. 캐시의 용량은 한정적이지만 자주 사용되는 값 혹은 사용될 예정인 값은 시시각각 변하기 때문이다. 막무가내로 내용물을 갈아끼우면 캐시 히트율을 항상 높게 유지하기 어려울 것이고, 성능 악화로 이어질 수 있다. 따라서 캐시 히트율을 높게 유지하는 메모리 교체 알고리즘이 필요하다. Cache 알고리즘 중에 가장 유명한 알고리즘 중 하나는 LRU 알고리즘이다.

LRU 알고리즘

캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고, 새로운 데이터를 배치한다.

구현은 보통 LinkedList, Queue, ArrayList 등을 사용한다.

Reference

백트래킹 (Backtracking) 이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다.

일종의 트리 탐색 알고리즘이라고 봐도 된다.

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다.

보통 비선형으로 구성된 자료 구조를 깊이 우선 탐색(Depth First Search, DFS)할 때, 

더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정이다.

깊이 우선 탐색(DFS) VS 백트래킹(Backtracking)

DFS는 가능한 모든 경로를 탐색한다. (완전 탐색 O)

불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다.

백트래킹은 모든 경로 중 특정 조건을 만족하는 경로만 탐색한다. (완전 탐색 X)

유망성 (promising) VS 가지치기 (pruning)

불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미에서 '가지치기'라고도 한다.

가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

유망성을 판단했을 때,

해가 될 가능성이 있는 것은 promising, 유망하지 않은 노드에 가지 않는 것은 pruning ! 

주로 문제를 풀 때 DFS 등으로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 조건문으로 정의하고, 그러한 상황일 경우에는 탐색을 중지하고 그 이전으로 돌아가서 다시 다른 경우를 탐색하도록 구현한다. 

즉, 백트래킹은 최적화 문제와 결정 문제를 푸는 방법이 되고, 보통 재귀함수로 구현한다.

+ 탐색 알고리즘이란 ?

Reference