Java多線程同步
前言：
本章節(jié)是參考網(wǎng)上文章并自行研究鎖的一部分總結(jié)，由于本人從事Android開(kāi)發(fā)祭犯，所以在針對(duì)鎖的底層實(shí)現(xiàn)時(shí)帘瞭，會(huì)對(duì)比x86和ARM架構(gòu)下對(duì)應(yīng)的實(shí)現(xiàn)，如有問(wèn)題請(qǐng)及時(shí)指出吊圾；
1. Java鎖
- Lock出現(xiàn)之前，Java使用synchronized實(shí)現(xiàn)多線程同步翰蠢，JDK5之后项乒，JUC包下引入Lock接口及其實(shí)現(xiàn)類實(shí)現(xiàn)同步功能，Lock相比synchronized更靈活梁沧，擁有手動(dòng)獲取和釋放鎖檀何、非阻塞式獲取鎖、響應(yīng)中斷廷支、獲取超時(shí)等新特點(diǎn)频鉴；
- Java提供了種類豐富的鎖，按照特性的不同恋拍，可以按以下宏觀概念理解：
- 樂(lè)觀鎖和悲觀鎖垛孔；
- 自旋鎖；
- 無(wú)鎖施敢、偏向鎖周荐、輕量級(jí)鎖、重量級(jí)鎖僵娃；
- 公平鎖和非公平鎖羡藐；
- 可重入鎖；
- 獨(dú)享鎖（排他鎖）和共享鎖悯许；
1.1 樂(lè)觀鎖VS悲觀鎖
- 悲觀鎖：
對(duì)于同一數(shù)據(jù)的多線程并發(fā)操作，悲觀鎖認(rèn)為辉阶，自己在使用數(shù)據(jù)的時(shí)候一定有其他線程來(lái)修改數(shù)據(jù)先壕，因此get數(shù)據(jù)的時(shí)候先加鎖瘩扼，確保數(shù)據(jù)不會(huì)被其他線程修改，Java中的synchronized關(guān)鍵字和Lock的實(shí)現(xiàn)類都是悲觀鎖垃僚； - 樂(lè)觀鎖：
認(rèn)為自己在使用數(shù)據(jù)時(shí)不會(huì)被別的線程修改集绰，所以不會(huì)添加鎖，只是在更新數(shù)據(jù)的時(shí)候去判斷之前有沒(méi)有其他線程更新了這個(gè)數(shù)據(jù)谆棺。如果沒(méi)有被更新栽燕，當(dāng)前線程write成功；如果被更新改淑，當(dāng)前線程根據(jù)不同的實(shí)現(xiàn)類碍岔，執(zhí)行不同的操作（例如報(bào)錯(cuò)或自動(dòng)重試）。樂(lè)觀鎖在Java中是通過(guò)使用無(wú)鎖編程實(shí)現(xiàn)的朵夏，采用CAS算法蔼啦，Java原子類中的遞增操作就是通過(guò)CAS自旋實(shí)現(xiàn)的； - 使用場(chǎng)景：
- 悲觀鎖適合write場(chǎng)景仰猖，synchronized捏肢，ReentrantLock，都是顯式的加鎖后再操作同步資源或代碼塊饥侵；
- 樂(lè)觀鎖適合read場(chǎng)景鸵赫，AtomicInteger.incrementAndGet()，Java層不鎖定躏升，直接操作資源辩棒；
- 樂(lè)觀鎖使用CAS算法實(shí)現(xiàn)多線程同步：
CAS（Compare and Swap），無(wú)鎖算法煮甥，在不使用鎖盗温，并且線程沒(méi)有被阻塞的情況下實(shí)現(xiàn)多線程之間數(shù)據(jù)同步。CAS算法涉及到三個(gè)操作數(shù)：需要讀寫的內(nèi)存值V成肘；進(jìn)行比較的的值A(chǔ)卖局；待寫入的新值B；
當(dāng)且僅當(dāng)V==A双霍，通過(guò)原子方式讓V=B（"比較+更新"整體是一個(gè)原子操作）砚偶，否則由一個(gè)do()while{}循環(huán)，繼續(xù)從頭執(zhí)行上述步驟洒闸，自旋次數(shù)也是有上限的（默認(rèn)10次染坯，看具體的操作系統(tǒng)，可以通過(guò)JVM參數(shù)修改）丘逸；java.utils.concurrent包中的原子類就是通過(guò)CAS實(shí)現(xiàn)的单鹿，例如AtomicInteger，后續(xù)介紹： - CAS高效深纲，因?yàn)樽孕郎p少切換線程所需的開(kāi)銷仲锄，但存在幾個(gè)問(wèn)題：
- ABA的問(wèn)題：CAS需要在操作值之前檢查內(nèi)存值是否發(fā)生變化劲妙，沒(méi)有變化才更新內(nèi)存值；但如果內(nèi)存值由A->B->A最終變回A儒喊，但其實(shí)內(nèi)存值是變化過(guò)的镣奋，這種情況不能被忽略，所以在變量前添加版本號(hào)即可怀愧；
- while循環(huán)時(shí)間長(zhǎng)開(kāi)銷大：如果長(zhǎng)時(shí)間while侨颈，會(huì)一直自旋，一直占用CPU資源芯义，開(kāi)銷也很大哈垢；
- 只能保證一個(gè)共享變量的原子操作：無(wú)法保證同時(shí)對(duì)多個(gè)共享變量的原子性操作，所以JDK1.5開(kāi)始提供了AtomicReference毕贼，把多個(gè)變量放到一個(gè)對(duì)象來(lái)保證執(zhí)行CAS操作時(shí)的原子性温赔；
- CAS無(wú)鎖算法和加鎖的效率，不一定誰(shuí)低誰(shuí)高鬼癣，不同場(chǎng)景需要使用不同的方式解決安全問(wèn)題陶贼；如果線程數(shù)和CPU核數(shù)一致，CAS效率高待秃；但如果線程很多拜秧，遠(yuǎn)大于CPU核數(shù)，則CAS效率很低章郁，因?yàn)镃AS會(huì)占用CPU資源枉氮；
1.2 自旋鎖
1.2.1 自旋鎖介紹
阻塞或喚醒一個(gè)Java線程需要操作系統(tǒng)切換CPU狀態(tài)暖庄，這種狀態(tài)切換需要耗費(fèi)處理器時(shí)間聊替。如果同步代碼內(nèi)容很簡(jiǎn)單，狀態(tài)轉(zhuǎn)換消耗的時(shí)間可能比執(zhí)行代碼的還長(zhǎng)培廓，為了這種情況切換線程（線程掛起惹悄、恢復(fù)現(xiàn)場(chǎng)，狀態(tài)同步）肩钠，得不償失泣港；
如果機(jī)器有多個(gè)處理器，能讓2個(gè)或以上線程同時(shí)并行執(zhí)行价匠，則可以讓后來(lái)的請(qǐng)求鎖的thread不放棄CPU的執(zhí)行時(shí)間当纱，而是通過(guò)自旋的方式"稍稍等待一下"，看看當(dāng)前持有鎖的線程是否很快就釋放鎖踩窖。如果自旋完成后坡氯，前面線程釋放了鎖，則當(dāng)前線程可以直接獲取鎖并且執(zhí)行同步代碼，而不必走"阻塞->喚醒"這樣耗時(shí)耗資源的步驟箫柳，這就是自旋鎖颓遏；
-
說(shuō)白了，自旋鎖可以簡(jiǎn)單理解為：如果發(fā)現(xiàn)鎖被其他線程拿著滞时，在當(dāng)前線程，一定條件的while循環(huán)滤灯，而不是阻塞當(dāng)前線程：
Java自旋鎖.png 缺點(diǎn)：
不能代替線程阻塞坪稽，自旋是可以減少線程切換的開(kāi)銷，但會(huì)占用CPU執(zhí)行時(shí)間鳞骤。如果鎖被占用的時(shí)間很少，那自旋鎖效果很好，反之装获，也會(huì)浪費(fèi)CPU資源吼砂。所以自旋的while是有限制的，超過(guò)自旋次數(shù)就掛起線程美旧；
1.2.2 自旋鎖具體實(shí)現(xiàn)原理
- 實(shí)現(xiàn)算法就是CAS渤滞，對(duì)應(yīng)具體的實(shí)現(xiàn)類就是juc包下Atomic開(kāi)頭的原子類，下面從java.util.concurrent.atomic.AtomicInteger.getAndAddInt()逐步分析：
public class AtomicInteger extends Number implements java.io.Serializable { private static final long serialVersionUID = 6214790243416807050L; // Unsafe對(duì)象可以直接獲取并操作內(nèi)存的數(shù)據(jù) private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); // 該成員變量對(duì)應(yīng)真正value在AtomicInteger對(duì)象所在內(nèi)存地址中的偏移量offset private static final long VALUE; static { try { VALUE = U.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (ReflectiveOperationException e) { throw new Error(e); } } // 真正的int值榴嗅，volatile修飾妄呕，保證線程之間是可見(jiàn)的，在volatile章節(jié)已介紹可見(jiàn)性的實(shí)現(xiàn) private volatile int value; ...... public final int getAndAdd(int delta) { // 最終調(diào)用Unsafe.getAndAddInt() return U.getAndAddInt(this, VALUE, delta); } }CAS 本質(zhì)：依賴核
- 接著看sun.misc.Unsafe類：
可以看到疏魏，native方法compareAndSwapInt()其實(shí)包括了2個(gè)操作：比較+更新，多個(gè)操作如何保證原子性晤愧？// sun.misc.Unsafe.getAndAddInt() public final int getAndAddInt(Object o, long offset, int delta) { int v; do { // 根據(jù)value在AtomicInteger對(duì)象所在內(nèi)存地址中的偏移量offset獲取當(dāng)前內(nèi)存中的值v嗽测，然后判斷內(nèi)存中的值是否等于v v = this.getIntVolatile(o, offset); // 然后調(diào)用native方法compareAndSwapInt()绪励，對(duì)比v和(v+delta)的值是否相等，如果相等則表示沒(méi)有其他線程更改過(guò)這個(gè)值唠粥，接著將新值設(shè)置到內(nèi)存 } while(!this.compareAndSwapInt(o, offset, v, v + delta)); return v; } - 繼續(xù)往下找大莫，以openjdk中HotSpot虛擬機(jī)為例，查看openjdk/hotspot/src/share/vm/prims/unsafe.cpp文件养涮，從中找到Unsafe_CompareAndSwapInt葵硕，代碼如下：
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) UnsafeWrapper("Unsafe_CompareAndSwapInt"); // p就是內(nèi)存中的Unsafe對(duì)象 oop p = JNIHandles::resolve(obj); // 從Unsafe對(duì)象中，根據(jù)偏移量offset拿到真正保存int值的地址 jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); // 調(diào)用Atomic::cmpxchg()函數(shù)進(jìn)行"比較+更新"的操作贯吓，x就是待更新的值懈凹，e是原值，Atomic::cmpxchg()的返回值 return (jint)(Atomic::cmpxchg(x, addr, e)) == e; UNSAFE_END - 上述最終調(diào)用Atomic::cmpxchg()函數(shù)實(shí)現(xiàn)悄谐，該函數(shù)的實(shí)現(xiàn)是平臺(tái)相關(guān)的介评，不同平臺(tái)實(shí)現(xiàn)不同，Linux x86系統(tǒng)的實(shí)現(xiàn)如下：
inline jint Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint compare_value) { // 這里mp表示當(dāng)前系統(tǒng)是否為多核架構(gòu) // 如果是就給總線加鎖，所以同一芯片上的其他處理器就暫時(shí)不能通過(guò)總線訪問(wèn)內(nèi)存们陆，保證了該指令在多處理器環(huán)境下的原子性 int mp = os::is_MP(); // LOCK_IF_MP()：判斷是否是多核架構(gòu)寒瓦，如果是，則需要添加"lock"指令坪仇，才能保證不被其他處理器打斷cmpxchgl操作杂腰； __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)" // 匯編模版，%1指向輸入?yún)?shù)中的exchange_value椅文，%3指向dest喂很，類推... : "=a" (exchange_value) // 輸出操作數(shù)，"a"對(duì)應(yīng)累加寄存器EAX皆刺，下面的"r"指其他寄存器 : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp) // 輸入?yún)?shù) : "cc", "memory"); // 一些其他參數(shù)少辣，"memory" return exchange_value; }這段ASM匯編代碼簡(jiǎn)單翻譯一下就是：匯編指令cmpxchgl會(huì)比較EAX寄存器的值（compare_value，該線程已經(jīng)拿到的值）和exchange_value（待更新的值）羡蛾，如果相等漓帅，就把dest的值（即真實(shí)地址中的值）賦給exchange_value并返回給上層Unsafe_CompareAndSwapInt()中，在該函數(shù)中會(huì)將dest的值和當(dāng)前線程已拿到的值e比較痴怨，此時(shí)不等忙干，則CAS失敗，繼續(xù)do{}while{}腿箩；否則豪直，將待更新的值exchange_value寫入EAX寄存器，CAS成功珠移；
- 總結(jié)：
Linux x86平臺(tái)弓乙，多核架構(gòu)，JDK中AtomicXX類的CAS算法是由匯編指令"lock cmpxchgl"實(shí)現(xiàn)的钧惧；單核架構(gòu)暇韧，不添加"lock"指令；該匯編指令保證了"比較+更新"操作的原子性浓瞪； - 對(duì)比 Linux ARM架構(gòu)的實(shí)現(xiàn)懈玻，代碼在linux/arch/arm/include/asm/atomic.h文件中：
... #if __LINUX_ARM_ARCH__ >= 6 /* * ARMv6 UP and SMP safe atomic ops. We use load exclusive and * store exclusive to ensure that these are atomic. We may loop * to ensure that the update happens. */ ... \ #define ATOMIC_OP_RETURN(op, c_op, asm_op) \ static inline int atomic_##op##_return_relaxed(int i, atomic_t *v) \ { \ unsigned long tmp; \ int result; \ \ prefetchw(&v->counter); \ \ __asm__ __volatile__("@ atomic_" #op "_return\n" \ "1: ldrex %0, [%3]\n" \ " " #asm_op " %0, %0, %4\n" \ " strex %1, %0, [%3]\n" \ " teq %1, #0\n" \ " bne 1b" \ : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter) \ : "r" (&v->counter), "Ir" (i) \ : "cc"); \ \ return result; \ }- 可以從上面匯編代碼里看到，Linux ARMv6及之后的架構(gòu)乾颁，使用ldrex和strex指令獨(dú)占的訪問(wèn)內(nèi)存涂乌，實(shí)現(xiàn)原子性；
- 簡(jiǎn)單理解英岭，這倆指令會(huì)將被訪問(wèn)的內(nèi)存段設(shè)置"獨(dú)占"標(biāo)記湾盒，這倆指令也是ARM架構(gòu)平臺(tái)實(shí)現(xiàn)線程同步工具的基礎(chǔ)；
- 補(bǔ)充LongAdder诅妹，專門用于基礎(chǔ)數(shù)據(jù)類型遞增的場(chǎng)景罚勾，替換AtomicXX類：
- 大致實(shí)現(xiàn)：
在increment()操作中毅人，創(chuàng)建Cell數(shù)組，分塊Cell累加尖殃，累加單元和CPU核數(shù)有關(guān)丈莺，利用多核CAS運(yùn)算，提高整個(gè)遞增的效率送丰，最后longValue()獲取結(jié)果時(shí)缔俄，所有的Cell累加后將結(jié)果拋到調(diào)用者； - 使用場(chǎng)景：
累加操作器躏，且量級(jí)很大的時(shí)候替代AtomicXX使用牵现；
- 大致實(shí)現(xiàn)：
1.2.3 Unsafe魔法類
不只是AtomicXXX的實(shí)現(xiàn)，看過(guò)Java鎖的代碼后發(fā)現(xiàn)邀桑，所有的鎖最終都會(huì)調(diào)用sun.misc.Unsafe的API來(lái)保證操作的原子性，接著了解一下黑科技Unsafe類科乎；
-
主要功能如下：
Java魔法類Unsafe.png -
Unsafe.java是單例壁畸，提供靜態(tài)方法getUnsafe()獲取Unsafe對(duì)象，當(dāng)且僅當(dāng)調(diào)用getUnsafe()的類為BootstrapClassLoader加載時(shí)才合法茅茂，否則拋出SecurityException異常：
public final class Unsafe { // 單例對(duì)象 private static final Unsafe theUnsafe; private Unsafe() { } @CallerSensitive public static Unsafe getUnsafe() { Class var0 = Reflection.getCallerClass(); // 僅在引導(dǎo)類加載器`BootstrapClassLoader`加載時(shí)才合法 if(!VM.isSystemDomainLoader(var0.getClassLoader())) { throw new SecurityException("Unsafe"); } else { return theUnsafe; } } } -
Unsafe類是JDK提供給Java開(kāi)發(fā)者的一個(gè)操作系統(tǒng)后門捏萍，可以直接對(duì)操作系統(tǒng)的內(nèi)存等資源進(jìn)行操作，即：增強(qiáng)了Java語(yǔ)言對(duì)底層資源操作的能力空闲。既然可以像C/C++一樣操作內(nèi)存空間令杈，使用Unsafe是比較高風(fēng)險(xiǎn)的，需要謹(jǐn)慎碴倾，下面簡(jiǎn)單描述下Unsafe常見(jiàn)的能力：
-
內(nèi)存操作：
- 主要包含堆外內(nèi)存的分配逗噩、拷貝、釋放跌榔、給定地址值操作等方法异雁；
- 通常Java中創(chuàng)建的對(duì)象都位于堆內(nèi)內(nèi)存（heap），heap由JVM管控僧须，是Java進(jìn)程內(nèi)存纲刀，遵循JVM垃圾回收機(jī)制；而Unsafe提供的接口是對(duì) "對(duì)外內(nèi)存"進(jìn)行操作担平，不受JVM內(nèi)存管理機(jī)制約束示绊，所以使用不當(dāng)很危險(xiǎn)；
- 使用堆外內(nèi)存的好處：1.改善垃圾回收時(shí)造成的停頓現(xiàn)象暂论；2.提升I/O性能面褐，通常在I/O通信過(guò)程中，會(huì)存在堆內(nèi)內(nèi)存到堆外內(nèi)存的數(shù)據(jù)拷貝操作空另，對(duì)于需要頻繁進(jìn)行內(nèi)存間數(shù)據(jù)拷貝且生命周期較短的暫存數(shù)據(jù)盆耽，都建議存儲(chǔ)到堆外內(nèi)存；
- 應(yīng)用：nio包下的DirectByteBuffer是Java層使用堆外內(nèi)存的具體實(shí)現(xiàn)，內(nèi)部接口就是使用Unsafe實(shí)現(xiàn)的摄杂；
-
CAS：
- CAS：實(shí)現(xiàn)并發(fā)算法時(shí)用到的一種技術(shù)坝咐，Compare And Swap；
- CAS操作包含3個(gè)操作數(shù)：內(nèi)存值value析恢、預(yù)期的原值old墨坚、新值new；
- 執(zhí)行CAS操作時(shí)映挂，比較value和old泽篮，如果value==old，則更新內(nèi)存值value=new柑船，否則根據(jù)具體的實(shí)現(xiàn)或進(jìn)行自旋帽撑，或報(bào)錯(cuò)等等；
- 應(yīng)用：JUC包下的AtomicXXX最終執(zhí)行Unsafe.compareAndSwapXXX()鞍时；還有Java AQS亏拉、CurrentHashMap等；
-
Class相關(guān)：
- 提供Class和它的靜態(tài)字段的操作相關(guān)方法逆巍，包含靜態(tài)字段內(nèi)存定位及塘、定義類、定義匿名類锐极、檢驗(yàn)&確保初始化等笙僚；
- 應(yīng)用：從Java 8開(kāi)始，JDK使用invokedynamic（JDK 7引入的運(yùn)行動(dòng)態(tài)語(yǔ)言的一條新的虛擬機(jī)指令）及VM Anonymous Class（一種模版機(jī)制）結(jié)合來(lái)實(shí)現(xiàn)Java語(yǔ)言層面上的Lambda表達(dá)式灵再；
-
操作對(duì)象：
- 對(duì)對(duì)象成員屬性肋层、非常規(guī)的實(shí)例化等操作（Unsafe.allocateInstance()等）；
- 常規(guī)的對(duì)象實(shí)例化：使用new關(guān)鍵字翎迁，如果Foo類只有有參構(gòu)造函數(shù)槽驶，且沒(méi)顯示聲明無(wú)參構(gòu)造函數(shù)，則只能調(diào)用有參構(gòu)造函數(shù)創(chuàng)建對(duì)象鸳兽；
- 非常規(guī)對(duì)象實(shí)例化：上述Foo掂铐，可以使用Unsafe.allocateInstance()繞過(guò)JVM安全檢查，直接調(diào)用Foo隱式的無(wú)參構(gòu)造函數(shù)實(shí)例化對(duì)象揍异；
- 應(yīng)用：Gson反序列化全陨；日常開(kāi)發(fā)需要注意這倆問(wèn)題：Gson與Kotlin碰撞出一個(gè)不安全的操作、Gson 又搞了個(gè)坑
-
線程調(diào)度：
- 包括線程阻塞（park()）衷掷、喚醒（unpark()）辱姨、鎖機(jī)制（Unsafe.monitorEnter()...）等方法；
- Java鎖的核心類AQS戚嗅；
-
獲取系統(tǒng)信息：
- 獲取系統(tǒng)相關(guān)信息：返回系統(tǒng)指針的大小雨涛、獲取內(nèi)存頁(yè)的大惺嗖啊；
- 應(yīng)用：nio包下的工具類Bits替久，DirectByteBuffer中使用了Bits凉泄；
-
內(nèi)存操作：
1.3 無(wú)鎖 VS 偏向鎖 VS 輕量級(jí)鎖 VS 重量級(jí)鎖
- JDK 1.6中引入了這4個(gè)概念，具體是指鎖的四種狀態(tài)蚯根，針對(duì)synchronized設(shè)定的后众，對(duì)于Android系統(tǒng)的synchronized可以參考synchronized 第1.3節(jié)第9點(diǎn)最后的流程圖；
- 無(wú)鎖：
沒(méi)有對(duì)資源進(jìn)行鎖定颅拦，所有的線程都能訪問(wèn)并修改同一個(gè)資源蒂誉，但同時(shí)只有一個(gè)線程能修改成功； - 偏向鎖：
是指一段同步代碼一直被一個(gè)線程所訪問(wèn)距帅，那么該線程會(huì)自動(dòng)獲取鎖右锨，降低獲取鎖的代價(jià)（如果一段synchronized代碼，只有一個(gè)線程在執(zhí)行碌秸，每次執(zhí)行都CAS操作陡蝇，該操作中包含"獲取鎖->釋放鎖"，沒(méi)有必要）哮肚。只有遇到其他線程嘗試競(jìng)爭(zhēng)偏向鎖時(shí)，持有偏向鎖的線程才會(huì)釋放鎖广匙，線程不會(huì)主動(dòng)釋放偏向鎖允趟。釋放后鎖的狀態(tài)恢復(fù)到無(wú)鎖或輕量級(jí)鎖； - 輕量級(jí)鎖：
是指當(dāng)鎖是偏向鎖的時(shí)候鸦致，被另外的線程所訪問(wèn)潮剪，偏向鎖就會(huì)升級(jí)為輕量級(jí)鎖，其他線程會(huì)通過(guò)自旋的形式嘗試獲取鎖分唾，不會(huì)阻塞抗碰，從而提高性能；偏向鎖和輕量級(jí)鎖對(duì)應(yīng) Android虛擬機(jī)ART 的"瘦鎖"態(tài)绽乔。 - 重量級(jí)鎖：
若當(dāng)前只有一個(gè)等待線程弧蝇，則該線程通過(guò)自旋進(jìn)行等待。但是當(dāng)自旋超過(guò)一定的次數(shù)折砸，或者一個(gè)線程在持有鎖看疗，一個(gè)在自旋，又有第三個(gè)來(lái)訪時(shí)睦授，輕量級(jí)鎖升級(jí)為重量級(jí)鎖两芳，這里的重量級(jí)鎖對(duì)應(yīng) Android虛擬機(jī)ART 的"胖鎖"態(tài)，即 使用ART封裝的Mutex鎖去枷。
1.4 公平鎖 VS 非公平鎖
- 公平鎖：
公平鎖是指多個(gè)線程按照申請(qǐng)鎖的順序來(lái)獲取鎖怖辆，線程直接進(jìn)入隊(duì)列中排隊(duì)是复，隊(duì)列中的第一個(gè)線程才能獲得鎖。公平鎖的優(yōu)點(diǎn)是等待鎖的線程不會(huì)餓死竖螃。缺點(diǎn)是整體吞吐效率相對(duì)非公平鎖要低淑廊，等待隊(duì)列中除第一個(gè)線程以外的所有線程都會(huì)阻塞，CPU喚醒阻塞線程的開(kāi)銷比非公平鎖大斑鼻。 - 非公平鎖：
非公平鎖是多個(gè)線程加鎖時(shí)直接嘗試獲取鎖蒋纬，獲取不到才會(huì)到等待隊(duì)列的隊(duì)尾等待。但如果此時(shí)鎖剛好可用坚弱，那么這個(gè)線程可以無(wú)需阻塞直接獲取到鎖蜀备，所以非公平鎖有可能出現(xiàn)后申請(qǐng)鎖的線程先獲取鎖的場(chǎng)景。非公平鎖的優(yōu)點(diǎn)是可以減少喚起線程的開(kāi)銷荒叶，整體的吞吐效率高碾阁，因?yàn)榫€程有幾率不阻塞直接獲得鎖，CPU不必喚醒所有線程些楣。缺點(diǎn)是處于等待隊(duì)列中的線程可能會(huì)餓死脂凶，或者等很久才會(huì)獲得鎖。 - Java中具體的實(shí)現(xiàn)愁茁，ReentrantLock可以選擇創(chuàng)建哪種鎖蚕钦，默認(rèn)是創(chuàng)建非公平鎖：
public ReentrantLock(boolean fair) { sync = fair ? new FairSync() : new NonfairSync(); } - 在JDK8中，對(duì)比ReentrantLock實(shí)現(xiàn) 公平鎖/非公平鎖 獲取鎖的代碼：
// 非公平鎖的實(shí)現(xiàn) final boolean nonfairTryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); if (c == 0) { if (compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } } else if (current == getExclusiveOwnerThread()) { ... return true; } return false; }
唯一區(qū)別在于促煮，公平鎖在嘗試獲取鎖時(shí)邮屁，增加了!hasQueuedPredecessors()判斷，接著查看該方法：// 公平鎖的實(shí)現(xiàn) static final class FairSync extends Sync { ... /** * Fair version of tryAcquire. Don't grant access unless * recursive call or no waiters or is first. */ protected final boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); if (c == 0) { // 區(qū)別６旌堋Ｋ痪印！ if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } } else if (current == getExclusiveOwnerThread()) { ... return true; } return false; } }
該方法的作用是菠齿，判斷當(dāng)前線程是否位于同步隊(duì)列中的第一個(gè)佑吝，如果是則返回true；即：通過(guò)同步隊(duì)列來(lái)實(shí)現(xiàn)多個(gè)線程按照申請(qǐng)鎖的順序來(lái)獲取鎖绳匀；而非公平鎖則直接嘗試獲取鎖芋忿；public final boolean hasQueuedPredecessors() { ... Node t = tail; // Read fields in reverse initialization order Node h = head; Node s; return h != t && ((s = h.next) == null || s.thread != Thread.currentThread()); }
1.5 可重入鎖
- 可重入鎖也叫遞歸鎖，指在同一線程疾棵，使用同一個(gè)鎖對(duì)象時(shí)盗飒，外層方法獲得鎖后，再進(jìn)入內(nèi)層方法時(shí)陋桂，自動(dòng)獲得鎖逆趣，不會(huì)因?yàn)橥鈱臃椒](méi)釋放鎖導(dǎo)致線程阻塞，當(dāng)然可重入的次數(shù)是有上限的嗜历；
- synchronized是可重入鎖宣渗，之前了解過(guò)抖所，ART虛擬機(jī)，使用synchronized時(shí)痕囱，對(duì)象鎖的可重入狀態(tài)封裝在c++代碼LockWord類的成員變量uint32_t value_中田轧，同一個(gè)線程多次獲取對(duì)象鎖時(shí)，這種情況說(shuō)明是瘦鎖狀態(tài)鞍恢，該value_字段的27-16位就保存了 Lock Count傻粘，即同一線程獲取該對(duì)象鎖的次數(shù)；
- ReentrantLock也是可重入鎖帮掉，ReentrantLock內(nèi)部通過(guò)Sync類實(shí)現(xiàn)所有的同步機(jī)制弦悉，而Sync繼承自AbstractQueuedSynchronizer（AQS，后面介紹）蟆炊，AbstractQueuedSynchronizer中state變量用來(lái)記錄鎖被獲取的次數(shù)（state是一個(gè)被volatile修飾的int類型）稽莉，通過(guò)公平鎖FairSync.lock()方法逐步分析，代碼如下：
接著看AQS.acquire(int)方法：static final class FairSync extends Sync { private static final long serialVersionUID = -3000897897090466540L; // 如果創(chuàng)建的是公平鎖涩搓，那ReentrantLock.lock()方法最終會(huì)調(diào)到這里 final void lock() { // Sync繼承自AQS污秆，該方法定義在AQS中 acquire(1); } protected final boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); if (c == 0) { // 介紹公平鎖/非公平鎖的時(shí)候知道，區(qū)別就在這里昧甘，獲得鎖的順序是否按照申請(qǐng)鎖的順序良拼，由一個(gè)隊(duì)列維護(hù)先后順序 ... } else if (current == getExclusiveOwnerThread()) { int nextc = c + acquires; if (nextc < 0) throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; } }public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }簡(jiǎn)單理解就是：
當(dāng)前線程獲得鎖之前，調(diào)用lock.lock()時(shí)充边，會(huì)走到AQS.tryAcquire()中庸推，具體實(shí)現(xiàn)在子類，但都是先拿到state進(jìn)行判斷痛黎，如果state==0，說(shuō)明該鎖沒(méi)有被任何一個(gè)線程持有刮吧，則讓當(dāng)前線程安全的（通過(guò)CAS操作保證獲取鎖的過(guò)程是原子的）拿到該鎖湖饱；
如果state!=0，則說(shuō)明該鎖已經(jīng)被某個(gè)線程持有杀捻，則繼續(xù)判斷持有鎖的線程是否是當(dāng)前線程井厌；
如果是當(dāng)前線程，則state++致讥，說(shuō)明當(dāng)前線程再一次拿到該鎖仅仆；
如果不是當(dāng)前線程，則回到AQS.acquire()方法中垢袱，執(zhí)行acquireQueued()墓拜，將本次獲取鎖的請(qǐng)求放入隊(duì)列，本次獲取鎖的操作失敗请契，走到后續(xù)的失敗處理流程中咳榜，后續(xù)介紹夏醉；
1.6 獨(dú)享鎖 VS 共享鎖
獨(dú)享鎖和共享鎖同樣也是一種概念；
是對(duì)可重入鎖的進(jìn)一步優(yōu)化涌韩，因?yàn)閱渭兊目芍厝腈iReentrantLock畔柔，state狀態(tài)記錄的是包括讀和寫，即"讀臣樱，寫"都需要加鎖靶擦，效率還是比較低，所以引入"獨(dú)享鎖（排他鎖）和共享鎖"雇毫；
獨(dú)享鎖也叫排他鎖玄捕，是指該鎖一次只能被一個(gè)線程所持有。如果線程T對(duì)共享數(shù)據(jù)A加上排它鎖后嘴拢，則其他線程不能再對(duì)A加任何類型的鎖桩盲。獲得排它鎖的線程即能讀數(shù)據(jù)又能修改數(shù)據(jù)。synchronized和Lock接口的實(shí)現(xiàn)類都是獨(dú)享鎖席吴；
共享鎖是指該鎖可被多個(gè)線程所持有赌结。如果線程T對(duì)數(shù)據(jù)A加上共享鎖后，則其他線程只能對(duì)A再加共享鎖孝冒，不能加排它鎖柬姚。獲得共享鎖的線程只能讀數(shù)據(jù)，不能修改數(shù)據(jù)庄涡。
-
具體的實(shí)現(xiàn)類是java.util.concurrent.locks.ReentrantReadWriteLock量承，實(shí)現(xiàn)了ReadWriteLock接口：
Java獨(dú)享鎖共享鎖.png 內(nèi)部有兩把鎖ReadLock和WriteLock分別標(biāo)記讀和寫，都是Sync的子類穴店，Sync是AQS(AbstractQueuedSynchronizer)的子類撕捍，state就保存在AQS中；讀鎖是共享鎖泣洞，寫鎖是獨(dú)享鎖忧风。讀鎖可保證并發(fā)讀非常高效，而讀寫球凰、寫讀狮腿、寫寫的過(guò)程互斥，因?yàn)樽x鎖和寫鎖是分離的呕诉。所以ReentrantReadWriteLock的并發(fā)性相比一般的互斥鎖有了很大提升缘厢；
-
其原理簡(jiǎn)單概括：將32位int類型的變量state分為【高16位】和【低16位】，分別存儲(chǔ)讀鎖個(gè)數(shù)和寫鎖個(gè)數(shù)甩挫，先看寫鎖的代碼tryAcquire()：
// 寫鎖代碼 protected final boolean tryAcquire(int acquires) { Thread current = Thread.currentThread(); int c = getState(); // 取到當(dāng)前ReentrantReadWriteLock鎖的state int w = exclusiveCount(c); // 取寫鎖的個(gè)數(shù)w贴硫，即獨(dú)享鎖個(gè)數(shù) if (c != 0) { // 如果已經(jīng)有線程持有了鎖(c!=0) // 如果寫線程數(shù)（w）為0（換言之僅存在讀鎖） 或者持有鎖的線程不是當(dāng)前線程就返回失敗 // 當(dāng)已經(jīng)存在某個(gè)線程拿到讀鎖時(shí)，不允許其他線程再獲得寫鎖伊者，否則無(wú)法保證數(shù)據(jù)對(duì)所有線程都是最新的夜畴，所以此處直接返回false拖刃，表示獲取寫鎖失敗 if (w == 0 || current != getExclusiveOwnerThread()) return false; if (w + exclusiveCount(acquires) > MAX_COUNT) // 如果寫鎖的重入數(shù)大于最大數(shù)（65535，2的16次方-1）就拋出一個(gè)Error贪绘。 throw new Error("Maximum lock count exceeded"); // 成功拿到寫鎖兑牡！ setState(c + acquires); return true; } // 如果當(dāng)且寫線程數(shù)為0，并且當(dāng)前線程需要阻塞（該方法只用于公平鎖税灌，即：因?yàn)樽罱K調(diào)用的是hasQueuedPredecessors()均函，只有在等待隊(duì)列的線程，才會(huì)被阻塞）菱涤，則獲取寫鎖失敯病；或者如果通過(guò)CAS增加寫線程數(shù)失敗也返回失敗 if (writerShouldBlock() || !compareAndSetState(c, c + acquires)) return false; // 如果c=0粘秆，w=0或者c>0如迟，w>0（重入），則設(shè)置當(dāng)前線程或鎖的擁有者攻走，獲得寫鎖成功 setExclusiveOwnerThread(current); return true; }接著看讀鎖的代碼：
// 讀鎖代碼 protected final int tryAcquireShared(int unused) { Thread current = Thread.currentThread(); int c = getState(); // 如果其他線程已經(jīng)獲取了寫鎖殷勘，則當(dāng)前線程獲取讀鎖失敗，并進(jìn)入等待狀態(tài) if (exclusiveCount(c) != 0 && getExclusiveOwnerThread() != current) return -1; // 拿到讀鎖個(gè)數(shù) int r = sharedCount(c); // readerShouldBlock()方法依然調(diào)用的是hasQueuedPredecessors() // 執(zhí)行compareAndSetState()方法昔搂，更新state的值 if (!readerShouldBlock() && r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) { ... return 1; } return fullTryAcquireShared(current); } -
總結(jié)：
- 對(duì)于ReentrantReadWriteLock玲销，獲得讀鎖和寫鎖的操作是互斥的，可能會(huì)造成線程阻塞摘符；而獲得讀鎖和讀鎖的操作是共享的贤斜，不會(huì)造成線程阻塞；
- 對(duì)于ReentrantLock逛裤，不論創(chuàng)建的是公平鎖還是非公平鎖瘩绒，不論是讀操作還是寫操作，添加的都是獨(dú)享鎖带族；
- 所以ReentrantReadWriteLock在"讀讀操作"時(shí)的效率比ReentrantLock高锁荔；
2. AbstractQueuedSynchronizer原理
2.1 介紹
- AQS是一種提供了原子式管理同步狀態(tài)、阻塞和喚醒線程功能以及隊(duì)列模型的簡(jiǎn)單框架炉菲；
- Java中的大部分同步類（Lock接口堕战、ReadWriteLock接口坤溃、Semaphore拍霜、CountDownLatch等）都是基于AbstractQueuedSynchronizer（簡(jiǎn)稱為AQS）實(shí)現(xiàn)的；
- 即：Java層又實(shí)現(xiàn)的一套同步鎖框架薪介，使用一個(gè)阻塞隊(duì)列（雙向鏈表）祠饺，解決多線程并發(fā)問(wèn)題；只不過(guò)AQS通過(guò)CAS無(wú)鎖算法和自旋汁政，可以讓多個(gè)線程在盡可能不暫停線程的情況下道偷，達(dá)到搶占鎖的目的缀旁；
- 本節(jié)將從ReentrantLock的實(shí)現(xiàn)分析AQS；
2.2 Lock的使用方法
介紹AQS原理前補(bǔ)一下ReentrantLock的基本使用方法勺鸦，它比synchronized更加靈活并巍，上鎖和解鎖的邏輯被開(kāi)發(fā)者控制：
Lock mLock;
public void testReentrantLock() {
mLock = new ReentrantLock(true);
try {
if (mLock.tryLock(1000, TimeUnit.MILLISECONDS)) {
// Do somethings ...
} else {
// Other things ...
}
} catch (Throwable e) {
e.printStackTrace();
} finally {
mLock.unlock();
}
}
2.3 AQS的實(shí)現(xiàn)原理
- 從最主要的
ReentrantLock.lock()加鎖方法著手分析，以NonfairSync實(shí)現(xiàn)為例换途，代碼如下：final void lock() { if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread.currentThread()); else acquire(1); }- 如果對(duì)state CAS成功懊渡，則當(dāng)前線程直接獲得鎖成功；
- 如果對(duì)state CAS失敗军拟，則進(jìn)入
acquire();方法進(jìn)行后續(xù)處理剃执；
- 獲取鎖成功的邏輯，在上面已經(jīng)介紹過(guò)懈息，不同類型的鎖有不同的實(shí)現(xiàn)肾档；而對(duì)于獲取鎖失敗后，肯定存在某種排隊(duì)等待的機(jī)制辫继，讓線程繼續(xù)擁有獲得鎖的機(jī)會(huì)怒见，而不是直接結(jié)束流程；從上面代碼可以知道骇两，需要看下acquire()方法的實(shí)現(xiàn)邏輯速种，而該方法定義在
java.util.concurrent.locks.AbstractQueuedSynchronizer中，所以下面分析一下AQS的原理低千； - AQS的整體結(jié)構(gòu)如下圖所示：
AQS框架.png - AQS核心思想：如果共享資源沒(méi)有被占用配阵，則將使用共享資源的線程設(shè)置為當(dāng)前線程；如果共享資源被占用示血，則通過(guò)阻塞棋傍、等待喚醒的機(jī)制，確保鎖可以正常的被分配难审，線程仍然有機(jī)會(huì)獲得鎖瘫拣；
- 這種阻塞等待喚醒機(jī)制是依賴CLH（一種單鏈表）變體實(shí)現(xiàn)的，AQS中的隊(duì)列是CLH變體的虛擬雙向隊(duì)列（FIFO）告喊，通過(guò)將每條請(qǐng)求共享資源的線程封裝成一個(gè)節(jié)點(diǎn)Node來(lái)實(shí)現(xiàn)鎖的分配麸拄，而每個(gè)Node都是去操作AQS的volatile成員變量state實(shí)現(xiàn)同步的；
- 繼續(xù)回到acquire()方法代碼：
tryAcquire()方法是嘗試獲得鎖和處理重入問(wèn)題黔姜，如果失敗則會(huì)繼續(xù)執(zhí)行acquireQueued(addWaiter(Node.EXCLUSIVE), arg))方法拢切，該步驟內(nèi)部就是將當(dāng)前線程信息封裝成Node對(duì)象，加入等待隊(duì)列中秆吵，接著將該線程park淮椰；具體來(lái)說(shuō)，是將新Node添加到雙向鏈表的尾部，并將頭節(jié)點(diǎn)指向剛創(chuàng)建的Node對(duì)象主穗，接著看acquireQueued()方法泻拦；public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }
這就是獲取鎖時(shí)的阻塞等待機(jī)制的實(shí)現(xiàn)绳慎，至于被阻塞的線程什么時(shí)候被喚醒，需要了解一下解鎖的過(guò)程漠烧；final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { boolean interrupted = false; // 開(kāi)始自旋，對(duì)整條鏈表忽媒，從后往前遍歷 for (;;) { // 先拿到當(dāng)前節(jié)點(diǎn)的【前驅(qū)節(jié)點(diǎn)】 final Node p = node.predecessor(); // 如果正好是頭節(jié)點(diǎn)争拐，則說(shuō)明當(dāng)前節(jié)點(diǎn)是等待隊(duì)列的頭部，輪到當(dāng)前節(jié)點(diǎn)再次嘗試拿鎖 if (p == head && tryAcquire(arg)) { // 如果成功拿到鎖晦雨，則指針前移陆错，將node的前驅(qū)節(jié)點(diǎn)置null，即讓prev出隊(duì) setHead(node); p.next = null; // help GC failed = false; // 并且不需要讓當(dāng)前線程中斷金赦，因?yàn)槌晒δ玫芥i了音瓷，所以此處是唯一跳出循環(huán)的地方 return interrupted; } // 然后根據(jù)前驅(qū)節(jié)點(diǎn)，判斷當(dāng)前節(jié)點(diǎn)是否需要阻塞 // 如果需要?jiǎng)t通過(guò)parkAndCheckInterrupt()將當(dāng)前線程阻塞夹抗，防止死循環(huán)浪費(fèi)CPU資源 if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true; } } finally { if (failed) cancelAcquire(node); } } - ReentrantLock的解鎖過(guò)程不區(qū)分公平鎖和非公平鎖杏愤，查看java.util.concurrent.locks.ReentrantLock.unlock()函數(shù)：
public void unlock() { // 最終還是調(diào)用了AQS.release(int)函數(shù) sync.release(1); } - 到j(luò)ava.util.concurrent.locks.AbstractQueuedSynchronizer：
public final boolean release(int arg) { // 已獲取鎖的線程執(zhí)行完同步代碼塊后，嘗試釋放鎖已脓，即將當(dāng)前鎖的成員變量exclusiveOwnerThread置空珊楼，并通過(guò)CAS操作安全的更新AQS.state的值 if (tryRelease(arg)) { // 如果lock沒(méi)有被任何線程占用，則通過(guò)unparkSuccessor()函數(shù)將當(dāng)前線程N(yùn)ode的后繼節(jié)點(diǎn)（因?yàn)槭且粭l鏈表度液，此時(shí)后繼節(jié)點(diǎn)一定是被阻塞的）喚醒 // 【注意】：為什么是當(dāng)前阻塞隊(duì)列head的后繼節(jié)點(diǎn)呢厕宗？因?yàn)槊總€(gè)阻塞隊(duì)列的head是一個(gè)Dummy（啞元）節(jié)點(diǎn)，是個(gè)占位節(jié)點(diǎn)堕担，他的next才是阻塞隊(duì)列的首個(gè)節(jié)點(diǎn) // unparkSuccessor()內(nèi)部通過(guò)LockSupport.unpark(thread)將后繼節(jié)點(diǎn)線程喚醒 // 喚醒節(jié)點(diǎn)之前也會(huì)把當(dāng)前線程節(jié)點(diǎn)狀態(tài)置成初始狀態(tài)0已慢，方便后續(xù)操作將該節(jié)點(diǎn)從鏈表中移除 Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); return true; } return false; }
2.3.1 wait/notify和await/singal和park/unpark
-
obj.wait()/notify()：依托于synchronized，即底層依賴Monitor實(shí)現(xiàn)線程阻塞和喚醒霹购，和synchronized配合使用佑惠；public void test() { Object o = new Object(); synchronized (obj) { try { obj.wait(); } cache (...) { } } } -
ReentrantLock.ConditionObject.await()/signal()：是條件變量的方法，底層還是基于park()/unpark();齐疙；即：ConditionObject內(nèi)部本質(zhì)就是一個(gè)雙向隊(duì)列（但只用了nextWaiter）膜楷； -
LockSupport.park(thread)/unpark(thread)：精準(zhǔn)的暫停或喚醒某一個(gè)thread對(duì)象贞奋，而上面的obj.notify();是隨機(jī)喚醒一個(gè)thread赌厅；底層設(shè)計(jì)基于"許可"，C層使用volatile int _counter保存這個(gè)許可忆矛；（以上是JDK的實(shí)現(xiàn)）察蹲；
2.4 AQS的應(yīng)用
AQS是Java中自定義線程同步鎖的基礎(chǔ)框架，在此基礎(chǔ)上可以自定義各種同步工具：
- ReentrantLock
- ReentrantReadWriteLock
- Semaphore：
限量鎖催训，在構(gòu)造方法中設(shè)置permits最大允許多少個(gè)線程可訪問(wèn)一段代碼洽议，如果訪問(wèn)的線程超過(guò)permit，則剩下的thread等待漫拭；場(chǎng)景類似廁所蹲坑亚兄； - CountDownLatch：
可以在構(gòu)造函數(shù)中，設(shè)置門閂個(gè)數(shù)采驻，當(dāng)門閂個(gè)數(shù)為0审胚，才會(huì)走之后的邏輯；場(chǎng)景類似LOL礼旅，等10個(gè)人都加載完畢膳叨，游戲才能開(kāi)始； - ThreadPoolExecutor
2.5 總結(jié)
JDK 1.6中引入了多種多線程同步工具
- AtomicXXX原子類痘系，是通過(guò)CAS無(wú)鎖算法菲嘴，在一定程度上實(shí)現(xiàn)同步的，而CAS算法的實(shí)現(xiàn)汰翠，是通過(guò)Unsafe魔法類保證"比較+更新"操作的原子性的龄坪；
- Lock接口、ReadWriteLock接口的實(shí)現(xiàn)類等复唤，是基于AQS實(shí)現(xiàn)同步健田，AQS引入雙向鏈表隊(duì)列結(jié)構(gòu)，將"申請(qǐng)鎖"的操作封裝并放入等待隊(duì)列中佛纫，實(shí)現(xiàn)線程排隊(duì)獲取鎖的機(jī)制妓局，此外AQS的底層也是通過(guò)CAS算法保證操作的原子性；
- AQS本質(zhì)：
原子變量（int state）+隊(duì)列（雙向鏈表）+ park/unpark阻塞喚醒線程呈宇，用上面3要素來(lái)搭建一個(gè)Java層的鎖框架跟磨，真正實(shí)現(xiàn)還是各種和業(yè)務(wù)場(chǎng)景相關(guān)的子類；
參考
Java核心技術(shù) 卷I
不可不說(shuō)的Java“鎖”事
Java CAS 原理剖析
Java魔法類：Unsafe應(yīng)用解析
從ReentrantLock的實(shí)現(xiàn)看AQS的原理及應(yīng)用
