Paging_Segmentation.md

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

Advanced!!

주소 변환(Address Translation)

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

[논리 주소(Logical Address)]

• 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에 해당된다. d를 제외한 나머지 2칸이 p가 된다.

50 = 110010

p = 11

d = 0010

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

f = 1000

d = 0010

물리주소 = 10000010

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

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

내부 단편화(Internal Fragment)

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

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

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

보호와 공유

보호(Protection)

모든 주소는 페이지 테이블을 경유하므로, 테이블을 이용해서 보호 기능을 수행할 수 있다. 대표적으로 페이지 테이블마다 r(read), w(write), x(execute) 비트를 두어, 해당 비트가 켜져있을 때, 그 수행이 가능하도록 한다.

페이지 테이블에 r,w,x 비트를 추가한 모습이다. 만약, 1번 페이지 엔트리처럼 쓰기 비트가 꺼져있는 페이지에 쓰기 작업을 시도하면 CPU에 인터럽트가 발생하여 ISR(Interrupt Service Routine)에서 강제로 해당 프로세스를 종료시킨다.

공유(Sharing)

공유는 메모리 낭비를 방지하기 위함이다. 같은 프로그램을 쓰는 복수 개의 프로세스가 있다면, 프로세스의 메모리는 code+data+stack 영역으로 나뉘는데 프로그램이 같다면 code 영역은 같을 것이다.

그러므로 하나의 code 영역을 복수 개의 프로세스가 공유하여 메모리 낭비를 줄이는 것이다. 단, code가 공유되려면 code가 변하지 않는 프로그램이어야 한다. 이를 non-self-modifying code = reentrant code(재진입 가능 코드) = puer code 라고 한다.

세그멘테이션(Segmentation)

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

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

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

[단점]

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

세그먼테이션에서 보호와 공유

먼저, 결론부터 말하면 페이징보다 세그먼테이션에서의 보호와 공유는 더 효율적이다.

보호에서는 세그먼테이션 역시 r,w,x 비트를 테이블에 추가하는데, 세그먼테이션은 논리적으로 나누기 때문에 해당 비트를 설정하기 매우 간단하고 안전하다. 페이징은 code+data+stack 영역이 있을 때, 이를 일정한 크기로 나누므로 두 가지 영역이 섞일 수 있다. 그러면 비트를 설정하기가 매우 까다롭다.

공유에서도 마찬가지다. 페이징에서는 code 영역을 나눈다해도 다른 영역이 포함될 확률이 매우 높다. 하지만, 세그먼테이션은 정확히 code 영역만을 나누기 때문에 더 효율적으로 공유를 수행할 수 있다.

세그먼테이션과 페이징

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

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

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

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

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

Reference

• 운영체제 13. 페이징
• 운영체제 14. 세그멘테이션
• 세그멘테이션과 페이징