🔍 명시적 가용 리스트란?
- 가용 블록끼리 포인터로 연결해 다음 블록 위치를 명시적으로 알 수 있다.이러한 연결은 할당된 블록들 간의 연결이며, 메모리 풀에서 다시 사용 가능한 가용한 블록들의 집합을 형성한다. 명시적 가용 리스트에서는 각 가용 블록에는 헤더와 푸터가 있을 수 있지만, 데이터를 저장하기 위한 payload는 필요로 하지 않는다. 대신, 가용 블록 내에서 다음 가용 블록과 이전 가용 블록의 주소를 포인터로 저장하여 연결한다.
할당 블록 vs 가용 블록
할당 블록 (Allocated Block):
- 할당 블록은 프로그램이 메모리를 요청하고 할당된 상태를 나타낸다.
- 이 블록은 프로그램이 실제로 사용 중인 데이터를 저장하는 용도로 사용된다.
- 할당된 블록은 사용자의 요청에 따라 할당되고, 더 이상 필요하지 않을 때 해제된다.
가용 블록 (Free Block):
- 가용 블록은 이미 할당되었다가 해제된 상태를 나타낸다.
- 이 블록은 메모리 풀에 다시 재활용될 수 있는 상태이다.
- 가용한 블록들은 새로운 할당 요청이 들어왔을 때, 다시 할당되어 사용될 수 있다.
가용 블록은 헤더와 푸터 말고는 데이터를 필요로 하지 않으므로, 가용 블록 안의 payload 자리에 다음 가용 블록과 이전 가용 블록의 주소를 저장한다.
특징
논리적 vs 물리적
- 💡 하나의 이중 연결 리스트를 만들어서 가용 블록을 연결한다.
- 실제 논리적으로는 연속적이나, 물리적으로는 연결이 엉켜있다.
할당
- 해당 가용 리스트를 분할한 다음 새 가용 블록을 기존 가용 블록과 링크되었던 이전(prev), 다음(next) 블록과 연결
연결
1. 앞, 뒤 블록 모두 가용하지 않은 경우
- 현재 가용 블록의 앞뒤로 모두 할당된 블록이 있는 경우
- 이 경우, 현재 가용 블록은 가용 리스트에서 분리되어야한다. 따라서 가용 리스트에서 제거된다.
- 뒤 블록만 가용한 경우
- 현재 가용 블록의 뒤에만 가용 블록이 있는 경우
- 이 경우, 현재 가용 블록은 다음 가용 블록과 이전 가용 블록을 연결하고, 이전 가용 블록의 다음 포인터를 수정하여 연결
- 앞 블록만 가용한 경우
- 현재 가용 블록의 앞에만 가용 블록이 있는 경우
- 이 경우, 현재 가용 블록은 이전 가용 블록과 다음 가용 블록을 연결하고, 다음 가용 블록의 이전 포인터를 수정하여 연결
- 앞, 뒤 블록 모두 가용한 경우
- 현재 가용 블록의 앞뒤로 모두 가용 블록이 있는 경우
- 이 경우, 현재 가용 블록은 이전 가용 블록과 다음 가용 블록을 가리키는 포인터를 수정하여 두 가용 블록을 연결
- 따라서 세 개의 가용 블록이 하나로 합쳐진다.
가용 리스트 관리방법 2가지
- 할당된 블록을 free 하게 되면, 그 free block을 어디에 넣을 것인가?
1️⃣ LIFO (Last In First Out)
2️⃣ Address Ordered - 명시적 가용 리스트 vs 묵시적 가용 리스트 차이
명시적 가용 리스트: 가용 블록만 연결 및 검색
묵시적 가용 리스트: 힙 전체를 연결 및 검색
Sunny Day!