[OS] Paging

Paging vs Segmentation

• 가상 메모리를 관리하는 방법이다.
• 가상 메모리는 메모리에 로드된 즉, 실행중인 프로세스가 가상의 공간을 참조하여 마치 커다란 물리 메모리를 갖고 있는 것처럼 사용할 수 있도록 하는 것이다.
• 간단하게 말해 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다.

ex)
내가 실행하고자하는 프로그램이 5GB인데 내 메모리는 4GB이다. 어떻게 할까?
올리기도 버겁지만 올리면 다른 프로그램은 돌리지도 못한다. 이럴때 사용하는게 가상 메모리이다.

가상 메모리 !?

• 메모리는 한정적인데 프로세스 용량이라던가, 프로세스의 수가 늘어나면 다중 프로그래밍이 힘들어질 수 있습니다. 그럴 때를 대비해서, 프로세스의 데이터 전체가 메모리에 올라가지 않더라도, 가상의 주소공간을 이용해서 프로세스를 유지할 수 있게끔 해주는 것을 의미합니다.

• 가상 메모리는 각 프로세스당 메인 메모리와 동일한 크기로 하나씩 할당된다. 그 공간은 보조기억장치 공간을 이용한다. 프로세스의 일부만 메모리에 로드하고 나머지는 보조기억장치에 두는 형태이다.

이렇게 할당되면 메모리 관리 장치(MMU) 에 의해 물리 주소로 변환되어 사용자가 메모리 맵핑이 어떻게 되는지 의식할 필요 없이 알아서 가상 메모리를 활용하여 작업을 한다.

페이징 (Paging)

프로세스의 주소 공간을 동일한(고정된) 사이즈의 페이지 단위로 나누어 물리적 메모리에 불연속적으로 저장하는 방식

• 외부 단편화와 압축 작업을 해소하기 위함이다.
• 메모리는 Frame이라는 고정 크기로 분할되고, 프로세스는 Page라 불리는 고정 크기로 분할된다.
• 하나의 프로세스는 연속적인 동작을 수행하는데, 이를 작은 조각으로 나누어 여기저기 흩어진다면 정상적으로 동작할까?
• 이처럼 메모리상에서 여러 곳에 흩어진 프로세스를 수행하기 위해 MMU를 통해 논리 주소와 물리 주소를 나누어 사용함으로써 CPU를 속여야 한다.
• 실제 메모리는 전혀 연속적이지 않는데, CPU는 연속적으로 사용하고 있다는 것을 보장받으며 정상적으로 수행한다.
• 50byte 크기의 프로세스가 있다고 가정하고, 페이징의 크기는 10byte로 나눈다.

• 프로세스 P1은 5개의 페이지로 나눌 수 있다. 이를 메인 메모리 5곳에 나눠서 할당했다.
• CPU는 논리 주소로 프로그램이 설정한대로 연속적인 주소값으로 명령을 내리고 이는 메모리로 가기 전에 각 페이지의 실제 메모리 주소가 저장되어 있는 테이블에서 물리 주소로 변경되어야 한다.
• 프로세스를 나눈 조각을 Page라 하고, 메모리를 나눈 조각을 Frame이라 한다.
• 프로세스는 페이지의 집합이고, 메모리는 프레임의 집합이다.
• 프로세스를 정상적으로 사용하기 위해 MMU의 재배치 레지스터를 여러 개 사용해서 위의 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이러한 여러 개의 재배치 레지스터를 페이지 테이블(Page Table)이라 한다.

단점

• 내부 단편화 문제의 비중이 늘어나게 된다.
  Ex) Page 크기 : 1024B, 프로세스 A가 3172의 메모리를 요구한다면 3개의 페이지 프레임(1024 x 3 = 3072)을 구성하고도 100B가 남기 때문에 총 4개의 페이지 프레임이 필요하다. 마지막 페이지 프레임에는 924B의 여유 공간이 남게 되는 내부 단편화 문제가 발생한다.

위에서 말했듯 페이징을 사용하면 여러 개로 흩어진 페이지에 CPU가 접근하기 위해서 페이지 테이블을 통해 주소를 변환해야 한다.

주소 변환 (Address Translation)

논리 주소

• CPU가 접근하는 주소는 2진수로 표현되고 이는 m비트가 있다고 가정하다.
• 여기서 하위 n비트는 오프셋(offset) 또는 변위(displacement)라고 한다.
• 그리고 상위 m-n비트는 페이지의 번호에 해당한다. (n = d, m-n = p)
• 논리주소를 물리주소로 변환하기 위해서 페이지 번호(p)는 페이지 테이블의 인덱스 값이고, p에 해당되는 테이블 내용은 메모리의 프레임 번호이다. 변위(d)는 변하지 않는 값이다. 이 규칙에 대한 예제를 살펴보자.

Page size = 16bytes
Page Table = 5,3,2,8,1,4
논리 주소 50번지는 물리주소 몇 번지인가?

프로세스 P가 메모리에 할당된 모습이다.
CPU가 50번지 접근하려고 한다.
그러면 페이지 테이블의 정보를 읽기 위해 논리 주소를 p와 d 값으로 나눠야 한다.

d는 페이지 크기에 따라 달라지는데, 현재 페이지 크기는 16byte이다. 이는 2^4이므로 d = 4이다.

p는 d를 제외한 나머지 크기이다.

그러면 실제로 p,d를 계산해보자. 현재 논리 주소는 50이며, 이진수로 나타내면 110010이다.
먼저, d는 4이므로 이진수의 뒤에서 4칸이 d(0010)에 해당된다. d를 제외한 나머지 2칸이 p(11)가 된다.

p는 이진수 11이고, 십진수로 3이다. 즉, 페이지 테이블의 페이지 번호 3을 가리킨다. 페이지 3번에 해당하는 프레임 번호는 8이므로 물리주소를 구성하는 f의 값은 8이 된다.

f = 1000

d = 0010

물리주소 = 10000010

최종적으로 물리주소는 f와 d로 구성되어 있으므로 물리주소는 이진수로 10000010이 되고, 십진수로 130번지가 된다.
즉, 변위는 2이므로 8번째 프레임의 시작 주소는 130에서 2를 뺀 128번지(16*8)가 된다.

연속 메모리 할당을 하면서 외부 단편화가 발생하여 이를 해결하기 위해 페이징 기법이 등장했지만, 페이징은 내부 단편화 문제가 발생한다.

내부 단편화

프로세스의 크기가 페이지 크기의 배수가 아닐 경우, 마지막 페이지는 한 프레임을 다 채울 수 없어서 발생하는 공간으로 메모리 낭비의 원인이 된다.

15byte 크기의 프로세스 p가 있다. 페이지 크기는 4byte로 p를 페이지로 나누면 4,4,4,3의 크기로 총 4개의 페이지로 구성된다. 마지막 3byte 페이지는 페이지의 크기보다 1byte 작아서 다 채우지 못한다.
이 만큼 메모리 공간이 비게 된다. 이렇게 비어진 공간은 프로세스 p에서도 쓰지 않고, 다른 프로세스에서도 쓰지 못하는 공간이 된다.

내부 단편화의 해결 책은 없다...
하지만, 내부 단편화는 외부 단편화에 비해 낭비되는 메모리 공간은 매우 적다.
내부 단편화의 최대 낭비되는 크기는 page size -1이 된다.
(외부 단편화는 최대 전체 메모리의 1/3이 낭비된다고 한다.) 이는 무시할 정도로 작은 크기.

Reference

• Ready-For-Tech-Interview