并发程序设计思路

实验目的

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

实验说明

给定Ticket类：

class Ticket {
    long tid;           // 车票编号
    String passenger;   // 乘客名字
    int route;          // 列车车次
    int coach;          // 车厢号
    int seat;           // 座位号
    int departure;      // 出发站编号
    int arrival;        // 到达站编号
}

给定TicketingSystem接口：

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)

主要数据结构

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)

主要数据结构

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)

主要数据结构

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 增加正确性分析和性能分析。