. 9.9.11 경계 태그로 연결하기
본문 바로가기
프로그래밍 공부/CSPP

9.9.11 경계 태그로 연결하기

by 불냥이_ 2021. 1. 16.

할당기는 어떻게 연결을 구현하는가?

 

 우리가 한 블록을 반환했다고 하자. 반환한 그 자리에 헤더가 있기 때문에 다음 가용 블록을 찾는 것은 쉽다. 그러나 바로 앞에 가용 블록이 있는지 없는지는 어떻게 알 것인가?

 현재 상태에서는 다시 처음부터 검색을 해서 반환자리까지 올 수 밖에 없다. 그러나 딱 봐도 엄청 비효율적이지 않은가?

 

 그래서 풋터footer(foot + pointer) 라는 경계 태그를 블록의 끝에 넣어준다. 데이터의 내용은 헤더와 동일하다.

그런데 그렇다면 풋터도 4바이트의 용량을 차지하게 되고, 헤더와 풋터를 합치면 8바이트가 된다.

 

 그런데 우리가 4바이트의 정수만을 할당받는다고 가정해보자. 그렇다면 블록의 구성은 헤더(4바이트)+데이터(4바이트)+풋터(4바이트) 의 12바이트의 블록을 할당받게 된다. 즉, 4바이트의 공간을 위해서 8바이트의 추가정보가 필요하게 되니 배보다 배꼽이 더 큰 상황이다.

 

 

 그런데 조건을 잘 생각해보자. 풋터는 어떤 경우 필요한 것인지 생각해보면, 그 블록의 헤더로 돌아가기 위해서다.

그렇다면 어떤 경우에 블록의 헤더로 돌아가게 되는가? 그건 그 블록이 가용일 경우에만 해당되고, 비가용일 경우에는 헤더로 돌아갈 필요가 없다.

 

 즉, 할당했을 경우에는 블록의 끝에 풋터를 달아놓을 이유가 없다. 록을 반환했을 때, 이제 비어진 블록 끝에 풋터를 달아놔서, 다음 블록이 가용으로 바뀌었을 때, 이 블록과 병합하도록 하는 것이다. (풋터의 존재 의의가 한 블록을 반환했을 때, 그 다음 가용 블록은 찾기 쉽지만, 앞에 있는 가용블록은 찾기 어려워서 달아놓은 것임을 상기하자)

 

 

댓글