進程同步（英文名稱:Process Synchronization）是指廣義上的并發(fā)進程在執(zhí)行序列中的相互制約，它包括進程的同步和互斥。從狹義上講，它是指為完成某項任務(wù)而建立的兩個或兩個以上的流程因需要在某些崗位上協(xié)調(diào)其工作順序而產(chǎn)生的相互等待限制。進程同步可以滿足某些共享資源（如I/O設(shè)備）中進程獨占訪問的要求。

進程同步的實現(xiàn)需要遵循相應(yīng)的機制和方法，其同步機制包括空閑產(chǎn)出、繁忙等待、受限等待和產(chǎn)出等待。進程同步的實現(xiàn)方法可以分為軟件方法和硬件方法，其中硬件方法包括中斷禁用和特殊機器指令，而軟件方法可以依靠鎖機制、信號量機制和管道機制，信號量機制可以細分為塑料信號量、記錄信號量以及信號量和信號量集類型。

典型的同步問題包括生產(chǎn)者-消費者問題、讀者-作者問題和哲學(xué)家進餐問題，這些問題可以通過不同的信號量機制來解決，生活中的實際問題可以直接或間接地參考這些經(jīng)典問題來解決。

過程限制關(guān)系：在操作系統(tǒng)中，雖然進程可以獨立運行，但它們之間也會相互制約。進程同步是操作系統(tǒng)管理共享資源和避免由并發(fā)進程引起的時間相關(guān)錯誤的一種方法。進程之間的關(guān)系可以表現(xiàn)為直接的相互制約（同步關(guān)系）和短暫的相互制約（互斥關(guān)系）。從廣義上講，進程同步被定義為并發(fā)進程在執(zhí)行時序上的相互制約，它包括進程同步和進程互斥。

間接相互制約（相互排斥）：間接相互限制是指進程之間競爭獨占資源（互斥資源）而造成的限制，即設(shè)置不允許兩個進程同時使用某個資源，此時一個進程要求使用該資源，而該資源正在被另一個進程使用，因此該進程必須等待已占用該資源的進程釋放該資源后才能使用。這種制約關(guān)系的基本形式是“過程-資源-過程”。這種約束關(guān)系源于多個同類進程需要互斥共享某些系統(tǒng)資源（如打印機），同類進程之間設(shè)置互斥以達到互斥訪問資源的目的。

直接相互制約（同步）：同步關(guān)系是指需要在某些地方協(xié)調(diào)工作并相互等待和交換信息的伙伴流程之間的約束關(guān)系。也就是說，如果一個進程沒有收到另一個進程提供的必要信息，它就無法繼續(xù)運行。這種情況表明，兩個進程需要在某個時候相互交換信息和通信。這種制約關(guān)系的基本形式是“過程-過程”。這種限制主要來自于進程之間的協(xié)作，在不同的進程之間設(shè)置同步以實現(xiàn)各種進程之間的同步。

一般來說，一個進程相對于另一個進程的運行速度是不確定的。也就是說，流程在異步環(huán)境中運行，但協(xié)作流程需要在某些關(guān)鍵點上協(xié)調(diào)工作。直接約束關(guān)系狹義上也叫進程同步。它是指為完成某項任務(wù)而建立的兩個或多個流程之間的相互等待約束關(guān)系，因為它們需要在某些崗位上協(xié)調(diào)它們的工作順序。

在運行過程中，一個進程一般會與其他進程共享資源，有些資源同一時間只能由一個進程使用。這種資源被稱為關(guān)鍵資源。包括打印機和繪圖儀在內(nèi)的許多物理設(shè)備都是關(guān)鍵資源。為了保證關(guān)鍵資源的正確使用，關(guān)鍵資源的訪問過程一般分為四個部分，即進入?yún)^(qū)、關(guān)鍵區(qū)、退出區(qū)和剩余區(qū)。無論是硬件關(guān)鍵資源還是軟件關(guān)鍵資源，多個進程必須互斥地訪問它。訪問進程中關(guān)鍵資源的代碼稱為關(guān)鍵部分。每個進程的臨界區(qū)代碼可以不同。為了進入關(guān)鍵區(qū)域并使用關(guān)鍵資源，需要在進入?yún)^(qū)域中檢查是否有可能進入關(guān)鍵區(qū)域；如果可以進入臨界區(qū)，通常會設(shè)置相應(yīng)的“訪問臨界區(qū)”標志，以防止其他進程同時進入臨界區(qū)。這個代碼叫做進入臨界區(qū)。如果此時某個進程正在訪問關(guān)鍵資源，則該進程無法進入關(guān)鍵區(qū)域。用于清除關(guān)鍵區(qū)域后的“訪問關(guān)鍵區(qū)域”標志的部分代碼稱為出口區(qū)域。除了入口區(qū)域、關(guān)鍵區(qū)域和出口區(qū)域之外，其余區(qū)域是其他部分的代碼。

為了實現(xiàn)進程的同步，必須遵守同步規(guī)則。用于實現(xiàn)進程間同步的工具稱為同步機制。對于關(guān)鍵區(qū)域的操作，同步機制應(yīng)遵循以下四個標準。

Idle yield:當臨界區(qū)中沒有進程時，表明臨界資源處于空閑狀態(tài)，應(yīng)該允許請求進入臨界區(qū)的進程立即進入自己的臨界區(qū)，以有效地使用臨界資源。

繁忙等待:當現(xiàn)有進程進入關(guān)鍵區(qū)域時，表明正在訪問關(guān)鍵資源，因此其他試圖進入關(guān)鍵區(qū)域的進程必須等待，以確保對關(guān)鍵資源的互斥訪問。

有限等待:對于需要訪問關(guān)鍵資源的進程，應(yīng)保證在有限時間內(nèi)進入相應(yīng)的關(guān)鍵區(qū)域，進入關(guān)鍵區(qū)域的進程應(yīng)在有限時間內(nèi)完成其操作，釋放資源并退出關(guān)鍵區(qū)域。

讓路并等待:對于那些當前處于阻塞狀態(tài)且無法進入臨界區(qū)的進程，它們應(yīng)該放棄占用CPU，以便其他進程可以獲得CPU的使用權(quán)。

進程同步問題可以通過硬件方法或軟件方法來解決。用于實現(xiàn)系統(tǒng)中進程之間同步和互斥的機制稱為同步機制。同步機制很少單獨采用軟件方法，而使用硬件方法實現(xiàn)互斥的主要思想是使用一條指令來檢查和修改標志，或者通過中斷禁用來確保檢查和修改作為一個整體進行，從而確保檢查和修改操作不會中斷。它具有應(yīng)用范圍廣、簡單和支持多個關(guān)鍵領(lǐng)域的優(yōu)點。常見的同步機制有:鎖機制、信號量機制和管道機制。

硬件模式

中斷禁用：中斷禁用使每個進程在進入臨界區(qū)后立即關(guān)閉所有中斷，并在離開臨界區(qū)前重新打開中斷。由于中斷禁用，時鐘中斷也被禁止，因此CPU不會切換到另一個進程。這種賦予用戶進程關(guān)閉中斷的權(quán)利的方法有很大的缺點。一旦進程關(guān)閉中斷，如果它不再打開中斷，系統(tǒng)可能會被終止。

特殊機器指令：許多計算機（尤其是多處理器計算機）都有一個稱為TSL（測試和設(shè)置鎖定）的指令:TSLRX，Lock。它將內(nèi)存字鎖的內(nèi)容讀入寄存器RX，然后在地址單元中存儲一個非零值。讀取和存儲數(shù)據(jù)的操作是不可分的，也就是說，在此指令完成之前，其他進程無法訪問該單元。然而，使用TSL指令解決進程互斥進入臨界區(qū)的問題可能會導(dǎo)致“忙等待”——如果一個進程已經(jīng)進入臨界區(qū)，后者將繼續(xù)使用TSL指令進行測試并等待前者解鎖。

軟件模式

鎖定機構(gòu)：鎖機制的基本內(nèi)容是用變量w來表示一個關(guān)鍵資源的狀態(tài)，w稱為鎖或鎖位置。W=0表示資源可用；W=1表示資源正在被使用。在使用關(guān)鍵資源之前，進程需要檢查鎖變量的值。如果值為0，鎖將被設(shè)置為1（已鎖定）。如果值為1，它將返回到第一步重新檢查鎖變量的值。當進程使用完資源后，鎖應(yīng)該設(shè)置為0。它的標準原語是lock（w）和unlock（w）。

進程同步

雖然鎖定機構(gòu)簡單方便，但其效率很低。當一個進程處于臨界區(qū)時，其他想要進入臨界區(qū)的進程必須不斷地進行測試，從而處于繁忙的等待狀態(tài)，導(dǎo)致處理器時間的浪費。

信號量機制：在操作系統(tǒng)中，信號量是一個代表資源的物理量，它是一個與隊列相關(guān)的整數(shù)變量。它的值只能通過P和V操作來更改，操作系統(tǒng)使用它的狀態(tài)來管理資源和進程。信號量同步機制是由荷蘭計算機科學(xué)家Dijkstra于1965年首次提出的。其基本思想是使用標準原語操作來解決多個協(xié)作進程之間的信號同步。其標準原語包括wait（S）和signa（S）訪問，也可以記錄為“P操作”和“V操作”。常見的信號量機制有:整形信號量由資源號的整數(shù)S表示，并由基元wait和signal操作。信號量的值只能由兩個標準原子操作wait和signal訪問。

和旗語：一個進程在運行過程中經(jīng)常需要申請多個共享資源。如果使用整數(shù)或記錄信號量，進程可能會由于申請資源的順序不正確而死鎖。為了解決這個問題，引入了信號量同步機制。其基本思想是將進程在整個運行過程中所需的所有資源一次性分配給該進程，然后在該進程被使用后一起釋放。只要有一種資源不能分配給該進程，所有其他可能分配給它的資源都不會分配給它。

信號量集類型：在記錄信號量機制中，一次只能獲得或釋放一個單位的關(guān)鍵資源。如果一次需要N個關(guān)鍵資源，則需要N次等待操作，這是非常低效的。此外，在某些情況下，當資源量低于某個限制時，它將不會被分配。因此，在每次分配之前，必須測試資源的數(shù)量，看它是否大于其下限。基于以上兩點，AND信號量機制可以擴展為廣義的“信號量集”機制。Swait操作可以描述如下，其中s是信號量，d是所需值，t是下限。

在信號量機制中，由于每個想要訪問關(guān)鍵資源的進程都必須有自己的同步操作等待和信號，因此大量的同步操作分散在每個進程中。它不僅給系統(tǒng)的管理帶來了麻煩，而且由于同步操作的使用不當而導(dǎo)致系統(tǒng)死鎖。

管程機構(gòu)：為了解決信號量機制中存在的問題，1974年和1975年，Hansen和Hoare提出了管道機制，該機制集中管理分散在各個進程中的關(guān)鍵區(qū)域，并用數(shù)據(jù)結(jié)構(gòu)抽象地表示系統(tǒng)中的共享資源。Pipeline定義了一個數(shù)據(jù)結(jié)構(gòu)和一組可以由并發(fā)進程（在數(shù)據(jù)結(jié)構(gòu)上）執(zhí)行的操作，這些操作可以同步進程并更改管道中的數(shù)據(jù)。

管道的主要特征包括共享:一個進程通過調(diào)用管道的一個進程進入管道，管道中的移除進程可以由所有想要調(diào)用管道進程的進程共享。安全性:管道的本地數(shù)據(jù)變量只能由管道的進程訪問，而不能由任何其他外部進程訪問，并且管道的進程不能訪問任何不屬于其本地的變量。互斥:在任何時候，只有一個進程可以進入管道執(zhí)行，其他任何調(diào)用管道的進程都將被阻塞，只能等待當前正在訪問的進程退出管道。

使用管道實現(xiàn)進程同步時，必須設(shè)置同步工具，如兩個同步操作原語wait和signal。當進程通過管道請求獲得關(guān)鍵資源但未能滿足這些資源時，管道調(diào)用wait原語使進程等待并將其放入等待隊列。只有在另一個進程訪問并釋放資源后，管道才會再次調(diào)用signal原語來喚醒隊列頭進程。管道流程由四個部分組成，它們是管道流程的名稱；共享數(shù)據(jù)的描述和說明；用于操作共享數(shù)據(jù)結(jié)構(gòu)的一組過程；共享數(shù)據(jù)的初始化設(shè)置。

在現(xiàn)實生活中，許多事件需要相互同步。在多程序環(huán)境中，進程同步是一個非常重要和有趣的問題，吸引了許多學(xué)者對其進行研究，并由此產(chǎn)生了一系列經(jīng)典的進程同步問題，其中比較經(jīng)典的有生產(chǎn)者-消費者問題、讀者-作者問題、哲學(xué)家進餐問題等。參考經(jīng)典問題可以直接或間接解決生活中的實際問題。

問題描述

生產(chǎn)者-消費者問題，也稱為緩沖區(qū)問題，是計算機操作系統(tǒng)中相互協(xié)作的并發(fā)進程之間的抽象。其核心內(nèi)容是一組生產(chǎn)者流程和消費者流程。生產(chǎn)者負責生產(chǎn)產(chǎn)品，消費者負責消費產(chǎn)品。在它們之間設(shè)置一個具有n個緩沖區(qū)的緩沖池，供生產(chǎn)者進程和消費者進程共享。生產(chǎn)者的工作是生產(chǎn)產(chǎn)品并將其放入空緩沖區(qū)；消費者從包含用于消費的產(chǎn)品的緩沖器中取出產(chǎn)品。兩人互相等待，互相喚醒。

在這個過程中，如果生產(chǎn)者進程沒有空的緩沖區(qū)來放置產(chǎn)品，它將轉(zhuǎn)入等待狀態(tài)，直到消費者取走產(chǎn)品并將其喚醒；同樣，消費者流程將轉(zhuǎn)變?yōu)榈却隣顟B(tài)，因為在生產(chǎn)者放置產(chǎn)品后將其喚醒之前沒有產(chǎn)品。

問題解決

以記錄信號量為例，它使用互斥體來實現(xiàn)進程對緩沖區(qū)的互斥使用。此外，信號empty和full分別表示空緩沖區(qū)的數(shù)量和滿緩沖區(qū)（即產(chǎn)品）的數(shù)量。