Paging, Segmentation

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의 여유 공간이 남게 되는 내부 단편화 문제가 발생한다.

 

내부 단편화(Internal Fragment)

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

예를 들어, 15bytes 크기의 프로세스 p가 있다. 페이지 크기는 4byte로 p를 페이지로 나누면 4,4,4,3의 크기로 총 4개의 페이지가 만들어진다. 마지막 3byte 페이지는 페이지의 크기보다 1byte 작으므로 사용하지 못하고, 이만큼의 메모리 공간이 비게 된다. 이렇게 비어진 공간은 프로세스 p에서도 쓰지 않고, 다른 프로세스에서도 쓰지 못하는 낭비되는 공간이 된다.

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

 

세그멘테이션(Segmentation)

• 프로세스를 서로 크기가 다른 논리적인 블록 단위인 '세그먼트(Segment)'로 분할하고 메모리에 배치하는 것을 말하며, 각 세그먼트의 크기는 일정하지 않다.
• 프로세스를 Code + Data + Stack 영역으로 나누는 것 역시 세그멘테이션의 모습이다. 물론, code, data, stack 각각 내부에서 더 작은 세그먼트로 나눌 수도 있다.
• 세그먼트를 메모리에 할당할 때는 페이지를 할당하는 것과 동일하다. 하지만, 테이블은 조금 다르다. 세그먼테이션을 위한 테이블은 세그먼트 테이블이라고 한다.
• 세그먼트 테이블은 세그먼트 번호와 시작 주소, 세그먼트 크기를 엔트리로 갖는다.
• 세그먼트에서 주소변환 역시, 페이징과 유사하다. 한 가지 주의할 점은 세그먼트의 크기는 일정하지 않기 때문에, 테이블에 limit 정보가 주어진다. 그리고 CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료시킨다.

위 그림은 세그먼트 테이블과 프로세스가 할당된 메모리의 모습이다. 페이징 주소변환과 동일하게 d(변위 : 변하지 않는 값)는 논리주소와 물리주소가 동일하다. 물리주소 a는 base[s]+d 로 계산된다.

• 논리 주소(2, 100) -> 물리주소 4400번지
• 논리 주소(1, 500) -> limit이 400밖에 안되므로 인터럽트로 인해 프로세스 강제 종료(범위를 벗어남)

[단점]

• 외부 단편화 문제가 발생할 수 있다.

 

세그먼테이션과 페이징

세그먼테이션은 페이징과 유사하고 보호와 공유 측면에서는 더 나은 성능을 보여주었지만, 현재 대부분은 페이징 기법을 사용한다. 그 이유는 세그먼테이션에는 치명적인 단점이 존재하기 때문이다.

메모리 할당을 처음 시작할 때, 다중 프로그래밍에서의 문제는 크기가 서로 다른 프로세스로 인해 여러 크기의 hole이 발생한다. 이로 인해 어느 hole에 프로세스를 할당하는 것에 대한 최적화 알고리즘이 존재하지 않고, 외부 단편화로 인해 메모리 낭비가 크다고 했었다.

세그먼테이션도 똑같은 문제점이 발생한다. 왜냐하면 세그먼테이션은 논리적인 단위로 나누기 때문에 세그먼트의 크기가 다양하다. 이로 인해 다양한 크기의 hole이 발생하므로 같은 문제가 발생한다.

결론적으로 세그먼테이션은 보호와 공유에서 효율적이고, 페이징은 외부 단편화 문제를 해결할 수 있다. 그러므로 이 두가지를 합쳐서 사용하는 방법이 나왔다. 두 장점을 합치기 위해서는 세그먼트를 페이징 기법으로 나누는 것이다. (Paged Segmentation)

하지만, 이 역시 단점이 존재한다. 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환도 두번해야 한다. 즉, CPU에서 세그먼트 테이블에서 주소 변환을 하고, 그 다음 페이지 테이블에서 또 주소 변환을 해야 한다.