1. 程序同步的基本概念
（1）程序同步的主要任務
使并發執行的諸程序之間能有效地共享資源和互相合作，進而使程式的執行具有可再現性。
（2）臨界資源
一次僅允許一個程序使用的資源。
*了解同步
互斥：在作業系統中，當一個程序進入臨界區使用臨界資源時，另一個程序必須等待，直到占用臨界資源的程序退出臨界區，我們稱程序之間的這種互相制約關系為“互斥”。
*同步：*多個互相合作的程序，在一些關鍵點上可能需要互相等待或互相交換資訊，這種互相制約關系稱為程序同步關系。可了解為“有序”。
（3）臨界區
每個程序中通路臨界資源的那段代碼叫臨界區。
為了正确同步，對臨界區的代碼要增加控制
進入區：對欲通路的臨界資源進行檢。若此刻未被通路，設正在通路的标志
臨界區：通路臨界資源的代碼。
退出區：将正在通路的标志恢複為未被通路的标志
剩餘區：其餘部分
（4）同步機制應遵循的規則
1）空閑讓進：資源使用最基本原則
2）忙則等待：保證互斥
3）有限等待：合适時被喚醒防止死等
4）讓權等待：能主動釋放CPU防止忙等
（5）硬體同步機制
許多計算機提供一些特殊的硬體指令，允許對一個字中的内容進行檢測和修正，或對兩個字的内容進行交換。利用這些特殊指令解決臨界區問題。
進入臨界區往往跟其标志有關，可将标志看做一個鎖，“鎖開”進入并關鎖，“鎖關”必須等待，初始時鎖是打開的。
①關中斷
進入鎖測試前關閉中斷，直到完成鎖測試并上鎖後才能打開中斷。程序在臨界區執行期間，系統不響應中斷，進而不引發排程。
缺點：
濫用風險
關中斷時間過長會影響效率，限制CPU交叉執行能力
不适用于多CPU系統
②Test-and-Set指令
boolean TS(boolean *lock)
{
Boolean old;
old=*lock;
*lock=TRUE;
return old;
}
為一個臨界資源設定一布爾變量lock，初值為false
do{
…
while TS(&lock) ;
critical section;
lock=FALSE;
remainder section;
}while(TRUE);
③利用Swap指令實作程序互斥
對換指令（intel 80x86中稱XCHG指令），用于交換兩個位元組的内容
void swap(boolean *a, boolean *b)
{boolean temp;
temp=*a;
*a=*b;
*b=temp;
}
為臨界資源設定一個全局布爾變量lock=false。每個程序一個局部布爾變量key。
do{
key=TRUE;
do{
swap(&lock,&key);
}while(key!=FALSE);
// 臨界區操作；
lock=FALSE;
//剩餘區；
}while(TRUE);
2. 信号量機制
（1） 整型信号量
信号量定義為一個整型量；根據初始情況賦相應的值；僅能通過兩個原子操作來通路。
P操作
wait(S):
While S<=0 do no-op;
S:=S-1;
V操作
signal(S):
S:=S+1;
（2） 記錄型信号量
整型信号量符合“有限等待”原則
signal釋放資源後，當CPU被配置設定給等待程序後，等待程序仍可繼續執行，可以符合“有限等待”。
但整型信号量不符合“讓權等待”原則
整型信号量的wait操作，當s ≤0時，目前程序會占着CPU不斷測試；
信号量原語不能被打斷，這個占有CPU的程序會一直不斷的占據CPU循環下去，陷入忙等。
改進：條件不符時應能夠主動放棄CPU
新問題：放棄CPU的程序進入阻塞隊列：因等待某信号量而放棄CPU的等待程序會有“若幹”個，需将它們組織管理起來，并在合适的時候喚醒。
#信号量結構資訊發生變化
不僅要有值的處理，還有隊列的處理。
此時形成記錄型資料結構，包括兩部分：
整型變量value(代表資源數目)
程序連結清單L(連結所有等待程序)：
代碼描述：
type Semaphore=record
value：integer;
L：list of PCB;
end;
操作：S.Value，S.L
Value>0，表示目前可用資源的數量；
Value≤0，其絕對值表示等待使用該資源的程序數，即在該信号量隊列上排隊的PCB的個數。
#P、V操作也有所變化
P操作
wait():
S.value = S.value - 1;
if S.value < 0 then block(S,L)
V操作
signal()：
S.value = S.value + 1;
if S.value <= 0 then wakeup(S,L)
• 定義信号量semaphore代表可用資源實體的數量，又叫信号燈。
• 當≥0，代表可供并發程序使用的資源實體數
• 當<0，表示正在等待使用該資源的程序數。
建立一個信号量必須經過說明，包括
• 信号量所代表的意義
• 賦初值
• 建立相應的資料結構，以便指向等待使用臨界區的程序。
除初值外，信号量的值僅能由标準原子操作P、V操作來改變。 PV操作是荷蘭語通過和釋放的意思。
（3）信号量的基本應用
1）實作程序互斥
設定一互斥信号量mutex，初值為1。
程序i：
P（mutex）；
critical section //操作共享資源R
V（mutex）
remainder section
互斥信号量注意點：
1. 互斥信号量mutex初值為1；
2. 每個程序中将臨界區代碼置于P(mutex)和V(mutex)原語之間
3. 必須成對使用P和V原語（在同一程序中），不能次序錯誤、重複或遺漏：
遺漏P原語則不能保證互斥通路
遺漏V原語則不能在使用臨界資源之後将其釋放（給其他等待的程序）；
2） 實作程序間的前驅關系（有序）
前趨關系:并發執行的程序P1和P2中，分别有代碼C1和C2，要求C1要在C2開始前完成；
為每對前趨關系設定一個同步信号量S12，并賦初值為0。則隻有V操作所在程序獲得cpu時能運作
P1 ： C1 ；signal(S)；
P2 ： wait(S)；C2 ；
控制同步順序的注意點
信号量值為0的點是限制的關鍵所在，成對使用P和V原語（在有先後關系的兩個程序中），不能次序錯誤、重複或遺漏，否則同步順序出錯。
（4） AND型信号量
出現原因：一些應用往往需要兩個或多個共享資源，而不是前述的一個資源。程序同時要求的共享資源越多，發生死鎖可能性越大。
解決思想：
一次性配置設定給程序所需資源，用完一起釋放。Wait操作時對它所有需要的資源都要判斷，有AND條件，故稱“AND同步”、“同時wait”。
Swait(S1, S2, …, Sn)
if （S1 >=1 and … and Sn>=1 ）then
for i:=1 to n do
Si:= Si -1 ;
endfor
else
将程序阻塞在第一個不能滿足資源信号量的隊列中
endif
Ssignal(S1, S2, …, Sn)
for i:=1 to n do
Si:= Si +1 ;
// 喚醒是以與si相關的阻塞程序
endfor
（5） 信号量集
**引入原因：**每次隻能獲得或釋放一個機關的資源，低效；某些時候資源配置設定有下限的限制；
修改：在大于可配置設定設定的下界值t前提下，每次可配置設定d個。
Swait(S1, t1, d1, …, Sn, tn, dn)
if S1>= t1 and … and Sn>= tn then
for i:=1 to n do
Si:= Si - di ;
endfor
else
…
endif
Ssignal(S1, d1, …, Sn, dn)
for i:=1 to n do
Si:= Si +di ;
….
endfor
信号量集的一個特例
隻有一個信号量S的幾種特殊情況：
①Swait(S, d, d)，，允許每次申請d個資源，若現有資源數少于d，不予配置設定。
②Swait(S, 1, 1)，蛻化為一般的記錄型信号量，一次申請一個，至多配置設定一個(S>1時可計數，或S=1時可控制互斥)。
③Swait(S, 1, 0)，當S>=1時，允許多個程序進入某特定區，當S變為0後，阻止任何程序進入特定區，相當于可控開關。并不對S資源的數量産生影響。