정의

메모리 리소스를 효율적으로 할당하고, 사용하고, 제거하는 과정을 말한다.

OS, HW, SW가 Memory를 어떻게 관리하느냐에 따라 시스템 성능과 안정성이 크게 좌우된다.

  • 효율적인 메모리 할당: 프로세스와 프로그램에 필요한 메모리를 적절하게 할당하고, 비효율적인 메모리 사용을 방지한다.
  • 메모리 보호: 한 프로세스가 다른 프로세스의 메모리에 접근하지 못하도록 보호하는 역할을 한다.
  • 가상 메모리 지원: 실제 메모리보다 더 많은 메모리 공간을 사용하는 프로그램을 실행할 수 있도록 가상 메모리를 지원한다.
  • 메모리 회수: 프로세스가 종료되거나 더 이상 사용하지 않는 메모리를 해제하여, 다른 프로세스가 사용할 수 있도록 한다.

Virtual Memory & Physical Memory

Memory를 프로세스(프로그램)에 할당하는 방식은 크게 두가지가 있다.

  • Physical Memory : 말 그대로 실제로 설치된 Memory의 크기를 말한다.
  • Virtual Memory : OS가 프로세스에 제공하는 가상 Memory 공간으로, Physical Memory보다 더 큰 공간을 사용할 수 있도록 한다. Linux의 swap이 Virtual Memory의 일종이라고 할 수 있다.

Paging

페이징은 Virtual Memory를 작은 Static Size의 블록(page)으로 나누어 Physical Memory의 프레임에 Provisioning 하는 방식이다.

페이징을 통해 Physical Memory와 Virtual Memory 사이의 매핑을 관리하며, 이로 인해 프로세스(프로그램)이 연속된 Memory Space를 요구하지 않아도 된다.

Segmentation

세그멘테이션은 Memory를 Dynamic Size의 Segment로 나누는 방식이다. 각 Segment는 논리적인 단위로, 프로세스의 코드, 데이터, 스택을 분리하여 관리한다.

Internal Fragmentation

내부 단편화는 메모리가 고정된 크기로 할당될 때, 할당된 메모리 블록 내에서 사용되지 않는 남은 공간이 발생하는 현상이다. 즉, 요청한 메모리보다 더 큰 메모리 블록이 할당될 때 발생한다.

해결책으로는 동적 메모리 할당, 블록 크기 다양화 등이 있다.

발생 원인

  • Management 기법에 따라 메모리는 종종 Static size 블록으로 할당된다. 즉, 프로그램이 필요로 하는 메모리 크기와 상관없이, 미리 정의된 고정된 크기의 메모리 블록을 Provisioning 한다.
  • 프로그램이 요청한 메모리 크기가 Static 블록보다 작으면, 남는 공간이 발생하며, 이 공간은 사용되지 않으면서 낭비된다.

예를 들어, 만약 128바이트 크기의 메모리 블록만 할당할 수 있다고 가정하고, 프로그램이 100바이트를 요청했다면, 28바이트는 사용되지 않으며 내부 단편화로 낭비된다.

특징

  • 내부 단편화는 할당된 메모리 블록 내부에서 발생하는 낭비이다.
  • 할당된 메모리 자체는 여전히 사용 중으로 간주되지만, 프로그램은 그 중 일부만 사용하고 나머지는 비어 있다.
  • 주로 페이징 시스템과 같이 고정된 크기로 메모리를 할당하는 메모리 관리 방식에서 발생한다.

External Fragmentation

외부 단편화는 메모리 할당과 해제가 반복될 때, 작고 비연속적인 빈 공간이 메모리 여러 곳에 분산되어 발생하는 현상이다. 이로 인해 전체적으로 충분한 메모리가 남아 있어도, 연속된 큰 메모리 블록을 할당하지 못하게 되는 상황을 말한다.

해결책으로는 Paging, Memory Compaction(압축)등이 있다.

발생 원인

  • 메모리는 할당과 해제를 반복하면서 불연속적인 빈 공간이 생깁니다. 즉, 프로그램이 종료되거나 더 이상 메모리를 사용하지 않으면 그 공간이 해제되지만, 다른 공간과 연속되지 않은 경우 큰 메모리 블록을 할당할 수 없게 된다.
  • 프로그램이 연속된 큰 메모리 블록을 필요로 할 때, 비록 메모리의 전체 사용 가능 공간이 충분하더라도 메모리 블록들이 서로 분리되어 있어 사용할 수 없다.

예를 들어, 시스템에 3개의 50MB, 200MB, 50MB의 빈 메모리 블록이 있다고 가정하자. 이때 150MB의 메모리를 할당하려고 하면, 개별 블록은 크기가 작아 할당할 수 없지만, 총 빈 메모리 공간은 300MB로 충분하다. 이 경우 외부 단편화가 발생하여 메모리를 효율적으로 사용할 수 없는 상태입니다.

특징

  • 외부 단편화는 메모리 전체에서 빈 공간이 단편적으로 존재하는 문제이다.
  • 총 빈 메모리 양은 충분해도, 큰 연속된 메모리 공간을 할당할 수 없는 경우 발생한다.
  • 주로 세그멘테이션 방식과 같이 가변 크기의 메모리 블록을 사용하는 시스템에서 발생한다.

Memory Management Strategy

first fit(최초 적합)

  • 가장 처음 만나는 빈 메모리 공간에 프로세스를 할당
  • 빠름

Best fit(최적 적합)

  • 빈 메모리 공간의 크기와 프로세스의 크기 차이가 가장 적은 곳에 프로세스를 할당

Worst fit(최악 적합)

  • 빈 메모리 공간의 크기와 프로세스의 크기 차이가 가장 큰 곳에 프로세스를 할당
  • 이렇게 생긴 빈 메모리 공간에 또 다른 프로세스를 할당할 수 있을 거라는 가정에 기인

Page Replacement Algorithm

페이지 교체 알고리즘의 핵심은 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상하는 것이다. 따라서, 이에 대한 구현 방식에 따라 아래와 같은 여러 종류의 페이지 교체 알고리즘이 만들어졌다.

FIFO (First In First Out, 선입선출)

시간상으로 물리 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 아웃시킨다. 페이지 부재일 때는 F, 원하는 페이지가 메모리에 있는 경우는 S로 표시되어 있다.

큐로 구현되어 있어, 새로운 페이지는 항상 맨 아래에 삽입되는데, 이때, 메모리가 꽉 차면, 맨 위의 페이지가 스왑 아웃되고 나머지 페이지들이 위쪽으로 이동하여, 새로운 페이지가 맨 아래로 들어온다.이 그림에서는 총 열 번의 페이지 요구에 대해 세 번만 성공하고, 페이지 부재는 일곱 번 발생했다. 페이지 교체 알고리즘에서는 앞으로 사용하지 않을 페이지를 스왑 아웃시키는 것이 중요한데, FIFO 알고리즘은 그렇지 않다. 따라서, 성능이 떨어진다.

OPT (Optimal, 최적)

최적 페이지 교체 알고리즘(Optimal)앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지, 즉 앞으로 사용하지 않을 가능성이 제일 높은 페이지를 대상 페이지로 선정한다.

4번 시점에서 이후에 A와 B 페이지가 사용될 것을 알고 있기 때문에 C 페이지를 대상 페이지로 선정해 스왑 아웃시킨다.하지만, 최적 페이지 교체 알고리즘은 어디까지나 이상적인 방법이므로 실제로는 미래의 접근 패턴을 알고 구현할 수가 없다. 따라서, 다음에 소개될 알고리즘들은 최적 페이지 교체 알고리즘에 근접하는 방법을 연구한 결과로 나온 알고리즘들이다.이러한 알고리즘들은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optimal Approximation Algorithm)이라고 부른다.

LRU (Least Recently Used)

메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 아웃시키는 알고리즘이다.

LFU (Least Frequently Used)

페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 즉, 현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 아웃시킨다.

위 그림에서 프레임 안에서 알파벳 아래의 숫자는 사용 빈도를 나타낸다. 이때, 사용 빈도가 같은 경우에는 FIFO, LRU, 무작위와 같은 추가 기준 알고리즘을 사용하여 대상 페이지를 선정하지만, 이 교재에서는 간단하게 맨 위의 페이지를 대상 페이지로 선정한다고 가정했다.따라서, 4번 시점에서는 페이지 A가 대상 페이지로 선정되고, 6번 시점에서는 페이지 A와 C의 사용 빈도가 가장 적고 같아 페이지 A가 대상 페이지로 선정되었다.알고리즘의 성능은 LRU 알고리즘과 비슷하다고 알려져 있다. 그러나, 페이지 접근 횟수(빈도)를 표시하는 데 LRU 알고리즘과 마찬가지로 메모리의 추가 공간이 필요하므로 낭비되는 메모리 공간이 많다는 단점이 존재한다.

참고로 Linux, Windows, macOS와 같은 대표적인 운영체제들은 LRU 알고리즘과 시계 알고리즘을 혼용해서 페이지 교체를 한다고 한다. 가장 오랫동안 사용되지 않는 페이지를 찾는 데에 효과적이고, 최근에 참조된 페이지를 보존하는 데에 효과적인 두 알고리즘의 장점을 조합하여 페이지 교체의 효율성을 높였다고 한다.

  • Ref.

https://medium.com/@mahmoudabdalghany/virtual-memory-b2c77308c9fd

https://www.baeldung.com/cs/virtual-memory-vs-swap-space

https://www.guru99.com/virtual-memory-in-operating-system.html

https://doh-an.tistory.com/28

https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/