【文章內(nèi)容簡介】 。所以，永遠(yuǎn)都不會存在一個可運行的、具有更高優(yōu)先級的線程。參考：[LEVI96]第5章 并發(fā)性：互斥和同步答：，將字符賦給一個只有一個字大小的緩沖區(qū)rs然后在賦給squash協(xié)同程。協(xié)同程序Read在每副卡片圖像的后面插入一個額外的空白。協(xié)同程序squash不需要知道任何關(guān)于輸入的八十個字符的結(jié)構(gòu)，它簡單的查找成對出現(xiàn)的星號，然后將更改夠的字符串經(jīng)由只有一個字符大小的緩沖sp，傳遞給協(xié)同程序print。最后協(xié)同程序print簡單的接受到來的字符串，并將他們打印在包含125個字符的行中。．考慮一個并發(fā)程序，它有兩個進(jìn)程p和q，定義如下。假設(shè)住程序執(zhí)行兩個進(jìn)程的parbegin Void p() void q() { A。 { D。 B。 E。 C。 } }答：ABCDE。ABDCE。ABDEC。ADBCE。ADBEC。ADEBC。DEABC。DAEBC。DABEC。DABCE。 const int n=50。 int tally。void total(){ int count。 for(count =1。count =n。count ++) {tally++。 }}void main(){ tally =0。parbegin(total(),total()。write(tally)。 }答：,tally值的范圍好像是落在[50,100]這個區(qū)間里,增加,存儲的情況,同時變更這個共享變量的取值: ,tally值加到1,在此時失去處理器(它已經(jīng)增加寄存器的值到1,但是還沒有存儲這個值). (仍然是0),然后運行完成49次增加操作,在它已經(jīng)將49這個值存儲給共享變量tally后,失去處理器控制權(quán). (用1去代替先前的49這個tally值),此時被迫立即放棄處理器. ,將1(當(dāng)前的tally值)載入到它自己的寄存器中,但此時被迫放棄處理器(注意這是B的最后一次載入). ,但這次沒有被中斷,直到運行完成它剩余的49次載入,增加和存儲操作,結(jié)果是此時tally值已經(jīng)是50. ,同時存儲這個值做為這個共享變量的最終結(jié)果. 一些認(rèn)為會出現(xiàn)低于2這個值的結(jié)果,[2,100]. ,tally值的最終范圍是[2,N*50],因為對其他所有進(jìn)程來說,.（根據(jù)處理器的使用時間）？請解釋。答：就一般情況來說是對的,有一種特殊情況,當(dāng)進(jìn)程執(zhí)行到程序的某一點處,在此處要等待直到條件滿足,而正好條件已滿足,此時忙等待會立即有結(jié)果,然而阻塞等待會消耗操作系統(tǒng)資源在換出與換入進(jìn)程上. boolean blocked[2]。 int rurn。 void P(int id) { While (true) { While(turn!=id)。 { While(blocked[1!id] /*do nothing*/。 Turn =id。 } } Void main () { Blocked[0]=false。 Blocked[1]=false。 Turn=0。 Parbegin(P(0),P(1))。 }這是【HYMA66】中提出的解決互斥問題的一種方法。請舉出證明該方法不正確的一個反例。答：考慮這種情況:此時turn=0,進(jìn)程P(1)使布爾變量blocked[1]的值為true,在這時發(fā)現(xiàn)布爾變量blocked[0]的值為false,然后P(0)會將true值賦予blocked[0],此時turn=0,P(0)進(jìn)入臨界區(qū),P(1)在將1賦值給turn后,也進(jìn)入了臨界區(qū).（bakery）算法，之所以起這個名字，是因為它的思想來自于面包店或其他商店中，每個顧客在到達(dá)時都得到一個有編號的票，并按票號依次得到服務(wù)，算法如下： Boolean choosing[n]。 Int number[n]。 While (true) { Choosing[i]=true。 Number[i]=1+getmax(number[],n)； Choosing[i]=false。 For(int j=0。jn。j++) { While (choosing[j]) {} While ((number[j]!=0)amp。amp。(number[j],j)(number[i],i) {} } /*critical section*/ Number[i]=0。 /*remainder*/。 }數(shù)組choosing和number分別被初始化成false和0，每個數(shù)組的第i個元素可以由進(jìn)程i讀或?qū)?，但其他進(jìn)程只能讀。符號（a，b）（c，d）被定義成 （a，c）或（a=c且bd）A． 用文字描述這個算法。B． 說明這個算法避免了死鎖。C． 說明它實施了互斥。答：,重新設(shè)置它的票號為0. ,那么總會有一個唯一的,死鎖可以避免. ,我們首先需要證明下面的定理:如果Pi在它的臨界區(qū),Pk已經(jīng)計算出來它的number[k],并試圖進(jìn)入臨界區(qū),此時就有下面的關(guān)系式: ( number[i], i ) ( number[k], k ).為證明定理,定義下面一些時間量: Tw1:Pi最后一次讀choosing[k], 當(dāng) j=k,在它的第一次等待時,因此我們在Tw1處有choosing[k] = false. Tw2:Pi開始它的最后執(zhí)行, 當(dāng)j=k,在它的第二次while循環(huán)時,因此我們有Tw1 Tw2. Tk1:Pk在開始repeat循環(huán)時。Tk2:Pk完成number[k]的計算。Tk3: Pk設(shè)置choosing[k]Tk2Tk3.因為在Tw1處,choosing[k]=false,我們要么有Tw1Tk1,要么有Tk3,我們有number[i]number[k],因為Pi在Pk之前被分配號碼。,我們有Tk2 Tk3 Tw1 Tw2,因此有Tk2,Pi已經(jīng)讀了當(dāng)前number[k],因為Tw2是當(dāng)j=k第二次while循環(huán)執(zhí)行發(fā)生的時刻,我們有(number[i], i ) ( number[k], k),因為它會發(fā)現(xiàn)number[i]不等于0,并且( number[i], i ) ( number[k], k ).，對進(jìn)程在允許訪問臨界區(qū)之前必須等待多久沒有控制。設(shè)計一個使用testset指令的算法，且保證任何一個等待進(jìn)入臨界區(qū)的進(jìn)程在n1個turn內(nèi)進(jìn)入，n是要求訪問臨界區(qū)的進(jìn)程數(shù)，turn是指一個進(jìn)程離開臨界區(qū)而另一個進(jìn)程獲準(zhǔn)訪問這個一個事件。答：以下的程序由[SILB98]提供：var j: 0..n1。key: boolean。repeatwaiting[i] := true。key := true。while waiting[i] and key do key := testset(lock)。waiting[i] := false。 critical section j := i + 1 mod n。while (j ≠ i) and (not waiting[j]) do j := j + 1 mod n。if j = i then lock := falseelse waiting := false。 remainder section Until這個算法用最普通的數(shù)據(jù)結(jié)構(gòu)：var waiting: array [0..n – 1] of boolean Lock：boolean這些數(shù)據(jù)結(jié)構(gòu)被初始化成假的，當(dāng)一個進(jìn)程離開它的臨界區(qū)，它就搜索waiting的循環(huán)隊列： Void semWait(s) { If (0) { 。 } Else { Place this process in 。 Block。 } } Void semSignal(s) { If (there is at liast one process blocked on semaphore) { Remove a process P from 。 Place process P on ready list。 } Else ++。 }，注意有這樣的一個區(qū)別：在前面的定義中，信號量永遠(yuǎn)不會取負(fù)值。當(dāng)在程序中分別使用這兩種定義時，其效果有什么不同？也就是說，是否可以在不改變程序意義的前提下，用一個定義代替另一個？答：這兩個定義是等價的，當(dāng)信號量的值為負(fù)值時，它的值代表了有多少個進(jìn)程在等待；在此題中的定義中，雖然你沒有關(guān)于這方面的信息，但是這兩個版本的函數(shù)是一樣的。 。我們使用semWaitB操作和semSignalB操作以及兩個二元信號量delay和mutex?？紤]下面的代碼 Void semWait(semaphor s) { semWaitB(mutex)。 s。 if (s0) { semSignalB(mutex)。 semWaitB(delay)。 } Else Semsignalb(mutex) } Void semSignal(semaphore s)。 { semWaitB(mutex)。 s++。 if(s=0) semSignalB(delay)。 semSignalB(mut