【文章內(nèi)容簡介】 分析Linux進(jìn)程調(diào)度算法的調(diào)度效果。答：Linux在調(diào)度級別上考慮三種特征進(jìn)程：Realtime FIFO, Realtime Round Robin, Timesharing. 調(diào)度基于Goodness度量指標(biāo)，涉及如下一些參量：Priority: 1~40(缺省值20)，可通過nice系統(tǒng)調(diào)用調(diào)整，nice(value)中value的取值范圍為(20,20)之間，以與經(jīng)典UNIX保持兼容，但在內(nèi)部對value值進(jìn)行反向，取priority=20value。Quantum: 進(jìn)程尚可運行的剩余時間．對于運行進(jìn)程來說，每個時鐘間隔(10ms，稱為一個jiffy)，將quantum減1，當(dāng)所有就緒進(jìn)程的quantum配額下降到0時，重新計算所有進(jìn)程(包括等待進(jìn)程)的quantum值。Goodness值的計算方法如下：If(Realtime)Goodness=1000 + priority。If(Timesharing amp。amp。 quantum=0))Goodness=0。If(Timesharing amp。amp。 quantum0)Goodness=quantum + priority.調(diào)度發(fā)生在如下時刻：(1)運行進(jìn)程的quantum減至0；(2)運行進(jìn)程執(zhí)行系統(tǒng)調(diào)用exit；(3)運行進(jìn)程因等待I/O、信號燈而被封鎖；(4)原來具有高goodness的進(jìn)程被解除封鎖。容易看出調(diào)度效果：實時優(yōu)先于分時，交互和I/O進(jìn)程優(yōu)先于CPU進(jìn)程。四、 同步與互斥習(xí)題及解答:1． 何謂與時間有關(guān)的錯誤? 舉例說明之。 答：并發(fā)進(jìn)程的執(zhí)行實際上是進(jìn)程活動的某種交叉，某些交叉次序可能得到錯誤結(jié)果。由于具體交叉的形成與進(jìn)程的推進(jìn)速度有關(guān)，而速度是時間的函數(shù)，因而將這種錯誤稱為與時間有關(guān)的錯誤。例如，兩個并發(fā)進(jìn)程的程序如下：int n=0。main( ){創(chuàng)建進(jìn)程A；創(chuàng)建進(jìn)程B；}；A( ){while(1){n++。}}。B( ){while(1){睡眠一段時間；printf(“%d”,n)。n=0。 }}。假設(shè)進(jìn)程A被部署在公園入口的終端上，用來記錄一段時間內(nèi)進(jìn)入公園的人數(shù)，進(jìn)程B被部署在公園的控制中心，用來輸出一段時間內(nèi)進(jìn)入公園的總?cè)藬?shù)。進(jìn)程A和進(jìn)程B共享全局變量n，n表示記錄下的人數(shù)。如果在進(jìn)程B執(zhí)行完打印語句后被進(jìn)程A打斷，進(jìn)程A執(zhí)行了若干次變量自增語句，之后進(jìn)程B接著執(zhí)行清0語句，那么進(jìn)程A對n的累加丟失了，相當(dāng)于進(jìn)程B被打斷的這段時間內(nèi)進(jìn)入公園的人沒有被記錄下來。發(fā)生與時間有關(guān)的錯誤。2． 有人說，假設(shè)兩個進(jìn)程之間沒有共享內(nèi)存，則二者之間沒有公共變量，這種說法準(zhǔn)確嗎? 說明原因。 答：如果只從用戶空間考慮，這種說法是正確的。但從操作系統(tǒng)的角度來說并不準(zhǔn)確。兩個沒有公共內(nèi)存的用戶進(jìn)程可能同時（宏觀）進(jìn)入操作系統(tǒng)，并訪問操作系統(tǒng)空間中的公共變量。3．何謂忙式等待? 是否還有其它方式的等待? 比較它們之間的聯(lián)系和差別。 答：不進(jìn)入等待狀態(tài)的等待稱為忙式等待。另一種等待方式是阻塞式等待，進(jìn)程得不到共享資源時將進(jìn)入阻塞狀態(tài)，讓出CPU給其他進(jìn)程使用。忙等待和阻塞式等待的相同之處在于進(jìn)程都不具備繼續(xù)向前推進(jìn)的條件，不同之處在于處于忙等待的進(jìn)程不主動放棄CPU，盡管CPU可能被剝奪，因而是低效的；而處于阻塞狀態(tài)的進(jìn)程主動放棄CPU，因而是高效的。4．下列進(jìn)程互斥方法哪些存在忙式等待問題? （1）軟件: 面包店算法(2) 硬件: TS指令(3) 關(guān)中斷指令答：（1）、（2）存在忙等待問題。5．為何開關(guān)中斷進(jìn)程互斥方法僅在單CPU系統(tǒng)中是有效的？ 答：關(guān)中斷方法不適用于多CPU系統(tǒng)，因為關(guān)中斷只能保證CPU不由一個進(jìn)程切換到另外一個進(jìn)程，從而防止多個進(jìn)程并發(fā)地進(jìn)入公共臨界區(qū)域。但即使關(guān)中斷后，不同進(jìn)程仍可以在不同CPU上并行執(zhí)行關(guān)于同一組共享變量的臨界區(qū)代碼.6．在多處理機(jī)系統(tǒng)中，軟件互斥方法是否有效？為什么？ 　　答：依然有效。多處理機(jī)并行與單處理并發(fā)之間的差別在于程序交叉的粒度，單處理機(jī)機(jī)環(huán)境中進(jìn)程交叉發(fā)生在指令之間，多處理機(jī)環(huán)境中進(jìn)程交叉發(fā)生在指令周期之間。由于純軟件互斥算法并不依賴特殊的硬件指令(如test_and_set)，指令之間的交叉與指令周期之間的交叉結(jié)果相同。7．試分析臨界區(qū)域的大小與系統(tǒng)并發(fā)性之間的關(guān)系。 答：關(guān)于同一組變量的臨界區(qū)域是不能并發(fā)執(zhí)行的代碼，臨界區(qū)越大，并發(fā)性越差，因而編寫并發(fā)程序應(yīng)盡量縮小臨界區(qū)域范圍。8．設(shè)CR1是關(guān)于一組共享變量SV1的臨界區(qū)域，CR2是關(guān)于另外一組共享變量SV2的臨界區(qū)域，當(dāng)進(jìn)程P1進(jìn)入CR1時，進(jìn)程P2是否可以進(jìn)入CR2? 為什么? 答：可以。因為互斥是在變量級別上的，多個進(jìn)程同時進(jìn)入關(guān)于不同變量的臨界區(qū)不會引起與時間有關(guān)的錯誤。9．Lamport面包店互斥算法是否會出現(xiàn)餓死情況? 　　不會，該算法是公平的。假定系統(tǒng)中共有n個進(jìn)程，每個想要進(jìn)入臨界區(qū)域的進(jìn)程(線程)在最壞的情況下需要等待其它n1個進(jìn)程進(jìn)入并離開臨界區(qū)域之后即可獲得進(jìn)入臨界區(qū)域的機(jī)會，因而存在(忙式)等待的上界。10．試用信號燈和PV操作實現(xiàn)臨界區(qū)語句: region 共享變量 do 語句變量類型共享變量答：semaphore s=1。P(s)。語句V(s)。11. 由V操作喚醒的進(jìn)程是否一定能夠直接進(jìn)入運行狀態(tài)? 舉例說明之。答：否。一般來說，喚醒是將進(jìn)程狀態(tài)由等待狀態(tài)變成就緒狀態(tài)，而就緒進(jìn)程何時獲得處理機(jī)則是由系統(tǒng)的處理機(jī)調(diào)度策略確定的。如果采用搶占式優(yōu)先級調(diào)度算法，并且被喚醒的進(jìn)程是當(dāng)前系統(tǒng)中優(yōu)先級最高的進(jìn)程，那么該進(jìn)程將被調(diào)度執(zhí)行，其狀態(tài)變成運行態(tài)。如果該進(jìn)程不是系統(tǒng)中優(yōu)先級最高的進(jìn)程或系統(tǒng)采用其它調(diào)度算法，那么該進(jìn)程不會被調(diào)度執(zhí)行，其狀態(tài)將維持在就緒態(tài)。12. 設(shè)S1和S2為兩個信號燈變量，下列八組P、V操作哪些可以同時進(jìn)行? 哪些不能同時進(jìn)行? 為什么?(1)P(S1)，P(S2) (2)P(S1)，V(S2)(3)V(S1)，P(S2) (4)V(S1)，V(S2)(5)P(S1)，P(S1) (6)P(S2)，V(S2)(7)V(S1)，P(S1) (8)V(S2)，V(S2)答：能同時進(jìn)行的包括：(1)、(2)、(3)、(4)。這些操作涉及不同信號燈變量，屬于關(guān)于不同組共享變量的臨界區(qū)。不能同時進(jìn)行的包括：(5)、(6)、(7)、(8)。這些操作涉及相同的信號燈變量，屬于關(guān)于同一組共享變量的臨界區(qū)。13. 對于生產(chǎn)者—消費者問題，假設(shè)緩沖區(qū)是無界的，試用信號燈與PV操作給出解法。答：由于是無界緩沖區(qū)，所以生產(chǎn)者不會因得不到緩沖區(qū)而被阻塞，不需要對空緩沖區(qū)進(jìn)行管理，可以去掉在有界緩沖區(qū)中用來管理空緩沖區(qū)的信號量及其PV操作。semaphore mutex_in=1。semaphore mutex_out=1。semaphore empty=0。int in=0，out=0。生產(chǎn)者活動：while(1){produce next product。P(mutex_in)。add the product to buffer[in]。in++。v(mutex_in)。V(empty)。} 消費者活動：while(1){P(empty)。P(mutex_out)。take the product from buffer[out]。out++。V(mutex_out)。}14. 設(shè)有一個可以裝A、B兩種物品的倉庫，其容量無限大，但要求倉庫中A、B兩種物品的數(shù)量滿足下述不等式:M≤A物品數(shù)量－B物品數(shù)量≤N其中M和N為正整數(shù)。 試用信號燈和PV操作描述A、B兩種物品的入庫過程。答：已知條件 M≤A物品數(shù)量－B物品數(shù)量≤N 可以拆成兩個不等式，即A物品數(shù)量－B物品數(shù)量≤N，B物品數(shù)量－A物品數(shù)量≤M。這兩個不等式的含義是：倉庫中A物品可以比B物品多，但不能超過N個；Ｂ物品可以比A物品多，但不能超過M個。semaphore a=n。semaphore b=m。void main(){createprocess(A,…)。createprocess(B,…)。}A物品入庫：void A(){while(1){P(a)。A物品入庫。V(b)。}}B物品入庫：void B(){while(1){P(b)。B物品入庫。V(a)。}}15. 試用信號燈與PV操作實現(xiàn)司機(jī)與售票員之間的同步問題。設(shè)公共汽車上有一個司機(jī)和一個售票員，其活動如下圖所示。 為了安全起見，顯然要求: (1)關(guān)車門后方能啟動車輛；(2)到站停車后方能開車門。亦即“啟動車輛”這一活動應(yīng)當(dāng)在“關(guān)車門”這一活動之后，“開車門”這一活動應(yīng)當(dāng)在“到站停車”這一活動之后。解：如果進(jìn)程P2尚未推進(jìn)到②處時，進(jìn)程P1已經(jīng)推進(jìn)到①處，則P1應(yīng)等待直到P2推進(jìn)到②處為止；同樣，如果進(jìn)程P1尚未推進(jìn)到③處時，進(jìn)程P2已經(jīng)推進(jìn)到④處，則P2應(yīng)等待直到P1推進(jìn)到③處為止。如果進(jìn)程P1在①處發(fā)生了等待，則當(dāng)進(jìn)程P2執(zhí)行到②處時應(yīng)將P1喚醒；同樣，如果進(jìn)程P2在④處發(fā)生了等待，則當(dāng)進(jìn)程P2執(zhí)行到③處時應(yīng)將P1喚醒。用信號量和P、V操作解決這一問題，需要定義兩個信號量，一個信號量start表示是否允許司機(jī)啟動車輛，另一個信號量open表示是否允許售票員開車門。初始狀態(tài)是車停在始發(fā)站，車門開著，等待乘客上車。因此，兩個信號量的初值都是0。semaphore start=0。semaphore open=0。司機(jī)的活動:P1: do{P(start)。 啟動車輛。正常行車。到站停車。V(open)。}while (1)。售票員的活動:P2: do{關(guān)車門。V(start)。 售票。P(open)。開車門。}while (1)。16. 設(shè)有A、B、C三組進(jìn)程，它們互斥地使用某一獨占型資源R，使用前申請，使用后釋放。資源分配原則如下:(1) 當(dāng)只有一組申請進(jìn)程時，該組申請進(jìn)程依次獲得R；(2) 當(dāng)有兩組申請進(jìn)程時，各組申請進(jìn)程交替獲得R，組內(nèi)申請進(jìn)程依次獲得R；(3) 當(dāng)有三組申請進(jìn)程時，各組申請進(jìn)程輪流獲得R，組內(nèi)申請進(jìn)程依次獲得R。試用信號燈和PV操作分別給出各組進(jìn)程的申請活動程序段和釋放活動程序段。解：int free=1。//設(shè)備狀態(tài)標(biāo)志semaphore mutex=1。semaphore qa=qb=qc=0。 //各組等待隊列int counta=countb=countc=0。//等待隊列長度A組申請：P(mutex)。if(free==1){free=0。V(mutex)。}else{counta++。V(mutex)。P(qa)。}A組釋放：P(mutex)。if(countb0){countb。V(qb)。}else{if(countc0){countc。V(qc)。}else{if(counta0){countaV(qa)。}else{ free=1。}}}}A組進(jìn)程活動可以給出B組和C組進(jìn)程活動。17. 設(shè)自行車生產(chǎn)線上有一只箱子，其中有N個位置(N≥3)，每個位置可存放一個車架或一個車輪。 又設(shè)有三個工人，其活動分別為:工人1活動：do {加工一個車架。車架放入箱中。}while(1)工人2活動：do {加工一個車輪。車輪放入箱中。}while(1)工人3活動：do {箱中取一車架。箱中取二車輪。組裝為一臺車。}while(1)試分別用信號燈與PV操作、管程、會合實現(xiàn)三個工人的合作，要求解中不含死鎖。解：用信號燈與PV操作實現(xiàn)三個工人的合作，管程與會合解法可仿照給出。首先不考慮死鎖問題，工人1與工人工人2與工人3構(gòu)成生產(chǎn)者與消費者關(guān)系，這兩對生產(chǎn)/消費關(guān)系通過共同的緩沖區(qū)相聯(lián)系。從資源的角度來看，箱子中的空位置相當(dāng)于工人1和工人2的資源，而車架和車輪相當(dāng)于工人3的資源。定義三個信號燈如下：semaphore empty=N。//空位置semaphore wheel=0。//車輪semaphore frame=0。//車架三位工人的活動分別為：工人1活動：do {加工一個車架。P(empty)。車架放入箱中。V(frame)。}while(1)工人2活動：do {加工一個車輪。P(empty)。車輪放入箱中。V(wheel)。}while(1)工人3活動：do {P(frame)。箱中取一車架。V(empty)。P(wheel)。P(wheel)。箱中取二車輪。V(empty)。V(empty)。組裝為一臺車。}while(1)分析上述解法易見，當(dāng)工人1推進(jìn)速度較快時，箱中空位置可能完全被車架占滿或只留有一個存放車輪的位置，而當(dāng)此時工人3同時取2個車輪時將無法得到，而工人2又無法將新加工的車輪放入箱中；當(dāng)工人2推進(jìn)速度較快時，箱中空位置可能完全被車輪占滿，而當(dāng)此時工人3取車架時將無法得到，而工人1又無法將新加工的車架放入箱中。上述兩種情況都意味著死鎖。為防止死鎖的發(fā)生，箱中車架的數(shù)量不可超過N2，車輪的數(shù)量不可超過N1，這些限制可以用兩個信號燈來表達(dá)。semaphore s1=N2。semaphore s2=N1。如此，可以給出不含死鎖的完整解法如下：工人1活動：do {加工一個車架。P(s1)。P(empty)。車架放入箱中。V(frame)。}while(1)工人2活動：