단편화(fragmentation)

컴퓨터 메모리에서 사용 가능한 메모리 공간이 작은 조각으로 나뉘어 실제로 사용 가능한 전체 공간은 충분하지만, 연속적인 큰 공간이 없어 할당이 불가능한 현상

내부 단편화 (Internal Fragmetation)

내부 단편화는 메모리를 할당할 때 필요한 크기보다 더 큰 공간이 할당되어 남는 공간이 발생하는 현상

• 원인: 고정된 크기 단위로 메모리를 할당하는 방식에서 주로 발생. 페이징(Paging)기법에서는 메모리를 4KB와 같은 고정된 페이지 단위로 관리. 프로세스가 10KB의 공간을 필요로 한다면, 운영체제는 4KB 페이지 3개를 할당. 그럼 마지막 3번째 페이지는 2KB만 사용하고 남은 2KB는 낭비된다. 이 낭비된 공간이 내부 단편화.
• 특징: 할당된 메모리 블록 내부에 발생, 낭비되는 공간을 다른 프로세스가 사용할 수 없다.

외부 단편화 (External Fragmentation)

외부 단편화는 메모리 내에 사용 가능한 총 공간은 충분하지만, 이 공간들이 연속적이지 않고 여러 개의 작은 조각으로 흩어져 있어 큰 메모리 요청을 충족시킬 수 없는 현상

• 원인: 가변적인 크기 단위로 메모리를 할당하고 해제하는 과정에서 발생. 세그멘테이션(Segmentation) 기법에서 여러 프로세스가 메모리에 할당. 해제되면서 중간중간에 작은 빈 공간이 생겨나는데 이 조각을 모으면 충분히 큰 공간이 되지만, 연속적이지 않아 큰 프로세스 하나를 할당할 수 없게 됨
• 특징: 할당되지 않은 메모리 공간들 사이에 발생. 이를 해결하기 위해 압축(Compaction)이라는 기법을 사용할 수 있다. 압축은 흩어진 메모리 조각들을 한 곳으로 모아 하나의 큰 연속적인 공간으로 만드는 작업이지만, 비용이 많이 들고 복잡

---

페이징과 세그멘테이션

페이징(Paging)

논리적 메모리를 페이지(page)라는 고정된 크기의 블록으로 나누고, 물리적 메모리를 프레임(frame)이라는 같은 크기의 블록으로 나누어 관리하는 기법

• 특징: CPU가 사용하는 논리 주소는 '페이지 번호(page number)'와 '변위(offset)'로 구성되며, 운영 체제는 페이지 테이블(page table)을 이용해 물리적 프레임 번호를 찾아 실제 물리 주소로 변환한다.
• 장점: 외부 단편화(external fragmentation) 문제를 해결
• 단점: 내부 단편화(internal fragmentation)가 발생할 수 있습니다. 예를 들어, 프로세스 크기가 4KB 페이지 2.5개라면 마지막 페이지는 절반만 사용되고 나머지 절반은 낭비된다.

세그멘테이션(Segmentation)

세그멘테이션은 프로그램을 논리적 단위인 세그먼트(segment)로 나누어 관리하는 기법
세그먼트의 크기는 가변적이며, 코드, 데이터, 스택 등 의미 있는 논리적 단위로 나뉜다.

• 특징: 논리 주소는 '세그먼트 번호(segment number)'와 '변위(offset)'로 구성되며, 세그먼트 테이블(segment table)에는 각 세그먼트의 시작 주소와 크기가 저장된다.
• 장점: 논리적인 구조를 반영하여 메모리를 보호하고 공유하기 용이함
• 단점: 외부 단편화 문제가 발생할 수 있다. 가변적인 크기의 세그먼트들이 할당, 해제되면서 메모리 중간에 사용하지 못하는 작은 공간들이 생겨난다.

---

가상 메모리(Virtual Memory)

가상 메모리는 실제 물리 메모리(RAM)보다 훨씬 큰 논리적 메모리 공간을 제공하는 기술
프로세스는 메인 메모리 전체를 사용하는 것처럼 인식하지만, 실제로 필요한 부분만 물리적 메모리에 로드하고 나머지는 보조 기억장치에 저장함

• 동작 방식: 페이징 기법을 기반으로 구현되며, 페이지 테이블에 유효/무효 비트를 추가하여 해당 페이지가 메모리에 있는지(유효) 보조 기억장치에 있는지(무효)를 나타낸다.
• 페이지 폴트(Page Fault): CPU가 접근하려는 페이지가 현재 물리 메모리에 없는 경우 발생하는 인터럽트
• 장점: 물리 메모리 크기의 제약을 넘어 더 큰 프로그램을 실행할 수 있으며, 여러 프로세스를 동시에 메모리에 올릴 수 있어 멀티태스킹 효율을 높인다.
• 문제점: 쓰레싱(Thrashing)이 발생할 수 있다. 이는 페이지 폴트가 너무 자주 발생하여 CPU가 프로세스 실행보다 페이지 교체에 대부분의 시간을 소모하는 현상으로, 과도한 프로세스 수가 할당될 때 발생할 수 있다.

---

페이지 교체 알고리즘

페이지 폴트가 발생했을 때, 물리 메모리에 빈 프레임이 없다면 기존의 페이지를 디스크로 내보내고 새로운 페이지를 로드해야 하는데 이때 어떤 페이지를 내보낼지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

• FIFO(First-In, First-Out): 메모리에 가장 먼저 들어온 페이지를 먼저 내보낸다. 페이지가 메모리에 들어온 순서를 큐(Queue)로 관리. 페이지 폴트 발생 시, 큐의 가장 앞에 있는 페이지(가장 오래된 페이지)를 제거하고 새로운 페이지를 큐의 맨 뒤에 추가
  • 특징: 구현이 간단하지만, 자주 사용되는 페이지가 초기에 로드된 경우에도 쫓겨나는 Belady의 모순(페이지 프레임 수를 늘렸는데 오히려 페이지 폴트 횟수가 증가하는 현상)이 발생할 수 있다.
• LRU(Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 내보낸다. 과거에 오랫동안 사용되지 않았다면 미래에도 사용될 가능성이 낮다는 가정을 기반
  • 특징: 미래에 사용될 가능성이 가장 낮은 페이지를 내보내는 합리적인 방식
    하지만, 각 페이지의 마지막 사용 시간을 추적해야 하므로 구현이 복잡하고 오버헤드가 크다.
• LFU(Least Frequently Used): 참조 횟수가 가장 적은(사용 빈도가 가장 낮은) 페이지를 내보낸다. 자주 사용되는 페이지는 메모리에 유지하려는 목적
  • 특징: 사용 빈도를 추적해야 하므로 구현이 복잡. 또한 한 번 많이 사용되고 더 이상 사용되지 않는 페이지가 메모리에 계속 남아있을 수 있다는 단점
    각 페이지마다 참조 횟수를 저장하는 카운터(counter)를 두고, 페이지가 참조될 때마다 카운터를 1씩 증가시킴. 페이지 폴트 발생 시, 카운터 값이 가장 작은 페이지를 교체
• NUR(Not Used Recently): LRU의 복잡성을 개선하기 위한 알고리즘으로 최근 사용 여부만 파악하여 교체 대상을 선정한다.
  • 특징: 각 페이지에 참조 비트(Reference Bit)와 변형 비트(Modified Bit)를 둔다. 참조 비트는 페이지가 참조될 때 1로 설정되고, 변형 비트는 페이지 내용이 변경될 때 1로 설정된다.
    LRU에 비해 구현이 간단하고 실제 시스템에서 효율적으로 작동
  • 교체 대상 선정: 페이지 교체가 필요할 때, 다음 우선순위에 따라 페이지를 찾는다. (낮을수록 우선순위 높음)
  1. (0, 0): 참조되지도 않았고 내용도 변경되지 않은 페이지
  2. (0, 1): 참조되지는 않았지만 내용이 변경된 페이지 (교체 시 디스크에 써야 함)
  3. (1, 0): 최근에 참조되었지만 내용이 변경되지 않은 페이지
  4. (1, 1): 최근에 참조되었고 내용도 변경된 페이지
• OPT(Optimal): 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘으로 이론상 최고 효율을 가진다.
  • 특징: 모든 페이지 교체 알고리즘 중에서 가장 적은 페이지 폴트 횟수를 보장하여 다른 알고리즘의 성능을 평가하는 기준으로 사용된다.
    하지만, 미래에 어떤 페이지가 언제 사용될지 미리 알 수 없기 때문에 실제 구현이 불가능

---

MMU(Memory Management Unit)

MMU(Memory Management Unit)는 CPU 내부에 위치한 하드웨어로, 논리 주소를 물리 주소로 변환하는 역할을 담당
페이징과 세그멘테이션의 주소 변환 과정은 MMU를 통해 효율적으로 이루어진다.