操作系統中互斥與同步問題求解方法的探析

唐伎玲，黃 葵，谷 赫

(長春大學 計算機科學技術學院，長春130022)

0 前言

多個進程在并發執行時，由于共享同一變量或系統資源，如打印機等，使這些并發執行的進程只能互斥地訪問，致使進程之間形成了相互制約的關系，稱為進程互斥。

一組進程，為協調其推進速度，在某些關鍵點處需要相互等待與相互喚醒，進程之間這種相互制約的關系稱為進程同步。

互斥與同步是操作系統與并發程序設計的核心問題，為此操作系統必須提供用于實現同步的機制。從本質上講，同步工具就是能用于進程(線程)等待或喚醒的機制，信號量機制是解決同步問題的常用工具。

如何使用信號量機制解決各種同步問題，需要準確理解并牢記信號量機制的定義，還需要分析和學習典型例子，并通過一定數量的練習來提高解題的技巧。

1 經典案列

1.1 圖書借閱系統

(x:某種書冊數，設當前x=1)。

如圖1 左圖所示，在并發環境下，兩個終端程序若按圖中標記的數字順序并發執行，則會出現將一本書借給兩個讀者的錯誤。為了避免出現這類的錯誤，對共享變量X 的訪問必須互斥，設置信號量mutex，初值為1，控制的代碼流程如圖1 右圖所示。

圖1 圖書借問系統

1.2 司機－售票員問題。

在并發環境下，司機進程和售票員進程向前推進過程中有兩個制約關系，如圖2 左圖所示。這是典型的同步控制，設置信號量s1 和s2，初值均為0，控制的代碼流程如圖2 右圖所示。

圖2 司機－售票員問題

1.3 生產者－消費者問題

生產者－消費者問題是一個著名的進程同步問題。它描述的是:有一群生產者進程在生產產品，并將這些產品提供給消費者進程去消費。為使生產者進程與消費者進程能并發執行，在兩者之間設置了一個具有n 個緩沖區的緩沖池，生產者進程將它所生產的產品放入一個緩沖區中;消費者進程可從一個緩沖區中取走產品去消費。盡管所有的生產者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程到一個空緩沖區去取產品，也不允許生產者進程向一個已裝滿產品且尚未被取走的緩沖區中投放產品。

分析問題:將產品和緩沖區視為組合資源，生產者進程和消費者進程的推進過程中要不斷使用和釋放這對組合資源，因此設兩個信號量empty=n 和full=0，分別來管理緩沖區和產品。生產者進程在生產產品放入緩沖區時，要先申請一個緩沖區，然后釋放一個產品，因此先執行wait(empty)，后執行signal(full)。消費者從緩沖區取產品時，要先申請一個產品，然后釋放一個緩沖區，因此要先執行wait(full)，后執行signal(empty)。又因緩沖區是多個進程共同訪問，必須互斥，因此還需設置互斥信號量mutex=1，控制的主要代碼如圖3 所示。

1.4 讀者－寫者問題

所謂“讀者－寫者問題”是指一個數據文件或記錄可被多個進程共享，允許多個進程同時讀一個共享對象，因為讀操作不會使數據文件混亂。但不允許一個寫進程和其他讀進程或其它寫進程同時訪問共享對象。因為這種訪問將會引起文件內容的混亂。

分析問題:這是多個進程在共享過程中又有互斥控制的問題。因為寫進程與寫進程之間、寫進程與讀進程之間互斥，故設置一個信號量w=1。又因讀進程之間共享，讓第一個讀進程執行wait(w)操作，最后一個讀進程執行signal(w)。為了區分讀進程，設置一個統計變量read_count，初值為0，每當一個讀進程到達執行read_count+1，離開時執行read_count－1;read_count=1 時表示第1 個讀進程到達，當read_count=0 時表示最后一個讀進程要離開。由于read_count 是多個讀進程共享變量，必須互斥訪問，為此再設置一個信號量r=1。整個問題同步控制的主要代碼如圖4 所示。

圖3 生產者－消費者問題

1.5 父母兒女吃水果問題

桌上有一個盤子，可以存放一個水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中，一個兒子專等吃盤中的香蕉，而一個女兒專等吃盤中的蘋果，試寫出這兩個并發進程能正確執行的程序。

分析問題:盤子放一個水果，這是互斥控制;女兒吃父親放的蘋果，兒子吃母親放的香蕉，這是兩個同步控制，因此設置一個互斥信號量S=1，初值為1，兩個同步信號量a 和b，初值均為0?？刂拼a的流程如圖5 所示。

圖4 讀者－寫者問題

圖5 父母兒女吃水果問題(一)

修改上述問題，桌上有一個盤子，可以存放兩個水果，但每次存和取一個水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中，兩個兒子專等吃盤中的香蕉，而兩個女兒專等吃盤中的蘋果，試寫出這兩個并發進程能正確執行的程序。

分析問題:由于盤子可以放兩個水果，故設置同種資源信息量E=2，盤子每次放取水果只能一個，因此設置互斥信號量S=1，兩個同步信號量a=0 和b=0。程序流程如圖6 所示。

圖6 父母兒女吃水果問題(二)

2 求解規律

通過上述案例的求解分析，關于互斥與同步問題總結出以下幾種的常見類型。不同類型的同步問題利用信號量機制去求解時，信號量的初值設置以及wait 和signal 操作的規律如表1 所示。編寫同步問題的代碼時，要分析有哪些進程，進程在推進過程中使用哪類資源，以確定互斥和同步的類型;然后按著進程推進的活動編寫代碼，設置信號量的初值和wait、signal 操作。代碼編寫完成后，還需進一步分析是否有死鎖和饑餓發生;若有則要解決，完善代碼;最后還要優化代碼，提高程序的并發度。

表1 同步問題類型表

3 結語

同步控制是操作系統、并發程序設計、多核多線程等計算機專業課程中的關鍵問題，也是難點問題。本文選擇及設計了幾個經典案例，通過對案例問題的求解分析，將同步控制問題劃分為互斥、同步、同種資源等六種類型，并給出了解決這六種類型問題的求解規律，希望對學習者有所借鑒和幫助。

［1］ 湯小丹，湯子瀛.計算機操作系統［M］.西安:西安電子科學大學出版社，2007.

［2］ 左萬歷，周長林.操作系統教程［M］.北京:高等教育出版社，2007.

［3］ 左萬歷.操作系統習題與實驗指導［M］.北京:高等教育出版社，2005.

［4］ Gary Nutt.操作系統現代觀點［M］.孟祥山，晏益，譯.北京:機械工業出版社，2004.