티스토리 뷰
가상 메모리 관리자의 입장에서 비어 있는 메모리가 많을 수록 일은 쉬워진다. 페이지 폴트가 발생하면 빈 페이지 리스트에서 비어 있는 페이지를 찾아서 폴트를 일으킨 페이지에게 할당하면 된다.
만약 빈 메모리 공간이 없다면? 그런 경우 OS는 memory pressure을 해소하기 위해 다른 페이지들을 강제적으로 paging out하여 활발히 사용 중인 페이지들을 위한 공간을 확보한다.
evict(내보낼) page 선택은 os의 replacement policy안에 집약되어 있다.
replacement policy가 중요하다. 그렇다면 ↓
Q. How to decide which page to evict?
1. Cache Management
policy에 대해서 말하기 전에 문제에 대해 좀 더 상세하게 알아보자.
시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면→ 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 Cache로 생각될 수 있다.
이 Cache를 위한 replacement policy의 goal은 Cache miss의 횟수를 최소화하는 것이다. → 즉, disk로부터 page를 가져오는 횟수를 최소로 만드는 것.
한편으론 Cache Hit 횟수를 최대로하는 것도 Goal이라고 할 수 있다.→ 접근된 페이지가 메모리에 이미 존재하는 횟수를 최대로 하는 것
Cache Hit와 Cache Miss의 횟수를 안다면 프로그램의 average memory access time, AMAT을 계산할 수 있다.(컴퓨터 아키텍트가 하드웨어 캐시의 성능을 측정할 때 사용하는 미터법)
Ex) 어떤 컴퓨터가 4KB의 작은 메모리를 가지고 있고, 페이지의 크기는 256바이트라고 하자.
가상 주소는 4비트 VPN(최상위 비트)과 8비트 offset(최하위 비트)의 부분으로 구성된다. 그러므로 이 예제에서 한 프로세스가 2^4 또는 총 16개의 가상 페이지들에 접근할 수 있다.
프로세스는 가상 주소 0x000, 0x100, 0x200, 0x300, 0x400, 0x500, 0x600, 0x700, 0x800, 0x900의 메모리를 가리키고 있다. 이 가상 주소들은 주소 공간의 첫 10개 페이지들의 첫 번째 바이트를 나타낸다.
가상 페이지 3을 제외한 모든 페이지가 이미 메모리에 있다고 가정하면 주어진 순서의 메모리 참조는 히트 히트 히트 미스 히트 히트 히트 히트 히트 히트된다 . hit reat을 계산하면 90%가 된다.
The Optimal Replacement Policy
Optimal Replacement plicy와 비교하면 Replacement Policy 동작을 잘 이해할 수 있다. 이 policy는 miss를 최소화한다. 간단하지만 구현하기 어려운 정책이다.
좀 더 생각해보자. 만약 페이지 하나를 Evict한다면 지금부터 가장 먼 시점에 필요하게 될 페이지를 버리는 것이 좋지 않을까? 핵심은 가장 먼 시점에 필요한 페이지보다 Cache에 존재하는 다른 페이지들이 더 중요하다는 것이다.
Ex) 프로그램이 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1의 순서대로 가상 페이지들을 접근한다고 가정하자.
Cache에 3개의 페이지를 저장할 수 있다고 가정할 때 아래 그림은 최적의 기법의 동작을 보여준다.
- 말로 설명하기그러면 어떤 페이지를 교체해야할까? optimal replacement policy의 경우 현재 load된 페이지 0,1,2의 미래를 살펴본다. 0은 거의 즉시 접근될 것이고, 1은 약간 후에, 그리고 2는 가장 먼 미래에 접근이 될 것이라는 것을 알 수 있다. 그러므로 optimal policy는 쉬운 선택을 한다. 페이지 2를 Evict한다. 결과적으로 0,1,3이 남게 된다. 그후에 세번의 참조는 Hit가 된다. 그 다음 페이지 2를 만나서 또 한번의 Miss를 만난다. 여기서 한번 각 페이지의 미래를 검사하고 페이지 1만 아니면(바로 다음에 접근 될 예정이라) 어느 페이지를 내보내도 괜찮다는 것을 알게 된다. 이 예제에서는 페이지 3을 내보냈다. 최종적으로 페이지 1을 히트되고 종료된다.
캐시의 히트율을 계산할 수 있다. 캐시 히트가 6번의 미스가 5번이었으므로 히트율은 6/(6+5)또는 54.5%가 된다. 강제 미스을 제외한 히트율을 계산하면 85.7% 히트율을 얻는다.
불행하게도 스케줄링 정책을 만들 때도 보았는데 미래는 일반적으로 알 수 없다. → 그렇기 때문에 범용 OS는 Optimal policy의 구현은 불가능하다. - Cache는 처음에 비어 있는 상태로 시작하기 때문에 첫 3번의 접근은 Miss다. 이러한 종류의 Miss는 cold-start miss 또는 compulsory miss라고한다. 그 다음에 페이지 0과 1을 참조하면 cahce에서 hit된다. 마지막으로 또 다른 miss를 만나게 된다.
이 때 Cache가 가득 차 있어서 replacement poliy 를 실행해야한다.
| Scheduling에서처럼 여러가지 Policy가 등장한다. |A Simple Policy: FIFO
복잡한 구현은 때려치고 매우 간단한 replacement policy을 채용하였다. 예를 들면, 일부 시스템에서는 FIFO replacement policy을 사용하였다. 이 방법은 시스템에 페이지가 들어오면 큐에 삽입되고, 교체를 해야 할 경우 큐의 꼬리에 있는 페이지가 내보내진다. 매우 간단하다 😆
이제 위 이미지의 예제를 살펴보자.
처음에는 마찬가지로 0, 1, 2에 대한 3개의 cold-start miss로 시작한다. 그 이후 0과 1이 다음에 HIT된다. 페이지 3이 참조되지만 Miss를 일으킨다. FIFO를 사용할 때 교체 결정은 쉽다. 순서상 첫 번째로 드러온 0을 선택하면 된다. 그다음 참조 페이지가 0이라 또 Miss가 발생하고 그 다음 페이지 1을 버린다. 간단하지만 성능이 안 좋다 히트율이 36.4%가 된다. 강제 미스를 제외하면 57.1%가 된다. FIFO는 블럭들의 중요도를 판단할 수가 없다.
Another Simple Policy: Random
항상 이런 식이었어 알고리즘.. 항상 잘 안되면 Random을 찾더라...
구현하기 쉽다. 중요도를 판단하지 못하니까 랜덤으로 버리는 것이다. ㅋㅋㅋㅋ 상당히 유쾌 흑쾌 운이 좋으면 한번도 쓸데 없는 Miss가 발생하지 않을 것이니까 운이 안 좋으면 최악이 나타날 것이다.
일반적인 성능을 알아보기 위해 수천번 반복해볼 수 있다. 만번을 수행했을 때 몇번의 Hit를 얻어냈는지를 나타낸다. 어떤 때는 40%가 살짝 넘는 경우들이 optimal 기법만큼 좋은 성능을 보이며 예제에서 6번 Hit를 얻었다. 때로는 안 좋은 성능을 보여주기도 한다. 동작은 그때 그때마다 달라진다.
Using History: LRU
위 예는 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1 → Hit ratio: 54.5%
스케줄링 정책에서와 같이 미래에 대한 예측 위해서 과거 사용 이력을 활용해보자. 예를 들어 어떤 프로그램이 가까운 과거에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 접근하게 될 확률이 높다고 생각하는 것이다. → frequency
페이지 교체 정책이 활용할 수 있는 과거 정보 중 하나는 frequency이다. 만약 한 페이지가 여러 차례 접근되었다면, 분명히 어떤 가치가 있기 때문에 교체되면 안 될 것이다.
좀 더 자주 사용되는 페이지의 특징은 접근의 recency(최근성)이다. 더 최근에 접근된 페이지일 수록 가까운 미래에 접근될 확률이 높을 것이다.
이러한 류의 정책은 principle of loacality이라고 부르는 특성에 기반을 둔다.
→ 이 원칙은 프로그램의 행동 양식을 관찰하여 얻은 결과이다. 이 원칙이 말하는 것은 단순하다.
프로그램들은 특정 코드들과 자료 구조를 상당히 빈번하게 접근하는 경향이 있다는 것이다. → 코드의 예로는 반복문 코드를 들 수 있으며, 자료 구조로는 그 반복문에 의해 접근되는 배열을 예로 들 수 있다.
과거의 현상을 보고 어떤 페이지들이 중요한지 판단하고, 내보낼 페이지를 선택할 때 중요한 페이지들은 메모리에 보존하는 것이다. 그리하여 과거 이력에 기반한 교체 알고리즘 부류가 탄생하게 되었다.
Least-Frequently-Used(LFU) 정책은 가장 적은 빈도로 사용된 페이지를 교체한다.
Least-Recently-Used(LRU) 정책은 가장 오래 전에 사용하였던 페이지를 교체한다.
이러한 알고리즘들은 기억하기 쉽다. 이름을 알면 정확하게 그 알고리즘이 어떻게 동작하는지 알 수 있다. 이름이 가지는 탁월한 성질이 아닐 수 없다.
Locality
Temporal locality
이것은 최근에 사용된 데이터나 명령이 다시 사용될 확률이 높다는 뜻입니다. 왜냐하면 프로그램엔 loop문(반복문)이 있기 때문에, 그 안의 코드는 여러 번 사용될 확률이 높은 것이지요,
예: 순환, sub program, stack 등
Spatical locality
특정 클레스터의 기억 장소들에대해 참조가 집중적으로 이루어지는 경향.
프로그램 실행시 접근하는 메모리의 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현.
Sequential processing, Array 등등.