[OS] 메모리관리 - 불연속메모리 할당, 페이징

불연속할당 기법

연속할당기법과 다르게 불연속할당 기법은 프로세스가 물리 메모리에 연속으로 할당 되어있는게 아닌 여러곳에 분산되어 할당 될 수 있는 기법을 말한다.
불연속 할당기법으로는 메모리를 동일한 크기로 나누어 할당하는 페이징기법, 크기는 다르지만 의미있는 단위로 나누어 할당하는 세그멘테이션 기법이 있다.

연속할당 기법에서는 단편화의 문제점과 메모리 크기보다 큰 프로세스를 실행할 수 없다는 단점이 있었다. 하지만 가상 메모리를 통한 불연속 할당을 통해 실제 메모리보다 큰 프로세스도 실행할 수 있다.

Paging(페이징)

페이징은 프로세스를 동일한 크기로 나누어 잘라서 물리 메모리에 할당하는 방식이다.
논리주소 공간은 페이지 단위로, 물리 공간은 페이지와 동일한 크기의 프레임으로 자루고 할당하는 방법이다.

페이징 기법에서는 프로세스를 연속적으로 한번에 할당하지 않아도 되기 때문에 당장 필요하지 않은 부분은 backing store에 저장해 놓고 스왑인, 스왑아웃 할 수 있다. 그렇기 때문에 실제 크기보다 큰 프로세스를 실행할 수 있는 것이다.

Page Table

페이징 기법에서는 프로세스가 메모리에 불연속적으로 할당되어 있기 때문에 CPU의 입장에서는 순차적 실행이 불가능하다. 그렇기 때문에 페이지가 실제 물리 메모리의 어느 프레임에 할당 되어있는지 알아야하는데 이를 Page Table을 통해서 찾아낼 수 있다.
즉 페이지 테이블에는 몇번 페이지가 몇번째 프레임에 있는지에 대한 정보를 담고 있다.

페이지 테이블은 프로세스가 갖고 있는 페이지의 개수만큼 엔트리가 생성되어야한다. 즉 크기가 크기 때문에 물리 메모리에 상주하고 있다.
마지막으로 페이징 기법에서는 외부 단편화는 발생하지 않지만 내부 단편화가 발생할 수 있다.
이유는 항상 프로세스의 크기가 페이지 크기의 배수가 아닐 수 있기 때문이다.

Address Translation

페이징 기법에서는 각 프로세스마다 각자의 페이지 테이블을 갖고 있다. 그리고 페이지 테이블을 물리 메모리에 적재되어있다. 그렇기 때문에
문맥교환이 일어난다면 현재 페이지 테이블을 통째로 바꿔야한다.

페이지 테이블에 접근하기 위해서 CPU는 두가지 레지스터를 사용하는데

1. Page Table Base Register
2. Page Table Length Register
   을 사용한다.

1번은 메모리에서의 페이지 테이블의 시작 위치를 가르키고, 2번은 페이지 테이블의 총 길이를 나타낸다.

페이징 기법에서 메모리 접근을 하기 위해서는 두번의 연산이 요구가 된다.
페이지 테이블이 메인 메모리에 있기 때문에 우선 해당 페이지 테이블을 접근할 때 1번, 그리고 변환된 주소에서 실제 데이터를 가져오는데 1번
총 2번의 연산이 필요하다. 이러한 연산의 오버헤드를 줄이고 접근 속도를 향상시키기 위해서 TLB 라는 Translation Lookaside Buffer을 사용한다.

이는 일종의 캐시메모리 이기 때문에 CPU와 메인 메모리 사이에 위치한다.

TLB

TLB는 캐시메모리이기 때문에 모든 엔트리에 대한 정보를 담을 수 없기 때문에 자주 참조되는 영역에 대한 정보를 담고 있다.
만약 CPU가 요구하는 주소가 TLB에 있다면 TLB Hit, 없다면 TLB Miss라고 한다.

하지만 TLB 는 페이지 테이블과 다르게 모든 엔트리를 갖고 있지 않기 때문에 페이지 번호와 해당 프레임번호를 한 쌍으로 갖고 있어야한다.
페이지 테이블에서는 모든 페이지에 대한 정보가 순차적으로 저장되어있기 때문에 페이지 번호만 알면 테이블의 시작위치에서 떨어져있는 페이지 번호만큼 떨어져있는 인덱스에 바로 접근 할 수 있다.

그와 반대로 TLB는 그러지 못하기 때문에 페이지 번호에 해당하는 프레임 번호를 갖고있다. 즉 TLB를 통한 주소 변환을 위해서는 모든 엔트리를 탐색해야된다는 단점이 있다.

TLB에서 엔트리를 탐색하지 못하면 메인 메모리의 페이지 테이블을 참조하게 된다.
이런 속도 문제를 향상 시키기 위해서 TLB에서는 병렬 탐색이 가능한 연관 레지스터를 보통 사용한다.

페이징 주소 변환

하나의 페이즈, 프레임 안에는 또 여러개의 주소가 들어가 있다. 마치 서울시에 위치한 강동구에 여러 도로가 있는것처럼이다.
그렇기 때문에 특정한 주소를 접근하기 위해서는 페이지 번호와 접근하고자 하는 주소가 페이지 번호에서 얼만큼 떨어져있는지 나타내는 offset이 필요하다.

이렇게 논리 주소의 페이지 번호와 Offset을 통해서 물리 메모리의 프레임번호와 Offset으로 변환이 된다.

Multi-level Paging

페이지 테이블은 프로세스가 갖고 있는 모드 페이지 엔트리를 저장하고 있다. 현대 32비트 컴퓨터는 약 4GB의 주소 공간을 갖고 있는 프로그램을 지원할 수 있는데 이러한 상황에서 프로세스는 상당히 많은 페이지를 갖게 된다. 이런 모든 페이지를 모두 저장하는 것은 비효율적이고 실제로 프로그램은 메모리 중 일부분만을 사용하기 때문에 공간적으로도 비효율적이다.

그래서 사용하는 것이 2단계 페이징 기법이다. 페이지 테이블을 여러 개의 페이지로 나누고, 해당 페이지를 가리키는 Outer 페이지 테이블을 두는 방식이다.

프로그램은 극히 일부분을 사용하기 때문에 Outer 테이블에서 사용되지 않는 공간에 대해선 NULL로 설정하게 된다.

2단계 페이지 테이블에서의 주소는 3개로 나뉘어진다. <바깥 페이지 번호, 안쪽 페이지 번호, Offset>이다.
우선 바깥 페이지 번호를 통해서 페이지 테이블에서의 페이지를 찾고
페이지 테이블의 페이지를 통해 프레임 번호를 찾는다.
그 이후에 변위(Offset) 값을 더해서 실제 물리 주소를 얻게 된다.