- 順序程序設(shè)計(jì)
單個(gè)程序內(nèi)部只有在前一個(gè)操作結(jié)束后，才能開(kāi)始后繼操作塘秦，這稱(chēng)為程序內(nèi)部順序性建蹄；多個(gè)程序合力去完成一個(gè)計(jì)算任務(wù)碌更，這些程序也按照調(diào)用次序有序執(zhí)行，這稱(chēng)為程序外部順序性洞慎。程序順序執(zhí)行的最終輸出至于初始輸入數(shù)據(jù)有關(guān)痛单，而與時(shí)間無(wú)關(guān)，好處在于方便編碼和調(diào)試劲腿，缺點(diǎn)在于效率不高 - 并發(fā)程序設(shè)計(jì)
自從操作系統(tǒng)引入并發(fā)程序設(shè)計(jì)技術(shù)后旭绒，程序的執(zhí)行不再是順序的，一個(gè)程序未執(zhí)行完而另一個(gè)程序便已開(kāi)始執(zhí)行焦人，程序外部的順序特性消失挥吵，程序與計(jì)算不再一一對(duì)應(yīng)。（《深入理解計(jì)算機(jī)系統(tǒng)》中控制流的概念可以很好地幫助理解并行和并發(fā)）花椭，并發(fā)的實(shí)質(zhì)是處理器在幾個(gè)程序之間的多路復(fù)用忽匈，產(chǎn)生了資源共享的需求。
并發(fā)程序的無(wú)關(guān)性
并發(fā)程序的無(wú)關(guān)性是進(jìn)程的執(zhí)行與時(shí)間無(wú)關(guān)的一個(gè)充分條件矿辽，在1966年由bernstein提出丹允。只要滿(mǎn)足Bernstein條件郭厌，并發(fā)執(zhí)行的程序就可以保持封閉性和可再現(xiàn)性。
鑒于簡(jiǎn)書(shū)不支持LaTeX公式雕蔽，有興趣自己查吧折柠，文字表述總是不如數(shù)學(xué)公式直觀(guān)。
并發(fā)進(jìn)程的交互
如果進(jìn)程間不滿(mǎn)足上面提及的Bernstein條件批狐，那么他們就會(huì)因?yàn)楣蚕碛?jì)算機(jī)資源而存在競(jìng)爭(zhēng)與協(xié)作關(guān)系(又稱(chēng)互斥與同步)
- 進(jìn)程互斥是指若過(guò)個(gè)進(jìn)程因相互爭(zhēng)奪獨(dú)占型資源而產(chǎn)生的競(jìng)爭(zhēng)制約關(guān)系
- 進(jìn)程同步是指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來(lái)協(xié)調(diào)其活動(dòng)扇售，因?yàn)闆](méi)需要在某些位置上排定執(zhí)行的先后次序而等待、傳遞信號(hào)或消息所產(chǎn)生的協(xié)作制約關(guān)系
不難看出嚣艇，進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系承冰，即逐次使用互斥共享資源，也是對(duì)進(jìn)程使用資源的次序的一種協(xié)調(diào)髓废。由此，我們提出同步機(jī)制這個(gè)概念该抒，用于解決共享資源問(wèn)題慌洪。
臨界區(qū)
同上面的概念類(lèi)似，兩個(gè)或多個(gè)進(jìn)程讀寫(xiě)某些共享數(shù)據(jù)凑保，而最后的結(jié)果取決于進(jìn)程運(yùn)行得精確時(shí)序(也就是這些進(jìn)程不滿(mǎn)足Bernstein條件)冈爹，我們把這種情況稱(chēng)為競(jìng)爭(zhēng)條件。解決競(jìng)爭(zhēng)條件的方法是實(shí)現(xiàn)互斥欧引，即以某種手段確保當(dāng)一個(gè)進(jìn)程在使用一個(gè)共享變量或文件時(shí)频伤，其他進(jìn)程不能做同樣的操作。
我們把對(duì)共享內(nèi)存進(jìn)行訪(fǎng)問(wèn)的程序片段稱(chēng)為臨界區(qū)芝此，如果存在某些方案憋肖，使得兩個(gè)進(jìn)程不可能同時(shí)處于臨界區(qū)中，就能夠避免競(jìng)爭(zhēng)條件婚苹。對(duì)于這些方案岸更，需要滿(mǎn)足一下4個(gè)條件
- 任何兩個(gè)進(jìn)程不能同時(shí)處于其臨界區(qū)
- 不應(yīng)對(duì)CPU的速度和數(shù)量做任何假設(shè)
- 臨界區(qū)外運(yùn)行得進(jìn)程不得阻塞其他進(jìn)程
- 不能使進(jìn)程無(wú)限期等待進(jìn)入臨界區(qū)
忙等待的互斥方案
本節(jié)將討論幾種實(shí)現(xiàn)互斥的方案。在這些方案中膊升，當(dāng)一個(gè)進(jìn)程在臨界區(qū)中更新共享內(nèi)存時(shí)怎炊，其他進(jìn)程將不會(huì)進(jìn)入其臨界區(qū)，也不會(huì)帶來(lái)任何麻煩
1. 屏蔽中斷
在單處理器系統(tǒng)中廓译，最簡(jiǎn)單的方法就是使每個(gè)進(jìn)程剛剛進(jìn)入臨界區(qū)后立即屏蔽所有中斷评肆，并在就要離開(kāi)之前再打開(kāi)中斷。屏蔽中斷后非区，時(shí)鐘中斷也會(huì)被屏蔽瓜挽。CPU只有發(fā)生時(shí)鐘中斷或其他中斷時(shí)才會(huì)進(jìn)行進(jìn)程切換，這樣征绸，在屏蔽中斷之后CPU將不會(huì)被切換到其他進(jìn)程秸抚。于是速和，一旦某個(gè)進(jìn)程屏蔽中斷之后，他就可以檢查和修改共享內(nèi)存剥汤，而不必?fù)?dān)心其他進(jìn)程介入颠放。
- 把屏蔽中斷的權(quán)利交給用戶(hù)進(jìn)程很不明智。如果一個(gè)進(jìn)程屏蔽中斷后不再打開(kāi)中斷吭敢，整個(gè)系統(tǒng)可能會(huì)因此終止碰凶。
- 對(duì)多CPU不適用。屏蔽中斷僅僅對(duì)執(zhí)行了disable指令的那個(gè)CPU有效鹿驼，其他CPU仍能訪(fǎng)問(wèn)共享內(nèi)存欲低。
2.測(cè)試并加鎖指令 TSL
某些計(jì)算機(jī)中，特別是那些設(shè)計(jì)為多處理器的計(jì)算機(jī)畜晰，都有以免一條指令：TSL RX, LOCK砾莱，稱(chēng)為測(cè)試并加鎖(test and set lock)，它將一個(gè)內(nèi)存字lock讀到寄存器RX中凄鼻，然后再該內(nèi)存地址上存一個(gè)非零值腊瑟。讀字和寫(xiě)字操作保證是不可分割的，即該指令結(jié)束之前其他處理器均不允許訪(fǎng)問(wèn)該內(nèi)存字块蚌。執(zhí)行TSL指令的CPU將鎖住內(nèi)存總線(xiàn)闰非，以禁止其他CPU在本指令結(jié)束之前訪(fǎng)問(wèn)內(nèi)存。
為了使用TSL指令峭范，要使用一個(gè)共享變量lock來(lái)協(xié)調(diào)對(duì)共享內(nèi)存的訪(fǎng)問(wèn)财松。當(dāng)lock為0時(shí)，任何進(jìn)程都可以使用TSL指令將其設(shè)置為1纱控，并讀寫(xiě)共享內(nèi)存辆毡。當(dāng)操作結(jié)束是，進(jìn)程用一條普通的move指令將lock的值重新設(shè)置為0.
enter_region:
TSL REGISTER, LOCK | 復(fù)制鎖到寄存器并將鎖設(shè)為1
CMP REGISTER, #0 | 鎖是零嗎甜害？
JNE enter_region | 若不是零胚迫，說(shuō)明鎖已被設(shè)置，所以循環(huán)
RET |返回調(diào)用者唾那，進(jìn)入了臨界區(qū)
leave_region:
MOVE LOCK, #0 |在鎖中存入0
RET |返回調(diào)用者
可以看出TSL也是一個(gè)忙等待方案：進(jìn)程在進(jìn)入臨界區(qū)之前先調(diào)用enter_region访锻，在鎖空閑之前一直循環(huán)等待。
3.對(duì)換指令 XCHG
一個(gè)可替代TSL的指令是XCHG闹获，它原子性地交換了兩個(gè)位置的內(nèi)容期犬，例如，一個(gè)寄存器與一個(gè)存儲(chǔ)器字避诽。
enter_region:
MOVE REGISTER, #1
XCHG REGISTER, LOCK
CMP REGISTER, #0
JNE enter_region
RET
leave_region:
MOVE LOCK, #0
RET
TSL和XCHG指令的函數(shù)形式描述在《操作系統(tǒng)教程》第五版有寫(xiě)龟虎，此處不詳細(xì)描述。
4.嚴(yán)格輪詢(xún)法
//進(jìn)程0
while(True){
while(turn != 0); //循環(huán)
critical_region();
turn = 1;
noncritical_region();
}
//進(jìn)程1
while(True){
while(turn !=1); //循環(huán)
critical_region();
turn = 0;
noncritical_region();
}
整型變量turn沙庐，初始值為0鲤妥，用于記錄輪到哪個(gè)進(jìn)程進(jìn)入臨界區(qū)佳吞，并檢查或更新共享內(nèi)存。開(kāi)始時(shí)棉安，進(jìn)程0檢查turn底扳，發(fā)現(xiàn)其值為0，于是進(jìn)入臨界區(qū)贡耽。進(jìn)程也發(fā)現(xiàn)其值為0衷模，所以在一個(gè)等待循環(huán)中不但測(cè)試turn，看其值何時(shí)變?yōu)?.連續(xù)測(cè)試一個(gè)變量直到某個(gè)值出現(xiàn)為止蒲赂，稱(chēng)為忙等待阱冶。由于這種方式浪費(fèi)CPU時(shí)間，所以通常應(yīng)該避免滥嘴。只有在有理由認(rèn)為等待時(shí)間是非常短的情況下木蹬，才使用忙等待。用于忙等待的鎖若皱，稱(chēng)為自旋鎖
這個(gè)算法的確避免了所有的競(jìng)爭(zhēng)條件镊叁，但違反了臨界區(qū)條件3（臨界區(qū)外運(yùn)行得進(jìn)程不得阻塞其他進(jìn)程），所以不是一個(gè)很好的方案是尖。
5.Peterson解法
#define FALSE 0
#define TRUE 1
#define N 2 //進(jìn)程數(shù)量
int turn; //現(xiàn)在輪到誰(shuí)意系？
int interested[N]; //所有值初始化為0（FALSE）
void enter_region(int process)
{
int other; //另一個(gè)進(jìn)程號(hào)
other = 1-process;
interested[process] = TRUE; //表示想進(jìn)入臨界區(qū)
turn = process;
while(turn == process && interested[other] ==TRUE); //掛起進(jìn)程作用
}
void leave_region(int process)
{
interested[process] = FALSE; //表示離開(kāi)臨界區(qū)
}
在使用共享變量之前泥耀，各個(gè)進(jìn)程使用其進(jìn)程號(hào)0或1作為參數(shù)來(lái)調(diào)用enter_region饺汹。該調(diào)用在使用時(shí)將使進(jìn)程等待，直到能安全地進(jìn)入臨界區(qū)痰催。在完成對(duì)共享變量的操作之后兜辞，進(jìn)程將調(diào)用leave_region，表示操作已完成夸溶，若其他的進(jìn)程希望進(jìn)入臨界區(qū)逸吵，則現(xiàn)在就可以進(jìn)入。
一開(kāi)始缝裁，沒(méi)有任何進(jìn)程進(jìn)入臨界區(qū)中扫皱，現(xiàn)在進(jìn)程0調(diào)用enter_region。它通過(guò)設(shè)置其數(shù)組元素和將turn置0來(lái)標(biāo)識(shí)它希望進(jìn)入臨界區(qū)捷绑。由于進(jìn)程1并不想進(jìn)入臨界區(qū)韩脑，所以enter_region很快便返回。如果進(jìn)程1現(xiàn)在調(diào)用enter_region粹污，進(jìn)程1將在此處掛起直到interested[0]變成FALSE段多，該事件只有在進(jìn)程0調(diào)用leave_region退出臨界區(qū)時(shí)才會(huì)發(fā)生。
現(xiàn)在考慮兩個(gè)進(jìn)程幾乎同時(shí)調(diào)用enter_region情況壮吩。它們都將自己的進(jìn)程號(hào)存入turn进苍，但只有后被保存進(jìn)去的進(jìn)程號(hào)才有效加缘，前一個(gè)因被重寫(xiě)而丟失。假設(shè)進(jìn)程1是后存入的觉啊，則turn為1拣宏。當(dāng)兩個(gè)進(jìn)程都運(yùn)行到while語(yǔ)句時(shí)，進(jìn)程0將循環(huán)0次進(jìn)入臨界區(qū)柄延，則進(jìn)程1則將不斷地循環(huán)而不能進(jìn)入臨界區(qū)蚀浆，直到進(jìn)程0退出臨界區(qū)為止。
