+

WO2002031660A3 - A data structure, memory allocator and memory management system - Google Patents

A data structure, memory allocator and memory management system Download PDF

Info

Publication number
WO2002031660A3
WO2002031660A3 PCT/GB2001/004506 GB0104506W WO0231660A3 WO 2002031660 A3 WO2002031660 A3 WO 2002031660A3 GB 0104506 W GB0104506 W GB 0104506W WO 0231660 A3 WO0231660 A3 WO 0231660A3
Authority
WO
WIPO (PCT)
Prior art keywords
cells
free
memory
allocator
free cells
Prior art date
Application number
PCT/GB2001/004506
Other languages
French (fr)
Other versions
WO2002031660A2 (en
Inventor
Christopher Donald Clack
Original Assignee
Univ London
Christopher Donald Clack
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Univ London, Christopher Donald Clack filed Critical Univ London
Priority to AU2001293984A priority Critical patent/AU2001293984A1/en
Priority to EP01974469A priority patent/EP1327194A2/en
Publication of WO2002031660A2 publication Critical patent/WO2002031660A2/en
Publication of WO2002031660A3 publication Critical patent/WO2002031660A3/en

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)

Abstract

We present a Best Fit allocator for dynamic memory management. Portions of the memory that are presently unused are call free cells, and each free cell has a size. The allocator uses a bitmap which, for each number of predetermined sizes, indicates whether free memory cells of that size exist. It also employs a second data array with an entry for each of the predetermined cell sizes. When one or more free cells of a given size exist, the corresponding entry of the data array is a pointer to one of those free cells. The free cells themselves contain pointers to other free cells of the same size, or to free cells that are slightly smaller or larger. The allocator is scalable, in that the worst-case behaviour is independent of the size of the heap, and is independent of the number of free cells and of the number of cells already in use for memory storage. It is also incremental and non-disruptive, in that each memory operation (including splitting and coalescing of free cells) is guaranteed to complete within a small bounded time. We also present a novel collector and a priority queuing mechanism that operate on principles similar to those of the allocator.
PCT/GB2001/004506 2000-10-11 2001-10-10 A data structure, memory allocator and memory management system WO2002031660A2 (en)

Priority Applications (2)

Application Number Priority Date Filing Date Title
AU2001293984A AU2001293984A1 (en) 2000-10-11 2001-10-10 A data structure, memory allocator and memory management system
EP01974469A EP1327194A2 (en) 2000-10-11 2001-10-10 A data structure, memory allocator and memory management system

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB0024927A GB0024927D0 (en) 2000-10-11 2000-10-11 A data structure memory allocator and memory management system
GB0024927.6 2000-10-11

Publications (2)

Publication Number Publication Date
WO2002031660A2 WO2002031660A2 (en) 2002-04-18
WO2002031660A3 true WO2002031660A3 (en) 2002-08-01

Family

ID=9901094

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/GB2001/004506 WO2002031660A2 (en) 2000-10-11 2001-10-10 A data structure, memory allocator and memory management system

Country Status (4)

Country Link
EP (1) EP1327194A2 (en)
AU (1) AU2001293984A1 (en)
GB (1) GB0024927D0 (en)
WO (1) WO2002031660A2 (en)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7039785B2 (en) 2004-02-24 2006-05-02 Hitachi, Ltd. Method and apparatus for increasing an amount of memory on demand when monitoring remote mirroring performance
GB2444746A (en) * 2006-12-15 2008-06-18 Symbian Software Ltd Allocating memory sectors for a data block by finding a contiguous area which starts with a sector with unused memory at least at much as the overlap
DE102009036095A1 (en) * 2009-08-04 2011-02-10 Giesecke & Devrient Gmbh Method for managing storage resources in a portable volume
FI20125118A7 (en) * 2012-02-03 2013-08-04 Tellabs Oy A method and a device for controlling memory allocation
US9128615B2 (en) 2013-05-15 2015-09-08 Sandisk Technologies Inc. Storage systems that create snapshot queues
US11474865B2 (en) * 2019-08-23 2022-10-18 Micron Technology, Inc. Allocation schema for a scalable memory area
GB2595265A (en) * 2020-05-20 2021-11-24 Imagination Tech Ltd Memory for storing data blocks

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0675442A1 (en) * 1994-03-31 1995-10-04 Lexmark International, Inc. Returned electronic memory retrieval
US5784699A (en) * 1996-05-24 1998-07-21 Oracle Corporation Dynamic memory allocation in a computer using a bit map index

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0675442A1 (en) * 1994-03-31 1995-10-04 Lexmark International, Inc. Returned electronic memory retrieval
US5784699A (en) * 1996-05-24 1998-07-21 Oracle Corporation Dynamic memory allocation in a computer using a bit map index

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
JONES ET AL.: "Garbage Collection: Algorithms for Automatic Dynamic Memory Management", 1996, WILEY, CHICHESTER; GB, XP002198230, 22942 *
OGASAWARA T: "An algorithm with constant execution time for dynamic storage allocation", REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, 1995. PROCEEDINGS., SECOND INTERNATIONAL WORKSHOP ON TOKYO, JAPAN 25-27 OCT. 1995, LOS ALAMITOS, CA, USA,IEEE COMPUT. SOC, US, 25 October 1995 (1995-10-25), pages 21 - 25, XP010196652, ISBN: 0-8186-7106-8 *

Also Published As

Publication number Publication date
WO2002031660A2 (en) 2002-04-18
GB0024927D0 (en) 2000-11-29
EP1327194A2 (en) 2003-07-16
AU2001293984A1 (en) 2002-04-22

Similar Documents

Publication Publication Date Title
WO2006072945A3 (en) Method of managing a multi-bit cell flash memory with improved reliability and performance
WO2004095461A3 (en) Redundant memory structure using bad bit pointers
EP2003649A3 (en) Emulated combination memory device
WO2001071465A3 (en) Portable computer system
TW345660B (en) Stabilization circuits and techniques for storage and retrieval of single or multiple digital bits per memory cell
EP1225589A3 (en) Semiconductor memory device having a plurality of low power consumption modes
CA2151181A1 (en) Multicast shared memory
WO2000045447A3 (en) Proton conducting membrane using a solid acid
WO2003051030A3 (en) Management and control of buffer in client device
WO2001067236A3 (en) System and method for preloading classes in a data processing device that does not have a virtual memory manager
WO2002031660A3 (en) A data structure, memory allocator and memory management system
WO2001059565A3 (en) Computer system including a memory access controller for using non-system memory storage resources during system boot time
CN101707565A (en) Method and device for transmitting and receiving zero-copy network message
EP0905711A3 (en) Nonvolatile memory device and deterioration detecting method
CA2249137A1 (en) Non-volatile mission-ready database for signaling transfer point
GB0327571D0 (en) A memory dump of a computer system
CN101281491B (en) VxWorks-based Memory Module and Management Method of Space Robot Central Processor
EP0810609A3 (en) Single electron memory cell device
JPS5314525A (en) Memory circuit
WO2003102725A3 (en) Method for data storage in external and on-chip memory in a packet switch
CN101655734A (en) Computer with power-saving state control and control method thereof
Franta et al. A comparison of heaps and the TL structure for the simulation event set
EP0788107A3 (en) Semiconductor memory device
WO2002027619A3 (en) Application-driven scheduling system and method
WO1999009467A3 (en) A transient datastream-processing buffer memory organization with software management adapted for multilevel housekeeping

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ PH PL PT RO RU SD SE SG SI SK SL TJ TM TR TT TZ UA UG US UZ VN YU ZA ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

AK Designated states

Kind code of ref document: A3

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ PH PL PT RO RU SD SE SG SI SK SL TJ TM TR TT TZ UA UG US UZ VN YU ZA ZW

AL Designated countries for regional patents

Kind code of ref document: A3

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 2001974469

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2001974469

Country of ref document: EP

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

WWW Wipo information: withdrawn in national office

Ref document number: 2001974469

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载