34-One-level storage system.pdf

ComputerScience261Copyright2005Page1of3One-LevelStorageSystemKilburn,Edwards,Lanigan,Sumner(1961)Supersetof:DynamicStorageAllocationintheAtlasComputer,IncludinganAutomaticUseofBackingStore,Fotheringham(1961).Whatkindofpaper?Newidea.Motivation.Explanation.Algorithms.AtlasArchitecture87-bitFPaccumulator.12824-bitindexregisters(90availableforgeneraluse).ExecutivestoreincludesROMforSupervisor.48-bitword24-bithalfwords10-bitopcode7bit7bitindexregisters24-bitstoreaddresscharacteroffsettopbitidshalf-wordop0:mainmemory1:executivestoreComputerScience261Copyright2005Page2of3MemoryArrangement512-byteblocks/pages.OnePageAddressRegisterperin-memory(core)page.PARcontainstheaddressofthepagecurrentlyresidentinmemory.Priorityschemeofhandlingtapeanddrum.Firstdrum(4usec).Nexttape(11usec).Restoftimegoestocorestore.Memoryisbankedinto4stacks.Motivationforsingle-levelstoreTooexpensivetomakeentirememorycorestore.Tooslowtomakeentirememorydrum.Desire:performanceofcoreatcostofdrum.Implementationofsingle-levelstoreFullyassociativelookuponeveryaddress(likeaTLB；howlargeistheirlookup?32entries；whywouldntthatworktoday).IfaddressfoundinaPAR,thenthedataisreturned.IfnoPARmatch,generateinterrupt.Keeptrackofdrumpositionintermsofblock.(diskanalogy?)UseaWAFLalgorithmtoassignblockstodrum.(keepdirectoryinmemory).BlockaddressgoesinPARuntildrumiscorrectlypositionedtopreventtransfertowrongblock.ComputerScience261Copyright2005Page3of3LearningprogramFirstuseof“use”bits.Oneusebitperpage.Canperformtransfers(memorytodrum；drumtomemory)ineitherorderifyouleaveroomonbothmedia.Lock-outbitpreventsprogramsfromaccessingblocksthatarebeingtransferred.Pagereplacement:usepasttopredictfuture.Periodicallyreadallusebitsandstorethem；resetusebitsto0.(periodically=onceevery1024instructions；whynotrealtime?thismakesitindependentofworkload)CalculatetandT,lengthsofthelasttwointervalsofinactivity.Applyfollowingalgorithm:IftisT+1,useit(implicationisthatthepageisbeingusedlessfrequentlythaninthepast).PickpagewiththemaximumT-tsuchthatt!=0(heretheassumptionisthatthememorywillhavesimilarlengthidlestimes,sowearepickingthepagethathasthelargestamountofitsidletimeyettogo).PickmaximumT(alltmustbe0)(principlehereisthateverythingisbusyandwellpickapagesuchthatwepromisewewontevictitagainifitwasamistake).Forallblocksondrum,calculatetauwhichisthetimeoflastuse.Whenmovingpagefromdrumtomemory,setTtobeidletimesincelastuse(currenttimetau)；tgetssetto0.ArgumentswhyAtlasprovidesflexibilityCanspreadthingsoutintheaddressspacetoallowforgrowth.Pro