之前的lab实现了数据库查询计划的执行，但我们都是建立在单线程的基础上。当引入了事务后，为了让多个事务能够并发执行，我们就需要一些方法实现事务间的隔离。常见的方法有：基于锁、基于时间戳、基于多版本。本次lab主要使用基于锁的并发控制实现事务间的隔离。具体来说，我们实现一个tuple级别的锁管理器lock manager，它支持对单个tuple加读锁or写锁。然后使用lock manager实现两阶段封锁协议。
TASK #1 - LOCK MANAGER
首先我们实现一个lock manager，它用于对单个tuple加锁和解锁。我们需要实现对同一个tuple的读锁和写锁，其核心数据结构是std::unordered_map<RID, LockRequestQueue> lock_table_，它用于存储当前某个tuple上的全部锁请求，包括已经授予锁的请求和正在等待锁的请求。
理论上，应该按照链表的方式管理锁请求，每个tuple都有一个链表。算法如下，这种方式可以避免锁请求被饿死。但如果采用条件变量(wait、signal)来检测请求链表，实现起来较为麻烦。
我在这里没有采用上述做法，而是直接采用操作系统里经典的读者-写者模型。当然，naive版的读写者模型会导致写者饿死，但我们结合考虑task2的 WOUND-WAIT算法，就会发现，这个死锁预防机制恰好可以消除读优先导致写者饿死的问题，具体细节留到task2详谈。
lock manager采用读写者模型，在LockManager类中设置两个变量：读锁计数器 shared_cnt 和写锁标志 exclusive_lock。其中LockShared负责处理读锁请求，其condition variable 等待条件为：当前申请锁的事务被abort（如果被abort了，就直接返回false），或者当前tuple没有加写锁。LockExclusive负责处理写锁请求，其condition variable等待条件为：当前申请锁的事务被abort，或者当前tuple没有加写锁和读锁(shared_cnt 为0)。LockUpgrade负责处理提升锁，即将已经获取shared lock的提升为exclusive lock，首先从请求队列中删除shared 锁，然后再请求exclusive锁，其中删除shared锁+请求exclusive锁之间必须是原子的（可以通过在这两个步骤外面加latch实现）。
解锁方面，解锁后，需要把request从锁请求队列中拿出来，然后修改shared_cnt和exclusive_lock的状态。最后，因为会存在一些线程阻塞在锁请求队列的等待锁上，因此需要将其唤醒。
TASK #2 - DEADLOCK PREVENTION
接着我们完成死锁预防机制。解决死锁，可以采取事先预防和事后处理的办法，事先预防就是提前避免死锁发生的条件，而事后处理则是根据锁请求建立一个请求graph，然后一旦graph中出现环，就说明发生了死锁，此时直接abort掉一个事务，破坏该环就行。
实验要求我们使用死锁预防，使用WOUND-WAIT机制避免死锁，这相当于破坏了死锁条件中的：不可剥夺。具体算法为：当前事务Ti申请的数据项被当前事务Tj持有，仅当Ti的时间戳小于Tj的时间戳时，允许Ti等待，否则Ti回滚。但是，根据lab4的test case可以发现，这个算法应该被修正为：当前事务Ti申请的数据项被当前事务Tj持有 **(或Tj正在等待该数据项)**，仅当Ti的时间戳小于Tj的时间戳时，允许Ti等待，否则Ti回滚。
在具体实现方面，我们还要考虑读写锁的相容问题，如果Ti和Tj相容（即Ti和Tj都对同一个tuple加读锁），则不需要考虑abort。
最后，还需要注意在abort一个请求后，需要将它从request队列中删除，并维护shared_cnt和exclusive_lock的状态。因为request队列以及shared_cnt和exclusive_lock的状态有两个渠道维护，其一是当阻塞中的事务发现自己被abort后，会在事务的结尾进行Unlock all locks；其二是未被阻塞的事务，它可能一直在运行中，其被DEADLOCK PREVENTION机制abort后，仍然在运行中，此时我们需要先行在DeadLockPrevection机制将其锁请求从请求队列中删掉。
此外，由于DEADLOCK PREVENTION的剥夺机制，写事务不会出现饿死的现象。
TASK #3 - CONCURRENT QUERY EXECUTION
现在我们要使用2阶段锁协议实现多事务的并发执行。事务的隔离级别如下，隔离级别从高到低，事务的并发也越来越强。
因为严格的2pl机制可以实现最高级别的事务隔离性，即serializable。但我们希望在容忍损失一定的隔离性的情况下，实现事务的高效并发，因此才会有其它隔离级别的存在。
下图是如何修改2pl协议，使得其支持不同隔离级别。
我们要做的，就是按照上述协议，在每个executor读or写一个tuple之前、后，给其加上适合的读写锁。
对于加读锁我们需要考虑，如果当前事务为read uncommitted级别，不需要读锁，因此直接abort或者抛异常。如果当前事物在这个tuple上已经有写锁or读锁了，那我们就不需要再申请。
对于加写锁我们考虑，如果当前事务在这个tuple上已经有读锁了，那我们应该直接upgrade。如果当前已经有写锁了，我们直接返回，不需要再次申请。
对于解锁，只有当隔离级别为read committed时，需要在读完tuple后立即释放读锁。其它的情况，都是在事务结束时的末尾，在transaction层面由transaction manager在对事务进行commit或abort时，统一解锁的。
实验结果
一些注意事项
在lock_table_中新插入一个{RID, RequestQueue}时，因为RequestQueue中有condition_variable变量，属于不可拷贝的变量，因此RequestQueue不可拷贝。我们不能用insert或map的中括号的方式插入新的{RID, RequestQueue}，而应该使用emplace_back。
1
lock_table_.emplace(std::piecewise_construct, std::forward_as_tuple(rid), std::forward_as_tuple());
最后附上实验结果
