硕士论文-基于NAND的使用压缩缓存策略的交换系统的设计与实

上海交通大学硕士学位论文基于NAND的使用压缩缓存策略的交换系统的设计与实现姓名：顾锋磊申请学位级别：硕士专业：软件工程指导教师：步丰林200801015NANDNANDNANDNANDNANDNANDNANDNANDNANDNANDNANDNANDSNSSSmartNANDSwapSystemSNSSNANDNANDSNSSNANDNANDNANDNANDSNSSLRUNAND6SNSSSNSSNANDNANDNANDNAND7ABSTRACTSomesmartphonesandlaptopcomputersnowexploitswapsystemwiththeirsecondstoragemediaasacosteffectivesolutiontoextendlimitedmemoryspace.TherapidevolvingflashmemorytechnologystartstoreplacethemagneticdisksofthesecomputersbyNANDflashduetoitsadvantageouscharacteristicssuchasenergyefficiency,accessspeedandmechanicalshockresistance.AlthoughNANDFlashiscurrentlyconsideredasthesecondmass-storagemedia,wecanimaginethattheswapsystemrunningoverNANDflashwillshowupinthefuture.However,NANDsufferslimitedlifespancomparedwithmagneticdisks.BlocksofNANDFlashwillbedestroyedifcertainblocksareerasedtoomanytimes.Asaresult,ourresearchfocusesonhowtoreducewritingoperationsonNANDFlashwhileswappinginandout.Thispaperpresentsanewswapsystemmodel,SNSS(SmartNANDSwapSystem).Andacompressedcacheinswapsystemisintroduced,aswellastwo-levelreplacementalgorithmandadaptivecompression,whichareintendtoreduceaccesstoNAND.AcompressedcacheisusedasmiddlelayerbetweenmainmemoryandNANDswaparea.ThecacheandtheNANDsharethesameaddressspaceofpageslots.Eachswappedpagewillbecompressedfirstandthenallocatedwithsomepageslot,incacheorNANDormaybeboth.Thetwo-levelreplacementalgorithmintroducedbySNSSisdesignedtobethatpagesinRAMarereplacedfollowingLRUliketradition,andpagesincompressedcachearereplacedwithaspecialalgorithmwhichperformsCleanpageFirst,ThenNew,DirtyLastwhilerewritingonNANDcoststoomuchandcreatinganewpagecostsless.Furthermore,adaptivecompressionisintroducedinSNSS,whichisusedtoavoidcompressionunderlowcompressionrate.BysimulatingtheSNSSmodel,wegettheconclusionthatSNSScanreduceflashwriteoperationsby50%onaveragecomparedwiththe8traditionalswapsystem.Asaresult,NANDwillkeephealthytwicelonger.Keywords:SwapSystem,NAND,Compression,Cache111..................................102C.Park[1]XIP-NAND..................................143jffs...........................................154Sangduck...........................205..............................226FTL(a)FASS(b)................................227..............................248SNSS.......................................279........................................2810........................................2911............................................2912FTL..................................3013FTL................................3114............................................3215CFLRU...............................................3416................................36175.1.1................................39185.1.1..................................39195.1.2............................40205.1.2NAND...........................40215.1.2..............................41225.2..............................41235.2NAND.............................41245.2................................4225..........................................42121.....................................52........................................333..................................36320083182008318200831811.13GEPROMNORFlashNANDNANDFlashIDC20061202010200NANDFlashNAND200632GBNAND20071064GBNANDFlashPCNANDFlash(NAND)NANDNANDNANDNANDPC(SwapArea)windowsPCSRAMNANDNANDG2NANDNANDNANDNANDNANDNANDNANDNAND1.2NAND-SNSSSmartNAND-basedSwapSystemSNSSNANDFlashNANDLinuxNAND1.3NANDSNSSNANDFlashSNSSSNSSSNSSzSNSSNANDzSNSSzSNSSzSNSSNANDSNSS3zSNSS1.4SNSS1.SNSSNANDFlash2.SNSSNAND3.NAND4.SNSS5.SNSSNAND6.SNSS1.5NANDNANDNANDNANDSNSSNANDSNSS42.1Flash2.1.1FlashFlashEEPROM()EEPROMFlashFlash(block)EEPROMEEPROMFlashFlashEEPROMFlashNANDNORNORFlashNANDFlashIntel1988NORFlashXIPeXecuteInPlaceNORFlashRAMToshibaNANDFlashNANDFlashNORNANDNORNANDNORFlashNANDFlashNANDFlash(block)0xffNORFlash(bit)0NANDFlash(page)NORFlash/NANDFlash4ms(8~32K)NORFlash5s64~128KNORNANDNANDNORNANDNOR1~4M5NORFlashCodeFlashbootloaderNORFlashmp3NANDFlashNANDNANDNORNANDFlashNORFlashNANDFlashDataFlash2.1.2FlashFlashFlash[1]SDRAMFlashNORNANDNANDNORNANDNORNANDCurrent(mA)Accesstime(4kB)DeviceIdleActiveReadWriteEraseNOR0.033223us28ms1.2secNAND0.0110291us1.8ms2msSDRAM(32MB)0.5085184us184usN/ASDRAM(64MB)1.00120184us184usN/AHarddisk(20GB)2342015ms15msN/A1FlashNANDFlash62.2NANDFlash2.2.1NANDNANDFlash(page)Flash(block)FlashNORNANDSpareArea51216SpareAreaECCNAND(SmallPage)(LargePage)MLCNAND512+162048+64MLCNAND4G41GNANDFlash8I/ONAND8I/O2.2.2NANDFlash/(EDC/ECC)NANDNORNANDFlashNANDFlashFlashNANDNANDNANDNAND10NANDNANDNAND71NANDI/O2NANDGarbageCollection3NANDWearLevelingNANDNAND4ECCNORNAND/EDC/ECCNANDEDC/ECC.NAND2.32.3.1MMUMMUMemoryManageUnitMMUCPUMMU1(VirtualAddress)(PhysicalAddress)MMU2(VirtualMemorySpace)3MMU4CPUCacheMMUMMU8/4GMMU12MMU3MMU2.3.2TLBMMU2nKBn2MMUTranslationLookasideBufferTLBassociativecachepagetableentryPTETLBdirtybitaccessedbitLRUusermodesupervisormode92.42.4.1LinuxDemandPagingMappingLinuxSwappingCPULinuxstructpagePresentRAMMMUMMU2.4.2UnixUnixthreshold10UnixLinuxLinuxzzzIPC1(SwapArea)UnixLinuxSwap(SwapFile)Windows1Lin