연속 메모리 할당과 페이징 방식

연속 메모리 할당이란

프로세스에 연속적으로 메모리를 할당하는 것이다. 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 할당한다.

연속 메모리 할당의 종류로는 고정 분할 방식과 가변 분할 방식이 있다.

연속 메모리 할당의 원리

연속 메모리 할당에서는 메모리를 여러 분할로 나누어서 프로세스를 할당한다.

프로세스들을 할당할 때 적재될 공간을 찾아야하는데 이를 구현한 방법이 대표적으로 3가지가 있다.

 
최초 적합
메모리를 탐색하다가 프로세스를 적재할 수 있는 공간(hole)이 나오면 그 자리에 바로 배치하는 것이다.
 
최적 적합
빈 자리가 있다고 무조건 적재하는 것이 아니라 적재 가능한 가장 작은 공간에 프로세스를 할당한다.
 
최악 적합
촤적 적합과는 반대로 적재할 수 있는 가장 큰 공간에 프로세스를 적재하는 것이다.
 

연속 메모리 할당으로 인한 문제점

근데 문제는 위처럼 빈 공간에 메모리를 할당하는 것은 그렇게 효율적인 방법이 아니다.
그 이유는 외부 단편화, 내부 단편화 때문인데 두 개의 문제가 꽤 치명적이다.

 

먼저 고정 분할 방식에서 생기는 문제점은 외부 단편화 , 내부 단편화가 있다.

고정 분할 방식은 분할의 크기보다 프로세스의 크기가 커서 실행되지 못하는 문제가 발생하는데 이를 외부 단편화 라고한다.

또한 프로세스에 비해 큰 분할에 적재될 경우 해당 분할의 남은 메모리가 낭비되는 내부 단편화 문제도 발생한다. 이는 하나의 분할에는 하나의 프로세스만 들어가야 하기때문에 발생하는 문제이다.

이처럼 고정 분할 방식은 메모리를 고정시켜 놓고 시작하기 때문에 가변 분할 방식에 비해 융통성이 떨어진다.

 

하지만 가변 분할 방식도 문제가 없는 것은 아니다. 가변 분할 방식도 외부 단편화 문제를 가지고 있다.
메모리에 빈 공간이 20MB , 30MB가 있더라도 50MB는 할당이 불가능하다. 이 두개의 메모리는 나뉘어져 있기 때문이다.
이렇게 메모리가 할당되면서 생기는 애매하게 작은 빈공간들은 계륵같은 존재여서 결국엔 빈공간으로 남게 된다. 이 문제를 외부 단편화라고 한다.
 

외부 단편화

 
단순한 해결 방법으로는 메모리 압축 방식이 있다. 하지만 이 방법은 좀 비효율적이다.
메모리를 압축하면서 오버헤드를 피할 수 없으며 그리고 메모리를 어떻게 압축할건지에 대한 효율적인 설계도 부담해야하기 때문에
현대에는 페이징이 대표적으로 사용되고 있다.
 

대표적인 해결 방법 - 페이징

지금까지 연속 메모리 할당은 여러 문제가 있다는 것을 살펴보았다.
그래서 운영체제가 선택한 방법은 가상 메모리를 이용한 페이징인데 페이징에 집중해서 알아볼 것이다.
https://cb036133.tistory.com/175

가상 메모리의 개념 (논리주소, 페이지 폴트, 스와핑)

 
페이징은 근원적인 문제를 해결한다.
결국 외부 단편화가 발생하는 이유는 프로세스의 크기가 모두 달라서인데 그렇다면 프로세스의 크기를 일정하게 자르고 필요한 부분만 할당한다면 어떨까?
이렇게하면 낭비되는 메모리도 줄일수 있고 크기 큰 프로세스도 일정 부분만 올려서 실행시킬 수 있다.
 
이렇게 일정한 크기로 자른 단위를 페이지라고하며 메인 메모리에서는 프레임이라고 한다.
그리고 안쓰는 페이지들은 다시 스왑 영역으로 swap out 시킬 수 있다. 즉 모든 메모리가 메모리에 적재되어 있을 필요가 없다.
 
근데 페이지는 연속 메모리 할당과는 다르게 불연속적으로 할당된다. 그렇기 때문에 CPU는 페이지 테이블을 이용하여 페이지와 테이블을 매핑시킨다.(약간 네트워크의 라우팅 테이블과 같은 역할이다)
프로세스마다 있는 페이지 테이블을 이용해서 순차적으로 프레임에 접근할 수 있으며 CPU는 불연속 적으로 할당되었다는 것을 고려할 필요가 없다.

 

근데 프로세스마다 테이블이 있다면 CPU는 어떻게 이 테이블을 찾아갈 수 있는 걸까? 이 역할을 하는게 PTBR이다.

하지만 페이지 테이블이 따로 있다면 불필요하게 메모리에 두번 접근하게 된다. (페이지 테이블 1번 + 페이지 참조 1번)

 

따라서 TLB를 통해 페이지 테이블의 일부를 가져와서 저장하는 캐시이다. 이를 통해 불필요한 메모리 접근을 줄일 수 있다.
 
페이징 방식이 좋다고 한들 계속 스왑을 하게 되면 성능적으로 떨어질 수 밖에 없다. 이제 관건은 어떤 프로세스를 메모리에 올리느냐인데, 이것을 고민한 결과들이 페이지 교체 알고리즘이다.
 
페이지 교체 알고리즘의 종류
 
오프라인 알고리즘(LFD)
가장 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 것이다.
오프라인 알고리즘은 가장 이상적인 알고리즘이지만 실현 가능성이 거의 없다. 유저의 미래 행동을 예측할 수 없기 때문이다.
하지만 현재 페이지 테이블에서 나올 수 있는 성능의 이상적인 척도(상한선)를 제공해준다. 
 
직관적으로 생각하면 가장 나중에 사용되는 페이지를 버린다고 볼 수 있다.

FIFO
먼저 온 페이지를 가장 먼저 교체한다.

특이하게도 FIFO의 경우 페이지의 수를 늘리게 되면 페이지 폴트가 더 자주 발생한다.(벨레이디의 모순)

 
LRU
참조가 가장 오래돤 페이지를 바꾼다. 이 방식을 구현하기 위해서는 각 페이지마다 카운터와 스택을 두어야한다.
 

LFU
가장 참조 횟수가 적은 페이지를 교체한다.

NUR (클럭 알고리즘)
0과 1을 가진 비트를 두고 시계 방향으로 돌면서 0을 찾은 순간 프로세스를 교체하는 것이다. 여기서 0은 참조되지 않았다는 뜻이다.

하지만 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다. 프로세스를 교체하면 해당 부분은 1로 바꾼다.