책너두 (컴퓨터 밑바닥의 비밀) 15일차 힙 영역 1

• 힙 영역이 필요한 이유
• 특정 데이터를 여러 함수에 걸쳐 사용해야 한다면?
  • 전역 변수는 모든 모듈에 노출되어 있는데, 모든 모듈에 노출하고 싶지 않을 때가 있음.
  • 이때, 프로그래머가 직접 관리하는 특정 메모리 영역에 저장해야 함.
• 메모리 수명 주기에 프로그래머가 완전히 직접 제어할 수 있는 매우 큰 메모리 영역이 필요함.
  • 이를 바로 힙 영역이라고 함.
• malloc 메모리 할당자 직접 구현하기
• c/c++ 언어에서 메모리의 도적 할당과 해제 요청은 모두 전문적으로 힙 영역에 메모리를 할당하고 해제하는 작은 프로그램에 전달되어야 함.
  • 이 프로그램은 malloc 메모리 할당자임.
• 메모리 할당자 입장에서 적절한 크기의 메모리 영역을 제공하기만 하면 됨.
  • 할당자는 그 메모리 영역에 무엇을 저장할지까지는 신경 쓰지 않음.
• 힙 영역은 사실 매우 간단한 구조로 되어 있음.
  • 커다란 배열 형태임.
• 힙 영역 위에서 두 가지 문제를 해결해 나간다.
  • malloc 함수 구현
    • 힙 영역에서 사용 가능한 메모리 영역을 찾음.
  • free 함수 구현
    • 메모리 영역의 사용이 완료되었을 때 메모리 영역을 반환하는 방법
• 여유 메모리 조각 관리
• 어떤 영역이 사용 가능한 메모리고 어떤 영역이 이미 할당된 메모리인지 구분하는 방법이 필요함.
  • 연결 리스트는 비교적 간단히 구현할 수 있는 방법임.
    • 모든 메모리 조각을 연결 리스트로 관리 할 수 있음.
    • 그러나 연결 리스트를 생성하려면 메모리 할당을 피할 수 없음.
    • 우리는 할당자를 만들어야 하는데, 아직 존재하지 않는 메모리 할당자에 메모리를 요청하는 것은 자가 당착에 빠지는 것임.
  • 따라서 연결 리스트와 메모리 사용 정보를 메모리 조각 그 자체에 함께 저장해야 함.
    • 메모리 조각은 할당, 또는 해제된 전체 메모리 조각을 의미함.
    • 다음 노드가 어디있는지 알려주는 포인터는 없지만, 메모리 사용 정보로 다음 노드 위치를 유추하는 것이 가능함.
  • 다음 두 가지 정보만 기록하면 됨.
    • 해당 메모리 조각이 비어 있는지 알려 주는 설정값
    • 해당 메모리 조각의 크기를 기록한 숫자
• 메모리 할당 상태 추적
• 모든 메모리 조각을 추적하기 위해 머리 정보를 사용하면 됨.
• 마지막 비트를 이용하여 메모리 조각이 여유 상태인지 할당되었는지 확인 가능함.