Simplified 2Q

Simplified 2Q

如果访问的数据P在Am中命中，将他放回到Am的Rear中，如果在A1命中，则将其从A1中移除，放入到Am中。

如果在A1和Am中都没有命中，则优先使用两个队列的空闲空间，将其放入A1的Rear端；如果没有剩余空间，则检查A1的Threshold，超过的话从A1的Front移除就数据，若没有超过，则从Am的Front端移除数据，新数据放入A1的Rear

Full Version2Q

2Q

Simplified 2Q的Threshold参数至关重要，这个参数过大或过小都无法合理平衡A1和Am的负载，尤其是当程序的数据模型变化时，这个值需要随着变化，这使得Cache的空间很难被合理使用，因此有了Full version 2Q来解决这个问题。

Full vision 2Q将A1分解成A1-in和A1-out两个队列，其中Kin为A1-in的阈值，Kout为A1-out的阈值。在A1-in和A1-out中不再保存数据，而是存放数据指针，这样Am可以使用所有的Slot，在一定程度上解决了适配性的问题

LRU算法都是居于Link list来实现的，数据从Front取出放回到Rear的过程是一个链表的替换过程，操作不算复杂，但是替换过程伴随着多处链表遍历，这个时间是不可忽略的。