Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-05-09
2003-01-21
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S111000, C707S793000
Reexamination Certificate
active
06510505
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to data storage systems that allocate storage space using bitmaps.
2. Description of the Related Art
Storage systems, particularly systems that store data objects contiguously, often use bitmaps to represent and manage free space. Typically, the value of each bit in a bitmap represents whether a unit of storage, e.g., a block, is free. A bit value of “1” in a free space bitmaps indicates that the block associated with the bit is free, and a value of “0” indicates that the block is not free. Of course, a used space bitmap would reverse the free
ot free values.
Larger storage systems require larger bitmaps, with some bitmaps potentially including many pages. Each page in turn includes many “words” of bits, with the word size being a power of two and generally being equal to the register width of the processor being used, e.g., 16 bits, 32 bits, 64 bits, and so on. Thus, a processor can read up to the word size number of bits in parallel. When it is time to allocate free space for a data object to be stored, the allocation processor searches the bitmap for a sequence of bits that represents free space which is sufficiently large to store the object.
Bitmaps have several advantages over other management tools such as so-called “extent lists” and the “buddy system” disclosed by Knuth in
The Art of Computer Science,
Vol. 1. For instance, bitmaps have the advantage of two-way addressing, meaning that the block address of managed space can be used to locate the corresponding bit address in the bitmap and vice-versa. This makes the “liberation” of space which is no longer required for storage relatively simple, and it also makes it relatively simple to extend an existing allocation in place. Moreover, bitmaps are self organizing, in that searching for a range of storage is localized to the respective bits in the bitmap that represent the range of storage. Extent lists and buddy systems, in contrast, can become disorganized. Still further, bitmaps are inherently parallel, with one performance advantage over extent lists being that relatively simple latches can be used to synchronize multiple processes over bitmaps, whereas extent lists require the use of more complex locks. Additionally, while the buddy system can quickly find strings of bits representing free space (“gaps”), the gaps are constrained to be aligned with power of 2 boundaries, which often results in undesirably splitting larger gaps into plural smaller gaps. This is not as robust as being able to exploit gaps of any size, and at any offset from a reference, a possibility the present invention understands is provided for by bitmaps.
However, the present invention observes that searching bitmaps for data object allocation purposes can be inefficient. For instance, a linear search of a bitmap requires a fixed number of steps to examine each bit, increasing the time it takes to find an allocation. Also, previous systems such as the GPFS/Tiger Shark file system look in only a single bitmap word for an allocation. As recognized herein, some data objects might be sufficiently large to require an allocation that cannot be represented by a single bitmap word. Moreover, by limiting an allocation to spaces represented in only a single bitmap word, an allocation that might span multiple contiguous words that together have a contiguous string of free space bits cannot be considered. The invention disclosed herein addresses one or more of the critical observations set forth above.
SUMMARY OF THE INVENTION
A general purpose computer is programmed according to the inventive steps herein to manage storage space in a storage system. The invention can also be embodied as an article of manufacture—a machine component—that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to execute the present logic. This invention is realized in a critical machine component that causes a digital processing apparatus to perform the inventive method steps herein.
The invention can be implemented by a computer system including a data storage system having a bitmap of bits representing free and used space on a data storage medium, and a processor associated with a data storage system. The processor has logic for receiving a size of an object to be stored, with the size establishing a target number “k” of bits in the bitmap. The processor also has logic for, in a first word of bits in the bitmap, determining a suffix sequence of bits when all bit values in the suffix sequence are a predetermined value. In a second word of bits in the bitmap, the processor logic determines a prefix sequence of bits when all bit values in the prefix sequence are the predetermined value. The logic of the processor returns an allocation for the object when the length of the prefix and suffix together equals at least the target number “k” of bits.
In another aspect, a computer program device includes a computer program storage device that is readable by a processor. A program is on the program storage device and includes instructions which can be executed by the processor for using a bitmap to allocate space in a data storage system. The program includes computer readable code means for identifying a contiguous number of bits in the bitmap when each bit in the contiguous number has a predetermined value and when the number of bits in the contiguous number is at least as great as a target number “k” of bits. The contiguous number of bits span more than a single word in the bitmap.
In still another aspect, a computer-implemented method for identifying a target number “k” of storage blocks using a bitmap including words of “w” bits each includes identifying, in a first word or words, a suffix having “s” contiguous bits. Each bit has a predetermined value, e.g., “high”. The method also includes identifying, in a second word or words contiguous to or near the first word or words, a prefix having “p” contiguous bits. Each bit in the prefix has the predetermined value, and “p” and “s” together equal at least “k”.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts, and in which:
REFERENCES:
patent: 5715455 (1998-02-01), Macon et al.
patent: 6175900 (2001-01-01), Forin et al.
patent: 6185663 (2001-02-01), Burke
Wilson et al. “Dynamic Storage Allocation : A Survey and Critical Review” Proc 1995 Int'*
McKusick et al. “A Fast File System for UNIX” ACM Trans. on Computer Systems, vol. 2, No. 3, Aug. 1984, p. 181-197.*
Navarro et al. “Fast and Flexible String Matching by Combining Bit-parallelism and Suffix Automata”, Proc. of the 9th Annual Symposium on Combinatorial Pattern Matching, 1998.*
Tanenbaum et al. “Operating Systems: Design and Implementation”, 1997 Prentice Hall, Second Edition p. 805-821 esp. routines alloc_zone and alloc_bit.
Burns Randal Chilton
Hineman Wayne Curtis
Baker Paul
International Business Machines - Corporation
Rogitz John L.
Yoo Do Hyun
LandOfFree
System and method for allocating storage space using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for allocating storage space using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for allocating storage space using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3025334