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비트)

• 첫줄은 이렇게 나누려고 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)라고 한다.

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

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

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

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

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

17. 빈 공간 관리

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

• 문제를 너무 잘 요약해서 책을 발췌하면, 관리해야 하는 공간이 가변 크기의 빈 공간으로 나뉘어져 있는 이슈를 해결해야한다.
• 위의 예시처럼, 빈공간은 20바이트나 있는데, 15바이트 할당에 실패한다.

17.1 가정

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

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

17.2 저 수준의 기법들

1. 빈공간 list 만들기

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

2. 분할

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

3. 병합

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

사실 병합의 문제는 간단히 해결 할 수 있다, 메모리가 반환되는 ‘시점’에 빈공간 리스트의 인접한 노드를 검사하고 병합시키면 된다. 참고로 포인터는 헤더가 있어서 실제 할당하려고 하면, 요청한 메모리 + 헤더 크기만큼 할당한다.

빈 공간 리스트 내장

• 새로운 노드를 위한 공간이 필요할 때 malloc()을 호출함
• 메모리 할당 라이브러리 루틴에서는 이게 불가능하고, 대신 빈 공간 내에 리스트를 구축해야함

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

...

node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

• 이렇게 초기화는 해두고,
• 메모리 청크 (예시 100바이트)가 요청되면 먼저 충분한 크기의 청크를 찾는다.
• 지금은 4088의 하나의 청크만이 존재하니까 여기가 선택된다.
• 그 후 헤더를 포인터 앞에 적고, 100바이트를 할당하고 스플릣한다.
• 지금까지의 과정
• 그리고 세개의 100바이트 청크가 있다가 가운데 하나가 해제되는 상황을 가정한다.
• 그러면 라이브러리는 빈공간리스트에 해당 반환된 공간을 삽입한다. (단편화 발생)
• 그리고 나머지가 반환되면 여러개의 빈공간 리스트가 생긴다.
• 요걸 다시 리스트순회해서 인접한 리스트끼리 합쳐서 하나의 빈공간으로 만든다.

#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. 페이징: 개요

가변 크기의 조각은 청크로 분할 할 때 공간자체가 단편화되고, 할당은 점점 더 어려워진다. 두 번째 방법인 공간을 동일한 조각으로 분할하는 것을 고려해볼 필요가 있다. 논리적 단위가 아닌 고정크기로 나누는 방법이고 그 크기 단위를 Page 메모리도 Page frame이라고 불리는 고정 크기의 슬롯의 배열로 바라본다.

핵심 질문 : 페이지를 사용하여 어떻게 메모리를 가상화 할 수 있을까?

18.1 간단한 예제 및 개요

• 128 바이트의 (비현실적으로 작은) 물리 메모리의 예시
• 가상 주소 공간의 페이지들은 물리메모리 전체에 분산 배치되어있다.
• 이전 방식에 비해 다양한 장점을 가지고 있다.
  • 일단 먼저 유연하다. 힙과 스택이 어떠한 방식으로 커지는가, 어떻게 사용되는가에 대한 가정이 필요 없다.
  • 다음으로 단순하다. 64바이트 주소공간을 8페이지 물리메모리에 배치한다고 했을 때, 4개의 비어있는 페이지만 찾으면 된다.
• 주소공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블이라는 자료 구조를 유지한다.
• 주소공간의 가상페이지 주서 변환 정보를 저장하는것이다. (virtual page 1 -> physical page 7) …
• 페이지 테이블은 프로세스마다 존재한다.
• 프로세스가 생성한 가상 주소의 변환을 위해 먼저 가상 주소를 가상 페이지 번호(Virtual Page Number)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다.

가상 페이지 번호(VPN) 계산 • 0x1C34A8 = 0001 1100 0011 0100 1010 1000₂ • 상위 20비트가 VPN: 0001 1100 0011 0₂ = 0x1C3 • VPN = 0x1C3 (10진수: 451)

페이지 오프셋 계산 • 하위 12비트: 0100 1010 1000₂ = 0x4A8 • 오프셋 = 0x4A8 (10진수: 1192)

테이블에서 물리 페이지 주소 얻기

• 0x1C3 -> 0x2F5

물리 주소 계산

물리 주소 = (PFN « 12) | Offset = (0x2F5 « 12) | 0x4A8 = 0x2F5000 + 0x4A8 = 0x2F54A8 (10진수: 3099432)

18.2 페이지 테이블은 어디에 저장되는가

• 기본적으로 추정하면 페이지 테이블의 용량은 산술적으로 엄청 큼
• 각 프로세스의 페이지 테이블을 메모리에 저장하는데, 당분간은 운영체제가 관리하는 물리 메모리에 상주한다고 가정하자.

18.3 페이지 테이블에는 실제 무엇이 있는가

• 가장 간단한 형태는 선형 페이지 테이블이고 단순한 배열이다.
• VPN으로 배열의 항목에 접근하고, 그항목의 페이지 테이블 항목(PTE)를 검색한다. (고 가정)
• Valid bit : 특정 변환의 유효 여부를 나타내기 위해서 포함 (모든 미사용 공간은 invalid) 만약 거기 접근하면 운영체제에 트랩을 발생시킨다. 또한 할당하지 않은 주소공간이라는 표식으로써 기능하 실제 물리 프레임을 할당할 필요을 없애 대량의 메모리를 절약한다.
• Protection bit : 읽기, 쓰기, 실행 가능 여부를 포함하는 비트이다. 허용되지 않은 방식의 접근은 트랩을 생성한다.
• Present bit : 페이지가 물리 메모리에 있는지, (혹은 스왑아웃 되었는지) 확인한다.
• Dirty bit : 페이지가 메모리에 적재된 이후 변경되었는지를 추적한다.
• reference bit : 페이지가 접근되었는지를 추적한다, 어떤 페이지가 인기있는지 확인하고 페이지 교체 알고리즘에 사용된다.

18.4 페이징: 너무 느림

movl 2l, %eax

• 가상주소 (21)을 정확한 물리적 주소 (117)로 변환해야한다.
• 117에서 데이터를 반입하기 전에 시스템은 프로세스의 페이지 테이블에서 적절한 페이지 테이블 항목을 가져와야하고,
• 변환을 수행한 후, 물리메모리에서 데이터를 탑재한다.
• 하드웨어는 현재 실행중인 프로세스의 페이지 테이블의 위치를 알아야 한다.
• 당분간 하나의 페이지 테이블 베이스 레지스터가 페이지 테이블의 시작 주소(물리주소)를 저장한다고 가정한다. (위의 물리 주소 계산 이후의 계산을 진행해야함)