METHOD AND DEVICE FOR MANAGING A MEMORY

• US 20150169237A1
• Filed: 09/26/2014
• Published: 06/18/2015
• Est. Priority Date: 12/17/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Koltsidas, Ioannis, Pletka, Roman A., Weigold, Thomas D., Ioannou, Nikolas, Tomic, Sasa
• Granted Patent: US 9,760,309 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method for managing a memory is disclosed, the memory including a set of units and a unit comprising a set of pages, wherein a unit of the set of units is erasable as a whole by a unit reclaiming process resulting in a free unit available for writing data to. The method includes maintaining a first pool of units available for reclamation by the unit reclaiming process; maintaining a second pool of units not available for reclamation by the unit reclaiming process; moving a first unit from the first pool to the second pool in response to invalidating a first one of the pages contained in the first unit; returning the first unit from the second pool to the first pool after a defined number of units of the set have been written; and selecting a unit out of the first pool for reclamation by the unit reclaiming process.

Claims

1. A method for managing a memory, the memory comprising a set of units and a unit comprising a set of pages, wherein a unit of the set of units is erasable as a whole by a unit reclaiming process resulting in a free unit available for writing data to, and wherein data updates are performed by writing data updates out-of-place, wherein data updates to outdated data are written to a page different from a page containing the outdated data, and wherein the page containing the outdated data is invalid, while a page containing up-to-date data is a valid page, the method comprising:

maintaining a first pool of units available for reclamation by the unit reclaiming process;

maintaining a second pool of units not available for reclamation by the unit reclaiming process;

moving a first unit from the first pool to the second pool in response to invalidating a first one of the pages contained in the first unit;

returning the first unit from the second pool to the first pool after a defined number of units of the set have been written; and

selecting a unit out of the first pool for reclamation by the unit reclaiming process.

2. The method of claim 1, wherein a unit of the set is written once the unit solely comprises either valid or invalid pages.

3. The method of claim 1, wherein the second pool comprises a circular buffer of queues for buffering units therein, and an index pointer for pointing at one of the queues, and moving a first unit from the first pool to the second pool comprises removing the first unit from the first pool and adding the first unit to the queue the index pointer presently points at.

4. The method of claim 3, wherein the index pointer is incremented for pointing at a next queue of the circular buffer in response to a unit of the set being written.

5. The method according to claim 3, further comprising, in response to the index pointer being incremented to point to the next queue, returning all units arranged in the next queue to the first pool by removing the units from the next queue and adding the units to the first pool.

6. The method of claim 1, wherein:

the second pool comprises a single queue for buffering units therein;

moving a unit from the first pool to the second pool comprises removing the first unit from the first pool, adding the first unit to the single queue and assigning a timestamp to the first unit for indicating a number of units of the set written until the move;

in response to a unit of the set being written, a subset of units is determined from the single queue comprising all units with a timestamp equal to a current value of a reference write timestamp indicating a number of written units in the set, minus a defined number of units to be written for delay purposes; and

the determined subset of units is returned to the first pool by removing the units thereof from the single queue and adding the units to the first pool.

7. The method of claim 1, wherein:

the first pool comprises bins each bin being reserved for units comprising a number of invalid pages which number falls in a defined range of one or more invalid pages associated with the subject bin;

in response to a trigger event the unit reclaiming process selects at least one unit from the bin populated with the units containing the highest number of invalid pages for reclamation; and

valid pages of the at least one unit selected are relocated to other units, wherein after relocation the at least one unit is erased.

8. The method according to claim 7, wherein the trigger event is defined by a number of units in a third pool falling below a threshold, the third pool comprising units being erased and not yet written.

9. The method according to claim 7, wherein returning a unit from the second pool to the first pool comprises determining one of the bins for adding the unit to dependent on a present number of invalid pages in the first unit, and adding the first unit to the determined bin.

11. A computer program product comprising a computer readable medium having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured to perform a method according to claim 1.

16. The memory controller of claim 11, wherein:

the second pool comprises a single queue for buffering units therein;

a unit from the first pool is moved to the second pool by removing the first unit from the first pool, adding the first unit to the single queue and assigning a timestamp to the first unit for indicating a number of units of the set written until the move;

in response to a unit of the set being written, a subset of units is determined from the single queue comprising all units with a timestamp equal to a current value of a reference write timestamp indicating a number of written units in the set, minus a defined number of units to be written for delay purposes; and

the determined subset of units is returned to the first pool by removing the units thereof from the single queue and adding the units to the first pool.

17. The memory controller of claim 11, wherein:

the first pool comprises bins each bin being reserved for units comprising a number of invalid pages which number falls in a defined range of one or more invalid pages associated with the subject bin;

in response to a trigger event the unit reclaiming process selects at least one unit from the bin populated with the units containing the highest number of invalid pages for reclamation; and

valid pages of the at least one unit selected are relocated to other units, wherein after relocation the at least one unit is erased.

18. The memory controller according to claim 17, wherein the trigger event is defined by a number of units in a third pool falling below a threshold, the third pool comprising units being erased and not yet written.

19. The memory controller according to claim 17, wherein returning a unit from the second pool to the first pool comprises determining one of the bins for adding the unit to dependent on a present number of invalid pages in the first unit, and adding the first unit to the determined bin.

10. A method for managing a memory, the memory comprising a set of units and a unit comprising a set of pages, wherein a unit of the set of units is erasable as a whole by a unit reclaiming process resulting in a free unit available for writing data to, and wherein data updates are performed by writing data updates out-of-place, wherein data updates to outdated data are written to a page different from a page containing the outdated data, and wherein the page containing the outdated data is invalid, while a page containing up-to-date data is a valid page, the method comprising:

maintaining a first pool of units available for reclamation by the unit reclaiming process;

maintaining a second pool of units not available for reclamation by the unit reclaiming process, which second pool comprises a First-In-First-Out buffer;

moving a first unit from the first pool to the second pool in response to invalidating a first one of the pages contained in the first unit;

in response to moving the first unit from the first pool to the second pool returning another unit from the second pool to the first pool; and

selecting a unit out of the first pool for reclamation by the unit reclaiming process.

12. A memory controller for managing a memory comprising a set of units and a unit comprising a set of subunits, wherein a unit of the set of units is erasable as a whole by a unit reclaiming process resulting in a free unit available for writing data to, and wherein data updates are performed by writing data updates out-of-place, wherein data updates to outdated data are written to a subunit different from a subunit containing the outdated data;

and wherein the subunit containing the outdated data is invalid, while a subunit containing up-to-date data is a valid subunit, wherein the memory controller is configured to;

maintain a first pool of units available for reclamation by the unit reclaiming process;

maintain a second pool of units not available for reclamation by the unit reclaiming process;

move a first unit from the first pool to the second pool in response to invalidating a first one of the pages contained in the first unit;

return the first unit from the second pool to the first pool after a defined number of units of the set have been written; and

select a unit out of the first pool for reclamation by the unit reclaiming process.

13. The memory controller of claim 12, wherein:

the second pool comprises a circular buffer of queues for buffering units therein, and an index pointer for pointing at one of the queues; and

wherein the memory controller is configured to move a unit from the first pool to the second pool by removing the first unit from the first pool and adding the first unit to the queue the index pointer presently points at.

14. The memory controller of claim 13, wherein the memory controller is further configured to:

increment the index pointer for pointing at a next queue of the circular buffer in response to a unit of the set being written; and

return all units arranged in the next queue to the first pool in response to the index pointer being incremented for pointing to the next queue.

15. The memory controller according to claim 13, wherein, in response to the index pointer being incremented to point to the next queue, all units arranged in the next queue are returned to the first pool by removing the units from the next queue and adding the units to the first pool.