進程同步

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

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

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

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

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

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

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

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

為了實現進程的同步，必須遵守同步規則。用于實現進程間同步的工具稱為同步機制。對于關鍵區域的操作，同步機制應遵循以下四個標準。

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

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

有限等待:對于需要訪問關鍵資源的進程，應保證在有限時間內進入相應的關鍵區域，進入關鍵區域的進程應在有限時間內完成其操作，釋放資源并退出關鍵區域。

讓路并等待:對于那些當前處于阻塞狀態且無法進入臨界區的進程，它們應該放棄占用CPU，以便其他進程可以獲得CPU的使用權。

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

硬件模式

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

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

軟件模式

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

進程同步

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

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

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

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

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

管程機構：為了解決信號量機制中存在的問題，1974年和1975年，Hansen和Hoare提出了管道機制，該機制集中管理分散在各個進程中的關鍵區域，并用數據結構抽象地表示系統中的共享資源。Pipeline定義了一個數據結構和一組可以由并發進程（在數據結構上）執行的操作，這些操作可以同步進程并更改管道中的數據。

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

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

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

問題描述

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

在這個過程中，如果生產者進程沒有空的緩沖區來放置產品，它將轉入等待狀態，直到消費者取走產品并將其喚醒；同樣，消費者流程將轉變為等待狀態，因為在生產者放置產品后將其喚醒之前沒有產品。

問題解決

以記錄信號量為例，它使用互斥體來實現進程對緩沖區的互斥使用。此外，信號empty和full分別表示空緩沖區的數量和滿緩沖區（即產品）的數量。