Memory Management
Page Replacement
- 메모리 과다 할당 상태(Over-allocating of memory): 필요한 메모리보다 프레임 수가 더 적은 경우 → 멀티 프로그래밍 시스템 내에서 사용자 프로세스 수가 증가할 때 발생
- 페이지 폴트 처리 시 페이지 교체(page replacement) 추가 → 피지컬 메모리에 위치한 페이지를 디스크에 저장 + 요구받은 페이지가 해당 프레임을 할당받도록 함(즉 할당받은 페이지를 프레임에서 빼내고 새로운 페이지로 교체하는 과정)
- 디스크에서 요구받은 페이지 위치를 찾기
- 피지컬 메모리에서 프리 프레임을 찾는다.
- 프리 프레임이 있을 때에는 그 프리 프레임에 페이지를 할당한다.
- 프리 프레임이 없다면 페이지 교체 알고리즘을 통해 빼낼 프레임(
victim)을 택한다(valid→invalid). - 빼낼 프레임을 디스크에, 넣을 페이지를 새롭게 만들어진 프리 프레임에 할당한다(
invalid→valid). - 사용자 프로세스를 재시작한다.
반복적인 페이지 교체 과정을 최소화하는 게 성능 향상의 키(I/O는 오버헤드가 크기 때문이다!)
Page Replacement Algorithm
- 페이지 폴트 발생 빈도가 가장 낮은 알고리즘
- 3개의 물리 프레임, 0~7번 페이지, 서로 20번의 페이지 참조 방식 가정
1. Optimal Algorithm
- 앞으로 사용률이 가장 낮은 페이지부터 교체하는 알고리즘
- (7, 0, 1)이 있는 시점에서 2번이 들어올 때 7번이 나가는 까닭은 이후 7, 0, 1이 각각 1, 5, 3번 참조되기 때문에 가장 참조 횟수가 적은 7이 교체됨
- 전체 참조 횟수를 알고 있어야 하기 때문에 실제로는 구현 불가능한 이상적인 알고리즘
2. FIFO Algorithm
- 교체되는 페이지는 큐 내에 가장 먼저 도착한 순서대로 FIFO 빠져나간다.
- 순차적 데이터 재생이 일반적인 멀티 미디어(동영상 등) 자료에 적합
3. SCR Algorithm
- Second Chance Replacement
- 자주 사용하는 페이지가 교체되는 경우를 방지하기
- 참조 비트: 프레임 로드 / 페이지 참조마다 1로 세팅 → 일정 주기마다 0으로 리셋
- 현재 교체 알고리즘에 걸릴 페이지가 최근에 썼다면(즉 현재 비트가 1) 비트를 0으로 변경하기만 하고 다른 페이지를 찾는다.
즉 최근에 쓴 히스토리가 있다면 한 번 더 기회를 준다는 알고리즘!
4. Clock Algorithm
- SCR 발전한 형태
- 원형 큐를 통해 페이지 프레임 관리
Head,Tail포인터 →Head는 큐를 따라서 이동. 가리키고 있는 페이지 참조 비트가 1이라면 0으로 리셋- 프리 프레임이 threshold 이하로 감소한다면
tail이 가리키고 있는 페이지를 내본다. 일반적인 시점에서는head를 움직여서 이후의 페이지 아웃을 대비Clock 알고리즘 또한 참조 비트가 1이라면 현재
head가 가리키는 페이지가 최근에 사용되었음을 체크한다!
5. LFU Algorithm
- Least Requently Used
- 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘
- 프로그램 실행 초기에 많이 사용, 이후에는 적게 사용되더라도 프레임에 계속 남아 있는 문제점 발생
6. NRU Algorithm
- Not Recently Used
- 참조 비트 + 변형 비트 두 자료구조를 통해 페이지 참조 여부 + 내용 변경 등을 동시에 확인
두 가지 비트의 활용 방법은 총 4가지. 1순위 ~ 4순위까지 잡아서 교체할 여부를 체크한다!
7. LRU Algorithm
- Optimal과 가장 유사한 알고리즘. 가장 오랜 시간 참조되지 않은 페이지부터 먼저 교체함
- 페이지 사용의 지역성 고려 → time locality
- Counter: 참조 시간 기록
Swapping
- 피지컬 메모리-프레임의 부족으로 페이지 스와핑 발생
- 페이지 아웃으로도 메모리 부족을 해결하지 못할 때(앞에서의 페이지 스와핑) 필요한 기법 → 프로세스 전체를 세컨더리 스토리지로 넣는 스와핑
- Linux: OOM(Out-of-memory) Killer
JUST DO IT