가상 메모리, 주소 바인딩, 메모리 할당

가상 메모리

가상 메모리는 메모리 관리 기법의 하나로, 각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다.

 

프로그램이 실행되면 프로그램의 모든 코드와 데이터는 가상 메모리에 할당된다. 가상 메모리는 추상화된 메모리 공간으로, 각 프로세스마다 가상 메모리를 갖는다. 그러나 가상 메모리에 할당된 코드와 데이터는 물리적 메모리에 로드될 때까지 실제 메모리에 존재하지 않는다. 

• 가상 주소(논리 주소): 가상적으로 주어진 주소
• 물리 주소(실주소): 실제 RAM 메모리 상에서의 주소

메모리 관리자(운영체제)는 프로그램을 물리적 메모리에 적재하기도 하고, 물리적 메모리 부족 시 스왑 영역으로 스왑 아웃시키기도 한다. 즉, 프로세스 입장에서는 물리적 메모리를 신경쓰지 않고 자신이 필요한 만큼 가상 주소 공간을 사용한다. 그리고 이 가상 주소 공간을 실제로 따져보면, 물리 메모리 + 스왑 영역인 것이다.

가상 메모리의 필요성

가상 메모리라는 개념은 왜 등장하게 되었을까?

• 물리적 메모리(RAM)의 한계 극복: 물리적 메모리 크기는 제한적이므로, 해당 메모리에 많은 프로그램을 동시에 실행하는 데에는 한계가 있다. 가상 메모리를 사용하면, 여러 프로세스를 동시에 실행할 때 모든 프로세스의 전체 내용을 RAM에 올려두지 않고, 필요한 부분의 코드와 데이터만 동적으로 RAM에 올려둘 수 있다. 따라서 물리적 메모리의 한계를 극복할 수 있다. 
• 보안(프로그램 간 메모리 보호): 가상 메모리는 각 프로세스에 독립된 주소 공간을 할당함으로써, 하나의 프로그램이 다른 프로그램의 메모리에 접근하는 것을 방지한다.
• 메모리 단편화 해결: 물리적 메모리 사용 중 발생하는 단편화를 줄이고, 메모리의 효율적 사용을 도모한다.

오버레이

위에서 가상 메모리를 통해 동적 로딩이 가능하다고 했다. 그런데 가상 메모리를 사용하지 않는 방법은 없었을까? 가상 메모리라는 개념이 등장하기 전에는 오버레이(overlay) 기법이 사용되었다. 오버레이는 프로그램을 여러 부분으로 나누고, 필요한 부분만 메모리에 로드하는 기법이다. 그런데 프로그램을 나누고 로드하는 등의 일을 프로그래머가 직접 했어야 했다. 즉, 가상 메모리와 오버레이의 차이점은 다음과 같다.

• 메모리 관리 주체
  • 오버레이: 프로그래머가 직접 프로그램을 분할하고, 필요한 부분만 메모리에 로드되도록 관리한다. -> 개발과 유지보수가 어렵다.
  • 가상 메모리: 운영체제가 자동으로 메모리를 관리하고, 페이지 폴트 발생 시 필요한 페이지를 로드한다. -> 프로그래머는 메모리 관리를 신경 쓸 필요가 없다.
• 유연성
  • 오버레이: 프로그램이 고정된 크기로 분할되어야 하므로 유연성이 떨어진다.
  • 가상 메모리: 프로그램이 실행 중에 필요한 만큼의 메모리만 사용하므로 유연성이 높다.

정리하자면, 가상 메모리 등장 전에는 오버레이 기법이 사용되었으며, 이는 프로그래머가 직접 프로그램을 분할하고 필요한 부분만 로드되도록 관리해야 했다. 반면, 가상 메모리는 운영체제가 메모리를 자동으로 관리하여, 프로그래머가 메모리 관리를 신경 쓸 필요가 없다. 

주소 바인딩

프로세스의 가상 주소는 프로세스가 실행되는 동안 일관되게 유지되지만, 해당 가상 주소가 물리적 메모리의 어디에 매핑되는지는 계속 변경될 수 있다. 이렇게 논리 주소를 물리 주소로 매핑하는 작업을 주소 바인딩이라고 한다. 

 

주소 바인딩은 시점에 따라 다음과 같이 나뉜다.

• 컴파일 타임 바인딩: 프로그램이 컴파일되는 시점에 물리적 메모리 주소가 결정된다. 이 방식에서 프로그램의 물리적 메모리 위치를 변경하고 싶으면 컴파일을 다시 하는 수고가 필요하다. 따라서 이 방식은 비현실적이고 현대의 시분할 컴퓨팅 환경에서 잘 사용하지 않는 기법이다.
• 로드 타임 바인딩: 프로그램이 실행되는 시점에 물리적 메모리 주소가 결정된다. 따라서 프로그램이 종료될 때까지 물리적 메모리 주소가 변하지 않는다.
• 실행시간 바인딩(런타임 바인딩): 프로그램의 실행이 시작된 후에도 물리적 메모리 주소가 변경될 수 있다. 따라서 CPU가 논리 주소를 참조할 때마다 해당 데이터의 물리 주소를 알아내기 위해 주소 바인딩을 거친다. 그리고 이때 논리 주소를 물리 주소로 매핑해주는 하드웨어 장치인 MMU(Memory Management Unit, 메모리 관리 장치)를 사용한다. 이때 MMU는 동적 주소 변환을 해주는 하드웨어 장치이다. 즉, 가상 메모리 내의 논리 주소를 물리적 메모리의 물리 주소로 변환하는 것을 의미한다. 

주소 바인딩 과정은 다음과 같다.

1. CPU가 논리 주소(346)을 요청한다(CPU는 논리 주소를 바라본다).
2. MMU는 논리 주소가 물리 주소의 어디(14346)에 매핑되는지 확인한다.
3. 접근하려는 물리 주소가 해당 사용자 프로그램이 접근 가능한 범위인지 확인한다.
   • 이때 기준 레지스터와 한계 레지스터가 사용된다.
     • 기준 레지스터(base register): 어떤 프로그램이 수행되는 동안 그 프로그램이 합법적으로 접근할 수 있는 메모리상의 가장 작은 주소를 보관한다.
     • 한계 레지스터(limit register): 그 프로그램이 기준 레지스터 값으로부터 접근할 수 있는 메모리의 범위를 보관한다.
   • 즉, 사용자 프로그램의 기준 레지스터가 14000이고 한계 레지스터가 3000이라면, 사용자 프로그램이 접근할 수 있는 범위는 14000 ~ 17000이다. 즉, 사용자 프로그램은 14346에 접근할 수 있다.
4. 사용자 프로그램이 해당 물리 주소에 접근이 가능하면 MMU는 물리 주소를 반환하여 메모리 접근이 이뤄진다. 반면, 사용자 프로그램이 해당 물리 주소에 접근이 불가능하면 악의적인 접근이라고 판단되어 소프트웨어 인터럽트인 트랩을 발생시킨다.

즉, 위 과정을 보면 프로세스는 물리 메모리에 직접 접근할 수 없으며, MMU를 통해 접근하려는 논리 주소에 해당하는 물리 주소를 받아온다. 그리고 이때 해당 프로세스가 해당 물리 주소에 접근 가능한지 접근 권한을 확인받는다. 즉, 가상 메모리라는 개념을 통해 각 프로세스는 접근하려는 물리 주소의 접근 권한을 MMU로부터 확인 받아, 보안이 이뤄지는 것이다.

메모리 할당 방식

물리적 메모리는 운영체제의 영역과 사용자 프로세스의 영역으로 나뉜다. 물리적 메모리의 낮은 주소 영역에는 운영체제 커널이 위치하게 된다. 반면 물리적 메모리의 높은 주소 영역에는 여러 사용자 프로세스들이 위치한다. 그리고 사용자 프로세스 영역의 관리 방법은 프로세스를 메모리에 올리는 방식에 따라 연속 할당 방식과 불연속 할당 방식으로 나뉜다. 

연속 할당 방식

연속 할당 방식은 하나의 프로세스를 메모리에 올릴 때 물리적 메모리의 한 곳에 연속적으로 적재하는 방식이다. 그리고 이때 물리적 메모리를 고정된 크기의 분할로 미리 나누어 놓는지 그렇지 않은지에 따라 고정분할 방식과 가변분할 방식으로 나뉜다.

고정분할 방식

• 고정분할 방식은 물리적 메모리를 주어진 개수만큼 미리 나누어두고, 각 분할에 하나의 프로세스를 적재해 실행시키는 방식이다. 이때 분할된 메모리의 크기는 모두 동일하게 할 수도 있고 서로 다르게 할 수도 있다. 단, 하나의 분할에는 무조건 하나의 프로그램만 적재할 수 있다. 
• 단점
  • 동시에 메모리에 올릴 수 있는 프로그램의 수와 최대 크기가 제한된다는 점에서 가변분할 방식에 비해 융통성이 떨어진다.
  • 외부 조각이 발생할 수 있다. 이는 프로그램의 크기보다 분할의 크기가 작은 경우 해당 분할이 비어 있는데도 불구하고 프로그램을 적재하지 못하기 때문에 발생하는 메모리 공간을 말한다. 즉 외부 조각은 어떠한 프로그램에게도 배정되지 않은 빈 공간임에도 현재 상태에서 사용될 수 없는 작은 분할을 말한다. 만약 이 외부조각보다 크기가 작은 프로그램이 도착한다면 그 프로그램을 외부조각에 적재시킬 수 있다. 
  • 내부 조각이 발생할 수 있다. 이는 프로그램의 크기보다 분할의 크기가 큰 경우 해당 분할에 프로그램을 적재하고 남는 메모리 공간을 뜻한다. 즉 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 공간을 말한다. 내부조각은 이미 특정 프로그램이 배당된 공간이므로 내부조각에 수용할 수 있는 충분히 작은 프로그램이 있다고 해도 해당 공간을 활용할 수 없다. 

가변분할 방식

• 가변분할 방식은 프로그램의 크기를 고려하여 분할의 개수와 크기가 동적으로 변하는 방식이다.
• 장점
  • 분할의 크기를 일부러 프로그램의 크기보다 크게 할당하지는 않기 때문에 내부조각이 발생하지 않는다.
• 단점 
  • 프로그램이 종료되고 메모리를 반납할 경우, 해당 프로그램의 크기만큼 빈 공간이 발생하게 되며, 이 공간이 새롭게 시작되는 프로그램의 크기보다 작을 경우 외부조각이 발생할 가능성이 있다.
  • 동적 메모리 할당 문제가 발생한다. 이는 특정 프로세스의 주소 공간의 크기가 n일 때 물리적 메모리의 가용 공간 중 어디에 프로세스를 올릴 것인지 결정하는 문제이다. 물리적 메모리 내에 존재하는 다양한 크기의 가용 공간 중 새로운 프로세스를 올릴 수 있는 공간을 찾아야 하는데, 운영체제는 이미 사용 중인 메모리 공간과 사용하고 있지 않은 가용 공간에 대한 정보를 각각 유지하고 있다. 동적 메모리 할당 문제를 해결하는 대표적인 방법으로는 세 가지가 있다.
    • 최초적합 방법
      • 크기가 n 이상인 가용 공간 중 가장 먼저 찾아지는 곳에 프로세스를 할당하는 방법이다.
      • 이 방법은 가용 공간을 모두 탐색하지 않고 최초로 발견되면 프로그램을 즉시 올리므로, 시간적인 측면에서 효율적이다.
    •  최적적합 방법
      • 크기가 n이상인 가장 작은 가용 공간을 찾아서 그곳에 프로세스를 할당하는 방법이다.
      • 이 방법은 가용 공간들의 리스크가 크기순으로 정렬되어 있지 않으면 모든 가용 공간을 탐색해야 하므로 시간적인 측면에서 비효율적이다. 그러나 공간적인 측면에서 효율적이다.
    • 최악적합 방법
      • 가용 공간 중에서 가장 크기가 큰 곳에 프로세스를 할당하는 방법이다.
      • 이 방법도 가용 공간들의 리스크가 크기순으로 정렬되어 있지 않으면 모든 가용 공간을 탐색해야 하므로 시간적인 측면에서 비효율적이다. 또한 상대적으로 더 큰 프로그램을 담을 수 있는 가용 공간을 빨리 소진한다는 문제가 있다.
• 컴팩션: 가변분할 방식에서 발생하는 외부조각 문제를 해결하기 위한 방법으로, 물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한쪽으로 몰아 가용 공간들을 다른 한쪽으로 모아서 하나의 큰 가용 공간을 만드는 방법이다. 그러나 이는 현재 수행 중인 프로세스의 메모리 위치를 이동시켜야 하므로 비용이 매우 많이 드는 작업이다. 또한 실행 중에 프로세스의 메모리 주소를 변경할 수 있는 실행시간 바인딩 방식이 지원되는 환경에서만 가능하다.

불연속 할당 방식

불연속 할당 방식은 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 적재되는 할당 기법이다. 그리고 이때 하나의 프로그램을 분할하는 방식에는 동일한 크기로 나누는 페이징 기법, 크기는 일정하지 않지만 의미 단위로 나누는 세그먼테이션 기법, 그리고 세그먼테이션 기법을 기본으로 하되 이를 다시 동일 크기의 페이지로 나누는 페이지드 세그먼테이션 기법 등이 있다. 

페이징 기법

• 논리적 메모리를 동일 크기의 페이지로 나눈다. 그리고 물리적 메모리를 페이지와 동일한 크기의 프레임으로 나눈다.
• 즉, 프로세스의 논리적 주소 공간과 물리적 메모리 공간이 모두 같은 크기의 페이지/프레임 담위로 나누어지기 때문에 물리적 메모리 공간의 어느 곳이든 활용할 수 있다.
• 장점
  • 동적 메모리 할당 문제와 외부 조각이 발생하지 않는다.
• 단점 
  • 프로그램의 크기가 항상 페이지 크기로 정확히 나누어 떨어지지 않을 수 있기 때문에 프로세스의 논리적 주소 공간 중 제일 마지막에 위치한 페이지에서는 물리적으로 내부조각이 발생할 수 있다.
  • 페이징 기법은 하나의 프로세스라 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 상이하다. 따라서 주소 바인딩 작업이 페이지 단위로 이루어지기 때문에 주소 바인딩 과정이 연속할당 방식에 비해 복잡하다. 즉, 하나의 프로세스에서도 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 물리적 주소 변환 정보를 갖고 있어야 한다. 따라서 페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블을 가지며, 이 테이블은 프로세스가 가질 수 있는 페이지 개수만큼 주소 변환 엔트리를 가지고 있다. 
• 페이지 테이블
  • 각 페이지의 논리 주소에 따른 프레임의 물리 주소를 갖는 테이블로, 각 프로세스마다 페이지 테이블을 갖는다.
  • 페이지 테이블은 메인 메모리에 위치한다.
  • 페이지 테이블은 페이지의 논리 주소가 인덱스가 된다. 따라서 인덱스인 논리 주소를 통해 O(1)의 시간으로 찾고자 하는 엔트리를 찾을 수 있다.

• TLB
  • 모든 메모리 접근 연산에는 메모리 접근이 총 2번 필요하다(페이지 테이블 접근, 실제 데이터 접근). 따라서 이러한 성능 저하를 막기 위해 주소 변환을 전담하는 캐시 메모리를 사용한다. 이를 TLB라고 한다.
  • 즉, 메모리 내의 페이지 테이블을 통해 주소 변환을 하지만, 그 중 일부는 TLB라는 캐시 메모리에 저장되어 있어서 더 빠르게 주소 변환을 할 수 있다.
  • TLB는 모든 정보가 담겨 있지 않기 때문에 페이지의 논리 주소가 인덱스가 될 수 없다. 즉, 페이지의 논리 주소와 프레임의 물리 주소가 함께 담겨 있다. 따라서 TLB에서는 인덱스로 엔트리를 조회할 수 없기 때문에 모든 엔트리를 순회해야 한다.
  • 그런데 이는 매우 비효율적이기 때문에 각 엔트리를 병렬적으로 조회할 수 있는 하드웨어인 associative register를 사용한다.
  • context switch가 발생하면 TLB의 모든 엔트리가 지워진다. 각 프로세스마다 논리 주소를 갖기 때문에 프로세스 A의 0번지와 프로세스 B의 0번지는 다르며 구분해야 하기 때문이다.

세그먼테이션 기법

• 세그먼테이션 기법은 프로세스의 주소 공간을 의미 단위의 세그먼트로 나누어 물리적 메모리에 올리는 방법이다.
• 프로세스의 주소 공간 전체를 하나의 세그먼트로 볼 수도 있으며, 일반적으로는 코드, 데이터, 스택 등의 기능 단위로 세그먼트를 정의한다. 혹은 프로그램을 구성하는 함수 하나하나를 각각의 세그먼트로 정의할 수도 있다.
• 결론적으로 세그먼트는 논리적인 단위로 나눈 것이기 때문에 그 크기가 균일하지 않다. 따라서 크기가 균일하지 않은 세그먼트들을 메모리에 적재하는 부가적인 오버헤드가 발생한다. 

페이지드 세그먼테이션 기법

• 이 기법은 세그먼테이션 기법과 마찬가지로 프로그램을 의미 단위인 세그먼트로 나눈다. 단 세그먼트가 임의의 길이를 가질 수 있는 것이 아니라 반드시 동일한 크기 페이지들의 집합으로 구성되어야 한다. 그리고 물리적 메모리에 적재하는 단위는 페이지 단위로 한다. 
• 즉, 하나의 세그먼트 크기를 페이지 크기의 배수가 되도록 하여, 세그먼테이션 기법에서 발생하는 외부조각의 문제점을 해결한다. 그리고 세그먼트 단위로 적재함으로써 페이징 기법의 약점을 해소한다. 

---

Reference

• 이화여자대학교출판문화원, 운영체제와 정보기술의 원리, 반효경