[OS] Segmentation을 사용한 가변 크기 메모리 관리 및 추상화 - OS 공부 10

안녕하세요 Pingu입니다!🐧

지난 글에서는 메모리 가상화를 하기 위해 base, limit 레지스터를 사용하여 가상 주소를 실제 메모리의 주소로 변환하는 주소변환에 대해 알아봤었습니다. 이러한 방법을 Dynamic relocation(동적 재배치)라고 했으며 글의 마지막 부분에 이 방법은 heap과 stack 사이의 사용하지 않는 공간도 할당하기 때문에 비효율적이라고 했었습니다. 이러한 점을 보완하기 위해서 이번 글에서는 Segmentation이라는 개념을 도입한 메모리 가상화 방법에 대해 알아보려고 합니다. 또한 이를 통해 저번 글에서 가정한 가정들도 제거할 수 있습니다! 이번 글은 제가 참고하고 있는 OSTEP책에서는 Chapter 16 - Segmentation입니다.

Segmentation (분할)

아까도 한 번 언급한 대로 지난 글까지는 프로세스의 전체 주소 공간을 한 번에 연속적으로 메모리에 할당했습니다. Base, limit 레지스터를 사용하여 OS는 프로세스의 가상 주소 공간을 실제 메모리에 재배치할 수 있었습니다.

Base, limit 레지스터만 사용하는 방법은 위의 그림과 같이 연속적으로 메모리에 할당하기 때문에 heap, stack 사이의 공간이 사용되고 있지 않아도 할당해야 하는 문제가 있었습니다. 저 공간이 위의 그림에서는 가상공간의 크기가 16KB이므로 크지 않아 보여서 크게 문제가 안되지 않을까..? 생각하실 수 있는데요, 요즘은 아니지만 이전에 많이 쓰이던 32bit 컴퓨터의 경우를 생각해 보겠습니다. 32비트의 주소 공간을 가지는 가상공간은 2^32 = 4GB입니다. 엄청나지 않나요? 심지어 요즘엔 64bit 컴퓨터를 사용하는데 base, limit 레지스터만 사용한다는 것은 정말 말이 되지 않습니다. 또한 메모리의 크기보다 큰 프로세스는 실행조차 할 수 없었습니다. 이러한 문제를 해결하려면 어떻게 해야 할까요?

Segmentation: Generalized Base / Limit

이러한 문제를 해결하기 위해 segmentation 아이디어가 탄생했습니다. 이는 1960년대 초반에 만들어진 아이디어라고 하네요. 어쨌든 이 아이디어는 아주 간단합니다. CPU의 MMU에 base, limit 레지스터가 하나만 존재하는 것보단 base, limit 레지스터를 한 쌍으로 segment를 표현하면 어떨까? 에서 시작합니다. 여기서 segment란 메모리에서 일정 부분을 뜻하며 일반적인 주소 공간은 3개의 segment(Code, Stack, Heap)으로 구성됩니다. OS는 메모리에 3개의 segment를 메모리에 배치하여 아까 발생한 문제인 heap, stack 사이의 공간을 낭비하지 않도록 하는 것입니다. 예를 보면 바로 이해를 할 수 있습니다!

위의 그림은 아까 그림의 프로세스를 segment를 사용하여 메모리에 배치한 것입니다. 위의 그림에서는 heap, stack 사이의 공간이 낭비가 되지 않는 것을 볼 수 있습니다. 이렇게 segment를 사용하려면 이전 방식처럼 base, limit 레지스터가 한 쌍만 있으면 안 될 것 같지 않나요? 따라서 위의 그림처럼 프로세스를 메모리에 배치하려면 다음과 같은 레지스터 쌍들이 필요합니다.

위의 표를 해석하기 전에 limit 레지스터의 이름이 Size로 바뀌었습니다. 이를 고려하여 위의 표를 해석하자면 Code segment는 32KB에 배치가 되고 크기는 2K입니다. Heap은 34KB에 배치되고 크기는 3K, Stack은 28KB에 배치되고 크기는 2K라고 해석할 수 있겠죠? 그럼 이제 segment을 사용하여 주소 변환을 해보겠습니다. 예를 들어 가상 주소 1000을 참조한다고 가정해 보겠습니다.

가상 주소 1000을 참조하면 이는 가상 주소에서는 Code 부분입니다. 따라서 이를 segment 레지스터의 값으로 Code segment의 base를 확인합니다. 이는 32KB이므로 실제 메모리에서는 32KB + 1000 부분을 참조하면 됩니다.

그렇다면 만약 Size를 넘어서는 부분을 참조하려고 하면 어떤 일이 발생할까요? 그럼 이번에는 가상 주소 7100을 참조한다고 가정해 보겠습니다.

가상 주소 7100은 free 공간입니다. 따라서 이 공간을 참조하려고 하면 size를 초과한 것을 감지하고 OS에 트랩 하여 해당 프로세스를 종료할 수 있습니다. 이것이 C언어로 개발하다가 자주 만나게 되는 유명한 segmentation fault입니다.

Which Segment Are We Referring To?

방금 segment를 활용한 주소변환을 해봤는데 이는 실제로는 하드웨어가 변환 중 segment 레지스터를 사용하여 처리됩니다. 그렇다면 segment로의 offset과 어떤 segment를 참조할지는 어떻게 알 수 있을까요? 아까처럼 매번 그림을 그릴 순 없으니 한 번 알아보도록 하겠습니다.

Segment의 offset과 어떤 segment를 참조할지는 가상 주소의 주소를 2진수로 나타내서 알아낼 수 있습니다. 아까의 예에서 이를 적용해 보겠습니다.

위의 예에서 가상 메모리의 크기는 16KB입니다. 즉 14비트로 표현할 수 있습니다. 그리고 segment는 총 3개입니다. Code는 00, Heap은 01, Stack은 11로 구별할 수 있습니다. 이를 위해 상위 2개 비트로는 segment를 구분하고 하위 12개의 비트로 offset을 계산할 수 있습니다. 실제로 위의 그림에서 가상 주소 1000을 변환했고 동일한 결과가 나오는 것을 볼 수 있습니다.

그럼 다른 예를 보며 한 번 더 익혀볼까요? 이번에는 가상 주소 4100을 변환해 보겠습니다.

가상 주소 4100을 2진수로 표현하면 위와 같이 나오게 됩니다. 앞의 2비트를 segment 구분에 사용한다고 했으니 이번에는 01, 즉 Heap 공간이네요! 그리고 offset은 4이므로 실제 메모리 주소는 34KB + 4가 됩니다. 이러한 계산을 코드로 나타내면 엄청 단순하게 표현할 수 있습니다.

// 상위 2 비트를 가지고 옵니다.
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT

// 하위 12 비트로 offset을 구합니다.
Offset = VirtualAddress & OFFSET_MASK

// Offset이 limit을 넘는지 확인합니다.
if (Offset >= Limit[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysicalAddress = Base[Segment] + Offset
    Register = AccessMemory(PhysicalAddress)

위의 코드처럼 가상 주소를 실제 메모리 주소로 변환할 수 있습니다. 변수의 값을 보자면 SEG_MASK = 0x3000, SEG_SHIFT = 12, OFFSET_MASK = 0xFFF입니다. 일부 시스템에서는 가상 주소 공간을 최대한 활용하기 위해 세그먼트를 구분하는 비트로 1개만 사용한다고 합니다. 지금 14비트에서 segment 구분을 위해 2개를 사용할 때는 segment 크기로 4KB가 최대였지만 1개만 사용하게 된다면 8KB를 사용할 수 있게 됩니다.

What about The Stack?

Stack은 Heap, Code 부분과 다르게 거꾸로 확장된다는 것을 기억하시나요?

만약 위와 같이 segment 레지스터들이 저장되어 있다면 Stack은 28KB에서 시작하여 역으로 자라 26KB까지 메모리를 할당받게 되는 것입니다. 즉 주소 변환도 다르게 해야 하는 것이죠. 이를 위해 가장 먼저 필요한 것은 추가적인 하드웨어의 지원입니다. Base, Limit 레지스터를 사용할 때와는 다르게 하드웨어는 segment가 어떤 방향으로 확장되는지 알아야 합니다.

즉 위와 같이 Grows Positice?라는 정보를 만들어줘야 하는 것이죠. 그럼 이를 적용해 보기 위해 Stack의 가상 주소를 변환해 보겠습니다. 가상 주소 15KB에 접근한다고 예를 들어 보겠습니다.

위와 같이 15KB를 2진수로 나타낸 값의 앞의 두 자리에 해당하는 11은 segment 구분을 위한 값이었습니다. 11이니까 Stack 이겠네요. 그리고 남은 값은 offset인데 3KB입니다. 여기서 다른 공간과 다르게 계산을 해줘야 하는데요, Stack은 확장되는 방향이 반대방향이기 때문입니다. 따라서 그냥 더해주던 방식이 아닌 offset인 3KB에서 segment의 최대 크기인 4KB를 빼줘야 합니다. 따라서 -1KB가 실제 계산에 사용될 offset이 됩니다. stack의 Base인 28KB에 offset인 -1KB를 더해주면 됩니다. 즉 28KB + (-1KB) = 27KB가 실제 메모리의 주소가 되는 것입니다.

이때 아까 heap 예제에서 offset이 할당된 size를 넘어서면 segmentation fault를 발생시켰는데요, Stack의 경우엔 해당 검사를 실제 계산에 사용될 offset의 절댓값을 활용해서 계산하면 됩니다. 위 예제에서는 offset인 -1KB의 절댓값이 Stack의 Size인 2KB보다 작으니 segmentation fault는 발생하지 않겠네요.

Support for Sharing

Segmentation에 대한 지원이 증가함에 따라 시스템 설계자는 하드웨어 지원을 조금 더 추가하여 새로운 효율성을 실현하게 되었습니다. 예를 들어 동일한 프로그램을 사용한다고 가정하겠습니다. 동일한 프로그램은 Code부분이 동일합니다. 따라서 이 부분은 공유하는 것이 효율적일 수 있습니다. 그림으로 설명하겠습니다!

위와 같이 파워포인터로 2개의 프로젝트를 진행 중이라고 가정하겠습니다. 2개의 프로젝트는 서로 다른 데이터를 갖겠지만 이를 작성 중인 파워포인트는 동일한 프로그램입니다. 따라서 위와 같이 Code부분을 공유할 수 있습니다.

물론 이러한 메모리 공유를 지원하려면 하드웨어에서 추가적인 지원이 필요합니다. 이를 위해 읽기, 쓰기, 실행 가능 여부를 나타낼 수 있는 비트를 추가적으로 사용하게 됩니다.

위와 같이 추가적인 정보를 사용하려면 앞에서 알아본 하드웨어 알고리즘도 변경되어야 합니다. 특정 segment에서 허용된 작업 외의 작업을 시도한다면 예외가 발생해야 하며 이를 OS가 처리해줘야 합니다.

Fine-grained vs Coarse-grained Segmentation

지금까지는 3개의 segment만 존재하는 시스템만 고려했습니다. 그렇다면 size가 큰 소수의 segment를 사용하는 것이 좋을까요 아니면 size가 작은 다수의 segment를 사용하는 것이 좋을까요?

언제나 그렇듯 둘 다 장단점이 존재합니다. size가 큰 segment를 사용하면 segment의 수가 줄어들게 되어 관리가 편해지지만 다소 단순하게 구성할 수밖에 없습니다. size가 작은 segment를 사용하면 유연하게 메모리를 구성할 수 있지만 segment가 많기 때문에 관리가 힘들어질 수 있습니다.

OS Support

이제 segmentation의 원리와 하드웨어 지원에 대해 알게 되었습니다. 그렇다면 OS는 segmentation을 통해 주소변환을 할 때 언제 어떤 일을 해야 할까요? 우선 segmentation가 OS에게 주는 문제를 살펴보겠습니다.

첫 번째는 Context-Switch(문맥 교환) 문제입니다. Segmentation에서는 Context-Switch를 어떻게 처리해줘야 할까요? 이 문제는 항상 나오는 문제니 이제 어느 정도 아이디어가 떠오르지 않나요? 아마도 segment 레지스터의 값들을 저장하고 복원해 주는 방식으로 처리하면 될 것 같습니다.

두 번째는 segment의 수가 증가하거나 감소할 때 OS와의 상호작용 문제입니다. 예를 들어 프로그램은 객체를 할당하기 위해 malloc() 함수를 호출할 수 있습니다. 어떤 경우에는 기존 Heap이 이를 처리할 수 있기 때문에 malloc()은 객체의 여유 공간을 찾아 포인터를 반환합니다. 하지만 어떤 Heap segment에 공간이 부족할 경우 segment 자체가 커져야 할 수도 있습니다. 이러한 경우 라이브러리는 heap을 늘리기 위해 system call을 사용합니다. 이로 인해 더 많은 공간을 제공하고 segment Size를 수정한 뒤 라이브러리에 성공 여부를 알려줍니다. 물론 실제 메모리의 공간이 없다면 OS가 이를 거부할 수도 있습니다.

마지막은 바로 실제 메모리의 여유 공간을 관리하는 것(managing free space in physical memory)입니다. 새로운 주소 공간이 생성되면 OS는 해당 segment에 대한 실제 메모리의 공간을 찾아줘야 합니다. 프로세스마다 크기가 모두 다르기 때문에 각 segment의 크기도 모두 다릅니다. 이때 발생하는 문제는 실제 메모리에 존재하던 segment들이 확장할 수도 있고 너무 큰 여유공간에 작은 segment가 들어가서 효율적이지 못할 수 있는 문제가 발생합니다. 이를 external fragmentation(외부 단편화)라고 부릅니다. 예를 보며 이해해 보겠습니다.

위의 예에서 왼쪽 메모리에 20KB 크기를 갖는 segment를 할당하려고 합니다. 왼쪽 메모리의 여유 공간을 모두 합치면 24KB가 되지만 연속적으로 20KB 이상을 갖는 공간은 없습니다. 따라서 OS는 이 segment에게 메모리를 할당해 줄 수 없습니다. 이를 해결하기 위한 방법 중 하나는 메모리를 compact(압축)하여 공간을 확보하는 것입니다. 이를 적용한 것이 위의 그림에서 오른쪽 메모리입니다. 이렇게 하면 20KB 크기를 갖는 segment를 할당할 수 있게 됩니다. 하지만 압축에는 비용이 많이 들게 되고 기존에 존재하던 segment들이 메모리를 더 필요로 할 때 segment를 확장시켜 줄 수도 없습니다. 이런 요청을 처리하기 위해 또다시 재배치를 해야 할 수도 있는데 이는 새로운 비용을 발생하게 됩니다.

압축하는 방법 말고 더 간단한 방법은 할당에 사용할 수 있는 메모리 즉 여유공간을 관리하는 free-list management algorithm을 사용하는 것입니다. 여기에는 best-fit, worst-fit, first-fit과 같은 알고리즘을 포함하여 여러 가지 알고리즘이 존재합니다. 하지만 이것을 아무리 잘 만든다고 해도 외부 단편화를 없앨 수는 없습니다. 좋은 알고리즘을 사용해서 이를 최소화할 뿐이죠.

Summary

Segmentation은 여러 문제를 해결하고 보다 효과적인 메모리 가상화를 구축하는데 도움을 줍니다. 저번에 알아봤던 dynamic relocation에서 발생한 heap, stack 사이의 메모리 낭비를 segmentation로 해결할 수 있었습니다. 또한 주소 변환이 간단하고 동일한 프로그램은 code segment를 공유함으로써 메모리를 절약할 수도 있었습니다.

하지만 segmentation에도 문제점은 존재했습니다. segment의 size가 모두 다르기 때문에 external fragmentation(외부 단편화)가 발생할 수 있었고 segmentation이 여유 공간을 잘 처리하지 못한다는 점이었습니다. 다음 글에서는 이러한 여유 공간들을 어떻게 사용할지에 대해 알아보겠습니다.

감사합니다.