缓存替换的LRU算法，假设缓存容量是3,初始为空，则访问1,

[单选题]

缓存替换的LRU算法，假设缓存容量是3,初始为空，则访问1,2,3,3,2,1,4,3,2,1的失败次数是（）

```
8
```
```
7
```
```
6
```
```
5
```

查看正确选项

lqqqdu

LRU是指最近最少使用的被替换

1 查找失败，因为此时是空的缓存，所以放入1，剩余容量为2

2 查找失败，此时缓存中只有1，所以放入2，剩余容量为1

3 查找失败，此时缓存中只有1、2，所以放入3，剩余容量为0

3 查找成功

2 查找成功

1 查找成功

4 查找失败，因为此时缓存中只有1、2、3，没有4，所以需要替换最近最少使用的数字，即替换3，放入4，此时缓存的数字为1、2、4，剩余容量为0

3 查找失败，因为此时缓存中只有1、2、4，没有3，所以需要替换最近最少使用的数字，即替换2，放入3，此时缓存的数字为1、3、4，剩余容量为0

2 查找失败，因为此时缓存中只有1、3、4，没有2，所以需要替换最近最少使用的数字，即替换1，放入2，此时缓存的数字为2、3、4，剩余容量为0

1 查找失败，因为此时缓存中只有2、3、4，没有1，所以需要替换最近最少使用的数字，即替换4，放入1，此时缓存的数字为2、3、1，剩余容量为0

共查找失败7次

发表于 2017-12-28 21:17:31 回复(0)

沧海v一粟

发表于 2020-05-07 16:51:05 回复(0)

灰色节能_聪

如图，一开始是空，所以一开始就失败3次，存入了123，然后一个个读下去，读到数字就移到最后，如果没有匹配的数字，就把第一个数字移除，在最后插入新的数字，并且加一次失败次数

发表于 2016-03-08 16:32:41 回复(0)

小学作业多

import java.util.Scanner;

public class Main {
    
    public static final int MAX_TASK_NUM = 100; 

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            int ***Blocks = scan.nextInt();
            int[] taskPages = new int [MAX_TASK_NUM];
            int i = 0;
            int page = scan.nextInt();
            while(page != -1)    // 输入结束标志
            {
                taskPages[i++] = page;
                page = scan.nextInt();
            }
            System.out.println(LRU.calMissingPages(***Blocks, i, taskPages));
            
        }
        scan.close();
    }

}

class LRU {

    public static int  calMissingPages(int ***Blocks, int taskNum, int taskPages[])
    {
        int[] *** = new int [***Blocks];  // 缓存
        ***[0] = taskPages[0];    　　　　   // 预处理，先将第一个作业页面放入缓存
        int ***Pages = 1;            　　　　// 已缓存的页面数
        int missingNum = 1;            　　　　// 缺页次数
        boolean missingFlag;        　　　　　 // 缺页标志
        for(int i = 1; i < taskNum; i++)
        {
            missingFlag = true;
            for(int j = 0; j < ***Pages; j++)
            {
                if(***[j] == taskPages[i])   // 命中
                {
                    missingFlag = false;
                    int t = ***[j];
                    for(int k = j + 1; k < ***Pages; k++)
                        ***[k - 1] = ***[k];
                    ***[***Pages - 1] = t;
                    break;
                }
            }
            if(missingFlag)　　　　　　　　　　　　// 未命中
            {
                missingNum++;
                if(***Pages == ***Blocks)   // 缓存已满
                {
                    for(int k = 1; k < ***Pages; k++)
                        ***[k - 1] = ***[k];
                    ***[***Pages - 1] = taskPages[i];
                }
                else    // 缓存未满
                {
                    ***[***Pages] = taskPages[i];
                    ***Pages++;
                }
            }
        }
        return missingNum;
    }
}

发表于 2016-06-15 19:56:29 回复(0)