[Operating System] Memory Management
운영체제는 프로세스의 할당과 반납 등 과정을 수행하기 위해 메모리 관리를 수행합니다.
그렇다면 메모리 관리란 무엇일까요?
메모리 관리란 다음 기능들을 의미합니다.
- 메모리의 할당 (Memory Allocation)
- 메모리의 보호 (Memory Protection)
- 메모리 재배치 (Relocation)
- 메모리 공유 (Sharing)
위 기능들에 대해 하나씩 알아봅시다.
메모리의 할당 (Memory Allocation)
메모리의 할당은, 물리적인 공간인 메인 메모리를 쪼개서 프로세스에게 할당하는 것을 의미합니다. 이 때, 메인 메모리를 효율적으로 사용할 수 있도록 적당한 크기의 공간을 프로세스에 할당 / 반납받아 관리하여야 합니다.
어떻게 메모리를 "쪼갤 수" 있는지, 어떻게 할당하고 반납하는 지는 뒤에 다루겠습니다.
메모리의 보호 (Memory Protection)
이전에 프로세스의 개념에 대해 다룰 때, 각 프로세스는 독립적 공간을 보장받으며 다른 프로세스의 공간에 침범할 수 없다고 말씀드린 바 있습니다.
메모리의 보호는 프로세스가 다른 프로세스의 영역에 침범할 수 없도록 보장하는 것을 의미합니다. 어떤 프로세스가 다른 프로세스의 영역에 침범할 지 안할 지는 컴파일 시점에 확인할 수 없습니다. 오로지 런타임 시점에 확인이 가능합니다.
메모리의 보호는 프로세서 (하드웨어) 에 의해 보장되어야 합니다. 왜냐하면, OS 는 한 프로그램이 만들 모든 메모리 공간의 참조를 확인할 수 없기 때문입니다.
메모리의 재배치 (Relocation)
프로그램을 실행하는 동안, 프로세스는 메인 메모리 내에서 독립적인 공간을 차지하고 있게 됩니다.
그러다가 어떤 이유로, 프로세스가 Swap out 되어 보조 기억장치로 갔다가, 다시 Swap in 되면 메인 메모리에 로드되어야 합니다.
이 때, 메모리의 재배치가 발생합니다.
또, 메모리에 외부 단편화가 많이 발생하여 비효율적으로 공간을 활용하고 있는 경우, 메모리의 재배치를 통해서 메인 메모리의 외부 단편화를 줄일 수도 있습니다.
메모리의 공유 (Sharing)
이전에 Inter-Process Communication 을 위해 Shared Memory 를 이용하는 방법에 다룬 적 있습니다. 기본적으로 프로세스는 각자의 영역에서만 동작 가능하지만, 커널에 의해 Shared Memory 공간을 만들면 서로 다른 프로세스가 같은 메모리 영역에 접근할 수 있습니다.
이제, Memory Allocation 을 위해 메인 메모리 공간을 쪼개는 방법에 대해 알아봅시다.
Memory Partitioning
메인 메모리를 쪼개서 관리하는 방법은 다음과 같습니다.
- Fixed Partitioning (고정 길이 분할)
- Dynamic Partitioning (가변 길이 분할)
- Buddy System
각 방법에 대해 알아봅시다.
Fixed Paritioning (고정 길이 분할)
고정 길이 분할법은 메모리 공간을 같은 사이즈의 블럭 여러개, 혹은 여러 사이즈의 블럭 여러개로 나누어 관리합니다.
예를 들어, 메인 메모리의 공간의 합이 총 10이라면, 크기 2인 블럭 5개로 관리하거나, 크기가 각각 1,2,3,4 인 블럭 4개로 관리할 수도 있습니다.
Equal Size 의 블럭으로 관리하는 Fixed Partitioning 방법의 경우, 모든 프로세스는 Equal Size 블럭 크기보다 작거나 같아야 메인 메모리에 로드할 수 있습니다. 만약, 프로세스의 크기가 한 블럭 사이즈보다 크다면, 프로그래머는 Overlay 형태로 디자인하여 프로그램을 작성해야합니다.
Equal Size 블럭으로 관리하는 Fixed Partitiong 방법의 경우, 내부 단편화가 발생합니다. 예를 들어, 프로세스를 할당할 때 필요한 공간의 크기가 3인데, Equal Size 블럭 크기가 10이라면, 7 만큼의 공간은 사용하지 않습니다. 프로세스는 각각 독립된 공간을 보장받아야 하기에, 이를 다른 프로세스가 이용할 수도 없습니다.
Unequal Size 블럭으로 관리하는 Fixed Partitioning 방법의 경우, 메모리 공간을 프로세스에 할당할 때, 내부 단편화가 가장 적게 발생하는 블럭을 할당합니다. Equal Size 블럭에 비해 더 유연하게 공간을 제공하여 메모리 공간을 효율적으로 이용할 수 있습니다. 하지만 할당 속도면에서는 프로세스의 크기와 블럭 사이즈를 비교하여 할당해주어야 하므로 Overhead 가 발생하여 Equal Size 방법보다 느릴 수 있습니다.
Dynamic Partitioning (동적 길이 분할)
동적 길이 분할법은 메모리 공간을 가변적으로 분할하여 관리합니다. 프로세스가 요구하는만큼의 메모리 공간을 할당하여, 내부단편화가 발생하지 않습니다.
이것은 Fixed Partitioning 의 Unequal size 방법과는 다릅니다. Unequal Size 방법은 사전에 메모리 공간을 분할하여 두고 할당을 관리하고, Dynamic Partitiong 방법은 프로세스의 요청이 있을 때 메인 메모리를 적당히 분할하여 할당하는 방법입니다.
그러나 Dynamic Partitioning 방법은 외부 단편화가 발생할 여지가 있습니다. 메인 메모리 상에 전체 남는 공간이 할당할 프로세스보다 클지라도, 프로세스 할당이 불가능한 경우가 있다는 뜻입니다.
따라서, Compaction 과정을 통해서 할당된 블록끼리는 연속적으로 존재하게 만들어 Free Block (가용 블럭) 을 하나의 블럭으로 존재할 수 있도록 해야 Memory Utilization 을 높일 수 있습니다.
Dynamic Partitioning 방법에서 가용 블럭을 프로세스에 할당하는 방법에는 다음과 같은 것들이 있습니다. (시스템 프로그래밍 시간에 다루었던 것들과 같습니다.)
- First-fit algorithm
- Best-fit algorithm
- Next-fit algorithm
- Worst-fit algorithm
First-fit Algorithm
Firtst-fit Algorithm 은 Free block 들을 관리하는 Free List 를 첫번째 블럭부터 탐색하여 할당 가능한 크기의 Free Block 을 찾으면 그곳에 프로세스를 할당하는 방법입니다.
Best-fit Algorithm
Best-fit Algorithm 은 Free List 에서 할당하고자 하는 프로세스 크기에 가장 가까운 Free Block 을 찾아 그 곳에 할당하는 방법입니다.
Next-fit Algorithm
Next-fit Algorithm 은 First-fit Algorithm 의 변형으로, Free List 에서 마지막으로 할당한 블럭의 인덱스부터 탐색하여 할당 가능한 크기의 Free Block 을 찾으면 그 곳에 프로세스를 할당하는 방법입니다. Next-fit 을 사용하면, Free Block List 의 뒷 편에 있는 블럭들을 잘 활용하지 않는 문제를 해결하여, throughput 을 높일 수 있습니다.
Worst-fit Algorithm
Worst-fit Algorithm 은 Best-fit Algorithm 과 정반대로 동작합니다. 로드하고자 하는 프로세스와 Free Block 크기의 차이가 최대로 되도록 하는 블럭을 배정합니다. Worst-fit 을 쓰는 이유는, 나중에 메모리 공간을 반납한 뒤에 남는 공간의 크기가 커지기 때문에 공간 활용률을 높일 수 있습니다.
하지만, Dynamic Allocation 은 외부 단편화가 발생하고, 메모리 공간을 할당/반납하고 Free Block 을 관리하는데 overhead 가 커 속도가 느려 요즘은 사용하지 않습니다.
Buddy System
Buddy System 은 메인 메모리의 블럭 크기를 2^n 의 크기로 나누어 할당/반납받아 메모리를 관리하는 기법입니다.
만약 로드될 프로세스의 크기가 s 이고 다음의 부등식을 만족할 때, 2^(U-1) < s <= 2^(U) OS 는 2^U 크기의 메모리 블럭을 할당합니다. 만약, 2^(U-1) 보다 작다면, 2^U 크기의 블럭을 반으로 쪼갠 뒤 할당합니다.
반납 시, 같이 쪼개졌던 블럭이 Free Block 이라면, Coalescing 을 통해 2^U 크기의 블럭으로 관리됩니다. 이 때, 같은 쌍으로 쪼개진 것이 아니라면, 즉 합친 뒤 블럭의 크기가 2^N 꼴이 아니라면 Coalescing 할 수 없습니다.
이렇게 Buddy System 으로 관리하면, 내부 단편화는 발생하지만, 외부 단편화가 현저하게 줄어듭니다. 또, 비어있는 메모리 공간을 List 를 순회하면서 순차적으로 찾지 않고, Binary Tree Search 로 찾을 수 있어 할당 속도도 빨라집니다.
이번에는 다른 주제로 넘어와서 Virtual Address Space 에 대한 이야기를 해보겠습니다.
우리는 이전에 프로세스에 대해 다룰 때, New 상태는 VAS 와 PCB 는 가지지만, 메모리에 로드되지는 않은 상태라고 했습니다. VAS 는 도대체 왜 필요한걸까요?
VAS 를 다루기에 앞서 Address (주소) 의 종류에 대해 먼저 다뤄보겠습니다.
메모리 주소의 종류 (Type of Memory Address)
- Physical Address : 절대 주소(Absolute Address)라고도 불리는 물리적 주소는 메인 메모리에서의 실제 주소를 의미합니다. 하드웨어는 이 주소로 접근하여 명령을 수행합니다.
- Logical Addrss : 논리적 주소는 논리적인 연산에 이용되는 주소로, 프로그램의 Instruction 내에 등장하는 주소입니다. 이는 실제 메인 메모리의 주소와는 다를 수 있습니다. 따라서 CPU 에 의해 Instruction 이 수행될 때 이 Logical Address 는 반드시 Physical Address 로 Translation 이 되어야합니다.
- Virtual Address : Logical Address 와 비슷한 개념입니다. 논리적인 연산에 이용되는 주소지만, Virtual Memory 에서 사용될 때 Virtual Address 라고 지칭합니다. Virtual Memory 란 메인 메모리와 보조 기억 장치의 공간을 같이 메인 메모리처럼 이용하는 메모리 관리 기술입니다. 후에 자세히 알아보겠습니다.
- Relative Address : Relative Address 는 특정 위치를 기준으로 얼마나 떨어져있는지로 표시한 주소입니다.
Virtual Address Space (VAS)
이전 프로세스에 대해 다룰 때, VAS 에 대해 잠시 살펴본 바 있습니다. VAS 의 정의를 간단히 짚고 넘어가자면 VAS 란, 프로세스 하나가 메인 메모리를 독차지 하는 것처럼 보이도록 보조 기억장치에 저장되는 주소공간입니다.
32-bits 컴퓨터에서 VAS 의 크기는 4GB 입니다. (2^2 * 2^30) 이 중, 4GB-1 부터 3GB 공간까지는 커널이 차지합니다. 실제로 커널이 VAS 에 복사되어 들어있지는 않습니다.
OS 는 VAS 의 각 영역의 시작 주소와 끝 주소를 PCB 에 기록합니다. VAS 에서 사용하는 주소는 Virtual Address 이고 이것은 Logical Address 라는 점을 짚고 아래 내용을 읽어나갑시다.
각 프로세스는 VAS 를 가지고 있습니다. VAS 에는 Code, Data, Stack, Kernel 영역이 존재합니다.
Kernel 영역은 정보로써만 존재할 뿐, 실제 디스크에서 공간을 차지하지는 않습니다.
VAS 에 실제 디스크에서 공간을 차지하는 영역은 Data, Stack 뿐입니다. 메인 메모리에 프로세스를 로드할 때 Code 영역은 Executable file 의 정보를 가져와서 로드합니다.
Stack 과 Data 영역 사이의 빈 영역인 Heap 영역 또한, 정보로써만 존재할 뿐 실제 디스크 공간을 차지하고 있는 것은 아닙니다.
이 VAS 에 기록된 프로세스의 Context 들은 메인 메모리에 로드될 수 있습니다.
앞서 메모리 주소의 종류에 대하여 설명드릴 때, 실제 Instruction 을 수행하기 위해서는 논리적 주소를 Physical Address 로 Translation 이 필요하다고 했습니다.
어떤 방식으로 Translation 을 수행하는지 살펴봅시다.
Address Binding
Address Binding 이란, Instruction 이나, 데이터의 주소를 Physical Address 로 결정짓는 것을 의미합니다.
Address Binding 방법은 다음과 같습니다.
- Compile Time Binding
- Load Time Binding
- Execution Time Binding
Compile Time Binding
Compile Time Binding 은, Address Binding 을 컴파일 시점에 수행하는 것을 의미합니다. 만약, 어떤 Instruction 이나 데이터가 실제 메모리에서 어디에 저장되는지 컴파일 시점에 "미리" 알고 있다면, 컴파일 시점에 모든 Instruction 이나 데이터의 주소가 Physical Address 로 Determine 될 수 있습니다.
하지만, 컴파일 타임에 Absolute Address 를 모두 지정했기 때문에 이 Executable 파일을 실행하여 프로세스가 Main Memory 로 로드 된 뒤, Relocation 이 발생하면 이 프로세스는 kill 될 확률이 매우 높습니다. 왜냐하면, 기존의 Absolute Address 가 가리키던 주소는 다른 프로세스가 들어가 있을 확률이 높기 때문입니다.
정리하면, Compile Time Binding 은 컴파일 시점에 Physical Address 를 결정지을 수 있고, 컴파일 결과인 Executable File 에 나타나는 Logical Address 가 곧 Physical Address 입니다. 하지만, Compile Time Binding 은 Relocation 에 매우 취약합니다.
(* Reloacation : eg., Swap In/Swap Out, Compaction)
Load Time Binding
Load Time Binding 은 컴파일 한 결과인 Executable File 에 Logical Address 와 Base Address (Starting Location, Register) 을 함께고려하여 실제 Executable 프로그램을 메인 메모리에 프로세스로 "로드" 할 때, Physical Address 로의 Address Binding 을 수행하는 방법입니다.
하지만, Load Time Binding 도 Relocation 을 수행할 수 없습니다. 왜냐하면 Load Time 에 Physical Address 를 확정지었기 때문에 이를 재배치하더라도 메인 메모리의 프로세스 Context 안에 들은 Instruction 이나 데이터를 가리키는 주소값이 변하지 않기 때문입니다. 즉, 다른 프로세스의 공간에 접근할 가능성이 매우 높습니다. (그렇다면 자신의 공간을 벗어난 프로세스는 kill 당할 것입니다.)
(* Reloacation : eg., Swap In/Swap Out, Compaction)
Execution Time Binding
Execution Time Binding 은, 메모리에 로드할 때도 Logical Address 의 형태로 올리고 실제 실행할 때 Base Address 를 참조하여 Physical Address 를 계산하고, Instruction 을 수행하는 것입니다.
따라서 Execution Time Binding 은 Relocation 이 일어나더라도, 정상적으로 동작할 수 있습니다.
(* Reloacation : eg., Swap In/Swap Out, Compaction)
만약 Comparator 에서 Out of Bound (다른 프로세스의 영역에 침범했을 경우) Segmentation Fault 를 발생시킵니다.
마지막으로, 메모리를 좀 더 효율적으로 관리하기 위한 기술 두가지를 살펴보겠습니다.
- Paging
- Segmentation
Paging
페이징에 관해 한마디로 정의하자면 '고정 길이 분할법을 이용하되, 프로세스도 고정 길이로 쪼개서 관리하자' 입니다.
용어 정리
- 페이지 : 프로세스를 잘게 쪼갠 것. 일반적으로 4KB
- 프레임 : 메인 메모리를 잘게 쪼갠 것. 일반적으로 4KB
페이지 크기, 프레임 크기, 디스크 블럭 사이즈가 모두 같아 간편하게 메모리를 관리할 수 있는 이점이 있습니다.
그리고 프로그램 내의 Logical Address 는 페이지 번호와 페이지에서의 Offset 을 이용하여 표현할 수 있습니다.
위 그림의 (d) 에서 메인 메모리는 14개의 프레임으로 구성되어 있으며, A, C 프로세스는 4개의 페이지로, B 프로세스는 3개의 페이지로 구성되어 있습니다.
그리고 B 프로세스가 Swap out 되고 D 를 로드한 그림이 (f) 입니다. 프로세스를 페이지 단위로 관리하기 때문에 프로세스는 메인 메모리 상에서 반드시 연속된 공간에 위치할 필요가 없습니다. (외부 단편화가 감소할 것임을 예상할 수 있습니다!)
그렇다면, 각 프로세스 별로 페이지는 어떻게 관리할까요?
바로, Page Table 을 이용하여 관리합니다.
프로세스의 페이지를 관리하는 Page Table 은 각 프로세스의 PCB 에 저장이됩니다.
페이지 테이블의 인덱스 번호는 프로세스의 페이지 번호가 되며, 테이블에 들어있는 값은 메인 메모리의 프레임이 됩니다. 그리고 새 프로세스의 페이지를 할당하기 위한 Free Frame List 는 OS 가 관리합니다.
다음 메모리 관리 기술인 Segmentation 에 대해 알아보겠습니다.
Segmentation
Segmentation 방법은 Paging 방법과는 달리 '동적 분할 방법을 이용하여 프로세스를 잘게 쪼개 메모리를 관리하는 기술' 입니다.
Segmentation 은, 프로세스를 논리적인 단위로 나누어 관리합니다. 이것의 Logical Address 를 계산할 때는 Segement Number 와 Offset 을 이용합니다.
Segment 를 메인 메모리에 로드할 때 어떻게 관리되는지 알아봅시다. 먼저 PCB 에 Segment Table 을 등록합니다. Segment Table 의 인덱스 번호는 세그멘트의 번호를 의미하며, Table 에 저장된 내용은 각 세그멘트의 메인 메모리 상에서의 Physical Address 를 표현합니다. Base (Starting Address) 와 limit (최대 길이) 를 이용합니다.
하지만 Segment 는 테이블에 저장되어야 할 내용도 많고, 적당한 크기의 Free Block 이 있는지 찾는 Algorithm 을 수행해야하는 Overhead 가 있기 때문에 현대에는 잘 사용되지 않는다고 합니다.