Memory management system and method using dual indexing structures

Claim 1

A memory management system for a memory, the memory manager system and memory comprising: a storage device organized into at least one file comprising frames of stored data for swapping into the memory; the memory comprising numbered pages for storing swapped frames of the stored data from the storage device, a page list heads list comprising list head entries, each said list head entry identifying the numbered page containing free memory blocks of storage space, at least one of said list head entries storing a page number identifying one of the numbered pages that contains one of the free memory blocks, and a blocks list for each frame comprising at least one blocksize entry, each such blocksize entry containing a count of frames in the storage device that contain available storage space of a given size; and a processor comprising means using the page number stored in the at least one list head entry for allocating the memory blocks responsive to a memory request, and means using the blocks list for allocating available storage space responsive to the memory request.

Claim 4

A method for allocating requested memory blocks in a system comprising a storage device organized into at least one file comprising data frames of stored data for swapping into a memory, the memory comprising numbered pages for storing swapped frames of the stored data from the storage device, a page list heads list comprising at least one list head entry, each said entry identifying one of said numbered pages that has free memory blocks of a predetermined block size, each entry storing a page number corresponding to one of the numbered pages in the memory containing a data frame from the storage device having a free memory block of the predetermined block size, and a blocks list for each data frame comprising at least one blocksize entry, each such blocksize entry containing a count of data frames in the storage device that contain available storage space of a given block size, the method comprising the steps of: allocating the requested memory blocks from the memory using the page number stored in the at least one list entry in response to a memory request; and when said previous allocating step is not successful, allocating the requested memory blocks from the available storage space in the storage device using the blocks list in response to a memory request.

Claim 5

A method for allocating requested memory blocks in a system comprising a storage device organized into at least one file comprising data frames of stored data for swapping into a memory, the memory comprising numbered pages for storing swapped frames of the stored data from the storage device, a page list heads list comprising at least one list head entry, each said entry identifying one of said numbered pages that has free memory blocks of a predetermined block size, each entry storing a page number corresponding to one of the numbered pages in the memory containing a data frame from the storage device having a free memory block of the predetermined block size, and a blocks list for each data frame comprising at least one blocksize entry, each such blocksize entry containing a count of data frames in the storage device that contain available storage space of a given block size, the method comprising the steps of: allocating the requested memory blocks from the memory using the page number stored in the at least one list entry in response to a memory request; and when said previous allocating step is not successful, allocating the requested memory blocks from the available storage space in the storage device using the blocks list in response to a memory request.

Claim 7

A method using a computer for managing a memory organized into a plurality of layers, comprising: generating a memory request for a fixed amount of memory in a service layer responsive to an application program; receiving, in a memory manager layer, the memory request, the memory manager layer comprising a cache containing a plurality of pages for storing frames of data; scanning at least one page list for a page entry, the page list containing a plurality of page entries, each page entry identifying one of the plurality of pages having a free memory block; scanning a disk block list for a non-zero frame count, the disk block list containing a count of frames not contained in the cache having a free memory block of a given size; and allocating free space by locating a block of free space in a memory-resident data frame at least as large as the fixed amount of memory in constant time and returning an in-memory address for the located block to the service layer.

Claim 8

A method using a computer for managing a memory organized into a plurality of layers, comprising: generating a memory request for a fixed amount of memory in a service layer responsive to an application program; receiving, in a memory manager layer, the memory request, the memory manager layer comprising a cache containing a plurality of pages for storing frames of data; scanning at least one page list for a page entry, the page list containing a plurality of page entries, each page entry identifying one of the plurality of pages having a free memory block; scanning a disk block list for a non-zero frame count, the disk block list containing a count of frames not contained in the cache having a free memory block of a given size; and allocating free space by locating a block of free space in a memory-resident data frame at least as large as the fixed amount of memory in constant time and returning an in-memory address for the located block to the service layer.

Claim 11

A method using a computer for allocating a memory block having a requested size in constant time, the computer comprising a cache comprising numbered pages for storing swapped frames of stored data and a page list heads list comprising at least one list head entry, each numbered page containing memory blocks for data storage, each such list head entry storing a page number identifying the first of the numbered pages that contains one of the free memory blocks, each frame comprising storage blocks of storage space, comprising the steps of: scanning the page list heads list responsive to a memory request to obtain from the one list head entry that stores a page number matching the first numbered page that contains the one memory block having free storage space at least as large as the requested size; determining a memory block offset for the one memory block relative to the beginning of the frame; maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size; performing at least one of the steps of allocating or deallocating the one memory block by updating the page list heads list; examining the disk block list after the step of allocating when none of the frames in memory have free space: and allocating one of the storage blocks responsive to the memory request.

Claim 12

A method using a computer for allocating a memory block having a requested size in constant time, the computer comprising a cache comprising numbered pages for storing swapped frames of stored data and a page list heads list comprising at least one list head entry, each numbered page containing memory blocks for data storage, each such list head entry storing a page number identifying the first of the numbered pages that contains one of the free memory blocks, each frame comprising storage blocks of storage space, comprising the steps of: scanning the page list heads list responsive to a memory request to obtain from the one list head entry that stores a page number matching the first numbered page that contains the one memory block having free storage space at least as large as the requested size; determining a memory block offset for the one memory block relative to the beginning of the frame; maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size; performing at least one of the steps of allocating or deallocating the one memory block by updating the page list heads list; examining the disk block list after the step of allocating when none of the frames in memory have free space: and allocating one of the storage blocks responsive to the memory request.

Claim 15

A method using a computer for managing a partitioned memory, the computer comprising a memory connected to a storage device, comprising the steps of: organizing the storage device into at least one file comprising numbered data frames of stored data for swapping into the memory, each frame in the at least one file comprising storage blocks of storage space; partitioning the memory into a cache comprising numbered pages for storing swapped frames, each numbered page containing data frames that contain memory blocks of storage space; forming a page list heads list comprising at least one list head entry, each such list head entry storing a page number identifying a first of the numbered pages that contains one of the free memory blocks of a given block size; maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size; allocating the one memory block responsive to a memory request by looking up the numbered page identified by the page number stored in the one list head entry; examining the disk block list after the step of allocating when none of the memory blocks have free space; and allocating one of the storage blocks responsive to the memory request.

Claim 16

A method using a computer for managing a partitioned memory, the computer comprising a memory connected to a storage device, comprising the steps of: organizing the storage device into at least one file comprising numbered data frames of stored data for swapping into the memory, each frame in the at least one file comprising storage blocks of storage space; partitioning the memory into a cache comprising numbered pages for storing swapped frames, each numbered page containing data frames that contain memory blocks of storage space; forming a page list heads list comprising at least one list head entry, each such list head entry storing a page number identifying a first of the numbered pages that contains one of the free memory blocks of a given block size; maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size; allocating the one memory block responsive to a memory request by looking up the numbered page identified by the page number stored in the one list head entry; examining the disk block list after the step of allocating when none of the memory blocks have free space; and allocating one of the storage blocks responsive to the memory request.

Claim 19

A method using a computer for managing a memory, the computer comprising a storage means for storing a file comprising a plurality of frames and a cache connected to the storage means for storing frames swapped into the memory in pages, comprising the steps of: updating a page list in the memory comprising a plurality of page entries, each such page entry containing a number identifying one of the pages that is storing a frame from the plurality of frames having free space of a given block size when a memory request is processed; and updating a disk block list in the memory comprising a plurality of count entries, each such count entry containing a count of frames in the storage means that is storing a frame from the plurality of frames having free space of the given block size when a memory request is processed.

Claim 20

A method using a computer for managing a memory, the computer comprising a storage means for storing a file comprising a plurality of frames and a cache connected to the storage means for storing frames swapped into the memory in pages, comprising the steps of: updating a page list in the memory comprising a plurality of page entries, each such page entry containing a number identifying one of the pages that is storing a frame from the plurality of frames having free space of a given block size when a memory request is processed; and updating a disk block list in the memory comprising a plurality of count entries, each such count entry containing a count of frames in the storage means that is storing a frame from the plurality of frames having free space of the given block size when a memory request is processed.