【文章內容簡介】 還未裝入內存，則發(fā)生缺頁，此時需記錄缺頁的次數，并將相應頁調入內存。如果 4個內存塊均已裝入該作業(yè)，則需進行頁面置換，最后顯示其物理地址，并轉下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最佳置換 （ OPT）算法。 提示 : （ 1）通過隨機數產生一個指令序列，共 320條指令。指令的地址按下述 原則生成： ① 50%的指令是順序執(zhí)行的； ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機選取一起點 m； ② 順序執(zhí)行一條指令，即執(zhí)行地址為 m+1的指令； ③ 在前地址 [0， m+1]中隨機選取一條指令并執(zhí)行，該指令的地址為 m′ ； ④ 順序執(zhí)行一條指令，其地址為 m′ +1 的指令； ⑤ 在后地址 [m′ +2， 319]中隨機選取一條指令并執(zhí)行； ⑥ 重復上述步驟①～⑤，直到執(zhí)行 320 次指令。 （ 2）將指令序列變換為頁地 址流 ① 設頁面大小為 1K； ② 用戶內存容量為 4頁到 32 頁； ③ 用戶虛存容里為 32K。 在用戶虛存中，按每 K 存放 10條指令排列虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條～第 9 條指令為第 0 頁（對應虛存地址為 [0， 9]）； 第 10 條～第 19條指令為第 1頁（對應虛存地址為 [10， 19]）； ?? ?? 13 第 310 條～第 319 條指令為第 31 頁（對應虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最佳置換 （ OPT） 算法在不同內存容量下的命中率。 其中，命中率 =1頁面失 效次數 /頁地址流長度 題目十六： 請求調頁存儲管理方式的模擬 4 1．設計 目的 通過對頁面、頁表、地址轉換和頁面置換過程的模擬，加深對請求調頁系統(tǒng)的原理和實現過程的理解。 2．設計 內容 1） 假設每個頁面中可存放 10 條指令，分配給作業(yè)的內存塊數為 4。 2） 用 C 語言模擬一個作業(yè)的執(zhí)行過程，該作業(yè)共有 320 條指令，即它的地址空間為 32 頁，目前它的所有頁都還未調入內存。在模擬過程中，如果所訪問的指令已在內存，則顯示其物理地址，并轉下一條指令。如果所訪問的指令還未裝入內存，則發(fā)生缺頁，此時需記錄缺頁的次數，并將 相應頁調入內存。如果 4個內存塊均已裝入該作業(yè)，則需進行頁面置換，最后顯示其物理地址，并轉下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最少訪問 （ LFU）算法。 提示 : （ 1）通過隨機數產生一個指令序列，共 320條指令。指令的地址按下述原則生成： ① 50%的指令是順序執(zhí)行的； ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機選取一起點 m； ② 順序 執(zhí)行一條指令，即執(zhí)行地址為 m+1的指令； ③ 在前地址 [0， m+1]中隨機選取一條指令并執(zhí)行，該指令的地址為 m′ ； ④ 順序執(zhí)行一條指令，其地址為 m′ +1 的指令； ⑤ 在后地址 [m′ +2， 319]中隨機選取一條指令并執(zhí)行； ⑥ 重復上述步驟①～⑤，直到執(zhí)行 320 次指令。 （ 2）將指令序列變換為頁地址流 14 ① 設頁面大小為 1K； ② 用戶內存容量為 4頁到 32 頁； ③ 用戶虛存容里為 32K。 在用戶虛存中，按每 K 存放 10條指令排列虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條～第 9 條指令為第 0 頁（對應虛存 地址為 [0， 9]）； 第 10 條～第 19條指令為第 1頁（對應虛存地址為 [10， 19]）； ?? ?? 第 310 條～第 319 條指令為第 31 頁（對應虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最少訪問 （ LFU） 算法在不同內存容量下的命中率。 其中，命中率 =1頁面失效次數 /頁地址流長度 題目十七： 請求調頁存儲管理方式的模擬 5 1．設計 目的 通過對頁面、頁表、地址轉換和頁面置換過程的模擬，加深對請求調頁系統(tǒng)的原理和實現過程的理解。 2．設計 內容 1） 假設每個頁面中可存 放 10 條指令，分配給作業(yè)的內存塊數為 4。 2） 用 C 語言模擬一個作業(yè)的執(zhí)行過程，該作業(yè)共有 320 條指令，即它的地址空間為 32 頁，目前它的所有頁都還未調入內存。在模擬過程中，如果所訪問的指令已在內存，則顯示其物理地址，并轉下一條指令。如果所訪問的指令還未裝入內存，則發(fā)生缺頁，此時需記錄缺頁的次數，并將相應頁調入內存。如果 4個內存塊均已裝入該作業(yè)，則需進行頁面置換，最后顯示其物理地址，并轉下一條指令。 在所有 320 指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。 3） 置換算法： 最近最不經常使用 （ NRU）算法。 提示 : （ 1）通過隨機數產生一個指令序列，共 320條指令。指令的地址按下述原則生成： ① 50%的指令是順序執(zhí)行的； 15 ② 25%的指令是均勻分布在前地址部分； ③ 25%的指令是均勻分布在后地址部分； 具體的實施方法是： ① 在 [0， 319]的指令地址之間隨機選取一起點 m； ② 順序執(zhí)行一條指令，即執(zhí)行地址為 m+1的指令； ③ 在前地址 [0， m+1]中隨機選取一條指令并執(zhí)行，該指令的地址為 m′ ； ④ 順序執(zhí)行一條指令，其地址為 m′ +1 的指令； ⑤ 在后地址 [m′ +2， 319]中隨機 選取一條指令并執(zhí)行； ⑥ 重復上述步驟①～⑤，直到執(zhí)行 320 次指令。 （ 2）將指令序列變換為頁地址流 ① 設頁面大小為 1K； ② 用戶內存容量為 4頁到 32 頁； ③ 用戶虛存容里為 32K。 在用戶虛存中，按每 K 存放 10條指令排列虛存地址，即 320 條指令在虛存中的存放方式為： 第 0 條～第 9 條指令為第 0 頁（對應虛存地址為 [0， 9]）； 第 10 條～第 19條指令為第 1頁（對應虛存地址為 [10， 19]）； ?? ?? 第 310 條～第 319 條指令為第 31 頁（對應虛存地址為 [310， 319]）。 按以上方式，用戶指令可組成 32 頁。 （ 3）計算 最近最不經常使用 （ NRU） 算法在不同內存容量下的命中率。 其中，命中率 =1頁面失效次數 /頁地址流長度 題目十八： P、 V 操作及進程同步的實現 1 1．設計 目的 掌握信號量通信方式的一般方法，了解系統(tǒng)實現 “阻塞 ”和 “喚醒 ”功能的方法和技巧。同時掌握進程同步和互斥的概念及實現技術。 2．設計 內容 16 1）用語言編程實現 P、 V 原語并用 P、 V 原語描述如下 理發(fā)師 顧客 問題： 有一個理發(fā)師，一把理發(fā)椅和 n 把提供給等候理發(fā)的顧客座的椅子。如果沒有顧客，則理發(fā)師便在理發(fā)椅子上睡覺；當第一個顧客到來時， 必須喚醒該理發(fā)師進行理發(fā)；如果理發(fā)師正在理發(fā)時又有顧客到來，則如果有空椅子可坐，他就坐下來等待，如果沒有空椅子，他就離開理發(fā)店。 為理發(fā)師和顧客各編一段程序描述他們的行為，要求不能帶有競爭條件，試用 P、 V 操作實現。 2）實驗要求及說明 ① 定義信號量并將 P、 V 操作定義為帶參數 ② 以輸出字符串的形式表示理發(fā)師和顧客的行為。 ③ 設計適當的數據結構和函數描述顧客等待隊列和 “喚醒 ”理發(fā)師理發(fā)過程，以及沒有顧客時的 “阻塞 ”理發(fā)師過程。 ④ 編程時需考慮理發(fā)師和顧客對應的程序是并發(fā)操作的。 提示：可利用隨機函數模擬 并發(fā)操作。 ⑤ 理發(fā)師和顧客兩個進程各自調用一個函數模擬生產及消費的操作。 題目十九： P、 V 操作及進程同步的實現 2 1．設計 目的 掌握信號量通信方式的一般方法，了解系統(tǒng)實現 “阻塞 ”和 “喚醒 ”功能的方法和技巧。同時掌握進程同步和互斥的概念及實現技術。 2．設計 內容 用語言編程實現 P、 V 原語并用 P、 V 原語 哲學家就餐 問題： 為每個哲學家 各編一段程序描述他們的行為，試用 P、 V 操作實現。 題目二十：銀行家算法 1．設計 目的 1）了解多道程序系統(tǒng)中，多個進程并發(fā)執(zhí)行的資源分配。 2）掌握銀行家算法，了解資源在進 程并發(fā)執(zhí)行中的資源分配情況。 3）掌握預防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。 2．設計 內容 設計一個 n 個并發(fā)進程共享 m個系統(tǒng)資源的程序以實現銀行家算法。要求： 1） 簡單的選擇界面； 2） 能顯示當前系統(tǒng)資源的占用和剩余情況。 3） 為進程分配資源，如果進程要求的資源大于系統(tǒng)剩余的資源，不與分配并且提示分配不成功； 4） 撤銷作業(yè)，釋放資源。 編寫和調試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產生的條件，并采用適當的算法，有效地防止和避免死鎖的發(fā)生。 17 銀行家算法分配資源的原則是：系統(tǒng)掌握每個進程對資源的最大需求量，當進程要求 申請資源時，系統(tǒng)就測試該進程尚需資源的最大量，如果系統(tǒng)中現存的資源數大于或等于該進程尚需求資源最大量時，就滿足進程的當前申請。這樣就可以保證至少有一個進程可能得到全部資源而執(zhí)行到結束，然后歸還它所占有的全部資源供其它進程使用。 銀行家算法中的數據結構 (1)可利用資源向量 Available(一維數組 ) 是一個含有 m個元素，其中的每一個元素代表一類