메모리 단편화 현상
내부 메모리 단편화
프로세스가 필요한 메모리보다 더 많은 메모리 공간이 할당되는 것
외부 메모리 단편화
전체 메모리 중간중간에 사용하지 않는 메모리 공간이 생겨 총 여유 메모리 공간은 프로세스를 할당하기에 충분하지만 실제로는 할당할 수 없는 현상
메모리 단편화 해결 방법
Paging
- 가상 메모리 사용
- 외부 단편화 문제 해결
- 내부 단편화 존재
보조기억장치를 이용한 가상메모리를 같은 크기의 블록으로 나눈 것을 페이지라고 하고 RAM을 페이지와 같은 크기로 나눈 것을 프레임이라고 한다
페이징 기법이란 사용하지 않는 프레임을 페이지에 옮기고 필요한 메모리를 페이지 단위로 프레임에 옮기는 방법이다
페이지와 프레임을 대응시키기 위해 page mapping과정이 필요해서 paging table을 만든다
페이징 기법을 사용하면 연속적이지 않은 공간도 활용할 수 있기 때문에 외부 단편화 문제를 해결할 수 있다
하지만 페이지 단위에 알맞게 메모리를 꽉 채워 사용하는게 아니므로 내부 단편화 문제는 존재한다
페이지 크기를 작게하면 내부 단편화 문제도 해결할 수 있겠지만 page mapping 과정이 많아져 오히려 효율이 떨어지게 된다
Segmentation
- 가상 메모리 사용
- 내부 단편화 문제 해결
- 외부 단편화 존재
페이징 기법에서는 가상메모리를 같은 크기의 단위로 분할했지만 세그멘테이션 기법에서는 가상메모리를 크기가 다른 논리적 단위인 세그멘트로 분할해서 메모리를 할당한다
각 세그먼트는 연속적인 공간에 저장되어 있다
세그먼트들의 크기가 다르기 때문에 미리 분할해 둘 수 없고 메모리에 적재될 때 빈 공간을 찾아 할당된다
세그멘트 mapping을 위한 세그먼트 테이블이 필요하다
프로세스가 필요한 메모리만큼 할당해주기 때문에 내부 단편화의 문제는 해결되나 여전히 중간에 프로세스가 메모리를 해제하면 생기는 구멍인 외부 단편화 문제는 존재한다
Memory Pool
필요한 메모리 공간을 필요한 크기, 개수만큼 사용자가 직접 지정하여 미리 할당받아 놓고 필요할 때 마다 사용하고 반납하는 방법이다
메모리 풀 없이 동적할당과 해제를 반복하면 메모리의 랜덤한(실제로는 알고리즘에 의한) 위치에 할당과 해제가 반복되면서 단편화를 일으킬 수 있겠지만 미리 공간을 할당한 뒤 가져다 쓰고 반납하기 때문에 할당과 해제로 인한 외부 단편화가 발생하지 않는다
또한 필요한 크기만큼 할당을 미리 해두기 때문에 내부 단편화 또한 생기지 않는다
하지만 메모리 단편화로 인한 메모리 낭비량보다 메모리 풀을 만들었지만 쓰지 않았을 때 메모리 양이 커지는 경우 사용하지 않아야 한다
메모리의 할당, 해제가 잦은 경우에 메모리 풀을 쓰면 효과적이다
미리 할당해놓고 사용하지 않는 순간에도 계속 할당된 상태로 있으므로 Memory Leak이 존재한다
그러므로 메모리 단편화로 생기는 낭비보다 메모리 풀을 할당한 뒤 사용하지 않는 메모리가 많은 경우에는 지양하여야 한다
페이지 교체 알고리즘
FIFO(First In First Out)
가장 먼저 들어온 페이지를 페이지 fault가 발생하면 교체한다
동일한 페이지가 계속 참조되는게 아니라면 페이지 fault가 지속적으로 발생한다
LFU(Least Frequently Used)
가장 적게 사용된 페이지를 페이지 Fault 발생시 교체한다
최근에 교체된 페이지가 교체될 가능성이 높다
페이지 참조에 대한 횟수를 기록하는 오버헤드가 발생한다
LRU(Least Recently Used)
가장 오랫동안 참조되지 않은 페이지를 교체한다
페이지 참조 시간을 기록하는 오버헤드가 발생한다
OPT(Optimal Replacement)
앞으로 오랫동안 사용되지 않을 페이지를 교체한다
제일 이상적이지만 각 페이지의 호출 순서와 참조상황을 미리 예측해야 하므로 어려운 부분이 있다
NUR(Not Used Recently)
LRU와 비슷한 알고리즘으로 시간 기록 오버헤드를 줄일 수 있다
최근에 사용되지 않은 페이지는 추후에도 사용되지 않을 가능성이 높다는 것을 전제로 한다
- 참조비트 : 페이지 호출시 1, 미호출시 0
- 변형비트 : 페이지 내용 변경시 1, 미변경시 0
| 참조 비트 | 변형 비트 | 교체 순서 |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 2 |
| 1 | 0 | 3 |
| 1 | 1 | 4 |
SCR(Second Change Replacement)
FIFO의 단점을 보완하기 위해 만들어진 알고리즘이다
참조 비트를 두고 페이지 Fault 발생시 교체하려고 할 페이지의 비트가 1이면 0으로 바꾼 뒤 FIFO리스트의 맨 마지막으로 둔다
교체하려고 할 페이지의 비트가 0이라면 교체를 수행한다