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