[시스템 프로그래밍] 가상메모리[3] - 명시적 리스트 (Explicit List)

 

 

 

 

🧐 명시적 리스트(Explicit List)

묵시적 리스트 방식을 사용하는 것은 간단하지만, 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 느리다는 단점이 있었습니다.

이 단점을 해결하기 위해서 명시적 리스트를 사용할 수 있습니다.

 

명시적 리스트 방식은 가용 블록들을 이전 가용 블럭과 다음 가용 블럭을 가리키는 포인터를 가진 일종의 이중 연결 링크드 리스트 자료구조로 구성하는 방법입니다.

가용 블럭은 프로그램에서 사용되지 않기 때문에, 해당 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장될 수 있습니다.

왼쪽은 할당된 블록, 오른쪽은 가용 블록의 구조

위 그림에서처럼 각 가용 블록 내에 pred(predeccesor)와 succ(successor) 포인터를 포함하는 이중 연결 가용 리스트로 구성될 수 있습니다.

할당된 블록의 구조는 묵시적 리스트 방식과 동일하며, 단지 가용 블록의 구조만 바뀌는 것에 유의하여야 합니다.

 

 

묵시적 가용 리스트 대신에 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있습니다.

 

그러나 블록의 반환(free) 시에는 가용 리스트 내에서 블록을 정렬하는 방식에 따라, 블록의 수에 비례하거나 상수 시간을 가질 수 있습니다.

 

이에 대해 살펴보기 전에 명시적 리스트의 구조를 간단히 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 명시적 리스트의 구조

명시적 리스트는 논리적으로는 다음과 같이 이어진 형태로 되어 있습니다.

 

 

 

 

그러나 이들의 실제 연결 형태는 메모리 블록의 순서와는 무관하며, 다음과 같습니다

 

 

 

 

 

 

 

 

 

 

🧐 명시적 가용 리스트에서의 블록 반환(free) 방법

 

👉 LIFO(Last-In-First-Out) 정책

새로 반환한 블록들을 명시적 가용 리스트의 시작 부분에 삽입하는 방식을 통해 후입선출(LIFO) 순서로 유지하는 방법입니다.

LIFO 순서와 first-fit 배치 정책을 사용하면, 할당기는 대부분 최근에 사용된 블록들을 먼저 조사하게 됩니다.

이 경우 블록의 반환은 상수 시간에 수행되며, 경계 태그를 사용하는 경우 coalescing도 상수 시간에 수행될 수 있습니다.

 

그러나 이는 파편화가 아래에서 나올 주소 정렬 정책보다 나빠진다고 합니다.

 

 

free 예시는 다음과 같습니다.

 

case 1 : 반환하는 블록을 리스트 맨 앞에 추가

빈 붉은 동그라미는 이전 블록이 없음을 의미합니다.

 

 

case 2 : 이전 블록과 연결한 후 새 블록을 Root 노드로 만든다.

case 2

 

 

case 3 : 다음 블록과 연결한 후 새 블록을 Root 노드로 만든다.

case 3

 

 

 

case 4 : 앞, 뒤 블록과 모두 연결한 후 새 블록을 Root 노드로 만든다.

 

 

 

 

 

 

👉 주소 정렬 정책

명시적 가용 리스트를 주소 순으로 관리하는 것으로, 리스트 내의 각 블록의 주소가 다음 블록의 주소보다 작도록 유지합니다.

 

이 경우 블록의 반환은 적당한 선행블록을 찾는데 선형 검색 시간($O(n)$)을 필요로 합니다.

그러나 이를 first-fit 정책과 함께 사용한다면 best-fit과 비슷한 수준으로 파편화를 예방할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

🧐 명시적 가용 리스트의 장단점

장점으로는 할당시간이 전체 블록의 수가 아니라 가용 블록의 수에 비례한다는 장점이 있습니다.

(묵시적 리스트의 경우에는 전체 블록의 수에 비례하였습니다.)

 

그러나 이중 연결을 하기 위해 가용 블록에 대해여 추가적인 공간이 필요하다는 단점이 존재합니다.

따라서 최소 블록의 크기가 커지고, 잠재적으로 내부 단편화 가능성이 증가합니다.

 

또한 할당과 반환과정이 묵시적 리스트에 비해 더 복잡합니다.

특히 반환 정책으로 주소정렬 방식을 사용하는 경우 선형 시간($O(n)$)이 소요됩니다.