2.3 進程同步

1. 理解同步的含義

2. 信號量機制控制進程同步

3. 管程

進程間有什么相互影響？

兩種制約關(guān)系：

1. 間接相互制約關(guān)系：主要源于資源共享,表現(xiàn)為進程A---打印機資源---進程B（互斥）

2. 直接相互制約關(guān)系：主要源于進程合作，表現(xiàn)為進程A寫緩沖---進程B讀緩沖（有序）

1.進程同步的基本概念

1）進程同步的主要任務(wù)：使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。

。

R1和R2為處理機中的兩個寄存器。兩個進程各自對x作加1操作。

所以對生產(chǎn)者和消費者而言，counter應(yīng)作為臨界資源，應(yīng)對其互斥訪問

若是一群生產(chǎn)者和消費者生產(chǎn)者之間共同要影響的變量in要互斥；消費者間的out也一樣

理解同步

互斥：在操作系統(tǒng)中，當一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，直到占用臨界資源的進程退出臨界區(qū)，我們稱進程之間的這種相互制約關(guān)系為“互斥”。

同步：多個相互合作的進程，在一些關(guān)鍵點上可能需要互相等待或互相交換信息，這種相互制約關(guān)系稱為進程同步關(guān)系。可理解為“有序”。

如：生產(chǎn)和消費的“有序”關(guān)系靠對counter的正確判斷達到，而對counter的修改必須“互斥”修改。

4）同步機制應(yīng)遵循的規(guī)則

實現(xiàn)互斥的方法應(yīng)符合如下每條原則

?空閑讓進：資源使用最基本原則

?忙則等待：保證互斥

?有限等待：合適時被喚醒防止死等

?讓權(quán)等待：能主動釋放CPU防止忙等

同步控制的關(guān)鍵

主要涉及”判斷”和”修改標志”操作

? 不應(yīng)被打斷（原語，OS核心態(tài)運行）

? 如何制定一種寫法，使標志的使用適用于各種具體應(yīng)用情況？

硬件同步機制

? 許多計算機提供一些特殊的硬件指令，允許對一個字中的內(nèi)容進行檢測和修正，或?qū)蓚€字的內(nèi)容進行交換。利

用這些特殊指令解決臨界區(qū)問題。

? 進入臨界區(qū)往往跟其標志有關(guān)，可將標志看做一個鎖，“鎖開”進入并關(guān)鎖，“鎖關(guān)”必須等待，初始時鎖是打開的。

關(guān)中斷

【】 進入鎖測試前關(guān)閉中斷，直到完成鎖測試并上鎖后才能打開中斷。進程在臨界區(qū)執(zhí)行期間，系統(tǒng)不響應(yīng)中斷，從而不引發(fā)調(diào)度。

【】缺點：

l 濫用風(fēng)險

l 關(guān)中斷時間過長會影響效率，限制CPU交叉執(zhí)行能力

l 不適用于多CPU系統(tǒng)

【】完全利用軟件方法，有很大局限性，也不適于多進程，現(xiàn)在已很少采用。

【】硬件指令機械操作可保證鎖開、關(guān)操作不被打斷；適用于任意數(shù)目的進程。但等待要耗費CPU時間，不能實現(xiàn)“讓權(quán)等待”，從等待進程中隨機選擇一個進入臨界區(qū)，有的進程可能一直選不上，難以實現(xiàn)較為復(fù)雜的進程同步問題。

2.信號量機制

2）記錄型信號量

【】 整型信號量符合“有限等待”原則

?signal釋放資源后，當CPU被分配給等待進程后，等待進程仍可繼續(xù)執(zhí)行，可以符合“有限等待”。

【】 但整型信號量不符合“讓權(quán)等待”原則

?整型信號量的wait操作，當s ≤0時，當前進程會占著CPU不斷測試；

?信號量原語不能被打斷，這個占有CPU的進程會一直不斷的占據(jù)CPU循環(huán)下去，陷入忙等。

改進：條件不符時應(yīng)能夠主動放棄CPU

新問題：放棄CPU的進程進入阻塞隊列：因等待某信號量而放棄CPU的等待進程會有“若干”個，需將它們組織

管理起來，并在合適的時候喚醒。

信號量結(jié)構(gòu)信息發(fā)生變化

【】不僅要有值的處理，還有隊列的處理。

【】此時形成記錄型數(shù)據(jù)結(jié)構(gòu)，包括兩部分：

?整型變量value(代表資源數(shù)目)

?進程鏈表L(鏈接所有等待進程)：

【】 代碼描述：

type Semaphore=record

value：integer;

L：list of PCB;

end;

?操作：S.Value，S.L

定義信號量semaphore代表可用資源實體的數(shù)量。又叫信號燈。

? 當≥0，代表可供并發(fā)進程使用的資源實體數(shù)

? 當<0，表示正在等待使用該資源的進程數(shù)。

【】建立一個信號量必須經(jīng)過說明，包括

? 信號量所代表的意義

? 賦初值

? 建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以便指向等待使用臨界區(qū)的進程。

【】除初值外，信號量的值僅能由標準原子操作P、V操作來改變。 PV操作是荷蘭語通過和釋放的意思。

3）信號量的基本應(yīng)用

【】實現(xiàn)進程互斥

【】實現(xiàn)進程間的前趨關(guān)系（有序）

互斥信號量注意點：

1. 互斥信號量mutex初值為1；

2. 每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間

3. 必須成對使用P和V原語（在同一進程中），不能次序錯誤、重復(fù)或遺漏：

l 遺漏P原語則不能保證互斥訪問

l 遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；

控制同步順序的注意點

? 信號量值為0的點是限制的關(guān)鍵所在；

? 成對使用P和V原語（在有先后關(guān)系的兩個進程中），不能次序錯誤、重復(fù)或遺漏，否則同步順序出錯。

2）民航售票系統(tǒng)問題

【】 n個售票處。每個售票處通過終端訪問系統(tǒng)的公用數(shù)據(jù)區(qū)

【】假定公用數(shù)據(jù)區(qū)中分別用Ri表示某時間i次航班的現(xiàn)存票數(shù)。

【】Pi表示某售票處的處理進程，試用信號量實現(xiàn)進程間的互斥關(guān)系。

5）信號量集

【】引入原因：

l 每次只能獲得或釋放一個單位的資源，低效；

l 某些時候資源分配有下限的限制；

l 修改：在大于可分配設(shè)置的下界值t前提下，每次可分配d個。

信號量集的一個特例

【】 只有一個信號量S的幾種特殊情況：

l Swait(S,? d, d)，，允許每次申請d個資源，若現(xiàn)有資源數(shù)少于d，不予分配。

l Swait(S,1,1)，蛻化為一般的記錄型信號量，一次申請一個，至多分配一個(S>1時可計數(shù)，或S=1時可控制互斥)。

l Swait(S,1,0)，當S>=1時，允許多個進程進入某特定區(qū)，當S變?yōu)?后，阻止任何進程進入特定區(qū)，相當于可控開關(guān)。并不對S資源的數(shù)

*信號量題目做題一般方法：

1. 分析問題，找出同步、互斥關(guān)系

2. 根據(jù)資源設(shè)置信號量變量

3. 寫出代碼過程，并注意P、V操作的位置

4. 檢查代碼，模擬機器運行，體驗信號量的變化和程序運行過程是否正確。