当计算机对虚拟存储器进行读取时,其即将读取的虚页号为下面的序列顺序: 3, 4, 2, 6, 4, 7, 1, 3, 2, 6, 3, 5, 1, 2, 3, 5 假设采用近期最少使用页面替换算法(LRU算法),主存只有4个页框且初始均为空,现求: 画出表格表示主存页框中虚页号的变化替换过程 计算在LRU算法下,主存的命中率
时间: 2023-09-17 11:11:06 浏览: 79
假设主存中有4个页框,我们可以用一个长度为4的队列来表示这4个页框,队列中存储的是主存中页框所对应的虚页号。在进行页面替换时,我们从队列的头部弹出一个元素,同时在队列的尾部插入一个元素。
下面的表格表示了主存页框中虚页号的变化替换过程:
| 读取的虚页号 | 主存页框 | 页框中的虚页号 | 替换过程 |
| --- | --- | --- | --- |
| 3 | 无 | | 3 |
| 4 | 3 | 3 | 3->4 |
| 2 | 3,4 | 3,4 | 3,4->2 |
| 6 | 3,4,2 | 3,4,2 | 3,4,2->6 |
| 4 | 3,2,6 | 3,2,6 | 3,2,6->4 |
| 7 | 3,2,6,4 | 2,6,4,7 | 2,6,4,7->3 |
| 1 | 6,4,7,3 | 6,4,7,3 | 6,4,7,3->1 |
| 3 | 4,7,3,1 | 4,7,1,3 | 4,7,1,3->3 |
| 2 | 7,1,3,2 | 7,1,3,2 | 7,1,3,2->2 |
| 6 | 1,3,2,6 | 1,3,2,6 | 1,3,2,6->6 |
| 3 | 1,2,6,3 | 1,2,6,3 | 1,2,6,3->3 |
| 5 | 2,6,3,5 | 2,6,3,5 | 2,6,3,5->5 |
| 1 | 6,3,5,1 | 6,3,5,1 | 6,3,5,1->1 |
| 2 | 3,5,1,2 | 3,5,1,2 | 3,5,1,2->2 |
| 3 | 5,1,2,3 | 5,1,2,3 | 5,1,2,3->3 |
| 5 | 1,2,3,5 | 1,2,3,5 | 1,2,3,5->5 |
在进行LRU算法的过程中,如果发现要读取的虚页号已经在主存页框中,那么就将其从队列中删除,并将其插入到队列的尾部。如果发现要读取的虚页号不在主存页框中,那么就需要进行页面替换。在这个过程中,我们总共进行了12次页面替换操作。
计算命中率的方法是:用总的读取次数减去页面替换次数,再除以总的读取次数。因此,在LRU算法下,主存的命中率为:
(16 - 12) / 16 = 0.25
即25%。