操作系統(tǒng)（四）——進(jìn)程管理(下)
一、進(jìn)程同步與互斥
1.進(jìn)程同步的基本概念
多道程序環(huán)境下，進(jìn)程是并發(fā)執(zhí)行的，不同進(jìn)程間存在著不同的相互制約關(guān)系。為了協(xié)調(diào)進(jìn)程之間的相互制約關(guān)系，達(dá)到資源共享和進(jìn)程協(xié)作，避免進(jìn)程之間的沖突，引入了進(jìn)程同步的概念。
（1）臨界資源（critical resource）
對臨界資源的訪問，必須互斥的進(jìn)行。每個進(jìn)程中，訪問臨界資源的那段代碼稱為臨界區(qū)。
為了保證臨界資源的正確使用，可以把臨界資源的訪問過程分為四個部分。
1） 進(jìn)入?yún)^(qū)。為了進(jìn)入臨界區(qū)使用臨界資源，在進(jìn)入?yún)^(qū)要檢查可否進(jìn)入臨界區(qū)。
2） 臨界區(qū)。進(jìn)程中訪問臨界資源的那段代碼。
3） 退出區(qū)。將正在訪問臨界區(qū)的標(biāo)志清除。
4） 剩余區(qū)。代碼中的其余部分。
（2）同步（synchronism）
同步也稱為直接制約關(guān)系（直接制約關(guān)系：進(jìn)程需等待來自其他進(jìn)程的信息而產(chǎn)生的協(xié)作關(guān)系。進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相關(guān)進(jìn)程間），它是為完成某種任務(wù)而建立的兩個或多個進(jìn)程。這些進(jìn)程因?yàn)樾枰谀承┪恢蒙蠀f(xié)調(diào)他們的工作次序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。進(jìn)程間的直接制約關(guān)系就是它們之間的相互合作。
進(jìn)程同步是指多個進(jìn)程之間協(xié)調(diào)彼此的執(zhí)行順序，以便在共享資源的情況下保持?jǐn)?shù)據(jù)的一致性和正確性。在多任務(wù)操作系統(tǒng)中，每個進(jìn)程都有自己的執(zhí)行時間片段，當(dāng)多個進(jìn)程同時訪問共享資源時，可能會引發(fā)沖突和競爭條件，導(dǎo)致數(shù)據(jù)錯誤或不一致。為了解決這些問題，需要使用進(jìn)程同步機(jī)制來確保進(jìn)程之間的協(xié)調(diào)和同步。常見的進(jìn)程同步方法包括信號量、互斥鎖、條件變量等。
同步，就是并發(fā)進(jìn)程/線程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種相互制約的等待與互通信息稱為進(jìn)程/線程同步。
（3）互斥（mutual exclusion）
互斥亦稱間接制約關(guān)系（進(jìn)程的間接制約關(guān)系：是指進(jìn)程獨(dú)占分配到的部分或全部共享資源（共享變量）而產(chǎn)生的競爭關(guān)系。進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相關(guān)進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間）。當(dāng)一個進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時，另一個進(jìn)程必須等待，當(dāng)占用臨界資源的進(jìn)程退出臨界區(qū)后，另一個進(jìn)程才允許去訪問此臨界資源。
進(jìn)程的互斥（間接作用）：由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，即多個進(jìn)程不能同時使用同一個資源，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。
進(jìn)程同步的目的是為了協(xié)調(diào)多個進(jìn)程或線程的執(zhí)行順序，以便它們能夠按照一定的規(guī)則協(xié)作完成某個任務(wù)。例如，在生產(chǎn)者消費(fèi)者模型中，生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程需要按照一定的順序交替執(zhí)行，以保證生產(chǎn)者生產(chǎn)的數(shù)據(jù)能夠被消費(fèi)者及時消費(fèi)。為了實(shí)現(xiàn)這種協(xié)作，需要使用進(jìn)程同步機(jī)制，如信號量、條件變量等，來確保進(jìn)程之間按照一定的順序進(jìn)行協(xié)作。
2.進(jìn)程互斥的基本方法
（1）軟件實(shí)現(xiàn)方法
（2）硬件實(shí)現(xiàn)方法
中斷屏蔽方法
當(dāng)一個進(jìn)程正在使用處理器執(zhí)行他的臨界區(qū)代碼時，要防止去其他進(jìn)程在進(jìn)入其臨界區(qū)訪問的最簡單方法就是禁止一切中斷的發(fā)生，或稱之為屏蔽中斷、關(guān)中斷。因?yàn)镃PU只有在發(fā)生中斷時引起進(jìn)程的調(diào)度和切換，這樣屏蔽中斷就能保證當(dāng)前運(yùn)行進(jìn)程將臨界區(qū)代碼順利的執(zhí)行完，然后再開中斷。
這種方法限制了處理器交替執(zhí)行程序的能力，因此執(zhí)行的效率將會明顯降低。對內(nèi)核來說，當(dāng)它執(zhí)行更新變量或列表的幾條指令期間關(guān)中斷是很方便的，但將關(guān)中斷的權(quán)力交給用戶則很不明智，若一個進(jìn)程關(guān)中斷之后不再打開終端，則系統(tǒng)可能會因此終止。
硬件指令——TestAndSet指令
TestAndSet指令可以用于實(shí)現(xiàn)原子操作，以避免多個線程同時訪問共享資源的問題。但是，如果多個線程同時使用TestAndSet指令來競爭同一個資源，可能會導(dǎo)致死鎖。這是因?yàn)門estAndSet指令會不斷地循環(huán)等待直到資源可用，而如果多個線程都在等待同一個資源，它們可能就會陷入無限循環(huán)，形成死鎖。
但是，TestAndSet指令本身不會導(dǎo)致饑餓，因?yàn)樗皇且粋€原子操作，不會導(dǎo)致其他線程無法訪問資源。如果發(fā)生饑餓，通常是由于其他原因，例如調(diào)度算法或鎖的實(shí)現(xiàn)方式不當(dāng)。
硬件指令——Swap指令
Swap指令用于實(shí)現(xiàn)原子操作，可以用于交換兩個變量的值。如果多個線程同時使用Swap指令來競爭同一個變量，可能會導(dǎo)致饑餓。這是因?yàn)槊總€線程都需要等待其他線程完成Swap操作，才能繼續(xù)執(zhí)行自己的操作。如果某個線程一直沒有機(jī)會執(zhí)行Swap操作，它可能會一直被阻塞，導(dǎo)致饑餓。
但是，Swap指令本身不會導(dǎo)致死鎖。因?yàn)镾wap操作是原子的，只有一個線程能夠成功執(zhí)行Swap操作，其他線程都會等待。如果多個線程同時等待Swap操作完成，它們可能會陷入無限循環(huán)，但不會形成死鎖。
硬件方法優(yōu)點(diǎn)：使用與任意數(shù)目的進(jìn)程，不管是單處理器還是多處理器：簡單、容易驗(yàn)證其正確性?？梢灾С诌M(jìn)程內(nèi)有多個臨界區(qū)，只需要為每個臨界區(qū)設(shè)立一個布爾變量。
硬件方法的缺點(diǎn)：進(jìn)程等待進(jìn)入臨界區(qū)時要耗費(fèi)處理器時間，不能實(shí)現(xiàn)讓權(quán)等待。從等待進(jìn)程中隨機(jī)選擇一個進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上，從而導(dǎo)致“饑餓”現(xiàn)象。
互斥鎖（mutex lock）
互斥鎖的實(shí)現(xiàn)是通過在代碼中加入一段互斥代碼區(qū)域，這段代碼區(qū)域只能被一個線程訪問。當(dāng)一個線程進(jìn)入互斥代碼區(qū)域時，它會請求互斥鎖，如果此時互斥鎖已經(jīng)被其他線程占用，則該線程將被阻塞，直到互斥鎖被釋放。
互斥鎖的優(yōu)點(diǎn)在于它可以確保所有線程對共享資源的訪問是有序的，避免了數(shù)據(jù)混亂和數(shù)據(jù)競爭的問題。但是，由于每個線程在訪問共享資源時都需要先獲得互斥鎖，如果互斥鎖的使用不當(dāng)會導(dǎo)致線程之間的競爭，從而降低程序的并發(fā)性能。因此，在使用互斥鎖時需要特別注意其使用方式和使用場景。TSL指令、Swap指令、單標(biāo)志法都是互斥鎖的實(shí)現(xiàn)方式之一，但它們并不是嚴(yán)格意義上的互斥鎖，因?yàn)樗鼈冎皇腔コ怄i的一種實(shí)現(xiàn)方式，而不是互斥鎖本身。
TSL指令（Test and Set Lock）是一種硬件機(jī)制，用于實(shí)現(xiàn)互斥鎖。它是通過在計算機(jī)硬件層面上實(shí)現(xiàn)一個原子的讀取和修改操作，來保證對共享資源的訪問是互斥的。
Swap指令（Exchange指令）也是一種硬件機(jī)制，用于實(shí)現(xiàn)互斥鎖。它是通過將兩個內(nèi)存地址中的值進(jìn)行交換，來實(shí)現(xiàn)對共享資源的訪問保護(hù)。
單標(biāo)志法（One-Flag Lock）是一種軟件實(shí)現(xiàn)的互斥鎖，它通過一個標(biāo)志位來實(shí)現(xiàn)對共享資源的訪問保護(hù)。當(dāng)一個線程想要訪問共享資源時，它會先將標(biāo)志位設(shè)置為“忙”，然后嘗試訪問共享資源，如果訪問成功，則將標(biāo)志位設(shè)置為“空閑”；如果訪問失敗，則一直等待，直到共享資源變?yōu)椤翱臻e”。
因此，可以說TSL指令、Swap指令、單標(biāo)志法都是互斥鎖的實(shí)現(xiàn)方式之一，但它們并不是互斥鎖本身。
3.信號量
前面的互斥算法都存在問題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個地位高于進(jìn)程的管理者來解決公有資源的使用問題。OS可從進(jìn)程管理者的角度來處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段。信號量的值代表可用資源實(shí)體的數(shù)量。
信號量結(jié)構(gòu)是一種功能較強(qiáng)的機(jī)制，可用來解決互斥與同步的問題，它只能被兩個標(biāo)準(zhǔn)原語wait和signal來訪問，也可以記作p操作和v操作。（原語是指完成某種功能且不被分割不被中斷執(zhí)行的操作序列，有時也成為原子操作，通?？捎糜布韺?shí)現(xiàn)完成某種功能的不可分割執(zhí)行特性）
作用范圍：互斥鎖只能用于同一進(jìn)程內(nèi)的線程同步，而信號量可以用于不同進(jìn)程之間的線程同步。
控制對象：互斥鎖只用于對臨界區(qū)資源的互斥訪問，而信號量可以用于控制多個線程對多個共享資源的訪問。
操作方式：互斥鎖只有兩種狀態(tài)：鎖定和解鎖，而信號量有多種操作方式，如增加、減少、等待、喚醒等。
用途：互斥鎖主要用于保護(hù)共享資源的原子性操作，而信號量則可以用于控制線程的執(zhí)行順序、進(jìn)程間通信等。
綜上所述，互斥鎖和信號量雖然都是線程同步的工具，但在使用時需要根據(jù)實(shí)際情況選擇合適的工具。
如果等待的對象是一個阻塞的資源，例如一個被其他線程占用的鎖或者一個讀寫操作被阻塞的管道，那么等待操作就會阻塞。阻塞意味著當(dāng)前線程會被掛起，直到等待的對象變?yōu)榭捎脿顟B(tài)。
但是，如果等待的對象是一個非阻塞的資源，例如一個已經(jīng)可用的鎖或者一個非空的消息隊列，那么等待操作就不會阻塞，當(dāng)前線程會立即返回。
此外，還有一些等待方式可以避免阻塞，例如超時等待和輪詢等待。超時等待指等待一定時間后如果等待的對象還未變?yōu)榭捎脿顟B(tài)，就放棄等待并返回結(jié)果；輪詢等待指在等待對象變?yōu)榭捎脿顟B(tài)之前，不斷地重復(fù)檢查等待對象的狀態(tài)，以避免長時間的阻塞。
綜上所述，等待操作并不一定會阻塞，具體取決于等待的對象和等待方式。
（1）整型信號量
整型信號量被定義為一個用于表示資源個數(shù)的整型量S。
雖然忙等會消耗大量的CPU資源，但是在某些情況下它仍然是必要的，特別是在實(shí)時系統(tǒng)中，需要快速響應(yīng)事件并且不能使用阻塞等待的方式。在非實(shí)時系統(tǒng)中，可以使用其他的同步機(jī)制，如條件變量、管程等來避免忙等。輪詢和忙等在某些情況下可以表示相同的意思，但它們并不完全相同。
輪詢是指不斷地查詢某個狀態(tài)是否滿足某個條件，如果滿足條件則執(zhí)行相應(yīng)的操作。輪詢可以是阻塞的，也可以是非阻塞的。在阻塞式輪詢中，如果狀態(tài)不滿足條件，則會一直等待；在非阻塞式輪詢中，如果狀態(tài)不滿足條件，則會立即返回，不會等待。
忙等是指在等待某個條件滿足期間，不斷地進(jìn)行查詢、檢查，直到條件滿足。忙等是一種阻塞式的輪詢方式。在忙等期間，會一直占用CPU資源，直到條件滿足為止。
因此，雖然輪詢和忙等有相似之處，但它們的含義和實(shí)現(xiàn)方式并不完全相同。
（2）記錄型信號量
避免忙等：如果沒有等待隊列，進(jìn)程或線程只能通過忙等來等待信號量變?yōu)榭捎脿顟B(tài)，這會占用大量的CPU時間，降低系統(tǒng)的性能。而等待隊列可以讓進(jìn)程或線程在信號量不可用時掛起，只有在信號量可用時才會被喚醒，從而避免了忙等的情況。
公平性：等待隊列可以保證多個進(jìn)程或線程按照請求的順序依次占用信號量，從而保證了公平性。如果沒有等待隊列，那么當(dāng)信號量可用時，可能會隨機(jī)選擇一個進(jìn)程或線程來占用信號量，這會導(dǎo)致某些進(jìn)程或線程一直無法獲取到信號量，從而降低系統(tǒng)的公平性。
可擴(kuò)展性：等待隊列可以支持多個進(jìn)程或線程等待同一個信號量，從而增加了系統(tǒng)的可擴(kuò)展性。如果沒有等待隊列，那么只能支持一個進(jìn)程或線程等待一個信號量，這會使得系統(tǒng)的并發(fā)性能受到限制。
總之，等待隊列是記錄型信號量實(shí)現(xiàn)多進(jìn)程或多線程同步的重要手段，它可以提高系統(tǒng)的性能、公平性和可擴(kuò)展性。
數(shù)據(jù)類型：整型信號量是一個整數(shù)，通常用于計數(shù)或者標(biāo)記資源的可用性；而記錄型信號量是一個結(jié)構(gòu)體，包含多個字段，可以記錄更為復(fù)雜的狀態(tài)信息。
值的取值范圍：整型信號量的取值范圍是整個整數(shù)范圍，通常只有兩個值：0和1。而記錄型信號量的取值范圍取決于結(jié)構(gòu)體中包含的字段的取值范圍，可以有更多的取值。
使用場景：整型信號量通常用于控制對某個共享資源的訪問，例如限制并發(fā)訪問數(shù)量；而記錄型信號量可以用于更為復(fù)雜的場景，例如控制進(jìn)程間的通信、同步和互斥等。
實(shí)現(xiàn)方式：整型信號量可以使用原子操作來實(shí)現(xiàn)，比較簡單；而記錄型信號量則需要更復(fù)雜的實(shí)現(xiàn)方式，例如使用互斥鎖、條件變量、共享內(nèi)存等。
綜上所述，記錄型信號量和整型信號量在功能和實(shí)現(xiàn)方式上存在較大的差異，開發(fā)者在使用時需要根據(jù)具體的場景選擇適合的信號量類型。
（3）利用信號量實(shí)現(xiàn)進(jìn)程互斥
信號量機(jī)制能很方便的解決進(jìn)程互斥問題。
互斥的實(shí)現(xiàn)是不同進(jìn)程對同一信號量進(jìn)行P操作和V操作，一個進(jìn)程在成功地對信號量執(zhí)行了P操作后進(jìn)入臨界區(qū)，并在退出臨界區(qū)后，由該進(jìn)程本身對該信號量執(zhí)行V操作，表示當(dāng)前沒有進(jìn)程進(jìn)入臨界區(qū)，可讓其他進(jìn)程進(jìn)入。
（4）利用信號量實(shí)現(xiàn)進(jìn)程同步
需要注意的是，使用信號量機(jī)制實(shí)現(xiàn)進(jìn)程同步時，需要保證所有進(jìn)程或線程都使用相同的信號量，否則就無法實(shí)現(xiàn)正確的同步。同時，還需要避免死鎖的情況，即當(dāng)多個進(jìn)程或線程互相等待對方釋放鎖時，就會出現(xiàn)死鎖。
（5）利用信號量實(shí)現(xiàn)前驅(qū)關(guān)系
前驅(qū)圖
信號量也可以用來描述程序之間或者語句之間的前驅(qū)關(guān)系。
1） 關(guān)系分析。找出問題中的進(jìn)程數(shù)，并且分析它們之間的同步和互斥關(guān)系。同步、互斥、前驅(qū)關(guān)系直接按照上面例子中的經(jīng)典范式改寫。
2） 整體思路。找出解決問題的關(guān)鍵點(diǎn)，并且根據(jù)做過的題目找出解決的思路。根據(jù)進(jìn)程的操作流程確定P操作、V操作的大致順序。
3） 設(shè)置信號量。根據(jù)上面兩步，設(shè)置需要的信號量，確定初值，完善整理。
（7）信號量集
一般信號量集是由多個二元信號量組成的集合，每個信號量只有兩種狀態(tài)，即0和1，用于實(shí)現(xiàn)基本的同步和互斥機(jī)制。一般信號量集中最常用的操作是P和V操作，分別用于對信號量的值進(jìn)行減1和加1操作。
而AND信號量集則是由多個信號量組成的集合，每個信號量可以有多個狀態(tài)，用于實(shí)現(xiàn)更加復(fù)雜的同步和互斥機(jī)制。AND信號量集中最常用的操作是Swait和Ssignal操作，可以對信號量集中的多個信號量進(jìn)行操作，例如等待多個信號量中的任意一個信號量被觸發(fā)，或讓多個信號量的值達(dá)到某一個特定值。
因此，一般信號量集和AND信號量集在功能和應(yīng)用場景上存在巨大的差異。一般信號量集適用于簡單的同步和互斥機(jī)制，如控制進(jìn)程和線程的訪問順序、實(shí)現(xiàn)互斥訪問共享資源等。而AND信號量集則適用于更加復(fù)雜的同步和互斥機(jī)制，如解決多進(jìn)程或多線程之間的同步和互斥問題、實(shí)現(xiàn)高級進(jìn)程同步機(jī)制等。
綜上所述，一般信號量集和AND信號量集是兩種不同類型的信號量集，它們在功能和應(yīng)用場景上存在較大差異，需要根據(jù)具體的應(yīng)用需求進(jìn)行選擇。
PV操作只能對一個信號量進(jìn)行操作，而Swait和Ssignal可以對信號量集中的多個信號量進(jìn)行操作。例如，可以通過Swait操作等待多個信號量中的任意一個信號量被觸發(fā)，而不是僅僅等待一個信號量被觸發(fā)。
PV操作通常用于二元信號量，即只有0和1兩種狀態(tài)，而Swait和Ssignal可以處理更多的狀態(tài)。例如，可以使用Swait操作等待信號量集中的一個信號量的值達(dá)到某一個特定值。
PV操作通常是原子操作，即在操作期間不會被其他進(jìn)程或線程中斷，而Swait和Ssignal操作通常不是原子操作，它們可能會被中斷和恢復(fù)。因此，在使用Swait和Ssignal時，需要考慮并發(fā)和競爭條件，以避免死鎖和競態(tài)條件的問題。
總之，Swait和Ssignal是AND型信號量集中常用的操作方法，相較于PV操作具有更加靈活和多樣的同步和互斥機(jī)制，可以滿足更加復(fù)雜的應(yīng)用場景。但是，在使用Swait和Ssignal時，需要仔細(xì)考慮并發(fā)和競爭條件，以避免死鎖和競態(tài)條件的問題。
4.經(jīng)典同步與互斥問題
（1）生產(chǎn)者-消費(fèi)者問題（the producer/consumer problem）
問題描述：一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享一個初始為空、大小為n的緩沖區(qū)，只有緩沖區(qū)沒滿時，生產(chǎn)者才能把消息放入到緩沖區(qū)，否則必須等待；只有緩沖區(qū)不為空時，消費(fèi)者才能從中取出消息，否則必須等待。由于緩沖區(qū)是臨界資源，它只允許一個生產(chǎn)者放入消息，或一個消費(fèi)者從中取出消息。
問題分析：
1）關(guān)系分析。生產(chǎn)者和消費(fèi)者對緩沖區(qū)互斥訪問是互斥關(guān)系，同時生產(chǎn)者和消費(fèi)者又是一個相互協(xié)作的關(guān)系，只有生產(chǎn)者生產(chǎn)之后，消費(fèi)者才能消費(fèi)，他們也是同步關(guān)系。
2）整理思路。這里比較簡單，只有生產(chǎn)者和消費(fèi)者兩個進(jìn)程，正好是這兩個進(jìn)程存在著互斥關(guān)系和同步關(guān)系。那么需要解決的是互斥和同步PV操作的位置。
3）信號量的設(shè)置。信號量mutex作為互斥信號量，它用于控制互斥訪問緩沖池，互斥信號量初始為1；信號量full用于記錄當(dāng)前緩沖池中“滿”緩沖區(qū)數(shù)，初值為0。信號量empty用于記錄當(dāng)前緩沖池中空緩沖區(qū)，初值為n。[互斥信號量mutex為1時，表示當(dāng)前沒有進(jìn)程占用資源，可以直接訪問臨界區(qū)代碼；互斥信號量mutex為0時，表示資源被另一個進(jìn)程占用，當(dāng)前進(jìn)程需要等待，直到mutex不為0才能繼續(xù)執(zhí)行臨界區(qū)代碼。]
互斥信號量（Mutual Exclusion Semaphore）是一種同步原語，用于控制對共享資源的訪問。它的值通常為1或0，0表示資源正在被占用，1表示資源空閑。在進(jìn)程訪問共享資源之前，需要先嘗試將互斥信號量的值減1（原子操作），如果值變成了0，則表示資源正在被占用，該進(jìn)程需要等待；否則，該進(jìn)程獲得了資源的使用權(quán)。
互斥鎖（Mutex）也是一種同步原語，它也用于控制對共享資源的訪問。它的作用是保證在同一時間只有一個線程可以訪問共享資源?；コ怄i在進(jìn)程訪問共享資源之前，需要先嘗試獲取鎖，如果鎖被其他線程占用，則當(dāng)前線程需要等待；否則，當(dāng)前線程獲得了鎖的所有權(quán)。
因此，互斥信號量和互斥鎖都可以用于實(shí)現(xiàn)線程同步，它們的作用類似，但細(xì)節(jié)和實(shí)現(xiàn)方式有所不同。在一些操作系統(tǒng)和編程語言中，互斥信號量和互斥鎖的實(shí)現(xiàn)方式可能不同。
互斥信號量和互斥鎖都可以用于進(jìn)程同步和線程同步。
在進(jìn)程并發(fā)編程中，互斥信號量和互斥鎖都是常用的同步機(jī)制，它們都可以用于控制對共享資源的訪問，避免了進(jìn)程或線程之間的競爭和沖突。無論是在進(jìn)程級別還是線程級別，互斥信號量和互斥鎖都可以防止多個進(jìn)程或線程同時訪問共享資源，從而保證程序的正確性和可靠性。
在一些操作系統(tǒng)和編程語言中，互斥信號量和互斥鎖的實(shí)現(xiàn)方式可能不同，但它們的作用和原理是相似的。因此，根據(jù)具體的應(yīng)用場景和需求，可以選擇使用互斥信號量或互斥鎖來實(shí)現(xiàn)進(jìn)程或線程的同步和互斥訪問。
（2）多生產(chǎn)者-多消費(fèi)者問題
問題描述：桌子上有一只盤子，每次孩子能向其中放入一個水果。爸爸專向盤子中放入蘋果，媽媽專向盤子中放入橘子，女兒專等吃盤子中的蘋果，兒子專等吃盤子中的橘子。只有盤子為空時，爸爸或媽媽就可向盤子中放一只水果2；僅當(dāng)盤子中有自己需要的水果時，兒子或女兒可以從盤子中取出。
1）關(guān)系分析。這里的關(guān)系略微復(fù)雜一些，首先由每次只能向其中放入一只水果可知爸爸和媽媽是互斥關(guān)系。爸爸和女兒、媽媽和兒子是同步關(guān)系，而且這兩對進(jìn)程必須連起來，兒子和女兒之間沒有互斥和同步關(guān)系，因?yàn)樗麄兪沁x擇條件執(zhí)行，不可能并發(fā)。
2）整理思路。這里有4個進(jìn)程，實(shí)際上可以抽象為兩個生產(chǎn)者和兩個消費(fèi)者被連接到大小為1的緩沖區(qū)上。
3）信號量設(shè)置。首先設(shè)置信號量plate為互斥信號量，表示是否允許想盤子放水果，初值為1，表示允許放入，且只允許放一只。信號量apple表示盤子里是否有蘋果，初值為0，表示盤子中無2蘋果；信號量orange表示盤子中是否有橘子，初始量為0，表示盤子中無橘子。
（3）吸煙者問題
問題描述：假設(shè)一個系統(tǒng)有三個吸煙者進(jìn)程和一個供應(yīng)者進(jìn)程。每個抽煙者不停的卷煙并抽調(diào)他，但是要卷起并抽掉一支煙，抽煙者必須要有三種材料：煙草、紙和膠水。三個抽煙者中，第一個有煙草，第二個有紙，第三個有膠水。供應(yīng)者進(jìn)程無線地提供提供三種材料。
供應(yīng)者每次將兩種材料放到桌子上，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應(yīng)者一個信號告訴完成了，供應(yīng)者就會放另外兩種材料在桌子上，這種過程一直重復(fù)。
問題分析：
1）關(guān)系分析。供應(yīng)者與三個抽煙者分別是同步關(guān)系。由于供應(yīng)者無法同時滿足兩個或兩個以上的抽煙者，三個抽煙者對抽煙這個動作是互斥關(guān)系。
2）整理思路。顯然這里有四個進(jìn)程。供應(yīng)者作為生產(chǎn)者向三個抽煙者提供材料。
3）信號量設(shè)置。信號量offer1、offer2、offer3分別表示煙草和紙組合的資源、煙草和膠水組合的資源、紙和膠水組合的資源。信號量finish 用于互斥進(jìn)行抽煙動作
（4）讀者一寫者問題（the readers-writers problem）
問題描述：有讀者和寫者兩組并發(fā)進(jìn)程，共享一個文件，當(dāng)兩個以上的讀進(jìn)程同事訪問共享數(shù)據(jù)時不會產(chǎn)生副作用，但若某個寫進(jìn)程和其他進(jìn)程（讀進(jìn)程或?qū)戇M(jìn)程）同時訪問共享數(shù)據(jù)時則可能導(dǎo)致數(shù)據(jù)不一致的錯誤。因此要求：1）允許多個讀者同時對文件執(zhí)行讀操作；2）只允許一個寫者往文件中寫信息；3）任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ鳎?）寫者執(zhí)行完寫操作前，應(yīng)讓已有的讀者或?qū)懻呷客顺觥?/p>
問題分析：
1）關(guān)系分析。由題目分析讀者和寫者是互斥的，寫者和寫者也是互斥的，而讀者和讀者不存在互斥關(guān)系。
2）整理思路。兩個進(jìn)程，即讀者和寫者。寫者和任何進(jìn)程互斥，用互斥信號量p操作、v操作即可解決。讀者的問題比較復(fù)雜，它必須實(shí)現(xiàn)與寫者互斥的關(guān)系，還要實(shí)現(xiàn)和其他讀者同步的關(guān)系。因此，簡單的一對pv操作時無法解決的。那么在這里用到了一個計數(shù)器，用它來判斷當(dāng)前是否有讀者讀文件。當(dāng)有讀者的時候，寫者是無法寫文件的，此時讀者會一直占用文件，當(dāng)沒有讀者的時候，寫者才可以寫文件。同時這里不同讀者對計數(shù)器的訪問也是互斥的。
3）信號量的設(shè)置。首先設(shè)置信號量count為計數(shù)器，用來記錄當(dāng)前讀者數(shù)量，初值為0；設(shè)置mutex為互斥信號量，用于保護(hù)更新count變量時的互斥；設(shè)置互斥信號量rw用于保證讀者和寫者的互斥訪問。
讀者優(yōu)先策略
寫者優(yōu)先策略——只要有寫者準(zhǔn)備要寫入，寫者應(yīng)盡快執(zhí)行寫操作，后來的讀者就必須阻塞如果有寫者持續(xù)不斷寫入，則讀者就處于饑餓。
公平策略——由于讀者優(yōu)先策略和寫者優(yōu)先策略都會造成饑餓的現(xiàn)象。
優(yōu)先級相同；
寫者、讀者互斥訪問；
只能一個寫者訪問臨界區(qū)；
可以有多個讀者同時訪問臨界資源；
沒有讀者到達(dá)會導(dǎo)致讀者隊列為空，即 rCount==0，此時寫者才可以進(jìn)入臨界區(qū)執(zhí)行寫操作。
而這里 flag 的作用就是阻止讀者的這種特殊權(quán)限（特殊權(quán)限是只要讀者到達(dá)，就可以進(jìn)入讀者隊列）。
比如：開始來了一些讀者讀數(shù)據(jù)，它們?nèi)窟M(jìn)入讀者隊列，此時來了一個寫者，執(zhí)行 P(falg) 操作，使得后續(xù)到來的讀者都阻塞在 flag 上，不能進(jìn)入讀者隊列，這會使得讀者隊列逐漸為空，即 rCount 減為 0。
這個寫者也不能立馬開始寫（因?yàn)榇藭r讀者隊列不為空），會阻塞在信號量 wDataMutex 上，讀者隊列中的讀者全部讀取結(jié)束后，最后一個讀者進(jìn)程執(zhí)行 V(wDataMutex)，喚醒剛才的寫者，寫者則繼續(xù)開始進(jìn)行寫操作。
（5）哲學(xué)家進(jìn)餐問題（the dining philosophers problem）
問題描述：一張圓桌上坐著五個哲學(xué)家，每兩個哲學(xué)家之間的桌子上擺著一根筷子，桌子的中間是一碗米飯。哲學(xué)家們傾注畢生精力用于思考和進(jìn)餐，哲學(xué)家在思考是，并不影響其他人。只有當(dāng)哲學(xué)家饑餓的時候，才視圖拿起左右兩根筷子。如果筷子已經(jīng)在他人手上，則需等待。饑餓的哲學(xué)家只有同時拿到了兩根筷子才可以開始進(jìn)餐，當(dāng)進(jìn)餐完畢后，放下筷子繼續(xù)思考。
問題分析：
1）關(guān)系分析。五個哲學(xué)家與左右鄰居對其中的筷子的訪問是互斥關(guān)系。
2）整理思路。顯然這五個進(jìn)程，要解決的問題有兩個：一個是讓他們同時拿起兩個筷子；而是對每個哲學(xué)家的動作執(zhí)行規(guī)則，避免饑餓或者死鎖現(xiàn)象發(fā)生。
3）信號量設(shè)置。定義互斥信號組chopsticks[5]={1,1,1,1,1}用于對五個筷子的互斥訪問。
對哲學(xué)家按順序0~4編號，哲學(xué)家i左邊的筷子編號為i，哲學(xué)家右邊的筷子編號為（i+1）%5。
解決方案一——讓偶數(shù)編號的哲學(xué)家「先拿左邊的叉子后拿右邊的叉子」，奇數(shù)編號的哲學(xué)家「先拿右邊的叉子后拿左邊的叉子」。
解決方案二——
用一個數(shù)組 state 來記錄每一位哲學(xué)家的三個狀態(tài)，分別是在進(jìn)餐狀態(tài)、思考狀態(tài)、饑餓狀態(tài)（正在試圖拿叉子）。
那么，一個哲學(xué)家只有在兩個鄰居都沒有進(jìn)餐時，才可以進(jìn)入進(jìn)餐狀態(tài)。
第?i?個哲學(xué)家的左鄰右舍，則由宏?LEFT?和?RIGHT?定義：
LEFT?: ( i + 5 - 1 ) % 5
RIGHT?: ( i + 1 ) % 5
比如 i 為 2，則?LEFT?為 1，RIGHT?為 3。
5.管程（Monitor, 監(jiān)視器）
二、死鎖
1.?死鎖的概念
在多道程序系統(tǒng)中，由于多個進(jìn)程的并發(fā)執(zhí)行，改善了系統(tǒng)資源的利用率并提高了系統(tǒng)的處理能力。然而，多個進(jìn)程的并發(fā)執(zhí)行也帶來了新的問題——死鎖。所謂死鎖是指多個進(jìn)程因競爭資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將無法向前推進(jìn)。
什么時候會發(fā)生死鎖？
1）系統(tǒng)資源的競爭
通常系統(tǒng)中擁有的不可剝奪資源，其數(shù)量不足以滿足多個進(jìn)程運(yùn)行的需要，似的進(jìn)程在運(yùn)行過程中會因爭奪資源而陷入僵局。只有對不可剝奪資源的競爭才可能產(chǎn)生死鎖，對可剝奪資源的競爭是不會引起死鎖的。
2）進(jìn)程推進(jìn)順序非法
進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，同樣會導(dǎo)致死鎖。
信號量使用不當(dāng)也會造成死鎖。進(jìn)程間相互等待對方發(fā)來的消息，結(jié)果也會造成某些進(jìn)程間無法繼續(xù)向前推進(jìn)。
3）死鎖產(chǎn)生的必要條件
產(chǎn)生死鎖必須同時滿足以下四個條件，只要其中任一個條件不成立，死鎖就不會發(fā)生。
互斥條件：進(jìn)程要求對所分配的資源進(jìn)行排他性控制，即在一段時間內(nèi)某資源僅為一個進(jìn)程所占用。此時若有其他進(jìn)程請求該資源，則請求進(jìn)程只能等待。
不剝奪條件：進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來釋放。
請求和保持條件：進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源已被其他進(jìn)程占有，此時請求進(jìn)程被阻塞，但對自己已獲得的資源保持不放。
循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中每一個進(jìn)程已獲得的資源同時被鏈中下一個進(jìn)程所請求。
死鎖與饑餓的區(qū)別？
2.死鎖的處理策略
3. 死鎖的預(yù)防[靜態(tài)策略]
① 破除資源互斥（Mutual Exclusion）條件，例如假脫機(jī)打印機(jī)技術(shù)允許若干個進(jìn)程同時輸出，唯一真正請求物理打印機(jī)的進(jìn)程是打印機(jī)守護(hù)進(jìn)程。
② 破除“請求與保持”(Request and Hold)條件：實(shí)行資源預(yù)分配策略，進(jìn)程在運(yùn)行之前，必須一次性獲取所有的資源。缺點(diǎn)：在很多情況下，無法預(yù)知進(jìn)程執(zhí)行前所需的全部資源，因?yàn)檫M(jìn)程是動態(tài)執(zhí)行的，同時也會降低資源利用率，導(dǎo)致降低了進(jìn)程的并發(fā)性。
③ 破除“不可剝奪”(Nonpreemptive)條件：允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。當(dāng)一個已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請求而不能得到滿足時，它必須釋放已經(jīng)保持的所有資源，待以后需要時再重新申請。這意味著進(jìn)程已經(jīng)占有的資源會被暫時被釋放，或者說被搶占了。
④ 破除“循環(huán)等待”條件(Circlar Wait)：實(shí)行資源有序分配策略，對所有資源排序編號，按照順序獲取資源，將緊缺的，稀少的采用較大的編號，在申請資源時必須按照編號的順序進(jìn)行，一個進(jìn)程只有獲得較小編號的進(jìn)程才能申請較大編號的進(jìn)程。
4. 死鎖的避免[動態(tài)策略]
死鎖預(yù)防通過約束資源請求，防止4個必要條件中至少一個的發(fā)生，可以通過直接或間接預(yù)防方法，但是都會導(dǎo)致低效的資源使用和低效的進(jìn)程執(zhí)行。而死鎖避免則允許前三個必要條件，但是通過動態(tài)地檢測資源分配狀態(tài)，以確保循環(huán)等待條件不成立，從而確保系統(tǒng)處于安全狀態(tài)。所謂安全狀態(tài)是指：如果系統(tǒng)能按某個順序為每個進(jìn)程分配資源（不超過其最大值），那么系統(tǒng)狀態(tài)是安全的，換句話說就是，如果存在一個安全序列，那么系統(tǒng)處于安全狀態(tài)。銀行家算法是經(jīng)典的死鎖避免的算法。
安全狀態(tài)
銀行家算法
銀行家算法是一種基于資源分配的死鎖避免算法，它在資源分配前檢查系統(tǒng)狀態(tài)，通過計算安全序列來判斷是否能夠分配資源，從而避免死鎖。在銀行家算法中，每個進(jìn)程都需要提前聲明它所需要的資源數(shù)目和資源類型，同時還需要聲明它所能夠接受的最大資源數(shù)目。當(dāng)一個進(jìn)程請求資源時，銀行家算法會檢查該請求是否符合系統(tǒng)安全狀態(tài)，如果符合，就會分配資源，否則就會等待資源。
相比之下，打破“循環(huán)等待條件”是一種死鎖預(yù)防的方法，它是通過對資源的有序分配來打破資源之間的循環(huán)等待關(guān)系，從而避免死鎖。在打破“循環(huán)等待條件”的過程中，通常需要指定資源的優(yōu)先級和分配順序，以確保資源分配的有序性。
因此，雖然銀行家算法和打破“循環(huán)等待條件”都與死鎖有關(guān)，但它們的解決問題的方式和核心思想是不同的。銀行家算法通過安全序列的計算來避免死鎖，而打破“循環(huán)等待條件”則是通過資源的有序分配來避免死鎖。
5.死鎖的檢測
死鎖預(yù)防策略是非常保守的，他們通過限制訪問資源和在進(jìn)程上強(qiáng)加約束來解決死鎖的問題。死鎖檢測則是完全相反，它不限制資源訪問或約束進(jìn)程行為，只要有可能，被請求的資源就被授權(quán)給進(jìn)程。但是操作系統(tǒng)會周期性地執(zhí)行一個算法檢測前面的循環(huán)等待的條件。死鎖檢測算法是通過資源分配圖來檢測是否存在環(huán)來實(shí)現(xiàn)，從一個節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對訪問過的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有存在環(huán)，也就是檢測到死鎖的發(fā)生。
（1）如果進(jìn)程-資源分配圖中無環(huán)路，此時系統(tǒng)沒有死鎖。
（2）如果進(jìn)程-資源分配圖中有環(huán)路，且每個資源類中只有一個資源，則系統(tǒng)發(fā)生死鎖。
（3）如果進(jìn)程-資源分配圖中有環(huán)路，且所涉及的資源類有多個資源，則不一定會發(fā)生死鎖。
常見的死鎖檢測算法包括：
1.銀行家算法（Banker's algorithm）：銀行家算法是一種基于資源分配圖的死鎖檢測算法。它通過模擬進(jìn)程請求資源的情況，來判斷系統(tǒng)是否會發(fā)生死鎖。
2.圖論算法：圖論算法是一種基于有向圖的死鎖檢測算法。它將系統(tǒng)中的資源和進(jìn)程表示為節(jié)點(diǎn)，將資源的分配和請求關(guān)系表示為有向邊，然后通過檢測是否存在環(huán)來確定是否存在死鎖。
3.等待圖算法（Wait-for graph algorithm）：等待圖算法是一種基于等待圖的死鎖檢測算法。它將系統(tǒng)中的進(jìn)程和資源表示為節(jié)點(diǎn)，將進(jìn)程等待資源的關(guān)系表示為有向邊，然后通過檢測是否存在環(huán)來確定是否存在死鎖。
這些死鎖檢測算法都有各自的優(yōu)缺點(diǎn)，具體應(yīng)用時需要根據(jù)實(shí)際情況進(jìn)行選擇。
資源獲取環(huán)可以采用圖來存儲，使用有向圖來存儲。
線程 A 獲取線程 B 已占用的鎖，則為線程 A 指向線程 B。
運(yùn)行過程中線程 B 獲取成功的鎖即為線程 B 已占用的鎖（可以使用hook方法得到）。
檢測的原理采用另一個線程定時對圖進(jìn)程檢測是否有環(huán)的存在。
*利用工具排查死鎖問題
java的jstack是jdk自帶的線程對戰(zhàn)分析工具，在linux下，可用pstack+gdb工具來定位死鎖問題，pstack 命令可以顯示每個線程的棧跟蹤信息（函數(shù)調(diào)用過程），它的使用方式也很簡單，只需要?pstack <pid>?就可以了。在定位死鎖問題時，我們可以多次執(zhí)行 pstack 命令查看線程的函數(shù)調(diào)用過程，多次對比結(jié)果，確認(rèn)哪幾個線程一直沒有變化，且是因?yàn)樵诘却i，那么大概率是由于死鎖問題導(dǎo)致的。
6.死鎖的恢復(fù)（解除）
死鎖解除的常用方法就是終止進(jìn)程和資源搶占，回滾。所謂進(jìn)程終止就是簡單地終止一個或多個進(jìn)程以打破循環(huán)等待，包括兩種方式：終止所有死鎖進(jìn)程和一次只終止一個進(jìn)程直到取消死鎖循環(huán)為止；所謂資源搶占就是從一個或者多個死鎖進(jìn)程那里搶占一個或多個資源。
綜合方法
*三、樂觀鎖和悲觀鎖
1. 互斥鎖與自旋鎖
互斥鎖是一種用于多線程編程中，防止多個線程同時執(zhí)行同一段代碼（臨界區(qū)）的機(jī)制。它是一種保護(hù)共享資源的鎖，一次只允許一個線程訪問共享資源。當(dāng)線程請求互斥鎖時，如果鎖沒有被其他線程占用，則該線程可以獲得鎖并繼續(xù)執(zhí)行；如果鎖已經(jīng)被其他線程占用，則該線程會被阻塞，直到鎖被釋放為止。 互斥鎖的實(shí)現(xiàn)通常使用了操作系統(tǒng)提供的原語（如mutex），可以跨進(jìn)程使用，適用于多核、多進(jìn)程的情況。
自旋鎖是一種用于多線程編程中，等待鎖釋放時不阻塞線程而是循環(huán)檢測鎖狀態(tài)的鎖。當(dāng)線程請求自旋鎖時，如果鎖沒有被其他線程占用，則該線程可以獲得鎖并繼續(xù)執(zhí)行；如果鎖已經(jīng)被其他線程占用，則該線程會一直循環(huán)等待，直到鎖被釋放為止。 自旋鎖的實(shí)現(xiàn)通常使用了操作系統(tǒng)提供的原語（如atomic指令），只能在同一進(jìn)程內(nèi)使用，適用于單核、多線程的情況。自旋鎖的優(yōu)點(diǎn)是等待鎖的線程不會被阻塞，避免了線程切換的開銷，缺點(diǎn)是對CPU資源的占用較高，如果等待鎖的時間較長會浪費(fèi)大量的CPU時間。
互斥鎖加鎖失敗后，線程會釋放 CPU?，給其他線程；
自旋鎖加鎖失敗后，線程會忙等待，直到它拿到鎖；
互斥鎖是一種「獨(dú)占鎖」，比如當(dāng)線程 A 加鎖成功后，此時互斥鎖已經(jīng)被線程 A 獨(dú)占了，只要線程 A 沒有釋放手中的鎖，線程 B 加鎖就會失敗，于是就會釋放 CPU 讓給其他線程，既然線程 B 釋放掉了 CPU，自然線程 B 加鎖的代碼就會被阻塞。
對于互斥鎖加鎖失敗而阻塞的現(xiàn)象，是由操作系統(tǒng)內(nèi)核實(shí)現(xiàn)的。當(dāng)加鎖失敗時，內(nèi)核會將線程置為「睡眠」?fàn)顟B(tài)，等到鎖被釋放后，內(nèi)核會在合適的時機(jī)喚醒線程，當(dāng)這個線程成功獲取到鎖后，于是就可以繼續(xù)執(zhí)行
互斥鎖加鎖失敗時，會從用戶態(tài)陷入到內(nèi)核態(tài)，讓內(nèi)核幫我們切換線程，雖然簡化了使用鎖的難度，但是存在一定的性能開銷成本——兩次線程上下文切換的成本。
當(dāng)線程加鎖失敗時，內(nèi)核會把線程的狀態(tài)從「運(yùn)行」?fàn)顟B(tài)設(shè)置為「睡眠」?fàn)顟B(tài)，然后把 CPU 切換給其他線程運(yùn)行；
接著，當(dāng)鎖被釋放時，之前「睡眠」?fàn)顟B(tài)的線程會變?yōu)椤妇途w」?fàn)顟B(tài)，然后內(nèi)核會在合適的時間，把 CPU 切換給該線程運(yùn)行。
線程的上下文切換的是什么？當(dāng)兩個線程是屬于同一個進(jìn)程，因?yàn)樘摂M內(nèi)存是共享的，所以在切換時，虛擬內(nèi)存這些資源就保持不動，只需要切換線程的私有數(shù)據(jù)、寄存器等不共享的數(shù)據(jù)。
所以，如果你能確定被鎖住的代碼執(zhí)行時間很短，就不應(yīng)該用互斥鎖，而應(yīng)該選用自旋鎖，否則使用互斥鎖。
自旋鎖是通過 CPU 提供的?CAS?函數(shù)（Compare And Swap），在「用戶態(tài)」完成加鎖和解鎖操作，不會主動產(chǎn)生線程上下文切換，所以相比互斥鎖來說，會快一些，開銷也小一些。
一般加鎖的過程，包含兩個步驟：
第一步，查看鎖的狀態(tài)，如果鎖是空閑的，則執(zhí)行第二步；
第二步，將鎖設(shè)置為當(dāng)前線程持有；
CAS 函數(shù)就把這兩個步驟合并成一條硬件級指令，形成原子指令，這樣就保證了這兩個步驟是不可分割的，要么一次性執(zhí)行完兩個步驟，要么兩個步驟都不執(zhí)行。
比如，設(shè)鎖為變量 lock，整數(shù) 0 表示鎖是空閑狀態(tài)，整數(shù) pid 表示線程 ID，那么 CAS(lock, 0, pid) 就表示自旋鎖的加鎖操作，CAS(lock, pid, 0) 則表示解鎖操作。
使用自旋鎖的時候，當(dāng)發(fā)生多線程競爭鎖的情況，加鎖失敗的線程會「忙等待」，直到它拿到鎖。這里的「忙等待」可以用?while?循環(huán)等待實(shí)現(xiàn)，不過最好是使用 CPU 提供的?PAUSE?指令來實(shí)現(xiàn)「忙等待」，因?yàn)榭梢詼p少循環(huán)等待時的耗電量。
自旋鎖是最比較簡單的一種鎖，一直自旋，利用 CPU 周期，直到鎖可用。需要注意，在單核 CPU 上，需要搶占式的調(diào)度器（即不斷通過時鐘中斷一個線程，運(yùn)行其他線程）。否則，自旋鎖在單 CPU 上無法使用，因?yàn)橐粋€自旋的線程永遠(yuǎn)不會放棄 CPU。
自旋鎖開銷少，在多核系統(tǒng)下一般不會主動產(chǎn)生線程切換，適合異步、協(xié)程等在用戶態(tài)切換請求的編程方式，但如果被鎖住的代碼執(zhí)行時間過長，自旋的線程會長時間占用 CPU 資源，所以自旋的時間和被鎖住的代碼執(zhí)行的時間是成「正比」的關(guān)系，我們需要清楚的知道這一點(diǎn)。
自旋鎖與互斥鎖使用層面比較相似，但實(shí)現(xiàn)層面上完全不同：當(dāng)加鎖失敗時，互斥鎖用「線程切換」來應(yīng)對，自旋鎖則用「忙等待」來應(yīng)對。
它倆是鎖的最基本處理方式，更高級的鎖都會選擇其中一個來實(shí)現(xiàn)，比如讀寫鎖既可以選擇互斥鎖實(shí)現(xiàn)，也可以基于自旋鎖實(shí)現(xiàn)。
2. 讀寫鎖
它由「讀鎖」和「寫鎖」兩部分構(gòu)成，如果只讀取共享資源用「讀鎖」加鎖，如果要修改共享資源則用「寫鎖」加鎖。
所以，讀寫鎖適用于能明確區(qū)分讀操作和寫操作的場景。
讀寫鎖的工作原理是：
當(dāng)「寫鎖」沒有被線程持有時，多個線程能夠并發(fā)地持有讀鎖，這大大提高了共享資源的訪問效率，因?yàn)椤缸x鎖」是用于讀取共享資源的場景，所以多個線程同時持有讀鎖也不會破壞共享資源的數(shù)據(jù)。
但是，一旦「寫鎖」被線程持有后，讀線程的獲取讀鎖的操作會被阻塞，而且其他寫線程的獲取寫鎖的操作也會被阻塞。
所以說，寫鎖是獨(dú)占鎖，因?yàn)槿魏螘r刻只能有一個線程持有寫鎖，類似互斥鎖和自旋鎖，而讀鎖是共享鎖，因?yàn)樽x鎖可以被多個線程同時持有。
知道了讀寫鎖的工作原理后，我們可以發(fā)現(xiàn)，讀寫鎖在讀多寫少的場景，能發(fā)揮出優(yōu)勢。
另外，根據(jù)實(shí)現(xiàn)的不同，讀寫鎖可以分為「讀優(yōu)先鎖」和「寫優(yōu)先鎖」。
讀優(yōu)先鎖期望的是，讀鎖能被更多的線程持有，以便提高讀線程的并發(fā)性，它的工作方式是：當(dāng)讀線程 A 先持有了讀鎖，寫線程 B 在獲取寫鎖的時候，會被阻塞，并且在阻塞過程中，后續(xù)來的讀線程 C 仍然可以成功獲取讀鎖，最后直到讀線程 A 和 C 釋放讀鎖后，寫線程 B 才可以成功獲取寫鎖。
寫優(yōu)先鎖是優(yōu)先服務(wù)寫線程，其工作方式是：當(dāng)讀線程 A 先持有了讀鎖，寫線程 B 在獲取寫鎖的時候，會被阻塞，并且在阻塞過程中，后續(xù)來的讀線程 C 獲取讀鎖時會失敗，于是讀線程 C 將被阻塞在獲取讀鎖的操作，這樣只要讀線程 A 釋放讀鎖后，寫線程 B 就可以成功獲取寫鎖。
讀優(yōu)先鎖對于讀線程并發(fā)性更好，但也不是沒有問題。如果一直有讀線程獲取讀鎖，那么寫線程將永遠(yuǎn)獲取不到寫鎖，這就造成了寫線程「饑餓」的現(xiàn)象。
寫優(yōu)先鎖可以保證寫線程不會餓死，但是如果一直有寫線程獲取寫鎖，讀線程也會被「餓死」。
既然不管優(yōu)先讀鎖還是寫鎖，對方可能會出現(xiàn)餓死問題，那么我們就不偏袒任何一方，搞個「公平讀寫鎖」。
公平讀寫鎖比較簡單的一種方式是：用隊列把獲取鎖的線程排隊，不管是寫線程還是讀線程都按照先進(jìn)先出的原則加鎖即可，這樣讀線程仍然可以并發(fā)，也不會出現(xiàn)「饑餓」的現(xiàn)象。
互斥鎖和自旋鎖都是最基本的鎖，讀寫鎖可以根據(jù)場景來選擇這兩種鎖其中的一個進(jìn)行實(shí)現(xiàn)。
3. 樂觀鎖和悲觀鎖
互斥鎖、自旋鎖、讀寫鎖，都是屬于悲觀鎖。
悲觀鎖做事比較悲觀，它認(rèn)為多線程同時修改共享資源的概率比較高，于是很容易出現(xiàn)沖突，所以訪問共享資源前，先要上鎖。
那相反的，如果多線程同時修改共享資源的概率比較低，就可以采用樂觀鎖。
樂觀鎖做事比較樂觀，它假定沖突的概率很低，它的工作方式是：先修改完共享資源，再驗(yàn)證這段時間內(nèi)有沒有發(fā)生沖突，如果沒有其他線程在修改資源，那么操作完成，如果發(fā)現(xiàn)有其他線程已經(jīng)修改過這個資源，就放棄本次操作。
放棄后如何重試，這跟業(yè)務(wù)場景息息相關(guān)，雖然重試的成本很高，但是沖突的概率足夠低的話，還是可以接受的。
可見，樂觀鎖的心態(tài)是，不管三七二十一，先改了資源再說。另外，你會發(fā)現(xiàn)樂觀鎖全程并沒有加鎖，所以它也叫無鎖編程。
這里舉一個場景例子：在線文檔。
我們都知道在線文檔可以同時多人編輯的，如果使用了悲觀鎖，那么只要有一個用戶正在編輯文檔，此時其他用戶就無法打開相同的文檔了，這用戶體驗(yàn)當(dāng)然不好了。
那實(shí)現(xiàn)多人同時編輯，實(shí)際上是用了樂觀鎖，它允許多個用戶打開同一個文檔進(jìn)行編輯，編輯完提交之后才驗(yàn)證修改的內(nèi)容是否有沖突。
怎么樣才算發(fā)生沖突？這里舉個例子，比如用戶 A 先在瀏覽器編輯文檔，之后用戶 B 在瀏覽器也打開了相同的文檔進(jìn)行編輯，但是用戶 B 比用戶 A 提交早，這一過程用戶 A 是不知道的，當(dāng) A 提交修改完的內(nèi)容時，那么 A 和 B 之間并行修改的地方就會發(fā)生沖突。
服務(wù)端要怎么驗(yàn)證是否沖突了呢？通常方案如下：
由于發(fā)生沖突的概率比較低，所以先讓用戶編輯文檔，但是瀏覽器在下載文檔時會記錄下服務(wù)端返回的文檔版本號；
當(dāng)用戶提交修改時，發(fā)給服務(wù)端的請求會帶上原始文檔版本號，服務(wù)器收到后將它與當(dāng)前版本號進(jìn)行比較，如果版本號不一致則提交失敗，如果版本號一致則修改成功，然后服務(wù)端版本號更新到最新的版本號。
實(shí)際上，我們常見的 SVN 和 Git 也是用了樂觀鎖的思想，先讓用戶編輯代碼，然后提交的時候，通過版本號來判斷是否產(chǎn)生了沖突，發(fā)生了沖突的地方，需要我們自己修改后，再重新提交。
樂觀鎖雖然去除了加鎖解鎖的操作，但是一旦發(fā)生沖突，重試的成本非常高，所以只有在沖突概率非常低，且加鎖成本非常高的場景時，才考慮使用樂觀鎖。
*快速面經(jīng)
1. 進(jìn)程間同步的方式有哪些？
1、臨界區(qū)：通過對多線程的串行化來訪問公共資源或一段代碼，速度快，適合控制數(shù)據(jù)訪問。
優(yōu)點(diǎn)：保證在某一時刻只有一個線程能訪問數(shù)據(jù)的簡便辦法。
缺點(diǎn)：雖然臨界區(qū)同步速度很快，但卻只能用來同步本進(jìn)程內(nèi)的線程，而不可用來同步多個進(jìn)程中的線程。
2、互斥量：為協(xié)調(diào)共同對一個共享資源的單獨(dú)訪問而設(shè)計的。互斥量跟臨界區(qū)很相似，比臨界區(qū)復(fù)雜，互斥對象只有一個，只有擁有互斥對象的線程才具有訪問資源的權(quán)限。
優(yōu)點(diǎn)：使用互斥不僅僅能夠在同一應(yīng)用程序不同線程中實(shí)現(xiàn)資源的安全共享，而且可以在不同應(yīng)用程序的線程之間實(shí)現(xiàn)對資源的安全共享。
缺點(diǎn)：
互斥量是可以命名的，也就是說它可以跨越進(jìn)程使用，所以創(chuàng)建互斥量需要的資源更多，所以如果只為了在進(jìn)程內(nèi)部是用的話使用臨界區(qū)會帶來速度上的優(yōu)勢并能夠減少資源占用量。
通過互斥量可以指定資源被獨(dú)占的方式使用，但如果有下面一種情況通過互斥量就無法處理，比如現(xiàn)在一位用戶購買了一份三個并發(fā)訪問許可的數(shù)據(jù)庫系統(tǒng)，可以根據(jù)用戶購買的訪問許可數(shù)量來決定有多少個線程/進(jìn)程能同時進(jìn)行數(shù)據(jù)庫操作，這時候如果利用互斥量就沒有辦法完成這個要求，信號量對象可以說是一種資源計數(shù)器。
3、信號量：為控制一個具有有限數(shù)量用戶資源而設(shè)計。它允許多個線程在同一時刻訪問同一資源，但是需要限制在同一時刻訪問此資源的最大線程數(shù)目?；コ饬渴切盘柫康囊环N特殊情況，當(dāng)信號量的最大資源數(shù)=1就是互斥量了。
優(yōu)點(diǎn)：適用于對Socket（套接字）程序中線程的同步。
缺點(diǎn):
信號量機(jī)制必須有公共內(nèi)存，不能用于分布式操作系統(tǒng)，這是它最大的弱點(diǎn)；
信號量機(jī)制功能強(qiáng)大，但使用時對信號量的操作分散， 而且難以控制，讀寫和維護(hù)都很困難，加重了程序員的編碼負(fù)擔(dān)；
核心操作P-V分散在各用戶程序的代碼中，不易控制和管理，一旦錯誤，后果嚴(yán)重，且不易發(fā)現(xiàn)和糾正。
4、事件： 用來通知線程有一些事件已發(fā)生，從而啟動后繼任務(wù)的開始。
優(yōu)點(diǎn)：事件對象通過通知操作的方式來保持線程的同步，并且可以實(shí)現(xiàn)不同進(jìn)程中的線程同步操作。
2. 線程同步的方式有哪些？
1、臨界區(qū)：當(dāng)多個線程訪問一個獨(dú)占性共享資源時，可以使用臨界區(qū)對象。擁有臨界區(qū)的線程可以訪問被保護(hù)起來的資源或代碼段，其他線程若想訪問，則被掛起，直到擁有臨界區(qū)的線程放棄臨界區(qū)為止，以此達(dá)到用原子方式操 作共享資源的目的。
2、事件：事件機(jī)制，則允許一個線程在處理完一個任務(wù)后，主動喚醒另外一個線程執(zhí)行任務(wù)。
3、互斥量：互斥對象和臨界區(qū)對象非常相似，只是其允許在進(jìn)程間使用，而臨界區(qū)只限制與同一進(jìn)程的各個線程之間使用，但是更節(jié)省資源，更有效率。
4、信號量：當(dāng)需要一個計數(shù)器來限制可以使用某共享資源的線程數(shù)目時，可以使用“信號量”對象。
區(qū)別：
互斥量與臨界區(qū)的作用非常相似，但互斥量是可以命名的，也就是說互斥量可以跨越進(jìn)程使用，但創(chuàng)建互斥量需要的資源更多，所以如果只為了在進(jìn)程內(nèi)部是用的話使用臨界區(qū)會帶來速度上的優(yōu)勢并能夠減少資源占用量 。因?yàn)榛コ饬渴强邕M(jìn)程的互斥量一旦被創(chuàng)建，就可以通過名字打開它。
互斥量，信號量，事件都可以被跨越進(jìn)程使用來進(jìn)行同步數(shù)據(jù)操作。
3. 什么是臨界區(qū)，如何解決沖突？
每個進(jìn)程中訪問臨界資源的那段程序稱為臨界區(qū)，一次僅允許一個進(jìn)程使用的資源稱為臨界資源。
解決沖突的辦法：
如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個進(jìn)程進(jìn)入，如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其它所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待；
進(jìn)入臨界區(qū)的進(jìn)程要在有限時間內(nèi)退出。
如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象。
4.什么是死鎖？死鎖產(chǎn)生的條件？如何處理死鎖問題？
什么是死鎖：
在兩個或者多個并發(fā)進(jìn)程中，如果每個進(jìn)程持有某種資源而又等待其它進(jìn)程釋放它或它們現(xiàn)在保持著的資源，在未改變這種狀態(tài)之前都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生了死鎖。通俗的講就是兩個或多個進(jìn)程無限期的阻塞、相互等待的一種狀態(tài)。
死鎖產(chǎn)生的四個必要條件：（有一個條件不成立，則不會產(chǎn)生死鎖）
互斥條件：一個資源一次只能被一個進(jìn)程使用
請求與保持條件：一個進(jìn)程因請求資源而阻塞時，對已獲得資源保持不放
不剝奪條件：進(jìn)程獲得的資源，在未完全使用完之前，不能強(qiáng)行剝奪
循環(huán)等待條件：若干進(jìn)程之間形成一種頭尾相接的環(huán)形等待資源關(guān)系
常用的處理死鎖的方法有：死鎖預(yù)防、死鎖避免、死鎖檢測、死鎖解除、鴕鳥策略。
（1）死鎖的預(yù)防：基本思想就是確保死鎖發(fā)生的四個必要條件中至少有一個不成立：
① 破除資源互斥條件
② 破除“請求與保持”條件：實(shí)行資源預(yù)分配策略，進(jìn)程在運(yùn)行之前，必須一次性獲取所有的資源。缺點(diǎn)：在很多情況下，無法預(yù)知進(jìn)程執(zhí)行前所需的全部資源，因?yàn)檫M(jìn)程是動態(tài)執(zhí)行的，同時也會降低資源利用率，導(dǎo)致降低了進(jìn)程的并發(fā)性。
③ 破除“不可剝奪”條件：允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。當(dāng)一個已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請求而不能得到滿足時，它必須釋放已經(jīng)保持的所有資源，待以后需要時再重新申請。這意味著進(jìn)程已經(jīng)占有的資源會被暫時被釋放，或者說被搶占了。
④ 破除“循環(huán)等待”條件：實(shí)行資源有序分配策略，對所有資源排序編號，按照順序獲取資源，將緊缺的，稀少的采用較大的編號，在申請資源時必須按照編號的順序進(jìn)行，一個進(jìn)程只有獲得較小編號的進(jìn)程才能申請較大編號的進(jìn)程。
（2）死鎖避免：
死鎖預(yù)防通過約束資源請求，防止4個必要條件中至少一個的發(fā)生，可以通過直接或間接預(yù)防方法，但是都會導(dǎo)致低效的資源使用和低效的進(jìn)程執(zhí)行。而死鎖避免則允許前三個必要條件，但是通過動態(tài)地檢測資源分配狀態(tài)，以確保循環(huán)等待條件不成立，從而確保系統(tǒng)處于安全狀態(tài)。所謂安全狀態(tài)是指：如果系統(tǒng)能按某個順序?yàn)槊總€進(jìn)程分配資源（不超過其最大值），那么系統(tǒng)狀態(tài)是安全的，換句話說就是，如果存在一個安全序列，那么系統(tǒng)處于安全狀態(tài)。銀行家算法是經(jīng)典的死鎖避免的算法。
（3）死鎖檢測：
死鎖預(yù)防策略是非常保守的，他們通過限制訪問資源和在進(jìn)程上強(qiáng)加約束來解決死鎖的問題。死鎖檢測則是完全相反，它不限制資源訪問或約束進(jìn)程行為，只要有可能，被請求的資源就被授權(quán)給進(jìn)程。但是操作系統(tǒng)會周期性地執(zhí)行一個算法檢測前面的循環(huán)等待的條件。死鎖檢測算法是通過資源分配圖來檢測是否存在環(huán)來實(shí)現(xiàn)，從一個節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對訪問過的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有存在環(huán)，也就是檢測到死鎖的發(fā)生。
（1）如果進(jìn)程-資源分配圖中無環(huán)路，此時系統(tǒng)沒有死鎖。
（2）如果進(jìn)程-資源分配圖中有環(huán)路，且每個資源類中只有一個資源，則系統(tǒng)發(fā)生死鎖。
（3）如果進(jìn)程-資源分配圖中有環(huán)路，且所涉及的資源類有多個資源，則不一定會發(fā)生死鎖。
（4）死鎖解除：
死鎖解除的常用方法就是終止進(jìn)程和資源搶占，回滾。所謂進(jìn)程終止就是簡單地終止一個或多個進(jìn)程以打破循環(huán)等待，包括兩種方式：終止所有死鎖進(jìn)程和一次只終止一個進(jìn)程直到取消死鎖循環(huán)為止；所謂資源搶占就是從一個或者多個死鎖進(jìn)程那里搶占一個或多個資源。
（5）鴕鳥策略：
把頭埋在沙子里，假裝根本沒發(fā)生問題。因?yàn)榻鉀Q死鎖問題的代價很高，因此鴕鳥策略這種不采取任何措施的方案會獲得更高的性能。當(dāng)發(fā)生死鎖時不會對用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。
