对于如何得到的文件平均访问长度我就不多说了,课本中推导得到:
前两种情况,若文件的被访问概率相等或者文件长度一样,比较容易理解,也不多说
对于第三种情况,课本中只是根据一个例子来进行猜测,而且课本中也出现了一点错误;对于两种情况,排列顺序为AB或BA,第二种文件的P/L应该是
0.4/10=0.04以及0.6/6=0.1
这里给出一种数学分析方法
对于一种最佳存储顺序,不能存在i使得,P[i]/L[i] > p[i+1]/L[i+1]
证明(反证法):假设存在i使得上述条件成立,交换第i和第i+1个文件,则
1) 在新序列中访问原第i个文件,需要多访问原第i+1个文件,从而增加访问长度P[i]*L[i+1]
2) 在新序列中访问原第i+1个文件,不需访问原第i个文件,从而减少访问长度P[i+1]*L[i]
从而增加访问长度P[i]*L[i+1]-P[i+1]*L[i],又P[i]/L[i] > p[i+1]/L[i+1]成立,则P[i]*L[i+1]-P[i+1]*L[i]<0,从而存在更好的存储顺序,与最佳存储顺序矛盾
故原命题成立,从而得到课本中的结论,P[i]/L[i]的值从大到小排列即为最佳存储顺序