[go: up one dir, main page]

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
Legal status (The legal status 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 status listed.)
Ceased
Application number
PCT/GB2001/004506
Other languages
French (fr)
Other versions
WO2002031660A2 (en
Inventor
Christopher Donald Clack
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University College London
Original Assignee
University College London
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 University College London filed Critical University College 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
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

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 Ceased 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
GB0024927.6 2000-10-11
GB0024927A GB0024927D0 (en) 2000-10-11 2000-10-11 A data structure memory allocator and memory management system

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 Ceased 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
FI20125118L (en) * 2012-02-03 2013-08-04 Tellabs Oy Method and apparatus for managing 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
AU2001293984A1 (en) 2002-04-22
EP1327194A2 (en) 2003-07-16
GB0024927D0 (en) 2000-11-29

Similar Documents

Publication Publication Date Title
WO2006072945A3 (en) Method of managing a multi-bit cell flash memory with improved reliability and performance
CN1037633C (en) Electronic device having ferroelectric memory
WO2004095461A3 (en) Redundant memory structure using bad bit pointers
EP2003649A3 (en) Emulated combination memory device
EP0774758A3 (en) Memory architecture using content addressable memory, and systems and methods using the same
WO2001071465A3 (en) Portable computer system
EP1046980A3 (en) Portable electronic device having a log-structured file system in flash memory
CA2151181A1 (en) Multicast shared memory
EP0981091A3 (en) Data copying in storage systems
WO2000045447A3 (en) Proton conducting membrane using a solid acid
WO2003051030A3 (en) Management and control of buffer in client device
CA2131079A1 (en) Fixed-Length Packet Switching System Adapted for Function Test
AU2002357982A1 (en) Reconfigurable elements
WO2002031660A3 (en) A data structure, memory allocator and memory management system
CN101707565A (en) Method and device for transmitting and receiving zero-copy network message
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
CA2415018A1 (en) Adaptive parallel data clustering when loading a data structure containing data clustered along one or more dimensions
JPS5314525A (en) Memory circuit
WO2004036664A3 (en) Hydrogen storage material with high storage capacity
Franta et al. A comparison of heaps and the TL structure for the simulation event set
CN101655734A (en) Computer with power-saving state control and control method thereof
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