大门|大门-CS-2016（第1组）|问题59

考虑一个具有十个物理页面框架的计算机系统。系统配备了一个访问序列a1、a2、…、a20、a1、a2、…、a20），其中每个ai编号。后进先出页面替换策略和最佳页面替换策略之间的页面错误数差异为__________

[请注意，这个问题最初是填空问题] （A） 0 （B） 1. （C） 2. （D） 3. 答复: （B） 说明： 后进先出代表后进先出 a1到a10会导致页面错误，所以a1到a10会有10个页面错误。 然后a11将替换a10（最后一个是a10），a12将替换a11，依此类推，直到a20，所以a11到a20和a20之间的10页错误将是堆栈的顶部，a9…a1将保持不变。 那么a1到a9已经存在了。因此，从a1到a9的页面错误为0。 a10将取代a20，a11将取代a10，依此类推。所以从a10到a20有11页错误。因此，总故障数为10+10+11=31。

最优的 a1到a10会导致页面错误，所以a1到a10会有10个页面错误。 然后a11将替换a10，因为在a1到a10之间，a10将稍后使用，a12将替换a11，依此类推。因此，从a11到a20和a20的10页错误将是堆栈的顶部，a9…a1将保持不变。 那么a1到a9已经存在了。因此，从a1到a9的页面错误为0。 a10将取代a1，因为它以后将不再使用，以此类推，a10到a19将有10个页面错误。 a20已经存在，所以a20没有页面错误。 总故障数10+10+10=30。 差=1 这个问题的小测验