[Operating System] Chapter 7 - Memory Management

1. Relocation

• Relocation : 멀티 프로그래밍 시스템 환경에서 메인 메모리는 여러 프로세스가 상주하며 메모리를 공유한다. 프로세스 실행이 원활하게 이루어지기 위해선 충분한 메모리 자원이 필요하기 때문에, 메인 메모리에는 필요한 프로세스만 위치하도록 해야한다. 즉, 메모리 관리를 효율적으로 하기 위해 프로세스를 동적으로 다른 메모리 영역으로 이동시키는 메커니즘이 필요하다.

  • Swap out : 메인 메모리에 상주해있던 프로세스를 메모리 확보 등의 이유로 보조 메모리 영역에 재배치하는 것.

  • Swap in : 보조 메모리에 존재하던 프로세스를 주 메모리 영역으로 재배치하는 것.

• Logical Address (논리 주소) : 프로세스에 의해 참조되는 주소로, 프로세스가 실행 될 때 실제 메모리 주소 (Physical Address)로 변환된다.

• Physical Address (물리 주소) : 메모리 내 실제 위치를 나타내는 주소로, 프로세스가 메모리에 할당될 때 실제 사용하는 주소이다.

• Address Translation 메커니즘 : Source Program (Source Code, Symbolic Address) $\rarr$ Compiler $\rarr$ Object Code (Logical Address) $\rarr$ loader $\rarr$ Executable Code (Physical Address)

논리 주소와 물리 주소간 변환은 Relocation 과정에 있어 매우 중요하다.

2. Memory Partition

2-1. Fixed Size Partition

• Fixed Size Partition : 메인 메모리를 고정된 용량을 갖도록 여러 파트로 나누는 기법이다. 이 경우, 요구하는 메모리의 크기가 파티션 크기 이하인 프로세스는 정상적으로 로드될 수 있다. OS는 프로세스의 생명 주기에 따라 메인 메모리의 파티션에 적절한 프로세스를 Swap in, Swap out한다.

  • 문제점

    • 파티션의 크기보다 큰 프로세스는 메모리에 로드될 수 없다.

    • 따라서 파티션 크기보다 큰 프로세스를 실행하기 위해선 Overlay같은 기법이 필요해진다.

    • Internal Fragment Issue가 있다.

• Internal Fragment (내부 단편화) : 만약 $8Mbyte$의 크기를 갖는 파티션에 $5Mbyte$ 짜리 프로세스가 로드된다면, 나머지 $3Mbyte$ 만큼 메모리 낭비가 발생한다. 이를 내부 단편화라고 한다.

2-2. Dynamic Partition

• Dynamic Partition : 프로세스가 요구하는 크기 만큼의 메모리를 동적으로 할당하는 기법이다. 이 경우, 분할의 크기와 개수가 동적이므로 고정 분할 방식에 비해 알고리즘이 복잡하고 메모리 관리가 어렵지만, 메모리 활용에 있어 더욱 효율적이다.

  • 문제점

    • 메모리 관리 알고리즘이 고정 분할 방식보다 복잡하다.

    • External Fragment Issue가 있다.

• External Fragment (외부 단편화) : 메모리 동적 할당 시스템에서, 여러 프로세스가 메인 메모리에 로드되고 해제된다. 이 과정에서 메모리는 여러 크기의 작은 조각으로 나누어져 충분한 총 공간이 있음에도 불구하고 프로세스에 메모리를 할당하지 못하는 현상이 발생한다. 이를 외부 단편화라고 한다.

• Compaction (조각 모음) : 외부 단편화 현상을 해결하기 위한 기법으로, OS가 프로세스들을 이동(압축)시켜 모든 빈 메모리를 하나의 블록으로 만드는 것이다.

3. Placement Algorithm

• Placement Algorithm : 메인 메모리에 프로세스를 할당할 때, OS는 특정 알고리즘을 통해 어떤 메모리 블록에 이 프로세스를 할당할지를 결정해야 한다. 이 때 고려할 수 있 알고리즘은 다음과 같다.

  • Best-Fit : 프로세스가 요구하는 메모리 용량에 최대한 딱 맞는 메모리 블록에 프로세스를 할당하는 알고리즘이다. 단편화 문제는 최소화할 수 있지만, 검색 시간이 오래 걸린다.

  • Worst-Fit : 사용 가능한 메모리 블록 중 크기가 제일 큰 블록에 프로세스를 할당한다. 이 알고리즘은 프로세스를 가장 큰 블록에 할당하므로, 남게 되는 공간이 여전히 크도록 유지한다.

  • First-Fit : 메모리의 시작부분부터 스캔하여 프로세스를 할당할 만큼의 크기를 가진 첫 번째 메모리 블록에 바로 프로세스를 할당한다. 가장 단순하며 일반적으로 가장 빠르다.

  • Next-Fit : 마지막으로 사용된 메모리 블록부터 스캔하여 프로세스를 할당할 만큼의 크기를 가진 메모리 블록을 선택하여 할당한다. 퍼스트 핏에 비해 메모리 전체적으로 프로세스가 할당되는 경향이 있지만, 적절한 블록을 찾지 못할 때 처음부터 다시 찾아야하는 경우가 발생한다.

4. Memory Management

• Overlay : 프로그램이 실행되기 위해 필요한 일부분만 메모리에 로드하고, 필요 없는 부분은 메모리에 로드하지 않는 방식이다. 이는 메모리 공간이 충분하지 않은 상황에서도 프로세스를 실행할 수 있도록 돕는다.

4-1. Paging

• Paging : Fixed Size Partition 방식의 아이디어를 더욱 발전시켜 생겨난 메모리 관리 기법. 메인 메모리를 크기가 매우 작은 고정된 크기의 조각(프레임)으로 나누고, 프로세스 를 프레임 크기의 작은 조각(페이지)으로 나누어 프레임에 페이지를 할당하는 방식이다. 이를 통해 메모리의 내부 단편화 문제를 어느정도 해결할 수 있다.

  • $Frame\,Size = Page\, Size$

  • 페이지는 어떤 프레임이든 관계없이 할당 가능하다. 즉, 프로세스의 페이지들은 메모리 내에 연속적으로 존재하지 않아도 된다.

  • Page Size가 작아질수록 Internal Fragment의 발생이 적어지고, Page Table의 Size는 커진다.

  • OS는 Page Table을 통해 프로세스의 각 페이지가 메모리의 어떤 프레임에 위치하는지 추적한다. 즉, 논리 주소와 물리 주소 사이의 매핑은 페이지 테이블을 통해 이루어진다.

• Page Table : 프로세스의 각 페이지가 위치한 프레임의 주소를 저장하고 있는 테이블이다. 테이블은 페이지 번호와 해당 페이지가 존재하는 프레임 번호로 구성되어 있다. CPU는 이 테이블을 참조해 논리 주소를 물리 주소로 변환한다. 즉, 페이지 테이블은 Address Translation을 위해 정의된 테이블이다.

  • 페이지 테이블을 통한 주소 변환 과정

    • 프로세스의 논리 주소는 (페이지 번호, 오프셋)으로 이루어져 있다.

    • CPU가 현재 프로세스의 페이지 테이블에서 각 페이지 번호가 어떤 프레임에 위치해 있는지 찾아낸다.

    • 페이지 테이블에서 얻은 프레임 번호와 논리 주소의 오프셋을 결합하여 물리 주소(프레임 번호, 오프셋)를 생성한다.

• Offset(오프셋) : 페이지 내부에서 데이터의 위치를 나타내는 것.
  

4-2. Segment

• Segment : Dynamic Partition 방식의 아이디어를 더욱 발전시켜 생겨난 기법. 프로세스를 동일하지 않은 크기의 여러 파트로 나누어(Segment) 메모리에 할당한다. 각 세그먼트는 연속적으로 존재할 필요가 없으며, 작은 조각으로 나누어진 메모리에도 할당할 수 있으므로 외부 단편화 문제를 어느정도 해결 할 수 있다.

• Segment Table : 세그먼트를 관리하기 위해 정의된 테이블이다. 세그먼트 테이블에는 각 세그먼트의 번호와 해당 세그먼트의 시작 주소, 세그먼트의 최대 길이가 저장되어 있다. 이 테이블을 참조해 메모리에 존재하는 세그먼트를 찾아낼 수 있다.

  • Segment Table을 통한 주소 변환 과정

    • 프로세스의 논리 주소는 (세그먼트 번호, 오프셋)으로 구성된다.

    • 주어진 세그먼트 번호를 세그먼트 테이블에서 찾는다. 이때, 오프셋이 최대 세그먼트 길이를 초과하지 않는지 확인한다.

    • 오프셋이 유효하다면, 세그먼트 테이블에 존재하는 베이스(세그먼트 시작 주소)와 오프셋을 결합해 물리 주소를 생성한다.

4-3. Segment-Paging

• Segment-Paging : 세그먼트와 페이징을 혼합하여 사용하는 기법이다. 이 방식은 세그먼트의 장점과 페이징의 장점을 모두 활용할 수 있으므로, 더욱 효율적으로 메모리를 관리할 수 있다.

  • 동작 방식

    • 세그먼트화 : 프로세스를 여러 개의 세그먼트로 나눈다. 각 세그먼트는 서로 다른 논리적 단위이다.

    • 페이징화 : 각 세그먼트를 고정된 크기의 페이지로 나눈다. 따라서 하나의 세그먼트는 여러개의 페이지로 구성된다.

    • 즉, 프로세스는 페이지가 결합된 세그먼트의 결합으로 볼 수 있다.

    • 메인 메모리는 페이지의 크기와 동일한 프레임으로 나누어진다.

  • Segment Table : 프로세스 당 1개씩 존재

  • Page Table : 세그먼트 당 1개씩 존재.

  • 주소 변환 과정

    • 논리 주소는 세그먼트 번호, 페이지 번호, 페이지 내 오프셋으로 구성된다.

    • 세그먼트 번호를 사용하여 세그먼트 테이블에서 해당 세그먼트의 메모리 주소를 찾는다.

    • 찾은 메모리 주소를 통해 해당 세그먼트의 페이지 테이블을 참조한다. 페이지 번호를 통해 페이지 테이블에서 해당 페이지의 프레임 번호를 찾는다.

    • 프레임 번호와 페이지의 오프셋을 결합하여 최종적인 물리 주소를 생성한다.