Heap-based mechanism for efficient garbage collection block selection
US8990484B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 14, 2012 |
| Grant date | Mar 24, 2015 |
| Priority date | — |
| Expiry date | Sep 23, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/7205
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
N page counters are associated with N blocks in the flash subsystem. Each of the N page counters indicates a count of invalid pages in each corresponding block in the N blocks. A max heap structure is formed over the N page counters. At least one of the N page counters is updated each time the count changes. The max heap structure is updated each time the at least one of the N page counters is updated.A maximum value is retrieved from a highest level of the max heap structure. The max heap structure is traversed down to lowest level using the maximum value at each level until reaching the lowest level. The lowest level corresponds to N page counters. One of the N blocks having associated page counter corresponds to the maximum value is identified as a candidate for block erasure.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.