摘要：并發模塊本身有兩種不同的類型進程和線程，兩個基本的執行單元。調用以啟動新線程。在大多數系統中，時間片發生不可預知的和非確定性的，這意味著線程可能隨時暫停或恢復。

什么是并發編程？
進程，線程和時間片
交織和競爭條件
線程安全

策略1：監禁

策略2：不可變性

策略3：使用線程安全數據類型

策略4：鎖定和同步

如何做安全論證
總結

并發
并發性：多個計算同時發生。

在現代編程中無處不在：

網絡上的多臺計算機中的多臺計算機

在一臺計算機上運行的多個應用程序一臺計算機上的多個應用程序

計算機中的多個處理器（今天，通常是單個芯片上的多個處理器內核）一個CPU上的多核處理器

并發在現代編程中至關重要：

網站必須處理多個同時使用的用戶。多用戶并發請求服務器的計算資源

移動應用程序需要在云中執行一些處理。 App在手機端和在云端都有計算

圖形用戶界面幾乎總是需要不中斷用戶的后臺工作。例如，Eclipse在編輯它時編譯你的Java代碼。 GUI的前端用戶操作和后臺的計算

為什么要“并發”？

處理器時鐘速度不再增加。摩爾定律失效了
相反，我們每個新一代芯片都會獲得更多內核。 “核”變得越來越多
為了讓計算更快運行，我們必須將計算分解為并發塊。為了充分利用多核和多處理器，需要將程序轉化為并行執行

并行編程的兩種模型

共享內存：并發模塊通過在內存中讀寫共享對象進行交互。
共享內存：在內存中讀寫共享數據
消息傳遞：并發模塊通過通信通道相互發送消息進行交互。模塊發送消息，并將傳入的消息發送到每個模塊以便處理。
消息傳遞：通過信道（channel）交換消息

共享內存

共享內存模型的示例：

A和B可能是同一臺計算機中的兩個處理器（或處理器核），共享相同的物理內存。

兩個處理器，共享內存

A和B可能是在同一臺計算機上運行的兩個程序，它們共享一個通用文件系統及其可讀取和寫入的文件。

同一臺機器上的兩個程序，共享文件系統

A和B可能是同一個Java程序中的兩個線程，共享相同的Java對象。

同一個Java的程序內的兩個線程，共享的Java對象

消息傳遞

消息傳遞的例子：

A和B可能是網絡中的兩臺計算機，通過網絡連接進行通信。

網絡上的兩臺計算機，通過網絡連接通訊

A和B可能是一個Web瀏覽器和一個Web服務器

A打開與B的連接并請求網頁，B將網頁數據發送回A.

瀏覽器和Web服務器，A請求頁面，B發送頁面數據給A

A和B可能是即時消息客戶端和服務器。

即時通訊軟件的客戶端和服務器

A和B可能是在同一臺計算機上運行的兩個程序，其輸入和輸出已通過管道連接，如鍵入命令提示符中的ls | grep。

同一臺計算機上的兩個程序，通過管道連接進行通訊

進程和線程

消息傳遞和共享內存模型是關于并發模塊如何通信的。
并發模塊本身有兩種不同的類型：進程和線程，兩個基本的執行單元。
并發模塊的類型：進程和線程

進程是正在運行的程序的一個實例，與同一臺計算機上的其他進程隔離。 特別是，它有自己的機器內存專用部分。進程：私有空間，彼此隔離

線程是正在運行的程序中的一個控制軌跡。 把它看作是正在運行的程序中的一個地方，再加上導致那個地方的方法調用堆棧（所以當線程到達返回語句時可以返回堆棧）。線程：程序內部的控制機制

（1）進程

進程抽象是一個虛擬計算機（一個獨立的執行環境，具有一套完整的私有基本運行時資源，尤其是內存）。進程：擁有整臺計算機的資源

它使程序感覺自己擁有整臺機器

就像一臺全新的計算機一樣，創建了新的內存，只是為了運行該程序。

就像連接網絡的計算機一樣，進程通常在它們之間不共享內存。多進程之間不共享內存

進程無法訪問另一個進程的內存或對象。

相比之下，新的流程自動準備好傳遞消息，因為它是使用標準輸入輸出流創建的，這些流是您在Java中使用的System.out和System.in流。進程之間通過消息傳遞進行協作

進程通常被視為與程序或應用程序的同義詞。一般來說，進程==程序==應用

但是，用戶將其視為單一應用程序實際上可能是一組協作過程。但一個應用中可能包含多個進程

為了促進進程之間的通信，大多數操作系統都支持進程間通信（IPC）資源，例如管道和套接字。 OS支持的IPC機制（pipe / socket）支持進程間通信

IPC不僅用于同一系統上的進程之間的通信，還用于不同系統上的進程。不僅是本機的多個進程之間，也可以是不同機器的多個進程之間。

Java虛擬機的大多數實現都是作為單個進程運行的。但是Java應用程序可以使用ProcessBuilder對象創建其他進程。 JVM通常運行單一進程，但也可以創建新的進程。

（2）線程

線程和多線程編程
就像一個進程代表一個虛擬計算機一樣，線程抽象代表一個虛擬處理器，線程有時稱為輕量級進程 進程=虛擬機;線程=虛擬CPU

制作一個新的線程模擬在由該進程表示的虛擬計算機內部制造新的處理器。

這個新的虛擬處理器運行相同的程序，并與進程中的其他線程共享相同的資源（內存，打開的文件等），即“線程存在于進程中”。程序共享，資源共享，都隸屬于進程

線程自動準備好共享內存，因為線程共享進程中的所有內存。共享內存

需要特殊的努力才能獲得專用于單個線程的“線程本地”內存。很難獲得線程私有的內存空間（線程堆棧怎么樣？）

通過創建和使用隊列數據結構，還需要顯式設置消息傳遞。通過創建消息隊列在線程之間進行消息傳遞

線程與進程

線程是輕量級的 進程是重量級的
線程共享內存空間 進程有自己的
線程需要同步（當調用可變對象時線程保有鎖） 進程不需要
殺死線程是不安全的 殺死進程是安全的

多線程執行是Java平臺的基本功能。

每個應用程序至少有一個線程。每個應用至少有一個線程

從應用程序員的角度來看，你只從一個叫做主線程的線程開始。這個線程有能力創建額外的線程。主線程，可以創建其他的線程

兩種創建線程的方法：

（很少使用）子類化線程。從Thread類派生子類

（更常用）實現Runnable接口并使用new Thread（..）構造函數。從Runnable接口構造線程對象

如何創建一個線程：子類Thread

子類Thread

Thread類本身實現了Runnable，盡管它的run方法什么都不做。應用程序可以繼承Thread，提供自己的run（）實現。

調用Thread.start（）以啟動新線程。

創建線程的方法：提供一個Runnable對象

提供一個Runnable對象

Runnable接口定義了一個方法run（），意在包含在線程中執行的代碼。

Runnable對象被傳遞給Thread構造函數。

如何創建線程

一個非常常見的習慣用法是用一個匿名的Runnable啟動一個線程，它消除了命名的類：
Runnable接口表示要由線程完成的工作。

為什么使用線程？

面對阻塞活動的表現

考慮一個Web服務器

在多處理器上的性能
干凈地處理自然并發

在Java中，線程是生活中的事實

示例：垃圾收集器在其自己的線程中運行（回憶：第8-1節）

我們都是并發程序員......

為了利用我們的多核處理器，我們必須編寫多線程代碼
好消息：它很多都是為你寫的

存在優秀的庫（java.util.concurrent）

壞消息：你仍然必須了解基本面

有效地使用庫

調試使用它們的程序

交錯和競爭

在具有單個執行核心的計算機系統中，在任何給定時刻只有一個線程正在執行。雖然有多線程，但只有一個核，每個時刻只能執行一個線程

單個內核的處理時間通過稱為時間分片的操作系統功能在進程和線程間共享。通過時間分片，在多個進程/線程之間共享處理器

今天的計算機系統具有多個處理器或具有多個執行核心的處理器。那么，我的計算機中只有一個或兩個處理器的多個并發線程如何處理？即使是多核CPU，進程/線程的數目也往往大于核的數目

當線程數多于處理器時，并發性通過時間分片模擬，這意味著處理器在線程之間切換。時間分片

時間分片的一個例子

三個線程T1，T2和T3可能在具有兩個實際處理器的機器上進行時間分割。

首先一個處理器運行線程T1，另一個運行線程T2，然后第二個處理器切換到運行線程T3。

線程T2只是暫停，直到下一個時間片在同一個處理器或另一個處理器上。

在大多數系統中，時間片發生不可預知的和非確定性的，這意味著線程可能隨時暫停或恢復。時間分片是由操作系統自動調度的

共享內存示例

線程之間的共享內存可能會導致微妙的錯誤！
例如：一家銀行擁有使用共享內存模式的取款機，因此所有取款機都可以在內存中讀取和寫入相同的賬戶對象。
將銀行簡化為一個賬戶，在余額變量中存儲美元余額，以及兩個操作存款和取款，只需添加或刪除美元即可：
客戶使用現金機器進行如下交易：
每筆交易只是一美元存款，然后是基礎提款，所以它應該保持賬戶余額不變。

在整個一天中，我們網絡中的每臺自動提款機正在處理一系列存款/提款交易。

在這一天結束時，無論有多少現鈔機在運行，或者我們處理了多少交易，我們都應該預期帳戶余額仍然為0.按理說，余額應該始終為0

但是如果我們運行這個代碼，我們經常發現在一天結束時的余額不是0.如果多個cashMachine（）調用同時運行

例如，在同一臺計算機上的不同處理器上

那么在一天結束時余額可能不會為零。為什么不？

交錯

假設兩臺取款機A和B同時在存款上工作。
以下是deposit（）步驟通常如何分解為低級處理器指令的方法：
當A和B同時運行時，這些低級指令彼此交錯...

余額現在是1

A的美元丟失了！

A和B同時讀取余額，計算多帶帶的最終余額，然后進行存儲以返回新的余額

沒有考慮到對方的存款。

競爭條件：程序的正確性（后置條件和不變量的滿足）取決于并發計算A和B中事件的相對時間。發生這種情況時，我們說“A與B競爭”。
事件的一些交織可能是可以的，因為它們與單個非并發進程會產生什么一致，但是其他交織會產生錯誤的答案 - 違反后置條件或不變量。

調整代碼將無濟于事

所有這些版本的銀行賬戶代碼都具有相同的競爭條件！
你不能僅僅從Java代碼中看出處理器將如何執行它。
你不能說出原子操作是什么。

它不是原子，因為它只是一行Java。

僅僅因為平衡標識符只在一行中出現一次才平衡一次。單行，單條語句都未必是原子的

Java編譯器不會對您的代碼生成的低級操作做出任何承諾。是否原子，由JVM確定

一個典型的現代Java編譯器為這三個版本生成完全相同的代碼！

競爭條件
關鍵的教訓是，你無法通過觀察一個表達來判斷它是否會在競爭條件下安全。
競爭條件也被稱為“線程干擾”

現在不僅是自動取款機模塊，而且賬戶也是模塊。
模塊通過相互發送消息進行交互。

傳入的請求被放入一個隊列中，一次處理一個請求。

發件人在等待對其請求的回答時不停止工作。它處理來自其自己隊列的更多請求。對其請求的回復最終會作為另一條消息返回。

消息傳遞能否解決競爭條件？

不幸的是，消息傳遞并不能消除競爭條件的可能性。消息傳遞機制也無法解決競爭條件問題

假設每個賬戶都支持收支平衡和撤銷操作，并帶有相應的消息。

兩臺A和B取款機的用戶都試圖從同一賬戶中提取一美元。

他們首先檢查余額，以確保他們永遠不會超過賬戶余額，因為透支會觸發大銀行的處罰。

問題是再次交錯，但是這次將消息交給銀行賬戶，而不是A和B所執行的指令。仍然存在消息傳遞時間上的交錯
如果賬戶以一美元開始，那么什么交錯的信息會欺騙A和B，使他們認為他們既可以提取一美元，從而透支賬戶？

使用測試發現競爭條件非常困難。很難測試和調試因為競爭條件導致的錯誤

即使一次測試發現了一個錯誤，也可能很難將其本地化到引發該錯誤的程序部分。 - - 為什么？

并發性錯誤表現出很差的重現性。因為交錯的存在，導致很難復現錯誤

很難讓它們以同樣的方式發生兩次。

指令或消息的交織取決于受環境強烈影響的事件的相對時間。

延遲是由其他正在運行的程序，其他網絡流量，操作系統調度決策，處理器時鐘速度的變化等引起的。

每次運行包含競爭條件的程序時，您都可能得到不同的行為。

Heisenbugs和Bohrbugs

一個heisenbug是一個軟件錯誤，當一個人試圖研究它時，它似乎消失或改變了它的行為。
順序編程中幾乎所有的錯誤都是bohrbugs。

并發性很難測試和調試！

當您嘗試用println或調試器查看heisenbug時，甚至可能會消失！增加打印語句甚至導致這種錯誤消失！?

原因是打印和調試比其他操作慢得多，通常慢100-1000倍，所以它們會顯著改變操作的時間和交錯。神奇的原因

因此，將一個簡單的打印語句插入到cashMachine（）中：
...突然間，平衡總是0，并且錯誤似乎消失了。但它只是被掩蓋了，并沒有真正固定。

3.5干擾線程自動交錯的一些操作

Thread.sleep（）方法
使用Thread.sleep（time）暫停執行：導致當前線程暫停指定時間段的執行。線程的休眠

這是使處理器時間可用于其他線程或可能在同一臺計算機上運行的其他應用程序的有效方法。將某個線程休眠，意味著其他線程得到更多的執行機會

線程睡眠不會丟失當前線程獲取的任何監視器或鎖。進入休眠的線程不會失去對現有監視器或鎖的所有權

Thread.interrupt（）方法
一個線程通過調用Thread對象上的中斷來發送一個中斷，以便使用interrupt（）方法中斷的線程 向線程發出中斷信號

t.interrupt（）在其他線程里向t發出中斷信號

要檢查線程是否中斷，請使用isInterrupted（）方法。檢查線程是否被中斷

t.isInterrupted（）檢查t是否已在中斷狀態中

中斷表示線程應該停止正在執行的操作并執行其他操作。 當某個線程被中斷后，一般來說應停止其run（）中的執行，取決于程序員在run（）中處理

由程序員決定線程是如何響應中斷的，但線程終止是非常常見的。 一般來說，線程在收到中斷信號時應該中斷，直接終止

但是，線程收到其他線程發來的中斷信號，并不意味著一定要“停止”...

Thread.yield（）方法
這種靜態方法主要用于通知系統當前線程愿意“放棄CPU”一段時間。使用該方法，線程告知調度器：我可以放棄CPU的占用權，從而可能引起調度器喚醒其他線程。

總體思路是：線程調度器將選擇一個不同的線程來運行而不是當前的線程。

這是線程編程中很少使用的方法，因為調度應該由調度程序負責。盡量避免在代碼中使用

Thread.join（）方法
join（）方法用于保存當前正在運行的線程的執行，直到指定的線程死亡（執行完畢）。讓當前線程保持執行，直到其執行結束

在正常情況下，我們通常擁有多個線程，線程調度程序調度線程，但不保證線程執行的順序。一般不需要這種顯式指定線程執行次序

通過使用join（）方法，我們可以讓一個線程等待另一個線程。

并發性：同時運行多個計算
共享內存和消息傳遞參數

進程和線程

進程就像一臺虛擬計算機;線程就像一個虛擬處理器

競爭條件

結果的正確性（后置條件和不變量）取決于事件的相對時間

多個線程共享相同的可變變量，但不協調他們正在做的事情。

這是不安全的，因為程序的正確性可能取決于其低級操作的時間安排事故。

這些想法主要以糟糕的方式與我們的優秀軟件的關鍵屬性相關聯。

并發是必要的，但它會導致嚴重的正確性問題：

從錯誤安全。并發性錯誤是找到并修復最難的錯誤之一，需要仔細設計才能避免。

容易明白。預測并發代碼如何與其他并發代碼交錯對于程序員來說非常困難。最好以這樣的方式設計代碼，程序員根本不必考慮交錯。

競爭條件：多個線程共享相同的可變變量，但不協調他們正在做的事情。

這是不安全的，因為程序的正確性可能取決于其低級操作時間的事故。
線程之間的“競爭條件”：作用于同一個可變數據上的多線程，彼此之間存在對該數據的訪問競爭并導致交錯，導致postcondition可能被違反，這是不安全的。

線程安全的意思

如果數據類型或靜態方法在從多個線程使用時行為正確，則無論這些線程如何執行，都無需線程安全，也不需要調用代碼進行額外協調。線程安全：ADT或方法在多線程中要執行正確

如何捕捉這個想法？

“正確行為”是指滿足其規范并保留其不變性;不違反規范，保持RI

“不管線程如何執行”意味著線程可能在多個處理器上或在同一個處理器上進行時間片化;與多少處理器，如何調度線程，均無關

“沒有額外的協調”意味著數據類型不能在與定時有關的調用方上設置先決條件，如“在set（）進行時不能調用get（）”。不需要在spec中強制要求客戶端滿足某種“線程安全”的義務

還記得迭代器嗎？這不是線程安全的。

迭代器的規范說，你不能在迭代它的同時修改一個集合。
這是一個與調用程序相關的與時間有關的前提條件，如果違反它，Iterator不保證行為正確。

線程安全意味著什么：remove（）的規范

作為這種非本地契約現象的一個癥狀，考慮Java集合類，這些類通常記錄在客戶端和實現者之間的非常明確的契約中。

嘗試找到它在客戶端記錄關鍵要求的位置，以便在迭代時無法修改集合。

線程安全的四種方法

監禁數據共享。不要在線程之間共享變量。

共享不可變數據。使共享數據不可變。

線程安全數據類型共享線程安全的可變數據。將共享數據封裝在為您協調的現有線程安全數據類型中。

同步 同步機制共享共享線程不安全的可變數據，對外即為線程安全的ADT。使用同步來防止線程同時訪問變量。同步是您構建自己的線程安全數據類型所需的。

不要共享：在多帶帶的線程中隔離可變狀態
不要改變：只共享不可變的狀態
如果必須共享可變狀態，請使用線程安全數據類型或同步

線程監禁是一個簡單的想法：

通過將數據監禁在單個線程中，避免在可變數據上進行競爭。將可變數據監禁在單一線程內部，避免競爭

不要讓任何其他線程直接讀取或寫入數據。不允許任何線程直接讀寫該數據

由于共享可變數據是競爭條件的根本原因，監禁通過不共享可變數據來解決。核心思想：線程之間不共享可變數據類型

局部變量總是受到線程監禁。局部變量存儲在堆棧中，每個線程都有自己的堆棧。一次運行的方法可能會有多個調用，但每個調用都有自己的變量專用副本，因此變量本身受到監禁。

如果局部變量是對象引用，則需要檢查它指向的對象。 如果對象是可變的，那么我們要檢查對象是否被監禁 - 不能引用它，它可以從任何其他線程訪問（而不是別名）。

避免全局變量

這個類在getInstance（）方法中有一個競爭

兩個線程可以同時調用它并最終創建PinballSimulator對象的兩個副本，這違反了代表不變量。

假設兩個線程正在運行getInstance（）。
對于兩個線程正在執行的每對可能的行號，是否有可能違反不變量？
全局靜態變量不會自動受到線程監禁。

如果你的程序中有靜態變量，那么你必須提出一個論點，即只有一個線程會使用它們，并且你必須清楚地記錄這個事實。 [在代碼中記錄 - 第4章]

更好的是，你應該完全消除靜態變量。

isPrime（）方法從多個線程調用并不安全，其客戶端甚至可能不會意識到它。

原因是靜態變量緩存引用的HashMap被所有對isPrime（）的調用共享，并且HashMap不是線程安全的。

如果多個線程同時通過調用cache.put（）來改變地圖，那么地圖可能會以與上一次讀數中的銀行賬戶損壞相同的方式被破壞。

如果幸運的話，破壞可能會導致哈希映射深處發生異常，如NullPointerException或IndexOutOfBoundsException。

但它也可能會悄悄地給出錯誤的答案。

實現線程安全的第二種方法是使用不可變引用和數據類型。使用不可變數據類型和不可變引用，避免多線程之間的競爭條件

不變性解決競爭條件的共享可變數據原因，并簡單地通過使共享數據不可變來解決它。

final變量是不可變的引用，所以聲明為final的變量可以安全地從多個線程訪問。

你只能讀取變量，而不能寫入變量。

因為這種安全性只適用于變量本身，我們仍然必須爭辯變量指向的對象是不可變的。

不可變對象通常也是線程安全的。不可變數據通常是線程安全的
我們說“通常”，因為不可變性的當前定義對于并發編程而言過于松散。

如果一個類型的對象在整個生命周期中始終表示相同的抽象值，則類型是不可變的。

但實際上，只要這些突變對于客戶是不可見的，例如有益的突變（參見3.3章節），實際上允許類型自由地改變其代表。

如緩存，延遲計算和數據結構重新平衡

對于并發性，這種隱藏的變異是不安全的。

使用有益突變的不可變數據類型必須使用鎖使自己線程安全。如果ADT中使用了有益突變，必須要通過“加鎖”機制來保證線程安全

更強的不變性定義

為了確信一個不可變的數據類型是沒有鎖的線程安全的，我們需要更強的不變性定義：

沒有變值器方法

所有字段都是私人的和最終的

沒有表示風險

表示中的可變對象沒有任何突變

甚至不能是有益的突變

如果你遵循這些規則，那么你可以確信你的不可變類型也是線程安全的。
不要提供“setter”方法 - 修改字段引用的字段或對象的方法。
使所有字段最終和私有。
不要讓子類重寫方法。

最簡單的方法是將類聲明為final。

更復雜的方法是使構造函數保持私有狀態，并使用工廠方法構造實例。

如果實例字段包含對可變對象的引用，請不要允許更改這些對象：

不要提供修改可變對象的方法。

不要共享對可變對象的引用。

不要存儲對傳遞給構造函數的外部可變對象的引用;如有必要，創建副本，并存儲對副本的引用。

同樣，必要時創建內部可變對象的副本，以避免在方法中返回原件。

實現線程安全的第三個主要策略是將共享可變數據存儲在現有的線程數據類型中。 如果必須要用mutable的數據類型在多線程之間共享數據，則要使用線程安全的數據類型。

當Java庫中的數據類型是線程安全的時，其文檔將明確說明這一事實。在JDK中的類，文檔中明確指明了是否線程

一般來說，JDK同時提供兩個相同功能的類，一個是線程安全的，另一個不是。線程安全的類一般性能上受影響

原因是這個報價表明：與不安全類型相比，線程安全數據類型通常會導致性能損失。

線程安全集合

Java中的集合接口

列表，設置，地圖

具有不是線程安全的基本實現。集合類都是線程不安全的

ArrayList，HashMap和HashSet的實現不能從多個線程安全地使用。

Collections API提供了一組包裝器方法來使集合線程安全，同時仍然可變。 Java API提供了進一步的裝飾器

這些包裝器有效地使集合的每個方法相對于其他方法是原子的。

原子動作一次有效地發生

它不會將其內部操作與其他操作的內部操作交錯，并且在整個操作完成之前，操作的任何效果都不會被其他線程看到，因此它從未部分完成。

線程安全包裝

public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static SortedMap synchronizedSortedMap(SortedMap m);

包裝實現將他們所有的實際工作委托給指定的集合，但在集合提供的基礎上添加額外的功能。
這是裝飾者模式的一個例子（參見5-3節）
這些實現是匿名的;該庫不提供公共類，而是提供靜態工廠方法。
所有這些實現都可以在Collections類中找到，該類僅由靜態方法組成。
同步包裝將自動同步（線程安全）添加到任意集合。

不要繞開包裝

確保拋棄對底層非線程安全集合的引用，并僅通過同步包裝來訪問它。
新的HashMap只傳遞給synchronizedMap（），并且永遠不會存儲在其他地方。
底層的集合仍然是可變的，引用它的代碼可以規避不變性。
在使用synchronizedMap（hashMap）之后，不要再參數hashMap共享給其他線程，不要保留別名，一定要徹底銷毀

迭代器仍然不是線程安全的

盡管方法調用集合本身（get（），put（），add（）等）現在是線程安全的，但從集合創建的迭代器仍然不是線程安全的。 即使在線程安全的集合類上，使用迭代器也是不安全的
此迭代問題的解決方案將是在需要迭代它時獲取集合的鎖。除非使用鎖機制

原子操作不足以阻止競爭

您使用同步收集的方式仍可能存在競爭條件。
考慮這個代碼，它檢查列表是否至少有一個元素，然后獲取該元素：
即使您將list放入同步列表中，此代碼仍可能存在競爭條件，因為另一個線程可能會刪除isEmpty（）調用和get（）調用之間的元素。

同步映射確保containsKey（），get（）和put（）現在是原子的，所以從多個線程使用它們不會損害映射的rep不變量。
但是這三個操作現在可以以任意方式相互交織，這可能會破壞緩存中需要的不變量：如果緩存將整數x映射到值f，那么當且僅當f為真時x是素數。
如果緩存永遠失敗這個不變量，那么我們可能會返回錯誤的結果。

注意

我們必須爭論containsKey（），get（）和put（）之間的競爭不會威脅到這個不變量。

containsKey（）和get（）之間的競爭是無害的，因為我們從不從緩存中刪除項目 - 一旦它包含x的結果，它將繼續這樣做。

containsKey（）和put（）之間存在競爭。 因此，最終可能會有兩個線程同時測試同一個x的初始值，并且兩個線程都會調用put（）與答案。 但是他們都應該用相同的答案來調用put（），所以無論哪個人贏得比賽并不重要 - 結果將是相同的。

......在注釋中自證線程
需要對安全性進行這種仔細的論證 - 即使在使用線程安全數據類型時 - 也是并發性很難的主要原因。

一個簡短的總結
通過共享可變數據的競爭條件實現安全的三種主要方式：

禁閉：不共享數據。

不變性：共享，但保持數據不變。

線程安全數據類型：將共享的可變數據存儲在單個線程安全數據類型中。

減少錯誤保證安全。

我們正試圖消除一大類并發錯誤，競爭條件，并通過設計消除它們，而不僅僅是意外的時間。

容易明白。

應用這些通用的，簡單的設計模式比關于哪種線程交叉是可能的而哪些不可行的復雜論證更容易理解。

準備好改變。

我們在一個線程安全參數中明確地寫下這些理由，以便維護程序員知道代碼依賴于線程安全。

最復雜也最有價值的threadsafe策略

回顧
數據類型或函數的線程安全性：在從多個線程使用時行為正確，無論這些線程如何執行，無需額外協調。線程安全不應依賴于偶然

原理：并發程序的正確性不應該依賴于時間事件。

有四種策略可以使代碼安全并發：

監禁：不要在線程之間共享數據。

不變性：使共享數據不可變。

使用現有的線程安全數據類型：使用為您協調的數據類型。

前三種策略的核心思想：

避免共享→即使共享，也只能讀/不可寫（immutable）→即使可寫（mutable），共享的可寫數據應該自己具備在多線程之間協調的能力，即“使用線程安全的mutable ADT”

同步和鎖定

由于共享可變數據的并發操作導致的競爭條件是災難性的錯誤 - 難以發現，重現和調試 - 我們需要一種共享內存的并發模塊以實現彼此同步的方式。
很多時候，無法滿足上述三個條件...
使代碼安全并發的第四個策略是：

同步和鎖：防止線程同時訪問共享數據。

程序員來負責多線程之間對可變數據的共享操作，通過“同步”策略，避免多線程同時訪問數據

鎖是一種同步技術。

鎖是一種抽象，最多允許一個線程擁有它。保持鎖定是一條線程告訴其他現成：“我正在改變這個東西，現在不要觸摸它。”

使用鎖機制，獲得對數據的獨家改變權，其他線程被阻塞，不得訪問

使用鎖可以告訴編譯器和處理器你正在同時使用共享內存，所以寄存器和緩存將被刷新到共享存儲，確保鎖的所有者始終查看最新的數據。
阻塞一般意味著一個線程等待（不再繼續工作）直到事件發生。

兩種鎖定操作

acquire允許線程獲取鎖的所有權。

如果一個線程試圖獲取當前由另一個線程擁有的鎖，它會阻塞，直到另一個線程釋放該鎖。

在這一點上，它將與任何其他嘗試獲取鎖的線程競爭。

一次只能有一個線程擁有該鎖。

release放棄鎖的所有權，允許另一個線程獲得它的所有權。

如果另一個線程（如線程2）持有鎖l，線程1上的獲取（l）將會阻塞。它等待的事件是線程2執行釋放（l）。

此時，如果線程1可以獲取l，則它繼續運行其代碼，并擁有鎖的所有權。

另一個線程（如線程3）也可能在獲取（l）時被阻塞。線程1或3將采取鎖定并繼續。另一個將繼續阻塞，再次等待釋放（l）。

（1）同步塊和方法

鎖定

鎖是如此常用以至于Java將它們作為內置語言功能提供。鎖是Java的語言提供的內嵌機制

每個對象都有一個隱式關聯的鎖 - 一個String，一個數組，一個ArrayList，每個類及其所有實例都有一個鎖。

即使是一個不起眼的Object也有一個鎖，因此裸露的Object通常用于顯式鎖定：

但是，您不能在Java的內部鎖上調用acquire和release。 而是使用synchronized語句來獲取語句塊持續時間內的鎖定：
像這樣的同步區域提供互斥性：一次只能有一個線程處于由給定對象的鎖保護的同步區域中。
換句話說，你回到了順序編程世界，一次只運行一個線程，至少就其他同步區域而言，它們指向同一個對象。

鎖定保護對數據的訪問

鎖用于保護共享數據變量。鎖保護共享數據

如果所有對數據變量的訪問都被相同的鎖對象保護（被同步塊包圍），那么這些訪問將被保證為原子 - 不被其他線程中斷。

使用以下命令獲取與對象obj關聯的鎖定：
synchronized（obj）{...}

它阻止其他線程進入synchronized（obj）直到線程t完成其同步塊為止。

鎖只與其他獲取相同鎖的線程相互排斥。 所有對數據變量的訪問必須由相同的鎖保護。 注意：要互斥，必須使用同一個鎖進行保護

你可以在單個鎖后面保護整個變量集合，但是所有模塊必須同意他們將獲得并釋放哪個鎖。

監視器模式

在編寫類的方法時，最方便的鎖是對象實例本身，即this。用ADT自己做鎖
作為一種簡單的方法，我們可以通過在synchronized(this)內包裝所有對rep的訪問來守護整個類的表示。
監視器模式：監視器是一個類，它們的方法是互斥的，所以一次只能有一個線程在類的實例中。
每一個觸及表示的方法都必須用鎖來保護，甚至像length（）和toString（）這樣的顯而易見的小代碼。
這是因為必須保護讀取以及寫入 - 如果讀取未被保留，則他們可能能夠看到處于部分修改狀態的rep。
如果將關鍵字synchronized添加到方法簽名中，Java將像您在方法主體周圍編寫synchronized（this）一樣操作。

同步方法

同一對象上的同步方法的兩次調用不可能交錯。對同步的方法，多個線程執行它時不允許交錯，也就是說“按原子的串行方式執行”

當一個線程正在為一個對象執行一個同步方法時，所有其他調用同一對象的同步方法的線程將阻塞（暫停執行），直到第一個線程完成對象。

當一個同步方法退出時，它會自動建立與同一對象的同步方法的任何后續調用之間的發生前關系。

這保證對所有線程都可見對象狀態的更改。

同步語句/塊

同步方法和同步（this）塊之間有什么區別？

與synchronized方法不同，synchronized語句必須指定提供內部鎖的對象。

同步語句對于通過細粒度同步來提高并發性非常有用。

二者有何區別？

后者需要顯式的給出鎖，且不一定非要是this

后者可提供更細粒度的并發控制

鎖定規則

鎖定規則是確保同步代碼是線程安全的策略。
我們必須滿足兩個條件：

每個共享的可變變量必須由某個鎖保護。除了在獲取該鎖的同步塊內，數據可能不會被讀取或寫入。任何共享的可變變量/對象必須被鎖所保護

如果一個不變量涉及多個共享的可變變量（它甚至可能在不同的對象中），那么涉及的所有變量都必須由相同的鎖保護。一旦線程獲得鎖定，必須在釋放鎖定之前重新建立不變量。涉及到多個mutable變量的時候，它們必須被一個鎖所保護

這里使用的監視器模式滿足這兩個規則。代表中所有共享的可變數據 - 代表不變量依賴于 - 都被相同的鎖保護。

發生-前關系

這種發生-前關系，只是保證多個線程共享的對象通過一個特定語句寫入的內容對另一個讀取同一對象的特定語句是可見的。
這是為了確保內存一致性。
發生-前關系（a→ b）是兩個事件的結果之間的關系，因此如果在事件發生之前發生一個事件，那么結果必須反映出，即使這些事件實際上是無序執行的。

這涉及基于并發系統中的事件對的潛在因果關系對事件進行排序。

它由Leslie Lamport制定。

正式定義為事件中最不嚴格的部分順序，以便：

如果事件a和b在同一個過程中發生，如果在事件b發生之前發生了事件a則a→b;

如果事件a是發送消息，并且事件b是在事件a中發送的消息的接收，則a→b。

像所有嚴格的偏序一樣，發生-前關系是傳遞的，非自反的和反對稱的。

原子數據訪問的關鍵字volatile

使用volatile（不穩定）變量可降低內存一致性錯誤的風險，因為任何對volatile變量的寫入都會在后續讀取該變量的同時建立happen-before關系。
這意味著對其他線程總是可見的對volatile變量的更改。
更重要的是，這也意味著當一個線程讀取一個volatile變量時，它不僅會看到volatile的最新變化，還會看到導致變化的代碼的副作用。
這是一個輕量級同步機制。
使用簡單的原子變量訪問比通過同步代碼訪問這些變量更有效，但需要程序員更多的關注以避免內存一致性錯誤。

（3）到處使用同步？

那么線程安全是否只需將synchronized關鍵字放在程序中的每個方法上？
不幸的是，
首先，你實際上并不想同步方法。

同步對您的程序造成很大的損失。 同步機制給性能帶來極大影響

由于需要獲取鎖（并刷新高速緩存并與其他處理器通信），因此進行同步方法調用可能需要更長的時間。

由于這些性能原因，Java會將許多可變數據類型默認為不同步。當你不需要同步時，不要使用它。除非必要，否則不要用.Java中很多mutable的類型都不是threadsafe就是這個原因

另一個以更慎重的方式使用同步的理由是，它最大限度地減少了訪問鎖的范圍。盡可能減小鎖的范圍

為每個方法添加同步意味著你的鎖是對象本身，并且每個引用了你的對象的客戶端都會自動引用你的鎖，它可以隨意獲取和釋放。

您的線程安全機制因此是公開的，可能會受到客戶的干擾。

與使用作為表示內部對象的鎖并使用synchronized（）塊適當并節省地獲取相比。
最后，到處使用同步并不夠實際。

在沒有思考的情況下同步到一個方法上意味著你正在獲取一個鎖，而不考慮它是哪個鎖，或者是否它是保護你將要執行的共享數據訪問的正確鎖。

假設我們試圖通過簡單地將synchronized同步到它的聲明來解決findReplace的同步問題：
public static synchronized boolean findReplace(EditBuffer buf, ...)

它確實會獲得一個鎖 - 因為findReplace是一個靜態方法，它將獲取findReplace恰好處于的整個類的靜態鎖定，而不是實例對象鎖定。

結果，一次只有一個線程可以調用findReplace - 即使其他線程想要在不同的緩沖區上運行，這些緩沖區應該是安全的，它們仍然會被阻塞，直到單個鎖被釋放。所以我們會遭受重大的性能損失。

synchronized關鍵字不是萬能的。
線程安全需要一個規范 - 使用監禁，不變性或鎖來保護共享數據。
這個紀律需要被寫下來，否則維護人員不會知道它是什么。

Synchronized不是靈丹妙藥，你的程序需要嚴格遵守設計原則，先試試其他辦法，實在做不到再考慮lock。
所有關于線程的設計決策也都要在ADT中記錄下來。

（4）活性：死鎖，饑餓和活鎖

活性
并發應用程序的及時執行能力被稱為活躍性。
三個子度量標準：

死鎖

饑餓

活鎖

（1）死鎖

如果使用得當，小心，鎖可以防止競爭狀況。
但是接下來的另一個問題就是丑陋的頭腦。
由于使用鎖需要線程等待（當另一個線程持有鎖時獲取塊），因此可能會陷入兩個線程正在等待對方的情況 - 因此都無法取得進展。
死鎖描述了兩個或更多線程永遠被阻塞的情況，等待對方。
死鎖：多個線程競爭鎖，相互等待對方釋放鎖
當并發模塊卡住等待對方執行某些操作時發生死鎖。
死鎖可能涉及兩個以上的模塊：死鎖的信號特征是依賴關系的一個循環，例如， A正在等待B正在等待C正在等待A，它們都沒有取得進展。
死鎖的丑陋之處在于它
線程安全的鎖定方法非常強大，但是（與監禁和不可變性不同）它將阻塞引入程序。
線程必須等待其他線程退出同步區域才能繼續。
在鎖定的情況下，當線程同時獲取多個鎖時會發生死鎖，并且兩個線程最終被阻塞，同時持有鎖，每個鎖都等待另一個鎖釋放。
不幸的是，監視器模式使得這很容易做到。

死鎖：

線程A獲取harry鎖（因為friend方法是同步的）。

然后線程B獲取snape上的鎖（出于同樣的原因）。

他們都獨立地更新他們各自的代表，然后嘗試在另一個對象上調用friend（） - 這要求他們獲取另一個對象上的鎖。

所以A正在拿著哈利等著斯內普，而B正拿著斯內普等著哈利。

兩個線程都卡在friend（）中，所以都不會管理退出同步區域并將鎖釋放到另一個區域。

這是一個經典的致命的擁抱。 該程序停止。

問題的實質是獲取多個鎖，并在等待另一個鎖釋放時持有某些鎖。

死鎖解決方案1：鎖定順序

對需要同時獲取的鎖定進行排序，并確保所有代碼按照該順序獲取鎖定。

在示例中，我們可能總是按照向導的名稱按字母順序獲取向導對象上的鎖定。

雖然鎖定順序很有用（特別是在操作系統內核等代碼中），但它在實踐中有許多缺點。
首先，它不是模塊化的 - 代碼必須知道系統中的所有鎖，或者至少在其子系統中。
其次，代碼在獲取第一個鎖之前可能很難或不可能確切知道它需要哪些鎖。 它可能需要做一些計算來弄清楚。

例如，想一想在社交網絡圖上進行深度優先搜索，在你開始尋找它們之前，你怎么知道哪些節點需要被鎖定？

死鎖解決方案2：粗略鎖定

要使用粗略鎖定 - 使用單個鎖來防止許多對象實例，甚至是程序的整個子系統。

例如，我們可能對整個社交網絡擁有一個鎖，并且對其任何組成部分的所有操作都在該鎖上進行同步。

在代碼中，所有的巫師都屬于一個城堡，我們只是使用該Castle對象的鎖來進行同步。

但是，它有明顯的性能損失。

如果你用一個鎖保護大量可變數據，那么你就放棄了同時訪問任何數據的能力。

在最糟糕的情況下，使用單個鎖來保護所有內容，您的程序可能基本上是順序的。

（2）饑餓

饑餓描述了線程無法獲得對共享資源的定期訪問并且無法取得進展的情況。

當共享資源被“貪婪”線程長時間停用時，會發生這種情況。

例如，假設一個對象提供了一個經常需要很長時間才能返回的同步方法。

如果一個線程頻繁地調用此方法，那么其他線程也需要經常同步訪問同一對象。

因為其他線程鎖時間太長，一個線程長時間無法獲取其所需的資源訪問權（鎖），導致無法往下進行。

（3）活鎖

線程通常會響應另一個線程的動作而行動。
如果另一個線程的動作也是對另一個線程動作的響應，則可能導致活鎖。
與死鎖一樣，活鎖線程無法取得進一步進展。
但是，線程并未被阻止 - 他們只是忙于響應對方恢復工作。
這與兩個試圖在走廊上相互傳遞的人相當：

阿爾方塞向左移動讓加斯頓通過，而加斯東向右移動讓阿爾方塞通過。

看到他們仍然互相阻攔，阿爾方塞向右移動，而加斯東向左移動。他們仍然互相阻攔，所以......

（5）wait（），notify（）和notifyAll（）

保護塊

防護區塊：這樣的區塊首先輪詢一個必須為真的條件才能繼續。
假設，例如guardedJoy是一種方法，除非另一個線程設置了共享變量joy，否則該方法不能繼續。

這種方法可以簡單地循環直到滿足條件，但是該循環是浪費的，因為它在等待時連續執行。 某些條件未得到滿足，所以一直在空循環檢測，直到條件被滿足。這是極大浪費。

wait（），notify（）和notifyAll（）

以下是針對任意Java對象o定義的：

o.wait（）：釋放o上的鎖，進入o的等待隊列并等待

o.notify（）：喚醒o的等待隊列中的一個線程

o.notifyAll（）：喚醒o的等待隊列中的所有線程

Object.wait（）

Object.wait（）會導致當前線程等待，直到另一個線程調用此對象的notify（）方法或notifyAll（）方法。換句話說，這個方法的行為就好像它只是執行調用wait（0）一樣。該操作使對象所處的阻塞/等待狀態，直到其他線程調用該對象的notify（）操作

Object.notify（）/ notifyAll（）

Object.notify（）喚醒正在等待該對象監視器的單個線程。如果任何線程正在等待這個對象，則選擇其中一個線程來喚醒。隨機選擇一個在該對象上調用等方法的線程，解除其阻塞狀態

線程通過調用其中一個等待方法在對象的監視器上等待。

在當前線程放棄對該對象的鎖定之前，喚醒的線程將無法繼續。

喚醒的線程將以通常的方式與其他可能正在主動競爭的線程競爭對該對象進行同步;例如，被喚醒的線程在作為下一個線程來鎖定這個對象時沒有可靠的特權或缺點。

此方法只應由作為此對象監視器所有者的線程調用。
線程以三種方式之一成為對象監視器的所有者：

通過執行該對象的同步實例方法。

通過執行同步對象的同步語句的主體。

對于Class類型的對象，通過執行該類的同步靜態方法。

在守衛塊中使用wait（）

wait（）的調用不會返回，直到另一個線程發出某個特殊事件可能發生的通知 - 盡管不一定是該線程正在等待的事件。
Object.wait（）會導致當前線程等待，直到另一個線程調用此對象的notify（）方法或notifyAll（）方法。
當wait（）被調用時，線程釋放鎖并暫停執行。
在將來的某個時間，另一個線程將獲得相同的鎖并調用Object.notifyAll（），通知所有等待該鎖的線程發生重要事件：
第二個線程釋放鎖定一段時間后，第一個線程重新獲取鎖定，并通過從等待的調用返回來恢復。

wait（），notify（）和notifyAll（）
調用對象o的方法的線程通常必須預先鎖定o：

回想一下：開發ADT的步驟
指定：定義操作（方法簽名和規約）。
測試：開發操作的測試用例。測試套件包含基于對操作的參數空間進行分區的測試策略。
代表：選擇一個代表。

首先實現一個簡單的，強大的代表。

寫下rep不變和抽象函數，并實現checkRep（），它在每個構造函數，生成器和增量器方法的末尾聲明了rep不變量。

+++同步

說出你的代表是線程安全的。

在你的類中作為注釋明確地寫下來，直接用rep不變量表示，以便維護者知道你是如何為類設計線程安全性的。

做一個安全論證

并發性很難測試和調試！
所以如果你想讓自己和別人相信你的并發程序是正確的，最好的方法是明確地說明它沒有競爭，并且記下來。在代碼中注釋的形式增加說明：該ADT采取了什么設計決策來保證線程安全

安全性參數需要對模塊或程序中存在的所有線程及其使用的數據進行編目，并針對您使用的四種技術中的哪一種來防止每個數據對象或變量的競爭：監禁，不可變性，線程安全數據類型或同步。采取了四種方法中的哪一種？

當你使用最后兩個時，你還需要爭辯說，對數據的所有訪問都是適當的原子

也就是說，你所依賴的不變量不受交織威脅。如果是后兩種，還需考慮對數據的訪問都是原子的，不存在交錯

用于監禁的線程安全論證

因為您必須知道系統中存在哪些線程以及他們有權訪問哪些對象，因此在我們僅就數據類型進行爭論時，監禁通常不是一種選擇。 除非你知道線程訪問的所有數據，否則Confinement無法徹底保證線程安全

如果數據類型創建了自己的一組線程，那么您可以討論關于這些線程的監禁。

否則，線程從外部進入，攜帶客戶端調用，并且數據類型可能無法保證哪些線程具有對什么的引用。

因此，在這種情況下，Confinement不是一個有用的論證。

通常我們在更高層次使用約束，討論整個系統，并論證為什么我們不需要線程安全的某些模塊或數據類型，因為它們不會通過設計在線程間共享。除非是在ADT內部創建的線程，可以清楚得知訪問數據有哪些

并發程序設計的目標

并發程序是否可以避免bug？

我們關心三個屬性：

安全。 并發程序是否滿足其不變量和規約？ 訪問可變數據的競爭會威脅到安全。 安全問題：你能證明一些不好的事情從未發生過？

活性。 程序是否繼續運行，并最終做你想做的事情，還是會陷入永遠等待事件永遠不會發生的地方？ 你能證明最終會發生什么好事嗎？ 死鎖威脅到活性。

公平。 并發模塊具有處理能力以在計算上取得進展。 公平主要是OS線程調度器的問題，但是你可以通過設置線程優先級來影響它。

實踐中的并發

在真正的項目中通常采用什么策略？

庫數據結構不使用同步（為單線程客戶端提供高性能，同時讓多線程客戶端在頂層添加鎖定）或監視器模式。

具有許多部分的可變數據結構通常使用粗粒鎖定或線程約束。大多數圖形用戶界面工具包遵循以下方法之一，因為圖形用戶界面基本上是一個可變對象的大型可變樹。 Java Swing，圖形用戶界面工具包，使用線程約束。只有一個專用線程被允許訪問Swing的樹。其他線程必須將消息傳遞到該專用線程才能訪問該樹。

安全失敗帶來虛假的安全感。生存失敗迫使你面對錯誤。有利于活躍而不是安全的誘惑。

搜索通常使用不可變的數據類型。多線程很容易，因為涉及的所有數據類型都是不可變的。不會有競爭或死鎖的風險。

操作系統通常使用細粒度的鎖來獲得高性能，并使用鎖定順序來處理死鎖問題。

數據庫使用與同步區域類似的事務來避免競爭條件，因為它們的影響是原子的，但它們不必獲取鎖定，盡管事務可能會失敗并在事件發生時被回滾。數據庫還可以管理鎖，并自動處理鎖定順序。將在數據庫系統課程中介紹。

總結

生成一個安全無漏洞，易于理解和可以隨時更改的并發程序需要仔細思考。

只要你嘗試將它們固定下來，Heisenbugs就會消失，所以調試根本不是實現正確線程安全代碼的有效方法。

線程可以以許多不同的方式交錯操作，即使是所有可能執行的一小部分，也永遠無法測試。

創建關于數據類型的線程安全參數，并在代碼中記錄它們。
獲取一個鎖允許一個線程獨占訪問該鎖保護的數據，強制其他線程阻塞 - 只要這些線程也試圖獲取同一個鎖。
監視器使用通過每種方法獲取的單個鎖來引用數據類型的代表。
獲取多個鎖造成的阻塞會造成死鎖的可能性。
什么是并發編程？
進程，線程和時間片
交織和競爭條件
線程安全

戰略1：監禁

策略2：不可變性

策略3：使用線程安全數據類型

策略4：鎖定和同步

如何做安全論證