Memory Management 1.

게시: February 14, 2022
수정: February 16, 2022

메모리는 주소를 통해 접근하는 매체로 프로그램이 실행되려면 논리적인 주소(Logical Address)의 값이 물리적인 주소(Physical address)에 올라가야 한다. Memory Management 파트에서는 이와 같이 프로세스를 물리적인 메모리에 할당하고 관리하는 방법에 대하여 다룬다.

주소 바인딩(Address Binding)이란?

프로그램이 실행되려면 프로그램이 컴퓨터 메모리 어디에 올라갈지 메모리 주소를 결정되어야 한다. 즉, 논리적 주소(Logical address)를 물리적 주소(Physical address)로 주소 변환해주어야 하는데 이와 같이 주소를 결정(변환)하는 것을 주소 바인딩이라고 한다.

Symbolic Address: 코딩 시 직접 논리적 주소(메모리 번지수)를 지정하기 보단 변수를 선언하여 메모리를 할당하는데 이처럼 직접적인 메모리 주소 대신 변수로 선언한 것(주소)을 말한다.
Logical Address(= Virtual Address): 프로세스마다 독립적으로 가지는 주소 공간(Address space)으로 CPU가 보는 주소이다.^[1] 각 프로세스마다 0번지부터 시작한다.
Physical Address: 실제 물리적인 메모리에 올라가는 위치(주소)이다. 하위 주소 부분에는 운영체제(Kernel)가 올라가고, 상위 주소 부분에는 여러 프로그램들이 올라간다.

Binding Process
Symbolic Address → Logical Address(Compiled) → Physical Address

바인딩 시점

각 프로그램이 가진 논리적 주소(Logical Address)가 물리적 메모리 주소(Physical Address)로 결정되는 시점이 언제인가에 따라 3가지로 나뉜다.

Compile Time Binding: 컴파일할 때 물리적 메모리 주소가 결정된다. 메모리에 올라갈 위치를 변경하려면 다시 컴파일해야 한다. 컴파일러는 절대 코드(Absolute code)를 생성한다.
Load Time Binding: 실행할 때 결정된다. Loader의 책임하에 물리적 메모리 주소가 부여된다. 메모리 주소를 변경하려면 다시 실행해야 한다. 컴파일러가 재배치 가능코드(Relocatable code)를 생성한 경우에 가능하다.
Execution Time Binding(Runtime Binding): 시작된 이후에도 중간에 변할 수 있다. CPU가 메모리 주소를 요청할 때마다 바인딩을 점검(Address mapping table)한다. 하드웨어적인 지원(MMU)가 필요하다. 현대적인 컴퓨터 시스템이 이에 해당한다.

MMU (Memory-Management Unit)

주소 변환을 위한 하드웨어이다. 논리적 주소(Logical address)를 물리적 주소(Physical address)로 매핑(Mapping)해주는 역할을 한다. 2개의 레지스터(Relocation register, Limit register)로 구성되어 있다.

Relocation Register(Base Register): 물리적 메모리에서 프로세스의 시작 위치 값을 나타낸다. 접근할 수 있는 물리적 메모리 주소의 최소값을 나타내는 레지스터이다.
Limit Register: 프로그램의 최대 크기를 나타낸다. 논리적 주소의 범위를 나타내는 레지스터이다. 소프트웨어가 인스트럭션을 통해서 지정된 범위를 넘어서는 주소하는 요청하는 악의적인 시도를 막는다. 즉, 다른 프로그램에 접근하는 것을 차단한다.

사용자 프로세스가 CPU에서 수행되면서 생성해내는 모든 주소값에 대해 Base register의 값을 더하여 물리적 주소를 매핑한다. (e.g. Logical 346, Relocation Regi. 14,000 → Physical 14,346)

Allocation of Physical memory (How to manage physic mem?)

물리적 메모리의 낮은 주소 영역에는 운영체제 커널이 상주하고 높은 주소 영역에는 사용자 프로그램들이 올라가는데 사용자 프로세스 영역을 관리하는 방법은 크게 2가지(연속 할당, 불연속 할당)으로 나눌 수 있다.

1. 연속 할당 (Contiguous Allocation)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것을 말한다. 쉽게 말해 프로그램이 메모리에 올라갈 때 통째로(~~앗세이~~)로 올라가는 것이 연속 할당이다. 후술할 이런저런 비효율적인 특징 때문에 현대적인 컴퓨터 시스템에서는 잘 쓰이지 않는다.

연속 할당은 다시 한 번 고정 분할(Fixed Partition)방식과 가변 분할(Variable Partition) 방식으로 나뉘는데 당연히 가변 분할이 고정 분할보다 더 진보된 방식이다.

1.1. 고정 분할(Fixed Partition Allocation)

물리적 메모리를 몇 개의 영구적인 분할(Partition)로 나누는 방식이다. 분할(Partition)당 하나의 프로그램을 적재한다. 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다. 동시에 메모리에 로딩되는 프로그램의 수가 고정되며 최대 수행 가능 프로그램의 크기가 제한되어 융통성이 없으며 내부 조각 또는 외부 조각 문제가 발생한다.

외부 조각(External Fragmentation): 프로그램 크기보다 분할의 크기가 작은 경우. 즉, 분할된 공간보다 프로그램의 크기가 커서 사용되지 않는 공간으로 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할(Partition)을 말한다.
내부 조각(Internal Fragmentation): 프로그램 크기보다 분할의 크기가 큰 경우. 분할된 공간에 비해서 프로그램의 크기가 작아서 남는 공간이다. 하나의 분할(Partition) 내부에서 발생하는 사용되지 않는 메모리 조각을 말한다. 특정 프로그램에 배정되었지만 사용되지 않는 공간이다.

1.2. 가변 분할 (Variable Partition Allocation)

고정 분할 방식과 달리 미리 분할하지 않고 프로그램이 실행되면 프로세스를 메모리에 차곡차곡 쌓아 올리는 방식이다. 프로그램의 크기를 고려해서 할당해야 하며 분할(Partition)의 크기와 개수가 동적으로 변한다. 기술적인 관리 기법이 필요한 방식이다.

예를 들어 프로그램 A가 끝나면 A의 주소 공간만큼 빈 공간이 생긴다. 이후 실행되는 B의 주소 공간이 이전 프로그램보다 작거나 같으면 해당 빈 공간을 사용하면 그만이지만, 만약 그렇지 않으면 다른 주소를 할당해야 하고 남은 해당 빈 공간은 외부 조각(홀, Hole)이 되기 때문에 기술적 관리 기법이 필요한 것이다.

1.2.1. 홀(Hole)

가용 메모리 공간을 말한다. 다양한 크기의 Hole들이 메모리 여러 곳에 흩어져 있으며 할당 공간, 가용 공간(Hole)을 유지하며 프로세스가 도착하면 수용가능한 Hole을 할당한다. 이때 어느 홀에 사이즈가 \(n\)인 새로운 프로그램을 할당하는 것이 가장 적절한지 결정하는 문제를 Dynamic Storage-Allocation Problem이라고 하며, 홀을 한 군데로 모는 것을 Compaction이라 한다.

Dynamic Storage-Allocation Problem: 가변 분할 방식에서 \(size n\)인 요청을 만족하는 가장 적절한 홀(Hole)을 찾는 문제이다. 실험적으로 First-fit과 Best-fit이 Worst-fit 보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려져 있다.
1. First-fit: \(size\ n\) 이상인 것 중 최초로 찾아지는 홀에 할당 (시간 복잡도 ↓)
2. Best-fit: \(size\ n\) 이상인 가장 작은 홀을 찾아서 할당 (공간 복잡도 ↓). 홀들의 리스트가 크기 순으로 정렬되어 있지 않은 경우 모든 홀의 리스트를 탐색해야 한다. 많은 수의 아주 작은 홀들이 생성된다.
3. Worst-fir: 가장 큰 홀에 할당. 모든 리스트를 탐색해야 하며 상대적으로 아주 큰 홀들이 생성된다. 실험적인 결과상 가장 비효율적인 것으로 알려져 있다.
Compaction: 사용 중인 메모리 영역을 한 군데로 몰고 홀들을 다른 한 곳으로 몰아 큰 블록(Block)을 만드는 것이다. 즉, 중간중간 작은 홀을 한 군데로 밀어서 하나의 큰 홀을 만드는 것을 말한다. 메모리 버전의 디스크 조각 모음이라고 할 수 있다.
- Cost가 매우 큰 방법이다.
- 매우 복잡하다. 실행중인 프로그램의 메모리 영역을 바인딩을 고려해서 밀어야 하고 최소한의 메모리 이동으로 Compaction 하는 방법을 찾아야 하므로 매우 Complexity하다.
- 프로세스의 주소가 실행 시간에 동적으로 재배치가 가능한 경우에만 수행할 수 있다. 즉, 메모리 위치를 실행중에 변경할 수 있어야 한다.

2. 불연속 할당 (Non-contiguous Allocation)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것을 말한다. 쉽게 말해 하나의 프로그램을 구성하는 주소 공간을 잘게 쪼개서 메모리 여기저기에 올리는 것이 불연속 할당이다. 현대적인 시스템에서는 불연속 할당을 채택하고 있다.^[2]

방법으로는 크게 페이징(Paging) 기법과 세그멘태이션(Segmentation) 기법으로 나뉜다.

2.1. 페이징 (Paging)

하나의 프로그램을 구성하는 주소 공간을 같은 크기의 페이지(Page)로 쪼개서 페이지 단위로 물리적인 주소에 올리거나 Backing store에 내리는 기법이다. 페이지가 들어갈 수 있도록 물리적인 메모리의 사용자 프로그램이 올라갈 수 있는 공간도 페이지 크기로 미리 쪼개 놓는데 이 물리적인 공간을 페이지 프레임(Page Frame)이라고 한다.

페이지는 비어 있는 페이지 프레임 아무 곳이나 들어갈 수 있기 때문에 가변 분할 방식을 사용했을 때 발생하는 Hole Dynamic Storage-Allocation Problem이나 Compaction 문제를 해결할 수 있다.

다만 주소 변환이 복잡해진다. 연속 할당은 시작위치만 알면 쉽게 주소 변환을 할 수 있지만 페이징 기법을 사용하면 페이지 단위로 주소 변환을 해야하기 때문에 주소 바인딩 과정이 복잡해지는 것이다.

또한 External Fragmentation은 없지만 Internal Fragmentation^[3]은 발생 가능한 특징이 있다.

2.2. 세그멘테이션 (Segmentation)

무조건 같은 크기로 자르는 페이징 기법과 달리 어떠한 의미 단위로 자르는 기법이다. 예를 들어 주소 공간을 구성하는 코드(Code), 데이터(Data), 스택(Stack)을 기준으로 각 세그먼트를 나눌 수 있다.^[4] 각각의 세그먼트는 필요 시 물리적인 메모리에 올린다.

각 세그먼트가 같은 크기일 것이라는 보장이 없기 때문에 크기가 균일하지 않다. 따라서 세그멘테이션 기법을 써도 Dynamic Storage-Allocation Problem은 발생한다.

Some Terminologies

마지막으로 몇 가지 용어에 대해서 정리하는 것으로 포스팅을 마친다.

1. Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 로딩하는 방법을 말한다. 모든 코드를 올려놓지 않고 그때그때 필요한 코드만 로딩하는 방법이다.

모든 코드를 메모리에 올려놓으면 공간이 비효율적 사용되기 때문에 예외처리 루틴 등 가끔씩 사용되는 많은 양의 코드의 경우 유용하다. 또한 Memory utilization(메모리 이용률)이 향상된다.

정확하게는 프로그래머가 운영체제의 라이브러리를 활용하여 명시적으로 구현하는 것만을 Dynamic loading이라고 한다. 하지만 현대적인 운영체제의 페이징 시스템을 통하여 프로그램에서 필요한 부분만 메모리에 올리고 필요 없는 부분을 내리는 것도 포괄적으로 Dynamic loading이라 부른다.

2. Overlays (Manual Overlay)

메모리에 프로세스의 부분 중 실제 필요한 정보만 올리는 방법을 말한다. Dynamoc loading과 달리 운영체제의 라이브러리 지원없이 프로그래머가 직접 구현하기 때문에 프로그래밍이 매우 복잡하다.

초창기 컴퓨터 시스템은 하나의 프로그램 메모리에 모두 올리지 못할 정도로 메모리 공간이 작았다. 따라서 어떤 정보를 언제 메모리에 올릴지 프로그래머가 프로그램을 쪼개서 수작업으로 구현해야 했는데 Overlays는 이러한 배경에서 탄생한 방식이다.

따라서 Overlays는 프로세스의 크기가 메모리보다 클 때 유용하다.

3. Dynamic Linking

Linking이란 여러 군데에 존재하던 Compiled files을 묶어서 하나의 실행 파일을 만드는 것을 말하며, Dynamic Linking은 Linking을 실행 시간(Execution time)까지 미루는 기법으로 라이브러리 파일 등을 미리 묶지 않고 실행할 때 Linking하여 실행 파일의 크기를 줄이는 기법이다.

라이브러리 실행 시 Link되며 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어온다. 실행 파일 코드에 실제 라이브러리가 포함되지 않고 해당 루틴을 찾기 위한 Stub이라는 작은 코드만 둔다.

c.f. Static Linking

라이브러라기 프로그램의 실행 파일 코드에 포함된다.
실행 파일의 크기가 커진다.
동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리가 낭비된다.
- e.g. printf 함수의 라이브러리 코드 등.

4. Swapping

프로세스를 일시적으로 메모리에서 Backing store로 쫓아내고 Backing store에서 다시 불러오는 것을 말한다. 즉, 프로세스를 통째로 메모리에서 쫓아내고 불러오는 것을 의미한다.

일반적으로 중기 스케줄러(Swapper)가 Swap out 시킬 프로그램을 결정하며 CPU 우선 순위가 낮은 프로그램을 쫓아낸다. (Priority-based CPU Scheduling algorithm)

Backing Store(= Swap Area): 메모리에서 쫓아낸 데이터를 저장하는 공간을 말한다. 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 공간(HDD, SSD)이다.
Swap In: Backing store로 쫓겨났던 게 다시 메모리로 올라오는 동작이다.
Swap Out: 메모리에서 쫓겨나서 Backing store로 내려가는 동작이다.

컴파일 바인딩 및 로드 타임 바인딩에 적용하면 Swap in 할 때 Swap out 이전과 같은 번지로 와야 하기 때문에 메모리를 비효율적으로 사용하게 된다. 따라서 Swapping은 런타임 바인딩이 지원되어야 효율적으로 사용할 수 있다.

방대한 양의 데이터가 왔다 갔다하는 것이기 때문에 디스크 접근 시간 대부분이 Transfer time이다.

원래는 프로세스가 통째로 Swapping되는 것만을 의미하는 용어이나, 최근에는 페이징 시스템에 의하여 프로그램 전체가 아닌 일부 구성하는 페이지만 Swap-In/Out 되는 것도 Swapping이라 한다.

각주

1: 유저 프로그램은 Logical address만을 다루며 실제 Physical을 볼 수 없고 알 필요도 없다.
2: 그 중에서도 Paging 기법을 채택하고 있다.
3: 프로그램의 크기가 반드시 페이지의 배수 단위가 되리라는 보장이 없기 때문에 마지막 페이지가 페이지 프레임보다 작은 경우 내부 조각이 발생한다. 하지만 페이지를 잘게 쪼개면 의미가 없다.
4: 더 잘게 쪼갤 수도 있다. 예를 들어 함수를 세그먼트로 잘라서 올릴 수도 있다.

Reference

반효경, “반효경 [운영체제] 18. Memory Management 1”. KOCW. 2014년 4월 25일. video, http://www.kocw.net/home/cview.do?lid=c750795d11871a36

OS 시리즈 모두보기 (펼치기)

Twitter Facebook LinkedIn

Seungho Jeong