选择替换缓存行的方法及其装置与流程

1.本技术涉及计算机技术领域，特别是涉及一种选择替换缓存行的方法和选择替换缓存行的装置。


背景技术：

2.良好的cache设计，既可以大大提高访问存储器的速度，也可以显著减小存储带宽的压力。cache结构使用哪种替换算法，会极大的影响cache的命中性能。
3.目前的cache缓存系统中，常用的cache替换算法有fifo(first in first out)、lru(least recently used)、random和plru(pseudo lru)。其中，fifo和random算法硬件实现简单，但是性能不佳，而lru算法总是能找到最老使用的cache line进行替换，性能最佳，但硬件设计复杂，消耗大量的硬件资源，同时时序不易收敛。而plru算法相较于lru算法，可以使用较少硬件资源，达到比较不错的性能。
4.然而，plru使用二叉树结构存储cache line(缓存行)的历史访问信息，但是如果替换状态二叉树指向的缓存行还没有被释放出来，则可能导致新的缓存行被选择替换，影响cache性能。


技术实现要素：

5.基于此，有必要针对上述技术问题，提供一种能够避免较新的缓存行被选择，提高cache性能的选择替换缓存行的方法和选择替换缓存行的装置。
6.第一方面，本技术提供了一种选择替换缓存行的方法。所述方法包括：
7.查看阻塞缓存系统对应的使用状态二叉树的根节点的状态；
8.若所述使用状态二叉树的根节点的状态为第一状态，则将所述使用状态二叉树的根节点作为所述使用状态二叉树的当前母节点；
9.若所述使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至所述阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点；
10.若所述阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为所述阻塞状态二叉树的新的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为所述阻塞状态二叉树的新的当前母节点；将所述阻塞状态二叉树的新的当前母节点映射回所述使用状态二叉树的相应的当前母节点；
11.重复所述使用状态二叉树与所述阻塞状态二叉树选取当前母节点的步骤，直至所述使用状态二叉树的当前母节点没有子节点，得到所述阻塞缓存系统中将要替换的缓存
行。
12.在其中一个实施例中，所述查看阻塞缓存系统对应的使用状态二叉树的根节点的状态之后，所述方法还包括：若所述使用状态二叉树的根节点的状态为第二状态，则判断所述阻塞缓存系统中没有可被替换的缓存行，继续查看所述使用状态二叉树的根节点的状态。
13.在其中一个实施例中，所述使用状态二叉树中节点的状态根据所述阻塞缓存系统中缓存行的可被替换状态确定。
14.在其中一个实施例中，所述阻塞状态二叉树中节点的状态根据所述阻塞缓存系统对应的替换状态二叉树中节点的状态及所述阻塞缓存系统中缓存行的可被替换状态确定。
15.在其中一个实施例中，所述方法还包括：所述阻塞缓存系统中将要替换的缓存行被选择后，更新所述使用状态二叉树及所述阻塞状态二叉树中节点的状态。
16.第二方面，本技术还提供了一种选择替换缓存行的装置。所述装置包括：
17.状态查看模块，用于查看阻塞缓存系统对应的使用状态二叉树的根节点的状态；
18.第一节点处理模块，用于若所述使用状态二叉树的根节点的状态为第一状态，则将所述使用状态二叉树的根节点作为所述使用状态二叉树的当前母节点；
19.第二节点处理模块，用于若所述使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至所述阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点；
20.第三节点处理模块，用于若所述阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为所述阻塞状态二叉树的新的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为所述阻塞状态二叉树的新的当前母节点；将所述阻塞状态二叉树的新的当前母节点映射回所述使用状态二叉树的相应的当前母节点；
21.缓存行得到模块，用于重复所述使用状态二叉树与所述阻塞状态二叉树选取当前母节点的步骤，直至所述使用状态二叉树的当前母节点没有子节点，得到所述阻塞缓存系统中将要替换的缓存行。
22.在其中一个实施例中，所述状态查看模块，还用于若所述使用状态二叉树的根节点的状态为第二状态，则判断所述阻塞缓存系统中没有可被替换的缓存行，继续查看所述使用状态二叉树的根节点的状态。
23.在其中一个实施例中，所述使用状态二叉树中节点的状态根据所述阻塞缓存系统中缓存行的可被替换状态确定。
24.在其中一个实施例中，所述阻塞状态二叉树中节点的状态根据所述阻塞缓存系统对应的替换状态二叉树中节点的状态及所述阻塞缓存系统中缓存行的可被替换状态确定。
25.在其中一个实施例中，还包括：状态更新模块，用于所述阻塞缓存系统中将要替换的缓存行被选择后，更新所述使用状态二叉树及所述阻塞状态二叉树中节点的状态。
26.上述选择替换缓存行的方法及其装置，通过添加阻塞状态二叉树代替替换状态二
叉树并根据该阻塞状态二叉树及使用状态二叉树选择将要替换的缓存行，以较小的代价，在阻塞缓存中，能更加准确地找出可被替换的缓存行中最老的缓存行作为即将被替换的缓存行，更加符合存储器访问的时间和空间的连续性，提高缓存系统的命中率。
附图说明
27.图1为一示例中替换状态二叉树示意图；
28.图2为一示例中使用状态二叉树示意图；
29.图3为一个实施例中阻塞状态二叉树示意图；
30.图4为一个实施例中选择替换缓存行的方法的流程示意图；
31.图5为一个实施例中选择替换缓存行的方法的状态跳转示意图
32.图6为一实例中替换状态二叉树的状态示意图；
33.图7为一实例中使用状态二叉树的状态示意图；
34.图8为一实例中阻塞状态二叉树的状态示意图；
35.图9为一个实施例中选择替换缓存行的装置的结构框图。
具体实施方式
36.为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
37.在基于阻塞缓存(blocking cache)的缓存系统中，传统方法是由替换状态二叉树和使用状态二叉树共同作用，选出即将被替换的缓存行(cache line)，这种方法很可能选择出比较新的缓存行来被替换掉，性能降低。而本技术提供的选择替换缓存行的方法基于新增阻塞状态二叉树及使用状态二叉树共同挑选缓存行，能够缓解上述问题，提高cache性能。
38.在现有的阻塞缓存系统中，使用替换状态二叉树和使用状态二叉树来确定即将被替换的缓存行(cache line)。本文如下部分将以8-way的cache line进行说明，如图1所示，使用7个节点状态位s[1～7]用于记录这些缓存行(cache line)的历史访问信息，为了方便描述，下文中将替换状态二叉树记为s树。其中，如果所有的缓存行都是可用的，则完全由s树指定将要替换的缓存行，其指定将要替换的缓存行的规则如下表1所示，以选择way0为例，当根节点s1为0时，则选择图1所示的替换状态二叉树的左半侧，然后判断节点s2，忽略节点s3的状态，若节点s2为0时，则选择节点s4进行判断，若节点s4为0时，则选择way0作为将要替换的缓存行进行替换。
[0039][0040]
表1
[0041]
选择合适的cache line或者cache hit后，需要更新s树的s[1～7]节点信息，其更新规则如下表2所示，仍然以way0被replace/hit为例，图1所示的替换状态二叉树中的s1、s2和s4节点的状态改变为1，其他节点保持不变。
[0042]
[0043][0044]
表2
[0045]
在阻塞缓存系统中，当缓存行仍在使用未被释放，此时该缓存行会被锁住，不允许被替换，则这些被锁住的缓存行不能参与替换选择，因此需要一套使用状态二叉树进行筛选，使用状态二叉树的结构如图2所示，为了方便描述，下文中称使用状态二叉树为r树。其中，r树的level3中各节点的状态信息由各缓存行的usable mask得到，以节点r4为例，若way0或者way1是可以被替换的，则节点r4的状态为1，同理节点r5、r6和r7分别由各自对应的缓存行cache line的可被替换状态所决定，同理level2中各节点的状态信息由level3中各节点的状态信息得到，下表3示出了r树各节点的生成/更新规则。
[0046][0047]
[0048]
表3
[0049]
在阻塞缓存系统中，plru使用的替换方法包括如下步骤：
[0050]
步骤1：查看r树中的根节点r1的状态，如果根节点r1的状态为0则表明没有缓存行是可被替换的，此时缓存系统应该被block住，若根节点r1的状态为1，则以r1为母节点。
[0051]
步骤2：查看r树当前母节点的左右子节点，若左右子节点状态为10，则选择左子节点为新的母结点；若左右子节点状态为01，则选择右子节点为新的母结点；若左右子节点状态为11，则将当前r树的母节点映射到s树相应的母节点处，若s树相应的母节点状态为0，则选择左子节点为新的母节点，若s树相应的母节点状态为1，则选择右子节点为新的母节点，并映射回r树的母节点。
[0052]
步骤3：重复步骤2直到r树的母节点没有子节点，则选出了需要被替换的缓存行。
[0053]
而如上所述的传统方法中，存在一个主要问题：由于每一个母节点仅关注自己下一级子节点的状态，导致选择缓存行替换时，很有可能会挑到刚替换不久的缓存行，而那些比较旧没有访问的缓存行没有被替换，这会很大程度上影响缓存系统的性能。
[0054]
为解决该技术问题，本技术提出添加阻塞状态二叉树，阻塞状态二叉树结构如图3所示，而其各节点的生成/更新规则如下表4所示，下文将阻塞状态二叉树称为b树。
[0055]
[0056][0057]
表4
[0058]
基于该阻塞状态二叉树，在一个实施例中，如图4所示，本技术提供了一种选择替换缓存行的方法，包括以下步骤：
[0059]
步骤s401，查看阻塞缓存系统对应的使用状态二叉树的根节点的状态。
[0060]
本步骤中，查看阻塞缓存系统对应的使用状态二叉树r的根节点r1的状态。在一个实施例中，在查看根节点r1的状态后，若该使用状态二叉树r的根节点r1的状态为第二状态(即r1的状态为0)，则判断阻塞缓存系统中没有可被替换的缓存行，此时表明阻塞缓存系统中没有缓存行是可以被替换的，继续查看使用状态二叉树r的根节点r1的状态。
[0061]
步骤s402，若使用状态二叉树的根节点的状态为第一状态，则将使用状态二叉树的根节点作为使用状态二叉树的当前母节点。
[0062]
本步骤中，若使用状态二叉树r的根节点r1的状态为第一状态(即r1的状态为1)，则以根节点r1为当前母节点。
[0063]
步骤s403，若使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为使用状态二叉树的新的当前母节点；若使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为使用状态二叉树的新的当前母节点；若使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点。
[0064]
本步骤为根据使用状态二叉树选取当前母节点的步骤，包括三种情况。具体的，第一种是：若使用状态二叉树r的当前母节点的左右子节点状态为第一子状态(即左右子节点状态为10)，则将该当前母节点的左子节点作为使用状态二叉树r的新的当前母节点；第二种是：若使用状态二叉树r的当前母节点的左右子节点状态为第二子状态(即左右子节点状态为01)，则将该当前母节点的右子节点作为使用状态二叉树r的新的当前母节点；第三种
是：若使用状态二叉树r的当前母节点的左右子节点状态为第三子状态(即左右子节点状态为11)，则将使用状态二叉树r的该当前母节点映射至阻塞缓存系统对应的阻塞状态二叉树b相应的当前母节点。
[0065]
步骤s404，若阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为阻塞状态二叉树的新的当前母节点；若阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为阻塞状态二叉树的新的当前母节点；将阻塞状态二叉树的新的当前母节点映射回使用状态二叉树的相应的当前母节点。
[0066]
本步骤为根据阻塞状态二叉树b选取当前母节点的步骤，包括两种情况。具体的，第一种是若阻塞状态二叉树b的当前母节点的状态为第三状态(即当前母节点的状态为0)，则将该当前母节点的左子节点作为阻塞状态二叉树b的新的当前母节点；第二种是若阻塞状态二叉树b的当前母节点的状态为第四状态(即当前母节点的状态为1)，则将该当前母节点的右子节点作为阻塞状态二叉树b的新的当前母节点。通过该两种情况的一种选取新的当前母节点后，将阻塞状态二叉树b的该新的当前母节点映射回使用状态二叉树r的相应的当前母节点处。
[0067]
步骤s405，重复使用状态二叉树与阻塞状态二叉树选取当前母节点的步骤，直至使用状态二叉树的当前母节点没有子节点，得到阻塞缓存系统中将要替换的缓存行。
[0068]
具体的，重复步骤s403和s404中使用状态二叉树与阻塞状态二叉树选取当前母节点的步骤，直至使用状态二叉树的当前母节点没有子节点，则选出了需要被替换的缓存行(cache line)。如图5示出了本技术提供的选择替换缓存行的方法的状态跳转图。
[0069]
接下来以一个实例来说明传统算法和本技术选取缓存行的差异。如图6所示为8-way的缓存系统经过第一轮访问后，s树中每个节点的状态，可以看到最老被使用的缓存行为way0，其次是way4，way2，way6，way1，way5，way3，最新被使用的缓存行为way7，此时，s树指向的是way0。如图7所示为r二叉树的状态情况，其中，way0、way3和way7还没有使用完毕，不能被替换，而其他的缓存行都可以被替换。
[0070]
基于此，使用传统算法选取缓存行的步骤如下：
[0071]
步骤1，首先从r树的r1出发，由于r2和r3的状态均为1，则根据s树s1的状态为0，选择r2节点；
[0072]
步骤2，从r树的r2出发，由于r4和r5的状态均为1，则根据s树s2的状态为0，选择r4节点；
[0073]
步骤3，从r树的r4出发，由于way0和way1中只有way1为1，则选择way1作为将要替换的缓存行。
[0074]
由此可以看出，使用传统算法找到的缓存行其实是比较新替换的缓存行，这样会比较影响性能。
[0075]
下面使用本技术提供的方法，图8示出了阻塞状态二叉树b的状态。
[0076]
本技术提供的方法选取缓存行的步骤如下：
[0077]
步骤1，首先从r树的r1出发，由于r2和r3的状态均为1，则根据b树b1的状态为1，选择r3节点；
[0078]
步骤2，从r树的r3出发，由于r6和r7的状态均为1，则根据b树b3的状态为0，选择r6节点；
[0079]
步骤3，从r树的r6出发，由于way4和way5均为1，则根据b树b6的状态为0，选择way4作为将要替换的缓存行。
[0080]
由此可以看出使用本技术提供的方法可以找到可替换的缓存行中最老的那一条缓存行。
[0081]
本技术实施例提供的上述选择替换缓存行的方法，通过添加阻塞状态二叉树代替替换状态二叉树并根据该阻塞状态二叉树及使用状态二叉树选择将要替换的缓存行，以较小的代价，在阻塞缓存中，能更加准确地找出可被替换的缓存行中最老的缓存行作为即将被替换的缓存行，更加符合存储器访问的时间和空间的连续性，提高缓存系统的命中率。
[0082]
在一个实施例中，上述使用状态二叉树中节点的状态根据阻塞缓存系统中缓存行的可被替换状态确定。具体的，使用状态二叉树r中节点的状态可根据如上表3进行确定。
[0083]
在一个实施例中，上述阻塞状态二叉树中节点的状态根据阻塞缓存系统对应的替换状态二叉树中节点的状态及阻塞缓存系统中缓存行的可被替换状态确定。具体的，阻塞状态二叉树b中节点的状态可根据如上表4进行确定。
[0084]
在一个实施例中，上述方法还包括：阻塞缓存系统中将要替换的缓存行被选择后，更新使用状态二叉树及阻塞状态二叉树中节点的状态。具体的，阻塞缓存系统中将要替换的缓存行被选择后，使用状态二叉树r及阻塞状态二叉树b中节点的状态可分别根据如上表3和4进行更新。
[0085]
整体来说，本技术可通过每条缓存行的唯一标识对进入缓存系统的请求和缓存的数据进行匹配，如果匹配的上则为hit，否则为miss。由此，首先进入缓存系统的请求进行唯一标识的匹配，如果hit，便可以直接从缓存行中取数据，否则需要向存储器发送请求，并在缓存系统中选择一条缓存行，存放存储器返回的数据；在每一次发生miss/hit或者缓存行被使用后，都会根据当前缓存行的使用状态和miss/hit情况更新的r树和s树，然后可根据r树和s树获得b树；最后在为miss的请求选取缓存行时，会通过r树和b树选择将要替换的缓存行，这使得本技术能够更加准确地找出可被替换的缓存行中最老的缓存行。可见，本技术通过添加阻塞状态二叉树代替替换状态二叉树，可以较小的代价，在阻塞缓存(blocking cache)中，能更加准确地找出可被替换的缓存行中最老的缓存行，作为即将被替换的缓存行，更加符合存储器访问的时间和空间的连续性，提高缓存系统的命中率。
[0086]
应该理解的是，虽然如上所述的各实施例所涉及的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，如上所述的各实施例所涉及的流程图中的至少一部分步骤可以包括多个步骤或者多个阶段，这些步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤中的步骤或者阶段的至少一部分轮流或者交替地执行。
[0087]
基于同样的发明构思，本技术实施例还提供了一种用于实现上述所涉及的选择替换缓存行的方法的选择替换缓存行的装置。该装置所提供的解决问题的实现方案与上述方法中所记载的实现方案相似，故下面所提供的一个或多个选择替换缓存行的装置实施例中的具体限定可以参见上文中对于选择替换缓存行的方法的限定，在此不再赘述。
[0088]
在一个实施例中，如图9所示，提供了一种选择替换缓存行的装置，包括：
[0089]
状态查看模块901，用于查看阻塞缓存系统对应的使用状态二叉树的根节点的状态；
[0090]
第一节点处理模块902，用于若所述使用状态二叉树的根节点的状态为第一状态，则将所述使用状态二叉树的根节点作为所述使用状态二叉树的当前母节点；
[0091]
第二节点处理模块903，用于若所述使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至所述阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点；
[0092]
第三节点处理模块904，用于若所述阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为所述阻塞状态二叉树的新的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为所述阻塞状态二叉树的新的当前母节点；将所述阻塞状态二叉树的新的当前母节点映射回所述使用状态二叉树的相应的当前母节点；
[0093]
缓存行得到模块905，用于重复所述使用状态二叉树与所述阻塞状态二叉树选取当前母节点的步骤，直至所述使用状态二叉树的当前母节点没有子节点，得到所述阻塞缓存系统中将要替换的缓存行。
[0094]
在一个实施例中，所述状态查看模块901，还用于若所述使用状态二叉树的根节点的状态为第二状态，则判断所述阻塞缓存系统中没有可被替换的缓存行，继续查看所述使用状态二叉树的根节点的状态。
[0095]
在一个实施例中，所述使用状态二叉树中节点的状态根据所述阻塞缓存系统中缓存行的可被替换状态确定。
[0096]
在一个实施例中，所述阻塞状态二叉树中节点的状态根据所述阻塞缓存系统对应的替换状态二叉树中节点的状态及所述阻塞缓存系统中缓存行的可被替换状态确定。
[0097]
在一个实施例中，还包括：状态更新模块，用于所述阻塞缓存系统中将要替换的缓存行被选择后，更新所述使用状态二叉树及所述阻塞状态二叉树中节点的状态。
[0098]
上述选择替换缓存行的装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。
[0099]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、数据库或其它介质的任何引用，均可包括非易失性和易失性存储器中的至少一种。非易失性存储器可包括只读存储器(read-only memory，rom)、磁带、软盘、闪存、光存储器、高密度嵌入式非易失性存储器、阻变存储器(reram)、磁变存储器(magnetoresistive randomaccess memory，mram)、铁电存储器(ferroelectric random access memory，fram)、相变存储器(phase change memory，
pcm)、石墨烯存储器等。易失性存储器可包括随机存取存储器(random access memory，ram)或外部高速缓冲存储器等。作为说明而非局限，ram可以是多种形式，比如静态随机存取存储器(static random access memory，sram)或动态随机存取存储器(dynamic random access memory，dram)等。本技术所提供的各实施例中所涉及的数据库可包括关系型数据库和非关系型数据库中至少一种。非关系型数据库可包括基于区块链的分布式数据库等，不限于此。本技术所提供的各实施例中所涉及的处理器可为通用处理器、中央处理器、图形处理器、数字信号处理器、可编程逻辑器、基于量子计算的数据处理逻辑器等，不限于此。
[0100]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0101]
以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本技术专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术的保护范围应以所附权利要求为准。

技术特征：
1.一种选择替换缓存行的方法，其特征在于，所述方法包括：查看阻塞缓存系统对应的使用状态二叉树的根节点的状态；若所述使用状态二叉树的根节点的状态为第一状态，则将所述使用状态二叉树的根节点作为所述使用状态二叉树的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至所述阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为所述阻塞状态二叉树的新的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为所述阻塞状态二叉树的新的当前母节点；将所述阻塞状态二叉树的新的当前母节点映射回所述使用状态二叉树的相应的当前母节点；重复所述使用状态二叉树与所述阻塞状态二叉树选取当前母节点的步骤，直至所述使用状态二叉树的当前母节点没有子节点，得到所述阻塞缓存系统中将要替换的缓存行。2.根据权利要求1所述的方法，其特征在于，所述查看阻塞缓存系统对应的使用状态二叉树的根节点的状态之后，所述方法还包括：若所述使用状态二叉树的根节点的状态为第二状态，则判断所述阻塞缓存系统中没有可被替换的缓存行，继续查看所述使用状态二叉树的根节点的状态。3.根据权利要求1所述的方法，其特征在于，所述使用状态二叉树中节点的状态根据所述阻塞缓存系统中缓存行的可被替换状态确定。4.根据权利要求1所述的方法，其特征在于，所述阻塞状态二叉树中节点的状态根据所述阻塞缓存系统对应的替换状态二叉树中节点的状态及所述阻塞缓存系统中缓存行的可被替换状态确定。5.根据权利要求1至4任一项所述的方法，其特征在于，所述方法还包括：所述阻塞缓存系统中将要替换的缓存行被选择后，更新所述使用状态二叉树及所述阻塞状态二叉树中节点的状态。6.一种选择替换缓存行的装置，其特征在于，所述装置包括：状态查看模块，用于查看阻塞缓存系统对应的使用状态二叉树的根节点的状态；第一节点处理模块，用于若所述使用状态二叉树的根节点的状态为第一状态，则将所述使用状态二叉树的根节点作为所述使用状态二叉树的当前母节点；第二节点处理模块，用于若所述使用状态二叉树的当前母节点的左右子节点状态为第一子状态，则将该当前母节点的左子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第二子状态，则将该当前母节点的右子节点作为所述使用状态二叉树的新的当前母节点；若所述使用状态二叉树的当前母节点的左右子节点状态为第三子状态，则将该当前母节点映射至所述阻塞缓存系统对应的阻塞状态二叉树相应的当前母节点；
第三节点处理模块，用于若所述阻塞状态二叉树的当前母节点的状态为第三状态，则将该当前母节点的左子节点作为所述阻塞状态二叉树的新的当前母节点；若所述阻塞状态二叉树的当前母节点的状态为第四状态，则将该当前母节点的右子节点作为所述阻塞状态二叉树的新的当前母节点；将所述阻塞状态二叉树的新的当前母节点映射回所述使用状态二叉树的相应的当前母节点；缓存行得到模块，用于重复所述使用状态二叉树与所述阻塞状态二叉树选取当前母节点的步骤，直至所述使用状态二叉树的当前母节点没有子节点，得到所述阻塞缓存系统中将要替换的缓存行。7.根据权利要求6所述的装置，其特征在于，所述状态查看模块，还用于若所述使用状态二叉树的根节点的状态为第二状态，则判断所述阻塞缓存系统中没有可被替换的缓存行，继续查看所述使用状态二叉树的根节点的状态。8.根据权利要求6所述的装置，其特征在于，所述使用状态二叉树中节点的状态根据所述阻塞缓存系统中缓存行的可被替换状态确定。9.根据权利要求6所述的装置，其特征在于，所述阻塞状态二叉树中节点的状态根据所述阻塞缓存系统对应的替换状态二叉树中节点的状态及所述阻塞缓存系统中缓存行的可被替换状态确定。10.根据权利要求6至9任一项所述的装置，其特征在于，还包括：状态更新模块，用于所述阻塞缓存系统中将要替换的缓存行被选择后，更新所述使用状态二叉树及所述阻塞状态二叉树中节点的状态。

技术总结
本申请涉及计算机技术领域，提供了一种选择替换缓存行的方法及其装置。本申请通过添加阻塞状态二叉树代替替换状态二叉树并根据该阻塞状态二叉树及使用状态二叉树选择将要替换的缓存行，以较小的代价，在阻塞缓存中，能更加准确地找出可被替换的缓存行中最老的缓存行作为即将被替换的缓存行，更加符合存储器访问的时间和空间的连续性，提高缓存系统的命中率。率。率。


技术研发人员：朱子文 武文杰 冯晶 余鹏程
受保护的技术使用者：格兰菲智能科技有限公司
技术研发日：2022.03.04
技术公布日：2023/9/12