Task1: Lock Manager

在这一步需要实现3种隔离级别，RU、RC、RR，需要实现总共五种锁，S、X、IS、IX、SIX。使用的并发控制协议是2PL。

需要实现四个函数：

LockTable
UnlockTable
LockRow
UnlockRow

LockTable

判断事务状态，如果事务已经是Aborted的状态，那么直接返回false，不需要为中止的事务分配锁。
判断事务是否已经持有锁了，事务在内部维护了锁集，所以可以直接用事务的成员函数去判断，如果已经拥有了当前申请的锁，那么直接返回true。
判断事务是否可以申请该锁，判断依据是事务的状态是Growing还是Shrinking，还有隔离级别等。
获取请求队列，由于请求队列是多个线程共享的数据结构，需要先调用table_lock_map_latch.lock()进行加锁保护。然后根据表的oid获取对应的请求队列，同时将请求队列加锁。注意，一定要将请求队列加锁之后再释放table_lock_map_latch。
判断是否是锁升级。如果是锁升级，那么说明请求队列中一定含有这个事务先前已经得到的锁，且这个锁的等级应该比申请的要低，否则反向升级需要中止事务。
1. 我们可以遍历请求队列去找到某个request，它的txn_id和当前的事务id相同的话，就说明找到了先前的锁请求，这个请求一定是grant的，如果不是，那么事务会一直阻塞，不可能又发出一个锁申请。
2. 检测是否同时具有多个锁升级，我们只能支持一个锁升级请求，如果队列里原先就有锁升级请求，那么同样Abort。
3. 如果检测无误，那么将这个请求插入到请求队列中，非grant的请求里最前面的位置，因为锁升级的优先级是最高的，队列按照FIFO规则处理。
如果不是锁升级请求，那么构造一个锁请求，插入到请求队列的队尾。
尝试申请资源，如果不成功，调用请求队列的条件变量进行阻塞，等待下一次唤醒时，再次尝试申请资源。
成功申请到资源，退出循环，更新事务的锁集，如果是锁升级，那么将队列的锁升级标志清空。

LockRow

与LockTable基本相同，但是最开始还需要检查是否拥有了对应的表锁，不能不申请表锁直接拿行锁。

UnlockTable

检查该事务是否已经解锁了所有该表下的行锁。
检查该事务是否持有对应的表锁。
都没问题，说明是一个合法的解锁请求，遍历请求队列找到对应的锁请求，将其删除，然后更新事务锁集，之后唤醒请求队列的条件变量，让先前阻塞的事务可以尝试申请资源。

UnlockRow

与UnlockTable基本一致。

Task2: Deadlock Detection

中心思想就是根据事务之间的资源争夺关系，建立一张waits-for图，然后在这个waits-for图中找到环路，环路意味着死锁，需要把环路中的某个节点Abort，从而打破环路。

拿到table_lock和row_lock，从而能够遍历对应的请求队列来建立waits-for图。
1. 事务A和事务B共同申请资源C，A拿到了，B阻塞。则B向A连一条边。
执行DFS去检测waits-for图中的环路。要求DFS的结果是确定的，这意味着我们搜索的方向必须得固定，从拥有最小txn_id的节点出发，每次选择邻居节点时也需要选择最小txn_id的节点。找到环路后，返回环路中拥有最大txn_id的节点作为abort对象。
1. 因此，在DFS前，需要对waits-for图中的节点进行一个排序，还要对waits-for图中的所有边进行排序。
循环调用DFS，直到找不到环路为止。图中可能存在多个环，需要一次性把所有环打破。一旦找到环，就将事务置为Abort，然后在waits-for图中删除该点对应的所有边。
最后，唤醒所有的请求队列，然后请求队列都去尝试一次获得资源。