CA project 思路笔记
coconutnut
 2021-11-28 14:33:12      

看Project description里给的Dual-versioned transactional memory的一些记录

关于access set

情况分析

假设当前A是readable copy，B是writable copy，某一个位置可能出现的一些情况：

  1. 小明读，成功，加入set
    1. 张三读，成功，加入set
      1. 小明写，发现张三也在set，失败 只要set里有别人，就不能写了
    2. 张三写，发现小明已经在set，失败 只要set里有别人，就不能写了
    3. 小明写，set里只有自己，成功
      1. 小明读，发现已经被写过了，自己在set里，成功，读B
      2. 张三读，发现已经被写过了，自己不在set里，失败

什么时候可以加入？

  1. 读成功的时候
    什么时候可以读？
    1. 没人写过，随便读，读A
    2. 自己写过，可以读，读B 如果是别人写的，自己不可能在set里，不能读
  2. 写成功的时候
    什么时候可以写？
    1. 没人写过，且set里没别人 只可能有一个人是通过写加入set的
    2. 自己写过

从而保证：

  1. 只可能有一个人写
  2. 写过的地方只有写的人能读
  3. 没写过的地方都可以读

set可以只记第一个

set里可以只记录第一个加入set的人，因为：

  1. 如果第一个加入set是通过写加入的
    1. 后面可以通过set判断自己写过，可以继续读写
    2. 其他人发现写过，且不是自己写的，读写都不可以
  2. 如果第一个加入set是通过读加入的，
    1. 别人不能写，因为虽然没人写过，但set里已经有人了
    2. 别人可以读
    3. 自己可以写，自己写过之后，别人也不可以读了
      这个第一个加入set的，可以视为所有者

🧐project description里面说不要implement an actual set，那么按这个逻辑，只存一个值应该就足够了

结论

也就是说，一个位置是否可以读写有以下几种状态：

且1状态中，如果没有其他人读过，占有者可写。如果有人读过，则不可写了。

以上都是针对读写事务，只读事务可以直接读，不影响

更新CA project 状态分析

其它问题

Q：可能有写成功的，但后续操作失败，如何处理？
A：这样的TX不会到commit()，而只有在commit()中可以更改valid copy，因此下一轮中有效的仍是旧的值

关于batcher

什么时候调？

1. 事务开始，调enter() -> 即在tm_begin()中
2. 最后一个操作结束时，调leave() -> 即在tm_end()中

情况分析

  1. 初始时，remaining=0
  2. 第一个人enter()，remaining变成1
  3. 后面的人enter()，都被挂到blocked
  4. 第一个人leave()，remaining变成0
  5. counter+1 相当于进入下一轮
    • remaining重设为blocked的长度
    • 叫醒所有blocked里的线程
    • 清空blocked
  6. 此时上一轮中被blocked的线程，在这一轮中一起开始工作。当有新线程调enter()，又会被挂到blocked里，等待下一轮

遗留问题

Q：为什么commit()中交换valid copy要推迟到两轮交替的间隙进行？
A：保证atomicity

Q：get_epoch()什么时候用到？是干什么用的？
A：优化的时候用

关于tx_t

一个事务需要记录的东西：

  • boolean 是否成功 如果已经失败了，后面读写的时候可以直接返回
  • boolean 是否只读 读的时候可以直接读