操作系統(tǒng)精髓與設(shè)計(jì)原理-第15章 分布式進(jìn)程管理

1、第15章分布式進(jìn)程管理復(fù)習(xí)題：15.1、討論實(shí)現(xiàn)進(jìn)程遷移的原因。答：負(fù)載共享：通過(guò)將進(jìn)程從負(fù)載較重的系統(tǒng)遷移到負(fù)載較輕的系統(tǒng)，負(fù)載就會(huì)得 到平衡，從而提高整體性能。通信性能：可以將交互密集的多個(gè)進(jìn)程移動(dòng)到同 一節(jié)點(diǎn)上，以減少因?yàn)樗鼈冎g的交互而帶來(lái)的通信開(kāi)銷。同樣，當(dāng)一個(gè)進(jìn)程 在某些文件或某組文件上執(zhí)行數(shù)據(jù)分析，且文件的大小比進(jìn)程要大很多時(shí)，將 該進(jìn)程移動(dòng)到數(shù)據(jù)端也許是更有利的。可用性：需要長(zhǎng)時(shí)間運(yùn)行的進(jìn)程，在得 到錯(cuò)誤的預(yù)先通知時(shí)，或者在預(yù)定的關(guān)機(jī)時(shí)間之前，為了能夠存活下來(lái)，可能 需要遷移到其他機(jī)器中。如果操作系統(tǒng)提供了這樣的通知，則那些需要繼續(xù)運(yùn) 行的進(jìn)程可以遷移到另一個(gè)系統(tǒng)上，或者保證在

2、稍后的某個(gè)時(shí)間在當(dāng)前系統(tǒng)上 能重新啟動(dòng)。特殊功能的使用：進(jìn)程的遷移可以充分利用特定節(jié)點(diǎn)上獨(dú)特的硬 件或軟件功能。15.2、在進(jìn)程遷移過(guò)程中，進(jìn)程地址空間是如何處理的？答：下列策略可能被采用：Eager（all）：在遷移時(shí)轉(zhuǎn)移整個(gè)地址空間。預(yù)先復(fù)制 （precopy）：進(jìn)程繼續(xù)在源節(jié)點(diǎn)上執(zhí)行，而地址空間已經(jīng)復(fù)制到了目標(biāo)節(jié)點(diǎn)上。在預(yù)先復(fù)制的過(guò)程中，源節(jié)點(diǎn)上的某些頁(yè)有可能又被修改，這些頁(yè)必須被復(fù)制第 二次。Eager（dirty）：僅僅轉(zhuǎn)移那些位于主存中且已被修改了的地址空間的頁(yè)。 虛地址空間的所有其他塊將在需要時(shí)才轉(zhuǎn)移。基于引用的復(fù)制（copy-on-reference）:這是Eager（dirt

3、y）的變體，只有在引用某頁(yè)時(shí)，該頁(yè)才 被取入。刷新（flushing）：通過(guò)把臟頁(yè)寫回磁盤，該進(jìn)程的頁(yè)可以從源機(jī)器的主 存中清除。這樣，在需要時(shí)可以從磁盤訪問(wèn)到頁(yè)，而不是從源節(jié)點(diǎn)的存儲(chǔ)器中訪 問(wèn)。15.3、搶占式和非搶占式進(jìn)程遷移的動(dòng)機(jī)是什么？答：非搶占式進(jìn)程遷移對(duì)于負(fù)載平衡是很有用的，它的優(yōu)點(diǎn)是能夠避免全面性進(jìn) 程遷移的開(kāi)銷，缺點(diǎn)是該方法對(duì)于負(fù)載分布的突然變化反應(yīng)不佳。15.4、為什么不可能確定真正的全局狀態(tài)？答：因?yàn)橄到y(tǒng)之間的通信延遲，不可能在系統(tǒng)范圍內(nèi)維護(hù)一個(gè)所有系統(tǒng)都隨時(shí)可用 的時(shí)鐘。而且，維護(hù)一個(gè)中央時(shí)鐘并讓所有本地時(shí)鐘與之保持精確同步，這在 技術(shù)上也是不現(xiàn)實(shí)的，因?yàn)榻?jīng)過(guò)一段時(shí)間后，

4、在各個(gè)本地時(shí)鐘之間就會(huì)產(chǎn)生一 些偏差，這將導(dǎo)致同步的丟失。15.5、集中式算法和分布式算法所實(shí)行的分布式互斥有何區(qū)別？答：在完全集中式算法中，一個(gè)節(jié)點(diǎn)被指定為控制節(jié)點(diǎn)，它控制對(duì)所有共享對(duì)象的 訪問(wèn)。當(dāng)任何進(jìn)程請(qǐng)求對(duì)一個(gè)臨界資源進(jìn)行訪問(wèn)時(shí)，就向本地資源控制進(jìn)程發(fā) 送一個(gè)請(qǐng)求，這個(gè)進(jìn)程接著向控制節(jié)點(diǎn)發(fā)送一條請(qǐng)求消息，當(dāng)共享對(duì)象可用時(shí)， 將返回一條許可消息。當(dāng)進(jìn)程結(jié)束使用資源后，向控制節(jié)點(diǎn)發(fā)送一條釋放消息。 在分布式算法中，互斥算法涉及到每個(gè)離散的實(shí)體之間的同步合作。15.6、定義兩種類型的分布式死鎖。答：在資源分配中產(chǎn)生的死鎖以及由于消息通信而產(chǎn)生的死鎖。習(xí)題：15.1、15.1節(jié)中的“進(jìn)程遷移機(jī)

5、制”小節(jié)描述了刷新策略。從源端的觀點(diǎn)來(lái)看，刷新像哪一種其他策略？從目標(biāo)端的觀點(diǎn)來(lái)看，刷新像哪一種其他策略？答案：a. Eager（dirty）：僅僅轉(zhuǎn)移那些位于主存中且已被修改了的地址空間的頁(yè)。虛地址 空間的所有其他塊將在需要時(shí)才轉(zhuǎn)移?；谝玫膹?fù)制（copy-on-reference）:這是Eager（dirty）的變體，只有在引用某 頁(yè)時(shí)，該頁(yè)才被取入。15.2、圖15.9聲稱所有4個(gè)進(jìn)程將順序a，q分派給兩條信息，即使q在a之前到達(dá)。分 析該算法以證明該聲明的真實(shí)性。答案：進(jìn)程P1開(kāi)始時(shí)時(shí)鐘的值為0。為了傳送消息a，它將時(shí)鐘加1并發(fā)送（a，1，1），第 一個(gè)數(shù)字值是時(shí)間戳，第二個(gè)是站點(diǎn)標(biāo)

6、識(shí)。同樣的，進(jìn)程P4也將自己的時(shí)鐘加1并 發(fā)送（q，1，4）。這兩個(gè)消息被第三個(gè)站點(diǎn)接受到。a和q具有相同的時(shí)間戳，但是 P1的數(shù)字標(biāo)識(shí)符要小于P4的數(shù)字標(biāo)識(shí)符（14）。因此，所有4個(gè)進(jìn)程將順序a，q 分派給兩條信息。15.3、對(duì)Lamport算法，有Pi可以保存它自己的一個(gè)Reply消息的傳輸?shù)那闆r存在嗎？答案：如果Pi已經(jīng)發(fā)出一個(gè)請(qǐng)求消息但還沒(méi)有收到相對(duì)應(yīng)的釋放信息，Pi可以保存它自己 的一個(gè)Reply消息的傳輸。15.4、對(duì)于RICA81的互斥算法：證明它實(shí)現(xiàn)了互斥。如果各消息沒(méi)有按照它們發(fā)送時(shí)的順序到達(dá)，則算法不能保證臨界區(qū)按照它們的請(qǐng) 求的順序執(zhí)行?？赡軙?huì)饑餓嗎？答案：a.如果一個(gè)已

7、經(jīng)請(qǐng)求進(jìn)入其臨界區(qū)的站點(diǎn)i收到了一個(gè)來(lái)自于所有其他站點(diǎn)的請(qǐng)求， 那么首先這個(gè)請(qǐng)求應(yīng)該是所有正在等待的請(qǐng)求中最舊的（在某種意義上是根據(jù)時(shí)間戳 排序來(lái)定義的）請(qǐng)求；其次比這個(gè)請(qǐng)求更早的臨界區(qū)請(qǐng)求已經(jīng)被完成。如果站點(diǎn)已 經(jīng)發(fā)出一個(gè)更早的請(qǐng)求或者它已經(jīng)進(jìn)入了臨界區(qū)，那么臨界區(qū)將不響應(yīng)站點(diǎn)i的請(qǐng)求。 b.進(jìn)入的請(qǐng)求全部按順序被服務(wù)；每一個(gè)請(qǐng)求都將在某段時(shí)間后成為最舊的然后 將會(huì)被服務(wù)。15.5、在令牌傳遞互斥算法中，用于重啟時(shí)鐘和糾正偏差的時(shí)間戳機(jī)制與分布式排隊(duì)算法中 的一樣嗎？如果不一樣，時(shí)間戳的功能是什么？答案：在令牌傳遞互斥算法中不考慮關(guān)于相互之間的重啟時(shí)間戳?xí)r鐘。拿給定的進(jìn)程Pi舉 個(gè)例子，時(shí)鐘

8、只被用于更新，一方面，request i通過(guò)請(qǐng)求消息的通信方式在其他進(jìn) 程中變化，另一方面，當(dāng)令牌類型的消息被傳輸時(shí)，token i會(huì)發(fā)生變化。所以時(shí)鐘 不是用于完全的順序請(qǐng)求，而是被當(dāng)作計(jì)數(shù)器使用，用來(lái)記錄多種進(jìn)程訪問(wèn)臨界區(qū)時(shí) 的時(shí)間戳，從而判斷Pi進(jìn)程進(jìn)入臨界區(qū)的的時(shí)間戳即token i的值是否小于它的請(qǐng)求 值，即對(duì)于Pj來(lái)說(shuō)是request, i的值。max函數(shù)被用于接受請(qǐng)求的進(jìn)程中的作用是如 果一些進(jìn)程要被遞送出順序隊(duì)列的話，只有最新的馬進(jìn)程的請(qǐng)求被考慮。15.6、對(duì)于令牌傳遞互斥算法，證明它保證互斥。避免死鎖。是公平的。答案：a.如果在任何情況下數(shù)值為真的token_present變

9、量數(shù)目不超過(guò)1,則保證了互斥的實(shí) 現(xiàn)。自這個(gè)條件成為初始化條件后，很明顯它將貫徹在整個(gè)程序之中。首先考慮整個(gè) 過(guò)程的首部，token_presenti是變量旦的變量值。當(dāng)Pi接收到令牌的時(shí)候?qū)i的變量 值從false變?yōu)閠rue。如果我們考慮pj將令牌傳送出去后的尾部處理，我們可以知道， 只有當(dāng)token_presentj將值變?yōu)閠rue并且P.在將令牌送出之前把這個(gè)值變?yōu)閒alse的時(shí) 候，P.才能進(jìn)行將令牌傳送出去后的后期處理。假設(shè)所有的進(jìn)程都希望進(jìn)入臨界區(qū)但是它們都沒(méi)有令牌，所以它們都處于阻塞狀態(tài)，并等待著令牌的到來(lái)。因此令牌是出于傳遞中的。它會(huì)經(jīng)過(guò)有限長(zhǎng)時(shí)間后傳遞給 一個(gè)進(jìn)程，并激活這個(gè)進(jìn)程。經(jīng)過(guò)有限長(zhǎng)時(shí)間釋放令牌時(shí)所有相關(guān)消息會(huì)被傳送出去，這一點(diǎn)保證了公平性。臨界區(qū)使用的尾部處理要求P.將令牌傳送給下面第一個(gè)進(jìn)程P。它選擇接受令牌的下一ij個(gè)進(jìn)程的方法是按照.=i+1, i+2, . . ., n, 1, . . ., i-1中誰(shuí)的請(qǐng)求已經(jīng)傳送給鳥(niǎo)的順序進(jìn)行 的。如果對(duì)于所有的信息傳輸延遲是有限的(比如：沒(méi)有信息遺失)。所有的程序獲悉某個(gè)P.希望進(jìn)入臨界區(qū)的消息而