bong-u/til

🏠 home 🐈 repository

221208 SYSP

🏷️ cs 🏷️ c

수정일 : 2024-11-15

12-memory-1

메모리에 관한 불편한 진실

  • 메모리는 무한의 자원이 아니다

동적 메모리 할당

  • 직접(explicit) vs 간접(implicit) 메모리 할당기
    • 직접 할당 : 응용프로그램이 할당하고, 반환한다
      • ex) malloc, free
    • 간접 할당 : 응용프로그램이 할당하지만, 반환하지는 않는다
      • ex) java의 garbage collector

프로세스의 메모리 이미지

  • 스택은 아래로, 힙은 위로 성장한다
  • sbrk 함수가 추가적인 힙 메모리를 운영체제로부터 요청한다 (brk 포인터 이동)

Malloc package

 1#include <stdlib.h>
 2void *malloc(size_t size)
 3// 성공시 : 최소 size 바이트의 메모리 블록의 포인터를 반환 (대게 8바이트 단위로 맞추어)
 4// 실패시 : NULL리턴, set errno
 5
 6void free(void *p)
 7// 가용 메모리 풀을 가리키는 블록 포인터 p 리턴
 8
 9void *realloc(void *p, size_t size)
10// 블록 p의 크기를 변경하고, 새 블록의 포인터를 리턴
11// 새 블록의 내용은 이전 블록과 새 블록 크기 중 적은 크기까지는 변화 없음

우수한 malloc/free 프로그램의 목표

  1. 주요 목표
    • malloc과 free에서 우수한 시간 성능을 얻는다
    • 우수한 공간 이용율을 가져야 한다
  2. 다른 목표
    • 우수한 지역성 : 시간적으로 인접 (또는 유사한 객체) -> 공간상으로 인접
    • 견고성 : free(p1) 함수가 유효한 포인터 p1에 대해 수행하는지 체크할 수 있다.

성능 지표 1 : 처리량 (Throughput)

  • 단위 시간 동안 완료한 요청의 수

성능 지표 2 : 최대 메모리 이용율 (Utilization)

  • k개의 요청 후에, 최대 메모리 이용율 $$ U*{k} = (max*{i<=k}: P*{i}) / H*{k} $$

내부 메모리 단편화 (Internal Fragmentation)

  • 일부 블록에서 블록 크기와 데이터 크기간의 차이로 인해 발생
  • 이전 요청 패턴에 의해서만 영향을 받으므로 측정이 용이

외부 메모리 단편화 (External Fragmentation)

  • 힙 전체 메모리를 합치면 수용이 가능하지만 가용 블록의 크기가 작은 경우에 발생
  • 외부 단편화는 미래의 요청 패턴에 의해 결정되므로 측정이 어렵다

Free 블럭 관리하기

  1. 간접리스트 : 크기 정보를 이용하여 모든 블록을 연결
  2. 직접리스트 : 가용 블록내에 포인터를 이용
  3. 구분 가용리스트 : 크기 클래스마다 별도의 가용 리스트를 유지
  4. 크기로 정렬된 블록

방법 1 : 간접 리스트 방식 (Implicit List)

  • 1 word = size(a) + payload + padding

  • 연습문제

    제한사항 : 헤더는 4바이트, double-word alignment, 블록의 크기는 8의 배수

    요청 block size block header(hex)
    Malloc(1) 4+1+3 = 8 size | alloc = 0x8 | 1 = 0x9
    Malloc(5) 4+5+7 = 16 size | alloc = 0x8 | 5 = 0xD
    Malloc(12) 4+12+0 = 16 size | alloc = 0x8 | 12 = 0x1A
    Malloc(13) 4+13+7 = 24 size | alloc = 0x8 | 13 = 0x1B

간접 리스트 : Free 블록 찾기

  1. First fit
  2. Next fit
  3. Best fit

간접 리스트 : 결합 (Coalescing)

  • free할때 해당 블록의 할당 플래그만 0으로 세팅 -> 잘못된 단편화 발생
  • free하는 블록의 이전과 다음 블록을 함께 연결해서 더 큰 free블록을 만든다

간접 리스트 : 양방향 연결

  • 경계 태그 (Boundary tags)
  • header를 복제해서 블록의 마지막에 넣는다 (-> footer)

13-memory-2

직접 리스트

  • 가용 블록들의 리스트만을 관리하면, 모든 블록을 관리하지 않는다
  • 연결 링크는 메모리 블럭의 순서와 무관하다

직접 리스트 : Free

  • 새롭게 반환한 블록은 가용리스트의 어느 위치에 끼워 넣어야 하는가?
  1. LIFO (last in first out) 정책 : 반환블록을 리스트 맨 앞에 끼워넣는 방법 -> 빠른 시간, 나쁜 단편화 성능
  2. 주소정렬 정책 : 블록들의 주소가 순서를 유지하도록 삽입 -> 느린 시간, 우수한 단편화 성능

직접리스트 <-> 간접리스트

  • 할당시간이 전체 블록의 수가 아니라 가용블록 수에 비례한다
  • 할당과 반환 과정이 복잡하다.
  • 링크 포인터 저장을 위해 추가적인 공간이 필요하다 (블록마다 2워드 추가 필요)

구분 가용 리스트 (segrated free list)

  • 각 크기 클래스들은 클래스마다의 블록들을 관리한다

  • 크기 n의 블록 할당 방법

    • 크기 n의 블록 리스트가 비어있지 않은 경우

      1. 리스트의 첫 블록을 할당한다.

    • 가용리스트가 비어 있는 경우

      1. 새 페이지를 할당받는다 (OS로부터 sbrk()를 사용하여)
      2. 이 페이지의 모든 블록들로부터 새로운 가용리스트를 생성한다
      3. 리스트의 첫 블록을 할당한다

    • 블록 반환 방법

      • 가용 리스트에 추가
      • 블록 연결 후 해당 클래스 가용리스트에 추가

  • 장점

    • 높은 처리량
    • 우수한 메모리 이용률