0%

并发程序设计思路

实验目的

设计并实现用于列车售票的可线性化并发数据结构。

实验说明

给定Ticket类:

1
2
3
4
5
6
7
8
9
class Ticket {
long tid; // 车票编号
String passenger; // 乘客名字
int route; // 列车车次
int coach; // 车厢号
int seat; // 座位号
int departure; // 出发站编号
int arrival; // 到达站编号
}

给定TicketingSystem接口:

1
2
3
4
5
6
7
8
public interface TicketingSystem {
// 买票,即乘客passenger购买route车次从departure站到arrival站的车票一张。若购买成功,返回有效的Ticket对象;若失败(无余票),则返回null
Ticket buyTicket(String passenger, int route, int departure, int arrival);
// 查询余票,即查询route车次从departure站到arrival站的余票数
int inquiry(int route, int departure, int arrival);
// 退票,对有效的Ticket对象返回true,对无效的Ticket返回false
boolean refundTicket(Ticket ticket);
}

给定TicketingDS类的构造器接口:

1
TicketingDS(routenum, coachnum, seatnum, stationnum, threadnum)

其中:route是车次总数(缺省为5),coachnum是列车车厢数目(缺省为8),seatnum是每节车厢的座位数(缺省为100),stationnum是每个车次经停站数量(缺省为10,含始发站和终点站),threadnum是并发购票的线程数(缺省为16)。

说明:

为简单起见,假设每个车次的coachnum、seatnum和stationnum都相同。车票涉及的各项参数均从1开始计数,例如车厢从1到8编号,车站从1到10编号等。

系统中同时存在threadnum个线程(缺省为16),每个线程是一个票务代理,按照60%查询余票,30%购票和10%退票的比率反复调用TicketingDS类的三种方法若干次(缺省为每个线程10000次)。按照线程数为4、8、16、32、64个的情况,分别给出每种方法调用的平均执行时间,同时计算系统的总吞吐率(单位时间内完成的方法调用总数)。

正确性要求

  • 每张车票都有一个唯一的你编号tid,不能重复。
  • 每一个tid的车票只能出售一次。退票后,原车票的tid作废。
  • 每个区段有余票时,系统必须满足该区段的购票请求。
  • 车票不能超卖,系统不能卖无座车票。
  • 查询结果允许不精确,但是在某个车次查票过程中没有其他购票和退票的“静止”状态下,该车次查询余票的结果必须准确。

设计思路

设计思路按照并发程序的基本设计思路来逐步实现。

设计并发程序的基本思路分别是粗粒度锁细粒度锁乐观锁无锁(lock-free)四个阶段。这四个阶段的难度也逐步递增,基本上来说,达到乐观锁的性能就已经不错了。

特别感谢王鹿鸣同学提供的部分优化思路。

粗粒度锁(Coarse-lock)

主要数据结构

1
2
3
4
5
6
7
public class Train {
public boolean[][] coachs; // 表示车座状态
public int seatNum; // 表示列车座位的总数
public int coachNum; // 表示车厢数
public int stationNum; // 表示车站数目
private ReentrantLock lock; // 列车锁,可重入锁
}

说明:用一个二维数组表示列车每个座位以及座位在每站之间的使用情况。coachs[i][j] == false表示火车的第i个座位在第j到j+1站之间,没有卖出。

思路

由于列车之间没有相关性,因此,可以给每个火车一把锁。
当购票和查询时,先获得该列车的锁,然后再遍历数组,修改某个座位的状态,最后释放锁。
由于退票不需要遍历数组,但是,依然要先获得锁,再修改座位的状态,最后释放锁。

需要注意的是,在修改座位状态时,一定要确认,修改前的状态是否符合你的预期,这样才能保证程序的正确性;若不符合,应返回false。如果没有验证座位的状态,会出现车票超售或者退票失败的情况。

细粒度锁(Fine-lock)

主要数据结构

1
2
3
4
5
6
7
public class Train {
public boolean[][] coachs;
public int seatNum;
public int coachNum;
public int stationNum;
private ReentrantLock[] locks;
}

与粗粒度锁相比,增加了锁的数量,每个座位有自己的一把锁。

思路

将锁进一步细化,给火车的每一个座位设置一把锁。
当遍历coachs数组时,要先获得该座位的锁,然后再去访问该座位的内容。
由于使用的是数组存储,因此不需要交叉手这样的方式加锁。

与粗粒度锁一样,在修改状态前,也要检查座位的状态是否符合预期。

乐观锁(Optimistic-lock)

主要数据结构

乐观锁的数据结构与细粒度锁一致。

思路

乐观锁认为,在对共享变量操作时,乐观的认为,读操作与写操作同时发生的概率非常小,因此,在读取变量时不需要加锁。
因此,乐观锁的退票与细粒度锁一样,不需要修改。而在查询操作中,完全不加锁,直接遍历一遍。

在购票过程中,在遍历数组时,不需要获得锁,只有在找到合适的、符合要求的未出售的座位时,才尝试获得锁。
获得锁后,一定要再次确认座位的状态是否符合预期。因为,在加锁过程中原本符合预期的状态,可能被其他线程修改了。因此要再次确认

改进思路

由于座位在每个站的状态使用boolean数组表示的,因此,可以尝试改用BitSet来表示。

无锁(Lock-free)

主要数据结构

1
2
3
4
5
6
public class Train {
public AtomicBitSet[] coachs;
public int seatNum;
public int coachNum;
public int stationNum;
}

思路

由乐观锁的改进思路演化而来,将座位设置成原子对象(Atomic),在修改车座状态时,通过CAS(CompareAndSet)方法操作。

由于车站数量不会过多,即stationnum < 64,所以,可以使用一个Long代替BitSet。
通过自己编写AtomicBitSet,减轻额外负担,可以提高性能。

改进思路

为了防止伪共享,可以在AtomicBitSet后面添加padding,使得一个Cache Line中只有一个AtomicLong对象,降低Cache的乒乓效应。

对已售车票的保存

  • ConcurrentLinkedDeque链表存储已售车票。但是发现在无锁结构下,该链表成为瓶颈。

  • ConcurrentHashMap存储已售车票,由于Hash表结构非常适合并发进程,因此,性能得到提升。
    PS: ConcurrentHashMap的contains(key)方法的效率远高于containsValue(value)方法。

实验代码

代码地址:https://gitee.com/873314461/ticketing-system

正确性分析

车票编号tid

车票的id使用一个AtomicInteger实现,保证了多个线程同时调用getAndIncrement()时,tid不会重复。

买票的正确性

在买票时,遍历车座,比较每一个座位是否符合购票条件,若符合条件,则锁定座位,并出票;否则返回null。

  • 粗粒度锁:保证每列火车只有一个线程在买票退票或者查询,因此,不会出现超售或者有座位但不出票的情况。
  • 细粒度锁:保证每个座位只有一个线程在买票退票或者查询,每个座位的状态在某个时刻是唯一的,保证正确性。
  • 乐观锁:保证每个座位只有一个线程在买票或者退票,由于读操作不会修改座位状态,并且,加锁后会再次确认状态,因此,在修改时,每个座位的状态是确定的,从而保证正确性。
  • 无锁:通过CAS方式,保证每个座位状态修改时,都是符合期望的,从而保证正确性。

查询车票的静态一致性

在车票查询过程中,只需要保证静态一致性即可。

静态一致性要求:由一系列静止状态分隔开的方法调用应呈现出与按照它们的实时调用次序相同的执行效果。

因此只要保证处于静止状态时,统计的车票数是准确的即可。因此,可以直接遍历数组,判断每一个座位的状态即可保证静态一致性。

性能分析

测试环境

使用老师提供的服务器:80核、160线程、256GB内存,单核1.0GHz,jdk 1.7。

共有5个车次,每个车次10个站点(包括始发站和终点站),每趟列车8个车厢,每节车厢100个座位。

买票、退票和查询的比例为:30%、10%和60%。

方法调用总次数为:线程数(threadnum) * 1000000。

结论

整体来看,无锁(Lock-Free) > 乐观锁(Optimistic-Lock) > 粗粒度锁(Coarse-Lock) > 细粒度锁(Fine-Lock)。
吞吐量如图所示:

在通常情况下,细粒度锁的吞吐量效果应该优于粗粒度锁的,但是因为本题目数据结构的特殊性(数组),使得粗粒度锁的效果优于细粒度锁。

这种现象与链表相似,由于在遍历数组时,每一步都要加锁,会阻塞后面的线程,无法超车,所有线程排队遍历数组,导致效率降低;又因为加锁的额外开销,导致性能低于粗粒度锁。

对于买票、退票和查询的时间对比如下:

我们发现,对于粗粒度锁和细粒度锁(退票方法除外)来说,方法调用的耗时基本上与线程数成线性关系。

粗粒度锁

ThreadNum Total Execution Time(ms) Throughput Rate(kop/s) Query AVE Time(ns) Buy AVE Time(ns) Refund AVE Time(ns)
1 6469 155 7388 4965 767
2 9925 202 10964 8434 4087
4 28808 139 30037 27598 15647
8 47171 170 48256 46116 34296
16 86127 186 86554 85520 73857
32 147005 218 146173 147348 137933
64 353209 181 350689 355260 348310

细粒度锁

ThreadNum Total Execution Time(ms) Throughput Rate(kop/s) Query AVE Time(ns) Buy AVE Time(ns) Refund AVE Time(ns)
1 17963 56 21619 14618 953
2 25675 78 31244 21151 1412
4 43890 91 52795 36645 2318
8 71095 113 85635 60442 2811
16 99502 161 119038 85477 4217
32 197168 162 229679 178344 10098
64 587544 109 686789 553489 17677

乐观锁

ThreadNum Total Execution Time(ms) Throughput Rate(kop/s) Query AVE Time(ns) Buy AVE Time(ns) Refund AVE Time(ns)
1 5862 171 6603 4459 861
2 6045 331 6718 4929 1501
4 6219 643 6875 5251 1897
8 6506 1230 6929 5368 3070
16 7942 2015 7928 6699 5125
32 11720 2730 9865 9476 8218
64 22591 2833 15138 15422 13319

无锁

ThreadNum Total Execution Time(ms) Throughput Rate(kop/s) Query AVE Time(ns) Buy AVE Time(ns) Refund AVE Time(ns)
1 3250 308 3436 2039 774
2 3230 619 3518 2247 934
4 3582 1117 3822 2619 1180
8 3590 2228 3714 2468 1010
16 5407 2959 5038 3883 1483
32 10566 3029 6906 5979 3585
64 18777 3408 11817 10041 5318

其他分析

结论

在买票和退票中,都是Linearizability、Lock-Free的。但是在LockFree实现中的买票和退票方法,因为使用了CAS操作,可能存在某个倒霉的线程,每次CAS操作都被别的打断,因此不是Starvation-Free和Wait-Free。

在查票方法中,只有粗粒度锁的实现中是Linearizability,其他的方法中,都只符合静态一致性。
但是,查询方法是可以达到线性化的,只需要在每次查询前,对数组做快照,就可以实现线性化的查询方法。
该方法会导致查询耗时和内存急剧增长,在没有严格要求查询满足线性化时,尽量不要使用这种方法。

买票

Lock Method Linearizability DeadLock-Free Starvation-Free Lock-Free Wait-Free
CoarseLock Yes Yes Yes Yes Yes
FineLock Yes Yes Yes Yes Yes
OptimisticLock with BitSet Yes Yes Yes Yes Yes
OptimisticLock without BitSet Yes Yes Yes Yes Yes
LockFree with AtomicBitSet Yes Yes No Yes No
LockFree with AtomicLong Yes Yes No Yes No

退票

Lock Method Linearizability DeadLock-Free Starvation-Free Lock-Free Wait-Free
CoarseLock Yes Yes Yes Yes Yes
FineLock Yes Yes Yes Yes Yes
OptimisticLock with BitSet Yes Yes Yes Yes Yes
OptimisticLock without BitSet Yes Yes Yes Yes Yes
LockFree with AtomicBitSet Yes Yes No Yes No
LockFree with AtomicLong Yes Yes No Yes No

查询

Lock Method Linearizability DeadLock-Free Starvation-Free Lock-Free Wait-Free
CoarseLock Yes Yes Yes Yes Yes
FineLock No Yes Yes Yes Yes
OptimisticLock with BitSet No Yes Yes Yes Yes
OptimisticLock without BitSet No Yes Yes Yes Yes
LockFree with AtomicBitSet No Yes Yes Yes Yes
LockFree with AtomicLong No Yes Yes Yes Yes

修改记录

2017.12.20 增加改进思路,提高对Cache Line的亲和性,并降低函数调用层次。
2018.01.05 增加正确性分析和性能分析。