CA project 思路笔记
看Project description里给的Dual-versioned transactional memory的一些记录
关于access set
情况分析
假设当前A是readable copy,B是writable copy,某一个位置可能出现的一些情况:
- 小明读,成功,加入set
- 张三读,成功,加入set
- 小明写,发现张三也在set,失败 只要set里有别人,就不能写了
- 张三写,发现小明已经在set,失败 只要set里有别人,就不能写了
- 小明写,set里只有自己,成功
- 小明读,发现已经被写过了,自己在set里,成功,读B
- 张三读,发现已经被写过了,自己不在set里,失败
- 张三读,成功,加入set
什么时候可以加入?
- 读成功的时候
什么时候可以读?- 没人写过,随便读,读A
- 自己写过,可以读,读B 如果是别人写的,自己不可能在set里,不能读
- 写成功的时候
什么时候可以写?- 没人写过,且set里没别人 只可能有一个人是通过写加入set的
- 自己写过
从而保证:
- 只可能有一个人写
- 写过的地方只有写的人能读
- 没写过的地方都可以读
set可以只记第一个
set里可以只记录第一个加入set的人,因为:
- 如果第一个加入set是通过写加入的
- 后面可以通过set判断自己写过,可以继续读写
- 其他人发现写过,且不是自己写的,读写都不可以
- 如果第一个加入set是通过读加入的,
- 别人不能写,因为虽然没人写过,但set里已经有人了
- 别人可以读
- 自己可以写,自己写过之后,别人也不可以读了
这个第一个加入set的,可以视为所有者
🧐project description里面说不要implement an actual set,那么按这个逻辑,只存一个值应该就足够了
结论
也就是说,一个位置是否可以读写有以下几种状态:
且1状态中,如果没有其他人读过,占有者可写。如果有人读过,则不可写了。
以上都是针对读写事务,只读事务可以直接读,不影响
其它问题
Q:可能有写成功的,但后续操作失败,如何处理?
A:这样的TX不会到commit(),而只有在commit()中可以更改valid copy,因此下一轮中有效的仍是旧的值
关于batcher
什么时候调?
1. 事务开始,调enter() -> 即在tm_begin()中
2. 最后一个操作结束时,调leave() -> 即在tm_end()中
情况分析
- 初始时,remaining=0
- 第一个人enter(),remaining变成1
- 后面的人enter(),都被挂到blocked
- 第一个人leave(),remaining变成0
- counter+1 相当于进入下一轮
- remaining重设为blocked的长度
- 叫醒所有blocked里的线程
- 清空blocked
- 此时上一轮中被blocked的线程,在这一轮中一起开始工作。当有新线程调enter(),又会被挂到blocked里,等待下一轮
遗留问题
Q:为什么commit()中交换valid copy要推迟到两轮交替的间隙进行?
A:保证atomicity
Q:get_epoch()什么时候用到?是干什么用的?
A:优化的时候用
关于tx_t
一个事务需要记录的东西:
- boolean 是否成功 如果已经失败了,后面读写的时候可以直接返回
- boolean 是否只读 读的时候可以直接读