운영체제

17) 빈 공간 관리

빈 공간 관리를 어떻게 하지??
만약 관리해야할 공간이 고정크기의 단위라면, 고정 크기 단위의 리스트만 유지하면 됨.
그래서 요청하면 공간을 주면 되니...

만약 관리해야할 공간이 가변적이라면,,?
malloc,free처럼 사용자가 메모리 할당할 수 있는 라이브러리, 세그멘테이션으로 실제 메모리를 관리하는 OS에서 발생

외부단편화가 발생해..

가정

• 할당, 할당해제를 위한 인터페이스를 가정
  • 할당 void* malloc(size)
    • 요청한 바이트 수를 파라미터로
    • 할당한 메모리의 시작 주소를 return
  • 반환 void free(*ptr)
    • 파라미터 해당 영역 해제
    • 해제한 영역의 크기와 같은 정보를 안줘
• 내부 단편화는 없다고 가정
  • 오직 외부 단편화 방지에 중점을 둔다.
• 재배치는 없다.
  • 단편화 해결에 유용한, 빈 공간의 압축을 사용할 수 없다.

이쯤에서 다시.. 파편화란??

Fragmentation

• external fragmentation
  • 외부에 낭비되는 공간
  • 찔끔 찔금 남는 공간들..
• internal fragmentation
  • paging때문에 page 내부에 발생하는 공간
  • 10kb 페이지에 5kb저장, 그럼 남는 5kb...?

할당 기법들

Splitting and Coalescing 분할과 병합

• 30 바이트의 힙이 있다고 가정
  • 0~9 미사용 10~19 사용 20~29 미사용
• 해당 힙의 free list
  • head -> 주소:0 길이 10 -> 주소:20 길이 10 -> NULL

이 때 10바이트보다 큰 요청은 실패해 NULL을 반환할 것이다

• 10바이트보다 작은 요청은 쉽게 충족 된다.

• 5바이트를 요청하면?

  • splitting을 수행
    • 작업을 수행할 수 있는 빈 공간을 찾아 공간을 분할
      • 그렇게 되면 free list에는 나눠진 두 공간 중 하나만 남게 됨.

• 그렇다면 공간을 free할 때는??

  • 단순 반환만 하고 해당 공간을 free list에 주면되나??

    • 안됨!!

      • 그렇게 된다면, 전체 30바이트가 free하지만 free list에는 10바이트 공간 3개가 연결되어 있어, 10 바이트보다 큰 공간에 대해 할당 못하는 문제가...

    • 그래서!! 새로 반환되는 공간이 기존에 빈 공간과 인접해 있다면, 그들을 합쳐 더 큰 공간으로 만든다

      • coalescing 병합이다.

Growing the Heap 힙의 확장

• 대부분의 할당은 작은 사이즈의 힙부터 시작해, 메모리가 부족할 경우 OS에 추가 메모리를 요청한다.

힙의 공간이 없을 때

1. sbrk 시스템콜을 사용한다.

   • 추가 힙을 할당함.

2. 새로 할당한 메모리의 시작 주소를 반환한다.

3. 요청은 성공적으로 시행 된다.

할당된 공간의 크기 파악

Header block free

• free 공간에 freelist를 작성
• Head: free list의 시작 주소
• Next field: 다음 free field의 주소

Header block used

• 할당된 영역의 사이즈를 저장
• hptr: 해제할 헤더의 시작 위치
• ptr: 할당된 블록(malloc의 리턴 값)
  • 해제 속도를 높이기 위해
• magic field: 유효성 확인을 위한 값

청크 = 헤더 + 데이터 영역

free할 때 일어나는 일

1. hptr 포인터를 얻는다
   • 해당 메모리 포인터에서 헤더의 크기를 뺀다.
2. 해당 영역의 매직 넘버의 안전성 검사(sanity check)를 한다.
3. 해제된 영역의 크기를 계산
   • 헤더의 크기를 영역 크기에 더한다.

빈 영역의 크기는 헤더 크기 + 할당된 영역의 크기

• 사용자가 N바이트의 메모리 청크를 요청하면, 라이브러리는 N 바이트 + 헤더 크기인 청크를 찾는다.

embedding a free lisg 빈 공간 리스트 내장

 메모리 청크가 요청되면, 라이브러리는 요청을 수용할만큼의 큰 청크를 찾는다

라이브러리는

• 큰 free 청크를 두개로 split한다.
  • 하나는 요청에 사용, 하나는 남겨둠
• free list를 줄인다.

4kb(2^10*4=4096) 청크가 있다고 가정, 32비트 구조 힙에 100 바이트를 malloc으로 요청 , 헤더는 8바이트 크기

• ptr = malloc(100)
  • 실제 청크 사이즈는 100+헤더의 사이즈
• 4kb 청크 size : 4088
  • 헤더 8 바이트 뺀거임!!

1. 4kb 청크를 요청한 크기 + 헤더 사이즈 청크와 나머지 청크로 splitting
   • size 100인 청크1, size: 3980 청크 2
     • 4088-100 = 3088, 여기에 헤더를 빼야지..

피피티 상황 2일때.

• 현재 힙에 100짜리 3개 공간이 할당됨
  • 그럼 1003 + 3 8 해서 총 324가 사용 중
  • 남는 여유공간은 4096(총 4KB힙) - 324(사용중) -8(헤더) = 3764
• 가상주소 16kb = 이 힙의 시작 주소 = 16384

이때 free를 통해 가운데 공간을 반환하면??

• 시작 주소(16384)+ 이전 메모리 청크 크기(108) + 해제되는 헤더 크기(8) = 16500(sptr)

  • free(16500)

  라이브러리는 빈 공간의 크기를 파악하고, 이 공간을 free list에 삽입

=> 사용, 빈, 사용, 빈

• 단편화가 일어남!!

나머지 공간도 free

• 외부 단편화가 일어난다.
• 병합(coalescing)이 필요하다!
• 마지막에 free됨 -> freelist의 첫번째 노드

리스트를 순회하며 인접한 청크를 병합!!

• 외부 단편화가 일어나지 않는다. 힙은 전체의 하나의 큰 청크가 된다.

free 공간 관리, 기본 전략

• 속도가 빠르고 단편화를 최소로해야 좋다

Best Fit 최적 적합

1. 빈 공간 리스트를 검색, 요청한 크기와 같거나, 더 큰 빈 메모리 청크를 찾음
2. 적합한 리스트 중 젤 작은 청크를 반환

• 공간의 낭비를 줄인다
  • 하지만 리스트를 전체 탐색해야하기 때문에 성능 저하가 심하다.

Worst Fit 최악 적합

1. 가장 큰 빈 청크를 찾아, 요청된 크기만큼 할당
2. 남는 청크는 free list에 유지

• 최적 적합에서 발생할 수 있는 작은 청크를 방지
  • 최적 적합과 같이 리스트를 전체 탐색해야하기 때문에 오버헤드 존재

First Fit 최초 적합

1. 요청보다 큰 첫번째 청크를 준다.
2. 남는 청크는 유지한다.

• 속도가 빠르다
• free list 초반에 크기가 작은 청크가 많이 생길 수 있다.

Next Fit 다음 적합

• 전에 할당된 다음 공간부터 공간 할당을 진행한다.
• 요청보다 큰 첫번째 청크를 준다
• free list 초반에 세그멘트가 집중적으로 발생하는 것을 방지

다른 접근 법

segregated list 개별 리스트

• 자주 요청하는 크기를 관리하기 위한 별도의 리스트를 유지
• 특정 크기 요청을 위한 메모리 청크를 유지해 단편화 가능성을 줄인다.

문제 발생

• 특수 요청을 위한 메모리 풀은 얼마나 할당해야함?
  => slab allocator가 이를 해결

Slab Allocation

• 개체에 캐시를 할당한다.
  • 개체는 자주 사용되는
• 기존에 할당된 캐시 공간이 부족하면 상위 메모리에 추가 메모리를 요청한다.

Buddy Allocation 버디 할당

• 할당기는 요청에 적합할 때 까지, free 공간을 2개로 분할한다,
• 2의 제곱 꼴만 할당할 수 있어 내부 단편화가 발생한다.
• 바로 옆에 같은 크기의 공간이 있어 쉽게 합병할 수 있다.

요약

• 할당의 목표
  • 속도
  • 공간 효율
  • 확장 가능성