Garbage Management System Project

Efficient Garbage Collection Policy and Block Management Method for NAND Flash Memory

For flash memories, blocks with saved data must be erased before new data can be written in them again. Research on garbage collection has been actively carried out for the efficient performance. Brief review of existing garbage collection and block management methods are as follows. A. Greedy Method The Greedy algorithm performs garbage collection by selecting blocks that have the highest number of invalid pages [3]. Because no separate operations are necessary, this method offers such advantages as fast performance and a smaller number of valid pages that must be copied to new blocks. However, it has a weak point for wear leveling, since the block erase count is not considered. B. Cost-Benefit Method The Cost-Benefit algorithm pursues the equal use of blocks by considering the block allocation time in addition to the Greedy algorithm [4].

The policy is to selectively erase blocks with profits (additionally acquired capacities) that are greater than their costs (block erasing cost and the cost of copying valid pages to other blocks), which can be expressed as follows Where u is the ratio of valid pages in a block; (l-u) is the ratio of invalid pages in a block; 2u is the cost when valid pages in a block are copied to another block; and Age is the elapsed time after the pages are written in the block. Code Shoppy The Cost-Benefit method induces wear leveling using Age, but it is a basically inappropriate wear leveling method because it uses the recording time rather than the block erase count. C. Plain Cleaning Policy(PCP) Method The PCP algorithm performs garbage collection by selecting blocks that have a low erase cost to improve the file system performance [5]. (2) calculates the erase cost, wherein V is the ratio of valid pages in a block to the total pages and F is the ratio of free pages to the total pages in the block. (3) is used to determine blocks with a high R value to reduce the erase cost and equalize the erase count of the blocks. EA is the difference between the erase count limit and the current erase count. D. Modification-aware(MODA) Page Allocation Method The data recorded in a NAND flash memory have different update counts. Considering this fact, [6] gathers and saves hot data and cold data in different blocks to improve purity. Here, purity means the ratio of blocks with both valid and invalid data to the total blocks of a flash memory. On the criterion for dividing hot and cold data, data are classified as hot data if the update count is 2 or more, and as cold data if the update count is 0 when ilt is 10. ilt is the logical time unit that increases each time there is a write request. Because hot data have a higher update probability than cold data, hot data are gathered in the same blocks when they are saved. Similarly, cold data with low update probability are stored in the same blocks to improve the probability of their exclusion from erasing, and thus, decreasing the total erase count. However, the MODA Page Allocation Method cannot guarantee wear leveling because it does not consider the erase count of the blocks.

This paper proposes a garbage collection and block management method that considers wear leveling while basically using the MODA Page Allocation Method. The proposed methods induce wear leveling of all blocks by selecting blocks for garbage collection based on different criteria by data type. Furthermore, a free block allocation method that considers wear leveling by separately creating free block lists by data type is presented.

. Block Management Method In general, the NAND flash memory creates a block list in RAM after it is mounted. YAFFS [7], a typical flash memory filing system, simply creates a list in the order of the block number, and it is inefficient for finding blocks to be erased or free blocks to allocate during garbage collection. We create different lists for blocks that contain data and for free blocks in the RAM. Additionally, data block lists and free block lists are separately created by data type for efficient garbage collection and free block allocation. 1) Creation of a free block list and the free block allocation method: Blocks that store hot data, cold data, and warm data (which do not belong to hot or cold data) have different probabilities of being erased. Therefore, different criteria for allocating free blocks are needed when writing these data. The proposed method arranges free blocks in the RAM in the ascending order of their erase count, and creates three lists of free blocks, i.e., Freelistl, Freelist2, and Freelist3 for hot data, warm data, and cold data, respectively. Because the blocks that store hot data have the highest probability of being erased, when hot data are written, a free block is allocated from the first free block list with the lowest erase count; for warm data or new data, a free block is allocated from the second list; and for cold data, a free block is allocated from the third list. If there is no free block in a free block list, a free block is allocated from the next free block list.

2) Creation of data block lists: When lists of blocks that contain data are created in RAM, separate lists are created for hot data blocks, warm data blocks, and cold data blocks. These three lists are arranged based on different criteria for efficient garbage collection and free block allocation. Due to frequent modifications, hot data blocks have a high percentage of invalid pages. Free blocks that have the lowest erase count are allocated for hot data. Therefore, hot data blocks should be considered first when garbage collection is performed. Hot data blocks are listed in the descending order of their invalid page ratio to minimize the erase cost during garbage collection. Since cold data are not updated frequently, cold data blocks have a lower invalid page ratio and a higher erase count. Thus, they should be processed last during garbage collection. Cold data blocks should be arranged in ascending order of their erase count so that the erase count limit would not be exceeded. Finally, since warm data are in the middle of hot and cold data, both the invalid page ratio and the erase count should be considered.

B. Garbage Collection Method Y AFFS performs garbage collection before data writing. Since this delays the write operation, garbage collection should be performed while the system is in idle status to prevent the delay of the write operation.

For this purpose, two cases are considered. First, based on the proof that if the system is idle for 2 seconds, the probability that the system will continue to be idle for 4 seconds is 95%, the garbage collection is performed when the system is idle for 2 seconds [8]. At this time, the blocks with only invalid pages are erased to minimize the system overhead. Second, if the system continues to run without idle time, garbage collection is performed when the number of free block falls below Tfi which is the number of hot data blocks. The garbage collection is carried out in the order of the list whose data blocks have low erase counts: hot data list, warm data list, and cold data list. To prevent the excessive erase cost, the threshold values are set. In the hot data list, the threshold value Th is the number of invalid pages in a block. If there are hot data blocks with their number of invalid pages greater than Th, garbage collection is performed in the descending order of the invalid page ratio in the hot data list. For the warm data list, garbage collection is performed for blocks that have the w value in (4) of which is greater than the threshold Tw. Lastly, in the cold data list, garbage collection is performed for the blocks that have erase counts lower than the threshold Te. Figure 3 shows the garbage collection flowchart using the proposed method. https://codeshoppy.com/shop/product/location-based-garbage-management-system-for-smart-city/