【正文】 圖bcs1s2s3圖c三種復(fù)制方法一次如上圖所示：1）顯示復(fù)制，如圖a所示，是為編程人員控制整個(gè)進(jìn)程所用，當(dāng)進(jìn)程產(chǎn)生一個(gè)文件時(shí)，可以在其他服務(wù)器上生產(chǎn)另外的拷貝，如果目錄服務(wù)允許一個(gè)文件有多個(gè)拷貝，所有拷貝的網(wǎng)絡(luò)地址都可以和這個(gè)文件名聯(lián)系起來(lái)。2）懶惰拷貝，如圖b所示，只要在某個(gè)服務(wù)器上建立每個(gè)文件的一個(gè)拷貝服務(wù)器自己在其他的服務(wù)器上也可以自動(dòng)生成副本。3）用組復(fù)制文件，如圖c所示，所有的寫(xiě)系統(tǒng)調(diào)用同時(shí)傳送到所有的服務(wù)器，于是，其他的拷貝在源文件產(chǎn)生時(shí)就產(chǎn)生了。：主拷貝算法、Gifford算法。答：主拷貝算法，使用時(shí)，指定一個(gè)服務(wù)器為主服務(wù)器，其他所有服務(wù)器為從服務(wù)器，當(dāng)要更新一個(gè)復(fù)制文件時(shí)，我們就將該改變發(fā)送至主服務(wù)器上，在本地完成修改，然后向各從服務(wù)器發(fā)出命令，命令他們也完成修改。這樣可以在任何一個(gè)（主或者從）服務(wù)器上進(jìn)行讀操作。這種方法簡(jiǎn)單，但是有個(gè)問(wèn)題，當(dāng)主服務(wù)器停機(jī)時(shí)，所有的更細(xì)將不能進(jìn)行。Gifford算法，基本思想是在讀寫(xiě)一個(gè)復(fù)制文件之前要求先申請(qǐng)并獲得多個(gè)服務(wù)器的允許。例如，讀一個(gè)已經(jīng)有N個(gè)副本的復(fù)制文件，客戶(hù)需要獲得一個(gè)讀法定數(shù)，它是任何Nr個(gè)或更多個(gè)服務(wù)器的任一集合，同樣的，修改一個(gè)文件需要一個(gè)至少Nw個(gè)服務(wù)器的寫(xiě)法定數(shù)。Nr和Nw的值必修滿(mǎn)足約束條件Nr+NwN，只有在適當(dāng)數(shù)目的服務(wù)器同意參與時(shí)，文件才能進(jìn)行讀寫(xiě)操作。 once協(xié)議。答：通寫(xiě)緩存一致性協(xié)議是一種特別簡(jiǎn)單的，通用的協(xié)議。當(dāng)CPU從存儲(chǔ)器中首次讀取某個(gè)字時(shí)，該字通過(guò)總線取出并存儲(chǔ)在提出請(qǐng)求的CPU緩存中，當(dāng)再次需要這個(gè)字時(shí)，CPU不再提出訪問(wèn)存儲(chǔ)器的請(qǐng)求，而是直接從緩存中獲取，這樣減少了總線流量，通寫(xiě)緩存一致性協(xié)議概括如下：事件緩存響應(yīng)本地CPU操作時(shí)執(zhí)行緩存響應(yīng)遠(yuǎn)程CPU操作時(shí)執(zhí)行的動(dòng)作讀失敗Read miss從存儲(chǔ)器中取得數(shù)據(jù)并存儲(chǔ)到緩存中無(wú)動(dòng)作讀命中Read hit從本地緩存中取得數(shù)據(jù)無(wú)動(dòng)作寫(xiě)失敗 Write miss更新存儲(chǔ)器中的數(shù)據(jù)并存儲(chǔ)到緩存中無(wú)動(dòng)作寫(xiě)命中 Write hit更新存儲(chǔ)器和緩存使緩存無(wú)效表中的第一列列出了可能發(fā)生的四種基本事件，第二列說(shuō)明緩存如何響應(yīng)CPU的操作，第三列說(shuō)明緩存發(fā)現(xiàn)（通過(guò)監(jiān)聽(tīng)）其他CPU的讀寫(xiě)操作如何反應(yīng)。例如，當(dāng)監(jiān)聽(tīng)者發(fā)現(xiàn)其他CPU寫(xiě)入的字在其緩存中（從監(jiān)聽(tīng)者角度看是命中）時(shí)，監(jiān)聽(tīng)者必須采取措施，即從本緩存中刪除這個(gè)字。通寫(xiě)協(xié)議易于理解和使用。缺點(diǎn)是所有的讀寫(xiě)操作必須通過(guò)縱向，因此允許掛在單一總線上的CPU數(shù)量仍然很少，不能滿(mǎn)足大型多處理機(jī)的需求。writeonce協(xié)議：該協(xié)議管理緩存塊，每個(gè)塊處于一下三種狀態(tài)之一：1）無(wú)效，本緩存塊沒(méi)有有效數(shù)據(jù)；2）干凈，存儲(chǔ)器被更新，該塊可能在別的緩存中；3）臟，存儲(chǔ)器錯(cuò)誤，該數(shù)據(jù)塊不在其他緩存中?；舅枷胧窃试S正被多個(gè)CPU讀取的字出現(xiàn)在它們所有的緩存中，而僅被一個(gè)CPU經(jīng)常寫(xiě)的字只保存在他的緩存中，為減少總線流量，不必每次都寫(xiě)回存儲(chǔ)器。；在如下并行執(zhí)行的進(jìn)程P1和P2，列出順序一致性所允許的6種語(yǔ)句交叉執(zhí)行情況。a=1。 b=1。if (b= =0) kill (P2) if(a= =0) kill (P1)(a) P1 (b) P2答：順序一致性模型由下述條件定義：1）如果所有進(jìn)程以一定順序執(zhí)行操作，每一進(jìn)程的操作都以程序規(guī)定的順序出現(xiàn)，則任何操作的結(jié)果都是一樣的；2）要求分布式系統(tǒng)中的所有成員和它們的進(jìn)程共享一個(gè)通用視圖，此視圖記錄了對(duì)于共享能存訪問(wèn)操作的順序。順序一致性所允許的6種語(yǔ)句交叉執(zhí)行情況：a = 1。b = 1。if(b == 0) kill(P2)if(a == 0) kill(P1)b = 1。a = 1。if(b == 0) kill(P2)if(a == 0) kill(P1)a = 1。b = 1。if(a == 0) kill(P1)if(b == 0) kill(P2)b = 1。a = 1。if(a == 0) kill(P1)if(b == 0) kill(P2)a = 1。if(b == 0) kill(P2)b = 1。if(a == 0) kill(P1)b = 1。if(a == 0) kill(P1)a = 1。if(b == 0) kill(P2)。假設(shè)兩個(gè)變量a和b,恰好位于基于分頁(yè)的DSM系統(tǒng)的同一頁(yè)上。然而，它們都不是共享變量。是否會(huì)發(fā)生錯(cuò)誤共享？說(shuō)明理由。答：錯(cuò)誤共享是指無(wú)關(guān)的變量出現(xiàn)在同一頁(yè)上，當(dāng)一進(jìn)程使用它們之一時(shí)，進(jìn)程也得到了其他變量。有效頁(yè)越大，發(fā)生錯(cuò)誤共享的可能性越大。假設(shè)有一頁(yè)包含了兩個(gè)無(wú)關(guān)的共享變量A和B，如下圖所示，進(jìn)程1經(jīng)常對(duì)A執(zhí)行讀寫(xiě)操作，進(jìn)程2經(jīng)常使用B，這時(shí)包含兩個(gè)變量的頁(yè)將經(jīng)常在兩個(gè)進(jìn)程之間傳送。“錯(cuò)誤共享”問(wèn)題是由于有效頁(yè)太大產(chǎn)生的，有效頁(yè)越大，發(fā)生錯(cuò)誤共享的可能性越大，共享頁(yè)越小，發(fā)生錯(cuò)誤共享的可能性越小。圖中所示的情況會(huì)發(fā)生錯(cuò)誤共享，因?yàn)閮蓚€(gè)變量A和B恰好位于基于分頁(yè)的DSM系統(tǒng)的同一頁(yè)上，即使不是共享變量，由于他們出現(xiàn)在同一頁(yè)上，當(dāng)一進(jìn)程使用它們之一時(shí)，進(jìn)程也得到了另一個(gè)變量，因此發(fā)生錯(cuò)誤共享。包含兩個(gè)無(wú)關(guān)變量的錯(cuò)誤共享處理器1使用A的代碼處理器2AB共享頁(yè)使用B的代碼AB兩個(gè)無(wú)關(guān)的共享變量。答：在這個(gè)協(xié)議中，任意時(shí)間每一頁(yè)或者在R狀態(tài)（可讀），或者在W狀態(tài)（可讀可寫(xiě)），在執(zhí)行程序時(shí)，頁(yè)的狀態(tài)可以改變，當(dāng)頁(yè)處于W狀態(tài)時(shí)，只有一個(gè)拷貝，當(dāng)頁(yè)處于R狀態(tài)時(shí)，擁有者有一個(gè)拷貝，其他進(jìn)程可能有其拷貝。每一頁(yè)有一個(gè)擁有者，即最近在該頁(yè)上寫(xiě)入的進(jìn)程。圖（a）給出了處理機(jī)1上的進(jìn)程P要讀一頁(yè)的六種情況。在前四種情況中，P僅做讀操作，頁(yè)被映射到他們的地址空間，所以讀操作由硬件完成，不會(huì)激活陷阱程序。第五六種情況，發(fā)生缺頁(yè)錯(cuò)誤，DSM的軟件獲得控制權(quán)，發(fā)送消息給擁有者以獲得一份拷貝。當(dāng)拷貝傳到時(shí)，頁(yè)被映射，出錯(cuò)的指令繼續(xù)執(zhí)行，如果擁有者處于W狀態(tài)，必須將之降級(jí)為R狀態(tài)。圖（b）給出了處理機(jī)1上的進(jìn)程P要寫(xiě)一頁(yè)的六種情況，第一種情況，因?yàn)轫?yè)映射為只讀模式嗎，所以寫(xiě)操作只是發(fā)生了，而不激活陷阱程序；第二種情況，也被改為W狀態(tài)，并寫(xiě)入；第三種情況，該頁(yè)有其他拷貝，所以在寫(xiě)以前，必須先置無(wú)效這些拷貝。在后三種情況中，當(dāng)P要執(zhí)行寫(xiě)操作時(shí)，其他進(jìn)程是擁有者，P必須要求現(xiàn)在的擁有者將其置無(wú)效，將擁有權(quán)傳給P，除非P已經(jīng)有了一個(gè)拷貝，將該頁(yè)的一個(gè)拷貝也傳給P。只有這樣寫(xiě)操作才能開(kāi)始。在這三例中，P最后擁有該頁(yè)的唯一拷貝，其狀態(tài)為W。在所有的六例中，在寫(xiě)操作執(zhí)行以前，協(xié)議保證要寫(xiě)得進(jìn)程的地址空間中只有頁(yè)的一個(gè)拷貝存在，這樣可以保證一致性。，復(fù)制頁(yè)更新時(shí)需要通過(guò)置無(wú)效協(xié)議以實(shí)現(xiàn)一致性，試給出一種尋找復(fù)制頁(yè)拷貝的方法。答：廣播的方式，要求擁有者對(duì)申請(qǐng)消息進(jìn)行響應(yīng)，從而確定所需拷貝頁(yè)的擁有者。使用擁有者定位協(xié)議，在系統(tǒng)中指定一個(gè)進(jìn)程為頁(yè)管理者，來(lái)跟蹤哪個(gè)進(jìn)程有哪些頁(yè)，在具體實(shí)現(xiàn)時(shí)有四消息和三消息兩種方法。四消息方法，申請(qǐng)者向頁(yè)管理者提交請(qǐng)求，頁(yè)管理者返回消息指出擁有者是誰(shuí)。申請(qǐng)者在向擁有者發(fā)送請(qǐng)求，擁有者返回所需的頁(yè)的拷貝或者擁有權(quán)。同時(shí)也管理者根據(jù)新的信息將相應(yīng)的進(jìn)程中的頁(yè)置為無(wú)效頁(yè)。三消息方法，申請(qǐng)者向頁(yè)管理者提交申請(qǐng)后，頁(yè)管理者將請(qǐng)求消息轉(zhuǎn)發(fā)給響應(yīng)的擁有者，由擁有者對(duì)申請(qǐng)者直接給出所需頁(yè)的拷貝或者擁有權(quán)。消息傳送完成后，頁(yè)管理者對(duì)頁(yè)的擁有者做出改變，同時(shí)設(shè)置無(wú)效頁(yè)。13