[전공생이 설명하는 OS] 메모리 관리 - (1) Partition/Page/Segment

1. Memory Management 란?

  메모리는 (1) OS(resident monitor, kernel) (2) user 두 부분으로 나뉜다. Uni-programming 환경에서는 user part 에 1개의 프로그램만 적재되고, multi-programming 환경에서는 다수의 프로그램이 적재될 수 있다. Memory management 라는 말은 OS 가 user 가 사용하는 메모리를, 프로세스의 요청에 맞게 분할 및 분배하는 것을 포함한다.

  메모리를 할당하는 방식은 프로세스 실행 시점에 따라 크게 두 가지로 분류할 수 있다.

• static allocation : 프로그램 실행 이전에 미리 메모리를 할당하는 방식
  (예, global 변수나 상수 등)
• dynamic allocation : runtime 에 필요할 때마다 메모리를 할당하는 방식
  (예, new 등의 동적할당)

---

2. 개요

(1) OS 요구사항

1. Relocation
   - 한정된 메모리 공간은 다수의 프로세스가 사용해야한다.
   - 프로그램이 어떤 메모리 주소에 적재될지 미리 알 수 없다.
   - 메모리 공간이 부족하면 victim process를 secondary storage 로 swap out 하는 상황이 발생한다.
   - 이런 이유들로 매번 다른 주소에 프로세스를 재할당하는 기능이 필수적이다.
   - 프로그램에서는 논리주소를 이용하고, 하드웨어(MMU)가 실제 주소로 매핑해준다.
2. Protection
   - 각 프로세스는 자신의 메모리 주소에만 접근해야한다.
   - 메모리 주소는 runtime 에 할당되기 때문에, 메모리에 접근할 때마다 동적으로 검사해야한다.
   - 주로 하드웨어의 지원을 받아서 구현된다. 
3. Sharing
   - 다수의 프로세스가 동일한 프로그램을 실행하고 있다면, 별도의 copy 를 만드는 것은 비효율적이다. 적어도 read-only 속성인 코드는 공유하는 것이 효율적이다.
   - OS의 커널 코드도 일종의 공유 메모리인 셈이다.
4. Logical organization
   - 개발자가 프로세스 메모리 주소를 바라볼때는 code / data / stack / heap 영역 등 논리적으로 바라본다.
   - 논리적 성격에 따라 비슷한 데이터끼리 묶으면, 더 효과적으로 메모리를 관리할 수 있다.
5. Physical organization
   - 메모리는 물리적으로 보통 Main memory와 Secondary memory 두 계층으로 나뉜다. 
   - 이런 계층적인 메모리를 프로그래머가 직접 관리하는 것이 아니라, OS 가 고려해서 관리한다.

 

(2) 주소의 종류

- Symbolic address : 소스코드 상에서의 변수의 주소, 함수 주소 등. 심볼테이블과 비슷한 느낌이다.

- Logical address : 논리주소, 상대주소, 가상주소, 실행가능한 파일의 형태.
프로그램이 실제로 실행되기 전에는 물리주소를 알 수 없으므로 첫 주소를 0으로 해서 사용하는 주소

- Physical address : 절대주소, 실제 메모리에 적재된 상태. 메모리상의 실제 주소 번호

 

(3) Dynamic Address Translation

 - runtime 에 가상 메모리를 물리 메모리 주소로 변환하는 작업.

 - 하드웨어 상에서 구현된다. (MMU)

 - Base register와 Bounds register 를 통해서 프로세스의 메모리 주소 범위를 지정한다.

 - 프로세스는 입장에서는 하드웨어에서 일어나는 일을 몰라도 된다.

 

---

3. Memory allocation

1) Contiguous

  : 프로세스를 분리되지 않은 하나의 덩어리로 적재하는 기법이다. (고정분할 / 동적분할 / 두가지의 중간쯤 되는 buddy system) 3가지 방식을 설명한다. 

(1) Fixed partitioning

균등 분할과 비균등 분할

  메모리를 미리 분할해 놓고, 하나의 파티션에 한 프로그램만 할당하는 방식이다. 모든 파티션을 같은 크기로 분할하는 방식은 균등 고정분할 방식(equal-size partitioning)이라고 하고, 다른 크기로 분할하는 방식을 비균등 고정분할 방식(unequal-size partitioning)이라고 한다. 두 방식의 장단점은 아래와 같다.

• 단점
  • 실행할 수 있는 프로세스의 개수가 정해져있다. -> 멀티 프로그래밍의 정도가 제한되어 있다.
  • Internal Fragment 가 발생 (파티션의 공간이 남는다.) -> memory utilization 이 낮다.
  • 파티션의 크기보다 크면 실행할 수 없다. -> overlay 기법을 고려해보아야 한다.
• 장점
  • 매우 간단하다.
  • 구현상의 overhead 가 적다.

비균등 할당 방식에서 프로세스 할당 전략

  참고로 비균등 할당 방식에서는 프로세스를 할당하는 전략이 다양해질 수 있다. 어떤 프로세스가 메모리 할당 요청을 했을 때, 가장 최적 크기의 파티션이 사용 중에 있으면 (a) 해당 파티션의 프로세스가 swap out 될 때까지 기다리거나 (b) 가용한 파티션 중에서 골라 들어간다.

1.  

(2) Dynamic partitioning

동적 파티셔닝

   run-time 요청을 왔을 때의 메모리 상황을 고려해서, 필요한만큼 파티션을 잡고 분할해준다. 파티션을 필요한 크기와 정확히 동일하게 잡기 때문에 내부 단편화는 발생하지 않는다. 반면 파티션 외부에 빈 공간들이 생기는데 이를 외부 단편화(external fragmentation) 이라고 한다. 메모리를 효율적으로 사용하기 위해서는 주기적인 memory compaction 이 필요하다.

 

3가지 할당 전략

빈 메모리 공간을 할당하는 전략이 여러가지 존재한다.

• First-fit : 요청이 있을 때마다 메모리 처음부터 탐색해서, 가능한 공간이 있으면 즉시 할당한다.
• Next-fit : 요청이 들어오면 포인터 위치에서 이어서 탐색을 시작한다. 할당하고 나면 포인터는 정지한다.
• Best-fit : 가장 잘 들어맞는 공간을 찾아서 할당한다. 성능이 최악이다. 단편화가 가장 자주 발생하기 때문에, 메모리 compaction 이 자주 발생한다.
• Worst-fit : 가장 공간이 많이 남는 곳을 찾아서 할당한다. memory compaction 이 덜 일어나도록 의도하는 전략이다.

 

(3) Buddy System

Buddy system 예시

  고정분할 방식과 동적분할 방식의 중간쯤 되는 방법이다. 기본크기인 블럭(block) 단위로 미리 분할해두고, 프로세스의 요청이 있으면 요청한 크기에 맞게 동적으로 블럭을 분할해서 할당하는 방식이다. 분할할 때는 \( 2^{i-1}\) ~ \(2^{i} \) 를 만족하도록 \(2^{i} \) 크기로 파티션을 잡는다. 중요한 것은 프로세스가 종료된 후에 메모리를 반납하면, 인접한 free partition 은 다시 합쳐진다.

  예를 들어 위의 그림을 보자. 1M 의 기본 블럭이 존재한다. 이 때 프로세스 A,B,C,D,E 가 순서대로 메모리를 할당받는다.

1. 프로세스 A가 100K 메모리를 요청 -> 128K 단위로 블럭을 쪼개서 할당한다.
2. 프로세스 B가 240K 메모리를 요청 -> 이미 쪼개져있는 256K 파티션을 할당한다.
3. 프로세스 C가 64K 메모리를 요청 -> 128K 블럭을 쪼개서 64K 파티션을 할당한다.
4. 프로세스 D가 256K 메모리를 요청 -> 512K 블럭을 쪼개서 256K 파티션을 할당한다.

이후는 그림과 동일하다. 메모리를 반납할 때 free block 이 다시 합쳐지는 것을 주목해야한다.

 

---

2) Non-contiguous

  이전까지는 한 프로세스를 연속적으로 적재하는 방식이었다면, 지금부터 소개하는 기법들은 한 프로그램을 여러 단위로 나누어 분산적재하는 방법이다. 동일한 길이로 자르면 paging, 가변길이로 자르면 segmentation 이라고 한다.

(1) Paging

process table

• page : 프로세스의 조각 / frame : 메인메모리의 조각
• 페이지의 크기와 프레임의 크기는 동일하다.
• 한 프로세스의 page 들이 불연속적으로 분산되어 적재될 수 있다. 따라서 프로세스마다 page 가 몇번 frame 에 위치하는 지에 관한 정보가 필요하다. -> os가 Page Table 로 별도로 관리한다. (프로세스마다 존재)
• 장점
  • page 와 frame 의 크기가 동일하기 때문에, 내부 단편화는 프로그램의 마지막 조각에서만 발생한다.
  • 메모리를 frame으로 나누었기 때문에, 파티션 사이의 공간을 의미하는 외부 단편화는 발생하지 않는다.

(2) Segmentation

segment table 예시. permission 과 같은 부가정보를 함께 저장한다.

• page는 고정길이였다면 segment 는 논리단위로 프로그램을 나눈다. 나누는 기준은 os 별로 상이하다.
• segment table 이 필요한데, 각 segment 의 시작주소와 길이를 저장한다. 또 접근 권한이라던가 readonly 속성등 부가적인 정보를 함께 나타낸다.
• 장점 : 내부 단편화가 없다. (segment 가 곧 파티션이므로) / segment 마다 추가적인 정보를 함께 다룰 수 있다.
• 단점 : 외부 단편화가 존재한다. -> compaction 이 필요하다.

(3) Address Translation 

  page와 segment 의 크기가 \(2^{i}\) 형태라고 가정하면 주소변환을 간단하게 할 수 있다. 

 

a. Paging

page 의 크기가 \(2^{10}\) 인 경우,

1. 프로세스의 1번 페이지의 0111011110 위치에 있는 주소로 접근하려고 한다.
2. page table 을 통해, 1번 페이지가 실제 메모리에서 몇번째 프레임인지 확인한다. (000110 번 프레임)
3. (프레임 번호) 와 (offset) 을 나란히 붙여 쓰면 된다.

b. segmentation

1. segment 번호로 segment table 을 조회한다.
2. offset 과 length 를 비교해서, length 보다 길면 segmentation fault 발생.
3. 실제 물리 메모리 주소는 (Base + offset) 이다.