Week-06

16. 세그멘테이션

16.1 베이스 바운드의 일반화

지금 가정의 단계에서 내부단편화가 발생하는 요인은 스택과 힙 사이에 사용하지 않는 메모리가 존재하는 것이다.

• 세그멘테이션은 60년대에 이미 사용되던 메모리 관리 기법이다.

• 기본적으로 세그멘테이션은 세그먼트마다 베이스와 바운드를 가지고 있다.

• 세그먼트란 논리적인 단위로, 프로그램이나 데이터를 담고 있는 논리적인 단위이다. (스택, 힙, 데이터영역, 코드영역 등)

• 즉 논리적인 단위로 나누어진 세그먼트(논리적 단위)에 각각 베이스와 바운드를 주는 것이다.

• 그외에는 베이스 바운드 기법을 사용한다. 예를들어 가상주소가 100, 베이스가 50, 바운드가 110이라면, 베이스 주소인 50으로 가서 100을 더하면 150이 되는데, 이는 바운드보다 크기 때문에 오류가 발생한다. (똑같음)

참고로 베이스 + 오프셋(가상주소)이 바운드보다 크면 오류가 발생하는데, 이걸 Segment Fault라고 한다.

‘일반화’ 라는 단어가 뭔가 묘하게 어울리지 않는 것 같아서 약간 헷갈릴 수 있지만 어려운 내용은 아니다.

16.2 세그먼트 종류에 대한 파악

당연하게도 뭐하나 자동으로 되는건 없다. 세그먼트를 베이스를 기반으로 참조했을때 이 세그먼트가 어떤 종류인지도 알 수 있도록 조치해야한다.

• 처음에는 네트워크에서 헤더 붙이는 것처럼 주소값에 최상위 몇 비트를 이용해서 구분했다.

Segment = (VirtualAddress & SEGMENT_MASK) >> SEGMENT_SHIFT

Offset = VirtualAddress & OFFSET_MASK

if Offset > SegmentSize[Segment] then
  Raise Exception(SEGMENTATION_FAULT)
else
  PhysicalAddress = Base[Segment] + Offset
  Register = Memory[PhysicalAddress]

해석

여기서 목표는 아래와 같음

가상 주소: 1100 0101 0010 1101 1010 1111 0001 0011 (32비트)
세그먼트 번호: 1100 (상위 4비트)
오프셋: 0101 0010 1101 1010 1111 0001 0011 (하위 28비트)

근데 우리는 아니까 앞에 4비트를 떼어내서 세그먼트 번호를 구할수 있는데, 컴퓨터는 멍청해서 그게 안된다.

첫줄은 이렇게 나누려고 SEGMENT_MASK로 &연산을 해서 세그먼트 번호를 구하는 코드

SEGMENT_MASK: 1111 0000 0000 0000 0000 0000 0000 0000 (32비트)

VirtualAddress: 1100 0101 0010 1101 1010 1111 0001 0011
SEGMENT_MASK:   1111 0000 0000 0000 0000 0000 0000 0000
결과:            1100 0000 0000 0000 0000 0000 0000 0000

여기서 결과값에 쉬프트 연산으로 다 밀어버리면 세그먼트 번호가 나온다.

비슷한 과정을 거쳐 오프셋을 구한다.

Base[Segment] : 해당하는 세그먼트의 베이스 주소, 여기다 오프셋을 더하면 물리주소가 나온다.

그리고 해당 주소값을 참조하기!

문제점

• 문제는 이러한 방식은 최대 세그먼트의 크기와 같은 것들이 ‘고정’이고, ‘약속’이 되어 있다는 것!

• 또한 위에 주소 비트를 이용해서 세그먼트를 구분하는데 쓰는것도 생각보다 더 비용이 많이 든다.

• 예를들어 앞에 네 비트를 사용하면 실제 offset으로 사용할 수 있는 비트가 2^4만큼 줄어든다.

• 16억개의 메모리 주소를 사용할 수 있었을건데 비트 네개를 까버리면 1억개만 사용할 수 있게 된다.

16.3 스택

스택이라고 소개를 하지만, 사실 세그먼트의 특성에 따라 관리와 행동이 달라진다는 것을 보여주는 예시

• 스택이라는 세그먼트는 주소가 음의 성장을 한다. 이거 cpp보면 진짜 그럼

• 이젠 순방향으로 증가하는지 여부를 어딘가에 저장해야한다.

• 그래서 스택 세그먼트에는 방향 비트를 추가해서 어느 방향으로 증가하는지를 표시한다.

16.4 공유 지원(Support for Sharing)

여기는 번역이 너무 이상하다. 예시에 대한 설명이 부족한데 갑자기 보호비트 이야기가 나와서 당황하스러움..

• 결론적으로는 일단, 특정 세그먼트를 공유하는게 메모리 공간상 효율적일 수 있는데, 바로 ‘code’를 공유하는 것이다.

• 가장 직관적으로 비유하면 라이브러리 같은 것을 공유하는 것이다.(정확하지는 않지만 c로 작성된 프로그램이 여럿인데, stl을 여러개 메모리에 올릴 이유가 없음!)

• 이건 진짜 좋긴 하지만 위험하니까, 공유를 위해 보호 비트를 추가해서 공유한다는게 주요 내용이다.

여기까지 세그먼트 레지스터에 저장해야할 데이터는 아래와 같다.

16.5 소단위대 대단위 세그멘테이션

• 지금은 대단위 세그멘테이션을 한다. (스택, 힙, 코드, 데이터) 요정도로만 크게크게 나눠서 대단위라고함

• 그런데 필요성에 따라서, 더 작은 단위로 나누어서 세그멘테이션을 할 수도 있다.

• 이렇게 세그먼트를 줄이고 많이 가지고 있으면 세그멘트 테이블 같은 새로운 하드웨어 지원이 필요하다.

16.6 운영체제의 지원

세그멘테이션 덕분에 낭비되는 ‘물리’메모리 없이 메모리를 효율적으로 사용할 수 있게 되었다. 근데 당연하게도 세그먼트가 야기하는 문제가 있고, 세그먼트가 아직 해결 못한 문제도 있다. 세그먼트가 야기하는 문제와 세그먼트로 해결 못한 문제 마지막으로 그걸 운영체제가 어떻게 해결 할 수 있는지 알아본다.

1. 세그먼트가 야기하는 문제

• 컨텍스트 스위치 시 세그먼트 레지스터 관리 문제
  • 각 프로세스는 자신의 가상 주소 공간을 가지고 있어, 컨텍스트 스위치 시 운영체제가 세그먼트 레지스터를 저장하고 복원해야 한다.(오버헤드가 커지겠지!)
• 세그먼트 크기 변경 시의 문제
  • 프로그램이 malloc()을 호출할 때, 기존 힙에서 요청을 처리할 수 없으면 힙 세그먼트가 커져야 한다.
  • 메모리 할당 라이브러리가 시스템 호출을 통해 힙을 확장하고, 운영체제는 힙을 확장하여 세그먼트 크기 레지스터를 업데이트하고, 라이브러리에 성공을 알린다.
  • 운영체제는 물리 메모리가 부족하거나 호출된 프로세스가 이미 너무 많은 메모리를 사용하고 있다고 판단하면 요청을 거부할 수 있다.
• 물리 메모리의 빈 공간 관리 문제
  • 새로운 주소 공간을 생성할 때 운영체제는 세그먼트에 대한 물리 메모리 공간을 찾아야 한다.
  • 물리 메모리가 작은 빈 공간들로 나뉘어 새로운 세그먼트를 할당하거나 기존 세그먼트를 확장하기 어려워진다. 이를 외부 단편화(external fragmentation)라고 한다.

2. 세그먼트가 아직 해결 못한 문제

• 외부 단편화 문제
  • 세그먼트가 가변 크기이기 때문에 빈 메모리가 작은 조각들로 나뉘어져 메모리 할당 요청을 충족하기 어렵게 된다.
• 완전히 일반화된 희박한 주소 공간 지원 부족 문제
  • 큰 논리적 세그먼트(예: 희박한 힙)가 메모리에 완전히 상주해야 한다.
  • 주소 공간 사용 모델이 세그멘테이션 설계 방식과 일치하지 않으면 세그멘테이션이 잘 작동하지 않는다.

3. 운영체제가 세그멘테이션 문제를 해결하는 방법

• 메모리 압축 방법 운영체제는 프로세스를 멈추고 데이터를 연속된 메모리 영역으로 복사하고, 세그먼트 레지스터 값을 새로운 물리적 위치로 변경하여 큰 빈 메모리 공간을 확보한다. 그러나 메모리 압축은 비용이 많이 든다.
• 자유 리스트 관리 알고리즘 사용 큰 메모리 공간을 유지하려고 시도하는 자유 리스트 관리 알고리즘을 사용한다. 대표적인 알고리즘으로는 best-fit, worst-fit, first-fit, buddy algorithm 등이 있다.

이러한 알고리즘은 외부 단편화를 최소화하려고 시도한다. 세그멘테이션은 메모리 가상화에서 여러 문제를 해결하지만, 여전히 외부 단편화와 희박한 주소 공간 지원 부족 문제를 가지고 있다. 운영체제는 메모리 압축과 다양한 자유 리스트 관리 알고리즘을 통해 이러한 문제를 해결하려고 노력하지만, 근본적인 문제는 여전히 존재하므로 더 나은 솔루션이 필요하다.

17. 빈 공간 관리

앞에서 세그먼트로 나눔으로써, 내부 단편화를 해결했지만 외부 단편화 문제가 주요하게 남아있다. 즉 고정 메모리 범위를 사용하면서 발생하는 문제를 세그먼트 단위로 적재하면서 해결했지만, 세그먼트를 메모리에 적재하는데 발생하는 문제가 외부 단편화이다.

• 문제를 너무 잘 요약해서 책을 발췌하면, 관리해야 하는 공간이 가변 크기의 빈 공간으로 나뉘어져 있는 이슈를 해결해야한다.

17.1 가정

이 논의의 대부분은 사용자 수준의 메모리 할당 라이브러리의 발전 역사를 중심으로 한다. (malloc()과 free()는 실시간으로 힙 세그먼트 내부의 빈 공간을 조정해야 하는 역할을 필연적으로 가지게 된다.)

1. 외부 단편화를 해결하는데 초점을 맞춘다.
2. 할당된 메모리는 다른 위치로 이동할 수 없다.

17.2 저 수준의 기법들

1. 빈공간 list 만들기

• 빈 공간을 관리하기 위해 위처럼 말 그대로 빈 공간의 리스트를 만들어서 관리한다.

2. 분할

• 빈 공간을 나누어서 할당하는 방법이다.
• 일단 요청이 청크보다 작으면, 청크를 나누어 사용자에게 할당하고, 남은 부분은 리스트에 남긴다.

3. 병합

• 반환받은 메모리를 병합시키는 방법이다.
• 문제는 여기서 발생한다.
• 위의 사진에서 10을 사용하던 두 메모리가 반환됐을때, 10을 의미하는 빈공간 리스트의 세개의 노드가 존재하게 되고, 사실상 30이 연달아 있어 사용할 수 있는 메모리가 30이 되어야 하는데,
• list를 순회하며 10이 넘는 요청에 대한 메모리를 할당하지 못하도록 되어있다.

사실 병합의 문제는 간단히 해결 할 수 있다, 메모리가 반환되는 ‘시점’에 빈공간 리스트의 인접한 노드를 검사하고 병합시키면 된다.

참고로 포인터는 헤더가 있어서 실제 할당하려고 하면, 요청한 메모리 + 헤더 크기만큼 할당한다.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>

typedef struct __node_t {
  int size;
  struct __node_t *next;
} node_t;

#define MAGIC 1234567
typedef struct {
  int size;
  int magic;
} header_t;

node_t *head = NULL;

// 힙 초기화 함수
void init_heap(int size) {
  head =
      mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0);
  if (head == MAP_FAILED) {
    perror("mmap");
    exit(1);
  }
  head->size = size - sizeof(node_t);
  head->next = NULL;
}

// 메모리 할당 함수
void *my_malloc(int size) {
  node_t *current = head;
  node_t *prev = NULL;

  while (current != NULL) {
    if (current->size >= size + sizeof(header_t)) {
      header_t *hptr = (header_t *)((char *)current + sizeof(node_t));
      hptr->size = size;
      hptr->magic = MAGIC;

      node_t *new_free = (node_t *)((char *)hptr + sizeof(header_t) + size);
      new_free->size = current->size - sizeof(header_t) - size - sizeof(node_t);
      new_free->next = current->next;

      if (prev == NULL) {
        head = new_free;
      } else {
        prev->next = new_free;
      }

      return (void *)(hptr + 1);
    }
    prev = current;
    current = current->next;
  }

  return NULL; // 할당 실패
}

// 메모리 해제 함수
void my_free(void *ptr) {
  header_t *hptr = (header_t *)ptr - 1;
  assert(hptr->magic == MAGIC);

  node_t *free_block = (node_t *)hptr;
  free_block->size = hptr->size + sizeof(header_t);

  node_t *current = head;
  node_t *prev = NULL;

  while (current != NULL && current < free_block) {
    prev = current;
    current = current->next;
  }

  free_block->next = current;
  if (prev == NULL) {
    head = free_block;
  } else {
    prev->next = free_block;
  }

  // 병합
  if (free_block->next != NULL &&
      (char *)free_block + free_block->size + sizeof(node_t) ==
          (char *)free_block->next) {
    free_block->size += free_block->next->size + sizeof(node_t);
    free_block->next = free_block->next->next;
  }

  if (prev != NULL &&
      (char *)prev + prev->size + sizeof(node_t) == (char *)free_block) {
    prev->size += free_block->size + sizeof(node_t);
    prev->next = free_block->next;
  }
}

// 힙 상태 출력 함수
void print_heap() {
  node_t *current = head;
  printf("Free list:\n");
  while (current != NULL) {
    printf("Address: %p, Size: %d\n", current, current->size);
    current = current->next;
  }
}

int main() {
  init_heap(4096); // 4KB 힙 초기화

  void *a = my_malloc(100);
  void *b = my_malloc(100);
  void *c = my_malloc(100);

  print_heap();

  my_free(b);

  print_heap();

  my_free(a);
  my_free(c);

  print_heap();

  return 0;
}

17.3 힙의 확장 기본 전략

힙의 확장은 빈 공간이 부족할 때, 더 큰 메모리 공간을 할당하는 것을 의미한다. 없으면 NULL을 반환한다 -끝- 이 아니고

• 아래와 같은 기본 전략들이 있다.

1. 최적 적합 (Best-Fit)

• 동작 방식:
  • 메모리 할당 요청 시, 전체 자유 리스트를 탐색하여 요청된 크기에 가장 가까운(즉, 요청 크기에 가장 적게 남는) 자유 블록을 선택하는 방식이다.
  • 선택된 블록을 할당하고 남은 부분을 다시 자유 리스트에 추가하는 방식이다.
• 장점:
  • 메모리 공간을 최소한으로 낭비하게 하여 외부 단편화를 줄이는 데 도움이 된다.
• 단점:
  • 전체 자유 리스트를 탐색해야 하므로 탐색 시간이 오래 걸릴 수 있다.
  • 작은 조각들이 많이 남아 내부 단편화가 증가할 수 있다.

2. 최초 적합 (First-Fit)

• 동작 방식:
  • 메모리 할당 요청 시, 자유 리스트의 첫 번째부터 시작하여 요청된 크기를 만족하는 첫 번째 블록을 선택하는 방식이다.
  • 선택된 블록을 할당하고 남은 부분을 다시 자유 리스트에 추가하는 방식이다.
• 장점:
  • 탐색 시간이 짧아 효율적이다.
  • 대체로 빠른 할당이 가능하다.
• 단점:
  • 초기 부분에 작은 조각들이 많이 남아 외부 단편화가 발생할 수 있다.
  • 자주 사용되는 영역에 단편화가 발생할 가능성이 있다.

3. 최악 적합 (Worst-Fit)

• 동작 방식:
  • 메모리 할당 요청 시, 전체 자유 리스트를 탐색하여 가장 큰 자유 블록을 선택하는 방식이다.
  • 선택된 블록을 할당하고 남은 부분을 다시 자유 리스트에 추가하는 방식이다.
• 장점:
  • 큰 블록을 분할하여 큰 조각들이 남아 큰 메모리 요청을 처리하기 쉽다.
• 단점:
  • 큰 블록을 분할하면서 작은 조각들이 많이 남아 외부 단편화가 증가할 수 있다.

4. 다음 적합 (Next-Fit)

• 동작 방식:
  • 메모리 할당 요청 시, 이전 할당이 끝난 위치부터 시작하여 요청된 크기를 만족하는 첫 번째 블록을 선택하는 방식이다.
  • 선택된 블록을 할당하고 남은 부분을 다시 자유 리스트에 추가하는 방식이다.
• 장점:
  • 최초 적합과 유사한 성능을 가지며, 자주 사용되는 영역에 단편화가 덜 발생한다.
• 단점:
  • 자유 리스트가 순환 구조를 가지므로 리스트의 끝에서 다시 시작해야 할 경우 탐색 시간이 길어질 수 있다.

5. 개별 리스트 (Segregated List)

• 동작 방식:
  • 크기별로 여러 개의 자유 블록 리스트를 따로 관리하는 방식이다.
  • 요청된 크기에 맞는 리스트에서 블록을 할당하고, 필요 시 더 큰 블록을 분할하여 할당한다.
• 장점:
  • 특정 크기의 블록을 빠르게 찾을 수 있어 탐색 시간이 짧다.
  • 크기별로 관리하므로 특정 크기의 블록들이 적절히 분리되어 단편화를 줄이는 데 도움이 된다.
• 단점:
  • 여러 리스트를 관리해야 하므로 구현이 복잡할 수 있다.
  • 크기별 리스트에 따라 메모리 낭비가 발생할 수 있다.

6. 버디 할당기 (Buddy Allocation)

• 동작 방식:
  • 메모리를 2의 거듭제곱 크기로 분할하여 관리하는 방식이다.
  • 요청된 크기에 가장 적합한 크기의 블록을 할당하며, 필요 시 블록을 분할한다.
• 장점:
  • 메모리 병합이 쉽고 빠르며, 내부 단편화가 적다.
• 단점:
  • 항상 2의 거듭제곱 크기로 할당하므로, 일부 경우 외부 단편화가 발생할 수 있다.

18. 페이징: 개요