上一篇博文介绍了2Q算法在实现到
PostgreSQL-8.0.22版本时设计的一些结构体以及相应的宏定义，下面继续介绍实现算法主体的代码段。
BufferDesc * StrategyBufferLookup(BufferTag *tagPtr, bool
recheck,int *cdb_found_index)
这个函数用来在缓存目录中查询一个请求的页，这种查询只是在T1或者T2列表中命中的情况下才会返回有效的缓冲区索引（因为B1列表中存放的只是缓冲区页的历史记录，真正的数据已经不在内存了）。如果没找到，cdb_found_index的值就为-1。
*cdb_found_index = BufTableLookup(tagPtr);
因为所有的缓冲区数据都是哈希表来统一管理的，因此这里调用函数BufTableLookup（）对哈希表进行查找。此时，如果*cdb_found_index为-1就说明我们要找到的缓冲区页不在缓冲区中，函数直接返回NULL退出。如果*cdb_found_index的值不为-1，我们就根据它的值获取相应的BufferStrategyCDB进行后续的处理。
cdb = &StrategyCDB[*cdb_found_index];
if (cdb->list == STRAT_LIST_T2)
if
(!strategy_hint_vacuum)
STRAT_LIST_REMOVE(cdb);
STRAT_MRU_INSERT(cdb, STRAT_LIST_T2);
return
&BufferDescriptors[cdb->buf_id];
如果这是一个T2列表上的命中，也就是说请求的这个页是一个频繁使用的页，我们就将这个BufferStrategyCDB移动到T2的MRU端（因为每个列表自身也是通过LRU策略来进行管理的）。如果当前的操作是VACUUM的话，这个BufferStrategyCDB就无需移动了，因为VACUUM是系统自身的操作，所以应该排除其对系统缓冲区策略的影响。
if (cdb->list == STRAT_LIST_T1)
if
(!strategy_hint_vacuum)//如果不是VACUUM事务的话，
if
(!cdb->t1_vacuum
&&//并且这个CDB是被另外一个事务读进T1列表的，而且这个所谓的另外一个事务也不是VACUUM的话，我们就
!TransactionIdEquals(cdb->t1_xid,
GetTopTransactionId()))//把这个CDB添加到T2列表的MRU端。
STRAT_LIST_REMOVE(cdb);
STRAT_MRU_INSERT(cdb, STRAT_LIST_T2);
else//否则只是将这个CDB添加到T1列表的MRU端。
STRAT_LIST_REMOVE(cdb);
STRAT_MRU_INSERT(cdb, STRAT_LIST_T1);
if
(cdb->t1_vacuum)
cdb->t1_xid = GetTopTransactionId();
cdb->t1_vacuum = false;
}
return
&BufferDescriptors[cdb->buf_id];
如果是T1列表上的一个命中，那么如果当前事务是一个VACUUM操作的话就不对T1列表进行处理。否则分为两种情况处理：
1）上一次对这个BufferStrategyCDB进行操作的不是VACUUM，而且这一次对这个BufferStrategyCDB进行操作的事务与上一次的事务不是同一个事务的话，我们将这个BufferStrategyCDB移动到T2列表的MRU端，即将这个BufferStrategyCDB从不频繁的缓冲区块列表中删除移动到频繁使用的缓冲区列表中。
2）不满足以上情况的话就将这个BufferStrategyCDB移动到T1列表的MRU端（即LRU策略）。
BufferDesc *StrategyGetBuffer(int *cdb_replace_index)
这个函数就是用来在查询请求页未果的情况下获得一个可用的缓冲区块候选。首先我们需要判断是否还有空闲的缓冲区可用，所以如果StrategyControl->listFreeBuffers
>=
0的话我们直接从维护的空闲缓冲区中直接获取一个空闲页就可以了，但如果没有空闲的话我们就必须从T1或者T2列表中选择一个进行替换了。此时，根据2Q算法的规则我们就要分为两种情况进行处理：
if (T1_LENGTH >=
T1_TARGET)//如果T1列表的当前长度已经大于等于目标长度的话
cdb_id =
StrategyControl->listHead[STRAT_LIST_T1];//获得T1列表的头部，然后依次遍历。
while
(cdb_id >= 0)
buf =
&BufferDescriptors[StrategyCDB[cdb_id].buf_id];//获取相应的缓冲区描述器，看它是不是被钉住的。
if
(buf->refcount == 0)//如果不是，我们就返回这个缓冲区。
*cdb_replace_index = cdb_id;
Assert(StrategyCDB[cdb_id].list == STRAT_LIST_T1);
return
buf;
cdb_id =
StrategyCDB[cdb_id].next;
cdb_id =
StrategyControl->listHead[STRAT_LIST_T2];
while
(cdb_id >= 0)
buf =
&BufferDescriptors[StrategyCDB[cdb_id].buf_id];
if
(buf->refcount == 0)
*cdb_replace_index = cdb_id;
Assert(StrategyCDB[cdb_id].list == STRAT_LIST_T2);
return
buf;
cdb_id =
StrategyCDB[cdb_id].next;
elog(ERROR,
"no unpinned buffers available");
}
如果T1_LENGTH>=T1_TARGET，也就是T1列表的当前长度已经超过了我们设定的长度了，这时我们遍历整个T1列表以获得一个未被钉住的缓冲区。只要遇到一个unpinned的缓冲区，我们直接返回就行了。T1中没找到的话，我们采用相同方式搜索T2，如果还找不到的话，报错！
else
cdb_id =
StrategyControl->listHead[STRAT_LIST_T2];
while
(cdb_id >= 0)
buf =
&BufferDescriptors[StrategyCDB[cdb_id].buf_id];
if
(buf->refcount == 0)
*cdb_replace_index = cdb_id;
Assert(StrategyCDB[cdb_id].list == STRAT_LIST_T2);
return
buf;
cdb_id =
StrategyCDB[cdb_id].next;
cdb_id =
StrategyControl->listHead[STRAT_LIST_T1];
while
(cdb_id >= 0)
buf =
&BufferDescriptors[StrategyCDB[cdb_id].buf_id];
if
(buf->refcount == 0)
*cdb_replace_index = cdb_id;
Assert(StrategyCDB[cdb_id].list == STRAT_LIST_T1);
return
buf;
cdb_id =
StrategyCDB[cdb_id].next;
elog(ERROR,
"no unpinned buffers available");
}
如果T1_LENGTH
<T1_TARGET的话我们先查找T2列表然后再查找T1，都没有的话报错。
