오늘도 TILTIL이다

오늘은 메모리 할당 하기 이전에 필수인 개념들에 대해 알아볼 건데요

우선 메모리 할당이 뭔지부터 알아야겠죠?

메모리 할당이란 메모리를 할당한다는 뜻이라고 하네요!!!

이상 메모리 할당에 대해 알아보았습니다!!!

…

시작은 가용 리스트다

가용 리스트

가용 리스트란?

• 할당 가능한 블록들의 모음을 가리킨다

블록?

힙에 존재하는 블록들을 말이다

어제 덜 다룬 것 같은데 힙(heap임 엉덩이 아님)에 있는 메모리는 블록 단위로 관리 된다

1. 헤더(header): 블록 크기, 할당 여부 저장

2. 페이로드(payload): 실제 사용자에게 제공되는 공간

이런식으로 말이다

그리고 블록은 상태에 따라 두가지로 나뉜다

• 할당 블록(Allocated block)

  • 사용자가 malloc으로 요청해서 프로그램이 쓰고 있는 상태

  • 힙 관리자가 임의로 건드릴 수 없다

• 가용 블록(Free block)

  • free로 반환되었거나 아직 누구에게도 주지 않은 상태

  • 추후 malloc 요청이 들어오면 이 블록이 재사용된다

아무튼 다시 가용 리스트로 돌아오면 가용리스트도 3갈래로 쪼개진다

가용 리스트 종류

1. 암시적 가용 리스트 (Implicit Free List)

• 모든 블록 순회하며 가용 블록 찾는 법

• 블록 크기 정보가 다음 블록 주소를 암시적으로 알려준다 해서 암시적 가용리스트

2. 명시적 가용 리스트 (Explicit Free List)

• 가용 블록들만 따로 묶어 탐색하는 방식이다

• 연결 리스트 방식으로 구현 (주로 이중 연결 리스트)

3. 분리 가용 리스트 (Segregated Free Lists)

• 가용 리스트 여러개를 크기 별로 운용하는 방식

• 분리 가용 리스트의 변형

  • 단순 분리 저장

    • 각 크기 클래스의 가용 리스트에 항상 동일 크기 블록만 저장

  
  

  • 분리 적합

    • 크기 범위 안에 다양한 크기 블록 저장

    • 크기에 맞는 블록 검사하고 있으면 할당하고 남은 조각은 맞는 범위로 이동

    • 검사해도 없을 경우 다음 크기 클래스 검사

추가로 버디 시스템이라는게 있다

분리 가용 리스트의 한 에라고 한다

블록 크기를 2의 거듭제곱으로 제한하고 크기별 가용리스트 유지

요청 받은 거보다 바로 다음으로 큰 $2^k$블록 할당하고 블록 없으면 한단계 윗놈을 반 갈라 하나주고 하나 리스트에 넣는다고 한다

으음…

특수 상황에서 좋다고 한다

깨달음을 하나 얻었다

앞에서 배웠던 링크드 리스트 구조를 어디에 쓰나 했더니 이런데에 쓸 수 있다니…

세그리게이티드 뭐시기 막 이러길래 어지러웠는데

뭔지 알게 되어버렸다…

이거 너무 강해지는 거 아닌가 걱정이다…

스티브 잡스가 벌벌떨고 빌게이츠가 눈치보는!!!

아무튼, 메모리 할당과정에 대해 이해도가 높아졌다

메모리 할당 과정, 분할 전략

메모리 할당해주는 법이다

요청 받은 크기 이상의 가용 블록 찾아 할당 해줘야 하는 거 말이다

대강 이런 절차라고 한다

1. 요청 크기 조정

   • 사용자의 요청 데이터 + 메타 데이터 + 정렬 패딩으로 실제 필요한 블록 크기 계산

1. 적합한 가용 블록 탐색

   • 메모리 할당 정책이 여기서 쓰인다 어떤 블록 쓸지 찾는다

1. 블록 분할

   • 적합한 블록 찾았고 블록이 요청 크기보다 충분히 크면 남는 부분 분할할지 결정한다
     충분의 기준은 최소 블록 크기 이상이냐 이다

   • 보통 분할하고 별도의 가용 블록으로 유지한다

   • 안하면 더 편하지만 내부 단편화가 늘어난다

1. 블록 할당 마킹

   • 선택된 블록을 할당된 상태로 표시한다

   • 블록 포인터 반환해 사용자가 쓸 수 있게 해준다

1. 히프 확장 (필요시)

   • 가용 블록 못찾았을 경우 힙 공간 확장 필요하다는 거다

   • 시스템 호출로 힙 확장

   • 이후 확장된 공간 전체를 가용 블록으로 초기화\

뭐 별거 없다

다음 거 알아보자

메모리 반환과 병합 처리

메모리 해제하는 법이다

대강 알아보자

메모리 할당된 거 해제하는 거랑 병합이 무슨 상관인지 나온다

1. 해당 블록 찾기 및 상태 변경

   • 해당 블록 정보 가져와 가용 상태로 표시한다

1. 인접 블록 검사

   • 해제된 현재 블록의 바로 앞/뒤에 있는 블록들이 가용 상태인지 확인

   • 네가지 조합으로 병합 ㄱㄴ

     1. 이전 블록 할당, 다음 블록 할당: 양 옆 모두 할당된 상태라 병합 블가능

     2. 이전 블록 할당, 다음 블록 가용: 뒷 블록과 병합 가능

     3. 이전 블록 가용, 다음 블록 할당: 앞 블록과 병합 가능

     4. 이전 블록 가용, 다음 블록 가용: 앞/뒤 블록과 병합 가능
        

2. 병합

   • 걍 앞/뒤 블록이 가용 상태일때까지 합치면 된다

1. 가용 리스트 갱신

   • 가용화된 블록 혹은 병합 결과 블록을 가용 블록 관리 구조에 반영한다

   • LIFO거나 정렬 리스트거나 종류에 맞춰 삽입

여기도 뭐 별거 없다

생각보다 메모리 할당 할만할지도?

단편화와 메모리 활용 효율

단편화, 자꾸 처 나오는데 뭔지를 몰랐다

대충 낭비되는 메모리로 이해했는데

대강 비슷한 거 같다

단편화: 메모리 중 일부가 사용되지 않지만 필요한 할당 만족시키는 데에도 쓸 수 없는 현상

이로인해 메모리 효율 떨어지기에 이를 해결하는게 중요하다

단편화 종류

1. 내부 단편화

   • 할당된 블록 내부에 필요 이외의 공간을 말한다

   • 1바이트 요청했는데 16바이트 줄 경우, 15 바이트가 내부 단편화다

   • 측정하기 쉽다

   • 여러 방법들로 줄이지만 어느 정도는 허용하는 느낌이다

1. 외부 단편화

   • 사용되지 않는 메모리는 충분하지만 연속된 큰 블록이 없을 경우다

   • 측정도 어렵고 미래 메모리 요청 패턴에도 좌우됨
     (미래 메모리 요청 패턴 : 할당, 해제 등등의 방법)

   • 병합이 필요한 이유가 되기도 함

대충 외부 단편화가 더 중요한 거 같다

한개의 커다란 블록이 없는 경우에는 병합으로 만들어서 해결하고
그냥 부족할 경우 힙 메모리 크기 늘리는 것 같다

나중에 구현 할때에 외부 단편화를 좀 유의깊게 보면 될 거 같고 그외에는 뭐…

그리 어려워 보이지는 않는다 ㅇㅇ

시스템 메모리 함수

동적 메모리 할당기가 운영체제(OS) 로부터 메모리 받아 올 때 쓰는 거다

여기는… 대강 읽고만 넘어가겠다

필요할때 검색해서 쓰면 되고

기능 설명인데 그런건 인터넷 쳐서 하는게 더 정확하고 좋으니 말이다