[자료구조]자료구조 Binomial Heap 설계 / 실습 레포트

소개글

본 프로그램은 동적 메모리 할당과 해제를 담당하는 메모리 관리 시스템을 구현한다.
파일에서 메모리의 할당 및 해제에 관한 정보를 읽어들여 할당된 메모리는 Linked List 구조를 이용하고, 비할당된 메모리는 Linked List와 Binomial Heap의 이중구조를 이용하여 관리하도록 하였다. 메모리가 할당되기 위해서는 비할당된 메모리 중 가장 큰 메모리를 먼저 찾아서 그 메모리에 할당이 될 수 있는지 여부를 판단한다.
만약 최대 비할당 메모리에 삽입될 수 없는 크기라면 남아있는 비할당 메모리의 총 크기를 살펴보고, 만약 삽입될 수 있을 크기가 남아있다면 남아있는 비할당 메모리들을 Coalescing하게 된다. 그 후 다시 삽입을 시도하게 되며 Coalescing 했음에도 최대 비할당 메모리의 크기가 삽입될 메모리보다 작으면 할당이 실패한다.
메모리 삽입이 성공하게 되면 할당된 메모리는 각각의 index를 가지게 되면 메모리 해제는 해당 index를 가지고 Linked List 내에서 메모리를 찾아서 해제하게 되고, 해제된 메모리는 비할당 메모리가 됨으로써 비할당 메모리 Linked List와 Binomial Heap에 삽입되게 된다.

목차

1. Instruction
1.1 overall descriptioin
1.2 requirements
1.3 sample input/output

2. Overall System Class Design
2.1 Relationships between classes
2.2 Present class ADTs

3. Data Structure Diagram

4. Algorithm Specfication
4.1 Pseudocodes
4.2 Performance Evaluation

5. Discussion and Conclusion

본문내용

본 프로그램을 구현하기 위해서는 Linked List와 Binomial Heap 구조에 대한 이해가 필요하다. 다음은 프로그램을 구현하기 위하여 사용되는 구조에 대한 설명이다.
할당된 메모리 및 비할당된 메모리를 주소순으로 연결하기 위해선 linked list 구조를 사용하여야 하는데, 연결구조는 아래 그림과 같다.


메모리를 주소 순으로 연결함으로써 출력 제한사항에 맞게 구성하고, 또한 메모리 해제시 리스트를 순회하면서 해당 index에 맞는 노드를 손쉽게 검색할 수 있으며, coalescing 시 메모리가 주소순으로 연결되어 있으므로써, 주소가 연결된 메모리 블록을 쉽게 찾아낼 수 있다.
비할당된 메모리는 linked list뿐만 아니라 binomial heap에도 연결되어 있는데, 이는 priority queue 구조인 binomial heap을 이용함으로써 비할당된 메모리 중 최대 크기의 메모리를 쉽게 찾아낼 수 있기 때문이다. 본 프로그램에서 사용하는 메모리 할당 방식은 worst-fit 방식인데 이는 비할당된 메모리 중에서 가장 큰 메모리에 새로운 메모리를 할당하는 방식으로 binomial heap구조를 사용하여 구현할 수가 있다.

5. Discussion and Conclusion

이번 과제는 동적 메모리 할당과 해제를 담당하는 메모리 관리 시스템을 시뮬레이션 한 프로그램을 구성하기 위하여 Binomial Heap 구조를 사용하여 주어진 입력 파일에 따라서 메모리를 할당 및 해제하고 기존 메모리 블록으로 할당이 불가하면 남은 메모리를 Coalescing하여 다시 할당 시도를 하고, 그래도 할당이 되지 않으면 Fail Count를 증가하였다.

Binomial Heap의 노드들은 이중연결구조를 가지도록 구성하여서, Binomial Heap에서는 비할당 메모리의 크기 순서대로, Linked List에서는 메모리 주소 순서대로 노드를 배열하여 비할당 메모리 삽입 및 삭제시 Binomial Heap과 Linked List에서 동시에 삽입과 삭제를 수행하였다.

메모리 할당을 시도할 때 비할당 메모리 중 가장 큰 메모리보다 할당할 메모리가 크고, 남아있는 비할당 메모리의 총 size보다 작으면 Coalescing을 실시하게 되는데, 이 때 Binomial Heap의 모든 노드를 삭제 후 Linked List에서 이어진 메모리 블록을 찾아서 병합하게 된다. 하지만 가령 비할당 메모리 블록 10, 30, 40, 50이 남아있고 여기서 30과 40만이 이어진 메모리라면 실제적으로 Binomial Heap에서는 30까지의 메모리만 삭제 후 Linked List에서 병합과정을 실시하면 되는데 불필요한 메모리까지 전부 삭제함으로써 코드 상으로는 복잡함이 줄어들었지만 불필요한 실행시간이 소요되었다.

참고 자료

없음

압축파일 내 파일목록

2000120007_v1.0_설계 레포트(Assignment3).doc
2000120007_v1.0_실습 레포트(Assignment3).doc