[운영체제] 메모리 가상화에 관해 1 - Base and Bound 부터 Segmentation까지

주소 공간 (Address Space)이란?

여러 프로그램이 메모리에 동시에 존재하려면 보호(protection)가 중요한 문제가 된다.

운영체제는 사용하기 쉬운 메모리 개념을 만들어야 한다. 이 개념이 주소 공간이다.

주소 공간은 실행 중인 프로그램이 가정하는 메모리의 모습이다. 여기에는 실행 프로그램의 모든 메모리 상태가 존재한다. 프로그램의 코드는 반드시 메모리에 존재해야 하고 따라서 주소 공간에 존재한다. 스택은 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자와 반환 값 등을 저장하는데 사용된다. 힙(heap)은 동적으로 할당되는 메모리를 위해 사용된다. malloc() 또는 객체 지향 언어의 new를 통해 메모리를 동적으로 할당받는다.

프로그램 코드는 정적이기 때문에 저장하기 쉽다. 그래서 할당된 주소 공간의 0KB부터 시작하는 상단에 배치한다. 남은 공간은 프로그램 실행과 더불어 확장되거나 축소될 수 있는 두 종류의 주소 공간으로 나눈다. 상단에 존재하는 힙과 하단에 존재하는 스택이다. 힙은 아래쪽으로 확장하고, 스택은 위쪽으로 확장한다.

실제 프로그램이 물리 주소 0부터 존재하는 것이 아니다. 이는 운영체제가 실행 중인 프로그램에게 제공하는 가상의 메모리 공간이다 (virtualizing memory).

메모리 가상화의 목표

가상 메모리 시스템(VM)의 주요 목표 중 하나는 투명성(transparency)이다. 운영체제는 실행 중인 프로그램이 가상 메모리의 존재를 인지하지 못하도록 가상 메모리 시스템을 구현해야 한다. 오히려 프로그램은 자신이 전용 물리 메모리를 소유한 것처럼 행동해야한다. 그래서 많은 작업들이 물리 메모리를 공유할 수 있도록하는 것이 목표다.

또 다른 목표는 효율성(efficiency)이다. 운영체제는 가상화가 시간과 공간 측면에서 효율적이도록 해야한다. 이를 위해 운영체제는 TLB 등의 하드웨어 기능을 포함하여 하드웨어의 지원을 받아야한다.

마지막 세 번째 목표는 보호(protection)이다. 운영체제는 프로세스를 다른 프로세스로부터 보호해야 하고 운영체제 자신도 프로세스로부터 보호해야한다. 즉, 자신의 주소 공간 밖의 어느 것도 접근할 수 있어서는 안 된다. 이를 위해 프로세스들을 서로 고립(isolate) 시킬 수 있다.

어떻게 메모리를 관리해야하는가?

메모리 공간의 종류

스택 메모리는 할당과 반환이 컴파일러에 의해 암묵적으로 이루어진다.

오랫동안 값이 유지되어야 하는 변수를 위해 힙 메모리가 있다. 모든 할당과 반환이 프로그래멍에 의해 명시적으로 처리된다.

malloc( ) 함수

메모리 할당을 운영체제에게 요청하는 C의 함수이다.

malloc( )의 인자는 요청하는 바이트 크기이다. 요청한 크기만큼 힙 영역에 메모리를 할당하고 할당된 메모리의 시작 주소를 가리키 포인터를 반환한다.

free( ) 함수

할당된 힙 메모리를 해제하는 함수이다.

free() 함수가 해제할 크기를 알 수 있는 방법은 malloc이나 alloc 함수가 메모리를 할당할 때 메타데이터를 함께 저장하기 때문이다.

메타데이터는 ‘데이터에 대한 데이터’를 의미한다. 힙 메모리 관리자는 메모리를 할당할 때 사용자가 요청한 크기보다 조금 더 큰 공간을 할당한다. 이 추가 공간에 할당된 블록에 대한 정보를 저장한다.

일반적인 메타데이터는 다음과 같은 정보를 포함한다.

• 할당된 메모리 블록의 크기(size): 가장 중요한 정보다. free 함수가 정확히 얼마만큼의 메모리를 해제해야 하는지 알려준다.
• 다음 또는 이전 블록의 주소: 빈 공간들을 연결 리스트로 관리할 때 사용된다.
• 할당 상태: 현재 블록이 사용 중인지 비어있는지 알려주는 플래그.

  운영체제의 지원

malloc()과 free()는 라이브러리 함수이다. 운영체제에게 시스템 콜을 날려서 메모리를 할당받고 해제하는 것이다.

brk라는 시스템 콜도 존재하는데, 프로그램의 break 위치를 변경하는 데 사용된다.

여기서 break는 힙의 마지막 위치를 나타낸다.

주소 변환 (Address translation)의 원리

운영체제는 가상화를 제공하는 동시에 효율성과 제어(control) 모두를 추구한다. 효율성을 높이려면 하드웨어 지원을 활용할 수밖에 없다. 레지스터부터 시작해서 TLB, 페이지 테이블 등으로 점차 복잡한 하드웨어를 사용하게 된다. 제어는 응용 프로그램이 자기자신의 메모리 이외에는 다른 메모리에 접근하지 못한다는 것을 운영체제가 보장하는 것을 의미한다. 이를 위해서도 하드웨어 도움이 필요하다.

마지막으로 유연성(flexibility) 측면에서 VM 시스템에서 필요한 것은 어떻게 효율적이고 유연하게 메모리를 가상화할지이다.

이번에 다룰 기법은 하드웨어-기반 주소 변환, 짧게 주소 변환이다. 주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제 존재하는 물리 주소로 변환한다. 이 때, 운영체제는 정확한 변환이 일어날 수 있도록 하드웨어를 설정하기 위해 메모리의 빈 공간과 사용 중인 공간을 항상 알고 있어야한다.

이를 통해 프로그램이 자신의 전용 메모리를 소유하고 있고 그 안에 자신의 코드와 데이터가 있다고 믿게 만드는 것이 목표이다.

가정 : 사용자 주소 공간은 물리 메모리에 연속적으로 배치되어야 한다. 주소 공간의 크기는 물리 메로리 크기보다 작다. 각 주소 공간의 크기는 같다고 가정한다.

동적 재배치 - 베이스와 바운드

CPU마다 베이스(base) 레지스터, 바운드 (bound) 레지스터 라는 2 개의 하드웨어 레지스터가 필요하다.

운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정한다.

프로세스가 실행되면 프로세스에 의해 생성되는 모든 주소가 베이스 레지스터를 더하여 변환된다.

physical address = virtual address + base

바운드 레지스터는 보호를 지원하기 위해 존재한다. 바운드 레지스터에는 할당된 크기로 설정되어 범위를 나타낸다. 프로세스가 바운드보다 큰 가상 주소 또는 음수인 가상 주소를 참조하면 CPU는 예외를 발생시키고 프로세스는 종료된다.

동적 재배치는 비효율적인 방법이다. 할당된 메모리 공간에서 스택과 힙 사이의 공간이 낭비되고 있기 때문이다. 이를 내부 단편화라고 한다.

더 효율적인 방법으로는 베이스 앤 바운드를 일반화한 세그멘테이션 기법이 존재한다.

세그멘테이션

아이디어는 하나의 베이스와 바운드 쌍만 존재하는 것이 아니라 주소 공간의 논리적인 세그먼트(segment)마다 베이스와 바운드 쌍이 존재하는 것이다. 예를 들어 코드, 스택, 힙 세 종류의 세그먼트가 주소 공간에 존재하면, 3개 베이스와 바운드 쌍이 존재한다.

예를 들어, 가상 주소 100번지는 코드 세그멘트에 속한다. 참조가 일어나면 하드웨어는 베이스 값에 이 세그먼트의 오프셋(100)을 더해 물리 주소는 100 + 32KB = 32868이된다. 그 후 주소가 범위(2KB) 내에 있는지 검사하고, 범위 내에 있을 경우 물리 메모리 주소 32868을 읽는다.

4200의 힙 영역을 읽을 경우, 힙의 베이스에 4200을 더하는 것이 아니라 힙 세그멘트가 시작하는 4KB를 뺀 4200-4096 = 104인 오프셋(offset)을 더해야한다.

세그멘트 종류의 파악

하드웨어는 가상주소가 어느 세그멘트를 참조하는지, 오프셋은 얼마인지를 어떻게 알 수 있을까?

한 가지 방법으로는, 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그멘트로 나누느 것이다.

위의 예에서는 최상위 2비트를 사용하여 00으로 시작하면 프로그램 코드, 01로 시작하면 4KB부터 시작하므로 힙 세그멘트, 11이면 스택 세그멘트라고 인지할 수 있다. 그 아래 비트는 오프셋(offset)이 된다.

하지만 이 방법은 전체 주소 공간의 1/4은 사용이 불가능하다. 이 문제르 해결하기 위해 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하고 세그멘트 선택을 위해 1비트만 사용한다.

스택

위의 예에서 스택은 다른 세그멘트들과는 달리 반대 방향으로 확장된다.

따라서 다른 방식의 변환이 필요하다.

첫 번째로 간단한 하드웨어가 추가로 필요하다. 어느 방향으로 확장하는지를 알리기 위해 1비트가 필요하다.

스택은 올바른 음수 오프셋을 얻기 위해 상위 2비트를 뺀 오프셋에서 세그멘트 최대 크기를 빼야한다.

바운드 검사는 오프셋의 절댓값이 세그멘트의 크기보다 작다는 것을 확인하여 계산한다.

세그멘테이션에서 발생한 새로운 문제

첫 번쨰 문제는, 문맥 교환 시 운영체제가 세그멘트 레지스터의 저장과 복원을 할 때 일어난다. 크기는 크지만 드문드문 사용되는 힙이 하나의 논리적인 세그멘트에 배정되어 있다고 할 때 이 힙에 접근하기 위해서는 힙 전체가 여전히 물리 메모리에 존재해야한다. 즉 주소 공간이 사용되는 모델과 이를 지원하기 위한 세그멘테이션의 설계방법이 정확히 일치하지 않는다면, 세그멘테이션은 제대로 동작하지 않는다.

두 번째 문제는 미사용 중인 물리 메모리 공간의 관리이다. 새로운 주소 공간이 생성되면 운영체제는 이 공간의 세그멘트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 한다.

물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워지는 것이 일반적인 문제이다. 이렇게 해서 생기는 작은 빈 공간들은 새로 생겨나는 세그멘트에 할당하기도 힘들고, 기존 세그멘트를 확장하는 데도 도움이 되지 않는다. 이를 외부 단편화 (external fragmentation) 이라 부른다.

이 문제의 해결책 중 한 가지는 기존의 세그멘트를 정리하여 물리 메모리를 압축하는 것이다. 하지만 세그멘트 복사는 메모리에 부하가 크고 긴 프로세서 시간을 사용하기 때문에 비용이 많이 든다.

다른 방법들로는 빈 공간 알고리즘으로 할당 가능한 메모리 영역들을 리스트 형태로 유지하는 것이다. 이를 위한 최적 적합, 최악 적합, 최초 적합, 버치 알고리즘 등 수많은 방식이 존재하지만, 수 많은 해결책이 존재한다는 것은 최선의 해결책이 존재하지 않는다는 것을 의미한다. 따라서 새로운 방식으로 메모리를 관리하는 방법이 필요하다.

페이징 개요

운영체제는 거의 모든 공간 관리 문제를 해결할 때 두 가지 중 하나를 사용한다.

첫 번째 방법은 세그멘테이션처럼 가변크기의 조각들로 분할하는 것이지만, 이는 태생적인 문제를 가진다.

두 번쨰 방법은 공간을 동일 크기의 조각으로 분할하는 것이다. 가상 메모리에서 이를 페이징(paging)이라 부른다. 프로세스의 주소 공가늘 몇 개의 가변 크기의 논리 세그멘트로 나누는 것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(page)라고 부른다. 상응하여 물리 메모리도 페이지 프레임 (page frame)이라고 불리는 고정 크기의 슬롯의 배열이라고 생각한다. 이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다.

페이징은 이전 방식에 비해 많은 장점을 가지고 있다. 가장 중요한 개선은 유연성이다. 페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 된다!

또 다른 장점은 페이징이 제공하는 빈 공간 관리의 단순함이다.

주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스 마다 페이지 테이블 (page table) 이라는 자료 구조를 유지한다. 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장하는 것이다. 각 페이지가 저장된 물리 메모리의 위치가 어디인지 알려준다. 이러한 페이지 테이블은 프로세스마다 존재한다. 프로세스를 새로 실행해야 한다면, 운영체제는 이 프로세스를 위한 다른 페이지 테이블이 필요하다. 새 프로세스의 가상 페이지는 다른 물리 페이지에 존재하기 떄문이다.

Reference

• Operating Systems: Three Easy Pieces (OSTEP) by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau