并發資料結構與多核編程 -- 列車售票系統

一.設計思路

認真分析題目要求后，我在TicketingDS類作為代碼主體，呼叫其他個模塊：SeatSection

、RouteSection、CoachSection，分別代表車次、車廂、座位，以及Test測驗模塊，

TicketingDS.java

1.定義私有屬性

private final int routeNum;// 車次總數
private final int stationNum;// 車站總數
private ArrayList<RouteSection> routeArray;//車次串列

ArrayList是Java集合框架中的一個重要的類，它繼承于AbstractList，實作了List介面，是一個長度可變的集合，提供了增刪改查的功能，集合中允許null的存在，ArrayList類還是實作了RandomAccess介面，可以對元素進行快速訪問，實作了Serializable介面，說明ArrayList可以被序列化，還有Cloneable介面，可以被復制，和Vector不同的是，ArrayList不是執行緒安全的，

2.依次遍歷每個車次

for (int routeId = 1; routeId <= routeNum; routeId++)
     this.routeArray.add(new RouteSection(routeId, coachNum, seatNum));
	}

3.買票

使用buyTicket方法，先判斷車次和車站是否在范圍內，再呼叫RouteSection模塊里的initSeal方法，嘗試購票，并回傳(route - 1)，

4.查詢

先判斷車次和車站是否在范圍內，再呼叫RouteSection模塊里的initInquiry方法嘗試購票，并回傳(route - 1)，

5.退票

先獲取車票的車次，判斷車票和車次是否在范圍內，再呼叫RouteSection模塊里的initRefund方法嘗試購票，并回傳(route - 1)，

RouteSection.java

具體實作TicketingDS類里的三個方法，

1.先定義屬性：

	private final int routeId;//車次序號
	private final int coachNum;//車廂數目
	private ArrayList<CoachSection> coachList;//車廂串列
	private AtomicLong ticketId;//車票的票號，每個車票有唯一的票號
	private Queue<Long> queue_SoldTicket;//構造佇列

2.使用構造方法，當java類實體化時，輸入引數值，將屬性初始化，

3.使用queue_SoldTicket構造佇列，

this.queue_SoldTicket = new ConcurrentLinkedQueue<Long>();

ConcurrentLinkedQueue是一個基于鏈接節點的無界執行緒安全佇列，它采用先進先出的規則對節點進行排序，當我們添加一個元素的時候，它會添加到佇列的尾部，當我們獲取一個元素時，它會回傳佇列頭部的元素，它采用了“wait－free”演算法來實作

4.遍歷車廂，

5.使用initSeal方法嘗試購票，建立車廂的資料結構使用了：

int randCoach = ThreadLocalRandom.current().nextInt(this.coachNum);

建立車廂的資料結構，其中ThreadLocalRandom是執行緒相關的，調ThreadLocalRandom.current()會回傳當前執行緒的ThreadLocalRandom物件，ThreadLocalRandom優點在于高并發條件下，不同執行緒產生的亂數能不一致，同樣的，呼叫nextInt方法也會回傳一個偽隨機整數值，

使用getAndIncrement方法，以原子方式將當前值加 1，回傳舊值（即加1前的原始值），保證了操作的原子性，

6.使用initInquiry方法，查詢余票情況，也使用getAndIncrement方法來保證原子性，

7.退票使用initRefund方法，建立哈希表，根據物件的地址或者字串或者數字算出對應的int型別的數值，contains判斷是否包含這張票，找到后然后洗掉票，再重新回傳，也使用getAndIncrement方法來保證原子性，

CoachSection.java

同RouteSection.java，

先定義變數，建立座位串列，存盤座位的情況，

嘗試購票，以及查詢，退票，

SeatSection.java

同RouteSection.java，

先定義變數，建立座位串列，存盤座位的情況，

嘗試購票，以及查詢，退票，

這里為了驗證座位是否空閑，使用了如下方法：

private AtomicLong availableSeat;

根據一個 AtomicLong 型 64 位的 availableSeat判斷是否空閑，availableSeat 的每一位表示座位對應的每一站， 0 表示未售出， 1 表示售出，購票查詢退票時均采用從 route->coach->seat 的方式呼叫方法，在 seatNode 操作時，用原語 compareAndSet 構造非阻塞式的自旋鎖來保證并發操作的原子性，

Test.java

test方法參考了網上提供的思路和講解，

先設定測驗數值：

	private final static int ROUTE_NUM = 5;// 列車車次
	private final static int COACH_NUM = 8;// 車箱數
	private final static int SEAT_NUM = 100;// 每個車廂的座位數
	private final static int STATION_NUM = 10;// 總站數

	private final static int TEST_NUM = 10000;// 每個執行緒里呼叫的方法數是10000次
	private final static int refund = 10;// 退票數目
	private final static int buy = 40;// 買票數目
	private final static int query = 100;// 查詢票數目
	private final static int thread = 64;// 執行緒數目

再獲取乘客資訊，

在main方法里，先設定不同的執行緒總數，再對不同threadNums數目的執行緒進行處理，并發完成threadNums數目的所有執行緒，在Thread建構式中傳入Runnable實作物件，在Thread原始碼中將Runnable物件傳遞給init方法，

運行執行緒，使用getAndIncrement方法將原值+1，并且回傳+1前的原值，獲取id，

根據退票/購票/查詢余票=1/3/6的比例進行測驗，

二.正確性與性能

運行老師提供的verify測驗單執行緒，通過，并顯示Verification Finished，

使用trace.java生成如下結果：

使用自己準備的test.java生成如下結果，來測驗性能：

綜上，測驗合格，

三.是否滿足相關要求

1.買票

使用buyTicket方法，先判斷車次和車站是否在范圍內，再呼叫RouteSection模塊里的initSeal方法，嘗試購票，并回傳(route - 1)，

	//買票
	public Ticket buyTicket(String passenger, int route, int departure,int arrival) {
		//先判斷車次和車站是否在范圍內
		if (route <= 0 || route > this.routeNum || arrival > this.stationNum
				|| departure >= arrival)
			return null;
		//嘗試購票，并回傳(route - 1)
		return this.routeArray.get(route - 1).initSeal(passenger, departure,
				arrival);
	}

從RouteSection到CoachSection，再到SeatSection，進一步的具體購票：（SeatSection）

	public int initSeal(final int departure, final int arrival) {
		long oldAvailSeat = 0;
		long newAvailSeat = 0;
		long temp = 0;

		int i = departure - 1;
		while(i < arrival - 1){
			long pow = 1;
			pow = pow << i;
			temp |= pow;
			i++;
		}

		do {
			oldAvailSeat = this.availableSeat.get();
			long result = temp & oldAvailSeat;
			if (result != 0) {
				return -1;
			}
			else {
				newAvailSeat = temp | oldAvailSeat;
			}
		} while (!this.availableSeat.compareAndSet(oldAvailSeat, newAvailSeat));
		return this.seatId;
	}

這里使用了compareAndSet，實作了區別于synchronouse同步鎖的一種樂觀鎖，使用這些類在多核CPU的機器上會有比較好的性能，它的作用是將指定記憶體地址的內容與所給的某個值相比，如果相等，則將其內容替換為指令中提供的新值，如果不相等，則更新失敗，CAS有3個運算元，記憶體值V，舊的預期值A，要修改的新值B，當且僅當預期值A和記憶體值V相同時，將記憶體值V修改為B，否則什么都不做，

2.查詢

先判斷車次和車站是否在范圍內，再呼叫RouteSection模塊里的initInquiry方法嘗試購票，并回傳(route - 1)，

	//查詢
	public int inquiry(int route, int departure, int arrival) {

		//先判斷車次和車站是否在范圍內
		if (route <= 0 || route > this.routeNum || arrival > this.stationNum
				|| departure >= arrival)

			return -1;

		//嘗試查詢，并回傳(route - 1)
		return this.routeArray.get(route - 1).initInquiry(departure, arrival);

	}

從RouteSection到CoachSection，再到SeatSection，進一步的具體購查詢：（SeatSection）

	public int initInquiry(final int departure, final int arrival) {
		long oldAvailSeat = this.availableSeat.get();
		long temp = 0;
		long pow;
		int i = departure - 1; 
		while(i < arrival - 1){
			pow = 1;
			pow = pow << i;
			temp |= pow;
			i++;
		}

		long result = temp & oldAvailSeat;
		return (result == 0) ? 1 : 0;
	}

3.退票

先獲取車票的車次，判斷車票和車次是否在范圍內，再呼叫RouteSection模塊里的initRefund方法嘗試購票，并回傳(route - 1)，

//退票
	public boolean refundTicket(Ticket ticket) {

		//獲取車票的車次
		final int routeId = ticket.route;
		//先判斷車票和車次是否在范圍內
		if (ticket == null || routeId <= 0 || routeId > this.routeNum)
			return false;
		//嘗試退票，并回傳(route - 1)
		return this.routeArray.get(routeId - 1).initRefund(ticket);

	}

從RouteSection到CoachSection，再到SeatSection，進一步的具體退票：（SeatSection）

public boolean initRefund(final int departure, final int arrival) {

		long oldAvailSeat = 0;
		long newAvailSeat = 0;
		long temp = 0;

		int i = departure - 1;
		while(i < arrival - 1){
			long pow = 1;
			pow = pow << i;
			temp |= pow;
			i++;
		}

		temp = ~temp;

		do {
			oldAvailSeat = this.availableSeat.get();
			newAvailSeat = temp & oldAvailSeat;
		} while (!this.availableSeat.compareAndSet(oldAvailSeat, newAvailSeat));

		return true;
	}

}

這里再次使用了compareAndSet，來實作退票的方法，

對于可線性化，可以實作并行操作時時序重疊，實際按可線性化點的順序來執行，我使用的是cas，它的作用是將指定記憶體地址的內容與所給的某個值相比，如果相等，則將其內容替換為指令中提供的新值，如果不相等，則更新失敗，CAS有3個運算元，記憶體值V，舊的預期值A，要修改的新值B，當且僅當預期值A和記憶體值V相同時，將記憶體值V修改為B，否則什么都不做，買票、查詢、退票都滿足可線性化，

對于無死鎖，申請鎖的執行緒最終都會獲得鎖，所以滿足無死鎖，

對于無饑餓，我使用的是cas，每個申請鎖的執行緒都會獲得鎖，并且所有的執行緒都能在有限步當中完成，因此必然不會有執行緒永久地呆在臨界區內出不去，所以它一定是無饑餓的，所以無饑餓，

對于無鎖，我的某一個方法呼叫執行緒，最終都會回傳，保證至少有一個執行緒能夠在有限步當中完成它的操作，所有的執行緒在不停地競爭直到有一個勝出為止，所以是無鎖的，

對于無等待，相比于無鎖更進一步，它首先要求是無鎖的，保證所有執行緒能進并且至少有一個執行緒能出來，它要求所有進入臨界區的執行緒都能夠在有限步當中完成其操作，這個要求很高，因為任何執行緒都能夠無障礙進入臨界區，并且任何執行緒都能夠在有限步當中完成操作后離開臨界區，呼叫一個方法的執行緒最終都會回傳，所以無等待，

綜上，均滿足要求，

附：專案要求

用于列車售票的可線性化并發資料結構

碼字不易，都看到這里了不如點個贊哦~

我還寫了很多文章，歡迎關注我哦~ 一起加油~