资源描述：
《pLRU替换策略的建议实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、LRUreplacementpolicyLeastRecentlyUsed(LRU)replacementpolicyisusedreplacethecachelineorpagethatisleastrecentlyused.ForBlock/LinereplacementinAssociativeCachesSincecachemanagementispurelydoneinhardware,implementingthisalgorithmcanbeexpensiveintermsofbitne
2、ededformaintaininghistoryofreferences.ThepseudoLRUversionisimplementedusingbinarysearchapproach.Examplefour-waysetassociativerequiresthreebitstokeeptrackofmostrecentlyusedline.Inorderunderstandthediagrambelowrefertofollowingdefinition:•eachbitrepresents
3、onebranchpointinabinarydecisiontree•let1representthattheleftsidehasbeenreferencedmorerecentlythantherightside,and0vice-versaareall4linesvalid?/yesno,useaninvalidline
4、
5、
6、bit_0==0?state
7、replacerefto
8、nextstate/------+---------------+-----------yn00x
9、line_
10、0line_0
11、11_/ 1x
12、line_1line_1
13、10_bit_1==0?bit_2==0?1x0
14、line_2line_2
15、0_1//1x1
16、line_3line_3
17、0_0ynyn//('x'means('_'meansunchanged)line_0line_1line_2line_3don'tcare)ForPageReplacementinVirtualMemoryAperfectimplementationofLRUrequiresatimestamponeachrefe
18、rence,andtheOSneedstokeepalistofpagesorderedbythetimestamp.However,thisimplementationistooexpensiveconsideringthefrequencyofmemoryreferences.ThecommonpracticeistoapproximatetheLRUbehavior.Onesuchapproximationisdoneusingclockalgorithm.ClockAlgorithmTheid
19、eaofapproximatingtheLRUreplacementpolicyistoreplaceanoldpage,nottheoldestpage.Theclockalgorithmarrangesphysicalpagesinacircle,withaclockhand.Ausebitisusedforeachphysicalpage.Theusebitissetto1oneachreference.Iftheusebitisnotset,itmeansthatthepagehasnotbe
20、enreferencedforsometime.00101010Onpagefault,theclockhandstartstosweepclock-wise.Ifitencountersausebitthatissetto1,itsetsitto0andmoveson.Iftheusebitis0,thepageischosenforreplacement.Intheworstcaseallusebitsmightbesetandthepointercyclesthroughalltheframes
21、,givingeachpageasecondchance.Aslowmovinghandmeansthatpagesareeitherfoundquickly,ortherearefewpagefaults.Aquickmovinghandmeanslotsofpagefaults,orlotsofuse-bitsets.Onesimplewaytoviewtheclockingalgorithmisthatofacrudepartitioningofp
