메모리 관리

메모리란 프로그램이 실행되는 공간으로, 프로그램이 실행되기 위해 필요한 데이터와 명령어를 저장합니다. 메모리 관리는 프로그램이 메모리에 올라가는 방법과 메모리를 효율적으로 사용하는 방법을 다룹니다.

메모리 주소의 종류

메모리 주소(Memory Address) 는 프로그램이 메모리에 접근하기 위해 사용하는 값으로, 메모리 주소는 다음과 같이 나뉩니다.

• 논리 주소(Logical Address): 프로그램이 메모리에 접근하기 위해 사용하는 주소로, 프로그램이 생성하는 주소입니다.
• 물리 주소(Physical Address): 실제 메모리에 저장되는 주소로, 논리 주소를 물리 주소로 변환하는 메모리 관리 장치(MMU)에 의해 변환됩니다.

MMU (Memory Management Unit): 논리 주소를 물리 주소로 변환하는 장치로, CPU와 메모리 사이에 위치합니다.

메모리 할당 및 관리

스와핑(Swapping) 은 메모리에 올라온 프로세스 중 일부를 디스크로 내보내어 더 많은 프로세스를 실행할 수 있도록 하는 기법을 말합니다. 스와핑은 다음과 같은 경우에 사용됩니다.

• 메모리에 여유 공간이 없을 때
• 프로세스가 일정 시간 동안 사용되지 않을 때
• 프로세스의 우선순위가 낮아질 때

메모리 할당은 프로그램이 메모리에 올라가는 방법을 말합니다. 메모리 할당은 다음과 같이 나뉩니다.

연속 메모리 할당(Contiguous Memory Allocation): 프로그램이 연속적인 메모리 공간에 할당되는 방법으로, 프로그램이 실행되는 동안 메모리 공간이 변하지 않습니다.

• 정적 메모리 할당(Static Memory Allocation): 프로그램이 실행되기 전에 메모리를 할당하는 방법으로, 컴파일 시간에 메모리의 크기가 결정됩니다.
• 동적 메모리 할당(Dynamic Memory Allocation): 프로그램이 실행 중에 메모리를 할당하는 방법으로, 실행 시간에 메모리의 크기가 결정됩니다.

1. First-Fit 알고리즘

• 개념: 빈 메모리 블록 리스트를 앞에서부터 순서대로 탐색하여, 해당 프로세스가 요구하는 크기보다 큰 첫 번째 빈 블록을 할당한다.
• 특징:
  • 단순하고 빠르며, 구현이 비교적 용이하다.
  • 메모리 블록 분할 후 앞부분에 작은 단편화들이 남기 쉬워, 시간이 지날수록 앞쪽 공간이 쓸모없는 조각들로 채워질 수 있다.
• 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB] 순서로 있다고 하고, 4MB 할당 요청이 왔을 때, First-Fit은 제일 앞에서 만난 5MB 블록을 4MB로 나누어 4MB 할당 후 1MB 남겨두는 식으로 진행한다.

2. Best-Fit 알고리즘

• 개념: 빈 메모리 블록 중 할당 요청 크기에 “가장 근접한(가장 작은 오차로 맞아떨어지는)” 블록을 선택한다. 즉, 프로세스가 요구하는 메모리 크기 이상인 블록들 중, 남는 공간이 최소가 되는 블록을 할당하는 방식이다.
• 특징:
  • 단편화를 줄이기 위한 시도: 가능한 한 정확한 크기의 블록에 할당하여 남는 공간(단편화)을 최소화한다.
  • 하지만 실제로는 Best-Fit에서도 작은 단편화가 여러 곳에 산재하기 쉽고, 필요한 블록을 찾기 위해 전체 리스트를 훑어야 하므로 탐색 비용이 크다.
• 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB]이고, 4MB 할당 요청이 왔다면, Best-Fit은 가능한 블록(5MB, 12MB, 7MB) 중, 남는 공간이 가장 적은 5MB 블록을 선택한다. 이로써 1MB 남는 공간이 발생하지만, 다른 블록(7MB나 12MB)을 선택했다면 남는 공간이 더 커질 것이다.

3. Worst-Fit 알고리즘

• 개념: 요청 크기보다 큰 블록들 중 가장 큰 블록을 선택해 할당한다.
• 특징:
  • 의도: 가장 큰 블록을 나누어 쓰면, 나머지 부분이 상대적으로 크게 남아 이후 큰 요청을 수용하기 쉽다고 기대할 수 있다.
  • 실전에서는 큰 덩어리를 잘라쓰는 과정에서 실제 단편화가 더 커질 수도 있어 효율성을 장담하기 어렵다.
  • Best-Fit과 반대로 가장 큰 블록을 선택하기 때문에, 탐색 비용이 클 수 있으며, 단편화 문제가 여전히 발생한다.
• 예시: 빈 블록이 [5MB, 12MB, 3MB, 7MB]에서 4MB 할당 요청이 왔다면, Worst-Fit은 [12MB] 블록을 선택하여 4MB 할당 후 8MB가 남는다. 나중에 큰 요청이 들어오면 남은 8MB 블록이 유용할 수 있다.

메모리 단편화(Fragmentation) 는 메모리에 빈 공간이 산재하여, 프로세스가 할당되지 못하는 상황을 말합니다. 메모리 단편화는 외부 단편화와 내부 단편화로 나뉩니다.

• 외부 단편화(External Fragmentation): 메모리에 사용하지 못하는 작은 조각들이 산재하는 상황을 말합니다. 외부 단편화는 메모리 공간이 충분하지만, 연속적이지 않아 프로세스를 할당할 수 없는 상황입니다.

• 내부 단편화(Internal Fragmentation): 프로세스가 요구하는 메모리보다 더 큰 메모리 공간을 할당하는 상황을 말합니다. 내부 단편화는 메모리 공간이 충분하지만, 프로세스가 사용하지 않는 메모리 공간이 발생하는 상황입니다.

불연속 메모리 할당(Non-Contiguous Memory Allocation): 프로그램이 연속적인 메모리 공간에 할당되지 않는 방법으로, 프로그램이 실행되는 동안 메모리 공간이 변할 수 있습니다.

• 페이징(Paging): 프로그램을 고정된 크기의 페이지로 나누어 메모리에 할당하는 방법
• 세그멘테이션(Segmentation): 프로그램을 논리적인 단위인 세그먼트로 나누어 메모리에 할당하는 방법

가상 메모리(Virtual Memory)

가상 메모리(Virtual Memory) 는 물리 메모리를 보조기억장치로 확장하는 기법으로, 프로그램이 물리 메모리보다 큰 메모리 공간을 사용할 수 있도록 합니다.

가상 메모리는 프로그램이 필요한 부분만 물리 메모리에 올리고, 나머지 부분은 보조기억장치에 저장합니다. 프로그램이 실행되는 동안 필요한 부분만 물리 메모리에 올려 사용하고, 필요 없는 부분은 보조기억장치에 저장합니다.

• 요구 페이징(Demand Paging): 프로그램이 실행되는 동안 필요한 페이지만 물리 메모리에 올리는 방식
• 유효-무효 비트(Valid-Invalid Bit): 페이지 테이블에 있는 비트로, 페이지가 물리 메모리에 있는지 여부를 나타냅니다.
• 페이지 폴트(Page Fault): 프로그램이 실행되는 동안 필요한 페이지가 물리 메모리에 없어서 보조기억장치에서 가져오는 현상

요구 페이징의 성능은 페이지 폴트의 발생 빈도에 크게 영향을 받습니다. 페이지 폴트는 디스크에서 정보를 읽어오는 막대한 시간이 소요되기 때문에, 페이지 폴트의 발생 빈도를 줄이는 것이 중요합니다.

• 페이지 교체 알고리즘: 페이지 폴트가 발생할 때, 물리 메모리에 있는 페이지 중 어떤 페이지를 교체할지 결정하는 알고리즘

  • FIFO(First-In, First-Out): 가장 먼저 들어온 페이지를 교체하는 알고리즘
  • LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
  • LFU(Least Frequently Used): 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘
  • Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
  • Clock: 하드웨어 지원을 받아 LRU를 근사하는 알고리즘, 참조 비트를 사용하여 페이지를 교체한다.

1. FIFO (First-In, First-Out) 알고리즘

• 개념: 가장 먼저 들어온(가장 오래된) 페이지를 우선적으로 제거한다.
• 특징:
  • 구현이 단순하며 큐(Queue) 자료구조를 사용해 쉽게 관리할 수 있다.
  • 프로그램의 실제 메모리 참조 패턴을 고려하지 않기 때문에, 실질적인 성능 측면에서 비효율적일 수 있다.
  • Belady의 모순(Belady’s anomaly) 라고도 불리는 FIFO 알고리즘의 오류(FIFO Anomaly) 가 발생할 수 있다. 페이지 프레임 수를 늘렸을 때 페이지 부재 횟수가 증가하는 현상이다.
• 적용 예시:
  • 메모리 프레임이 3개일 때, A → B → C → A → B → D 순서로 페이지 참조가 발생할 경우, 가장 먼저 들어왔던 A, B, C 순서대로 내보낸다.

2. LRU (Least Recently Used) 알고리즘

• 개념: 가장 최근에 사용된 시점을 기준으로 오래 사용되지 않은 페이지부터 교체한다.
• 특징:
  • 최근에 많이 사용된 페이지는 앞으로도 사용될 가능성이 높다는 지역성(Locality)을 가정한다.
  • FIFO보다 성능 면에서 대개 우수하지만, 각 페이지 접근 시점에 대한 기록이 필요해 구현 복잡도가 올라간다.
  • 페이지 접근 시마다 시간을 기록하거나 스택과 유사한 자료구조를 활용하여 현재 사용 패턴을 추적할 수 있다.
• 적용 예시:
  • 메모리 프레임이 3개, 참조 순서가 A → B → C → A → B → D → A → C라 할 때, D를 로드할 때는 A, B, C 중 가장 오래 참조되지 않은 페이지를 찾아 제거한다(예: C가 가장 오랫동안 미사용 상태였다면 C 제거).

3. LFU (Least Frequently Used) 알고리즘

• 개념: 사용 빈도(참조 횟수)가 가장 낮은 페이지를 교체한다.
• 특징:
  • 단순히 최근 시점이 아닌 전체 참조 횟수를 기준으로 교체를 결정한다.
  • 장기간 거의 사용되지 않은 페이지가 분명히 제외될 수 있다는 장점이 있으나, 최근에 많이 쓰였지만 아주 과거에 사용 횟수가 적었던 페이지가 비효율적으로 제거될 수 있다.
  • 참조 횟수를 관리하기 위한 추가적인 카운터나 자료구조가 필요하다.
• 적용 예시:
  • A, B, C 페이지가 있고, A는 총 5번, B는 총 3번, C는 총 1번 참조되었다면, 새로운 페이지를 로드할 때 C(1회 참조)를 우선 제거한다.

4. Optimal 알고리즘

• 개념: 이론상 가장 이상적인 알고리즘으로, 앞으로의 페이지 참조 패턴을 모두 알고 있다고 가정했을 때, 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거한다.
• 특징:
  • 실제로 미래에 어떤 페이지가 필요할지 정확히 알 수 없으므로, 현실적으로 구현 불가능하다.
  • 다른 알고리즘의 성능을 평가하기 위한 기준(비교 대상)이 된다.
  • 가능한 페이지 부재 횟수를 최소화한다.
• 적용 예시:
  • 참조 순서가 A → B → C → D → A → B일 때, D를 로드하기 위해 어떤 페이지를 빼야 할 지를 미래 참조 기반으로 판단한다. 앞으로 가장 늦게 사용할 페이지를 선택해 제거한다(예: A와 B는 곧 필요하나 C는 한참 뒤나 필요 없으므로 C 제거).

5. Clock 알고리즘

• 개념: LRU를 근사하는 알고리즘으로, 참조 비트를 사용하여 페이지를 교체한다. LRU와 비슷한 성능을 보이면서도 구현이 간단하다. 하드웨어가 지원해주기 때문이다.
• 특징:
  • 페이지를 참조하면 해당 페이지의 참조 비트를 1로 설정한다.
  • 교체 시, 시계 바늘을 회전시키며 참조 비트가 0인 페이지를 찾을 때까지 이동한다. 참조 비트가 1인 페이지는 0으로 재설정만 하고 넘어간다.
  • 한 바퀴 돌아도 0인 페이지가 없다면, 그제서야 이미 1에서 0으로 리셋한 페이지 중 하나를 제거한다.
  • FIFO에 비해 자주 사용되는 페이지의 잔류 확률을 높여 성능을 개선한다.