基于YAFFS2的静态磨损均衡算法设计

2014-11-202014-12-301989-、[e-mail]1977-、1966-、1990-．YAFFS211121．4500012．71426454150FTLflashtranslationlayerYAFFS2。。。YAFFS2TP302A1001-3695201604-1091-05doi10．3969/j．issn．1001-3695．2016．04．029Designofstaticwear-levelingalgorithmbasedonYAFFS2LiHengheng1HuZeming1YueChunsheng1WangZhifeng21．InstituteofInformationSystemsEngineeringPLAInformationEngineeringUniversityZhengzhou450001China2．71426UnitJiaozuoHenan454150ChinaAbstractSincemostoftheexistingwear-levelingalgorithmsdesignedforFTL-basedflashmemorystoragesystemcannotbeappliedtotheflashfilesystemwellthispaperdesignedastaicwear-levelingalgorithmbasedonYAFFS2．Consideringthedifferentdataattributesitproposedtwodifferentblockallocationstrategiestospeeddownthegrowthofmaximumerasurecountandstrengthentheutilizationoftheblocksoccupiedbythecolddata．Withthedistributionoftheblockerasurecountsintheflashphysicalspacerandomizedthealgorithmsimplifiedthesearchoperationinblockallocationprocesswhichreducedthealgorithmcomplexity．Theuneventhresholdtriggermechanismalsoensuredaoutstandingwear-levelingeffect．Theexperi-mentresultsshowthatthealgorithmreducesthevarianceoftheerasurecountsandimprovesthedegreeofevennesswhichcanprolongtheservicelifeofflashandimprovethereliabilityofflashstoragesystemeffectively．KeywordswearlevelingflashfilesystemYAFFS2storagereliability0flash、、、、、、。、PCflash-basedsolidstatediskSSD。1flashFTLflashtranslationlayerflash。1。Flashflash1a。FTL、、。flashflash、、、12。flashflash、flash1b。FTLflash33420164ApplicationＲesearchofComputersVol．33No．4Apr．2016、。flashTrueFFS、JFFSx、YAFFS、SMXFFS。YAFFS2。。3～5FTLflashYAFFS26。2。。NANDflashYAFFS2。。1。。。7。1.1。。I/O。1.2、。。。Woodhouse8100。Ban91000。。、、。Chang3dualpoolDP“”“”“”“”。“”“”。“”。“”。。1.3YAFFS2YAFFS210。YAFFS2YAFFS23。YAFFS2。YAFFS2·2901·33ab。YAFFS2。。。24。。。。2.1YAFFS2。。。。。2、N、dif。C=EC1EC2…ECnEC1＜EC2＜…＜ECnK=k1k2…kn。、dif=ECn－EC1=n－1ECiPc=ECi=ki∑Nj=1kj1ECiFECi=Pc≤ECi=∑im=1km∑nj=1kj2EClimit∈CEC≤EClimitEClimit3Plimit∈01。EClimit=maxECi|FECi≤Plimit3nEC≤EClimitn。nEC≤EClimitPP=1－1－FEClimitn4FEClimit=PlimitEClimit∈CnEC≤EClimitPP=1－1－Plimitn。5。dif。2.2。YAFFS2。YAFFS2。5。2．1。ECwl∈CEC＞ECwlECwl5。Pwl∈012．1。ECwl=minECi|1－FECi＞Pwl5·3901·4YAFFS2。YAFFS2sequencenumber。。。。。。2.3、。。ECmax－ECmin＞TH6、TH6。。2.41aalloc_blockselect=0balloc_block=alloc_block+1Ns=ECmax－ECmin+1cwl_flag1afdNs=0he3EClimitalloc_blockecec≤EClimitselect=alloc_blockhNs=Ns－1alloc_block=alloc_block+1dfNs=0hg5ECwlalloc_blockecec＞ECwlselect=alloc_blockhalloc_block=alloc_block+1Ns=Ns－1f。hselect。2ab、ECmax、ECminΔ=ECmax－ECmincΔ＜THdBlockInfoblocksequenceBWLe1Ballocalloc_blockfBWLBallocBWL。3IntelCorei5CPU2．5GHz4GBDDＲ31600MHz。Ubuntu11．042．6．38-8-generic。LinuxNANDSIM1。post-mark19．7MB15%TH42YAFFS2。6。1NANDSIM128MB10246425ns2KB200ns2ms2THPlimitPwl19．7MB10KB～200KB6002．5～1540．50．56StaticYAFFS2YAFFS25、10ID。ID100YAFFS2Static。72．5～15ΔΔ=ECmax－ECmin7Static。Static。8StaticYAFFS2YAFFS2。9·4901·33。PD811PD=ECMAX1－ECMAX2/ECMAX28ECMAX1、ECMAX2ECMAX1＞ECMAX2。Static。150000PD17．9%。10Static15%。THTH。4YAFFS2。。。1．FlashJ．2010474716-726．2．J．201350149-59．3ChangLipin．Onefficientwearlevelingforlarge-scaleflash-memorystoragesystemsC//ProcofACMSymposiumonAppliedCompu-ting．S．l．ACMPress20071126-1130．4WangChundongWongWengfei．Observationalwearlevelinganeffi-cientalgorithmforflashmemorymanagementC//Procofthe49thACM/EDAC/IEEEDesignAutomationConference．S．l．IEEEPress2012235-242．5GudetaYHKwonSJChoESetal．Probability-basedstaticwear-levelingalgorithmforblockandhybrid-mappingNANDflashmemoryJ．DesignAutomationforEmbeddedSystems2012164241-264．6HommaT．EvaluationofflashfilesystemsforlargeNANDflashmem-oryC//ProcofCELFEmbeddedLinuxConference．2009．7MuruganMDuDHC．ＲejuvenatorastaticwearlevelingalgorithmforNANDflashmemorywithminimizedoverheadC//Procofthe27thIEEESymposiumonMassStorageSystemsandTechnologies．S．l．IEEEPress20111-12．8WoodhouseD．JFFSthejournallingflashfilesystemC//ProcofOt-tawaLinuxSymposium．2001．9BanA．WearlevelingofstaticareasinflashmemoryU．S．Patent6732221P．2004-05-04．10ManningC．HowYAFFSworksEB/OL．20102011-04-03．http//．yaffs．net/documents/how-yaffs-works．11．OEBSJ．200930122489-2492．10901．ITJ．201225287-97．2ChauhanSS．ProthJM．AnalysisofasupplychainpartnershipwithrevenuesharingJ．InternationalJournalofProductionEcono-mics200597144-51．3FrankYC．Analysisofthird-partywarehousingcontractswithcom-mitmentsJ．EuropeanJournalofOperationalＲesearch2001621603-610．4ZhouYongwu．Acomparisonofdifferentquantitydiscountpricingpo-liciesinatwoechelonchannelwithstochasticandasymmetricdemandandinformationJ．EuropeanJournalofOperationalＲesearch20071815686-703．5ArcelusFJKumarS．EvaluatingmanufacturesbuybackpoliciesinasingleperiodtwoechelonframeworkunderpricedependentstochasticdemandJ．Omega2006365808-824．6AlfredssonM．HowTPIproviderscreateeffectivenessandefficiencybycoordinationofcustomersactivitiesandstrategiesC//ProcofSSE/EFIWorkingPaperSeriesinBusinessAdministration．2001．7．J．201218365-71．8．J．20081558-60．9．J．2008324589-592．10．J．201032848-52．11．J．200915122412-2419．12．J．20061227-229．13．J．20134284-90．14．J．200917259-65．15SpinierSHuehzermeierA．Thevaluationofoptionsoncapacitywithcostanddemandunc