빈 공간 관리

• 메모리 관리 시스템 : 프로세스 힙(공간)의 페이지를 관리하는 malloc 라이브러리일 수도 있고 혹은 프로세스의 주소 공간의 일부분을 관리하는 운영체제 자체일 수도 있다.
• 빈 공간 관리:

  • 쉬운 경우: 관리하고 있는 공간이 고정 크기의 단위로 나뉘어져 있는 경우, 관리하고 있는 공간이 고정 크기 단위의 리스트를 유지하면 된다. 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 된다.

  • 어려운 경우: 가변- 크기 빈 공간들의 집합으로 구성되어 있는 경우, 사용자-수준 메모리 할당 라이브러리에서(ex. malloc ,free), 세그멘터이션으로 물리 메모리를 관리하는 운영체제에서 발생한다. 어느 경우에도 외부 단편화가 존재. 빈 공간은 다양한 크기의 작은 조각으로 분할되어 결국 단편화 된다. 이때 빈 공간들의 전체 크기가 요청된 것보다 크더라도 하나의연속된 영역이 존재하지 않으면 요청은 실패할 수 있다.

    https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcTqvnf2ulg8jIp--tQvHL0o000Y55S9OIQqaRShe8Pa_AR2-gyrdGD3lXb4_z2rhM1dLw&usqp=CAU

    💡 위의 경우 빈 공간의 전체 크기는 20바이트, but 10바이트 2개로 쪼개져 있다. 20바이트의 빈 공간이 있지만 15바이트의 요청은 실패한다. 이를 어떻게 관리 할 것인가 (빈 공간을 관리하는데 일반적으로 링크드 리스트 사용됨)
• 저수준 기법들

  • 분할과 병합

  • 위의 예시를 빈 공간 링크드 리스트로 나타냄

    https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcQGatK65O4smqoRR4T9HzLI19RT9xlLZn0Izw&usqp=CAU

    (위의 그림은 1바이트를 요청 받아 원래 주소 20에 1바이트 반환하고 21에 길이 10에서 9로 줄어들었다)

  • 10바이트를 초과하는 요청 → return NULL

  • 10바이트 → 두 청크중 하나를 사용하여 충족

  • 10바이트 미만 →분할 실시

    • 요청을 만족 시킬 공간에 찾아가서 둘로 분할한다. 첫번째 청크는 사용자에게 다른 청크는 리스트에 남게 된다.

      

  • 10바이트 3개로 이루어진 청크 리스트에 20을 요청 받으면 실패한다

  • 이 문제는 청크가 반환 될때 빈 공간들을 병합함으로써 해결이 가능하다.

    • 메모리 청크를 반환 할때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 검사 하는 것이다.새로 해제된 빈 공간이 기존에 존재하는 빈 청크와 바로 인접해 있다면 그들을 하나의 더 큰 공간으로 병합
• 할당된 공간의 크기 파악
  • free()는 크기를 매개변수로 받지 않는다→ malloc 라이브러리에는 해제되는 메모리 영역의 크기를 신속히 파악하여 그 공간을 빈 공간 리스트에 추가시킬 수 있다고 가정한다.
  • 데이터의 헤더블럭에 size를 저장해 놓는다.
• 빈 공간 리스트 내장
  • 새로운 노드를 구현할때 malloc()을 썼지만 메모리 할당에서는 사용 불가능! → 빈 공간 내에 리스트를 구축해야함
  • 교재 p184~p186
• 힙 공간이 부족할 경우
  • 대부분의 전통적인 할당기는 적은 크기의 힙으로 시작, 모두 소진시 운영체제로부터 더 많은 메모리를 요청한다. 할당기는 힙을 확장하기 위하여 특정 시스템 콜을 호출한다(sbrk)
  • sbrk 요청을 수행하기 위해 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환한다.
  • 기본 정책들
    • First Fit: 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 남은 빈 공간은 후속 요청을 위해 계속 유지된다, 속도가 빠르고 원하는 블럭을 찾기 위해 빈공간 리스트 전체를 탐색할 필요 X, but 리스트의 시작에 크기가 작은 객체가 많이 생길수 있다.
      → 외부 단편화, 메모리 이용 효율이 감소( 큰 블록이 필요할 경우), 순차적인 할당으로 인한 성능 하락(리스트를 처음 부터 끝까지 검색하니까)
      즉, 빈 공간 리스트의 순서를 관리하는 방법이 쟁점→ 주소 기반 정렬을 사용하게 됨
    • Next FIt: 항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지(마지막으로 할당된 프로세스 위치)한다. 아이디어는 빈 공간 탐색을 리스트 전체에 더 균등하게 분산시키는 것이다. 리스트의 첫 부분에만 단편이 집중적으로 발생하는 것을 방지한다. 이러한 접근 방식은 전체 탐색을 하지 않기 때문에 최초 적합의 성능과 비슷하다.
    • Best Fit:먼저 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다, 그후 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다.

      • →항상 전체를 검색해야한다