저번 포스트에선 Page Fault에 대해 공부했는데 이번 글에는 Page Fault를 최대한 줄이기 위한 메모리 관리 기법들에 대해 알아보려고 한다.
메모리 지역성
프로그램은 아무 메모리나 무작위로 접근하는 게 아니라, 일정 시간 동안 특정 영역을 집중적으로 사용하는 경향이 있다.
- 시간 지역성 : 최근에 사용된 데이터를 다시 사용할 가능성이 높음.
- 변수나 상수는 프로그램 실행 도중 여러 번 반복해서 사용함.
- 공간 지역성 : 접근한 주소 근처의 주소를 곧 사용할 가능성이 높음.
for i in range(100): arr[i] += 1이런 반복문은 연속된 메모리 영역을 반복적으로 접근하니까 공간 지역성이 강함.
시스템은 메모리 지역성 정책에 따라 특정 영역의 데이터도 함께 캐시 공간에 저장한다.
최신 시스템에서 CPU캐시와 메인 메모리 사이의 속도 차이가 크기 때문에 메모리 지역성을 고려한 프로그래밍은 시스템 성능 향상에 큰 영향을 준다.
게다가 디스크 드라이브와 메모리 또한 큰 속도 차이를 가지고 있기 때문에 메모리 지역성이 없다면 Page Fault가 빈번히 일어날 것이고, 디스크에서 데이터를 읽는 횟수가 많아지게 되면서 시스템 성능이 현저히 느려질 것이다.
하지만 L1부터 L3, 그리고 물리 메모리 모두 공간이 무한하지 않기 때문에 페이지를 관리하는 것 또한 중요하다.
Page Replacement
MMU가 페이지 테이블을 확인했을 때, Valid bit를 확인하여 페이지가 메모리에 적재되어 있는지 판단한다.
Valid bit가 0이면 Page Fault가 발생하고 OS는 비어 있는 페이지를 메모리 Frame에 올린다.
이 때 메모리에 비어 있는 프레임이 없다면 어떻게 될까?
메모리는 무한한 자원이 아니기 때문에 기존에 적재된 페이지들을 삭제해야 한다.
그런데 나중에 또 접근할 페이지를 삭제해버리면 또다시 Page Fault가 발생하겠고, 그러면 속도가 느려질 수 밖에 없다.
어떤 페이지를 삭제하고 올려야 Page Fault를 줄일 수 있을 지 판단하는 알고리즘
이 바로 페이지 교체 정책이다.
대표적으로 FIFO, OPTIMAL, LRU정도가 있다.
-
FIFO(First In First Out)
말 그대로 먼저 들어온 페이지 먼저 나가는 알고리즘이다.
페이지의 재참조 가능성을 전혀 고려하지 않고 적재된 순서만 고려하기 때문에 대부분에 상황에서 비효율적이다.
FIFO알고리즘에서는 프레임 수가 증가해도 Page Fault가 더 증가하는 Belady's Anomaly가 발생할 수 있다.
-
LRU(Least Recently Used)알고리즘
LRU Cache문제로도 해결한 적이 있었던 알고리즘이다.
LRU 알고리즘은 시간 지역성과도 관련이 있다. 최근에 참조된 페이지가 다시 참조될 가능성이 높기 때문에, LRU알고리즘은 페이지 교체 시 가장 오래 전에 참조된 페이지부터 교체한다.
-
Optimal Algorithm
앞으로 사용하지 않을 페이지만 교체하는 알고리즘이다. 알고리즘 구조 상 Page Fault 비율도 가장 낮고 가장 이상적으로 작동한다.
Optimal Algorithm은 정말 완벽해 보이지만, 구현 불가능하다. Page Fault가 일어났을 때 미래에 가장 나중에 참조되는 페이지를 교체하는 방식이기 때문에, 미래에 어떤 페이지가 참조될지 알고 있어야 하기 때문이다.
교체 알고리즘 그 자체로는 의미가 없겠지만 최적화 알고리즘은 다른 교체 알고리즘의 성능의 척도로 사용될 수 있다.
