第15章分布式程序管理
複習題：
15.1、 討論實現程序遷移的原因。
答：負載共享：通過將程序從負載較重的系統遷移到負載較輕的系統，負載就會得到平衡，從而提高整體效能。
通訊效能：可以將互動密集的多個程序移動到同一節點上，以減少因為它們之間的互動而帶來的通訊開銷。同樣，當乙個程序在某些檔案或某組檔案上執行資料分析，且檔案的大小比程序要大很多時，將該程序移動到資料端也許是更有利的。
可用性：需要長時間執行的程序，在得到錯誤的預先通知時，或者在預定的關機時間之前，為了能夠存活下來，可能需要遷移到其他機器中。如果作業系統提供了這樣的通知，則那些需要繼續執行的程序可以遷移到另乙個系統上，或者保證在稍後的某個時間在當前系統上能重新啟動。
特殊功能的使用：程序的遷移可以充分利用特定節點上獨特的硬體或軟體功能。
15.2、 在程序遷移過程中，程序位址空間是如何處理的？
答：下列策略可能被採用：eager（all）：
在遷移時轉移整個位址空間。預先複製（precopy）：程序繼續在源節點上執行，而位址空間已經複製到了目標節點上。
在預先複製的過程中，源節點上的某些頁有可能又被修改，這些頁必須被複製第二次。eager（dirty）：僅僅轉移那些位於主存中且已被修改了的位址空間的頁。
虛位址空間的所有其他塊將在需要時才轉移。基於引用的複製（copy-on-reference）：這是eager（dirty）的變體，只有在引用某頁時，該頁才被取入。
重新整理（flushing）：通過把髒頁寫回磁碟，該程序的頁可以從源機器的主存中清除。這樣，在需要時可以從磁碟訪問到頁，而不是從源節點的儲存器中訪問。
15.3、 搶占式和非搶占式程序遷移的動機是什麼？
答：非搶占式程序遷移對於負載平衡是很有用的，它的優點是能夠避免全面性程序遷移的開銷，缺點是該方法對於負載分布的突然變化反應不佳。
15.4、 為什麼不可能確定真正的全域性狀態？
答：因為系統之間的通訊延遲，不可能在系統範圍內維護乙個所有系統都隨時可用的時鐘。而且，維護乙個**時鐘並讓所有本地時鐘與之保持精確同步，這在技術上也是不現實的，因為經過一段時間後，在各個本地時鐘之間就會產生一些偏差，這將導致同步的丟失。
15.5、 集中式演算法和分布式演算法所實行的分布式互斥有何區別？
答：在完全集中式演算法中，乙個節點被指定為控制節點，它控制對所有共享物件的訪問。當任何程序請求對乙個臨界資源進行訪問時，就向本地資源控制程序傳送乙個請求，這個程序接著向控制節點傳送一條請求訊息，當共享物件可用時，將返回一條許可訊息。
當程序結束使用資源後，向控制節點傳送一條釋放訊息。在分布式演算法中，互斥演算法涉及到每個離散的實體之間的同步合作。
15.6、 定義兩種型別的分布式死鎖。
答：在資源分配中產生的死鎖以及由於訊息通訊而產生的死鎖。
習題：15.1、15.1節中的「程序遷移機制」小節描述了重新整理策略。
a.從源端的觀點來看，重新整理像哪一種其他策略？
b.從目標端的觀點來看，重新整理像哪一種其他策略？
答案：a. eager（dirty）：僅僅轉移那些位於主存中且已被修改了的位址空間的頁。虛位址空間的所有其他塊將在需要時才轉移。
b. 基於引用的複製（copy-on-reference）：這是eager（dirty）的變體，只有在引用某頁時，該頁才被取入。
15.2、圖15.9聲稱所有4個程序將順序分派給兩條資訊，即使q在a之前到達p3。分析該演算法以證明該宣告的真實性。
答案：程序p1開始時時鐘的值為0。為了傳送訊息a，它將時鐘加1並傳送（a，1，1），第乙個數字值是時間戳，第二個是站點標識。
同樣的，程序p4也將自己的時鐘加1並傳送（q，1，4）。這兩個訊息被第三個站點接受到。a和q具有相同的時間戳，但是p1的數字識別符號要小於p4的數字識別符號（1<4）。
因此，所有4個程序將順序分派給兩條資訊。
15.3、對lamport演算法，有pi可以儲存它自己的乙個reply訊息的傳輸的情況存在嗎？
答案：如果pi已經發出乙個請求訊息但還沒有收到相對應的釋放資訊，pi可以儲存它自己的乙個reply訊息的傳輸。
15.4、對於[rica81]的互斥演算法：
a.證明它實現了互斥。
b.如果各訊息沒有按照它們傳送時的順序到達，則演算法不能保證臨界區按照它們的請求的順序執行。可能會飢餓嗎？
答案：a.如果乙個已經請求進入其臨界區的站點i收到了乙個來自於所有其他站點的請求，那麼首先這個請求應該是所有正在等待的請求中最舊的（在某種意義上是根據時間戳排序來定義的）請求；其次比這個請求更早的臨界區請求已經被完成。
如果站點j已經發出乙個更早的請求或者它已經進入了臨界區，那麼臨界區將不響應站點i的請求。
b. 進入的請求全部按順序被服務；每乙個請求都將在某段時間後成為最舊的, 然後將會被服務。
15.5、在令牌傳遞互斥演算法中，用於重啟時鐘和糾正偏差的時間戳機制與分布式排隊演算法中的一樣嗎？如果不一樣，時間戳的功能是什麼？
答案：在令牌傳遞互斥演算法中不考慮關於相互之間的重啟時間戳時鐘。拿給定的程序pi舉個例子，時鐘只被用於更新，一方面，request [i]通過請求訊息的通訊方式在其他程序中變化，另一方面，當令牌型別的訊息被傳輸時，token [i]會發生變化。
所以時鐘不是用於完全的順序請求，而是被當作計數器使用，用來記錄多種程序訪問臨界區時的時間戳，從而判斷pi程序進入臨界區的的時間戳即token [i]的值是否小於它的請求值，即對於pj來說是requestj [i]的值。max函式被用於接受請求的程序中的作用是如果一些程序要被遞送出順序佇列的話，只有最新的pj程序的請求被考慮。
15.6、對於令牌傳遞互斥演算法，證明它
a.保證互斥。
b.避免死鎖。
c.是公平的。
答案：a.如果在任何情況下數值為真的token_present變數數目不超過1，則保證了互斥的實現。
自這個條件成為初始化條件後，很明顯它將貫徹在整個程式之中。首先考慮整個過程的首部，token_presenti是變數pi的變數值。當pi接收到令牌的時候將pi的變數值從false變為true。
如果我們考慮pj將令牌傳送出去後的尾部處理，我們可以知道，只有當token_presentj將值變為true並且pj在將令牌送出之前把這個值變為false的時候，pj才能進行將令牌傳送出去後的後期處理。
b.假設所有的程序都希望進入臨界區但是它們都沒有令牌，所以它們都處於阻塞狀態，並等待著令牌的到來。因此令牌是出於傳遞中的。它會經過有限長時間後傳遞給乙個程序，並啟用這個程序。
c.經過有限長時間釋放令牌時所有相關訊息會被傳送出去，這一點保證了公平性。臨界區使用的尾部處理要求pi將令牌傳送給下面第乙個程序pj。
它選擇接受令牌的下乙個程序的方法是按照j = i+1, i+2, . . .
, n, 1, . . .
, i-1中誰的請求已經傳送給pi的順序進行的。如果對於所有的資訊傳輸延遲是有限的（比如：沒有資訊遺失）。
所有的程式獲悉某個pj希望進入臨界區的訊息而且當pj輪到的機會來的時候會同意其進入臨界區。
15.7、在圖15.11（b）中，解釋為什麼第二行不能簡單地讀做「request(j) = t」。
答案：接收乙個來自程序pj的請求有著更新本地變數的作用即函式request(j)，它記錄著程序pj最新請求的時間。而函式max保證了正確指令得到維護。
作業系統精髓與設計原理第11章IO管理和磁碟排程
11.5在磁碟讀或寫時有哪些延遲因素？尋道時間，旋轉延遲，傳送時間 11.6簡單定義圖11.7中描述的磁碟排程策略。fifo 按照先來先服務的順序處理佇列中的專案。sstf 選擇使磁頭臂從當前位置開始移動最少的磁碟i o請求。scan 磁頭臂僅僅沿乙個方向移動，並在途中滿足所有未完成的請求，直到它到...
第3章答案 作業系統基礎
1.計算機作業系統屬於 b a.應用軟體 b.系統軟體 c.工具軟體 d.文字處理軟體 2.作業系統負責管理計算機的 c a.程式b.作業c.資源d.程序 3.在計算機系統中配置作業系統的主要目的是 b a.增強計算機系統的功能b.提高系統資源的利用率 c.提高系統的執行速度d.合理組織系統的工作流...
《作業系統原理》課程設計報告
作業系統原理 課程設計報告書 題目 動態分割槽演算法 最佳適應演算法 專業 電腦科學與技術 學號學生姓名 指導教師 完成日期 2016 06 09 一 題目及要求 實現對動態分割槽演算法中最佳適應演算法 演算法的模擬。編寫程式，提供乙個介面，使用者輸入記憶體初始狀態以及不同長度作業對記憶體的釋放要求...