Research On Cache Replacement And Garbage Collection Algorithms For Flash Memory System

Flash memory is a pure electronic data storage device.Compared with mechanical disk,it has the advantages of small volume,fast access,low energy consumption and strong shock-resistance and other characteristics.Therefore,flash memory has become one of the storage media that replaces or partially replaces mechanical hard disks.Compared with mechanical hard disk,flash memory exhibits completely different physical characteristics,such as inconsistent read and write speeds and limited erasure times.As a result,current cache algorithms optimized and designed for mechanical hard disks cannot be directly applied to flash memory storage systems.Besides,the flash memory has an off-site update feature and the garbage collection mechanism must be triggered when retrieving an invalid page operation,but the existing garbage collection algorithm still has some shortcomings.Based on the above two issues,this paper intends to study the cache replacement and garbage collection algorithms for flash storage systems.The specific research contents are as follows:(1)This thesis proposes a new buffer replacement algorithm CF-ARC for Flash database.It designs a new page replacement mechanism and adds a new mirror area to the existing buffer chain table to save the page number information which are ejected.At the same time,the pages in the cache are divided into clean pages and dirty pages.When the buffer capacity is full,the clean pages are firstly expelled,and through the dynamic adjustment mechanism of the mirror area and the buffer area,the defects of the well-defined range of the work area w in the CF-LRU algorithm are compensated;(2)In order to solve the problem of high eviction cost brought by CF-ARC algorithm to expel hot clean pages,this thesis proposes an H-ARC algorithm after the above algorithm is optimized,subdividing the buffer into cold zone and hot zone,specifically setting two mirror zone linked lists to store page number information of the evicted page and the parameter values of the related page,and preferentially replacing the clean pages with low frequency of access,it allows hot pages to stay in the buffer and thus increases page hits.When the buffer is full,the dynamic adjustment mechanism of the mirror area and the buffer helps to solve the problem of the clean pages5 being evicted when they just enter the buffer.Through comparative analysis of the experimental results,it is found that in most cases the algorithm has a better performance than other replacement algorithms;(3)The existing garbage collection algorithm of the flash translation layer has defects in triggering garbage collection operations,for it is difficult to perform optimal sacrifice block selection when facing the same function value.This thesis presents a new optimization strategy to solve the dilemma of easily encountering sacrificial block selection in large-capacity flash memory.Experiments show that the new strategy can achieve good recovery performance and guarantee the service life of flash memory chips.