A Bit-Parallel Search Algorithm for Allocating Free Space
Posted 2009. 6. 26. 17:55
abpsafs.pdf
그러나, cluster bitmap을 탐색하고 수정하는 것은 많은 비용을 발생시킨다. 이 논문은 이 비용 중에서도 연속된 free cluster bitmap을 효과적으로 탐색하는 알고리즘을 소개하고 있다.
gap-search라는 방법이 그것인데, 논문에서는 이 알고리즘과 일반적인 순차탐색을 비교하면서 gap-search 알고리즘의 우수성을 증명하고 있다.
하지만, 비교의 대상이 왜 순차탐색이냐 하는데는 의문을 갖는다. 분명 gap-search방법이 순차 탐색보다는 월등한 성능을 가져 오는 것은 사실이나, 순차탐색 보다 더 안좋은 탐색 방법이 없다는 것도 사실이기 때문이다.
free cluster를 찾는 방법은 list를 활용하는 방법도 있고, tree를 이용하는 방법도 있다. 이렇게 bitmap을 다른 자료구조로 추상화한뒤 검색하는 방법과 비교를 했더라면 하는 아쉬움이 든다.
탐색 시간을 고려 해봤을 때는 tree나 list를 이용하는 방법이 bitmap을 사용한 방법보다 우월할 것이 자명하나, 메모리 사용량이나 bitmap을 추상화하는 비용도 만만치 않기 때문에 bitmap을 그대로 사용하는 gap-search 알고리즘이 더 효과적일 수 있기 때문이다.
아쉬움도 있었지만, gap-search 알고리즘은 정말 단순하면서도 놀라울 정도로 성능이 좋다. 정말 좋은 논문이다.
'paper & book' 카테고리의 다른 글
| A Bit-Parallel Search Algorithm for Allocating Free Space (0) | 2009.06.26 |
|---|---|
| C 언어 펀더멘털 (0) | 2009.06.08 |
| 2006 IEEE ToCE New Techniques for Real-Time FAT File System in Mobile Multimedia Devices (0) | 2009.05.17 |
| Flash-Aware Buffer Management Policy for Portable Media Players (0) | 2009.05.17 |
- Filed under : paper & book
- Tag : bit-parallel, Bitmap, cluster, exFAT, FAT, gap-search
- 0 Comments 1 Trackbacks